RSA

Wikipedia · RSA (cryptosystem) · CC BY-SA 4.0

RSA is an asymmetric cipher: the encryption key (public) and decryption key (private) are different. Anyone can encrypt a message with the public key, but only the private key holder can decrypt it. Security rests on the difficulty of factoring the product of two large primes. The math works because of Euler's theorem: m^ed mod n = m when ed = 1 mod phi(n).

Key generation

Pick two large primes p and q. Compute n = pq and phi(n) = (p-1)(q-1). Pick e coprime to phi(n) (commonly 65537). Compute d = e^-1 mod phi(n) using the extended Euclidean algorithm. Public key: (e, n). Private key: d. Discard p, q, phi(n).

Scheme

; RSA key generation with small primes

(define p 61)
(define q 53)
(define n (* p q))              ; 3233
(define phi (* (- p 1) (- q 1))) ; 3120

(display "p = ") (display p) (newline)
(display "q = ") (display q) (newline)
(display "n = p * q = ") (display n) (newline)
(display "phi(n) = (p-1)(q-1) = ") (display phi) (newline)

;; Choose e coprime to phi
(define e 17)

;; Extended Euclidean algorithm to find d = e^(-1) mod phi
(define (extended-gcd a b)
  (if (= a 0)
    (list b 0 1)
    (let* ((result (extended-gcd (modulo b a) a))
           (g (car result))
           (x (cadr result))
           (y (caddr result)))
      (list g (- y (* (quotient b a) x)) x))))

(define (mod-inverse a m)
  (let* ((result (extended-gcd a m))
         (g (car result))
         (x (cadr result)))
    (modulo x m)))

(define d (mod-inverse e phi))

(display "e = ") (display e) (newline)
(display "d = e^(-1) mod phi = ") (display d) (newline)
(display "Check: e * d mod phi = ")
(display (modulo (* e d) phi))  ; should be 1

; RSA key generation with small primes

(define p 61)
(define q 53)
(define n (* p q))              ; 3233
(define phi (* (- p 1) (- q 1))) ; 3120

(display "p = ") (display p) (newline)
(display "q = ") (display q) (newline)
(display "n = p * q = ") (display n) (newline)
(display "phi(n) = (p-1)(q-1) = ") (display phi) (newline)

;; Choose e coprime to phi
(define e 17)

;; Extended Euclidean algorithm to find d = e^(-1) mod phi
(define (extended-gcd a b)
  (if (= a 0)
    (list b 0 1)
    (let* ((result (extended-gcd (modulo b a) a))
           (g (car result))
           (x (cadr result))
           (y (caddr result)))
      (list g (- y (* (quotient b a) x)) x))))

(define (mod-inverse a m)
  (let* ((result (extended-gcd a m))
         (g (car result))
         (x (cadr result)))
    (modulo x m)))

(define d (mod-inverse e phi))

(display "e = ") (display e) (newline)
(display "d = e^(-1) mod phi = ") (display d) (newline)
(display "Check: e * d mod phi = ")
(display (modulo (* e d) phi))  ; should be 1

Encrypt and decrypt

To encrypt message m: compute c = m^e mod n. To decrypt ciphertext c: compute m = c^d mod n. This works because m^ed mod n = m (by Euler's theorem, since ed = 1 mod phi(n)).

Scheme

; RSA encrypt and decrypt

(define (mod-exp base exp m)
  (let loop ((result 1) (b (modulo base m)) (e exp))
    (if (= e 0) result
        (loop (if (odd? e) (modulo (* result b) m) result)
              (modulo (* b b) m)
              (quotient e 2)))))

(define n 3233)
(define e 17)
(define d 2753)  ; computed in key generation

(define message 65)  ; 'A'

;; Encrypt: c = m^e mod n
(define ciphertext (mod-exp message e n))
(display "Message:    ") (display message) (newline)
(display "Ciphertext: ") (display ciphertext) (newline)

;; Decrypt: m = c^d mod n
(define recovered (mod-exp ciphertext d n))
(display "Recovered:  ") (display recovered) (newline)
(display "Round-trip? ") (display (= message recovered)) (newline)

;; Try another message
(define msg2 42)
(define enc2 (mod-exp msg2 e n))
(define dec2 (mod-exp enc2 d n))
(display "42 -> ") (display enc2) (display " -> ")
(display dec2) (display " (round-trip: ")
(display (= msg2 dec2)) (display ")")

Why it works: Euler's theorem

Euler's theorem states: if gcd(m, n) = 1, then m^phi(n) mod n = 1. Since ed = 1 mod phi(n), we can write ed = 1 + k*phi(n) for some integer k. Then m^ed = m^{1 + k*phi(n)} = m * (m^phi(n))^k = m * 1^k = m (mod n). The security relies on the fact that computing phi(n) requires factoring n = pq, which is hard for large primes.

Scheme

; Verifying Euler's theorem: m^phi(n) = 1 mod n

(define (mod-exp base exp m)
  (let loop ((result 1) (b (modulo base m)) (e exp))
    (if (= e 0) result
        (loop (if (odd? e) (modulo (* result b) m) result)
              (modulo (* b b) m)
              (quotient e 2)))))

(define p 61)
(define q 53)
(define n (* p q))                ; 3233
(define phi (* (- p 1) (- q 1)))  ; 3120

;; Euler's theorem: m^phi(n) = 1 mod n (when gcd(m,n) = 1)
(display "Euler's theorem tests:") (newline)
(let loop ((m-vals (list 2 7 42 100 999)))
  (when (not (null? m-vals))
    (let ((m (car m-vals)))
      (display "  ") (display m) (display "^phi mod n = ")
      (display (mod-exp m phi n)) (newline))
    (loop (cdr m-vals))))

;; Therefore m^(ed) = m^(1 + k*phi) = m * (m^phi)^k = m * 1 = m
(define e 17)
(define d 2753)
(display "e * d = ") (display (* e d)) (newline)
(display "e * d mod phi = ") (display (modulo (* e d) phi)) (newline)
(display "m^(ed) mod n = m, for any m coprime to n")

Neighbors

Cross-references

🔗 Judson Ch. 6 — rings: RSA uses modular arithmetic in Z/nZ
# Number Theory Ch.4 — RSA correctness is a direct corollary of Euler's theorem
⚙ Algorithms Ch.2 — fast modular exponentiation is the algorithmic heart
🔀 Theory of Computation Ch.8 — RSA security assumes integer factorization is not in P

Foundations (Wikipedia)

← Key Exchange by june.kim