7
ASYMMETRIC KEY ALGORITHMS

NASRIN SULTANA AND SAIFUL AZAD

Contents

Keywords

7.1 Basic Concept

7.2 Applications of Asymmetric Key Algorithms

7.2.1 Encryption/Decryption

7.2.2 Digital Signature

7.2.3 Encryption and Digital Signature

Keywords

Asymmetric key algorithm

Digital signature

Private key

Public key

In the very early era of cryptography, multiple parties involved in secret message exchange had to depend on a secret key that they interchanged among themselves through a trusted, but noncryptographic method. Generally, simple methods like one-to-one communication through a reliable carrier were exercised to exchange any secret key. They kept this key absolutely secret among themselves. Later, this secret key would be utilized to encrypt their desired messages. Since only the parties involved in the communication had the secret key, they could only decrypt any message exchanged between them. One of the major limitations of this technique was the methods exercised to exchange a secret key. Commonly, some impractical and unsafe methods, like face-to-face meeting or trusted courier service, were employed before the modern era. Although currently the key is exchanged through an existing encryption channel, the security depends on the confidentiality of the previous key exchange. Asymmetric key, also known as public-key cryptography, resolves this issue by not disclosing the secret key to anyone. The users can now communicate and exchange messages securely over a public channel without having to agree upon any shared key beforehand.

For the last 20 years, Whitfield Diffie, Martin Hellman, and Ralph Merkle have been given credit as the cryptographers who discovered the technique of public-key cryptography, while Ron Rivest, Adi Shamir, and Leonard Adleman have been honored for developing RSA, the most integrated implementation of public-key cryptography. However, a recent announcement indicates that the history of cryptography has to be rewritten. According to the British government, public-key cryptography was originally invented at the Government Communications Headquarters (GCHQ) in Cheltenham. It was in the late 1960s that a senior member of the military did some work in the field of nonsecret encryption, which is related to public-key cryptography without the inclusion of the concept of digital signature. There are some evidentiary artifacts available that could support these claims.

In 1969, James Ellis, one of Britain’s foremost government cryptographers, started searching for a way to resolve the key distribution problem. Later, the method explored by Ellis was unlike those of Diffie, Hellman, and Merkle in that it was extremely advanced. However, the discovery of Ellis was sworn to secrecy as he was a recruit of the British government. He conceptualized and developed the theme of separate public-key and private-key use. Meanwhile, he realized that he had to look for a special one-way function that could be reversed if the receiver end had access to some pieces of special information. Unfortunately, he failed to draw any conclusion to the work. In 1973, Clifford Cocks discovered the first workable mathematical formula for nonsecret encryption, and he recorded it in a secret British Communications-Electronics Security Group (CESG) report titled A Note on Non-Secret Encryption. Afterward, in 1974, a few months after Clifford’s discovery, Malcolm Williamson discovered a key exchange method similar to the one discovered by Diffie, Hellman, and Merkle. However, the work of James Ellis, Clifford Cocks, and Malcolm Williamson was not patented for two reasons: (1) patenting would mean forcing GCHQ to reveal the details of their work, which would have been incompatible with GCHQ’s aims as an organization, and (2) in the early 1970s, it was far from the imagination that mathematical algorithms could be patented.

In 1976, it was evident that Diffie and Hellman patented their work on public-key cryptography. At that time, Williamson was eager to go public and stop Diffie and Hellman’s application for patent. He was stopped from doing so by his superiors, who did not have much foresight regarding the digital revolution and the future potential scope of public-key cryptography. In the beginning of the 1980s, Williamson’s superiors realized that their decision was wrong. Development in computing and Internet technology made it clear that RSA and Diffie–Hellman–Merkle key exchanges would both be successful commercial products. Therefore, in 1996, RSA Data Security, Inc. (the company responsible for RSA products) was sold for $200 million. Finally, in 1997, it became known to the public that an asymmetric key algorithm was secretly developed by James H. Ellis, Clifford Cocks, and Malcolm Williamson at the GCHQ in the UK in 1973. Several years later, Ellis, Cocks, and Williamson received the acknowledgment they deserved for their invention.

The motivation of the asymmetric key cryptosystem developed by Diffie and Hellman came from work on public-key distribution by Merkle. A few years later, Rivest, Shamir, and Adleman from MIT independently invented an asymmetric key algorithm commonly known as RSA. They utilize modular arithmetic and two very large prime numbers for encryption and digital signature. Security of the RSA is related to the difficulty of factoring those large prime numbers, for which currently there is no known efficient method. In the mid-1980s, Neal Koblitz and Victor Miller introduced a new public-key algorithm based on a discrete algorithm problem known as the elliptic curve algorithm. Although it utilizes smaller keys for faster operations, it assures estimated security approximately analogous to RSA.

