20 Public Key Cryptography

LEARNING OBJECTIVES:

• To understand the definitions of Public Key Cryptography
• To understand the need for symmetric and asymmetric cryptography
• To know the basic terms related with Digital signature and Digital certificate

1. Introduction:

Symmetric-Key Cryptography: Symmetric-key cryptography uses a single key for both encryption and decryption. Encryption and decryption algorithm are inverse of each other.

Example:

• To create the cipher text from the plaintext John uses an encryption algorithm and a key.
• To create the plaintext from cipher text, Bob uses the decryption algorithm and the same key.

Asymmetric-Key cryptography: It is also called public key cryptography. In public key cryptography two keys: a private key and a public key is used. Encryption is done through the public key and decryption through private key. Receiver creates both the keys and is responsible for distributing its public key to the communication community.

Example:

  The sender (say John) uses the public key to encrypt the plaintext into ciphertext and the receiver (say Bob) uses his private key to decrypt the ciphertext.

Unlike symmetric key cryptography, we do not find historical use of public-key cryptography. It is a relatively new concept.

Symmetric cryptography was well suited for organizations such as governments, military, and big financial corporations were involved in the classified communication.

With the spread of more unsecure computer networks in last few decades, a genuine need was felt to use cryptography at larger scale. The symmetric key was found to be non-practical due to challenges it faced for key management. This gave rise to the public key cryptosystems.

The most important properties of public key encryption scheme are −

• Different keys are used for encryption and decryption. This is a property which set this scheme different than symmetric encryption scheme.
• Each receiver possesses a unique decryption key, generally referred to as his private key.
• Receiver needs to publish an encryption key, referred to as his public key.

Some assurance of the authenticity of a public key is needed in this scheme to avoid spoofing by adversary as the receiver. Generally, this type of cryptosystem involves trusted third party which certifies that a particular public key belongs to a specific person or entity only.

Encryption algorithm is complex enough to prohibit attacker from deducing the plaintext from the cipher text and the encryption (public) key.

Though private and public keys are related mathematically, it is not be feasible to calculate the private key from the public key. In fact, intelligent part of any public-key cryptosystem is in designing a relationship between two keys.

The shorter keys result in two benefits −

• Ease of key management
• Efficient computation

These benefits make elliptic-curve-based variants of encryption scheme highly attractive for application where computing resources are constrained.

1. Key Distribution Problem

In symmetric key cryptosystems, over complete graph with n nodes, nC₂ = n(n-1)/2 pairs secret keys are required.

Example: n=100, 99 x 50 = 4,950 keys are required

Problem: Managing large number of keys and keeping them in a secure manner is difficult.

Secret keys are required between (a,b), (a,c), (a,d), (a,e), (b,c), (b,d), (b,e), (c,d), (c,e), and (d,e)

The briefcase example with unshared key

The briefcase has to be sent back and forward three times, which seems pretty inefficient.

2.      Public-Key Cryptography

The public key systems, uses two keys. The development of public-key cryptography is the greatest and perhaps the only true revolution in the entire history of cryptography. It is asymmetric, involving the use of two separate keys, in contrast to symmetric encryption, which uses only one key. Anyone knowing the public key can encrypt messages or verify signatures, but cannot decrypt messages or create signatures, counter-intuitive though this may seem. It works by the clever use of number theory problems that are easy one way but hard the other. Note that public key schemes are neither more nor less secure than private key (security depends on the key size for both), nor do they replace private key schemes (they are too slow to do so), rather they complement them. Both also have issues with key distribution, requiring the use of some suitable protocol.

The major issues in Public-Key Cryptography  are:

– key distribution – how to have secure communications in general without having to trust a KDC with your key

– digital signatures – how to verify a message comes intact from the claimed sender

Each entity in public key cryptography has two keys:

• A public-key
  • Public to anybody
  • used to encrypt messages and verify signatures
• A private-key
  • known only to the owner
  • used to decrypt messages, and sign (create) signatures

