Public Key Crypto Systems
The concept of public-key cryptography evolved from an attempt to attack two of the most difficult problems associated with symmetric encryption.The first problem is that of key distribution.The key distribution under symmetric encryption requires either that two communicants already share a key, which somehow has been distributed to them; or the use of a key distribution center.Whitfield Diffie, one of the discoverers of public-key encryption (along with Martin Hellman, both at Stanford University at the time), reasoned that this second requirement negated the very essence of cryptography: the ability to maintain total secrecy over your own communication. As Diffie put it , “what good would it do after all to develop impenetrable cryptosystems, if their users were forced to share their keys with a KDC that could be compromised by either burglary or subpoena?”
The second problem that Diffie pondered, and one that was apparently unrelated to the first, was that of digital signatures. If the use of cryptography was to become widespread, not just in military situations but for commercial and private purposes, then electronic messages and documents would need the equivalent of signatures used in paper documents. That is, could a method be devised that would stipulate, to the satisfaction of all parties, that a digital message had been sent by a particular person? This is a somewhat broader requirement than that of authentication, and its characteristics and ramifications are explored later.
Diffie and Hellman achieved an astounding breakthrough in 1976 by coming up with a method that addressed both problems and was radically different from all previous approaches to cryptography, going back over four millennia.In the next subsection, we look at the overall framework for public-key cryptography. Then we examine the requirements for the encryption/decryption algorithm that is at the heart of the scheme.
Public key cryptography is a fundamental aspect of modern security systems, providing a range of essential functions and benefits. Here are some key reasons why public key cryptography is needed:
Secure Communication: Public key cryptography allows two parties to exchange information securely over an insecure channel. Each party has a pair of cryptographic keys: a public key (which can be shared openly) and a private key (which is kept secret). This setup enables the encryption and decryption of messages, ensuring that only the intended recipient can access the information.
Authentication: It helps verify the identity of users and systems. By using digital signatures, which are created using a sender's private key, recipients can verify the authenticity of a message or document using the sender's public key, confirming that the content has not been tampered with.
Integrity: Public key cryptography ensures the integrity of data. Digital signatures not only authenticate the sender but also confirm that the message has not been altered since it was signed, providing assurance that the data remains intact.
Non-repudiation: This property ensures that a sender cannot deny sending a message or transaction. Once a digital signature is attached to a document, it provides legal proof of the origin and integrity of the message, which can be used in disputes.
Key Management: Compared to symmetric key cryptography, which requires the secure exchange of keys, public key cryptography simplifies key management. Users only need to protect their private keys and can freely distribute their public keys.
Scalability: Public key cryptography is more scalable in environments with a large number of users. In such scenarios, maintaining unique keys for each pair of users with symmetric key cryptography becomes impractical, whereas public keys can be openly shared and managed more efficiently.
Confidentiality and Privacy: It ensures that sensitive information is kept confidential, only accessible to those with the appropriate decryption keys. This is crucial in applications such as email encryption, secure web browsing, and data protection.
Implementation of Secure Protocols: Many security protocols and standards, such as SSL/TLS for secure web browsing, PGP for email encryption, and SSH for secure remote access, rely on public key cryptography to establish secure communication channels.
Overall, public key cryptography provides the foundation for secure and trustworthy digital interactions, making it essential in today's interconnected world.
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 characteristic.
• 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 characteristic.
• Either of the two related keys can be used for encryption, with the other used for decryption.
A public-key encryption scheme has six ingredients
- Plaintext: This is the readable message or data that is fed into the algorithm as input.
- Encryption algorithm: The encryption algorithm performs various transformations on the plaintext.
- 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.
- 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.
- Decryption algorithm: This algorithm accepts the ciphertext and the matching key and produces the original plaintext.
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 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 below summarizes some of the important aspects of symmetric and publickey 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.
Secrecy
There is some source $A$ that produces a message in plaintext, $X = [X_1, X_2, . . . ,X_M]$. 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, $PU_b$, and a private key, $PR_b$. $PR_b$ is known only to $B$, whereas $PU_b$ is publicly available and therefore accessible by $A$.
With the message $X$ and the encryption key $PU_b$ as input, $A$ forms the ciphertext $Y = [Y_1, Y_2, . . . , Y_N]$:
$$Y = E(PU_b, X)$$
The intended receiver, in possession of the matching private key, is able to invert the transformation:
$$X = D(PR_b, Y)$$
An adversary, observing $Y$ and having access to $PU_b$, but not having access to $PR_b$ or $X$, must attempt to recover $X$ and/or $PR_b$. 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 $\hat{X}$ . Often, however, the adversary is interested in being able to read future messages as well, in which case an attempt is made to recover $PR_b$ by generating an estimate $\hat{PR_b}$.
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
Authentication
Figure below show the use of public key encryption to provide authentication.
$$Y=E(PR_a,X)$$
$$X=D(PU_a,Y)$$
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.
Authentication and Secrecy
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.
It is important to emphasize that the encryption process depicted 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, 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 as shown in Figure below.
$$Z = E(PU_b, E(PR_a, X))$$
$$X = D(PU_a, D(PR_b, Z))$$
In this case, we begin as before 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
•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 below indicates the applications supported by the algorithms discussed in this course.
Requirements for Public-Key Cryptography
The public key cryptosystem illustrated depends on a cryptographic algorithm based on two related keys. Diffie and Hellman postulated this system without demonstrating that such algorithms exist. However, they did lay out the conditions that such algorithms must fulfill
1.It is computationally easy for a party $B$ to generate a pair (public key $PU_b$, private key $PR_b$).
2.It is computationally easy for a sender $A$, knowing the public key and the message to be encrypted,$M$, to generate the corresponding ciphertext:
$$C = E(PU_b,M)$$
3.It is computationally easy for the receiver $B$ to decrypt the resulting ciphertext using the private key to recover the original message:
$$M = D(PR_b, C) = D[PR_b, E(PU_b,M)]$$
4. It is computationally infeasible for an adversary, knowing the public key, $PU_b$, to determine the private key,$PR_b$
5.It is computationally infeasible for an adversary, knowing the public key, $PU_b$, and a ciphertext, $C$, to recover the original message,$M$.
We can add a sixth requirement that, although useful, is not necessary for all public-key applications:
6. The two keys can be applied in either order:
$$M = D[PU_b, E(PR_b,M)] = D[PR_b, E(PU_b,M)]$$
The requirements boil down to the need for a trap-door one-way function.A one-way function is one that maps a domain into a range such that every function value has a unique inverse, with the condition that the calculation of the function is easy, whereas the calculation of the inverse is infeasible:
$$Y=f(X) \quad easy$$
$$X=f^{-1}(Y) \quad infeasible$$
Generally, easy is defined to mean a problem that can be solved in polynomial time as a function of input length. Thus, if the length of the input is $n$ bits, then the time to compute the function is proportional to $n^a$, where $a$ is a fixed constant. Such algorithms are said to belong to the class $P$.The term infeasible is a much fuzzier concept. In general, we can say a problem is infeasible if the effort to solve it grows faster than polynomial time as a function of input size. For example, if the length of the input is $n$ bits and the time to compute the function is proportional to $2^n$, the problem is considered infeasible. Unfortunately, it is difficult to determine if a particular algorithm exhibits this complexity. Furthermore, traditional notions of computational complexity focus on the worst-case or average-case complexity of an algorithm. These measures are inadequate for cryptography, which requires that it be infeasible to invert a function for virtually all inputs, not for the worst case or even average case.
We now turn to the definition of a trap-door one-way function, which is easy to calculate in one direction and infeasible to calculate in the other direction unless certain additional information is known. With the additional information the inverse can be calculated in polynomial time.We can summarize as follows: A trapdoor one-way function is a family of revertible functions $f_k$, such that
Thus, the development of a practical public-key scheme depends on discovery of a suitable trap-door one-way function.
Public-Key Cryptanalysis
As with symmetric encryption, a public-key encryption scheme is vulnerable to a brute-force attack.The countermeasure is the same: Use large keys. However, there is a tradeoff to be considered. Public-key systems depend on the use of some sort of invertible mathematical function.The complexity of calculating these functions may not scale linearly with the number of bits in the key but grow more rapidly than that. Thus, the key size must be large enough to make brute-force attack impractical but small enough for practical encryption and decryption. In practice, the key sizes that have been proposed do make brute-force attack impractical but result in encryption/decryption speeds that are too slow for general-purpose use. Instead, as was mentioned earlier, public-key encryption is currently confined to key management and signature applications.
Another form of attack is to find some way to compute the private key given the public key. To date, it has not been mathematically proven that this form of attack is infeasible for a particular public-key algorithm.Thus, any given algorithm, including the widely used RSA algorithm, is suspect. The history of cryptanalysis shows that a problem that seems insoluble from one perspective can be found to have a solution if looked at in an entirely different way.
Finally, there is a form of attack that is peculiar to public-key systems.This is, in essence, a probable-message attack. Suppose, for example, that a message were to be sent that consisted solely of a 56-bit DES key. An adversary could encrypt all possible 56-bit DES keys using the public key and could discover the encrypted key by matching the transmitted ciphertext.Thus, no matter how large the key size of the public-key scheme, the attack is reduced to a brute-force attack on a 56-bit key. This attack can be thwarted by appending some random bits to such simple messages.
Comments
Post a Comment