Section 9.4. Key Terms, Review Questions, and Problems


[Page 281 (continued)]

9.4. Key Terms, Review Questions, and Problems

Key Terms

chosen ciphertext attack (CCA)

digital signature

key exchange

one-way function

optimal asymmetric encryption padding (OAEP)

private key

public key

public key cryptography

public key cryptosystems

public key encryption

RSA

time complexity

timing attack

trapdoor one-way function

Review Questions

9.1

What are the principal elements of a public-key cryptosystem?

9.2

What are the roles of the public and private key?

9.3

What are three broad categories of applications of public-key cryptosystems?

9.4

What requirements must a public key cryptosystems fulfill to be a secure algorithm?

9.5

What is a one-way function?

9.6

What is a trapdoor one-way function?

9.7

Describe in general terms an efficient procedure for picking a prime number.

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, in which the kth entry is the value of f1(k). Similarly, f2 and f3 can be represented by N x N matrices M2 and M3. The intent is to represent the encryption/decryption process by table look-ups for tables with very large values of N. Such tables would be impractically huge but could, in principle, be constructed. 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:


[Page 282]

f3(f2(f1(k),p),k) = p

for all k, p with 1 In words,

  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.

  1. 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 x = i; to 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.

  2. Describe the use of this set of tables to perform encryption and decryption between two users.

  3. Argue that this is a secure scheme.

9.2

Perform encryption and decryption using the RSA algorithm, as in Figure 9.6, for the following:

  1. p = 3; q = 11, e = 7; M = 5

  2. p = 5; q = 11, e = 3; M = 9

  3. p = 7; q = 11, e = 17; M = 8

  4. p = 11; q = 13, e = 11; M = 7

  5. p = 17; q = 31, e = 7; M = 2. Hint: Decryption is not as hard as you think; use some finesse.

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?

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 trail and error to determine p and q; then use the extended Euclidean algorithm to find the multiplicative inverse of 31 modulo f(n).

9.5

In using the RSA algorithm, if a small number of repeated encodings give back the plaintext, what is the likely cause?

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?

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?

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(A 0,..., Z 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.


[Page 283]
9.9

Using a spreadsheet (such as Excel), or a calculator, perform the described below operations. Document results of all intermediate modular multiplications. Determine a number of modular multiplications per each major transformation (such as encryption, decryption, primality testing, etc.).

  1. Test all odd numbers in the range from 233 to 241 for primality using the Miller-Rabin test with base 2.

  2. Encrypt the message block M = 2 using RSA with the following parameters: e = 23 and n = 233 x 241.

  3. Compute a private key (d, p, q) corresponding to the given above public key (e, n).

  4. Perform the decryption of the obtained ciphertext using two different methods:

    1. without using the Chinese Remainder Theorem,

    2. using the Chinese Remainder Theorem.

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 > nR, nS < nR, nS = nR)]? Explain your answer. In case your answer is "no," how would you correct this scheme?

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 isat least partiallypredictable, 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.

9.12

Show how RSA can be represented by matrices M1, M2, and M3 of Problem 9.1.


[Page 284]
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.

  4. Calculate .

Is this scheme equivalent to RSA? Show why or why not.

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' 1 (mod QQ' 1 (mod

    B encrypts message M as C = MN mod N.

  4. A finds M by solving M Q) and M P).

  1. Explain how this scheme works.

  2. How does it differ from RSA?

  3. Is there any particular advantage to RSA compared to this scheme?

  4. Show how this scheme can be represented by matrices M1, M2, and M3 of Problem 9.1.

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.

9.16

Use the fast exponentiation algorithm of Figure 9.7 to determine 5596 mod 1234. Show the steps involved in the computation.

9.17

Here is another realization of the fast exponentiation algorithm. Demonstrate that it is equivalent to the one in Figure 9.7.


    [Page 285]
  1. f 1; T a; E b

  2. if odd(e) then f d x T

  3. E |E/2|

  4. T T x T

  5. if E > 0 then goto 2

  6. output f

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 want to obtain the original message M = Cd mod n. Bob chooses a random value r less than n and computes

Z

= re mod n

X

= ZC mod n

t

= r1 mod n


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.

9.19

Show the OAEP decoding operation, used for decryption, that corresponds to the encoding operation of Figure 9.9.

9.20

Improve on algorithm P1 in Appendix 9B.

  1. Develop an algorithm that requires 2n multiplications and n + 1 additions. Hint: xi+1 = xi x x.

  2. Develop an algorithm that requires only n + 1 multiplications and n + 1 additions. Hint: P(x) = a0 + x 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 F.

9.21

What items are in the knapsack in Figure F.1?

9.22

Perform encryption and decryption using the knapsack algorithm for the following:

  1. a' = (1, 3, 5, 10); w = 7; m = 20; x = 1101

  2. a' = (1, 3, 5, 11, 23, 46, 136, 263)); w = 203; m = 491; x = 11101000

  3. a' = (2, 3, 6, 12, 25); w = 46; m = 53; x = 11101

  4. a' = (15, 92, 108, 279, 563, 1172, 2243, 4468); w = 2393; m = 9291; x = 10110001

9.23

Why is it a requirement that




Cryptography and Network Security Principles and Practices
Cryptography and Network Security (4th Edition)
ISBN: 0131873164
EAN: 2147483647
Year: 2005
Pages: 209

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net