Cryptography is a fascinating subject and is of great importance in most technology today, from computers to credit cards and government to ecommerce. Public-key algorithms provide a solution to what had been a big problem for cryptographers for thousands of years: key exchange. Historically, the same key had been used to encrypt and decrypt a plain text message, a process known as symmetric encryption. This meant though that the encryption key, as well as the encrypted data, had to be sent to the intended receiver. Somehow the sender and receiver had to securely share the encryption key in advance.
This problem of key distribution was solved in 1976 by two researchers at Stanford University, Whitfield Diffie and Martin Hellman. They proposed a cryptosystem in which the encryption key and the decryption key were different. This approach to cryptography, known as public-key cryptography, uses a pair of cryptographic keys, a public key and a private key. The private key is kept secret, while the public key can be distributed openly, thereby negating the need to transmit a secret key in advance. The keys are related mathematically, allowing the sender of a message to encrypt his message using the recipient's public key. The message can then only be decrypted using the recipient's private key.
Public-key cryptography serves both to authenticate a message and ensure its privacy, so it's essential that you know that the public key you are using to encrypt a message does belong to a specific person or entity. This has led to the creation of a public-key infrastructure (PKI), in which one or more third parties, known as certificate authorities, certify the ownership of key pairs. VeriSign Inc. is one of the best-known certificate authorities. Several algorithms in common employ public-key cryptography, probably the best known being the RSA algorithm named after its inventors, Ronald Rivest, Adi Shamir and Leonard Adleman.
Although your interest is in public-key cryptography algorithms, you will need to study other types of encryption algorithms to fully understand how different algorithms are used in different situations. Public-key encryption is slow and computationally intensive, so most systems only use it for highly secure transactions, such as to send the symmetric key used to encrypt a message. The SSL/TLS family of cryptographic protocols does this, and together they are called hybrid cryptosystems.
Another important aspect of cryptography to understand is that of breakability. All public-key schemes are susceptible to brute-force key search attacks. Theoretically, however, "breakable" and "practically breakable" are different. An attack is impractical if the amount of computation needed for a break to succeed, termed work factor, is beyond the means of a would-be attacker. For example, if it would, in theory, take 10 years to break an encryption scheme, then it is safe to use when encrypting your credit card details, as your credit card will expire well before the attacker can decrypt them.
When you're studying different algorithms, bear in mind that it's mostly their implementation that creates weaknesses rather than the algorithm itself. Attacking the physical implementation of a cryptosystem is called a side-channel attack. For example, timing information, power consumption, electromagnetic leaks or even sound can provide an extra source of information which can be exploited to break the system. As you can see, cryptography is a fascinating subject, and I'm sure you'll enjoy learning more about it.
This was first published in August 2009