1. RSA is the name of the most prevalent public/private key algorithm. It is also the name of the company (RSA Security) that originally held the patent rights to this system. It was invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman. Details: In order to generate the keys: First, some random data is generated. Most of the successful attacks against RSA implementations have been against this step. Two large primes are randomly chosen. This can be a time consuming step as the computer randomly generates numbers and tests to see if they are prime. These two numbers are traditionally called p and q. The two numbers are multiplied together, n = pq. We will be publishing n as part of the public-key. The security of RSA lies in the fact that it is computationally too difficult to factor n back into p and q. (However, somebody may in the future discover a way to easily factor large numbers, in which case all of today's cryptography will be rendered useless in one fell swoop). A number e is chosen, where e is less than n and "relatively prime" (no common factors) to (p-1)(q-1). The public-key will consist of the pair (n,e). A number d is chosen, where (ed-1) is divisible by (p-1)(q-1). The private-key consists of the pair (n,d). Usually, the original prime numbers p and q are discarded after this step. The numbers n, e, and d are of interest because they serve as fields within digital certificates. Details: In order to encrypt/decrypt something using RSA, the following algorithm is used. Start with the original message called m. Note that in reality, we've already encrypted the real message with a randomly generated symmetric key, and we really are just encrypting this key to send along with the encrypted message. Public-key cryptography is generally used for key-exchange because it is too slow for general-purpose encryption. Therefore, m is really just a small 128-bit key rather than the entire message. Create the ciphertext c using the equation c = me mod n, where (n,e) are the public-key. Send the ciphertext message c. Upon reception, use the equation m = cd mod n, where (n,d) is the private-key and m is the decrypted message. (Again, this is usually just the symmetric key that we will use to decrypt the actual message). Point: RSA forms the basis for X.509 certificates in web servers and browsers. Key point: RSA Security charges a hefty license to use the RSA algorithm. However, the patent expires in September of the year 2000. At that time, the number of products using the RSA algorithm are likely to explode. Key point: An alternative to RSA is the "Diffie-Hellman" algorithm. This is used in many cases, but it is hampered by the fact that many products that could use it (like Netscape and Microsoft browsers) do not; for interoperability you often need to use RSA over DH. History: When exporting RSA was illegal, a popular form of disobedience would be to wear T-shirts with the algorithm or us it as part of your .sig. #!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj $/=unpack('H*',$_);$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1lK[d2%Sa2/d0$^Ixp"|dc`;s/\W//g;$_=pack('H*',/((..)*)$/) Applications: PGP, SSL, SET, DNSSEC, SSH See also: DSA From Hacking-Lexicon