Asymmetric Cryptography · 3.2

🔢 RSA Algorithm

How multiplying two huge primes keeps the internet secure⏱ ~3 min

RSA (Rivest–Shamir–Adleman, 1977) is the most widely known asymmetric algorithm. It is used for key exchange, digital signatures, and encryption in TLS, PGP, SSH, and many other systems.

How RSA Keys Are Generated

1.Choose two large random prime numbers p and q (each 1024+ bits in modern usage)
2.Compute n = p × q (the modulus — this is part of both the public and private key)
3.Compute φ(n) = (p−1)(q−1) (Euler's totient function)
4.Choose public exponent e (typically 65537 — prime, small, and speeds up encryption)
5.Compute private exponent d such that e × d ≡ 1 (mod φ(n)) using the Extended Euclidean Algorithm
6.Public key = (n, e). Private key = (n, d). Destroy p, q, and φ(n).

Encryption and Decryption

math

To encrypt message M (where M < n):
  Ciphertext C = M^e mod n
 
To decrypt ciphertext C:
  Message M = C^d mod n
 
Small example (toy — real RSA uses 2048-4096 bit numbers):
  p = 61, q = 53, n = 3233, e = 17, d = 2753
  Encrypt 'A' (65): 65^17 mod 3233 = 2790
  Decrypt 2790:    2790^2753 mod 3233 = 65

RSA Key Sizes

Key Size	Security Level	Status
1024 bits	~80 bits security	❌ Broken — NIST deprecated in 2010
2048 bits	~112 bits security	✓ Minimum acceptable for TLS today
3072 bits	~128 bits security	✓ Recommended by NIST through 2030
4096 bits	~140 bits security	✓ High security; noticeably slower key operations

⚠ WarningRSA's security depends entirely on p and q being secret and truly random. If p and q share common factors with keys on other systems (due to weak random number generation), all keys can be factored instantly. In 2012, researchers found that 0.2% of all public RSA keys on the internet shared factors — instantly compromising those keys.

RSA in Practice

•TLS handshake — server's RSA key authenticates the server; used to exchange a symmetric session key
•SSH — RSA keys authenticate users (ssh-keygen generates a 2048/4096-bit RSA key pair by default)
•Code signing — software publishers sign binaries with RSA private keys; OS verifies with public key
•PGP/GPG — email encryption and signing

💡 TipRSA with PKCS#1 v1.5 padding has a known vulnerability (Bleichenbacher's padding oracle attack). Always use RSA-OAEP for encryption and RSA-PSS for signatures. Never use raw/textbook RSA — the padding scheme is not optional.

🧠Quick Checkfirst try = +5 XP

RSA's security relies on the difficulty of…

🎮 Practice what you learned

🔓

Cipher Cracker

Break Caesar & substitution ciphers yourself

→🏰

Password Fort

See hashing & cracking in action

→

⭐ 0 XP🔥 0 days

Open the full interactive Cryptography module →