Description

Sundry
Before you start writing your final homework submission, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.)
1 RSA with Just One Prime
Given the message x ∈ {0,1,…,N −1} and N = pq, where p and q are prime numbers, conventional RSA encrypts x with y = E(x) ≡ xe (mod N). The decryption is done by D(y) ≡ yd (mod N), where d is the inverse of e (mod (p−1)(q−1)).
Alice is trying to send a message to Bob, and as usual, Eve is trying to decipher what the message is. One day, Bob gets lazy and tells Alice that he will now use N = p, where p is a 1024-bit prime number, as part of his public key. He tells Alice that it’s okay, since Eve will have to try out 21024 combinations to guess x. It is very likely that Eve will not find out the secret message in a reasonable amount of time! In this problem, we will see whether Bob is right or wrong. Assume that Eve has found out about this new setup and that she knows the public key.
Similar to the original method, for any message x ∈ {0,1,…,N − 1}, E(x) ≡ xe (mod p), and D(y) ≡ yd (mod p). Choose e such that it is coprime with p−1, and choose d ≡ e−1 (mod p−1).
(a) Prove that the message x is recovered after it goes through your new encryption and decryption functions, E(x) and D(y).
(b) Can Eve compute d in the decryption function? If so, by what algorithm and approximately how many iterations does it take for it to terminate?
(c) Given part (b), how would Eve recover x and what algorithm would she use? Approximately how many iterations does it take to terminate?
(d) Based on the previous parts, can Eve recover the original message in a reasonable amount of time? Explain.
2 Squared RSA
(a) Prove the identity ap(p−1) ≡ 1 (mod p2), where a is coprime to p, and p is prime. (Hint: Try to mimic the proof of Fermat’s Little Theorem from the notes.)
(b) Now consider the RSA scheme: the public key is (N = p2q2,e) for primes p and q, with e relatively prime to p(p− 1)q(q− 1). The private key is d = e−1 (mod p(p− 1)q(q− 1)). Prove that the scheme is correct for x relatively prime to both p and q, i.e. xed ≡ x (mod N).
(Hint: Try to mimic the proof of RSA correctness from the notes.)
3 The CRT and Lagrange Interpolation
Let n1,…nk be pairwise co-prime, i.e. ni and nj are co-prime for all i6= j. The Chinese Remainder Theorem (CRT) tells us that there exist solutions to the following system of congruences:
x ≡ a1 (mod n1) (1)
x ≡ a2 (mod n2) (2)
… .
(..)
x ≡ ak (mod nk) (k)
and all solutions are equivalent (mod n1n2 ···nk). For this problem, parts (a)-(c) will walk us through a proof of the Chinese Remainder Theorem. We will then use the CRT to revisit Lagrange interpolation.
(a) We start by proving the k = 2 case: Prove that we can always find an integer x1 that solves (1) and (2) with a1 = 1,a2 = 0. Similarly, prove that we can always find an integer x2 that solves (1) and (2) with a1 = 0,a2 = 1.
(b) Use part (a) to prove that we can always find at least one solution to (1) and (2) for any a1,a2. Furthermore, prove that all possible solutions are equivalent (mod n1n2).
(c) Now we can tackle the case of arbitrary k: Use part (b) to prove that there exists a solution x to (1)-(k) and that this solution is unique (mod n1n2 ···nk).
For polynomials p1(x), p2(x) and q(x) we say that p1(x) ≡ p2(x) mod q(x) if p1(x)− p2(x) is of the form q(x)×m(x) for some polynomial m(x).
(d) Define the polynomials x−a and x−b to be co-prime if they have no common divisor of degree 1. Assuming that the CRT still holds when replacing x,ai and ni with polynomials (using the definition of co-prime polynomials just given), show that the system of congruences
p(x) ≡ y1 (mod (x−x1)) (1’) p(x) ≡ y2 (mod (x−x2)) (2’)
… (…)
p(x) ≡ yk (mod (x−xk)) (k’)
has a unique solution (mod (x−x1)···(x−xk)) whenever the xi are pairwise distinct. What is the connection to Lagrange interpolation?
4 Polynomials in Fields
Define the sequence of polynomials by P0(x)= x+12, P1(x)= x2 −5x+5 and Pn(x)= xPn−2(x)−
Pn−1(x).
(For instance, P2(x)= 17x−5 and P3(x)= x3 −5×2 −12x+5.)
(a) Show that Pn(7) ≡ 0 (mod 19) for every n ∈ N.
(b) Show that, for every prime q, if P2017(x) 6≡ 0 (mod q), then P2017(x) has at most 2017 roots modulo q.
5 Secrets in the United Nations
A vault in the United Nations can be opened with a secret combination s∈Z. In only two situations should this vault be opened: (i) all 193 member countries must agree, or (ii) at least 55 countries, plus the U.N. Secretary-General, must agree.
(a) Propose a scheme that gives private information to the Secretary-General and all 193 member countries so that the secret combination s can only be recovered under either one of the two specified conditions.
(b) The General Assembly of the UN decides to add an extra level of security: each of the 193 member countries has a delegation of 12 representatives, all of whom must agree in order for that country to help open the vault. Propose a scheme that adds this new feature. The scheme should give private information to the Secretary-General and to each representative of each country.
6 Secret Sharing with Spies
An officer stored an important letter in her safe. In case she is killed in battle, she decides to share the password (which is a number) with her troops. However, everyone knows that there are 3 spies among the troops, but no one knows who they are except for the three spies themselves. The 3 spies can coordinate with each other and they will either lie and make people not able to open the safe, or will open the safe themselves if they can. Therefore, the officer would like a scheme to share the password that satisfies the following conditions:
• When M of them get together, they are guaranteed to be able to open the safe even if they have spies among them.
• The 3 spies must not be able to open the safe all by themselves.
Please help the officer to design a scheme to share her password. What is the scheme? What is the smallest M? Show your work and argue why your scheme works and any smaller M couldn’t work. (The troops only have one chance to open the safe; if they fail the safe will self-destruct.)