I finished the rest of Simon Singh’s book last week over break as I tried to wrap my head around cryptography. Dan Boneh’s online Cryptography class started as well so there’s quite a few things to keep track of at the same time. Let’s go through it one step at a time.
The thing with RSA and PKE is that they are all very well documented. From the conception to implementation, everyone knows everything about them, but thats what gives the algorithm its strength, that exactly so many mathematicians and computer scientists know how the system works but haven’t been able to suggest a way to break it.
The concept by itself is startling, the idea that you can encrypt something with every one knowing most everything about the encryption process and yet not being able to decrypt the message. That’s because the algorithms use certain one-way functions like modulus arithmetic to encrypt, and then utilize properties of modulus arithmetic to undo the one way function.
Whitfield Diffie, Martin Hellman and Ralph Merkle worked on the idea of public key cryptography when every else thought they were insane. From the birth of cryptography all encryption ciphers were symmetric and as a result when the scope of what was being encrypted by whom grew the problem of key generation and distribution grew as well into a herculean task. Diffie, Hellman and Merkle began work to find a new way of key exchange that wouldn’t require perfect secrecy to create secret keys. What they came up with is the Diffie-Hellman key exchange system.
The algorithm is explained beautifully on the wikipedia page, but what you might note is that this process that they created is simultaneous. That is, both parties need to send messages back and forth before a key can be created. With email, this can be a type of problem since people might not both be online. Instead, the solution to that problem came from three other very famous cryptographers, Ron Rivest, Adi Shamir, and Leonard Adleman (RSA).
What Rivest, Shamir and Adleman did was respond to a paper by Diffie, Hellman and Merkle that proposed the idea of public key cryptography. That is cryptographic ciphers that used entirely public keys to encrypt a message, but could then only be (easily) decrypted using a second more private key.
Utilizing the same modulus arithmetic that Diffie, Hellman and Merkle were working with the trio came up with an algorithm based on the properties of prime numbers. To start with, party A (in cryptography circles party A is referred to as Alice) creates a number N by multiplying two very very large prime numbers, prime ‘p’ and ‘q’. Alice then creates another number called an exponent ‘e’ using Euler’s Totient, and releases this number publicly.
Now we party B (or Bob) who tries to send Alice an encrypted message M. He does this by taking exponential result of M^e (where ‘e’ is the same ‘e’ that Alice publically released) and then modulo the result by Alice’s public N. The resulting integer is the encrypted message C. Thus the formula is C = M^e (mod N).
Now Alice takes the result and runs it through the decryption algorithm where M = C^d (mod N). ‘d’ is defined as the multiplicative inverse of the ‘e’ modulo Euler’s totient of N.
This works and works well enough for this algorithm to have become the basis of all modern cryptography. It’s used in billions of transactions a day, and while it has its problems, the algorithm is secure enough. I’m hoping to learn more about the mathematics behind this to be able to concisely explain why it works the way it does but in the meantime I’m moving onto another aspect of cryptography, visual cryptography. More on that soon!