SimuVeda

Computer Science · Simulator 057

RSA Cryptography

Build a tiny RSA key pair from two small primes, then encrypt a message with the public key and decrypt it with the private key, one modular calculation at a time. Try to break the key by factoring n, and see why real keys use primes hundreds of digits long.

How the model works

Key generation:

  1. Pick two primes p and q, and compute n = pq and φ(n) = (p − 1)(q − 1).
  2. Choose a public exponent e with gcd(e, φ) = 1 (65537 is common; small values are used here).
  3. Find the private exponent d with e·d ≡ 1 (mod φ) using the extended Euclidean algorithm.

Encrypt: c = mᵉ mod n. Decrypt: m = cᵈ mod n. This works because of Euler's theorem. Sign with d and anyone can verify with e.

The public key is (n, e). Knowing p and q gives φ and therefore d, so security rests on factoring n being hard. For the toy sizes here it takes microseconds; for 2048-bit keys, no known classical method finishes in any practical time.

Educational only. Tiny keys, no padding, and character-by-character encryption are completely insecure. Never use this for real secrets. Real RSA uses padding schemes (OAEP, PSS) and 2048+ bit keys.

Guided experiments

  1. Classic textbook key. p = 61, q = 53, e = 17. Prediction: n = 3233, φ = 3120, d = 2753. Encrypting m = 65 gives c = 2790, and decrypting gives 65 back.
  2. Break the key. Press “Factor n”. Prediction: trial division finds 53 × 61 almost instantly, revealing d. That is why real primes are enormous.
  3. Bad exponent. Choose e that shares a factor with φ (e = 3 when φ = 3120). Prediction: no inverse exists, so no valid d, and the key is rejected.

Challenge

With n = 3233 and e = 17, why does encrypting each letter separately leak information even though the key is “correct”?

Reveal the explanation

The same letter always gives the same ciphertext number, so frequency analysis works exactly as for a simple substitution cipher. Repeated letters are visible in the ciphertext readout. Real RSA adds random padding so equal messages encrypt differently, and it usually encrypts only a random symmetric key.

References

  • Rivest, Shamir & Adleman (1978), “A method for obtaining digital signatures and public-key cryptosystems”, Communications of the ACM 21: 120–126.
  • NIST SP 800-56B Rev. 2 (RSA key establishment).