Discrete Mathematics and Probability Theory HW 5

CS 70 Discrete Mathematics and Probability Theory

HW 5
Sundry
Before you start your homework, write down your team. Who else did you work with on this
homework? List names and email addresses. (In case of homework party, you can also just describe
the group.) How did you work on this homework? Working in groups of 3-5 will earn credit for
your "Sundry" grade.
Please copy the following statement and sign next to it:
I certify that all solutions are entirely in my words and that I have not looked at another student’s
solutions. I have credited all external sources in this write up.
1 RSA with Three Primes
Show how you can modify the RSA encryption method to work with three primes instead of two
primes (i.e. N = pqr where p,q,r are all prime), and prove the scheme you come up with works in
the sense that D(E(x)) ≡ x (mod N).
2 Breaking RSA
(a) Eve is not convinced she needs to factor N = pq in order to break RSA. She argues: "All I need
to know is (p−1)(q−1)... then I can find d as the inverse of e mod (p−1)(q−1). This should
be easier than factoring N." Prove Eve wrong, by showing that if she knows (p − 1)(q − 1),
she can easily factor N (thus showing finding (p−1)(q−1) is at least as hard as factoring N).
Assume Eve has a friend Wolfram, who can easily return the roots of polynomials over R (this
is, in fact, easy).
(b) When working with RSA, it is not uncommon to use e = 3 in the public key. Suppose that
Alice has sent Bob, Carol, and Dorothy the same message indicating the time she is having
CS 70, Fall 2017, HW 5 1
her birthday party. Eve, who is not invited, wants to decrypt the message and show up to the
party. Bob, Carol, and Dorothy have public keys (N1, e1),(N2, e2),(N3, e3) respectively, where
e1 = e2 = e3 = 3. Furthermore assume that N1,N2,N3 are all different. Alice has chosen a
number 0 ≤ x < min{N1,N2,N3} which indicates the time her party starts and has encoded
it via the three public keys and sent it to her three friends. Eve has been able to obtain the
three encoded messages. Prove that Eve can figure out x. First solve the problem when two of
N1,N2,N3 have a common factor. Then solve it when no two of them have a common factor.
Again, assume Eve is friends with Wolfram as above.
Hint: The concept behind this problem is the Chinese Remainder Theorem: Suppose n1,...,nk
are positive integers, that are pairwise co-prime. Then, for any given sequence of integers
a1,...,ak
, there exists an integer x solving the following system of simultaneous congruences:
x ≡ a1 (mod n1)
x ≡ a2 (mod n2)
.
.
.
x ≡ ak (mod nk)
Furthermore, all solutions x of the system are congruent modulo the product, N = n1 ···nk
.
Hence: x ≡ y (mod ni) for 1 ≤ i ≤ k ⇐⇒ x ≡ y (mod N).
3 Squared RSA
(a) Prove the identity a
p(p−1) ≡ 1 (mod p
2
), where a is relatively prime to p and p is prime.
(b) Now consider the RSA scheme: the public key is (N = p
2q
2
, 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, i.e. x
ed ≡ x (mod N). You may assume that x is relatively
prime to both p and q.
(c) Continuing the previous part, prove that the scheme is unbreakable, i.e. your scheme is at least
as difficult as ordinary RSA.
4 Badly Chosen Public Key
Your friend would like to send you a message using the RSA public key N = (pq, e). Unfortunately,
your friend did not take CS 70, so your friend mistakenly chose e which is not relatively prime to
(p−1)(q−1). Your friend then sends you a message y = x
e
. In this problem we will investigate
if it is possible to recover the original message x. Throughout this problem, assume that you have
discovered an integer a which has the property that a
(p−1)(q−1) ≡ 1 (mod N), and for any positive
integer k where 1 ≤ k < (p−1)(q−1), a
k 6≡ 1 (mod N).
(a) Show that for any integer z which is relatively prime to N, z can be written as a
k
(mod N) for
some integer 0 ≤ k < (p−1)(q−1). [Hint: Show that 1,a,a
2
,...,a
(p−1)(q−1)−1
are all distinct
modulo N.]
CS 70, Fall 2017, HW 5 2
(b) Show that if k is any integer such that a
k ≡ 1 (mod N), then (p−1)(q−1) | k.
(c) Assume that y is relatively prime to N. By the first part, we can write y ≡ a
`
(mod N) for some
` ∈ {0,...,(p − 1)(q − 1) − 1}. Show that if k is an integer such that (p − 1)(q − 1) | ek − `,
then ˜x := a
k
satisfies ˜x
e ≡ y (mod N).
(d) Unfortunately the solution ˜x found in the previous part might not be the original solution x.
Show that if d := gcd(e,(p−1)(q−1)) 1, then there are exactly d distinct integers x1,..., xd
which are all distinct modulo N such that x
e
i = y, i = 1,...,d. [Hint: You will probably find it
helpful to use a as a tool here.]
5 Properties of GF(p)
(a) Show that, if p(x) and q(x) are polynomials over the reals (or complex, or rationals) and
p(x)· q(x) = 0 for all x, then either p(x) = 0 for all x or q(x) = 0 for all x or both. (Hint: You
may want to prove first this lemma, true in all fields: The roots of p(x)·q(x) is the union of the
roots of p(x) and q(x).)
(b) Show that the claim in part (a) is false for finite fields GF(p).
6 Repeated Roots
Let p(x) = akx
k +···+a0 be a polynomial in the variable x, where k is a positive integer and the
coefficients a0,...,ak are from some field F (here, F can be Q, R, C, or GF(p) for some prime p).
We formally define the polynomial’s derivative to be the polynomial p
0
(x) := kakx
k−1+···+a1 =
∑
k
j=1
jajx
j−1
. [Note: You may be familiar with the derivatives of polynomials from studying
calculus, but we are not using any calculus here, because it does not really make sense to perform
calculus on finite fields! Think of the polynomial’s derivative as a formal definition, i.e., in this
context, it has nothing to do with rate of change, etc. In particular, you should not use any calculus
rules such as the product rule without proof.] We say that α is a repeated root of p if p(x) can be
factored as (x−α)
2q(x) for some polynomial q. Show that α is a repeated root of p if and only if
p(α) = p
0
(α) = 0.
CS 70, Fall 2017, HW 5 3