Hello everyone! Get ready to peek under the hood of encryption. This post is for those who know a bit of math or computing and are curious about how encryption actually works at a (slightly) deeper level. We’ll still keep it engaging and fun, but we won’t shy away from the technical foundations – things like modular arithmetic, prime numbers, and one-way functions. If terms like “modulus” or “binary” make you nervous, don’t worry – I’ll explain everything in an intuitive way. By the end, you’ll understand not just the what but the how of modern encryption algorithms like RSA, and even hear a bit about cutting-edge topics like post-quantum cryptography (the future!).
Setting the stage: Imagine two students, Alice and Bob, who want to communicate securely in a class without others (or the teacher 😅) understanding. They have powerful computers and some math knowledge – what tools can they use? This scenario isn’t far from reality: encryption is basically math applied to communication. Let’s equip Alice and Bob (and you) with that math!
Recap of basics: In case you skipped the non-technical article: encryption converts plaintext to ciphertext and back using keys. We have symmetric (one key) and asymmetric (key pairs). In this article, we’ll dig into why those systems are secure. What makes a good cipher mathematically? Let’s find out.
The Math Toolbox: Modular Arithmetic & One-Way Functions
First up, a quick math primer – but an interesting one, promise! Modular arithmetic is at the heart of many encryption schemes. If you’ve ever done math with clock faces or remainders, you’ve done modular arithmetic. For example, in mod 12 (clock math), 9 + 5 isn’t 14, it’s 2 (because 14 mod 12 = 2). Essentially, you wrap around after reaching a certain number (the modulus).
Caesar cipher revisited (with mod math): Recall (from the non-technical article) Caesar shifting letters by 3. We can express that as numbers mod 26. If we assign A=0, B=1, ..., Z=25, then Caesar’s encryption of a letter could be: E = (P + 3) mod 26, where P is the plaintext letter’s number and E is the encrypted letter’s number. Decryption would be P = (E - 3) mod 26. This mod arithmetic makes it clear and general – a shift cipher is just addition mod 26. Why mod? Because after “Z” (25), we wrap to “A” (0). This simple use of mod math is a baby step toward the big uses of modular arithmetic in modern ciphers (where numbers might be astronomically large, not just 0–25!).
One-Way Functions: A core concept for encryption (especially asymmetric) is the idea of a one-way function – easy to compute in one direction, but extremely hard to reverse. A classic analogy: it’s easy to mix paint colors together, but impossible to un-mix them. Or, easy to smash a glass, but impossible to reassemble it perfectly from the shards. In math terms, think of something like multiplication: multiplying two big prime numbers is straightforward for a computer, but given a huge number that is the product of two primes, figuring out those original primes (factoring) turns out to be insanely hard – this is a one-way function in action. Encryption schemes leverage these kinds of problems.
Example of one-way (hash idea): Take two eggs and scramble them – you get an omelette. Can you get the original eggs back? Nope. That irreversibility is analogous to how certain encryption-related functions work. More formally, functions like exponentiation mod n can be easy, but the inverse (discrete log, factoring, etc.) can be hard without extra info.
Why one-way matters: If encrypting a message is like going forward through a one-way function (easy), then breaking the encryption without the key is like trying to go backward (hard). The legitimate receiver has a secret (like a key or factor) that does allow the backward step. For everyone else, it’s a dead end.
To summarize this toolbox:
We use modular arithmetic to make numbers wrap around (crucial for keeping numbers in manageable ranges and for cyclic properties in ciphers).
We rely on one-way functions so that even if an attacker sees the ciphertext, they can’t feasibly reverse the process without the key.
Keep these in mind – they’re the foundation upon which RSA and others are built.
Inside RSA: Prime Numbers to the Rescue
Time to dive into RSA, the superstar of public-key cryptography. RSA is named after its creators (Rivest, Shamir, Adleman) and is fundamentally based on the difficulty of factoring large numbers. Here’s a step-by-step of how RSA works, with just enough math to see the beauty:
Key Generation: This is where the math magic begins. Pick two large prime numbers, call them p and q. For example, to illustrate, let’s choose small ones like p = 7, q = 13 (in practice, primes are hundreds of digits long!). Multiply them: n = p × q = 7 × 13 = 91. That number n (91 in our toy example) is part of the public key. The primes p and q themselves are kept secret. Why? Because if someone can factor n to get p and q, they break the system. With real big primes, factoring n is believed to be practically impossible with current tech (that’s the one-way function: easy to multiply, hard to factor).
Choose Public/Private Exponents (e and d): Next, we calculate the following value related to p and q, (p−1)*(q−1) (called φ(n), Euler’s totient). We then pick an exponent e (public exponent) that’s relatively prime to φ(n). Common choice is 65537 (for reasons beyond this talk, it’s a nice number for efficiency and security). Then we compute d which is the modular inverse of e mod φ(n). This d will be the private exponent. In short, e and d are a special pair where: (message^e) mod n, then that result^d mod n = original message (mod n).
The math ensures that applying exponent e (encryption) and then d (decryption) gets you back. The pair (n, e) is the public key and (n, d) is the private key.
In our tiny example, φ(91) = φ(7*13) = (7-1)(13-1) = 6*12 = 72. Let’s pick e = 5 (which is coprime with 72). Now find d such that 5d ≡ 1 mod 72. One solution is d = 29 (since 5*29 = 145, and 145 mod 72 = 1). So public key = (n=91, e=5), private key = (n=91, d=29).
Encryption: To encrypt a number (which represents our message) M using RSA, you compute: C = M^e mod n. That’s modular exponentiation – and thanks to mod math, even though M^e could be huge, we reduce it mod n to get a manageable number C. This C is the ciphertext. For example, say our message M is 8 (again, very small example). Using our public key (91,5): C = 8^5 mod 91. Indeed, 8^5 = 32768, and 32768 mod 91 = 32. So ciphertext C = 32.
Decryption: Now someone with the private key can decrypt by computing: M = C^d mod n. Continuing our example, we take C=32 and do 32^29 mod 91. That’s a big number! But doing mod along the way, it will come back to 8. Indeed, if we trust the math, we’ll get the original message M=8. (Feel free to verify on paper or trust that the RSA design makes this work every time when keys are correct.)
The cool part: if an eavesdropper knows n (91) and e (5) and sees C (32), can they get M? To do so, they’d need to figure out d. Without knowing p and q (7 and 13), finding d is equivalent to factoring 91. For small values of n it’s trivial, but imagine n was a 2048-bit number (around 600 digits). Factoring that is beyond the reach of any current computer (and if not, then just take a 4096-bit number...), meaning the eavesdropper is stuck. RSA’s security rests on this factoring difficulty – multiply two primes easy, reverse it (factor) hard.
Why primes? Primes are the building blocks of integers (fundamental theorem of arithmetic). When you multiply two big primes, the result has a unique factorization. Without the primes, the number is just a big composite with no easy clues. It’s like mixing two secret colors of paint to get a new color; unless you know the original two, you can’t figure them out just by seeing the mixed color.
Key Sizes and Security: Typically, RSA uses 2048-bit keys (or 3072, etc.). These correspond to primes that are each roughly 1024 bits. As of now, no known method can factor such large numbers in a reasonable time. If someone could, RSA would be broken. Smaller RSA (like 512-bit) has been broken by clever mathematicians and computing power. So key size matters – the bigger, the safer (but also slower).
Mathematical Assurance: RSA works because of properties of modular arithmetic and Euler’s theorem: M^(e*d) mod n = M (under certain conditions given how e and d are chosen). We won’t deep-dive into the proof, but it’s a beautiful mix of number theory. The takeaway: RSA creates a trapdoor function – easy to do (encrypt) with the public key, but only easy to undo (decrypt) if you know the private key.
Technical Terms Explained (Accessibly)
As we discuss RSA and others, let’s clarify some jargon in simple terms:
Plaintext/Ciphertext: Plaintext is the original message (e.g., “HELLO”). Ciphertext is the encrypted gibberish (e.g., “URYYB” if we did a ROT13 cipher). It’s like input/output of the encryption process.
Key: A piece of information that controls the encryption/decryption. In symmetric encryption, it’s one secret (like a password). In asymmetric, it’s the public or private key (a large number in RSA).
Modular Arithmetic: As introduced, it’s wrapping around numbers at a certain modulus. We notate “mod” as in equations. It’s essential for keeping numbers in range and creating cyclical patterns (e.g., exponentiation mod n).
Prime Numbers: Numbers only divisible by 1 and themselves (2,3,5,7,11,...). They’re the atoms of multiplication. RSA loves primes because of the factoring difficulty.
One-way function: A function easy to compute, hard to invert. RSA’s core (multiplying primes or mod exponentiation without the key) is one-way. Another one-way idea used in crypto is hashing (though that’s a different topic) – think of it as a meat grinder: easy to grind the meat, impossible to get a cow back out.
Cryptographic protocol: The bigger picture of how algorithms are used in practice (like SSL/TLS uses RSA + other steps for a full secure conversation). It’s like a recipe using these crypto ingredients.
We’ll keep defining as we go if new terms pop up. Never be afraid to ask/google “what does that mean” – often the fancy term hides a simple idea.
Beyond RSA: Other Encryption Algorithms
While RSA is a fundamental cornerstone, there are many other algorithms, each with their own math:
AES (Advanced Encryption Standard): This is a symmetric cipher, widely used for everything from Wi-Fi to file encryption. It doesn’t use prime numbers; instead, it works on bytes and uses permutations and substitutions on a 4x4 grid of bytes with multiple rounds. The math is in a field of numbers mod 2 (binary arithmetic) and some linear algebra over finite fields. In simpler terms, AES repeatedly scrambles data in complex ways with the secret key guiding the process. It’s fast and very secure (no known practical attacks when used properly).
Diffie-Hellman Key Exchange: This isn’t an encryption algorithm per se, but a method for two parties to agree on a secret key over a public channel. The math involves exponentiation in mod prime (or mod a prime-based group). It’s like Alice and Bob mixing secret paint colors with a public color and exchanging mixtures to end up with a shared secret paint that eavesdroppers can’t determine. Diffie-Hellman introduced the world to the idea of public-key exchange of keys, and it’s based on the difficulty of the discrete logarithm problem (another one-way function).
Elliptic Curve Cryptography (ECC): Instead of prime numbers and mod multiplication, ECC uses points on an elliptic curve (an algebraic structure) and the difficulty of the elliptic curve discrete log problem. The cool thing is ECC can achieve similar security to RSA but with much smaller keys. For example, a 256-bit ECC key can be as secure as a 3072-bit RSA key. This is used in many modern systems (like by Bitcoin for its digital signatures, and by secure messaging for efficient encryption). The technical background: you have a curve equation and “points” on that curve form a group under addition, and scalar multiplication of a point is easy, but finding the multiplier given the original and final point is hard (one-way).
Others: There are plenty of other algorithms (Blowfish, Twofish, DES (old), RSA-OAEP variants, etc.), but the above cover the big categories: symmetric (AES), asymmetric (RSA, ECC), and key exchange (DH/ECC). We also have hash functions (SHA-256, etc.) in cryptography, but those are for integrity, not for encrypting messages (they’re one-way but not reversible at all). If a future article, we may touch on how hashes help ensure messages aren’t tampered with, and how they tie into digital signatures – but the main focus here is encryption.
Throughout these, notice a theme: find a hard mathematical problem and build an encryption scheme around it. As computing power grows, some problems become easier, so cryptographers continuously monitor and upgrade what “hard problems” we rely on.
Fun Challenge: Can You Break This Cipher?
Time for a hands-on challenge to apply what we’ve learned. I’ve prepared a secret message encrypted with a substitution cipher – not as easy as Caesar’s fixed shift, but each letter is consistently swapped with another (a random mapping). This is akin to the “Sherlock Holmes” dancing men cipher or the classic puzzles you see in newspapers (cryptograms).
Ciphertext:UJH XQJFU QDTF YJ FQQ RJXXFLJUT?
(Hint: This is a simple substitution where each letter stands for another. You might use frequency analysis – e.g., the most common letter might be substituting for “E” or “T”, common letters in English. Also, lone letter “J” could be “A” or “I”.)
Take a couple of minutes. Feel free to scribble on paper, try out possibilities, and remember common short words (“THE”, “AND”, “YOU”). Why are we doing this? Because breaking a substitution cipher by hand shows the principles of cryptanalysis (code-breaking). It’s doable for classical ciphers but should be impossible for strong ciphers like RSA without the key. Did you solve it?
Let’s solve it step by step:
We see “FQQ” – double letters could be “EE” or “OO” or “LL” etc.
The question mark at end suggests it’s a question.
“UJH” -- U could be W, J could be H, and H could be Y, forming “WHY”. That’s promising (“WHY” is a common question word).
If “UJH” is “WHY”, we have mappings: U->W, J->H, H->Y (or something along those lines; actually in “WHY”, W->U, H->J, Y->H if mapping cipher->plain).
Try “XQJFU” with those: X->?, Q->?, J->H, F->? U->W. We have ??H?W. Could that be “should”? No... How about “would”? If it were “would”, W->X (but we had W->U, conflict). Perhaps this is taking too long here, so I’ll unveil: The plaintext was “WHY WOULD YOU USE SUBSTITUTION?” – a cheeky question indeed!
If you got it or came close, congrats – you did manual cryptanalysis. If not, no worries, that’s why we have computers and better algorithms now. The exercise shows that older ciphers can be broken with logic, but something like RSA needs number theory and computing to break – far beyond pen-and-paper solving.
For the more mathematically inclined, here’s another challenge: a small RSA crack. Given n = 391 and e = 3, and a ciphertext C = 85, can you find the plaintext M? (Hint: 391 is small enough to factor if you try a few primes.) Indeed, 391 = 17 * 23. Using those, you could derive φ(n) = 352, then find d (which would be the modular inverse of 3 mod 352, which happens to be 235), and then compute M = 85^235 mod 391. That’s a bit tedious by hand, but since 391 is tiny, you could guess that maybe the plaintext was a small phrase encoded somehow. This is just to illustrate that with small RSA, a determined student could actually break it, but with real RSA (large n), no such luck.
Advanced Topic: Post-Quantum Cryptography (The Future of Encryption)
We’ve talked about how current encryption relies on certain math problems being hard (factoring, discrete log, etc.). Enter the potential game-changer: quantum computers. These are not your everyday computers; they leverage quantum physics to do computations in ways classical computers can’t. Why do we care? Because a big enough quantum computer could solve some of those “hard” math problems much faster. In particular, Shor’s algorithm (on a quantum computer) could factor large numbers efficiently, which would break RSA and ECC by cracking their one-way functions wide open.
Quantum threat in a nutshell: A quantum computer with enough qubits could factor a 2048-bit number in maybe hours or days, something impossible for billions of years on classical machines. This isn’t reality yet – quantum computers today are small and error-prone – but the potential is there. It means our current encryption might become vulnerable in the future (maybe a decade or two, nobody knows for sure when). Hence, the field of post-quantum cryptography (PQC) is preparing new algorithms that even quantum computers can’t easily break
.
Post-Quantum approaches: These new algorithms are based on different hard problems, not factoring or discrete logs. Leading contenders:
Lattice-based cryptography: Based on problems like the Learning With Errors (LWE) or Shortest Vector Problem in high-dimensional lattices. It’s like finding a shortest route in a multi-dimensional grid – hard for both classical and quantum. One lattice scheme, for example, is Kyber (for encryption) and Dilithium (for signatures) – recently selected by NIST for standardization.
Code-based cryptography: Based on problems from error-correcting codes (like decoding a general linear code, which is hard). The classic example is the McEliece cryptosystem from the 1970s (still unbroken by quantum).
Multivariate polynomial cryptography: Based on solving large systems of multivariate equations (which quantum doesn’t help too much with).
Hash-based signatures: Not for encryption, but for signatures, using hash functions (which are believed quantum-resistant aside from requiring bigger output sizes due to Grover’s algorithm speedups).
Larger keys, same principle: PQC algorithms often have larger key sizes or ciphertexts (for example, lattice keys can be kilobytes long, compared to 256-bit ECC keys). But if it keeps security, it’s worth it. The transitions happening as we speak – NSA and NIST have advised moving to quantum-safe algorithms in the coming years.
Practical impact: It’s a fascinating time – crypto experts are making sure that when quantum computers mature, our secrets from today remain safe. Imagine someone records an encrypted message of yours today and stores it. In 20 years, if there’s a quantum computer, they could decrypt it if it was using RSA/ECC. To prevent that, we want to shift to PQC soon, so even recorded ciphertexts stay secure in the long term
Visualization note: A quantum computer looks nothing like a PC – if you’ve seen those shiny chandeliers of chips and wires (like IBM’s quantum computer photo with golden tubes and plates), that’s the hardware that might one day challenge RSA. It’s both an exciting and intimidating prospect for encryption experts.
The image shows a wafer with lots of shiny squares – each could be a tiny quantum processor. This technology pushes us to innovate new cryptographic schemes. Post-quantum cryptography is our response: new locks before the old locks can be broken.
In summary, post-quantum cryptography is about being proactive – developing and standardizing encryption algorithms that even quantum computers will likely be unable to crack. It’s a perfect example of how cryptography is a living field, adapting to new threats and technologies. For the younger readers, by the time you’re deep into careers, you might be using completely different encryption algorithms than RSA/AES because of this shift!
Conclusion and Q&A
We went on a whirlwind tour from the basics of encryption math to the forefront of cryptographic research! Let’s recap what we’ve covered in this technically-flavored article:
We reinforced how encryption works (symmetric vs asymmetric) with a peek at the underlying math like modular arithmetic and one-way functions.
We walked through RSA, seeing how primes and exponentiation create a secure system, and why it’s secure (factoring is hard, no known efficient attacks without the private key).
We mentioned other algorithms like AES, Diffie-Hellman, and ECC, to appreciate the landscape of cryptographic tools and that RSA isn’t the only star.
We challenged ourselves with a code-breaking exercise, illustrating the gap between classical ciphers (easy to break) and modern ciphers (designed to be practically unbreakable without keys).
We looked ahead to post-quantum cryptography, understanding why new algorithms are on the horizon and the importance of always staying ahead of attackers in the crypto world.
The key takeaway: encryption is applied math. It transforms theoretical problems (like factoring or discrete log) into practical security. As computing advances, the math problems we rely on may change, but the goal remains: protect data. For those of you with technical backgrounds, there’s a whole world of fascinating math in cryptography – number theory, algebra, geometry (elliptic curves), probability (for security proofs)… If you find this interesting, you might enjoy courses or careers in cryptography or security engineering.
One last thought: with great encryption comes great responsibility. Encryption is a double-edged sword – it secures good people’s data, but also can shield bad actors. There are ongoing debates about encryption policy, backdoors, etc. As future technologists, it may fall on you to balance these issues – ensuring privacy while considering societal safety. No easy answers there, but a solid understanding of the tech (which you’re building right now) is crucial to inform that discussion.
Thank you for reading — I hope I made it engaging and clear. Now, I’d love to read your questions! Whether it’s about something we covered (maybe you want a bit more detail on how exactly we choose e and d in RSA or how AES mixes bytes) or something we didn’t (perhaps you’re curious about how Bitcoin encryption or password hashing works), feel free to send me an email to ferberasaf@gmail.com.
Comments