This blogpost is not a candidate for Nobel’s price in mathematics, be aware the stuff I mention here is over-simplified and digested by a person with no CS or math studies degree (me). I’ve tried my best here describing how modern encryption works, what power it gives us, all while personally understanding the topic. A lot of principles below I find attractive and want the broader audience to have a common understanding of. Enjoy your reading.
Intro
Modern cryptography is an unprecedentedly powerful tool that has given the last few generations a secure way to encode and decode virtually any piece of information. If today’s cryptography had been present during WW2 for instance, who knows where history whould’ve turned to. Nevertheless, today we have an “unbreakable Enigma” in our pockets, kettles and light bulbs. Quite impressive if you think about it!
Flaw
In the end it all comes down to bad intent (it always does), so before getting deep into technological side of modern encryption, I’d like to define three types of bad actors. They are: 1) Individual criminals 2) BigTech companies 3) Governments. The first one is actually the simplest to protect from - because criminals have finite amount of money, knowledge and time on their side, plus they encounter the largest, most straightforward risk being catched and physically retained in case of capture.
BigTechs, however, think only in money terms: if it’s economically justified to steal the data (which it always is), sell it and push certain agenda in between, they would absolutely do it. Even with today level of technological penetration we still have wagies in big companies selling private information of clients to some attacker on a daily basis. Our mobile numbers, addresses, password hashes are being actively traded on dark web. Someone’s civil data (date of birth, mobile number, billing address, sometimes even social IDs) cost less than a coffee, while big companies possess hundreds of millions of these records. However, there’s not much a fraud can do while pretending to be another person (taking microloans, rent cheap cars, etc. becomes more and more difficult). But a “fraud” term isn’t limited to these two cases. Goverments are even bigger players that sadly but surely cannot be thrown out of the equation...
An inherent aspect of our lives (and natural freedom according to UDHR, bear in mind) is a right to private correspondence... Or is it?
Try and think, how sure you are that your messages to mom are not intercepted and being filtered for separatism or antisemitism? How can you be sure it’s not happening after NSA leaks? After Texas sues META for WhatsApp privacy claims? If it’s not the case and our messages are not being spied on, then well, where’s a single proof other than “trust us, we definitely changed during this administration”. This proof is crap, the only one I would believe (still with caution) is open-source code of messaging apps and operating systems they are running on. But it’s not the case either. We have to leave where we leave, but obeying and bending over is still a choice. I myself would rather not communicate at all, if every message I compile is sent to God knows whom.
By the time I left Russia, the local government has effectively blocked all foreign messaging apps prior to imposing a “sovereign” messenger with whole lot of backdoors and MITM proofs (of course all this bullshit being funded with taxpayers’ money). Sadly, when push comes to shove, practically none is willing to stand by their grounds while sacrificing privacy for convenience. More and more people are unwillingly but calmly bending towards convenience, whatever it’s being currently defined as. To my Russian friends I can safely say: “if I someday approach you in MAX messenger - that’s not me”.
Okay, enough contemplation, let’s see what modern cryptography is capable of today.
Technology out there
To enliven the narrative, let’s introduce some characters that we know from the previous blogpost on cryptocurrencies .
Meet Chad and Katie - two friends living far away from each other who need a way to securely communicate (one of them can be a server rather than a person, nothing would fundamentally change).
Suppose Chad wants to send a message to Katie thru some public channel (internet). He hence relies on channel’s infrastructure and trusts internet to deliver the message to the recepient (he’s got no control over nodes along the way that will pass the message, thus the message may be listened to by malitious actors which means it is already potentially compromised (if Chad was from Russia, China or Iran, he’d be 100% sure that there’s a passive listener to every message he sends).
| ~~~ public channel ~~~ |
| |
Chad (sender) ---> | Man In The Middle | ---> Katie (recepient)
| (listener) |
| | There’s a way to rephrase (encrypt) the message and pass Katie a key, so that she would manually apply it when receiving the message. Amazingly and expectedly, the key doesn’t even have to travel thru public channel - there’s a way to quickly generate it on both ends without MITM ever touching or guessing it (see DH key exchange).
Symmetric key Cryptography
Diffie-Hellman key exchange will be the example today. If you do not want to dive into math behind, feel free to skip this section (just trust it works).
Diffie-Hellman
Proposed in 1976 and used right now by the device you are reading this from, here’s how it works:
Algoritm’s based around 2 public numbers known by Chad, Katie and others:
- \(g\) (generator - small prime number)
- \(n\) (large prime).
Chad picks a secret number \(a\), Katie picks \(b\).
Chad calculates \(g^amod(n)\), Katie does the same, but for her number: \(g^bmod(n)\).
| Chad | public channel | Katie |
|---|---|---|
| \(a\) | \(g,n\) | \(b\) |
| \(g^amod(n)\) | \(g^bmod(n)\) |
They then send each other their intermediate results (man in the middle sees them, but he doesn’t know \(a\) or \(b\)).
| Chad | public channel | Katie |
|---|---|---|
| \(a\) | \(g,n\) | \(b\) |
| \(g^amod(n)→\) | \(g^amod(n)\) | |
| \(g^bmod(n)\) | \(←g^bmod(n)\) |
When chad receives \(g^bmod(n)\) from Katie, he raises it to his secret \(a\): \(g^{b^a}mod(n)\). Katie calculates \(g^{a^b}mod(n)\) accordingly. They both now come to the same result:
\[g^{b^a}mod(n) = g^{a^b}mod(n)\]which is their mutual key.
| Chad | public channel | Katie |
|---|---|---|
| \(a\) | \(g,n\) | \(b\) |
| ↓ | \(g^amod(n) ↘\) | ↓ |
| \(g^{b^a}mod(n)\) | \(← g^bmod(n)\) | \(g^{a^b}mod(n)\) |
\(mod(n)\) is used, so that the computation doesn’t get too far into big numbers: it wraps the result around a finite “circle”, making equations work without exceeding modern computing capabilities. Modular arithmetic is used a lot in cryptography. That’s for several reasons: modulos are efficient on hardware, easy to compute forward and hard to reverse, they are predictable to a certain sense.
Most importantly, the attacker has no idea what the final number is. He doesn’t know Chad’s \(a\) or Katie’s \(b\) (they were never publicly released) and he’s not capable of solving the discrete logarithm problem. The best he can do is calculate \(g^{ab}mod(n)\) which’s far from equal to \(g^{a^b}mod(n)\). He has to brute-force every possible \(a\) or \(b\) to find what \(g^{a^b}mod(n)\) is.
In other words, the attacker knows both intermediate values but has no idea how to get to the key itself.
That’s as simple as it gets, other algorithms found below are more obscure and more powerful.
Weakness
What DH doesn’t cover is the following attack vector:
Clever attacker can not only listen but also intercept and tamper messages that flow through the channel. Just like in strategy stealing1 case, where a noob is playing two chess grandmasters by mirriring each others moves, here the attacker can stick to the same pass-through strategy: make a secret key with Chad pretending to be Katie and make one with Katie, pretending to be Chad. None of them know how \(g^amod(n)\) or \(g^bmod(n)\) should look like, these are just pseudo-random numbers.
| Chad | attacker | Katie | ||
|---|---|---|---|---|
| \(a ↓\) | \(↙ s ↘\) | \(b ↓\) | ||
| \(g^amod(n)→\) | \(g^{a^s}mod(n)\) | \(←g^smod(n)→\) | \(g^{s^b}mod(n)\) | \(←g^bmod(n)\) |
It would take some time for an attacker to intercept a message from Chad, decode it with key \(g^{a^s}mod(n)\), then re-encode it with key \(g^{s^b}mod(n)\) for Katie every time the message is passed, but still it’s a crucial flaw of symmetric cryptography that comes as its main limitation. Another limitation is that Chad can be offline while Katie is forming a message. If her device’s not running, she cannot get alleged \(g^amod(n)\) and thus cannot encrypt a message without a key being agreed upon.
That’s where asymmetric keys come around...
Asymmetric or Public key cryptography
Public key cryptography provides us a way to precompute personal pair of keys: private and public, and then distribute the latter one to the broad audience (it couldn’t be simpler that that, but people still mess up and publish private keys in public repos, losing millions .
How it works is you sign a message with a private key, and it can be later verified using the public key. You can also encrypt the message using other’s public key, so that only the corresponding owner (private key owner) can decipher it.
Public key cryptography is computaionally more intensive than symmetric key algos (like Diffie-Hellman that we looked at above), so they are oftenly used in pair: first establish a secure connection to a public key owner (ensuring it’s not a fraud that you are communicating with), then making a symmetric key to continue exchange of information.
RSA
RSA is the most commonly recognised asymmetric algorithm out there. It’s based on factoring large prime integers \(n=p*q\) while keeping them private. Breaking RSA is believed to require factoring \(n\) back to \(p\) and \(q\) which’s beyond the capabilities of modern computers for large \(p\) and \(q\). There are quite a lot of prime numbers out there, so we expect many unique combinations of these “keys” that are hard to guess.
Quantum computers threaten RSA sustainability with Shor’s2 and Grover’s3 algos. But even more exposed to quantum computers are elliptic curves algorithms, though public keys are shorter and computing is faster there.
Elliptic curves
Elliptic curves rely on ECDLP - EC Discrete Log Problem. On the curve there are points that are represented with a coordinate pair (point is a location). These points move when we add or multiply (repeatedly add) them with each other. It’s well-defined how these operations work, but reverse functions are computationally infeasible - no fast algorithm to substraction/division on an elliptic curve is known yet.
I found it quite hard to unroll EC algo into my
| favorite | table |
|---|---|
| design | system |
so here’s a nice YouTube video . Go on and understand by yourself why substraction is infeasible: to reverse the chain you’d have to know what \(G_{a-1}\) was. But all the attacker can possibly have is a resulting \(aG\) point coordinates. To guess a secret \(a\) he has to brute-force every possible number of additions there is.
We can actually compare EC operations with 5th grade math: if we have an equation \(p=a*G\) and we want to know \(a\), we simply move \(G\) to the other side, getting
\[a=\frac{p}{G}\]But that operation is not defined on an elliptic curve - that’s what secures our secret \(a\) multiplier.
PGP
It’s not an actual algoritm, but a widely used standard that states how to encrypt/authenticate data. One of the biggest thing it did was enabling web of trust .
You can find my PGP key and see its use cases here .
Final remarks
I hope you now have a coherent idea of what cryptography is capable of. You do not have to understand how every operation works (I don’t), but having a general picture is useful.
What encryption does not cover though is that the actual borderline between real and fake is rapidly fading out.
Let’s put security aside for a moment and talk about another, more vital issue. Imagine there’s an Instagram girl who’s deeply concerned of being processed through an automated LLM dating filter that some guy created to maximise his leads w/o any effort. Sounds silly? But it’s happening in the real time! The girl cannot distinguish between AI and a random person in her DM. The guy doesn’t care at all, he’s not sincere to a random bimbo, why would he be? Isn’t it a magnificent example of both instagram LARPs and AI slop colliding into a perfect union? I find this conflict hilarious, though these girls may deserve a little more compassion, idk.
The point being no amount of security checks or asses scanned can prevent strangers from exploiting the sick nature of modern social interactions. The system is flawed. My suggestion is to value a glimpse of genuine human communication that we still have and not trying and convince some stranger of how cool/rich/unattainable/charismatic you are. Then, may be, they won’t try to convince you the same...
Don’t be that chess noob1 who’s mirroring grandmasters moves - you won’t convince youself that you’re capable of winning, no matter how many games you win that way. Picking a “mirroring strategy” will probably not bring you happiness in the longer run.
Footnotes
In game theory the strategy stealing argument proves that in a symmetric game there’s no guaranteed winning strategy for the second player to move. Supposedly this strategy exists - that would mean after the first player makes an arbitrary move, he can then play according to the very same “winning” strategy. So both players are guaranteed to win - contradiction. In mirrored chess games, exploiter becomes the second player on board 1 and the first player in board 2. Given that, he cannot lose on both boards. ↩︎ ↩︎
Takes the problem and gives an exponential search speedup via a quantum Fourier transform. It puts pressure on RSA/DH/ECC algoritms and suggests a replacement towards post-quantum algos. ↩︎
It takes the problem and square-roots the run time: for instance, an AES key of 128 bits will have a search space of just 64 bits. For 256 bit key it will bring us down to 128 bits which’s still not within reach. ↩︎