Public Key Algorithms in Cryptography

Cryptography is the study and practice of hiding data. It provides the services : Confidentiality, Integrity, Authentication and Non-repudiation.

Cryptography is mainly focused on securing data at transit but it can be used for securing data at rest too. It is heavily used in technical controls.

Cryptography ensures that the message sent by the authorized sender is only received by the authorized recipient. Any other party should not be able to read the message.

Message sent by Alice to Bob should not be readable to Mallory

A plain text, which is the meaningful and useful message is encrypted using an encryption algorithm to create a cipher text. The cipher text thus created, is a meaningless unreadable message. The encryption algorithm uses a key for encrypting. The same key is needed to decrypt and obtain the plain text again.

Most modern encryption algorithms use a key. It is preferable to use a key because the algorithm can even be published while keeping the key a secret.

Some algorithms do not use a key, but such algorithms can be easily cracked using reverse engineering mechanisms.

Public Key Algorithms

A public key algorithm or asymmetric encryption algorithm does not use the same key for encryption and decryption. Instead the sender and receiver use their own keys to encrypt/decrypt.

How does asymmetric cryptography work?

Each party involved has a key pair : public key and private key

If a message is encrypted using a public key, the private key of the same pair is needed to decrypt it. Similarly, a message encrypted with a private key needs the public key from the same pair to decrypt it.

So which key should the sender use to encrypt the message?

Let’s consider the following scenarios using an example where A is the sender and B is the receiver. E could be a man-in-the-middle. Each party has a key pair.

1 Using B’s public key to encrypt

This method is called close message format where the recipient’s public key is used to encrypt the message. B receives the encrypted message and it can only be decrypted using B’s private key.

In this method only confidentiality is maintained. As there is nothing unique to A in the message received by B, B cannot prove that it was sent by A. Hence, no data origin authentication. Integrity and non-repudiation are also not preserved.

2 Using A’s public key to encrypt

Only A’s private key can be used decrypt the message .This is not a practical scenario as B will not be able to decrypt.

3 Using A’s private key to encrypt

This method is called open message format where the sender’s private key is used to encrypt the message.

Although B can decrypt the message using A’s public key this method has no confidentiality as E or any third party can also decrypt the message using A’s public key which is available to anyone. Some refer to this method as signing and not as an encryption.

Although any attacker can decrypt the message and alter it, re-encrypting the altered message is impossible.

Some examples of Public Key Algorithms are Deffie Hellman Key Exchange (DH), Elgamal, Elliptic curves, RSA etc.

Deffie Hellman Key Exchange

In Deffie Hellman Key Exchange or DH algorithm, both sender and receiver use the same key for encryption and decryption. This key is mathematically calculated.

DH was introduced as a means of securely exchanging the key to the receiver’s end. The key is not exchanged over the media but rather a parameter is exchanged.

Initially A and B agree on 2 parameters : g — generator (suppose an integer) and p — a prime number. g should be smaller than p.

Both parties have their private keys and based on g and p the respective public keys will be calculated and shared.

Next, both parties will calculate the keys : K1 by A and K2 by B. These keys are equal and that is the symmetric key used for encryption by A and decryption by B.

Digital Signature

A message can be sent through a hash function to obtain its hash or digital fingerperint. This hash can be encrypted using A’s private key and sent to B. B can then decrypt the hash using A’s public key and check if the message sent by A has been altered.

The encrypted hash is called as the digital signature.

Encrypting a hash is much more easier than encrypting a message. When the message is too large, it is difficult to be encrypted. Therefore encrypting the hash is the standard way. A digital signature preserves authenticity, integrity and non-repudiation.

In most of the countries, a digital signature is a valid evidence for non-repudiations and considered to have the same effect of a physical signature. Why do we use the same physical signature for all instances but different digital signatures for each different message? i. e. Why is a digital signature message-dependent?

This is because anybody can copy and append the digital signature to anything and send. Using message-dependent digital signatures solves this problem.

Properties of a digital signature

> The signature is not re-usable

> It is not alterable

> The signature cannot be repudiated

> The signature is authentic and is not forgeable

Consider a scenario where A has to send a large message to B. If all security services (Confidentiality, integrity, non-repudiation and data origin authentication) should be preserved, how can A send the message?

The most accurate method is : first obtain the hash or digital fingerprint of the message. Second, encrypt the hash using A’s private key. Third, encrypt the message using B’s public key. Now both the encrypted hash and message can be appended and sent to B.

B can now decrypt the hash using A’s public key and the message using B’s private key.

This way B can prove that the message was sent by A and also the message is securely delivered.

Inspired by the little things in life, I aspire to be more.