How public key cryptography works, using only simple math | Hacker News Reader

How public key cryptography works, using only simple math

quantamagazine.org

90 pointspseudolus23 comments

This article explains, poorly, _what_ public key cryptography is but not _how_ public key cryptography really works, at all.

Saying that Natasha and Boris both choose a prime number and then "create a safe" with it, is the same as telling someone that to make cake Alice and Bob went to the store and bought flour and eggs.

If you want a real, good and visual explanation of _how_ it works, with simple maths, go watch Computerphile's video[0] about Diffie-Hellman.

[0]: https://www.youtube.com/watch?v=NmM9HA2MQGI

I really liked the book “Implementing SSL / TLS Using Cryptography and PKI”. When trying to understand certificates and TLS, there always seemed to be some tricky bits that most explanations glossed over. In this book, the author builds a working TLS implementation in C, which means they have to cover all the details.

This gotta be my favourite Diffie-Hellman explanation and it's pretty much just a picture,

https://upload.wikimedia.org/wikipedia/commons/thumb/4/46/Di...

As usual with Quanta, the actual article didn’t explain anything well and was a waste of time (which is funny because Quanta is usually off the deep end with pages of esoteric babble that is gibberish except to genuine specialists. In this case, not only was there no ‘simple math’ - there was no math!). I’ve really got to stop clicking on Quanta links.

For an actually well written and deeply informative ‘how it works’ for public key cryptography, see:

https://www.bloomberg.com/features/2022-the-crypto-story/?em...

I was expecting a real example using some actual numbers and simple operations to demonstrate how this works. Instead there are a couple of vague metaphors that don’t explain much about the actual math involved beyond “multiply two primes”.

Would you be interested in that ? I could write about it

If you write about it, I’ll read it

https://www.cs.utexas.edu/~mitra/honors/soln.html

Worked example using p = 3 and q = 11.

φ(n) is the most complex part, but you can take it as shown if you don't care about the proof. For two primes, φ(p * q) = (p - 1) * (q - 1). The proof of this is more complex, and the calculation can get more involved if it's not a pair of primes, but for RSA it's that simple.

Coprime can be defined using middle/high school math: two numbers are coprime if gcd(n,m) = 1. They have no common factors other than 1, that's all it means. So 4 and 9 are coprime even though neither are prime.

----

φ(n) is Euler's totient function. It gives you the number of numbers coprime to n in the range 1 <= k <= n. So in the worked example, φ(n) = 20 means there are 20 numbers in that range that have no factors other than 1 in common with 33:

   1  2  4  5  7
   8 10 13 14 16
  17 19 20 23 25
  26 28 29 31 32

None of those have 3 or 11 as factors.

https://en.wikipedia.org/wiki/Euler's_totient_function

The original RSA paper is only 7 pages long and is worth reading.

https://dl.acm.org/doi/pdf/10.1145/359340.359342

I don't think the link is a great resource. However this is the best elliptic curve cryptography resource that I've found to date. Would love to see something similar for ZKs.

https://curves.xargs.org/

This is great, thanks!

Do you mean an explainer for ZK proofs? I found this primer by Matthew Green very helpful in understanding the basics: https://blog.cryptographyengineering.com/2014/11/27/zero-kno...

Vitaliks intro to ZK snarks article is great: https://vitalik.eth.limo/general/2021/01/26/snarks.html

Nice explanation with the ink. Here are some other sites to checkout:

https://tls13.xargs.org/

https://curves.xargs.org/

https://fangpenlin.com/posts/2019/10/07/elliptic-curve-crypt...

I was hoping for simple math. None found.

Would you be interestedin that ? I could write about it.

Some time ago I tried to come up with something that worked with pen and pencil, even if it used backup tables or something, to make a board game that would explain the concept to kids.

I wasn't very successful, and eventually gave up. It's hard to come with something simple that's easy to do in one direction, but moderately hard to do in the opposite across some skill levels.

Which, eventually makes the concept unintuitive, when explained through the lens or “simple, primary school math” (which is all most grown ups can deal with, without immediately reaching out for a phone/calculator).

So, the intuitive explanation that does work (for RSA) is the “I send you an open safe only I have the key for, you fill it, and you close it and send it to me.” That's instantly intuitive, and works. The rest… meh.

Well, I could write about the rest, modular algebra, inversibility of x in mod n, why we use the product of two primes, how we are lucky to generate prime numbers, what is modular exponentiation and why it allows us to encrypt and decrypt messages, and finally, why having a public key allows you to encrypt a message but doesn't allow you to decrypt one : where does the asymetry comes from. That's what I find interesting (not instantly intuitive).

This describes rsa. Which you should not be using anymore. It's slow and has huge keys. The current reccommendation is to use ed25519, which doesn't work quite like this.

If you're really serious about security then elliptic curves are kind of already obsolete as well. We should be using post-quantum algorithms today, and I'm surprised more people aren't concerned about that.

Quanta also has an article about how lattice-based cryptography works: https://www.quantamagazine.org/cryptographys-future-will-be-...

My understanding is that RSA is fast for signature verification and encryption but is slow for signature creation, decryption and keypair creation. So it might depend on the application.

In my opinion, the "safe", "magic ink" and such terminologies only make it harder to grasp. I would prefer if the actual terms were used

Yes, the bane of the self learners. Explanations often omit "you don't need to know this" bits because it's crystal clear to the explainer but you're left with big gaps in the shape of black boxes in your understanding.

Until you can piece it together from other explanations that omitted different bits.

Public key cryptography (and specifically the Diffie-Hellman key exchange) is arguably the greatest mathematical discovery of the 20th century. I guess digital trust wouldn't exist without it.

Reply on news.ycombinator.com