Tuesday, September 10, 2013

Public Key Encryption from trapdoor permutations (Week - 6) - Cryptography I


Score of 10.00 out of 11.00.

Question 1

Recall that with symmetric ciphers it is possible to encrypt a 32-bit message and obtain a 32-bit ciphertext (e.g. with the one time pad or with a nonce-based system). Can the same be done with a public-key system?
Your Answer
Score Explanation
Yes, when encrypting a short plaintext the output of the public-key encryption algorithm can be truncated to the length of the plaintext.


It is not possible with the ElGamal system, but may be possible with other systems.


It is possible and depends on the specifics of the system.


No, public-key systems with short ciphertexts can never be secure. Correct 1.00 An attacker can use the public key to build a dictionary of all 232 ciphertexts of length 32 bits along with their decryption and use the dictionary to decrypt any captured ciphertext.
Total
1.00 / 1.00

Question 2

Let (Gen,E,D) be a semantically secure public-key encryption system. Can algorithm E be deterministic?
Your Answer
Score Explanation
No, semantically secure public-key encryption must be randomized. Correct 1.00 That's correct since otherwise an attacker can easily break semantic security.
No, but chosen-ciphertext secure encryption can be deterministic.


Yes, some public-key encryption schemes are deterministic.


Yes, RSA encryption is deterministic.


Total
1.00 / 1.00

Question 3