7.1 Basic Concept

As mentioned above, one of the major problems of a secret key (also known as symmetric key) algorithm is the secure key distribution between the two parties, which encouraged people to search for an alternative. The asymmetric key algorithm is a solution that utilizes two separate keys, where one key is kept secret from the external world, which is referred to as the private key, and another one is publicized, referred to as the public key. These keys are constructed in such a way that they conceive mathematical relationships and build on employing integer factorization, discrete logarithm, and elliptic curve algebraic structures. There are a couple of aspects that need to be considered while employing such a cryptographic algorithm:

1. Generating a key pair must be computationally easy and inexpensive.

2. Encryption and decryption using these keys also must be easy and inexpensive.

3. It must be computationally infeasible to unlock a key while knowing the other key.

4. Encryption and decryption of a message need not be possible employing the identical key.

7.2 Applications of Asymmetric Key Algorithms

Asymmetric key algorithms can be used for encryption/decryption, digital signature, or both. They are described in the following sections in detail.

7.2.1 Encryption/Decryption

In the case of encrypting a message, the public key of the recipient is utilized to encrypt a message, which is not possible to decrypt by anyone who does not own the corresponding private key. In other words, the sending party uses the public key of the desired receiver to encrypt a message to be sent. That message can only be decrypted by the desired receiver, who holds the corresponding private key. Thus, it preserves the confidentiality of a message. An example of the encryption technique utilizing asymmetric key algorithms is illustrated in Figure 7.1. Let us assume that Alice and Bob are the two parties who previously decided to exchange their messages securely through non-secure communication media, like the Internet. They come to consent for using an asymmetric key algorithm. Therefore, both of them generate a pair of keys for each. One of them is kept secret and another one is exchanged between them. After receiving the public key of the other party, one stores it in his or her public-key ring. If Bob wants to send a secret message to Alice, he must encrypt the message utilizing Alice’s public key. On the other hand, after receiving this message from Bob, Alice employs her private key to decrypt. Similar procedures are also followed to exchange messages from Alice to Bob.

Figure 7.1 Encryption/decryption technique using asymmetric key algorithm.

7.2.2 Digital Signature

In many cases, along with the confidentiality of a message, it is also necessary to verify the identity of the sender. This could be performed through a digital signature, which is an electronic signature generated through a mathematical scheme. There are three main reasons for applying a digital signature:

1. Authentication: Digital signatures are used to validate the source of a message. A receiver can make sure that the message has been sent from the valid user.

2. Nonrepudiation: A sender cannot deny the transmission of a message if it is digitally signed.

3. Integrity: It also preserves the integrity of a message by not allowing it to alter in transit.

Asymmetric key algorithms also can be utilized to sign a message digitally. A sender’s private key is utilized to sign a message, which can then be verified by the receiver who has access to the sender’s public key. If the message is decrypted successfully, it proves that the sender had proper access to the private key, which is likely to be the authenticated person associated with the public key. It also verifies that the message has not been altered, as a change in the encrypted message would result in a change in the message digest. Recalling the previous example, if Bob wants to digitally sign the message, he must employ his private key to encrypt that message. After receiving that message, if Alice can decrypt the message using Bob’s public key, she can be assured that the message was transmitted by a legitimate party. This scenario is illustrated in Figure 7.2.

Figure 7.2 Digital signature using asymmetric key algorithm.

7.2.3 Encryption and Digital Signature

A message can be both encrypted and digitally signed at the same time by encrypting it twice with different keys and decrypting withtheir relevant keys. As mentioned in the previous sections, if two parties desire to exchange encrypted messages among themselves, the sender must encrypt a message with the public key of the receiver. Again, for digitally signing a message, the sender must encrypt the message with his or her private key. Therefore, whenever a sender wants both, he or she must encrypt a message with his or her private key (for digital signature), and then again encrypt that message using the receiver’s private key (for encryption). It this case, the sequence of encryptions needs to be maintained precisely to achieve the plaintext. On the other hand, after receiving this message, it must be decrypted using two relevant keys following the encryption sequence. If the plaintext is possible to acquire after the decryption, a receiver can presume that the packet was received from a valid sender and the message is without any alteration. An example of such a technique is given in Figure 7.3.

Figure 7.3 Encryption/decryption and digital signature using asymmetric key algorithm.

Table 7.1 Application of Asymmetric Key Algorithms

A summary of the above discussions is given in Table 7.1.

In the next two chapters, renowned algorithms—RSA and elliptic curve cryptography—will be discussed in detail with their relative operational methods and implementation.