Secrets from Primes

RSA calculator

Pick two primes and a public exponent; encrypt and decrypt a number or a short text. Teaching-sized, so not secure.

Textbook RSA with primes below 1012. Each prime is checked exactly, e is checked against φ(n), and d is found by the extended Euclidean algorithm. Real RSA uses moduli of 2048 bits or more and randomized padding.

How the calculator works

This is RSA exactly as Rivest, Shamir and Adleman described it in 1978[1]:

  1. Two different primes p and q; the calculator proves each one prime (or names a divisor) and accepts primes below 1012.
  2. n = p × q and φ(n) = (p − 1)(q − 1).
  3. A public exponent e with 1 < e < φ(n) and gcd(e, φ(n)) = 1. If yours fails, the calculator lists exponents that work.
  4. The private exponent d = e−1 mod φ(n), by the extended Euclidean algorithm[2].
  5. Encryption c = me mod n for a message 0 ≤ m < n; decryption m = cd mod n.

Many textbooks and standards use λ(n) = lcm(p − 1, q − 1) instead of φ(n) in step 4; that gives a smaller d that decrypts equally well. For p = 61, q = 53 and e = 17, λ(n) = 780 and that d is 413 rather than 2753.

Worked example from the 1978 paper

The original paper uses p = 47, q = 59, so n = 2773 and φ(n) = 2668. It chooses d = 157 and finds e = 17. The message ITS ALL GREEK TO ME is coded two letters per block (blank = 00, A = 01, …, Z = 26), giving 0920 1900 0112 1200 0718 0505 1100 2015 0013 0500, and the first block encrypts to 92017 mod 2773 = 948[1]. Enter 47, 59, 17 and the message 920 to reproduce it.

Why this is not secure

With primes below 1012, n has at most 24 digits, and this site's own Prime checker factors such numbers in about a second; from the factors anyone can compute d. NIST's comparable-strength table pairs a 2048-bit modulus (617 digits) with 112-bit security and a 3072-bit modulus with 128-bit security[3]. Textbook RSA is also deterministic: the same message always gives the same ciphertext, as the text mode shows. Real systems add random padding and use RSA mostly to carry a key for a faster symmetric cipher. Use this page to learn and to check homework, never to protect anything.

Sources

  1. R. L. Rivest, A. Shamir and L. Adleman (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21 (2), 120–126. doi:10.1145/359340.359342. paper
  2. Victor Shoup (2008). A Computational Introduction to Number Theory and Algebra, 2nd edition (Version 2, free PDF). Cambridge University Press. ISBN 9780521516440. textbook
  3. E. Barker (2020). Recommendation for Key Management: Part 1 – General (SP 800-57 Part 1 Rev. 5), §5.6.1.1 and Table 2. National Institute of Standards and Technology. doi:10.6028/NIST.SP.800-57pt1r5. standard