Rivest, Adleman, Shamir
Kevin Heller
Cryptography
Ronald Rivest, Leonard Adleman, and Adi Shamir are the creators of the RSA algorithm. They created it in 1977. For this they received the 2002 ACM Turing Award. The basis behind the algorithm was discovered 4 years earlier by Clifford Cocks but this wasn't discovered until 1997. Public key encryption and digital signatures are the 2 areas that RSA algorithm can be used for. The challenge in factoring large integers is why this is a good security technique.
Leonard Adleman is a professor University of Southern California. He teaches computer science and molecular biology. He studied at Univ. of California, Berkeley where he received both his BA in math and a PHD in computer science. Besides the RSA algorithm he has done work in molecular biology. He wrote a paper titled, “Molecular Computation of Solutions To Combinational Problems”. In it he describes the experimental use of DNA as a computational system. It is the first successful use of DNA to solve an algorithm.
Ronald Rivest is a professor at MIT in the electrical engineering and computer science department. He founded a security company called RSA Data Security. It was later bought by Security Dynamics and the combined company is RSA Security. His education includes a BA in math from Yale and a PHD in computer science from Stanford. Along with the RSA algorithm he invented the symmetric key encryption algorithms RC2, RC4, RC5, and co-invented RC6. In addition he designed the MD4 and MD5 hash functions.
Adi Shamir is an Israeli cryptographer. He received his BS in math from Tel-Aviv University. He is part of the faculty at the Weizmann Institute where he also received his masters and PHD in computer science. He has had numerous other contributions to cryptography. These include his secret sharing scheme, breaking the Merkle-Hellman cryptosystem, visual cryptography, the TWIRL and TWINKLE factoring devices. He co-invented differential cryptanalysis, however it was later found that both IBM and the NSA had known differential cryptanalysis and kept it a secret.
Here is a summary of the algorithm….
The public key is (n,e) and the private key is (n,d). p,q, and phi should also be kept secret. Here is how to generate the primes p and q….for p: generate a random number of bit length b/2, where b is the bit length of n you need it to be. Set the low bit (this guarantees that the number is odd) and set the 2 highest bits (this ensures that the high bit of n is also set). Check if the number is prime using the Rabin-Miller test; if it isn't prime increment by 2 and test again….for q: repeat the steps in p but start with an integer of length b-b/2. If p is less than q you can swap them but this is only required if you use the CRT form of the private key.