Public Key Encryption

This video, linked by Tyler Cowen, is the best I have seen to simplify the basic theory of public key encryption:

This follow-up video takes this basic understanding and explains RSA encryption

  • Sam P

    The explanation of the underlying ideas of one-way functions, DH, and RSA using mixing color paints and lights seemed very good, but I suspect they lose a lot of the less mathematically inclined when they go to the real stuff with modular arithmetic and exponentiation, much less modular discrete logarithms, especially with the sudden appearance of nearly unexplained mathematical jargon.

    However, I am interested in a layman's opinion (having actually implemented DH, RSA, and fast modular exponentiation using the Chinese Remainder Theorem before, I'm hardly the target audience).

  • herdgadfly

    It makes absolutely no sense to me.

  • Mercury

    The top video is pretty confusing and misleading (everybody knows red and blue make purple). The bottom video is a little better.

    It’s not that complicated really. Symmetric encryption means you and I (or Alice and Bob) use the same code to communicate secretly. There are many ways something like that can be cracked or compromised. The insight of Mr. RS&A produced a workable way to use asymmetric encryption (which means you and I have different “keys” to encrypt and decrypt
    a secret message) that is secure.

    Euclid’s Fundamental Theorem of Arithmetic states that every integer >1 can be written as a product of prime numbers which are unique. So 20 = 2x2x5 or, 2^2 x 5^1. 1200 = 2^4 x 3^1x5^2 etc. It follows that the product of two prime numbers will only have four factors: 1, itself and those two prime numbers. That’s the germ of RSA.

    Although there are a few tricks and rules of thumb, there is no elegant formula to factor numbers. It’s basically brute force trial and error. The bigger the number the more work it is, even for computers.

    I’m skipping a few steps here (see video #2) but, long story short: if I pick two (very large) prime numbers and multiply them together, their product can be used as my ‘Public Key’. I can put it on my web site or business card and
    anyone who wants to send me a secure communication encrypts their message with my public key. Only I can “unlock” the message because only I know what the original two prime numbers are (my “Private Key”) that were used to make the public key. To send a secure message to you I use your public key etc. The bigger the numbers involved, the harder it is to find these factors and break the code – effectively impossible with today’s tech once you get into the 1024bit range.

    Here is a pretty decent walk-through .pdf doc of the math with an example:
    https://math.berkeley.edu/~kpmann/encryption.pdf

    It’s not difficult math but there are a bunch of steps and variables to keep track of. Once you have a good grip on the process this video rips through the whole history, methodology and an example (with an Indian accent) in about five minutes: https://www.youtube.com/watch?v=ADozzYA8sTs

    Just hang in there the first time around and you’ll see that the steps are pretty simple (especially for a computer). Then, go back and re-watch certain parts if you want. You’ll get it.

    “Modulus arithmetic” is pretty straightforward too. As one of Coyote’s videos explains, a clock face is a mod 12 system. 11 o’clock + 5 hrs = 4 o’clock, not “16 o’clock”.

    Encryption is just math and anyone can use this math. If the government declares war on math, math will win. Regarding this business with Apple: even if Apple disables its encryption, provides a backdoor or whatever, any off-the-shelf system will work just as well with varying degrees of additional hassle.

    And, no matter how the cat-and-mouse number-crunching arms race shakes out in the near term, “square one” (as far as the surveillance state vs. “bad guys” game is concerned) will always be the “One Time Pad” (Google that) which is a simple, symmetric encryption system that is unbreakable as long as it’s used correctly. It’s inconvenient but if any two people have the same list of (truly) random numbers and they can also count backwards and forwards to 26 on their fingers,
    they can communicate in secret.