1. How do digital signatures schemes, MACs and hash functions compare to each other? Give
an example of a real-world application for each primitive.
2. Show that if you can solve the computational Diffie-Hellman problem (CDH) then you can
solve the decisional Diffie-Hellman problem (DDH). Be sure that you define what these
3. Suppose you have an instance of RSA with two m-bit primes, p and q.
(a) What is the expected bitlength of the modulus N = pq?
(b) If you choose a random number in f1; 2; :::Ng, what is the expected bitlength of this
(c) Using schoolbook multiplication (which has cost O(n2) to multiply two n-bit numbers),
what is the cost of computing an RSA encryption with e = 3? What is the expected cost
of decryption when e = 3? Assume you are using an efficient exponentiation algorithm.
Give a brief explanation.
4. Describe the singing and verification algorithms of the RSA-FDH signature scheme (this is
the Full Domain Hash version of the RSA signature scheme).
5. If the hash function used in the RSA-FDH signature scheme is NOT second pre-image
resistant, describe how a forgery can be created. What kind of attack is this? What kind
of forgery is this?
6. Suppose Alice and Bob want to use the Diffie-Hellman key exchange protocol using Z∗ 11 with
generator g = 6. What is the shared secret if Alice chooses the random exponent 5 and Bob
chooses 3? Show how both Alice and Bob compute this shared secret.
7. Consider the ElGamal signature scheme (see last page) with public key h11; 7; 2i. Compute
the signature for the message m = 6 using the ‘randomly’ chosen k = 7. Use the hash
function H(x) = x + 1. You will need to first find the private key x and then k−1.
8. Consider the following method of encrypting a plaintext document.
• Break the text into words separated by whitespace/punctuation.
• Encrypt each word using textbook RSA (with a 2048-bit modulus and public exponent
that was randomly chosen).
• Send the text with each word replaced by its encryption leaving the whitespace and
For example, if the text was “The cat, in the hat!”, then encryption of this text would
be the string
Enc(The) Enc(cat), Enc(in) Enc(the) Enc(hat)!
where Enc(x) is the encryption of X.
Describe three major problems with this encryption scheme. One of your major problems
should illustrate why this does not provide any confidentiality at all.
EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!
E-mail: email@example.com 微信:easydue