Massachusetts Institute of Technology Handout 126.857: Network and Computer Security October 26, 2004Professor Ronald L. Rivest Due: Novemb e r 2, 2004 (Don’t Forget to Vote!)Problem Set 5Submit this problem set in PostScript, PDF, or MS Word format to [email protected] beforelecture on the due date. We have provided templates for LATEX and Microsoft Word on the course website.Each solution must appear on separate sheets of paper. Mark the top of each sheet with your name(s), thecourse numb er (6.857), the problem set number and question, and the date.You are to work in groups of three or four people and should submit a single set of s olutions for allproblems parts designated [Group]. You should turn in a separate, individual solution to any problemsdesignated [Individual].Problem 5-1. Secret Sharing [Group]A master secret s ∈ Zp, where p is a large prime, was split into 22 shares by selecting a random polynomialP (x) of degree 4, where P (0) = s. This polynomial is evaluated over the field Zp, that is, every operation istaken modulo p. We denote this as P (x) ∈ Zp[x].Once P (x) was selected, 22 shares of s were generated by evaluating P (x) at the points [1, 22] to obtainP (1), . . . , P (22). Since P (x) has degree 4, any 5 different shares c an fully reconstruct the polynomial P . Inother words, s has been split using a (22, 5)-Shamir Secret Sharing s cheme.Each group will receive an individual share P (i). However, this share will be split a second time amongyour t-member group by choosing a random polynomial Q(x) ∈ Zp[x] of degree d = max(1, t − 2), suchthat Q(0) = P (i). Each member will rec eive a share Q(1), . . . , Q(t) via e-mail. As usual, d + 1 shares canreconstruct P (i).Once your group recovers P (i), you’ll need to find four other groups to recover s. To make this problemfun and interesting, it is against the rules for groups to help each other in any way except trading their ownP (i) shares. For example:1.Do not tell another group any of your group’s Q(j) values .2.Do not share your group’s P (i) value unless explicitly asked for it. You are not allowe d to pos t it tothe class mailing list or to a website.3.Do not re-transmit another group’s P (i) values.4.Do not notify another group that they incorrectly calculated their P (i) share.5.Do not tell another group the master s ec ret s or any partial information about s.Exactly one group may have been given an incorrect value for P (i). Be careful! Yours may be this group! Andother groups may have incorrect software. However, groups caught intentionally cheating by giving incorrectvalues will be penalized. You can acquire more than 5 P (i) shares to verify your s value if necessary.Every student should receive their group’s number i, their own own (j, Q(j)) pair, and the global prime p viae-mail. Hint: The value s is a prime number and its decimal representation will contain the string “6857”.Turn in the following:•Your group’s P (i) value.•The (j, P (j)) values of other group shares you used to compute s.•The master secret s.•If you think you received a fake P (i) value, an brief explanation of how you know this is the case.•A sentence or two attesting that your group did not violate the given rules or aid another group incomputing s.2 6.857 : Handout 12: Problem Set 5Problem 5-2. RSA and Semantic Security [Individual]Throughout this problem, you may assume that RSA is computationally hard. That is, assume that noprobabilistic polynomial time algorithm can decrypt an RSA ciphertext without knowledge of the privatekey w ith more than negligible probability.(a) In one sentence, explain why the original RSA is not semantically secure.(b) Implementations of RSA often choose 3, 5, 17, or 65537 as their exponent e. Assume that for eachof these e values, e ∈ Z∗φ(n). In two sentences, explain why these particular values make better RSAexponents than a random elem ent e ∈ Z∗φ(n).(c) For convenience, assume our RSA exp onent e is 3 and that e ∈ Z∗φ(n). A proposal to make RSAsemantically secure is as follows: Let |x| signify the number of bits representing a number x. Ifk = |n|, define the length of a valid message m to be |m| < 3k/4. For each encryption operation,choose k/4 random bits r, append them to m such that m0= (m ◦ r) = m ∗ 2k/4+ r (where ◦ isthe composition operator), and encrypt the value m0. Note that |m0| < |n|, so m0∈ Zn. When wedecrypt a ciphertext, we will simply discard the k/4 least significant bits of the decrypted plaintext.Is this scheme semantically secure? Prove or disprove it either way.(d) Suppose we have a standard RSA public/private keypair. Consider an RSA-variant where we willfirst select a random r ∈ Z∗n. To encrypt a message m ∈ Z∗n, we will compute a ciphertext of the formc = (m ⊕ r, remod n) = (s, t), where ⊕ is the binary XOR operator. To decrypt c, one can simplydecrypt t using RSA and XOR the result with s.Is this scheme semantically secure? Prove or disprove it either way.Problem 5-3. Notorious BIGnum [Group]Professor Bignum is taking a sabbatical to write a book on security, and doesn’t want to be disturbed much.So he devises the following s cheme.He decides that the only folks who should be able to send him email are his mother Alice, his w ife Bobbie,or his daughter Charlene. B ut he wants to require that at least two of them must cooperate to send himemail.He plans to create an RSA public-key instance for himself, with public exponent e, modulus n, and secretkey d. He will register and publish his public key with the certificate authority VeriKey.He next plans to create six values e1, e2, e3, e4, e5, and e6, where e1, e3, and e5will be chosen randomly, ande2, e4, and e6will be found s atisfying the equations:e1e2= e mod φ(n)e3e4= e mod φ(n)e5e6= e mod φ(n)He then will give Alice e1and e3, gives Bobbie e2and e5, and gives Charlene e4and e6. Thus, any two ofthem can encrypt a message for Professor Bignum. For example,me= (me1)e2mod nwhen Alice and Bobbie cooperate. Alice and Charlene use e3and e4, and Bobbie and Charlene use e5ande6. Professor Bignum then starts to write his e mail handler so that it rejects any email that does not appearto be encrypted with RSA using exponent e.Explain as many things as you can that are wrong with Professor Bignum’s plan.6.857 : Handout 12: Problem Set 5 3Problem 5-4. Block Cipher Modes [Group]A message is sent using a block cipher without any authentication
View Full Document
Unlocking...