Let (Gen,E,D) be a chosen ciphertext secure public-key encryption system with message space {0,1}128. Which of the following is also chosen ciphertext secure?
Your Answer
Score Explanation
(Gen,E,D) where E(pk,m)=(E(pk, m), E(pk, 0128)) and D(sk, (c1,c2))=D(sk,c1). Correct 0.25 This construction is not chosen-ciphertext secure. An attacker can output two messages m0=0128 and m1=1128 and be given back a challenge ciphertext (c1,c2). The attacker would then ask for the decryption of (c1,E(pk,1128) and be given in response m0 or m1 thereby letting the attacker win the game. Note that the decryption query is valid since it is different from the challenger ciphertext (c1,c2).
(Gen,E,D) where E(pk,m)=(E(pk, m), E(pk, m)) and D(sk, (c1,c2))=D(sk,c1)if D(sk,c1)=D(sk,c2)otherwise. Correct 0.25 This construction is not chosen-ciphertext secure. An attacker can output two messages m0=0128 and m1=1128 and be given back a challenge ciphertext (c1,c2). He would then, on his own, create a new random encryption of m0, call it c3, and ask for the decryption of (c1,c3), which is a valid decryption query since it is different from the challenge ciphertext with high probability. The response is either m0 or depending on the contents of the challenge ciphertext and this lets the attacker win the game.
(Gen,E,D) where E(pk,m)=E(pk, m1128) and D(sk,c)=D(sk,c)1128 Correct 0.25 This construction is chosen-ciphertext secure. An attack on (Gen,E,D) gives an attack on (Gen,E,D).
(Gen,E,D) where E(pk,m)=[cE(pk,m),  output (c,c)] and D(sk, (c1,c2))=D(sk,c1)if c1=c2otherwise. Correct 0.25 This construction is chosen-ciphertext secure. An attack on (Gen,E,D) gives an attack on (Gen,E,D).
Total
1.00 / 1.00

Question 4

Recall that an RSA public key consists of an RSA modulus N and an exponent e. One might be tempted to use the same RSA modulus in different public keys. For example, Alice might use (N,3) as her public key while Bob may use (N,5) as his public key. Alice's secret key is da=31modφ(N) and Bob's secret key is db=51modφ(N).

In this question and the next we will show that it is insecure for Alice and Bob to use the same modulus N. In particular, we show that either user can use their secret key to factor N. Alice can use the factorization to compute φ(N) and then compute Bob's secret key.

As a first step, show that Alice can use her public key (N,3) and private key da to construct an integer multiple of φ(N). Which of the following is an integer multiple of φ(N)?
Your Answer
Score Explanation
da1


5da1


3da


3da1 Correct 1.00 Since da=31modφ(N) we know that 3da=1modφ(N) and therefore 3da1 is divisibly by φ(N).
Total
1.00 / 1.00

Question 5

Now that Alice has a multiple of φ(N) let's see how she can factor N=pq. Let x be the given muliple of φ(N). Then for any g in ZN we have gx=1 in ZN. Alice chooses a random g in ZN and computes the sequence
   gx,gx/2,gx/4,gx/8 in ZN
and stops as soon as she reaches the first element y=gx/2i such that y1 (if she gets stuck because the exponent becomes odd, she picks a new random g and tries again). It can be shown that with probability 1/2 this y satisfies
  y=1modp, andy=1modqory=1modp, andy=1modq
How can Alice use this y to factor N?
Your Answer
Score Explanation
compute gcd(N1, y) Inorrect 0.00 This will mostly like return 1 which doesn't help Alice factor N.
compute gcd(N, 2y1)


compute gcd(N, y+1)


compute gcd(N+1, y)


Total
0.00 / 1.00

Question 6

In standard RSA the modulus N is a product of two distinct primes. Suppose we choose the modulus so that it is a product of three distinct primes, namely N=pqr. Given an exponent e relatively prime to φ(N) we can derive the secret key as d=e1modφ(N). The public key (N,e) and secret key (N,d) work as before. What is φ(N) when N is a product of three distinct primes?
Your Answer
Score Explanation
φ(N)=(p1)(q1)


φ(N)=(p+1)(q+1)(r+1)


φ(N)=(p1)(q1)r


φ(N)=(p1)(q1)(r1) Correct 1.00 When is a product of distinct primes then |ZN| satisfies |ZN|=|Zp||Zq||Zr|=(p1)(q1)(r1).
Total
1.00 / 1.00

Question 7

An administrator comes up with the following key management scheme: he generates an RSA modulus N and an element s in ZN. He then gives user number i the secret key si=sri in ZN where ri is the i'th prime (i.e. 2 is the first prime, 3 is the second, and so on).

Now, the administrator encrypts a file that is accssible to users i,j and t with the key k=srirjrt in ZN. It is easy to see that each of the three users can compute k. For example, user i computes k as k=(si)rjrt. The administrator hopes that other than users i,j and t, no other user can compute k and access the file.

Unfortunately, this system is terribly insecure. Any two colluding users can combine their secret keys to recover the master secret s and then access all files on the system. Let's see how. Suppose users 1 and 2 collude. Because r1 and r2 are distinct primes there are integers a and b such that ar1+br2=1. Now, users 1 and 2 can compute s from the secret keys s1 and s2 as follows:
Your Answer
Score Explanation
s=s1a+s2b in ZN.


s=s1b+s2a in ZN.


s=s1bs2a in ZN.


s=s1as2b in ZN. Correct 1.00 s=s1as2b=sr1asr2b=sr1a+r2b=s in ZN.
Total
1.00 / 1.00

Question 8

Let G be a finite cyclic group of order n and consider the following variant of ElGamal encryption in G:
  • Gen: choose a random generator g in G and a random x in Zn. Output pk=(g,h=gx) and sk=(g,x).
  • E(pk,mG): choose a random r in Zn and output (gr, mhr).
  • D(sk,(c0,c1)): output c1/c0x.
This variant, called plain ElGamal, can be shown to be semantically secure under an appropriate assumption about G. It is however not chosen-ciphertext secure because it is easy to compute on ciphertexts. That is, let (c0,c1) be the output of E(pk,m0) and let (c2,c3) be the output of E(pk,m1). Then just given these two ciphertexts it is easy to construct the encryption of m0m1 as follows:
Your Answer
Score Explanation
(c0/c3, c1/c2) is an encryption of of m0m1.


(c0/c2, c1/c3) is an encryption of of m0m1.


(c0+c2, c1+c3) is an encryption of of m0m1.


(c0c2, c1c3) is an encryption of of m0m1. Correct 1.00 Indeed, (c0c2, c1c3)=(gr0+r1, m0m1hr0+r1), which is a valid encryption of m0m1.
Total
1.00 / 1.00

Question 9

Let G be a finite cyclic group of order n and let pk=(g,h=ga) and sk=(g,a) be an ElGamal public/secret key pair in G as described in Segment 12.1. Suppose we want to distribute the secret key to two parties so that both parties are needed to decrypt. Moreover, during decryption the secret key is never re-constructed in a single location. A simple way to do so it to choose random numbers a1,a2 in Zn such that a1+a2=a. One party is given a1 and the other party is given a2. Now, to decrypt an ElGamal ciphertext (u,c) we send u to both parties. What do the two parties return and how do we use these values to decrypt?
Your Answer
Score Explanation
party 1 returns u1u1/a1, party 2 returns u2u1/a2 and the results are combined by computing vu1+u2.


party 1 returns u1u(a12), party 2 returns u2u(a22) and the results are combined by computing vu1u2.


party 1 returns u1ua1, party 2 returns u2ua2 and the results are combined by computing vu1+u2.


party 1 returns u1ua1, party 2 returns u2ua2 and the results are combined by computing vu1u2. Correct 1.00 Indeed, v=u1u2=ga1+a2=ga as needed for decryption. Note that the secret key was never re-constructed for this distributed decryption to work.
Total
1.00 / 1.00

Question 10

Suppose Alice and Bob live in a country with 50 states. Alice is currently in state a{1,,50} and Bob is currently in state b{1,,50}. They can communicate with one another and Alice wants to test if she is currently in the same state as Bob. If they are in the same state, Alice should learn that fact and otherwise she should learn nothing else about Bob's location. Bob should learn nothing about Alice's location.

They agree on the following scheme:
  • They fix a group G of prime order p and generator g of G
  • Alice chooses random x and y in Zp and sends to Bob (A0,A1,A2)=(gx, gy, gxy+a)
  • Bob choose random r and s in Zp and sends back to Alice (B1,B2)=(A1rgs,  (A2/gb)rA0s)
What should Alice do now to test if they are in the same state (i.e. to test if a=b) ?

Note that Bob learns nothing from this protocol because he simply recieved a plain ElGamal encryption of ga under the public key gx. One can show that if ab then Alice learns nothing else from this protocol because she recieves the encryption of a random value.
Your Answer
Score Explanation
Alice tests if a=b by checking if B1xB2=1.


Alice tests if a=b by checking if B1/B2x=1.


Alice tests if a=b by checking if B2B1x=1.


Alice tests if a=b by checking if B2/B1x=1. Correct 1.00 The pair (B1,B2) from Bob satisfies B1=gyr+s and B2=(gx)yr+sgr(ab). Therefore, it is a plain ElGamal encryption of the plaintext gr(ab) under the public key (g,gx). This plaintext happens to be 1 when a=b. The term B2/B1x computes the ElGamal plaintext and compares it to 1.

Note that when ab the r(ab) term ensures that Alice learns nothing about b other than the fact that ab. Indeed, when ab then r(ab) is a uniform non-zero element of Zp.
Total
1.00 / 1.00

Question 11

[OPTIONAL: EXTRA CREDIT] What is the bound on d for Wiener's attack when N is a product of three equal size distinct primes?
Your Answer
Score Explanation
d<N2/3/c for some constant c.


d<N1/3/c for some constant c.


d<N1/2/c for some constant c.


d<N1/6/c for some constant c. Correct 1.00 The only change to the analysis is that Nφ(N) is now on the order of N2/3. Everything else stays the same. Plugging in this bound gives the answer. Note that the bound is weaker in this case compared to when N is a product of two primes making the attack less effective.
Total
1.00 / 1.00