Prime numbers and encryption

I have just completed reading the code book by Simon Singh and was immediately struck by the elegance of our current encryption technologies and their pervasiveness. The book clarifies how the very fundamental concept of prime numbers lies at the very heart of all our Amazon purchases and our banking transactions.

The fundamental problem of encryption is the following. Person A wants to transmit a private message to person B. This message is vulnerable to getting intercepted by person C but even if it gets intercepted A wants the meaning of the message to hidden from C. The fundamental way in which it can be achieved is by changing the form of the message (encrypting) and transmitting the encrypted message. B receives the encrypted message and if he knows how to decrypt it then he can reverse the process of encryption and gather the original message. If C happens to snoop in on it and doesn't know how to decrypt the message then even though he has the communication, he would not be able to make sense of it. As a very simple example, A might want to transmit two numbers 15 and 20 to B but he adds, let's say 50 to each and transmits them. The encryption in this case is the addition of the number 50. If B knows the encryption function (addition of a number) and the key (the number 50) then he can retrieve the original two numbers. If C doesn't have the ingenuity to figure out the encryption and the key, then he would not know the original numbers. There are, therefore, two distinct problems here. The first one is deciding upon an encryption algorithm and the second is deciding upon a key with which to encrypt the message. Ideally one would want to encrypt a message with an encryption algorithm which is complex enough to render decryption impossible without the knowledge of the key. In essence, the encryption algorithm may be public knowledge but it should be impossible to break it without the knowledge of the key. The simple encryption described above doesn't suffice obviously. If A is trying to transmit something meaningful like say the Fibonacci sequence and if it's known that he has merely added a number to all the entries, a mere trial and error would reveal the original sequence. Precisely because A is trying to transmit something meaningful, the simple encryption would be rendered useless. The second problem is how does B know what the key is? A can also transmit the key but then the key may itself get intercepted. A can personally meet B and give him the key but in the real world where billions of messages are being exchanged every day, personal meetings between senders and receivers are frankly out of question.

A solution to both these cryptographic problems was suggested in 1976 and goes by the name Diffie-Hellman-Merkle key exchange. The first idea is to use an encryption algorithm which is very difficult to undo without the knowledge of the key. The second and more revolutionary idea concerns the distribution of the key itself. The encryption algorithm is a modulo function.  c = a(mod b) gives the remainder c when a is divided by b. 8(mod 2) is 0, 9(mod 2) is 1 etc. As it turns out, if one only knows c and b, it is very difficult, if not impossible, to figure out a. The modulo function, therefore, is a one way function and a good candidate for encryption. The second idea was how the modulo function was utilized to solve the key distribution problem. 'A' chooses 3 different numbers let's say 3, 7, 11. He transmits the encryption function as being (mod 11) where can be any number. He keeps the first number 3 secret. 'B' also decides on his own secret number, let's say 6. Now C, who is snooping, may get to know the encryption function which is public but he doesn't know the private numbers 3 and 6 which were never transmitted. Now A transmits the result (mod 11)=2 and B transmits back (mod 11)=4. Upon receiving 4, A calculates (mod 11)=9 and upon receiving 2, B calculates (mod 11)=9. Both have come to the same number 9 which is the key. C which knows the encryption function and the numbers 2 and 4, cannot figure out the key 9 because he doesn't know the numbers 3 and 6. It can be seen that the key depends upon the secret numbers which were never transmitted and yet, both A and B come to know this key.

The next major development in cryptography was the RSA encryption which is the mainstay of all secure communication today. The above key exchange process still suffers from the fact that there needs to be a two way exchange of information between A and B. RSA does away with this by another neat usage of the modulo function coupled with the headache that is prime factorization. A prime number is a number which is only divisible by itself and 1. While it is very easy to take 2 prime numbers p and q and find r=p*q, given r it is extremely time consuming to figure out p and q. The RSA works by having a public and a private key. 'A' chooses 2 very big primes p and q and multiplies them. He keeps p and q secret but publishes r=p*q. If 'B' wants to transmit an encrypted message to A he uses A's public key (the number r) and uses a modified modulo function to encrypt his message. The function is such that even if r is known, it is extremely difficult to decrypt the message. As long as r is large enough, there is no way to decrypt the message unless p and q are also known (and hence A can do it).

The strength of RSA encryption basically boils down to the difficulty of prime factorization then. As all public knowledge stands currently, the encryption is unbreakable. Despite the tremendous amount of research in the problem of prime factorization there is no fast solution yet. The day the problem is solved much of our daily activities would grind to a halt! I find it fascinating now to think that every time I buy something on Amazon and provide my credit card information, the data is encrypted by what would be Amazon's public key (just a very very big number which is a multiple of 2 very big primes) and the current theoretical understanding assures me that decryption by a third party is beyond all human capabilities.