CMU 15-827 Security and Cryptography Fall 1998 Symmetric and Public Key Cryptography Wing Homework 1 14 September 1998

1. RSA and DES In Practice
2. You may do this question in a group and hand in a single group solution. List all group members in what you hand in.

1. Generate RSA moduli of 512 bits and 1024 bits; generate public-private key pairs for both moduli.
2. Program or copy routines for RSA and DES encryption for the most interesting hardware platforms to which you have access.
3. Carefully obtain benchmark figures to answer the following questions:
• What is the throughput of the routines?
• What is the set up cost for inserting a new key?
• How many keys can be searched per minute?
• How many megabytes can be encrypted under a single key?
For RSA, find these benchmarks figures for both sizes of moduli.

4. What can you do to speed up the performance of your routines on your chosen hardware platforms? Describe improvements, and when feasible, implement them and remeasure.

3. n-DES key space
4. We have discussed the use of triple-DES to increase the key search size (under a known plaintext attack) to 2112. What is the minimum key search space that you can discover (using "meet in the middle" attacks) if you use quadruple-DES? k-independent invocations of DES?

5. Message Authentication Codes
6. Alice and Bob share a secret key k. Bob wants an assurance that the message he receives are really coming from Alice. In order to obtain this assurance Alice sends the message m and a MAC along with it MACk(m). We say that a MAC is secure against chosen message attack if attacker Eve, after requesting the MAC MACk(mi) of n messages of her choice m1, …., mn will not be able to produce a new message m =/= mi and a valid MACk(m).

Let CBC-MAC be a way of implementing MACs using symmetric encryption. Let

fk : {0, 1}l -> {0,1}l

be an encryption function with key k (e.g., with l = 64, f could be DES). Let m be a message of length bl bits.

m = m1 o … o mb

where o denotes concatenation and mi is a block of length l bits. The MAC of m is computed using the cipher f in CBC mode:

MACk(m) = fk ( fk(… fk( fk m1) XOR m2) XOR … mb-1) XOR mb)

1. Show that the CBC-MAC does not support variable length input. That is, show that if messages have variable length it is possible to devise a chosen message attack.
2. Suppose the length of the messages is always smaller than 2l. An attempt to get around the above problem would be to append the length of the message at the end as an extra block, before computing the MAC. Show that it is still possible to mount an effective chosen message atttack.

7. Protocol Failure Involving RSA
8. Remember that an RSA public-key is a pair (n, e) where n is the product of two primes.

RSA(n, e)(m) = me mod n

Assume that three users in a network, Alice, Bob,and Carol use RSA public-keys (nA, 3), (nB, 3), and (nC, 3), respectively. Suppose David wants to send the same message m to the three of them. So David computes

yA = m3 mod nA, yB = m3 mod nB, yC = m3 mod nC

and sends the ciphertexts to the respective users. Show how an eavesdropper Eve can now compute the message m even without knowing any of the secret keys of Alice, Bob, and Carol.

9. Perfect Forward Secrecy
10. Suppose two parties Alice and Bob want to communicate privately. They both hold public keys in the traditional Diffie-Hellman model. An eavesdropper Eve stores all the encrypted messages between them and one day she manages to break into Alice’s and Bob’s computers and find their secret keys, corresponding to their public keys.

Show using only public-key cryptography that we can achieve perfect forward secrecy, i.e., Eve will not be able to gain any knowledge about the messages Alice and Bob exchanged before the disclosure of the secret keys.

11. Secret Sharing
12. Consider a generic Secret Sharing scheme. A dealer D wants to share a secret s between n trustees so that no t of them have any information about s, but t+1 can reconstruct the secret. Let si be the share of trustee si. Let v denote the number of possible values that s might have, and let w denote the number of different possible share values that a given trustee might receive, as s is varied. (Let’s assume that w is the same for each trustee.)

1. Argue that w > v for any Secret Sharing Scheme. (It then follows that the number of bits needed to represent a share cannot be smaller than the number of bits needed to represent the secret itself.)
2. Dishonest trustees can prevent the reconstruction of the secret by contributing bad shares si =/= si. Using the cryptographic tools you have seen in class, show how to prevent this denial of service attack. There are many possible solutions to this question. State your assumptions clearly and state how strong (computionally secure vs. unconditional secure) your solution is.

13. Elliptic curves and ElGamal
14. Show how to use elliptic curves to implement ElGamal’s encryption/decryption scheme.

15. Blum Integers and Coin Flipping
16. Use Blum integers to solve the remote coin flipping problem.

Back to Lectures

Heather L. Marko