CS 4288/5288 Assignment #3

1. (RSA) Suppose Alice’s public key (e,N)=(7,pq) where p=103, q=313.
a. Alice’s private key is (p,q,d). Compute d. 13639
b. If you want to encrypt a message M=112 and send to Alice, what is the ciphertext? 14275
c. If Alice wants to sign a message M such that R(M)=353. Suppose R(x)=2R+3. What is the RSA signature? 24117
d. Suppose you receive an RSA signature s=11455 for message M’ from Alice. Recover M’. 198

2. (Rabin)
a. Suppose p=239, q=547, Plaintext=55. If we pad 4 bits, what is the ciphertext? 2371
b. Suppose ciphertext=23432. What is the plaintext (suppose we pad 5 bits)? 3621

3. (ElGamal) We use Z1307* with generator g=2. Suppose Alice’s private key=43
a. Bob wants to send an encrypted message to Alice. Suppose plaintext=913, and the random number for encryption is 41. What is the ciphertext?
(688, 927)
b. Alice receives ciphertext (A,B)=(62,164), what’s the plaintext?
1139
c. Alice wants to sign a message m with h(m)=235. Alice chooses random number k=37. What is the digital signature? (43, 980)
d. Suppose you receive a message m’ tagged with Alice’s signature (R’,S’)= (613,758). If we already calculated h(m’)=323, verify this signature.
v1 = 197, v2 = 466
they are not equal, so invalid

4. (DSA) Let p=2339, q=167. Select generator g=17 for Zp*. Alice’s private key a=37.
a. Suppose she wants to sign a message m with h(m)=789. She chooses the random integer k=49. What’s the signature?
α=17^14 = 1431 mod 2339.
y=1431^37 = 1132 mod 2339. r=(1431^49 mod p) mod q = 127.
Apply Euclid’s algorithm, we can find k^-1=75 mod q.
The signature is (r, s) = (127,112).
b. Verify the signature (75, 99).
r = 127, v = 116
they are not equal, so invalid