This blog was posted on my workspace blog on 08-FEB-2008
~~~***~~~
The Science of Secrecy - Part III
Links to the previous parts : Part I and Part II
RSA
At the end of part II, We saw that Diffie, Helman and Merkle key exchange method was used to communicate the secret key among two people. This scheme was workable but imperfect as it lacked spontaneity. Then they proposed the concept of public key cryptography or asymmetric encryption. This remained a theoretical concept as they had not yet found a special one-way function that could satisfy the requirements of an asymmetric encryption system. So their concept remained a perfect but unworkable one.
After 2 years, since the concept of an asymmetric cipher was proposed by D-M-H(in 1975), another trio named Ron Rivest, Leonard Adleman and Adi Shamir discovered a working model of an asymmetric encrytion system.
All three of them were researchers in the MIT Lab for computer science. Rivest and Shamir were computer scientists while Adleman was a mathematician. It was first Rivest's idea to find a solution for this problem. He then approached Adleman to help him and then Shamir joined in. It turned out to be a perfect partnership.
Rivest and Shamir worked hard to find one one-way function after the other, only to let Adleman find flaws in it. This continued till one day in april 1977, when Rivest came home drunk after a pass-over party. He was sleepless and was pondering over the asymmetric cipher problem. And then all of a sudden, he had a 'Eureka!' moment. At daybreak next day, he was ready with a full length scientific paper. Shamir and Adleman tried to find flaws but the efforts were of no use this time.
The Adleman-Rivest-Shamir(as it was first called by them) asymmetric encryption system was perfect! Then Adleman renamed it as RSA as he was the one to put minimal efforts into it. Before going into the mathematics of RSA, let us recollect the requirements of an asymmetric encryption system:
1. Alice must create a public key with which anyone(Bob) can encrypt their messages to her. It should be an one-way function so that no stranger(Eve) can reverse it to get the secret message.
2. Alice must decrypt the encrypted message. She must therefore have a secret private key which allows her(and only her) to reverse the one-way function.
Putting it black-and-white, we need a system with a one-way function which can be reversible under special conditions(which help only Alice to reverse the irreversible one-way funtion). And this was what R-S and A found:
The Mathematics of RSA
Stage 1 : Alice chooses 2 prime numbers p and q, say p=17 and q = 11. These are her secret.
Stage 2 : She works out N = p x q = pq = 17 x 11 = 187 and then she chooses another number 'e', say e = 11.
Stage 3 : N and e are published in a directory by Alice as her public key or encryption key. It is to be noted that N is unique for every person while 'e' can be common. So these two numbers put together can be used by anyone to encrypt messages to her.
Stage 4 : Now let us say that Bob wants to send her the letter 'X' (its ASCII value is 88). To find the ciphertext C for the plaintext M(which is only the letter 'X'), Bob should use the common one-way function : C = Me(mod N). Substituting the values, we get:
C = 887(mod 187) = 11. {NOTE : 887 is a very large value. But there are simple techniques to find out 887(mod 187) easily}
Stage 5 : Bob sends the ciphertext C = 11 to Alice. Now Eve can intercept this message. Eventhough he knows the C = 11 value, N , e and the function used, she cannot get the value of M = 88 because the function used is an one-way funtion. (NOTE : It is the same function used D-H-M key exchange method)
Stage 6 : Now Alice can decipher the message back because she has some special information. She knows p and q. She first works out the decryption key or her secret private key named 'd' with the formula :
e x d = 1 {mod[(p-1) x (q-1)]}
so substituting the values:
7 x d = 1 [mod (16 x 10)] = d = 1 (mod 160) / 7 = 23. [Note : finding 'd' is easier thru a technique called Euclid's algorithm]
So, d = 23 is Alice's private key.
Stage 7 : Now, Alice just has to pass her Ciphertext and her private key into a simple formula to get the plaintext M. The formula is M = Cd(mod N) = 1123(mod 187) = 88! which was Bob's message to Alice. The calculations of this stage are similar to stage 4.
Note : RSA system needs mathematical tools to easily perform calculations for Stages 4, 6 and 7. I feel that understanding the working of this system is itself a great thing from me. My understanding about RSA would be complete only after understanding the proof and how R-S and A created such a method. But I'm worried about the mathematics behind. So if any of you understood the proof, please do a KT to me :-)
Getting bBack, we have already seen the system from Eve's point of view till Stage 5. She cannot get back M = 88 from C = 11 as it is one-way function. But she knows all the values of N, e and the function. So, Instead of trying to reverse this function to get the plaintext, Can't Eve just work out the decryption key 'd' just as Alice did? like in Stage 6? The answer is 'no'! because she doesnot know the value of p and q(which are Alice's secret).
But Eve knows N. And N was calculated from p and q (i.e., N = pq). So will it not be easy for Eve to find p and q from N? The answer is another big 'No' and here lies the beauty of RSA. N is a product of two prime numbers - p and q. It is very difficult and time consuming to factorise N which is a product of 2 primes. In real life the values of p and q chosen are so large, that it is practically impossible to crack an RSA encrypted message.
As of 2005, the largest values of N factored is 200 decimal digits(660 binary digits or bits) long. That means that p and q were each 100 digits long(compare them with our example of p = 17 and q = 11). It is an accepted fact that 128, 256 and even 512 bit keys are vulnerable to attack because of distributed computing. So the choice of keys are either 1024 or 2048 bits as of now. But computing power and resources exponentially increase day-after-day forcing the use of longer keys.
Unless someone finds an algorithm for rapid factoring(the existence of which has not been proved or disproved by mathematicians and it still remains a great puzzle), RSA is impregnable. The increase in computing power may push the limits of the key-length. But computing power is like a double-edged knife as it can also be used to search for larger primes and thus feeding RSA with high-security keys. (NOTE: The largest known prime, as of August 2007, is 2232,582,657 - 1 . This number is 9,808,358 digits long! If p and q are this long, N would be 19,616,716 decimal digits long!). Anyways, this holds true no matter what! :-) Edit : Intranet Link
But since RSA is ultimately dependent on the factoring of N back to the primes p and q, the final verdict is that a breakthrough in Mathematics and rapid prime factoring can give RSA the run for its money.
For the time being, RSA system has solved the problem of spontaneity. Anyone could use Alice's public key and send her their encrypted emails while her own computer could decrypt it with her private key and have the message waiting for her to be read. This is totally unlike D-H-M key exchange method where it requires few intermediate calculations to be exchanged between Alice and Bob before the actual message is exchanged. One more problem with D-M-H method is that with each person one communicates, the choice of numbers must vary. But in RSA, Alice can use the same set of public and private keys as long as she feels that they are safe.
RSA was patented in August 1977 and RSA Data Security Inc was found by Rivest, Shamir and Adleman. It first sold its data security products to militaries and large corporations. The products were initally designed for the computing power and resources of such organisations and it was the effort of a free-thinker named Philip Zimmermann that brought RSA out to the public.
PGP :
"Pretty Good Privacy" was the name Phil Zimmermann gave to his controversial application that he distributed across the Internet as a freeware in 1991. It was controversial because it used the concept of RSA encryption without receiving a license from RSA Data Security Inc. RSA Inc branded PGP as a Banditware and Zimmermann was sued for copyright infringements.
PGP was responsible for the data security of the common masses. One main drawback of RSA was that it required high computing power to encrypt long texts. But Zimmermann reused the age-old technique of encrypting it with someother encryption system.(Note that encryption algorithms were really strong(ex: DES) even before D-M-H and R-S-A. But it was only the key distribution problem that undermined them). So Zimmermann used an encryption system called IDEA to encrypt the message and RSA only for the initial key exchange! This resulted in using RSA even in PCs and thus the wide spread use!
The PGP application had other great features too. It was very user-friendly. It kept the RSA, IDEA and other technical mumbo-jumbo to itself and helped the user to just type in, choose the PGP option and send the email. Even the choice of public and private key was innovative. A user could move his mouse in random directions and according to the movement, the public and private keys(the 2 large primes) were selected. PGP also listed everyone's public keys in a directory thus avoiding the need to remember other people's public keys.
Now comes the best part about PGP. Imagine this : Alice wants to send Bob a love letter. She knows Bob's public key. She can encrypt it with Bob's public key and send it to him. Bob can decipher it with his private key. But everyone knows Bob's public key, right? So why can't Eve write a love letter and put Alice's sign at the bottom and send it to him? What guarantee is there that the email that you receive is from the person you expect it to be from? PGP solves this in an brilliant yet simple manner!
Imagine this and see if this makes any sense - What if Alice encrypts her message using her private key(note: private) and sends its across to everyone? does that make any sense? Everyone can dechiper it with her public key and read it, right? It doesnt help for security. But it helps for 'Identity'! If Alice encrypts a message with her private key and sends it to someone, And if they can decrypt it with her public key, it surely means that the message is only from Alice and no one else!
So PGP uses a double encryption system for this 'digital signature':
1. Alice encrypts her message using her private key first (This identifies Alice). Then she encrypts this message with Bob's public key. This ensures that only Bob get the message(and Thus the security).
2. Bob decrypts it with his private key first. And then to see if it really was from Alice, he decrypts it with her public key!
This system was the first to implement the concept of 'Digital signatures' and was the forerunner to SSL(Secure Socket Layer).
The Anti-Climax:
In 1997, after nearly 3 decades from the time Diffie thought he could solve the key distribution problem, the British Government declassified information about three cryptographers of Government Communication Head-Quarters(GCHQ) with the claims that they had discovered the solution for the key distribution problem and the working concept of asymmetric encryption or public key cryptography way back in 1975 (2 years before RSA was patented)
The British Government gave the credits to three of its cryptographers namely - James Ellis, Clifford Cocks and Malcolm Willianson for discovering it even before the DMH and RSA's times. Since, it was for invented for the military, it was classified as 'top secret' and it remained so for 20 years till 1997 when the British Government thought that it was no use keeping it secret anymore.
It is another story of remarkable ingenuity, anonymous heroes and a government cover-up that endured for decades. It is indeed a sad story which I do not wish to share here for the fact that you will kill me for sucking your time.
FYI, from Wikipedia : "On June 29, 2006 it was announced that EMC Corporation will acquire RSA Security for $2.1 billion." But Cocks and Williamson remained unrewarded till 1997 looking at their invention taking over the world. And the saddest was that James Ellis who discovered a solution to key distribution problem in 1969(4 years before Diffie) died even before the information was declassified!
Phew... Whatever it is, my e-banking account and transaction passwords are safe! Thanks to Modern Cryptography!
## The End ##
The Science of Secrecy - Part III
Links to the previous parts : Part I and Part II
RSA
At the end of part II, We saw that Diffie, Helman and Merkle key exchange method was used to communicate the secret key among two people. This scheme was workable but imperfect as it lacked spontaneity. Then they proposed the concept of public key cryptography or asymmetric encryption. This remained a theoretical concept as they had not yet found a special one-way function that could satisfy the requirements of an asymmetric encryption system. So their concept remained a perfect but unworkable one.
After 2 years, since the concept of an asymmetric cipher was proposed by D-M-H(in 1975), another trio named Ron Rivest, Leonard Adleman and Adi Shamir discovered a working model of an asymmetric encrytion system.
All three of them were researchers in the MIT Lab for computer science. Rivest and Shamir were computer scientists while Adleman was a mathematician. It was first Rivest's idea to find a solution for this problem. He then approached Adleman to help him and then Shamir joined in. It turned out to be a perfect partnership.
Rivest and Shamir worked hard to find one one-way function after the other, only to let Adleman find flaws in it. This continued till one day in april 1977, when Rivest came home drunk after a pass-over party. He was sleepless and was pondering over the asymmetric cipher problem. And then all of a sudden, he had a 'Eureka!' moment. At daybreak next day, he was ready with a full length scientific paper. Shamir and Adleman tried to find flaws but the efforts were of no use this time.
The Adleman-Rivest-Shamir(as it was first called by them) asymmetric encryption system was perfect! Then Adleman renamed it as RSA as he was the one to put minimal efforts into it. Before going into the mathematics of RSA, let us recollect the requirements of an asymmetric encryption system:
1. Alice must create a public key with which anyone(Bob) can encrypt their messages to her. It should be an one-way function so that no stranger(Eve) can reverse it to get the secret message.
2. Alice must decrypt the encrypted message. She must therefore have a secret private key which allows her(and only her) to reverse the one-way function.
Putting it black-and-white, we need a system with a one-way function which can be reversible under special conditions(which help only Alice to reverse the irreversible one-way funtion). And this was what R-S and A found:
The Mathematics of RSA
Stage 1 : Alice chooses 2 prime numbers p and q, say p=17 and q = 11. These are her secret.
Stage 2 : She works out N = p x q = pq = 17 x 11 = 187 and then she chooses another number 'e', say e = 11.
Stage 3 : N and e are published in a directory by Alice as her public key or encryption key. It is to be noted that N is unique for every person while 'e' can be common. So these two numbers put together can be used by anyone to encrypt messages to her.
Stage 4 : Now let us say that Bob wants to send her the letter 'X' (its ASCII value is 88). To find the ciphertext C for the plaintext M(which is only the letter 'X'), Bob should use the common one-way function : C = Me(mod N). Substituting the values, we get:
C = 887(mod 187) = 11. {NOTE : 887 is a very large value. But there are simple techniques to find out 887(mod 187) easily}
Stage 5 : Bob sends the ciphertext C = 11 to Alice. Now Eve can intercept this message. Eventhough he knows the C = 11 value, N , e and the function used, she cannot get the value of M = 88 because the function used is an one-way funtion. (NOTE : It is the same function used D-H-M key exchange method)
Stage 6 : Now Alice can decipher the message back because she has some special information. She knows p and q. She first works out the decryption key or her secret private key named 'd' with the formula :
e x d = 1 {mod[(p-1) x (q-1)]}
so substituting the values:
7 x d = 1 [mod (16 x 10)] = d = 1 (mod 160) / 7 = 23. [Note : finding 'd' is easier thru a technique called Euclid's algorithm]
So, d = 23 is Alice's private key.
Stage 7 : Now, Alice just has to pass her Ciphertext and her private key into a simple formula to get the plaintext M. The formula is M = Cd(mod N) = 1123(mod 187) = 88! which was Bob's message to Alice. The calculations of this stage are similar to stage 4.
Note : RSA system needs mathematical tools to easily perform calculations for Stages 4, 6 and 7. I feel that understanding the working of this system is itself a great thing from me. My understanding about RSA would be complete only after understanding the proof and how R-S and A created such a method. But I'm worried about the mathematics behind. So if any of you understood the proof, please do a KT to me :-)
Getting bBack, we have already seen the system from Eve's point of view till Stage 5. She cannot get back M = 88 from C = 11 as it is one-way function. But she knows all the values of N, e and the function. So, Instead of trying to reverse this function to get the plaintext, Can't Eve just work out the decryption key 'd' just as Alice did? like in Stage 6? The answer is 'no'! because she doesnot know the value of p and q(which are Alice's secret).
But Eve knows N. And N was calculated from p and q (i.e., N = pq). So will it not be easy for Eve to find p and q from N? The answer is another big 'No' and here lies the beauty of RSA. N is a product of two prime numbers - p and q. It is very difficult and time consuming to factorise N which is a product of 2 primes. In real life the values of p and q chosen are so large, that it is practically impossible to crack an RSA encrypted message.
As of 2005, the largest values of N factored is 200 decimal digits(660 binary digits or bits) long. That means that p and q were each 100 digits long(compare them with our example of p = 17 and q = 11). It is an accepted fact that 128, 256 and even 512 bit keys are vulnerable to attack because of distributed computing. So the choice of keys are either 1024 or 2048 bits as of now. But computing power and resources exponentially increase day-after-day forcing the use of longer keys.
Unless someone finds an algorithm for rapid factoring(the existence of which has not been proved or disproved by mathematicians and it still remains a great puzzle), RSA is impregnable. The increase in computing power may push the limits of the key-length. But computing power is like a double-edged knife as it can also be used to search for larger primes and thus feeding RSA with high-security keys. (NOTE: The largest known prime, as of August 2007, is 2232,582,657 - 1 . This number is 9,808,358 digits long! If p and q are this long, N would be 19,616,716 decimal digits long!). Anyways, this holds true no matter what! :-) Edit : Intranet Link
But since RSA is ultimately dependent on the factoring of N back to the primes p and q, the final verdict is that a breakthrough in Mathematics and rapid prime factoring can give RSA the run for its money.
For the time being, RSA system has solved the problem of spontaneity. Anyone could use Alice's public key and send her their encrypted emails while her own computer could decrypt it with her private key and have the message waiting for her to be read. This is totally unlike D-H-M key exchange method where it requires few intermediate calculations to be exchanged between Alice and Bob before the actual message is exchanged. One more problem with D-M-H method is that with each person one communicates, the choice of numbers must vary. But in RSA, Alice can use the same set of public and private keys as long as she feels that they are safe.
RSA was patented in August 1977 and RSA Data Security Inc was found by Rivest, Shamir and Adleman. It first sold its data security products to militaries and large corporations. The products were initally designed for the computing power and resources of such organisations and it was the effort of a free-thinker named Philip Zimmermann that brought RSA out to the public.
PGP :
"Pretty Good Privacy" was the name Phil Zimmermann gave to his controversial application that he distributed across the Internet as a freeware in 1991. It was controversial because it used the concept of RSA encryption without receiving a license from RSA Data Security Inc. RSA Inc branded PGP as a Banditware and Zimmermann was sued for copyright infringements.
PGP was responsible for the data security of the common masses. One main drawback of RSA was that it required high computing power to encrypt long texts. But Zimmermann reused the age-old technique of encrypting it with someother encryption system.(Note that encryption algorithms were really strong(ex: DES) even before D-M-H and R-S-A. But it was only the key distribution problem that undermined them). So Zimmermann used an encryption system called IDEA to encrypt the message and RSA only for the initial key exchange! This resulted in using RSA even in PCs and thus the wide spread use!
The PGP application had other great features too. It was very user-friendly. It kept the RSA, IDEA and other technical mumbo-jumbo to itself and helped the user to just type in, choose the PGP option and send the email. Even the choice of public and private key was innovative. A user could move his mouse in random directions and according to the movement, the public and private keys(the 2 large primes) were selected. PGP also listed everyone's public keys in a directory thus avoiding the need to remember other people's public keys.
Now comes the best part about PGP. Imagine this : Alice wants to send Bob a love letter. She knows Bob's public key. She can encrypt it with Bob's public key and send it to him. Bob can decipher it with his private key. But everyone knows Bob's public key, right? So why can't Eve write a love letter and put Alice's sign at the bottom and send it to him? What guarantee is there that the email that you receive is from the person you expect it to be from? PGP solves this in an brilliant yet simple manner!
Imagine this and see if this makes any sense - What if Alice encrypts her message using her private key(note: private) and sends its across to everyone? does that make any sense? Everyone can dechiper it with her public key and read it, right? It doesnt help for security. But it helps for 'Identity'! If Alice encrypts a message with her private key and sends it to someone, And if they can decrypt it with her public key, it surely means that the message is only from Alice and no one else!
So PGP uses a double encryption system for this 'digital signature':
1. Alice encrypts her message using her private key first (This identifies Alice). Then she encrypts this message with Bob's public key. This ensures that only Bob get the message(and Thus the security).
2. Bob decrypts it with his private key first. And then to see if it really was from Alice, he decrypts it with her public key!
This system was the first to implement the concept of 'Digital signatures' and was the forerunner to SSL(Secure Socket Layer).
The Anti-Climax:
In 1997, after nearly 3 decades from the time Diffie thought he could solve the key distribution problem, the British Government declassified information about three cryptographers of Government Communication Head-Quarters(GCHQ) with the claims that they had discovered the solution for the key distribution problem and the working concept of asymmetric encryption or public key cryptography way back in 1975 (2 years before RSA was patented)
The British Government gave the credits to three of its cryptographers namely - James Ellis, Clifford Cocks and Malcolm Willianson for discovering it even before the DMH and RSA's times. Since, it was for invented for the military, it was classified as 'top secret' and it remained so for 20 years till 1997 when the British Government thought that it was no use keeping it secret anymore.
It is another story of remarkable ingenuity, anonymous heroes and a government cover-up that endured for decades. It is indeed a sad story which I do not wish to share here for the fact that you will kill me for sucking your time.
FYI, from Wikipedia : "On June 29, 2006 it was announced that EMC Corporation will acquire RSA Security for $2.1 billion." But Cocks and Williamson remained unrewarded till 1997 looking at their invention taking over the world. And the saddest was that James Ellis who discovered a solution to key distribution problem in 1969(4 years before Diffie) died even before the information was declassified!
Phew... Whatever it is, my e-banking account and transaction passwords are safe! Thanks to Modern Cryptography!
## The End ##
