Simple RSA Encryption with Mathematica

RSA is a widely used public-key algorithm that relies on a pair of keys — a public key (e) for encryption and a private key (d) for decryption. More information can be found on Wikipedia and Understanding Cryptography Textbook. For testing purposes and to explore how Mathematica handles RSA encryption, I would like to write a small script that encrypts and decrypts data using RSA with small numbers. You can download Mathamatica notebook and also sample output.

1. Generate large prime number p and q, Mathematica has built in function RandomPrime that generate prime number up to nth value.

maxLen = 100
p = RandomPrime[maxLen]
q = RandomPrime[maxLen]

2. Compute n = p * q

n = p * q

3. Compute Phi(n) = (p-1) * (q-1)

qn = (p - 1)*(q - 1)

4. Choose a public key (e), e in {1, 2, …., Phi(n)-1
such that gcd(e, [Phi](n)) = 1

e = RandomPrime[qn-1]
GCD[e, qn]

5. Choose private key such that d * e = 1 mod Phi(n), Mathematica has built in function for modular inverses ModularInverse

d = ModularInverse[e,qn]

6. Given with private key d, and n, decryption of cipher y, is x = y^d mod n

x' = Mod [Power[y, d], n ]
x == x'