For example:

Public Key = 4, Private Key = 1/4, message M = 5

Encryption:

Ciphertext C = M * Public Key

5 * 4 = 20

Decryption:

Plaintext M = C * Private Key

20 * ¼ = 5

3.  Public Key Encryption

Both sender and recipient is having two keys in public key cryptosystem. Here during encryption, cipher text is generated with recipient’s public key.

Decryption is done with recipient’s private key and plain text is retrieved. No nodes other than intended recipient can do the decryption, because the private is not known to other nodes in the network.

Hybrid Encryption Systems

All known public key encryption algorithms are much slower than the fastest secret-key algorithms. In a hybrid system, Alice uses Bob’s public key to send him a secret shared session key. Alice and Bob use the session key to exchange information

4.  Digital Signature

A conventional signature has the following salient characteristics: relative ease of establishing that the signature is authentic, the difficulty of forging a signature, the non-transferability of the signature, the difficulty of altering the signature, and the nonrepudiation of signature to ensure that the signer cannot later deny signing. A digital signature should have all the aforementioned features of a conventional signature plus a few more as digital signatures are being used in practical, but sensitive, applications such as secure e-mail and credit card transactions over the Internet. Since a digital signature is just a sequence of zeroes and ones, it is desirable for it to have the following properties: the signature must be a bit pattern that depends on the message being signed (thus, for the same originator, the digital signature is different for different documents); the signature must use some information that is unique to the sender to prevent both forgery and denial; it must be relatively easy to produce; it must be relatively easy to recognize and verify the authenticity of digital signature; it must be computationally infeasible to forge a digital signature either by constructing a new message for an existing digital signature or constructing a fraudulent digital signature for a given message; and it must be practical to recopies of the digital signatures in storage for arbitrating possible disputes later. To verify that the received document is indeed from the claimed sender and that the contents have not been altered, several procedures, called authentication techniques, have been developed. However, message authentication techniques cannot be directly used as digital signatures due to inadequacies of authentication techniques. For example, although message authentication protects the two parties exchanging messages from a third party, it does not protect the two parties against each other. In addition, elementary authentication schemes produce signatures that are as long as the message themselves.

Creating and verifying a digital signature

A simple generic scheme for creating and verifying a digital signature is shown in Figure respectively. A hash function is applied to the message that yields a fixed-size message digest. The signature function uses the message digest and the sender’s private key to generate the digital signature. A very simple form of the digital signature is obtained by encrypting the message digest using the sender’s private key. The message and the signature can now be sent to the recipient. The message is unencrypted and can be read by anyone. However, the signature ensures authenticity of the sender (something similar to a circular sent by a proper authority to be read by many people, with the signature attesting to the authenticity of the message). At the receiver, the inverse signature function is applied to the digital signature to recover the original message digest. The received message is subjected to the same hash function to which the original message was subjected. The resulting message digest is compared with the one recovered from the signature. If they match, then it ensures that the message has indeed been sent by the (claimed) sender and that it has not been altered.

5. Digital Certificate

A digital certificate is a certificate issued by a CA to verify the identity of the certificate holder. It actually uses a digital signature to attach a public key with a particular individual or an entity. Typically, a digital certificate contains the following information: a serial number that is used to uniquely identify a certificate, the individual or the entity identified by the certificate and the algorithm that is used to create the signature.

Elements of Digital Certificate

A Digital ID typically contains the following information:

–  Your public key, Your name and email address

–  Expiration date of the public key, Name of the CA who issued your Digital ID

Certificate Validation

Essentially, this is just checking the digital signature ,but you may have to “walk the path” of all subordinate authorities until you reach the root

–  Unless you explicitly trust a subordinate CA

Summary

We have considered:

–  Symmetric and Asymmetric cryptography.

–  Public Key cryptography.

–  Creation, Verification, transmission of digital signatures.

–  Elements of Digital Certificate and Certificate validation.