Public-Key Crypto-System

Rivest, Shamir, Adleman (RSA)
Public-Key Crypto-System
● Based on the fact that finding large (e.g. 100
digit) prime numbers is easy, but factoring
the product of two such numbers appears
computationally infeasible
● Choose very large prime numbers P and Q
– N = P x Q
– N is public; P, Q are secret

● Euler totient: Phi(N) = (P-1)(Q-1) = Number
of integers less than N & relatively prime to N

● Next, choose E in [2, Phi(N)-1], E is public

● A message is represented as a sequence
M1, M2, M3..., where each M in [0, N-1]

● Encryption: C = ME mod N

● Using the secret Phi(N), A can compute D
such that ED = 1 mod Phi(N)

● ED = k x Phi(N) + 1

● Then, for any X < N, Xk x Phi(N)+1 = X mod N

● Decryption: CD = MED = Mk x Phi(N)+1 = M mod N

● Example: Choose P = 17, Q = 31
– N = 527, Phi(N) = 480
– Choose E = 7, then D = 343
– If M = 2, Encryption: C = 128
– Decryption: D = CD mod N = 128343 mod 527 = 2