11 Encryption using RSA

Procedure Keygen $(1^{\lambda })$

01: Choose two random λ/2-bit primes p and q
02: n = p · q
03: ϕ = (p − 1)(q − 1)
04: Select e such that 1 < e < ϕ and gcd(e, ϕ) = 1
05: Compute d such that 1 < d < ϕ and (e · d) ≡ 1 mod ϕ
06: Set PK = (e, n)
07: Set SK = (d, n)
08: return (PK, SK)

Procedure Encrypt(PK ,m)

// Assume m ∈ ℤₙ* (i.e., m is invertible mod n)
Procedure Encrypt(m, PK = (e, n))
01: c = m^e mod n
02: return c

Procedure Decrypt(SK, c)

Procedure Decrypt(c, SK = (d, n))
01: m = c^d mod n
02: return m

• RSA security depends on hardness of finding $d$ from $e$, $n$; Related to hardness of factoring of $n$.
• The textbook algorithm are deterministic. In practice, some random padding is used.
• Shor’s quantum algorithm can solve factoring in polynomial time. However, a quantum computer of required capacity is still quite far away in the future.
• Wikipedia says $m<n$ would work. Strictly speaking, it is required that $gcd(m,n)=1$. On the other hand, finding a $m<n$ such that $gcd(m,n)>1$ will lead to finding $p$ or $q$, and breaking the system.
• Wikipedia says any $m<n$ would work. Strictly speaking, it is required that $gcd(m,n)=1$. On the other hand, finding a $m<n$ such that $gcd(m,n)>1$ will lead to finding p or q, and breaking the system.