What is Public Key Cryptography?

Classical Cryptography is popularly known as symmetric key cryptography as the same key is used for encryption (by the sender) and for decryption (by the receiver). So, the communicating parties must agree upon a common key before any message is sent. Secure exchange of a common key is tedious and could be expensive in some cases. Also if one is communicating with several people, one needs one key for each person one is communicating with. One has te remember a secret key for each contact in his address book. Thus two major problems with classical cryptography is secure key exchange and key management. Advent of public key cryptography overcame these two problems.

In public key cryptography (PKC) each user has 2 keys one is public key and the other is private key. The public key of the users are made public through a publicly available directory. Public key is used by people who send message to the user and messages are encrypted using the public key. Every user also possesses a private key, which is the user's secret. An user decrypts the message sent to him/her using his/her public key. As public key is publicly available, anyone can encrypt a message using an user's public key. But it can be decrypted by that user only who has the corresponding secret key. An analogy is our email system. It is easy to get one's email ID (like public key) and send a message to one. But only the person with that email ID can read it as he only knows the password of that email account.

As PKC uses 2 different keys for encryption and decryption purposes, it is also known as Assymetric Key Cryptography. Thus in PKC, the encryption and decryption methods and the public keys of the users are all know to everybody. The only secret is the private key. See the figure below.

Public Key Cryptography uses a special type of Mathematical functions called "trapdoor one-way" function to achieve its goals. A function f is a trapdoot one-way function, if for any x in its domain it is computationally simple to compute f(x), but without the knowledge and use of some secret (trapdoor) it is computationally very hard to compute f^-1(y) for any y in its range.

For example, if m, n and p are any integers, it is simple to compute m × n modulo p. But given a huge number x computing its factors is a very difficult problem. This fact is used in devising the first public key cryptosystem, popularly knon as RSA. The cryptosystem derives its strength from the computationally hard problem, the so called integer factorization problem. The name RSA is derived from the first letters of the names of the people who invented it in 1978: Rivest, Shamir and Addleman. It has been very popular since the day of its invention. The contemporary state of computational technology, speed of processors, memory etc dictates that the size of the keys used in RSA must be 1024 bits in length to provide adequate security for next five/ten years.

For people with some background in Abstract Algebra, here is another example of a one-way trapdoor function: Let G be a cyclic group of large finite orger. Then every element can be represented as a power of a base element αin G. That is if β is any element in G, then β = α^k for some integer k. It is believed that for some groups of very large size, given some β in G, it is computationally very hard to compute k. This is called Discrete Logarithm Problem. ElGamal in 1985 had proposed a beautiful cryptosystem based on this problem named after him as ElGamal Cryptosystem.

The discovery of public key cryptography was inspired by the Key Exchange protocol discovered by Diffie and Hellman a couple of years before RSA. (For Diffie-Helman protocol see my hubpage: Cryptography Simplied).

One major advantage of PKC is digital signatures. a message signed with a sender's private key can be verified by anyone who has access to the sender's public key, thereby proving that the sender had access to the private key (and therefore is likely to be the person associated with the public key used), and the part of the message that has not been tampered with. Because classical (symmetric key) cryptography uses the same key for encryption and decryption, both, it is not possible to define digital signature. This concept is meaningful in the context of PKC only.

The major disdvantages of PKC are (1) Key sizes are much bigger in comparison to symmetric key cryptography (the standard RSA key os now 1024 bits), (2) implementations are quite slower in comparison to the symmetric key. To overcome these, people use PKC for key exchange purpose only. After a successful key exchange, data is encrypted using symmetric key algorithms. Such an implementation is called a hybrid cryptosystem.

ΔΔΔ