CSci 4509 Cryptographic Protocols -- Problem set 5.

Due Thursday, May 5th

Unless otherwise specified, assume that Alice and Bob use RSA system with the following parameters. Here e denotes the public (i.e. encryption) exponent, and d denotes the private (i.e. decryption) exponent:

Problem 1: chosen ciphertext attack on RSA

Recall that chosen ciphertext attack on RSA involves obtaining a digital signature on a specially constructed message (Schneier 19.3). Suppose Bob sends Alice a ciphertext (i.e. a message encrypted with Alice's public key) which consists of a single number 99. Construct such a plaintext that by signing it Alice reveals the information sent to her by Bob. Show the following computations:

Problem 2: another chosen ciphertext attack on RSA

Alice knows that it's dangerous to sign just any document sent by a stranger. Therefore she signs only messages that are prime numbers. Show how Mallory can obtain Alice's signature on the message m = 10. Show all your computations and the result.

Problem 3: choosing the same e and d

Note: this problem has been modified on 4/29/05
Note that there is another possibility for e and d for Bob's RSA system: e = d = 19. Describe an attack that would allow Eve (a passive attacker) to determine that e and d are the same. What does the attacker gain by learning that e and d are the same?
Would choosing the same e and d present a problem in a real-life RSA system?

Problem 4: Shamir's three-pass protocol

Would the following work as an implementation of Shamir's three pass protocol?
  1. Alice generates an RSA system (p1, q1, n1, e1, d1) and keeps all the parameters secret,
  2. Bob generates an RSA system (p2, q2, n2, e2, d2) and keeps it secret,
  3. Alice encrypts a message M with using e1 and n1: M1 = M^e1 mod n1, sends M1 to Bob,
  4. Bob encrypts M' using e2 and n2: M2 = M1^e2 mod n2, sends M2 to Alice.
  5. Alice decrypts the result using d1 and n1: M3 = M2^d1 mod n1, sends the result to Bob,
  6. Bob decrypts it using d2 and n2: M4 = M3^d2 mod n2.
Please explain your answer.
Would choosing n1 = n2 make a difference?

Problem 5: Diffie-Hellman

Consider Diffie-Hellman key exchange protocol with p = 7 and g = 5. Alice's random number is x = 4, Bob's random number is y = 6. What is the key generated in this protocol?

Problem 6: EKE

Consider encrypted key exchange protocol (Schneier 22.5). Suppose in step 2 Bob generates a key and an initialization vector IV for a block cipher in OFB mode which produces a stream of bits. In the remaining steps Alice and Bob use this cipher, always starting with the same initialization vector. Can Eve get any information about the key by observing steps 3, 4, and 5 of the protocol? If yes, what is it? If not, why?

Problem 7: Secret broadcasting

Suppose Alice wants to broadcast a message encrypted with a secret key K = 7. Alice shares a secret key with each participant as following: Alice wants the message to be readable to Bob and Dave, but not to Carol. What number does she have to broadcast in addition to the message to accomplish this?

Problem 8: Secret splitting

Suppose you want to split a secret between Alice, Bob, and Carol in such a way that only all three of them together can restore it (see Schneier 3.6). Describe the process that accomplishes this. Show how the secret can be restored.

Problem 9: Secret sharing

Using LaGrange interpolating polynomial scheme (Schneier 23.2), show how you can set up a scheme in which Alice, Bob, Carol, and Dave can restore a secret as follows: Write down the formula for a polynomial that you need to generate, give a list of points at which you compute the polynomial, and indicate how many shadows each of the participants gets.

Problem 10: Bit commitment

Suppose Alice wants to use a bit commitment protocol which uses symmetric cryptography (see Schneier 4.9, p. 86). Suppose Alice uses a one-time pad to encrypt Bob's string and the bit she is committing to. Does it give any of the participants an ability to cheat? Please explain your answer in detail.

Problem 11: Bit commitment using pseudo-random sequences

Suppose Bob's string in this algorithm is just 2 bits long. How easy would it be for Alice to cheat? Would it be easy for Bob to cheat? Please explain your answer.

Problem 12: Zero-knowledge proofs

Is it possible to use the graph isomorphism problem (instead of the Hamiltonian cycle problem) for a non-interactive zero-knowledge proof? If yes, how? If not, why? Give a detailed answer.

That's all!!
CSci 4509 homepage