CS 70 Discrete Mathematics and Probability Theory Fall 2021
Due: Saturday 10/02, 4:00 PM Grace period until Saturday 10/02, 5:59 PM
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 Practice
Consider the following RSA schemes and solve for asked variables.
(a) AssumeforanRSAschemewepick2primes p=5andq=11withencryptionkeye=9,
what is the decryption key d? Calculate the exact value.
(b) If the receiver gets 4, what was the original message?
(c) Encode your answer from part (b) to check its correctness.
2 Tweaking RSA
You are trying to send a message to your friend, and as usual, Eve is trying to decipher what the message is. However, you get lazy, so you use N = p, and p is prime. Similar to the original method,foranymessagex∈{0,1,…,N−1},E(x)≡xe (modN),andD(y)≡yd (modN).
(a) Show how you choose e and d in the encryption and decryption function, respectively. 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 now compute d in the decryption function? If so, by what algorithm?
(c) Now you wonder if you can modify the RSA encryption method to work with three primes (N = pqr where p,q,r are all prime). Explain how you can do so, and include a proof of correctness showing that D(E(x)) = x.
CS 70, Fall 2021, HW 5 1
3 RSA with Multiple Keys
Members of a secret society know a secret word. They transmit this secret word x between each other many times, each time encrypting it with the RSA method. Eve, who is listening to all of their communications, notices that in all of the public keys they use, the exponent e is the same. Therefore the public keys used look like (N1,e),…,(Nk,e) where no two Ni’s are the same. Assume that the message is x such that 0 ≤ x < Ni for every i.
(a) Suppose Eve sees the public keys (p1q1,7) and (p1q2,7) as well as the corresponding trans- missions. Can Eve use this knowledge to break the encryption? If so, how? Assume that Eve cannot compute prime factors efficiently. Think of p1,q1,q2 as massive 1024-bit numbers. Assume p1,q1,q2 are all distinct and are valid primes for RSA to be carried out.
(b) The secret society has wised up to Eve and changed their choices of N, in addition to changing their word x. Now, Eve sees keys (p1q1,3), (p2q2,3), and (p3q3,3) along with their trans- missions. Argue why Eve cannot break the encryption in the same way as above. Assume p1,p2,p3,q1,q2,q3 arealldistinctandarevalidprimesforRSAtobecarriedout.
(c) Let’s say the secret x was not changed (e = 3), so they used the same public keys as before, but did not transmit different messages. How can Eve figure out x?
4 How Many Polynomials?
Let P(x) be a polynomial of degree at most 2 over GF(5). As we saw in lecture, we need d + 1 distinct points to determine a unique d-degree polynomial, so knowing the values for say, P(0), P(1), and P(2) would be enough to recover P. (For this problem, we consider two polynomials to be distinct if they return different values for any input.)
(a) Assume that we know P(0) = 1, and P(1) = 2. Now consider P(2). How many values can P(2) have? How many distinct possibilities for P do we have?
(b) Now assume that we only know P(0) = 1. We consider P(1) and P(2). How many different (P(1), P(2)) pairs are there? How many distinct possibilities for P do we have?
(c) Now, let P be a polynomial of degree at most d on GF(p) for some prime p with p > d. Assume we only know P evaluated at k ≤ d + 1 different values. How many different possibilities do we have for P?
(d) Apolynomialwithintegercoefficientsthatcannotbefactoredintopolynomialsoflowerdegree on a finite field, is called an irreducible or prime polynomial.
Show that P(x) = x2 + x + 1 is a prime polynomial on GF(5).
5 Polynomials over Galois Fields
Real numbers, complex numbers, and rational numbers are all examples of fields. A field is a set of numbers on which operations such as addition, multiplication, and inverses behave as they do
CS 70, Fall 2021, HW 5 2
on rational and real numbers. Galois fields are fields with only a finite number of elements, unlike fields such as the real numbers. Galois fields are denoted by GF(p), where p is a prime number and is also the number of elements in the field. Working over a GF(p) can be thought of as working withnumbersin (modp).
(a) In the field GF(p), where p is a prime, how many roots does q(x) = xp −x have? Use this fact to express q(x) in terms of degree one polynomials. Justify your answers.
(b) Prove that in GF(p), where p is a prime, whenever f(x) has degree ≥ p, it is equivalent to some polynomial f ̃(x) with degree < p.
(c) Show that if P and Q are polynomials over the reals (or complex numbers, or rationals) and P(x)Q(x) = 0 for all x, then either P(x) = 0 for all x, Q(x) = 0 for all x, or both.
(d) Show that the claim in part (c) is false for finite fields GF(p), where p is a prime.
6 Lagrange? More like Lamegrange.
In this problem, we walk you through an alternative to Lagrange interpolation.
(a) Let’s say we wanted to interpolate a polynomial through a single point, (x0,y0). What would be the polynomial that we would get? (This is not a trick question.)
(b) Call the polynomial from the previous part f0(x). Now say we wanted to define the polynomial f1(x) that passes through the points (x0,y0) and (x1,y1). If we write f1(x) = f0(x)+a1(x−x0),
what value of a1 causes f1(x) to pass through the desired points?
(c) Now say we want a polynomial f2(x) that passes through (x0,y0), (x1,y1), and (x2,y2). If we
write f2(x) = f1(x) + a2(x − x0)(x − x1), what value of a2 gives us the desired polynomial?
(d) Suppose we have a polynomial fi(x) that passes through the points (x0,y0), ..., (xi,yi) and we want to find a polynomial fi+1(x) that passes through all those points and also (xi+1,yi+1). If we define fi+1(x) = fi(x)+ai+1 ∏ij=0(x−xj), what value must ai+1 take on?
7 Secret Sharing
Suppose the Oral Exam questions are created by 2 TAs and 3 Readers. The answers are all en- crypted, and we know that:
• Both TAs should be able to access the answers
• All 3 Readers can also access the answers
• One TA and one Reader should also be able to do the same
Design a Secret Sharing scheme to make this work.
CS 70, Fall 2021, HW 5 3
8 Trust No One
Gandalf has assembled a fellowship of eight peoples to transport the One Ring to the fires of Mount Doom: four hobbits, two humans, one elf, and one dwarf. The ring has great power that may be of use to the fellowship during their long and dangerous journey. Unfortunately, the use of its immense power will eventually corrupt the user, so it must not be used except in the most dire of circumstances. To safeguard against this possibility, Gandalf wishes to keep the instructions a secret from members of the fellowship. The secret must only be revealed if enough members of the fellowship are present and agree to use it.
Requiring all eight members to agree is certainly a sufficient condition to know the instructions, but it seems excessive. However, we also know that the separate peoples (hobbits, humans, elf, and dwarf) do not completely trust each other so instead we decide to require members from at least two different peoples in order to use the ring. In particular, we will require a unanimous decision by all members of one group in addition to at least one member from a different group. That is, if only the four hobbits want to use the ring, then they alone should not have sufficient information to figure out the instructions. Same goes for the two humans, the elf, and the dwarf.
More explicitly, only four hobbits agreeing to use the ring is not enough to know the instructions. Only two humans agreeing is not enough. Only the elf agreeing is not enough. Only the dwarf agreeing is not enough. However, all four hobbits and a man agreeing is enough. Both humans and a dwarf agreeing is enough. Both the elf and the dwarf agreeing is enough.
Gandalf has hired your services to help him come up with a secret sharing scheme that accom- plishes this task, summarized by the following points:
• There is a party of four hobbits, two humans, an elf, and a dwarf.
• There is a secret message that needs to be known if enough members of the party agree.
• The message must remain unknown to everyone if not enough members of the party agree.
• If only the members of one people agree, the message remains a secret.
• If all the members of one people agree plus at least one additional person, the message can be determined.
CS 70, Fall 2021, HW 5 4