Cryptography Basics Rsa Diffie Hellman: Notes and FAQs

Cryptography is the mathematics of keeping secrets: turning readable messages into scrambled ciphertext that only the intended recipient can unscramble. Two ideas built modern public-key cryptography. RSA lets anyone encrypt a message using your public key while only you, holding the private key, can decrypt it — no shared secret needed in advance. Diffie–Hellman lets two strangers agree on a shared secret key over a public channel, even while an eavesdropper listens to every message.

These matter because every secure web connection, online payment and encrypted message relies on them. RSA protects the key exchange that starts an HTTPS session; Diffie–Hellman (in its elliptic-curve form) creates the session keys that then encrypt the actual data. Understanding the small-number versions below shows exactly why the real systems, with 2000-bit numbers, are secure: the same easy one-way computations become practically impossible to reverse.

Key Concepts

• Plaintext and ciphertext: the original message and its scrambled form.
• Public and private keys: in RSA the public key (n, e) encrypts and the private key (n, d) decrypts; the private exponent d is derived from the factorisation of n.
• One-way function: multiplying two primes is easy, but factoring their product back is hard — the asymmetry RSA exploits.
• Modular exponentiation: computing m^e mod n efficiently by repeated squaring; the core operation of both systems.
• Discrete logarithm problem: given g, p and g^a mod p, finding a is hard — the asymmetry Diffie–Hellman exploits.
• Generator: a base g modulo p whose powers cycle through many residues, used to build the shared secret.

Formulas

• RSA key generation: pick primes p, q; n = pq; φ(n) = (p − 1)(q − 1); choose e coprime to φ(n); compute d with e·d ≡ 1 (mod φ(n)).
• RSA encryption/decryption: c ≡ m^e (mod n); m ≡ c^d (mod n), for message m < n.
• Diffie–Hellman exchange: public prime p and generator g. Alice picks secret a, sends A ≡ g^a (mod p); Bob picks secret b, sends B ≡ g^b (mod p).
• Shared secret: both compute S ≡ B^a ≡ A^b ≡ g^ab (mod p); the eavesdropper sees only g, p, A and B.
• Euler's theorem (why RSA works): m^φ(n) ≡ 1 (mod n), so m^ed ≡ m (mod n) since ed ≡ 1 (mod φ(n)).

Worked Example

Part A — RSA with p = 3, q = 11. Then n = 33 and φ(n) = 2·10 = 20. Choose e = 3 (coprime to 20); the private exponent d satisfies 3d ≡ 1 (mod 20), and 3·7 = 21 ≡ 1, so d = 7. Encrypt m = 5: c = 5^3 = 125; 125 mod 33: 33·3 = 99, so c = 125 − 99 = 26. Decrypt c = 26: compute 26^7 mod 33. Note 26 ≡ −7 (mod 33): (−7)^2 = 49 ≡ 16; (−7)^4 ≡ 16^2 = 256 ≡ 256 − 231 = 25; then 26^7 = 26^4·26^2·26 ≡ 25·16·(−7) (mod 33). Now 25·16 = 400 ≡ 400 − 396 = 4, and 4·(−7) = −28 ≡ 5 (mod 33). The decrypted message is 5 ✓. Part B — Diffie–Hellman with p = 23, g = 5. Alice picks a = 6: A = 5^6 mod 23 = (5^4)(5^2) ≡ 4·2 = 8. Bob picks b = 15: B = 5^15 mod 23; with 5^2 ≡ 2, 5^4 ≡ 4, 5^8 ≡ 16, we get B ≡ 16·4·2·5 = 640 ≡ 640 − 621 = 19. Alice computes 19^6 mod 23: 19 ≡ −4, 19^2 ≡ 16, 19^4 ≡ 256 ≡ 3, so 19^6 ≡ 3·16 = 48 ≡ 2. Bob computes 8^15 mod 23: 8^2 ≡ 18, 8^4 ≡ 2, 8^8 ≡ 4, so 8^15 ≡ 4·2·18·8 = 1152 ≡ 1152 − 1150 = 2. Both arrive at the shared secret 2 ✓, while anyone listening heard only 23, 5, 8 and 19.

Common Misconceptions

• "RSA is secure because the formulas are secret." The algorithms are fully public. Security comes from the hardness of factoring n — knowing n and e gives no practical route to d.
• "Diffie–Hellman encrypts the message." It does not encrypt anything; it only establishes a shared secret. That secret then becomes the key for a symmetric cipher that encrypts the data.
• "Small examples prove the system works at scale." The mathematics is identical, but security needs huge numbers: 33 can be factored instantly, while a 2048-bit n cannot be factored with any foreseeable computer.

Real-World Applications

• HTTPS/TLS: your browser uses RSA (or elliptic-curve Diffie–Hellman) to agree on session keys with every secure website.
• Digital signatures: RSA run in reverse — signing with the private key — proves a document came from you and was not altered.
• Messaging apps: end-to-end encrypted chats use Diffie–Hellman-style key exchanges so that even the service provider cannot read messages.
• Software updates: signatures on updates use RSA so your device can verify downloads really came from the vendor.

RSA turns the factoring problem into public-key encryption: anyone can lock a message with (n, e), but only the holder of d can unlock it. Diffie–Hellman turns the discrete logarithm problem into a key agreement two strangers can perform in public. The worked numbers — encrypting 5 to 26 and back, and two parties independently reaching the secret 2 — are the exact computations your browser performs, just with numbers thousands of bits long.