9.1 What are the principal elements of a public-key cryptosystem?
Get 9.1 exercise solution
9.2 What are the roles of the public and private key?
Get 9.2 exercise solution
9.3 What are three broad categories of applications of public-key cryptosystems?
Get 9.3 exercise solution
9.4 What requirements must a public-key cryptosystems fulfill to be a secure algorithm?
Get 9.4 exercise solution
9.5 What is a one-way function?
Get 9.5 exercise solution
9.6 What is a trap-door one-way function? 9.7 Describe in general terms an efficient procedure for picking a prime number.
Get 9.6 exercise solution
Problems
9.1 Prior to the discovery of any specific public-key schemes, such as RSA, an existence proof was developed whose purpose was to demonstrate that public-key encryption is possible in theory. Consider the functions f1(x1) = z1; f2(x2, y2) = z2; f3(x3, y3) = z3, where all values are integers with 1 … xi, yi, zi … N. Function f1 can be represented by a vector M1 of length N, in which the kth entry is the value of f1(k). Similarly, f2 and f3 can be represented by N * N matrices M2 and M3. The intent is to represent the encryption/decryption process by table lookups for tables with very large values of N. Such tables would be impractically huge but could be constructed in principle. The scheme works as follows: Construct M1 with a random permutation of all integers between 1 and N; that is, each integer appears exactly once in M1. Construct M2 so that each row contains a random permutation of the first N integers. Finally, fill in M3 to satisfy the following condition: f3(f2(f1(k), p), k) = p for all k, p with 1 … k, p … N To summarize, 1. M1 takes an input k and produces an output x. 2. M2 takes inputs x and p giving output z. 3. M3 takes inputs z and k and produces p. The three tables, once constructed, are made public.
a. It should be clear that it is possible to construct M3 to satisfy the preceding condition. As an example, fill in M3 for the following simple case: Convention: The ith element of M1 corresponds to k = i. The ith row of M2 corresponds to x = i; the jth column of M2 corresponds to p = j. The ith row of M3 corresponds to z = i; the jth column of M3 corresponds to k = j.
b. Describe the use of this set of tables to perform encryption and decryption between two users.
c. Argue that this is a secure scheme.
Get 9.1 exercise solution
9.2 Perform encryption and decryption using the RSA algorithm, as in Figure 9.5, for the following:
a. p = 3; q = 11, e = 7; M = 5
b. p = 5; q = 11, e = 3; M = 9
c. p = 7; q = 11, e = 17; M = 8
d. p = 11; q = 13, e = 11; M = 7
e. p = 17; q = 31, e = 7; M = 2 Hint: Decryption is not as hard as you think; use some finesse.
Get 9.2 exercise solution
9.3 In a public-key system using RSA, you intercept the ciphertext C = 10 sent to a user whose public key is e = 5, n = 35. What is the plaintext M?
Get 9.3 exercise solution
9.4 In an RSA system, the public key of a given user is e = 31, n = 3599. What is the private key of this user? Hint: First use trial-and-error to determine p and q; then use the extended Euclidean algorithm to find the multiplicative inverse of 31 modulo f(n).
Get 9.4 exercise solution
9.5 In using the RSA algorithm, if a small number of repeated encodings give back the plaintext, what is the likely cause?
Get 9.5 exercise solution
9.6 Suppose we have a set of blocks encoded with the RSA algorithm and we don’t have the private key. Assume n = pq, e is the public key. Suppose also someone tells us they know one of the plaintext blocks has a common factor with n. Does this help us in any way?
Get 9.6 exercise solution
9.7 In the RSA public-key encryption scheme, each user has a public key, e, and a private key,
d. Suppose Bob leaks his private key. Rather than generating a new modulus, he decides to generate a new public and a new private key. Is this safe?
Get 9.7 exercise solution
9.8 Suppose Bob uses the RSA cryptosystem with a very large modulus n for which the factorization cannot be found in a reasonable amount of time. Suppose Alice sends a message to Bob by representing each alphabetic character as an integer between 0 and 25 (AS 0, c, Z S 25) and then encrypting each number separately using RSA with large e and large n. Is this method secure? If not, describe the most efficient attack against this encryption method.
Get 9.8 exercise solution
9.9 Using a spreadsheet (such as Excel) or a calculator, perform the operations described below. Document results of all intermediate modular multiplications. Determine a number of modular multiplications per each major transformation (such as encryption, decryption, primality testing, etc.).
a. Test all odd numbers in the range from 233 to 241 for primality using the MillerRabin test with base 2.
b. Encrypt the message block M = 2 using RSA with the following parameters: e = 23 and n = 233 * 241.
c. Compute a private key (d, p, q) corresponding to the given above public key (e, n).
d. Perform the decryption of the obtained ciphertext 1. without using the Chinese Remainder Theorem, and 2. using the Chinese Remainder Theorem.
Get 9.9 exercise solution
9.10 Assume that you generate an authenticated and encrypted message by first applying the RSA transformation determined by your private key, and then enciphering the message using recipient’s public key (note that you do NOT use hash function before the first transformation). Will this scheme work correctly [i.e., give the possibility to reconstruct the original message at the recipient’s side, for all possible relations between the sender’s modulus nS and the recipient’s modulus nR (nS 7 nR, nS 6 nR, nS = nR)]? Explain your answer. In case your answer is “no,” how would you correct this scheme?
Get 9.10 exercise solution
9.11 “I want to tell you, Holmes,” Dr. Watson’s voice was enthusiastic, “that your recent activities in network security have increased my interest in cryptography. And just yesterday I found a way to make one-time pad encryption practical.” “Oh, really?” Holmes’ face lost its sleepy look. “Yes, Holmes. The idea is quite simple. For a given one-way function F, I generate a long pseudorandom sequence of elements by applying F to some standard sequence of arguments. The cryptanalyst is assumed to know F and the general nature of the sequence, which may be as simple as S, S + 1, S + 2, … , but not secret S. And due to the one-way nature of F, no one is able to extract S given F(S + i) for some i, thus even if he somehow obtains a certain segment of the sequence, he will not be able to determine the rest.” “I am afraid, Watson, that your proposal isn’t without flaws and at least it needs some additional conditions to be satisfied by F. Let’s consider, for instance, the RSA encryption function, that is F(M) = MK mod N, K is secret. This function is believed to be one-way, but I wouldn’t recommend its use, for example, on the sequence M = 2, 3, 4, 5, 6, …” “But why, Holmes?” Dr. Watson apparently didn’t understand. “Why do you think that the resulting sequence 2K mod N, 3K mod N, 4K mod N, … is not appropriate for one-time pad encryption if K is kept secret?” “Because it is—at least partially—predictable, dear Watson, even if K is kept secret. You have said that the cryptanalyst is assumed to know F and the general nature of the sequence. Now let’s assume that he will obtain somehow a short segment of the output sequence. In crypto circles, this assumption is generally considered to be a viable one. And for this output sequence, knowledge of just the first two elements will allow him to predict quite a lot of the next elements of the sequence, even if not all of them, thus this sequence can’t be considered to be cryptographically strong. And with the knowledge of a longer segment he could predict even more of the next elements of the sequence. Look, knowing the general nature of the sequence and its first two elements 2K mod N and 3K mod N, you can easily compute its following elements.” Show how this can be done.
Get 9.11 exercise solution
9.12 Show how RSA can be represented by matrices M1, M2, and M3 of Problem 9.1.
Get 9.12 exercise solution
9.13 Consider the following scheme:
1. Pick an odd number, E.
2. Pick two prime numbers, P and Q, where (P - 1)(Q - 1) -1 is evenly divisible by E.
3. Multiply P and Q to get N. Is this scheme equivalent to RSA? Show why or why not.
Get 9.13 exercise solution
9.14 Consider the following scheme by which B encrypts a message for A. 1. A chooses two large primes P and Q that are also relatively prime to (P - 1) and (Q - 1). 2. A publishes N = PQ as its public key. 3. A calculates P′and Q′ such that PP′ K 1 (mod Q - 1) and QQ′ K 1 (mod P - 1). 4. B encrypts message M as C = MN mod N. 5. A finds M by solving M K CP′ (mod Q) and M K CQ′(mod P).
a. Explain how this scheme works.
b. How does it differ from RSA?
c. Is there any particular advantage to RSA compared to this scheme?
d. Show how this scheme can be represented by matrices M1, M2, and M3 of Problem 9.1.
Get 9.14 exercise solution
9.15 “This is a very interesting case, Watson,” Holmes said. “The young man loves a girl, and she loves him too. However, her father is a strange fellow who insists that his would-be son-in-law must design a simple and secure protocol for an appropriate public-key cryptosystem he could use in his company’s computer network. The young man came up with the following protocol for communication between two parties. For example, user A wishing to send message M to user B: (messages exchanged are in the format sender’s name, text, receiver’s name)” 1. A sends B the following block: (A, E(PUb, [M, A]), B). 2. B acknowledges receipt by sending to A the following block: (B, E(PUa, [M, B]), A). “You can see that the protocol is really simple. But the girl’s father claims that the young man has not satisfied his call for a simple protocol, because the proposal contains a certain redundancy and can be further simplified to the following:” 1. A sends B the block: (A, E(PUb, M), B). 2. B acknowledges receipt by sending to A the block: (B, E(PUa, M), A). “On the basis of that, the girl’s father refuses to allow his daughter to marry the young man, thus making them both unhappy. The young man was just here to ask me for help.” “Hmm, I don’t see how you can help him.” Watson was visibly unhappy with the idea that the sympathetic young man has to lose his love. “Well, I think I could help. You know, Watson, redundancy is sometimes good to ensure the security of protocol. Thus, the simplification the girl’s father has proposed could make the new protocol vulnerable to an attack the original protocol was able to resist,” mused Holmes. “Yes, it is so, Watson. Look, all an adversary needs is to be one of the users of the network and to be able to intercept messages exchanged between A and B. Being a user of the network, he has his own public encryption key and is able to send his own messages to A or to B and to receive theirs. With the help of the simplified protocol, he could then obtain message M user A has previously sent to B using the following procedure:” Complete the description.
Get 9.15 exercise solution
9.16 Use the fast exponentiation algorithm of Figure 9.8 to determine 5596 mod 1234. Show the steps involved in the computation.
Get 9.16 exercise solution
9.17 Here is another realization of the fast exponentiation algorithm. Demonstrate that it is equivalent to the one in Figure 9.8.
Get 9.17 exercise solution
9.18 The problem illustrates a simple application of the chosen ciphertext attack. Bob intercepts a ciphertext C intended for Alice and encrypted with Alice’s public key
e. Bob wants to obtain the original message M = Cd mod n. Bob chooses a random value r less than n and computes
Next, Bob gets Alice to authenticate (sign) X with her private key (as in Figure 9.3), thereby decrypting X. Alice returns Y = Xd mod n. Show how Bob can use the information now available to him to determine M.
Get 9.18 exercise solution
9.19 Show the OAEP decoding operation used for decryption that corresponds to the encoding operation of Figure 9.10.
Get 9.19 exercise solution
9.20 Improve on algorithm P1 in Appendix 9A.
a. Develop an algorithm that requires 2n multiplications and n + 1 additions. Hint: xi+1 = xi * x.
b. Develop an algorithm that requires only n + 1 multiplications and n + 1 additions. Hint: P(x) = a0 + x * q(x), where q(x) is a polynomial of degree (n - 1). Note: The remaining problems concern the knapsack public-key algorithm described in Appendix J.
Get 9.20 exercise solution
9.21 What items are in the knapsack in Figure F.1?
Get 9.21 exercise solution
9.22 Perform encryption and decryption using the knapsack algorithm for the following:
a. a′ = (1, 3, 5, 10); w = 7; m = 20; x = 1101
b. a′ = (1, 3, 5, 11, 23, 46, 136, 263); w = 203; m = 491; x = 11101000
c. a′ = (2, 3, 6, 12, 25); w = 46; m = 53; x = 11101
d. a′ = (15, 92, 108, 279, 563, 1172, 2243, 4468); w = 2393; m = 9291; x = 10110001
Get 9.22 exercise solution
9.23 Why is it a requirement that m
Get 9.23 exercise solution
