Die Funktionsweise von RSA wird mit kleinen Zahlen nachvollzogen. Aus den Primzahlen p = 5 und q = 11 wird n = pq gebildet, und der öffentliche Exponent ist e = 3. Mit φ(n) = (p − 1)(q − 1): Welcher private Exponent d (0 < d < φ(n)) erfüllt e × d ≡ 1 (mod φ(n))?

Antwort: B. 27

n = 5 × 11 = 55 und φ(n) = 4 × 10 = 40. Gesucht ist ein d, für das 3 × d bei Division durch 40 den Rest 1 lässt: 3 × 27 = 81 = 2 × 40 + 1, also d = 27. Der öffentliche Schlüssel ist (n, e) = (55, 3), der private Schlüssel d = 27; die Sicherheit beruht darauf, dass man ohne p und q den Wert φ(n) nicht kennt und d nicht bestimmen kann. Beim realen RSA sind p und q jeweils große Primzahlen mit über 1000 Bit, und für e wird häufig 65537 verwendet.