Simple RSA Encryption

RSA (Rivest–Shamir–Adleman) by example

Mehmet Ali Erturk - https://mehmetalierturk.com

Introduction

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.

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 ϕ(n) = (p-1) * (q-1)

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

4. Choose a public key (e),   e ϵ  = {1, 2, ...., ϕ(n)-1 }
such that gcd(e,  ϕ(n)) = 1

e = RandomPrime[qn-1]

GCD[e, qn]

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

d = ModularInverse[e,qn]

Mod[e *d, 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'