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 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 be a semantically secure public-key encryption
system. Can algorithm 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 be a chosen ciphertext secure public-key encryption
system with message space . Which of the following is
also chosen ciphertext secure?
Your Answer | Score | Explanation | |
---|---|---|---|
where and . | Correct | 0.25 | This construction is not chosen-ciphertext secure. An attacker can output two messages and and be given back a challenge ciphertext . The attacker would then ask for the decryption of and be given in response or thereby letting the attacker win the game. Note that the decryption query is valid since it is different from the challenger ciphertext . |
where and . | Correct | 0.25 | This construction is not chosen-ciphertext secure. An attacker can output two messages and and be given back a challenge ciphertext . He would then, on his own, create a new random encryption of , call it , and ask for the decryption of , which is a valid decryption query since it is different from the challenge ciphertext with high probability. The response is either or depending on the contents of the challenge ciphertext and this lets the attacker win the game. |
where and | Correct | 0.25 | This construction is chosen-ciphertext secure. An attack on gives an attack on . |
where and . | Correct | 0.25 | This construction is chosen-ciphertext secure. An attack on gives an attack on . |
Total | 1.00 / 1.00 |
Question 4
Recall that an RSA public key consists of an RSA modulus
and an exponent . One might be tempted to use the same
RSA modulus in different public keys. For example, Alice might
use as her public key while Bob may use as his
public key. Alice's secret key is
and Bob's secret key is .
In this question and the next we will show that it is insecure for Alice and Bob to use the same modulus . In particular, we show that either user can use their secret key to factor . Alice can use the factorization to compute and then compute Bob's secret key.
As a first step, show that Alice can use her public key and private key to construct an integer multiple of . Which of the following is an integer multiple of ?
In this question and the next we will show that it is insecure for Alice and Bob to use the same modulus . In particular, we show that either user can use their secret key to factor . Alice can use the factorization to compute and then compute Bob's secret key.
As a first step, show that Alice can use her public key and private key to construct an integer multiple of . Which of the following is an integer multiple of ?
Your Answer | Score | Explanation | |
---|---|---|---|
Correct | 1.00 | Since we know that and therefore is divisibly by . | |
Total | 1.00 / 1.00 |
Question 5
Now that Alice has a multiple of let's see how she can
factor . Let be the given muliple of .
Then for any in we have
in . Alice chooses a random
in and computes the sequence
in
and stops as soon as she reaches the first element such that (if she gets stuck because the exponent becomes odd, she picks a new random and tries again). It can be shown that with probability this satisfies
How can Alice use this to factor ?
in
and stops as soon as she reaches the first element such that (if she gets stuck because the exponent becomes odd, she picks a new random and tries again). It can be shown that with probability this satisfies
How can Alice use this to factor ?
Your Answer | Score | Explanation | |
---|---|---|---|
compute | Inorrect | 0.00 | This will mostly like return which doesn't help Alice factor . |
compute | |||
compute | |||
compute | |||
Total | 0.00 / 1.00 |
Question 6
In standard RSA the modulus is a product of two distinct primes.
Suppose we choose the modulus so that it is a product of three distinct primes,
namely . Given an exponent relatively prime
to we can derive the secret key
as . The public key and
secret key work as before. What is when
is a product of three distinct primes?
Your Answer | Score | Explanation | |
---|---|---|---|
Correct | 1.00 | When is a product of distinct primes then satisfies . | |
Total | 1.00 / 1.00 |
Question 7
An administrator comes up with the following key management scheme:
he generates an RSA modulus and an element
in . He then gives user number the secret
key in where is the '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 and with the key in . It is easy to see that each of the three users can compute . For example, user computes as . The administrator hopes that other than users and , no other user can compute and access the file.
Unfortunately, this system is terribly insecure. Any two colluding users can combine their secret keys to recover the master secret and then access all files on the system. Let's see how. Suppose users 1 and 2 collude. Because and are distinct primes there are integers and such that . Now, users 1 and 2 can compute from the secret keys and as follows:
Now, the administrator encrypts a file that is accssible to users and with the key in . It is easy to see that each of the three users can compute . For example, user computes as . The administrator hopes that other than users and , no other user can compute and access the file.
Unfortunately, this system is terribly insecure. Any two colluding users can combine their secret keys to recover the master secret and then access all files on the system. Let's see how. Suppose users 1 and 2 collude. Because and are distinct primes there are integers and such that . Now, users 1 and 2 can compute from the secret keys and as follows:
Your Answer | Score | Explanation | |
---|---|---|---|
in . | |||
in . | |||
in . | |||
in . | Correct | 1.00 | in . |
Total | 1.00 / 1.00 |
Question 8
Let be a finite cyclic group of order and consider
the following variant of ElGamal encryption in :
- Gen: choose a random generator in and a random in . Output and .
- : choose a random in and output .
- : output .
Your Answer | Score | Explanation | |
---|---|---|---|
is an encryption of of . | |||
is an encryption of of . | |||
is an encryption of of . | |||
is an encryption of of . | Correct | 1.00 | Indeed, , which is a valid encryption of . |
Total | 1.00 / 1.00 |
Question 9
Let be a finite cyclic group of order and let and be an ElGamal public/secret
key pair in 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 in such
that . One party is given and the other party
is given . Now, to decrypt an ElGamal ciphertext
we send 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 , party 2 returns and the results are combined by computing . | |||
party 1 returns , party 2 returns and the results are combined by computing . | |||
party 1 returns , party 2 returns and the results are combined by computing . | |||
party 1 returns , party 2 returns and the results are combined by computing . | Correct | 1.00 | Indeed, 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 and Bob is currently in
state . 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:
Note that Bob learns nothing from this protocol because he simply recieved a plain ElGamal encryption of under the public key . One can show that if then Alice learns nothing else from this protocol because she recieves the encryption of a random value.
They agree on the following scheme:
- They fix a group of prime order and generator of
- Alice chooses random and in and sends to Bob
- Bob choose random and in and sends back to Alice
Note that Bob learns nothing from this protocol because he simply recieved a plain ElGamal encryption of under the public key . One can show that if then Alice learns nothing else from this protocol because she recieves the encryption of a random value.
Your Answer | Score | Explanation | |
---|---|---|---|
Alice tests if by checking if . | |||
Alice tests if by checking if . | |||
Alice tests if by checking if . | |||
Alice tests if by checking if . | Correct | 1.00 | The pair from Bob satisfies and . Therefore, it is a
plain ElGamal encryption of the plaintext under the
public key . This plaintext happens to be 1 when .
The term computes the ElGamal plaintext and compares it to 1.
Note that when the term ensures that Alice learns nothing about other than the fact that . Indeed, when then is a uniform non-zero element of . |
Total | 1.00 / 1.00 |
Question 11
[OPTIONAL: EXTRA CREDIT] What is the bound on for Wiener's attack when is a product
of three equal size distinct primes?
Your Answer | Score | Explanation | |
---|---|---|---|
for some constant . | |||
for some constant . | |||
for some constant . | |||
for some constant . | Correct | 1.00 | The only change to the analysis is that is now on the order of . Everything else stays the same. Plugging in this bound gives the answer. Note that the bound is weaker in this case compared to when is a product of two primes making the attack less effective. |
Total | 1.00 / 1.00 |