10.4. Public-Key Encryption Protocols
The introduction of public-key encryption brought a revolution to the field of cryptography. Public-key cryptography provided a very clever method for key exchange. In the public-key encryption model, a sender/receiver pair use different keys. This model is sometimes known as asymmetric , or two-key , encryption .
Public-key algorithm is based on mathematical functions rather than on substitution or permutation, although the security of any encryption scheme indeed depends on the length of the key and the computational work involved in breaking an encrypted message. Several public-key encryption protocols can be implemented. Among them, the following two protocols are the focus of our study:
-
Rivert, Shamir, and Aldeman (RSA) protocol
-
Diffie-Hillman key-exchange protocol.
In the public-key encryption methods , either of the two related keys can be used for encryption; the other one, for decryption. It is computationally infeasible to determine the decryption key given only the algorithm and the encryption key. Each system using this encryption method generates a pair of keys to be used for encryption and decryption of a message that it will receive. Each system publishes its encryption key by placing it in a public register or file and sorts out the key as a public one.
The companion key is kept private. If A wishes to send a message to B , A encrypts the message by using B 's public key. On receiving the message, B decrypts it with the private B key. No other recipients can decrypt the message, since only B knows its private key. This way, public-key encryption secures an incoming communication as long as a system controls its private key. However, public-key encryption has extra computational overhead and is more complex than the conventional one.
10.4.1. RSA Algorithm
Rivert, Shamir, and Aldeman developed the RSA public-key encryption and signature scheme. This was the first practical public-key encryption algorithm. RSA is based on the intractability of factoring large integers. Assume that a plaintext m must be encrypted to a ciphertext c . The RSA algorithm has three phases for this: key generation , encryption , and decryption .
Key Generation
In the RSA scheme, the key length is typically 512 bits, which requires an enormous computational power. A plaintext is encrypted in blocks, with each block having a binary value less than some number n . Encryption and decryption are done as follows , beginning with the generation of a public key and a private key.
Begin Key Generation Algorithm
-
Choose two roughly 256-bit prime numbers , a and b , and derive n = ab . (A number is prime if it has factors of 1 and itself.)
-
Find x . Select encryption key x such that x and ( a - 1 )(b - 1) are relatively prime. (Two numbers are relatively prime if they have no common factor greater than 1.)
-
Find y . Calculate decryption key y :
Equation 10.5
-
At this point, a and b can be discarded.
-
The public key = { x , n }.
-
The private key = { y , n }.
In this algorithm, x and n are known to both sender and receiver, but only the receiver must know y . Also, a and b must be large and about the same size and both greater than 1,024 bits. The larger these two values, the more secure the encryption.
Encryption
Both sender and receiver must know the value of n . The sender knows the value of x , and only the receiver knows the value of y . Thus, this is a public-key encryption, with the public key { x , n } and the private key { y , n }. Given m<n , ciphertext c is constructed by
Equation 10.6
Note here that if a and b are chosen to be on the order of 1,024 bits, n 2, 048. Thus, we are not able to encrypt a message longer than 256 characters .
Decryption
Given the ciphertext, c , the plaintext, m , is extracted by
Equation 10.7
In reality, the calculations require a math library, as numbers are typically huge. One can see easily how Equations (10.6) and (10.7) work.
| |
| Example. | For an RSA encryption of a 4-bit message of 1,000, or m = 9, we choose a = 3 and b = 11. Find the public and the private keys for this security action, and show the ciphertext. |
| Solution. | Clearly, n = ab = 33. We select x = 3, which is relatively prime to ( a - 1 )(b - 1) = 20. Then, from xy mod ( a - 1 )(b - 1) = 3 y mod 20 = 1, we can get y = 7. Consequently, the public key and the private key should be {3, 33} and {7, 33}, respectively. If we encrypt the message, we get c = m x mod n = 9 3 mod 33 = 3. The decryption process is the reverse of this action, as m = c y mod n = 3 7 mod 33 = 9. |
10.4.2. Diffie-Hillman Key-Exchange Protocol
In the Diffie-Hillman key-exchange protocol, two end users can agree on a shared secret code without any information shared in advance. Thus, intruders would not be able to access the transmitted communication between the two users or discover the shared secret code. This protocol is normally used for virtual private networks (VPNs), explained in Chapter 16. The essence of this protocol for two users, 1 and 2, is as follows. Suppose that user 1 selects a prime a , a random integer number x 1 , and a generator g and creates y 1 ˆˆ{1, 2, ..., a - 1} such that
Equation 10.8
In practice, the two end users agree on a and g ahead of time. User 2 performs the same function and creates y 2 :
Equation 10.9
User 1 then sends y 1 to user 2. Now, user 1 forms its key, k 1 , using the information its partner sent as
Equation 10.10
and user 2 forms its key, k 2 , using the information its partner sent it as
Equation 10.11
It can easily be proved that the two Keys k 1 and k 2 are equal. Therefore, the two users can now encrypt their messages, each using its own key created by the other one's information.