~/Writing Your Own RSA Encryption Scheme

May 18, 2022

RSA is a public key cryptography algorithm based on the difficulty of factoring large integers. To write your own scheme, follow these steps.

Key Generation

1. Pick two large random primes p and q.
2. Compute n = p * q.
3. Compute Euler’s totient phi_n = (p - 1) * (q - 1).
4. Choose integer e such that 1 < e < phi_n, and gcd(e, phi_n) = 1, often 65537.
5. Calculate d, the modular inverse of e modulo phi_n.

The public key is (n, e) and the private key is d.

Encryption
To encrypt message m, compute
c = m^e mod n

Decryption
To decrypt ciphertext c, compute
m = c^d mod n

Example in Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# Note: Use real cryptographic libraries in production
p = 61
q = 53
n = p * q
phi_n = (p - 1)*(q - 1)
e = 17
d = pow(e, -1, phi_n)
m = 42
c = pow(m, e, n)
m_decrypted = pow(c, d, n)
print(m_decrypted)

Security Notes
Never use small primes or implement RSA without cryptographic libraries like PyCryptodome. Always use padding such as OAEP for real systems.

For more details see Wikipedia RSA details.