Arithmetic
Cryptography in Plain Terms
From Caesar to Turing: 2000 Years of Secret Messages
**Julius Caesar** encrypted orders with a simple substitution: each letter shifted by 3 positions (A→D, B→E). Enemies couldn't read them - they lacked the idea. Two thousand years later, the German **Enigma** used the same substitution concept but with rotors that changed the cipher after every letter. It seemed unbreakable.
He who controls the information controls the world. - Winston Churchill
All cryptography before the 1970s was **symmetric**: one key for both encryption and decryption. The problem: how do you share that key? By courier? What if it's intercepted? This was called the "key distribution problem" - and seemed unsolvable.
The Secret Discovery That Changed the World
In **1973**, British cryptographer **James Ellis** of the secret agency GCHQ conceived the impossible: encryption without key exchange. Two years later, 22-year-old mathematician **Clifford Cocks** found the implementation - the very one the world would come to know as RSA. But the discovery was **classified for 24 years**.
Cryptography is the only field where you can be paranoid and still be right. - Whitfield Diffie
When in **1991** Phil Zimmermann created **PGP** (Pretty Good Privacy) and posted it online, the US government opened a criminal investigation - cryptography was classified as a **weapon**. Three years of proceedings. But the genie was already out of the bottle: RSA became the foundation of internet security, and then - **Bitcoin** and the entire crypto economy.
Every time you see the padlock in your browser, RSA is at work. Your card number is encrypted with the merchant's public key. Only the merchant can decrypt it - with the private key. A hacker intercepted the data? Useless. Behind that encryption is a simple idea: multiplying 100-digit primes takes milliseconds; factoring their product would take billions of years.
- **HTTPS:** protecting web traffic
- **Banks:** encrypting transactions
- **Digital signatures:** legally binding documents
The Public Key Idea
**Public-key cryptography** is a revolutionary idea from the 1970s: two keys instead of one. The public key encrypts; the private key decrypts. Knowing the public key gives no help in finding the private key.
**Symmetric cryptography (old):** One key for both encryption and decryption. Problem: how do you share the key over an insecure channel? **Asymmetric (public key):** • Public key: share it with everyone • Private key: keep it secret Encrypt with public key → decrypt with private key
Public-key cryptography solved the key distribution problem. Now you can communicate securely with strangers over the internet.
What can you do knowing only the public key?
The RSA Algorithm
**RSA** is the first and most famous public-key algorithm. It is based on the difficulty of factorization: multiplying two primes is easy; factoring their product is practically impossible for large numbers.
**The key idea of RSA:** Easy: p × q = n (multiply primes) Hard: n → (p, q) (factorize) **Parameters:** • p, q - large prime numbers (secret) • n = p × q - modulus (public) • e - encryption exponent (public) • d - decryption exponent (secret)
RSA turns the hardness of factorization into cryptographic security. As long as no fast factoring algorithm exists, RSA remains reliable.
What mathematical hard problem is RSA security based on?
Modular Exponentiation
**Modular exponentiation** computes a^b mod n. The naïve approach (compute a^b, then take mod) is impossible for large numbers. Fast exponentiation by squaring solves the problem.
**Modular arithmetic property:** (a × b) mod n = ((a mod n) × (b mod n)) mod n **Consequence:** We can reduce mod at every step, avoiding huge intermediate values. **"Square and multiply" method:** a^b computed in O(log b) multiplications
Fast exponentiation makes it practical to work with exponents thousands of bits long. Without this algorithm RSA would be unusable.
How many multiplications are needed to compute a^1024 mod n using fast exponentiation?
Why RSA Works
The mathematical foundation of RSA rests on **Fermat's little theorem** and its generalization - **Euler's theorem**. They guarantee that decryption recovers the original message.
**Fermat's little theorem:** If p is prime and gcd(a, p) = 1, then: a^(p-1) ≡ 1 (mod p) **Euler's theorem:** If gcd(a, n) = 1, then: a^φ(n) ≡ 1 (mod n) where φ(n) is Euler's totient function
The beauty of RSA lies in applying deep number theory to a practical problem. Euler in the 18th century had no idea his theorem would protect bank transactions in the 21st century.
RSA is absolutely secure and will never be broken
RSA is secure as long as factorization is hard; quantum computers will change that
Shor's algorithm on a quantum computer can factor numbers in polynomial time. When quantum computers become powerful enough, RSA will need to be replaced by post-quantum cryptography. But for now (2020s), RSA with 2048+ bit keys is considered secure.
Which theorem guarantees that RSA decryption recovers the original message?
Key Ideas
- Public key encrypts; private key decrypts
- RSA is based on the hardness of factoring n = p × q
- Fast exponentiation: O(log n) operations
- Euler's theorem guarantees M^(ed) ≡ M (mod n)
Related Topics
RSA uses fundamental concepts:
- Modular Arithmetic — Foundation of computation
- Prime Numbers — p and q in the keys
- GCD and Euclidean Algorithm — Finding d
Вопросы для размышления
- Why does RSA specifically require prime numbers, not arbitrary ones?
- How do quantum computers threaten RSA?
- Why can the public key be shared with everyone without risk?