How does public key cryptography work?

Question

How does public key cryptography work?

Answer 1

It's entirely possible, and it works very well.



The most popular public-key cipher, RSA, has a simple basis, although the implementations and the math behind them are a lot more complex. In RSA, you just take a block of plaintext, and treat it as one gigantic, really huge number. Then you raise it to an extremely high power (one with hundreds of digits), divide it by a still bigger number (the modulus), and then take the remainder as the ciphertext. The exponent used is the encryption key. To decrypt, you just repeat the operation, but with a different exponent that represents the decryption key. As long as the modulus, encryption exponent, and decryption exponent have a certain mathematical relationship to each other, it works perfectly. Anything that is encrypted with one of the keys can be decrypted (only) by the other key.



Breaking RSA requires factoring numbers with hundreds or thousands of digits, or taking discrete logarithms of similar numbers. Right now, nobody knows how to do that with any efficiency, so RSA is considered secure with a sufficient key length (several thousand bits).



There are many other public-key algorithms. The principles have been known for about fifty years, although they didn't become known outside of secret government circles until the 1990s or thereabouts.

Answer 2

How PGP Works

=

- http://www.pgpi.org/doc/pgpintro/

Answer 3

I guess they use some form of hash table and algorithm to make it so that it's not as easy as just dividing by something. One might be able to run through all possible starting keys to see what they end up with, but that brings up other problems.



Basically the way it gets the keys isn't as simple as dividing by twelve, more like dividing by some number that you can only realise when the first value was entered.



Not sure how to not explain this in a confusing way...

Answer 4

RSA is a relatively simple asymmetric algorithm, but in order to obtain an understanding of *why* it works requires one to have an understanding of some basic number theory principles. One site that I think does a decent job of outlining the basics for beginners is:



http://www.muppetlabs.com/~breadbox/txt/rsa.html



The article answers your question about trap-door functions, motivates and explains the general idea and then provides some examples. My main gripe is they stray from the standard notation used when discussing RSA (e.g. e is the public exponent, d is the private exponent, n is the modulus, etc. The notation doesn't really matter, but I do value consistency)



Good luck