Public-Key Cryptosystems

 Public-Key Cryptosystems

Asymmetric algorithms rely on one key for encryption and a different but related key for decryption.

These algorithms have the following important characteristics:

• It is computationally infeasible to determine the decryption key given only knowledge of the cryptographic algorithm and the encryption key.

In addition, some algorithms, such as RSA, also exhibit the following characteristics:

• Both related keys can be used for encryption, with the other for decryption.

A public-key encryption scheme has six ingredients (Figure 1):

1. Plaintext: This is the readable message or data that is fed into the algorithm as input.
2. Encryption algorithm: The encryption algorithm performs various transformations on the plaintext.
3. Public and private keys: This is a pair of keys that have been selected so that if one is used for encryption, the other is used for decryption. The exact transformations performed by the algorithm depend on the public or private key that is provided as input.
4. Ciphertext: This is the scrambled message produced as output. It depends on the plaintext and the key. For a given message, two different keys will produce two different ciphertexts.
5. Decryption algorithm: This algorithm accepts the ciphertext and the matching key and produces the original plaintext.

Figure 1. Public-Key Cryptography

The essential steps are the following:

1. Each user generates a pair of keys to be used for the encryption and decryption of messages
2. Each user places one of the two keys in a public register or other accessible file. This is the public key. The companion key is kept private. As Figure 9.1a suggests, each user maintains a collection of public keys obtained from others.
3. If Bob wishes to send a confidential message to Alice, Bob encrypts the message using Alice's public key.
4. When Alice receives the message, she decrypts it using her private key. No other recipient can decrypt the message because only Alice knows Alice's private key.

With this approach, all participants have access to public keys, and private keys are generated locally by each participant and therefore need never be distributed. As long as a user's private key remains protected and secret, incoming communication is secure. At any time, a system can change its private key and publish the companion public key to replace its old public key.

Table 1 ahead summarizes some of the important aspects of symmetric and public-key encryption. To discriminate between the two, we refer to the key used in symmetric encryption as a secret key. The two keys used for asymmetric encryption are referred to as the public key and the private key.  Invariably, the private key is kept secret, but it is referred to as a private key rather than a secret key to avoid confusion with symmetric encryption.

The following notation is used consistently throughout. A secret key is represented by Km, where m is some modifier; for example, Ka is a secret key owned by user A. A public key is represented by PUa, for user A, and the corresponding private key is PRa, Encryption of plaintext X can be performed with a secret key, a public key, or a private key, denoted by E(Ka, X), E(PUa, X), and E(PRa, X), respectively. Similarly, decryption of ciphertext C can be performed with a secret key, a public key, or a private key, denoted by D(Ka, X), D(PUa, X), and D(PRa, X), respectively.

Conventional Encryption	Public-Key Encryption
Needed to Work:	Needed to Work:
The same algorithm with the same key is used for encryption and decryption.      The sender and receiver must share the algorithm and the key.	One algorithm is used for encryption and decryption with a pair of keys, one for encryption and one for decryption.      The sender and receiver must each have one of the matched pair of keys (not the same one).
Needed for Security:	Needed for Security:
The key must be kept secret.      It must be impossible or at least impractical to decipher a message if no other information is available.      Knowledge of the algorithm plus samples of ciphertext must be insufficient to determine the key.	One of the two keys must be kept secret.      It must be impossible or at least impractical to decipher a message if no other information is available.       Knowledge of the algorithm plus one of the keys plus samples of ciphertext must be insufficient to determine the other key.

Table 1. Conventional and Public-Key Encryption

Let us take a closer look at the essential elements of a public-key encryption scheme, using Figure 9.2 (compare with Figure 2.2). There is some source A that produces a message in plaintext, X =[X1, X2,..., XM,]. The M elements of X are letters in some finite alphabet. The message is intended for destination B. B generates a related pair of keys: a public key, PUb, and a private key, PUb. PUb is known only to B, whereas PUb is publicly available and therefore accessible by A.

Figure 2. Public-Key Cryptosystem: Secrecy

With the message X and the encryption key PUb as input, A forms the ciphertext Y = [Y1, Y2,..., YN]:

