## RSA (Rivest–Shamir–Adleman) - Cryptosystem

### Algorithm

#### 1. Choose two distinct prime numbers p and q. 

<p> For security purposes, the integers p and q should be chosen at random, and should be similar in magnitude but differ in length by a few digits to make factoring harder. Prime integers can be efficiently found using a primality test. </p>

#### 2. Compute n = pq.

<p> n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length. </p>

#### 3. Compute Φ(n) = lcm(Φ(p), Φ(q)) = lcm(p − 1, q − 1)

<p> Φ is Carmichael's totient function. This value is kept private. </p>

#### 4. Choose an integer e such that 1 < e < Φ(n) and gcd(e, Φ(n)) = 1; i.e., e and Φ(n) are coprime.

<p> Note that if e is prime and also not a divisor of Φ(n), so e and Φ(n) are coprime. </p>

#### 5. Determine d as (e*d) %  Φ(n) = 1

<p> d is the modular multiplicative inverse of e (modulo Φ(n)).</p>

#### To encrypt:

<p> c(m) = m^e % n </p>

<p> The <b>public key</b>, composed by e and n, is used to encrypt the message. </p>

#### To decrypt:

<p> m(c) = m^d % n </p>

<p> The <b>private key</b>, composed by d and n, is used to decrypt the encrypted message. </p>

#### References:

[Wikipedia - RSA (cryptosystem)](https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29)

[Wikipedia - Carmichael function](https://en.wikipedia.org/wiki/Carmichael_function)

[Sympy.org](http://www.sympy.org/pt/index.html)

[Wikibooks - Extended Euclidean algorithm](https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm)


```python
from random import randint
import sympy
import numpy

# return the smallest prime in range [n,n+1000)
# return -1 if it doesn't exist
def next_prime(n):
    for i in range(n,n+1000):
        if (sympy.isprime(i)):
            return i
    return -1

# Extended Euclidean algorithm
def egcd(a, b):
    if a != 0:
        x, y, z = egcd(b % a, a)
        return (x, z - (b // a) * y, y)
    return (b, 0, 1)

# Modular Inverse
# return -1 if it doesn't exist
def mod_inv(a, b):
    x, y, _ = egcd(a, b)
    if x != 1:
        return -1
    else:
        return y % b

def encrypt(m,e,n):
    return pow(m,e,n)
    
def decrypt(c,d,n):
    return pow(c,d,n)


## 1. p and q

p = -1
while(p == -1):
    p = next_prime(randint(10**130,10**150))

q = -1
while(q == -1):
    q = next_prime(randint(10**100,10**120))
    if (q == p):
        q = -1

if(randint(0,9) % 2 == 0):
    aux = p
    p = q
    q = aux

print("p and q:")
print(hex(p))
print(hex(q))

## 2. n

n = p*q

print("\nn:")
print(hex(n))

## 3. phi

phi = sympy.lcm((p-1),(q-1))

print("\nphi(n):")
print(hex(phi))


## 4. e

e = -1
while(e == -1):
    e = next_prime(randint(2,phi))
    if e >= phi:
        e = -1
    elif e%phi == 0:
        e = -1

print("\ne:")
print(hex(e))

## 5. d

d = int(mod_inv(e, phi))

if d == -1:
    raise Exception('Modular inverse does not exist, but don`t worry, just run it again. =)')

print("\nd:")
print(hex(d))

## Encrypt:

c = encrypt(42,e,n)
print("\nmessage encrypted:")
print(hex(c))

## Decrypt:

m = decrypt(c,d,n)
print("\nmessage decrypted:")
print(m)

```

    p and q:
    0x4972224d37eeec694dbc80cdb3b88052a29faa76b113148ad06f89995c3a7fcdb97cbe523efadde3a0b889e7f8094b893b255c5c7a05d7c99819c9c3e9d29
    0x3e5810c28da948c519eb2b92dccc0f1afc654f60bc1ad1588514a5cf20b0ee057117cc0071499f887d56e9477be11a12f23b
    
    n:
    0x11e2e859715e5783e98e5c5d6d5d73817889d24062c2f6c3212a495b072cc1a30fbac63d61d0221094d0c31731a3d4ed56a36d57374822025b1f9626e90c087607d3da2127815f5f38216729e9fe211b8c6e37b702828131a57555c8d0b23f3d584e65118d537fc2f28b2173169e0fa73
    
    phi(n):
    0x8f1742cb8af2bc1f4c72e2eb6aeb9c0bc44e92031617b61909524ad839660d187dd631eb0e811084a68618b98d1ea76ab5191f28a7d7509b75b2435341f286c033a8753743f2e56b86eb476cfb98a8d5bd5393c4b8d5cf2be9a61829bf4f8114802916bcb7f3ef3d61688cd9d9c7b588
    
    e:
    0x5645c37219fad185353336fd4f4aa8a1d95ecfe4d083ef88e064082ddc892eee4db2127436c07be7edeed3fb96cf941531ac9ea5bb4b17bb5bb8854b42c67f6998038558b7f3033cf2c84cfd598a3218e3d1fa34901767143c26c744d80bc88fb691ebfe975279f1aba94fd56924ce9d
    
    d:
    0x3d0cf1214c4b09200b502b82b053d719e78bb40a1bbfbe8314a4faaa0fecd828273b559921ba436d6ae979c7d6aeedac2255a76ec54d61e0476091101b2f2c3de4a31e2f00061ad351bad807dfbe4a55f5e3e4ef94e3b65f89f3d03ba7f79fadfb17a7a9113462fa256b4c2201f32a6d
    
    message encrypted:
    0x1036f1372d8acabac7b61cc594e93393c9a30754d8270134da09a71cdbd1aa62591f132ef877a21e595996b90ab8fb3f2361afd44a5665f8ff51f86a1ea35f2f5144d9afeac125c48696bb3fd6dd034a3cffb423cc57d2a706cbbc6833344272be898d53d14bdc459b6b958128d96beaa
    
    message decrypted:
    42


ff164429ba61533d3af1420af58c32a7556be6c7
ipynb
Jupyter Notebook
RSA.ipynb
vdbalbom/RSA
cdc9189c6f6a6170a41d30ea8ed4ba1f5f5a30ed
MIT
2018-06-15T10:47:31.000Z
2019-06-13T10:17:08.000Z
RSA.ipynb
vdbalbom/RSA
cdc9189c6f6a6170a41d30ea8ed4ba1f5f5a30ed
MIT
RSA.ipynb
vdbalbom/RSA
cdc9189c6f6a6170a41d30ea8ed4ba1f5f5a30ed
MIT
Qwen/Qwen-72B
1. YES
2. YES