1. RSA and DES In Practice

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 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.

1. 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.

1. n-DES key space

We have discussed the use of triple-DES to increase the key search size (under a known plaintext attack) to 2¹¹². 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?

Triple-DES is normally preferred to double-DES since the latter is vulnerable to a meet-in-the-middle attack. The EFF’s "Deep Crack" custom key-search machine found a 56-bit single-DES key from a single plaintext/ciphertext pair in under 56 hours. What challenges would the makers of "Deep Crack" face if they wanted to modify it to do the meet-in-the-middle attack?

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

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

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.

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

MAC_k(m) = f_k ( f_k(… f_k( f_k (m₁) XOR m₂) XOR … m_b-1) XOR m_b)

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 2^l. 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 attack.

4. Protocol Failure Involving RSA

 

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

 

RSA_{(n, e)}(m) = m^e mod n

 

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

y_A = m³ mod n_A, y_B = m³ mod n_B, y_C = m³ mod n_C

 

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.

 

 

5. Perfect Forward Secrecy

 

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.

 

6. Secret Sharing

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 s_i be the share of trustee s_i. 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 s_i’ =/= s_i. 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.

Suppose we have a group of employees and we want to calculate their average salary without any one employee having to reveal his or her salary to the group. Explain how to use Shamir’s secret sharing scheme to solve this problem. Describe a simpler method that does not use secret sharing.

9. Elliptic curves and ElGamal

 

Show how to use elliptic curves to implement ElGamal’s encryption/decryption scheme.

 

10. Blum Integers and Coin Flipping

Use Blum integers to solve the remote coin flipping problem.