Can someone explain (or link to an explanation of) the math behind PKI? How can something be encrypted by one key but only decrypted by another key?

gbeier · 6 months

The Handbook of Applied Cryptography is now 100% free and explains it very well. Two of the authors are Menezes and Vanstone (the 'M' and 'V' in MQV). If you need to understand this for anything remotely important, you should really read this book.

joe_n · 6 months

The math depends on the algorithm. Here's my best stab at explaining it for RSA.

Consider the powers of a number subject to a modulus, e.g. the powers of 9 mod 33:

9 * 9 = 81 = 15 (mod 33)

15 * 9 = 135 = 3 (mod 33)

3 * 9 = 27 = 27 (mod 33)

27 * 9 = 243 = 12 (mod 33)

12 * 9 = 108 = 9 (mod 33)

In this case we see that 9 * 9⁵ = 9 (mod 33). This also forms the cycle 9 -> 15 -> 3 -> 27 -> 12 -> 9

The same can happen for all numbers 2-32 (technically 0 and 1 as well), though the cycle may be longer or shorter. So suppose I tell you to pick a number in this range and send me the 3rd element in the cycle it forms. In other words, if you want to tell me x, you send y = x³ (mod 33). Without even looking at what number you sent, I would know that the cycle length is a factor of 20, because we're using 33 as the modulus (more on this later). Therefore I know that x * x²⁰ = x (mod 33) no matter what you chose for x. Combining that with the fact that 3 * 7 = 21, I know that:

y⁷ (mod 33) = (x³ )⁷ (mod 33) = x²¹ (mod 33) = x * x²⁰ (mod 33) = x (mod 33)

Why x³ ? Why not x⁵ or x¹⁰ ? Well, even if I know the cycle length and y, I won't know immediately what is x (that is the entire point), so I can't directly advance or retreat in the cycle one element at a time. However, if I know x³ then I know how to go 3 steps at a time, and I can keep doing that until I know I must be at the start of the cycle. In this case, advancing seven times in this fashion puts me at the 21st element, which is the original element after some number of full cycles. This can only be done if I choose an exponent coprime to 20. So it doesn't need to be 3; it could have instead been 7, 11, etc. (but not 5 or 10).

Now the question is what do I know that an attacker wouldn't know? To understand the answers you have to bear in mind that in reality the scale of numbers here is much larger. Here, 33 is the product of two prime numbers, and this is no coincidence. However, instead of 3 and 11, you might use two very large prime numbers. It's important that they are chosen with some randomness so they cannot be guessed. Then, instead of 33 you would use the product of these prime numbers for your modulus.

The length of the cycle formed by the powers of a number is always a factor of 20 = (11-1) * (3-1). In general it will be the number of positive integers coprime to and less then your modulus. Since the modulus is a product of two primes, we count the positive integers less than 33 (11 * 3 - 1) and subtract the multiples of 3 (11-1 of them) and the multiples of 11 (3-1 of them). Again you can imagine that with large prime numbers the length of cycles can get very long, and because (or, assuming) an attacker can not figure out the factorization, this cycle length multiple is unknown to them as well. Without knowing any such multiple, even though it can also advance three steps at a time, it does not know when to stop its advancement. Also note that it is practically unfeasible to advance through step by step. Implementations of this algorithm will use repeated squaring or other methods to get to the specific power (x³ and y⁷ ) much more quickly.

Finally, the keys are setup as follows. To send me something, you need to know the modulus (33) and the index in the cycle that you should send (3). In RSA this is generally referred to as N and e, N being the product of two prime numbers which are not public.

In order to decipher what you've sent, I'll need to know the modulus as well (33) and the number of times to advance it to get back to the original element (7). These are generally referred to as N and d.

Note that the two prime numbers (p=3, q=11) are the base secrets involved. N is computed as their product and e,d are chosen such that e * d = 1 (mod (p-1) * (q-1)). However, after computing N/e/d, p/q are no longer necessary and can be discarded.

You can also notice the symmetric relationship between e and d, and this can be used to create digital signatures. If I want to sign something, I 'encrypt' it using (N,d) which is known only to me. Others can decrypt it with (N,e) to see that I did in fact sign it. However all of this assumes that I can reliably send you (N,e), but that's somewhat of a different problem.

edit: fixing a bunch of typos >.<

dokuhebi · 6 months

One-way mathematical functions are problems that are easy to solve one way, but difficult to reverse. For example, it's trivially easy to multiply two prime numbers together, but very difficult to figure out the two prime numbers that were multiplied together with just the result.

That's the gist of it. gooz's link to RSA gives a lot more of the details particular to RSA.

gooz · 6 months

The Wikipedia article on RSA is a pretty good start.

px403 · 6 months

I like to think of it like a rotation. One key moves the number left, the other key moves the number right. If you keep doing the same operation (encrypting with the public key) you won't get back to where you started for a while, but if you rotate the other direction (with the private key) you get right back to your clear text data.

iheartrms · 6 months

Bruce Scheier's "Applied Cryptography" covers this in a very nice way also.

aviewanew · 6 months

ElGamal is another public key cryptosystem, similar to RSA, but with different math. But it's not too difficult to follow. Here's my attempt at explaining it.

rainereality · 6 months

From "download: the true story of the Internet". This is probably the most straight forward explanation I've ever seen. I even recommended it to my university professor. http://www.youtube.com/watch?v=a72fHRr6MRU

ltx · 6 months

I think this is a pretty good explanation (even though I still don't understand it).

dguido · 6 months

It looks like I'm late to this game, but if you want just the basics then the chapter on Cryptography from Security Engineering should do it: http://www.cl.cam.ac.uk/~rja14/Papers/SE-05.pdf

terremoto · 6 months

There are two parts to public key cryptography. There's the key exchange then the actual communication. Take a look at this, and if you want a more detailed explanation after looking that over, there's this on a key exchange methodology.

As for the communication with the exchanged keys, there's a decent summary of the actual math here.

niczar · 6 months

Magic.

EryHax · 6 months

PKI is the coolest thing ever.

you'll need to login or register to do that

create a new account

login