Public Key Cryptography

In the previous article, I discussed an overview of symmetric key cryptographic systems. The major drawback of such a system that held symmetric key cryptography to be used widely in business circles was the exchange of keys over an insecure channel. In the absence of any other method of secure information exchange, governments established methods of managing keys. However, many in the business world were not interested in employing circumspect and perhaps even dangerous methods of key exchanging keys. In the 1960s, this became known as the "key management" problem.

Diffie - Hellman Key exchange

In 1976, Whit Diffie and Martin Hellman published a paper describing a method of establishing a common key securely over an insecure channel which used exponentiation and the fact that exponents can be multiplied in any order with the same results. The protocol (steps) set out here permits two parties (say Alice and Bob) to use these insecure channels to exchange information in such a way that after several communications, they share a single value known only to them and then use this key to further conceal communications.

Step 1: In the first step, Alice and Bob agree on common parameters which do not have to be kept secret from anyone else. These are

• a large prime number q and
• a primitive root a(mod q)

Now both (we take Alice here) generate their own public key independently by

• choosing a secret integer: X_A < q
• and computing their public key: Y_A = a^x_A (mod q)

Alice and Bob now publish their respective public keys Y_A and Y_B wherever they like. In particular, they need to know each other's public keys and can simply send them to each other directly.

Step 2: Alice and Bob now establish a common value as follows:

• Bob computes Y_A^X_B (mod q) using his private key;
• Alice computes Y_B^X_A (mod q) using her private key;
• But both are the same: K_AB = a^X_AX_B (mod q).

Note: Each party uses their own secret key in generating a common value, so no one else is able to do this. Consequently, K _AB is known only to A and to B and can now be used as a key in encryption between Alice and Bob.

However, this scheme was only useful for establishing keys and did not actually encrypt any data. The search was still on for an encryption scheme that allowed anyone to send an enciphered message to any other person without pre-establishing keys, such that only the targeted recipient could decrypt the message.

The first example of such a solution appears to have been developed independently from two sources.

Basically, the idea is for each person to have two keys, one to encrypt and one to decrypt. The two keys would have to be bound together in some fundamental way in order for them to "invert" each other, but it should be impossible for an attacker to derive one from the other. The encryption key would be published as we publish our phone number. However, only the recipient would know his/her decryption key; it would not be revealed to anyone else. This idea completely solved the problem of exchanging keys, except for the fact that initially, no one had a real way of setting up such a scheme.

RSA (Rivest-Shamir-Adleman)

In 1978, the first actual method for implementing such a scheme was published by Ronald Rivest and is now widely known by the first letter of each of the authors' names as RSA. The security of RSA was based on the difficulty of factoring large integers. In 1977, it was finally revealed that members of the British intelligence agency Government Communications Headquarters (GCHQ) had also invented essentially the same scheme early in the 1970s. A detailed description of the RSA scheme will be discussed in later articles.

ElGamal

The ElGamal cryptographic algorithm was invented a few years after the RSA scheme, developing from the PhD thesis of Taher ElGamal, which was awarded in 1984. The underlying security principle on which this scheme is based is quite different from RSA. In ElGamal, the target is to determine the exponent in an equation of the form \(a = b^x\) where a and b are known. A detailed description of the ElGamal scheme will be discussed in later articles.

Elliptical Curve Cryptography (ECC) is another public key encryption algorithm which is reported to be 50 to 100 times faster than RSA on 256-bit security levels.

A Comparison of Symmetric and Asymmetric Key Cryptography

All known asymmetric(public) key schemes are far more computationally expensive than symmetric key schemes. For example, the disadvantage of the ElGamal scheme is that the encrypted message becomes very big, about twice the size of the original message. Similarly, RSA is a lot slower than DES which is a symmetric key protocol, almost by a factor of 1000. For this reason, public key schemes are traditionally used only for small messages, such as secret keys, whereas symmetric key schemes are retained for sending large messages.

Both symmetric and asymmetric key schemes use encryption and decryption keys, but in symmetric key schemes, both of these are identical. In contrast, they are different but related in the asymmetric (public) key system. However, the security of such a system is based on the difficulty of deriving one from another.

Cryptography - More than Just Hiding Secrets

As the adoption of computers and the internet increased for communication, various applications of cryptographical schemes other than just concealing information were developed to address the needs of the digital age.

Q. How to confirm that a message received indeed came from the sender purported? (It's quite easy to change the name of the sender in most e-mail systems).

Q. How to prevent a sender from claiming that they did not, in fact, send the message you received?

Q. How to ensure that the message received was the one sent and had not been altered?

The most recent significant application of cryptography is, therefore, for the identification of senders, authentication of senders and recipients, as well as the message themselves, and digital signatures applied to messages.

Digital Signatures for User Authentication

A digital signature is a method of applying data to a message which identifies the sender of the message in the same way that a written signature on a piece of paper confirms authorship. All known public key schemes can be used to implement this in practice.

In using a public key scheme to send a signed message to Bob, Alice can simply encrypt the message using her private key. When Bob receives the message, he can verify that it was "signed" by Alice by applying Alice's public key to the received encrypted message. The result should be a readable message that makes sense to Bob. If it was not signed with Alice's private key, then applying her public key to decrypt the message would result in nonsense, so Bob can be sure that it was signed by Alice.

Message Authentication

Hashing algorithms, along with encryption schemes, can be used to verify the message and if it has been altered from its original version during the transmission to the recipient. The original message M can be hashed (more on hashing algorithms in later articles), and the generated digest of the message D can be appended to the message M||D. This appended string is then encrypted using the public key of the recipient and the private key of the sender in any order. The recipient, on receiving this doubly encrypted string M||D, can perform double decryption once using his private key and once using the sender's public key in a pre-determined order. He can then separate the message M and digest D using many methods (like the first few bits can be used to depict the length of the message M). He can independently calculate the message digest D' and compare D and D' to verify if the message has been altered from its original version.

That was about public key cryptography from my side. If you want to read about symmetric key cryptography, you can refer to my this article.

Adios 👋