6
Asymmetric-key Algorithms
1. What are the requirements of asymmetric-key cryptography?
Or
What are the characteristics that an asymmetric-key cryptographic algorithm must possess?
Ans.: Asymmetric-key cryptography requires the use of two different keys: the public key for encryption and private key for decryption. The public key is known to everyone, whereas the private key is known to its owner only. Diffie and Hellman laid out some requirements that must be fulfilled by the algorithms used for asymmetric-key cryptography. These requirements are listed below:
It should be easy for the receiver to generate the pair of keys (public and private).
It should be easy for the sender to generate the ciphertext from the original message (that is, the plaintext) with the help of the receiver's public key.
It should be easy for the receiver to decrypt the ciphertext generated by the sender by using its private key in order to recover the original message.
It should be infeasible for an intruder to determine the private key of the receiver, even if he or she knows the public key of the receiver.
It should be infeasible for an intruder to determine the original message even if he or she knows the public key of the receiver as well as the ciphertext.
It should be possible to use any of the two keys (public or private) for encryption and decryption. That is, it should be possible to encrypt the message with any one of the keys and decrypt it using the other.
2. Explain the RSA cryptosystem.
Ans.: In 1978, a group at MIT discovered a strong method for public-key encryption. It is known as RSA, the name derived from the initials of its three discoverers Ron Rivest, Adi Shamir, and Len Adleman. RSA cryptosystem is the most widely accepted asymmetric-key algorithm; in fact, most of the practically implemented security systems are based on RSA. The algorithm requires keys of at least 1024 bits for good security. This algorithm is based on some principles from number theory, which states that determining the prime factors of a large number is extremely difficult.
RSA Key Generation
Let A and B be two users who wish to communicate. Suppose that A wants to send a message securely to B. To encrypt the message, A needs to know B's public key. Thus, B uses the following steps to generate his or her public and private keys.
1. Choose two large distinct prime numbers, p and q (about 1024 bits), such that p ≠q.
2. n: = p*q
3. Φ(n): =(p-1)*(q-1)
4. Choose a number E such that 1 < E < Φ(n), and such that E is relatively prime to Φ(n). The public (encryption) key is (E, n), which is announced publicly.
5. Find another number D such that E * D = 1 mod Φ(n), that is, D = E-1 mod Φ(n). In other words, D is the inverse of E modulo Φ(n). The private (decryption) key is D, which is kept secret.
An important property of RSA algorithm is that the roles of E and D can be interchanged. As the number theory suggests, it is very hard to find the prime factors of a large number n, and hence it is extremely difficult for an intruder to determine the private key D using just E and n.
RSA Encryption and Decryption
In RSA, modular exponentiation is used for performing encryption and decryption. For example, if A has to send a message to B using B's public key (E, n), A encrypts the plaintext (P) to produce the ciphertext (C), as shown here:
C = PE mod n
After B has received the ciphertext (C), he or she decrypts the ciphertext using its private key (D) to get back the original plaintext (P) as shown here.
P = CD mod n
3. Discuss the different attacks on RSA.
Ans.: Although RSA is a secure algorithm used for encryption in public-key cryptography, there are still some weaknesses that enable an attacker to crack the security of the algorithm. There are several attacks that have been predicted on the basis of weak plaintext, parameter selection or inappropriate implementation. These attacks are discussed as follows:
Factorization attack: This attack is possible if the value of n is small, so that the intruders can easily factorize n and obtain the value of p and q (as n = p × q). As the value of e is public, it may further result in obtaining the value of Φ(n) and d (as d = e-1 mod (p-1)(q-1)). Thus, by using all these values, an intruder can now decrypt any encrypted plaintext and crack the security. To prevent such an attack, n must be more than 300 decimal digits, so that it becomes infeasible to factorize such a long value of n.
Chosen-ciphertext attack: This attack tries to get the plaintext from the ciphertext by using the multiplicative property of RSA. Suppose the sender sends the ciphertext (C) to the receiver and an intruder intercepts it. Now, the intruder sends fake ciphertext, say Y, to the receiver by choosing a random integer X. As the receiver is unaware about the interception of the original ciphertext, he or she decrypts the fake ciphertext by performing Yd mod n to get Z. Thus, an intruder can now easily get the plaintext (P), as P = Z * X-1 mod n. That is, an intruder needs to find only the multiplicative inverse of X to get the original plaintext. Therefore, the name of attack is chosen-ciphertext attack, as only the particular ciphertext was chosen to know the corresponding plaintext.
Timing attack: This is a cipher-text-only attack that was unveiled by Paul Kocher. In this attack, an intruder determine a private key by keeping track of how long a computer takes to decrypt the encrypted plaintext. That is, variable timing in evaluation helps an intruder find the value of each bit in d. This means that an intruder can now perform bit-by-bit analysis of the exponential. Such an attack can be prevented if random delays are added to exponentiation, such that the underlying hardware takes a random amount of time to process each. In addition, the concept of blinding can also be used. In this concept, the ciphertext is multiplied by a random number before evaluation. Thus, an intruder will be unable to decipher the ciphertext bits and, therefore, bit-by-bit analysis can be prevented.
Plaintext attack: In this attack, an intruder already knows something about the plaintext. This helps the intruder to also know about the fact that the ciphertext is the permutation of the plaintext. Thus, an intruder can now compute all the possible messages until the result is equal to the ciphertext intercepted.
Common modulus attack: In this attack, a common modulus is used by a group of people. That is, a whole group agrees for a trusted third party to select the values of two prime numbers p and q, computes n and Φ(n) and then creates exponents (ei ,di) for each person belonging to the group. By doing this, any person who is a member of the group can decrypt the ciphertext by factoring n and can also compute the receiver's private exponent (dr) . Therefore, to prevent such attack, the modulus must not be shared, and each person in the group must calculate his or her own modulus.
4. Discuss the uses of public-key cryptography in relation to key distribution.
Ans.: One of the major problems in secret-key cryptography is that of key distribution, which can be overcome by the use of public-key cryptography. The two aspects that must be taken into account for using public-key cryptography include the distribution of public keys and the use of public-key encryption for the distribution of secret keys.
Distribution of Public Keys
There are several schemes that have been used for the distribution of public keys. These schemes are as follows:
Public announcement: The main focus of public-key encryption is on the fact that the public key should be public; that is, a user can send his or her public key to any other user or broadcast it to a large community. Though this approach is convenient, it has some drawbacks. The main problem is that of forgery. That is, anyone can forge the key while it is being transmitted. For example, someone could pretend to be user A and send a public key to another user or broadcast it to many users. Until the original user A comes to know about this forgery and alerts other users, the forger is able to read all the messages intended for user A.
Public directory: As the public announcement scheme for the distribution of public keys was not too secure and there were chances of forgery, a new scheme was introduced, in which a dynamic directory having the name and public key entry for each user is maintained and distributed by some trusted authority. This approach assumes that the public key of the authority is known to everyone, however the corresponding private key is known only to the authority. Each user has to register his or her public key with the directory authority. The authority either publishes the entire directory periodically in a widely circulated newspaper, or the user can access the directory electronically. The user can replace its existing key with a new one as per his or her choice. Although this scheme is more secure than public announcement, it has some weaknesses. If anyone is able to compute the private key of the directory authority, the person would get the authority to pass around the fake public keys and, later, may pretend to be a genuine user and eavesdrop on the messages being sent to any other user. The fake user may also read or alter the records kept by the authority.
Public-key authority: In public directory scheme, if the private key of the authority is stolen, then it may result in loss of data. Thus, to achieve stronger security for public-key distribution, a tighter control needs to be provided over the distribution of public keys from the directory. In this case also, a central authority maintains the dynamic directory of the public keys of all the users. The user knows only the public key of the authority, while the corresponding private key is secret to the authority.
To understand how the public-key authority scheme works, consider two users A and B who wish to communicate securely. To enable communication, the following steps are used.
1. A sends a timestamped message containing a request for the current public key of B to the public-key authority.
2. The authority responds by sending A a message that is encrypted using the private key of authority (say, Pauthority ). The user A attempts to decrypt the message using the authority's public key. If the message gets decrypted, A is assured that the message has been sent by the authority itself. The message sent by the authority contains the following:
B's public key (say, PUBB), which can be used by A to send messages to B.
The original request sent by A, so that A can match the message received from the authority with its corresponding request, and also verify that the request was not altered before reaching the authority.
The original timestamp, so that A can verify whether the message is a new one containing the current public key of B, or an old message containing any other public key.
3. A stores B's public key and uses it to encrypt the message destined for B containing an identifier of A (say, IA) and a nonce N1, which uniquely identifies this transaction.
4. B also follows the same method to retrieve A's public key from the authority. It stores the A's public key for future use. Now, both A and B have got the public keys of each other and, thus, may start exchange messages.
5. B sends a message to A, encrypting it with the public key of A (PUBA). The message contains A's nonce N1 as well as B's nonce N2. As the message could have been decrypted by B only, the inclusion of N1 in the message assures A that the corresponding user is B.
6. A returns N2, encrypted with B's public key (PUBB), to assure B that the corresponding user is A.
Note that the first four steps need not to be followed each time, as the users A and B can store the public keys of each other for future use. This technique is known as caching. However, the users should periodically request for fresh or new copies of the public keys.
Public-key (or digital) certificates: A better approach where a user can exchange keys without communicating to the public-key authority is to use digital certificates—an electronic document that signifies the association between the user and his/her public key. A certificate authority, such as a government agency or some trusted institution, issues a certificate to each user, which contains a public key and the identifier of the key owner. The certificate is signed by the certificate authority. A user can present his or her public key to the authority to get the certificate. The user can then publish his or her certificate. Now, any other user wishing to get the public key can obtain the certificate and verify its validity by means of the attached trusted signature. The user can also send his or her key information to another user by transmitting the certificate. Users can easily verify that the certificate has been generated by the authority and that it is not a fake certificate. Moreover, only the certificate authority can create or update the certificates.
Distribution of Secret Keys using Public-key Cryptography
The public-key encryption can be exclusively used for providing distribution of secret keys that are to be used for conventional encryption. There are certain schemes for this, which are described as follows:
Simple method: In this method, a session is created between the two users who wish to communicate (say, A and B). When A wants to communicate with B, he or she first creates a pair of public and private keys. Then, A transmits to B a message that contains the public key and A's identifier. B creates a secret key, encrypts it with the public key of A, and sends it to A. A recovers the secret key by decrypting the received encrypted message using his or her private key. At this point, both A and B know the secret key. After exchanging the secret key, A discards both the public and private keys, and B discards the public key. Now, both A and B can securely communicate using conventional encryption and the secret key.
The main advantage of this technique is that no keys exist before the start of the communication and none exists after the communication ends. Therefore, the risk of compromising the keys is minimal, and the communication is secure from eavesdropping. Note that the technique is well suited when the only threat is eavesdropping, as it does not provide confidentiality and assure authenticity of the message.
Distribution with confidentiality and authentication: This method provides protection against both active and passive attacks. To prevent the transmission of the message from attacks, assuming that A and B have already exchanged their public keys by any of the earlier-discussed schemes, the following steps take place:
1. A sends a message to B, encrypted with the public key of B, say PUBB. The message contains an identifier of A (say, IA) and a nonce N1, which is used to identify this transaction uniquely.
2. B sends a message to A encrypted with the public key of A (say, PUBA). The message contains A's nonce N1 as well as B's nonce N2. Since only B could have decrypted the message sent by A, the inclusion of B's nonce in the message assures A that the corresponding user is B. Similarly, A sends B's nonce N2, encrypted with B's public key, to assure B that the corresponding user is A.
3. A chooses a secret key (say, SCRA), encrypts it with its private key (PRVA) and sends a message m, encrypted with B's public key (PUBB), as shown here:
m = EPUBB[EPRVA[SCRA]]
Encrypting the message m with B's public key ascertains that only B can read it, and encrypting the message with A's private key ascertains that only A could have sent it.
4. Now, B decrypts the message by computing DPUBA[DPRVB[m]], thus recovering the secret key. This method ensures both confidentiality and authenticity in the exchange of a secret key.
Hybrid method: This method uses the key distribution centre (KDC), in which a secret master key is shared with each user. The role of KDC is to distribute the session secret keys, encrypted using the master key. A public-key scheme is used for the distribution of the session key. Generally, the applications in which session keys often change, the use of public-key encryption for distributing the secret session keys could degrade the overall system's performance. This is because relatively high computational efforts are required for the public-key's encryption and decryption.
The main advantage of this three-level hierarchy is that public-key encryption is rarely used to update the master key between a user and a KDC. Moreover, the scheme is compatible with existing KDC schemes and, thus, can be overlaid on existing schemes with minimal changes required.
5. Discuss Diffie-Hellman key exchange algorithm. Also discuss about its security.
Ans.: Diffie-Hellman key exchange is the first published public-key algorithm that was published in 1976 by Whitefield Diffie and Martin Hellman. This algorithm was devised for the exchange of secret keys between the communicating users in a secure manner. It allows two users to securely exchange a key that can be further used for encryption of messages. Notice that this algorithm can be used only for the exchange of keys, and not for encryption and decryption.
Diffie-Hellman key exchange algorithm enables two users to establish a symmetric session (secret) key without requiring the use of KDC. This is what is referred to as the symmetric-key agreement. Once both the communicating parties have agreed (exchanged) on the common secret key, then a symmetric-key encryption algorithm can be used for encryption and decryption of messages.
Diffie-Hellman algorithm
Consider two users A and B who want to communicate with each other securely over an insecure network. Initially, both A and B need to agree upon a key that is to be used for encryption and decryption of the messages. For this, they can follow the Diffie-Hellman key exchange algorithm, which is given below:
1. Select two numbers p and q by the mutual agreement of A and B, such that p is prime, q is a primitive root of p and q < p. There is no need to keep these two numbers secret.
2. A selects a random number XA (less than p), which becomes his or her private key. Then it computes its public key, YA, as shown here:
YA = qXA mod p
A sends its public key YA to B.
3. B selects a random number XB (less than p), which becomes his or her private key. Then, it computes its public key, YB, as shown here:
YB = qXB mod p
B sends its public key YB to A.
4. After exchanging the public keys, both A and B compute the common secret key(K). A generates the secret key as shown here:
K =(YB)XA mod p
B generates the secret key as shown here:
K =(YA)XB mod p
Proof of algorithm
To show that both A and B have computed the same secret key, we need to prove that the calculation of K by A and B produce the identical results.
Hence, proved.
Security of the Diffie-Hellman algorithm
In Diffie-Hellman algorithm, the private keys XA and XB are secret, while the numbers p and q and the public keys YA and YB are known to everyone. Thus, an opponent has p,q,YA and YB to work with. To determine the key using the available information, the opponent has to use the discrete logarithm. For example, if the opponent wants to find the private key of user A, then he or she has to perform the following calculation:
XA = dlogq,p(YA)
After computing XA, the opponent can compute the common secret key (K) in the same way that A computed it. Since it is difficult to compute the discrete logarithm in comparison to computing exponentials modulo a prime number, the security of the Diffie-Hellman algorithm depends on this fact. In case of large prime numbers, it is infeasible to compute the discrete logarithm and, thus, to break the security of the Diffie-Hellman algorithm.
5. List some advantages of the Diffie-Hellman algorithm.
Ans.: Some advantages of the Diffie-Hellman key exchange algorithm are as follows:
Secret keys are generated as and when required. Thus, they need not be stored for a long time, thereby making them less vulnerable to attacks.
No pre-existing infrastructure is required for key exchange. The communicating parties just have to agree upon the values of global variables p and q.
6. What are the limitations of the Diffie-Hellman algorithm?
Ans.: Although the Diffie-Hellman key exchange algorithm allows two communicating parties to securely exchange the key over an insecure network, there are a number of weaknesses to this algorithm, which are given below:
It does not provide any information regarding the identities of the users exchanging the key. In other words, it does not authenticate the communicating users.
It is vulnerable to man-in-the-middle-attack, where a third user (say, C) pretends to be user B while communicating with A and pretends to be user A while communicating with B, thereby intercepting their messages. This attack is discussed in the next question.
It involves a lot of computations and, thus, is subject to clogging attacks . In this attack, an opponent requests for a large number of keys, thus keeping the victim busy in doing unnecessary calculations rather than doing the real work.
7. Explain the man-in-the-middle attack.
Ans.: As the Diffie-Hellman algorithm does not authenticate the users exchanging the keys, it is vulnerable to man-in-the-middle attacks, also referred to as the bucket brigade attack. To understand this attack, consider that A and B are two users who want to communicate and, thus, exchange their keys using the Diffie-Hellman algorithm. Let C be an opponent who wants to intercept the communication between A and B. Now, the man-in-the-middle attack proceeds as follows:
1. A sends a message containing its public key (YA) to B.
2. C intercepts this message, stores A's public key and sends a new message containing its public key (YC) and A's user ID to B.
3. On receiving the message, B saves the C's public key (YC) with A's user ID.
4. B sends a message containing its public key (YB) to A.
5. The opponent C intercepts this message, stores B's public key (YB) and sends a new message containing its public key (YC) and B's user ID to A.
6. On receiving the message, A saves C's public key (YC) with B's user ID.
7. A computes the secret key K1 based on its private key XA and C's public key YC as shown here:
K1 =(YC)XA mod p
8. B computes the secret key K2 based on its private key XB and C's public key YC, as shown here:
K2 =(YC)XB mod p
9. C computes K1 using its private key XC and YA and computes K2 using XC and YB as shown here:
K1 =(YA)XC mod p
K2 =(YB)XC mod p
At this point, A and B think that they have shared a common secret key; however, actually A and C have shared the key K1, whereas B and C have shared the key K2. The opponent C is now able to trap all the messages coming from A to B and B to A, without letting A and B know that their communication is shared with C. This happens in the following way:
1. A sends a message m encrypted with key K1 to B.
2. C intercepts the encrypted message and decrypts it to obtain the original message.
3. C sends either the same message (m) or a modified message (m') to B, encrypted using the key K2.
B receives the message assuming that it has come from A. A similar thing happens when B sends a message to A. This way, C comes in the middle of the communication between A and B and, therefore, the attack is named so.
8. What is the ElGamal encryption system? Explain its encryption and decryption processes.
Ans.: The ElGamal encryption system is a public-key cryptosystem based on the concept of Diffie-Hellman key agreement. It was discovered by Taher ElGamal in 1984. It is based on the discrete logarithm problem. To understand this problem, consider that p is a large prime number, q is an integer and e1 is a primitive root in the group G = <. Now, it is easy to compute 
, *>e2 = e by using fast exponential algorithms. However, if 
mod pe1, e2 and p are given, then it is difficult to calculate q = log(e1 * e2)mod p. This is what is known as the discrete logarithm problem. Thus, the security of ElGamal depends on the complexity of computing discrete logarithms.
The Elgamel encryption system consists of three different components, and separate algorithms are defined for them. The components are key generator, encryption algorithm and decryption algorithm.
ElGamal key generation
Suppose A and B are the communicating parties, and A wishes to send a message to B using the ElGamal encryption system. For this, A needs to know the public key of B. Thus, B uses the following steps to generate his or her private and public keys.
1. Choose a large prime number p.
2. Choose a random number q in the group G = <, that is, ,*>1 ≤ q < p.
3. Choose a primitive root e1 in the group G = <Zp*,*>.
4. e2: = e. mod p
5. Announce (e1, e2, p) as the public key.
6. Retain q as the private key and keep it secret.
After knowing the public key of B, anyone can now send a message to B using its public key.
ElGamal encryption
Suppose the user A wants to send an encrypted message to B. For this, A uses the B's public key (e1, e2, p) and the following steps to convert the plaintext P to ciphertexts C1 and C2.
1. Choose a random number d in the group G = <.,*>
2. C1: = e.
mod p
3. C2: =(P * e.
) mod p
4. Send C1 and C2.
ElGamal decryption
After receiving the ciphertext (C1 and C2), the recipient B uses its private key q to decrypt the ciphertext and, thus, obtain the original plaintext P, as shown here:
P =[C2(C)-1] mod p
Proof of decryption
We can also verify the ElGamal decryption expression [C2(C to be equivalent to )-1] mod pP. Putting the values of C1 and C2 in the ElGamal decryption expression, we get:
9. Discuss the different attacks on the ElGamal algorithm.
Ans.: Although the ElGamal algorithm can be used for key exchange, encryption, decryption and authentication of small messages, it has certain weaknesses that may help an attacker to crack the security of the algorithm. Generally, the ElGamal cryptosystem is subject to two types of attacks, which are as follows:
Modulus attack: In case the value of modulus p is small, it will be much easier for an attacker to solve the discrete logarithm problem. For example, the attacker can easily solve the discrete logarithm problem q = loge1e2 mod p and obtain the value of q. It can store the value of q and use it to decrypt any message sent to the recipient. The attacker can do so as long as the recipient uses the same keys. The attacker can also easily solve the discrete logarithm problem d = loge1C1 mod p and get the value of random number d used by the sender. Thus, to avoid this attack, it is recommended to use large values, at least of 1024 bits, for modulus p.
Known-plaintext attack: If the sender uses the same value of q to encrypt two different plaintexts, P1 and P2 , the attacker can determine P2 if he or she knows P1 . Let C = P1 * e and 
mod pC' = P2 * e. Now, the attacker can determine q mod pP2 using the following steps:
1. e: = C' * P
mod p
2. P2: = C' * (e)-1 mod p
Thus, to avoid this attack, it is recommended that the sender use a different value of q to encrypt each plaintext.
10. Write a short note on elliptic curves.
Ans.: An elliptic curve can be defined by an equation in two variables with coefficients. The general form of an elliptic curve is given as:
y2 + b1xy +b2y = x3 + a1x2 +a2x +a3
Where x, y are the variables, while a1, a2, a3, b1 and b2 are the coefficients.
There are three kinds of elliptic curves, which are as follows:
Elliptic curves over real numbers: When we talk about elliptic curves over real numbers, we use a special class of elliptic curves, of the form given here:
y2 = x3 + ax + b
Here, the variables x and y take values of real numbers and the coefficients a and b are the real numbers as well.
Elliptic curves over finite field GF(p): In elliptic curves over finite field GF(p), the variables and coefficients are bound to be the elements of the finite field. Here, the elliptic curve is denoted as Ep(a,b), where p is the modulus and all calculations are made using modulo p. The elliptic curve Ep(a,b) over finite field GF(p) is represented as:
y2 mod p =(x3 + ax + b)mod p
Notice that the value of x lies between 0 and p.
Elliptic curves over finite field GF(2n): The elliptic curves over finite field GF(2n), denoted as E2n(a,b), are of the form given here:
y2 + xy = x3 + ax2 + b
Where the variables x and y and the coefficients a and b are the elements of finite field GF(2n), and all calculations are performed in GF(2n).
11. What is the elliptic curve cryptosystem?
Ans.: The elliptic curve cryptosystem (ECC) is a public-key cryptosystem based on the theory of elliptic curves over finite field, and was unveiled by Neal Koblitz and Victor S. Miller in 1985. It involves both groups and logarithmic problems, and provides a higher rate of security at smaller key size, which is not possible using ElGamel and RSA.
In ECC, the plaintext is first encoded in the form of P(x,y) point and then further encrypted or decrypted.
ECC with Diffie-Hellman key exchange
Consider that A and B are two users who wish to communicate and, thus, exchange the secret key using ECC. The exchange of key between A and B proceeds as follows:
1. Choose a large integer p, such that p is either a prime or in the form 2n.
2. Choose the elliptic curve coefficients a and b for the cubic equations of the form y2 mod p = (x3 + ax + b)mod p or y2 + xy = x3 + ax2 + b. This defines Ep(a,b), the elliptic group of points.
3. Choose a base point G =(x1,y1) in Ep(a,b), whose order is a very large value, m.
4. A chooses an integer XA < m, which becomes his or her private key. Then, A calculates his or her public key YA, as shown here:
YA = XA * G
The public key YA is a point in Ep(a,b).
5. B chooses an integer XB < m, which becomes his or her private key. Then, B calculates his or her public key YB, as shown here:
YB = XB * G
The public key YB is a point in Ep(a,b).
6. A calculates the secret key K using his or her private key XA and the public key of B (that is, YB), as shown here:
K = XA * YB
7. Similarly, B calculates the secret key K using his or her private key XB and public key of A (that is, YA), as shown here:
K = XB * YA
Proof of algorithm
To prove that both A and B have generated the same secret key, we need to show that the calculation of K by both users yield the same result.
Hence, proved.
ECC encryption
When A has to send a message (say, Pm) to B, A first chooses a random integer (say, r). Then, A encrypts the message using B's public key YB and the base point G to produce the ciphertext Cm, containing the pair of points as shown here:
Cm = {r * G, Pm + r * YB}
ECC decryption
On receiving the ciphertext Cm, B decrypts the ciphertext to obtain the original plaintext Pm. For this, it multiplies the first point in Cm (that is, r * G) with its private key XB, and then subtracts it from the second point (that is, Pm + r * YB), as shown here:
Security of ECC
A encrypts the message Pm with r * YB (r is only known to A) and r * G; therefore, the attacker needs the value of r, G and r * G to decrypt the message, which is not so easy.
12. Encrypt the plaintext 6 using RSA public key encryption algorithm. Use prime numbers 11 and 3 to compute the public key and private key. Also, decrypt the cipher text using the private key.
Ans.: According to the RSA algorithm explained in Question 2, we have:
We choose D = 3 (a number relatively prime to 20, that is, gcd (20,3)= 1)
As we know, the public key consists of (E,p), and the private key consists of (D,p). Therefore, the public key is (7, 33), and the private key is (3, 33).
The plaintext 6 can be converted into ciphertext using the public key (7, 33), as shown here:
If we apply the private key to the ciphertext 30, we get the original plaintext, as follows:
13. In the Diffie-Hellman key exchange algorithm, let the prime number be 353 and one of its primitive root be 3. Let the users A and B select their secret keys XA = 97 and XB = 233. Compute:
(i) The public keys of A and B
(ii) The common secret key
Ans.: According to the Diffie-Hellman key exchange algorithm explained in Question 5, we have:
(i) Public key of A
Public key of B
(ii) Common secret key
14. A is using the ElGamal encryption system to transmit a message to B, with p = 11, primitive root in G is 2, private key of A is 3 and the plaintext is 7.
(i) Calculate e2 and public key of A
(ii) If B chooses d = 4, then calculate C1, C2
Ans.: According to the ElGamal encryption system explained in Question 8, we have:
(i) As we know, e2 = e mod p
Thus, the public key of A =(e1, e2, p)=(2, 8, 11)
(ii) Given, d = 4
Thus, the ciphertexts are C1 = 5 and C2 = 6.
15. Using elliptic curve encryption/decryption scheme, key exchange between users A and B is accomplished. The cryptosystem parameters are elliptic group of points E11(1, 6) and point G on the elliptic curve is G = (2, 7). B's secret key is XB = 7.
(i) Find out B's public key YB.
(ii) A wishes to encrypt the message Pm = (10, 9) and chooses the random value r = 3. Determine the ciphertext Cm.
(iii) How will B recover Pm from Cm?
Ans.: Given G = (2, 7)
B's private key, XB = 7
(i) B's public key, YB, can be computed as:
(ii) Given, Pm = (10, 9) and r = 3. Thus, the ciphertext Cm can be computed as:
(iii) B can recover Pm from Cm using its private key (XB) as follows:
Multiple-choice Questions
1. In asymmetric-key cryptography, how many keys are required for each communicating party?
(a). 2
(b). 3
(c). 4
(d). 1
2. In asymmetric-key cryptography, the private key must be __________.
(a). Shared with anyone
(b). Distributed
(c). Kept secret
(d). None of these
3. In asymmetric-key cryptography, if A wants to communicate with B, then B must know __________.
(a). A's private key
(b). A's public key
(c). B's private key
(d). B's public key
4. If a sender encrypts the message with his or her private key, it achieves __________.
(a). Confidentiality
(b). Confidentiality and authentication
(c). Confidentiality but not authentication
(d). Authentication
5. To decrypt a message that is encrypted using RSA, we need the __________.
(a). Sender's private key
(b). Sender's public key
(c). Receiver's private key
(d). Receiver's public key
6. Which method provides a higher level of security with a small-sized key?
(a). RSA
(b). ElGamal
(c). Elliptic curve cryptography
(d). Diffie-Hellman key agreement
7. Which of the following is the first secure key exchange algorithm?
(a). RSA
(b). ElGamal
(c). Elliptic curve cryptography
(d). Diffie-Hellman key agreement
Answers
1. (a)
2. (c)
3. (b)
4. (b)
5. (c)
6. (c)
7. (d)