Y = E(PUb, X).

The intended receiver, in possession of the matching private key, is able to invert the transformation:

X = D(PRb, Y).

An adversary, observing Y and having access to PUb but not having access to PRb or X, must attempt to recover X and/or PRb. It is assumed that the adversary does have knowledge of the encryption (E) and decryption (D) algorithms. If the adversary is interested only in this particular message, then the focus of effort is to recover X, by generating a plaintext estimate x(with cap) Often, however, the adversary is interested in being able to read future messages as well, in which case an attempt is made to recover PRb by generating an estimate PRb(with cap).

We mentioned earlier that either of the two related keys can be used for encryption, with the other being used for decryption. This enables a rather different cryptographic scheme to be implemented. Whereas the scheme illustrated in Figure 9.2 provides confidentiality, Figures 1b and 3 show the use of public-key encryption to provide authentication:

Y = E(PRa', X)

Y = E(PUa', Y)

Figure 3. Public-Key Cryptosystem: Authentication

In this case, A prepares a message to B and encrypts it using A's private key before transmitting it. B can decrypt the message using A's public key. Because the message was encrypted using A's private key, only A could have prepared the message. Therefore, the entire encrypted message serves as a digital signature. In addition, it is impossible to alter the message without access to A's private key, so the message is authenticated both in terms of source and in terms of data integrity.

In the preceding scheme, the entire message is encrypted, which, although validating both author and contents, requires a great deal of storage. Each document must be kept in plaintext to be used for practical purposes. A copy also must be stored in ciphertext so that the origin and contents can be verified in case of a dispute. A more efficient way of achieving the same results is to encrypt a small block of bits that is a function of the document. Such a block, called an authenticator, must have the property that it is infeasible to change the document without changing the authenticator. If the authenticator is encrypted with the sender's private key, it serves as a signature that verifies origin, content, and sequencing. Chapter 13 examines this technique in detail.

It is important to emphasize that the encryption process depicted in Figures 9.1b and 9.3 does not provide confidentiality. That is, the message being sent is safe from alteration but not from eavesdropping. This is obvious in the case of a signature based on a portion of the message, because the rest of the message is transmitted in the clear. Even in the case of complete encryption, as shown in Figure 9.3, there is no protection of confidentiality because any observer can decrypt the message by

using the sender's public key. 

It is, however, possible to provide both the authentication function and confidentiality by a double use of the public-key scheme (Figure 4):

Z = E(PUb, E(PRa, X))

X = D(PUa, E(PRb, Z))

Figure 4. Public-Key Cryptosystem: Authentication and Secrecy

In this case, we begin by encrypting a message, using the sender's private key. This provides the digital signature. Next, we encrypt again, using the receiver's public key. The final ciphertext can be decrypted only by the intended receiver, who alone has the matching private key. Thus, confidentiality is provided. The disadvantage of this approach is that the public-key algorithm, which is complex, must be exercised four times rather than two in each communication.

Applications for Public-Key Cryptosystems

Before proceeding, we need to clarify one aspect of public-key cryptosystems that is otherwise likely to

lead to confusion. Public-key systems are characterized by the use of a cryptographic algorithm with two keys, one held private and one available publicly. Depending on the application, the sender uses either the sender's private key or the receiver's public key, or both, to perform some type of cryptographic function. In broad terms, we can classify the use of public-key cryptosystems into three categories:

• Encryption/decryption: The sender encrypts a message with the recipient's public key.
• Digital signature: The sender "signs" a message with its private key. Signing is achieved by a cryptographic algorithm applied to the message or to a small block of data that is a function of the message.
• Key exchange: Two sides cooperate to exchange a session key. Several different approaches are possible, involving the private key(s) of one or both parties.

Some algorithms are suitable for all three applications, whereas others can be used only for one or two

of these applications. Table 2 indicates the applications supported by the algorithms discussed in this

book.

Table 2. Applications for Public-Key Cryptosystems

Download below given Presentation for the referances.

References:

1. Cryptography and Network Security Principles and Practices, Fourth Edition By William Stallings.