CMU 15-827 |
Security and Cryptography |
Fall 1998 |
Symmetric and Public Key Cryptography |
||
Wing |
Homework 1 |
14 September 1998 |
You may do this question in a group and hand in a single group solution. List all group members in what you hand in.
We have discussed the use of triple-DES to increase the key search size (under a known plaintext attack) to 2^{112}. 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?
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 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_{1}, …., 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
f_{k} : {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 = m_{1} o … o m_{b}
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_{1}) XOR m_{2}) XOR … m_{b-1}) XOR m_{b})
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^{3 }mod n_{A}, y_{B} = m^{3 }mod n_{B}, y_{C} = m^{3 }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.
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.
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.)
Show how to use elliptic curves to implement ElGamal’s encryption/decryption scheme.
Use Blum integers to solve the remote coin flipping problem.
Back to Lectures
Heather L. Marko
Last Modified: September 1998