Massachusetts Institute of Technology Handout 116.857: Network and Computer Security October 2, 2003Professor Ronald L. RivestProblem Set 4This problem set is due on paper, in room 6-120 on Thursday, October 16 at the beginning of class. Note:You have two weeks to complete this problem set!You are to work on this problem set in groups of three or four people. Problems turned in by individuals,pairs, pentuples, etc. will not be accepted. Be sure that all group members can explain the solutions. SeeHandout 1 (Course Information) for our policy on collaboration. If you do not have a group, seek partnersby emailing [email protected] must be typed! Each problem answer must appear on separate sheets of paper. Mark the topof each sheet with your names (alphabetically by last name), the course number (6.857), the problem setnumber and question, and the date. Homework must be typed and clear. We have provided templatesfor LATEX and Microsoft Word on the course website.Grading and Late Policy: Each problem is worth 10 points, except where noted. Late homeworkwill not be accepted without prior approval. Homework should not be submitted by email except with priorapproval. (Somebody from your group should be in class on the day that the homework is due.)With the authors’ permission, we will distribute our favorite solution to each problem as the “official”solution – this is your chance to become famous! If you do not wish for your homework to be used as anofficial solution, or if you wish that it only be used anonymously, please note this on your homework.Problem 4-1. Paillier Encryption [20 points]In this problem, we introduce the Paillier cryptosystem, which shares some of the flavors of both RSA anddiscrete log-based systems, but also enjoys many other desirable properties (and whose security relies uponnew assumptions).For a summary of the relevant mathematics and the definition of the Paillier scheme, read Sections 2.1through 2.3 (especially Figure 1) on pages 4–5 of “Efficient Public-Key Cryptosystems Provably SecureAgainst Active Adversaries,” by Paillier and Pointcheval (the paper is posted on the 6.857 website). In thisproblem, we will only be dealing with the so-called “Main Scheme.”(a) Implement key generation, encryption, and decryption algorithms for the Paillier scheme in yourfavorite programming language. You may use any big-integer libraries you like. Include your code inyour write-up, and make it clean and readable!(b) When you are confident in the correctness of your code, generate a public/private key pair n, g, p, q(where n is about 256 bits long), and the encryptions of m = 2 and m = 314159 under your key.Go to http://theory.lcs.mit.edu/classes/6.857/ps4.php and supply these values (in decimal)along with the PIN the TAs emailed you. The page will reply with a secret number, encrypted underthe public key you supplied. Decrypt the ciphertext, and report the secret number in your write-up.You may try this process as many times as you wish; your final attempt will be the one we grade.(c) The Paillier cryptosystem has a nice homomorphic property: En,g(m1) · En,g(m2) mod n2is an en-cryption of (m1+ m2) mod n. This inspires Ben Bitdiddle to propose the following voting scheme: aPaillier keypair is generated by the election agency, and the public key (n, g) is disseminated to thepopulace. To vote in favor of a resolution, a voter encrypts a 1; to vote against the resolution, heencrypts a 0. The ciphertext is then submitted to a device which keeps a running product mod n2of all the ciphertexts. At the end, the election agency decrypts this cumulative product: if the valueof the plaintext exceeds half the number of votes, the resolution passes, otherwise it fails. Ben claimsthat this scheme protects the voter’s anonymity while ensuring correctness. Find one major securityflaw in his idea.2 6.857 : Handout 11: Problem Set 4Problem 4-2. The MegaSoft Corporation has introduced a new public key cryptosystem, which works asexplained throughout the parts of this problem. Please answer all parts.(a) Each user finds a large prime p of the form p = 2qr + 1 where q and r are themselves distinct largeprimes. Sketch briefly how you would find such a prime p.(b) What are the possible orders of an element in Z∗p? How many are there of each type? (Note thatthere are φ(t) elements of order t, where φ is Euler’s totient function.) Explain briefly how you wouldfind a generator g in Z∗p.(c) Each user also needs to find two elements, a and b, of respective orders q and r. Explain how, givena generator g of Z∗p, you could find such elements. (Note: be careful — they are rare!)(d) A user’s public key consists of the quadruple (p, g, a, b). (The generator g isn’t really used, but isincluded anyway.) When another user wants to send an n-bit message m to the first user, he proceedsas follows:1. Let m = m1. . . mndenote the message, bit by bit.2. Each bit is encrypted and transmitted separately, in order.3. If mi= 0, he generates a random value k ∈ Z∗q, and sends akmod p as the ciphertext for this bit.If mi= 1, he generates a random value k ∈ Z∗r, and sends bkmod p as the ciphertext for this bit.(Note that this encryption is not terribly efficient: each message bit requires a modular exponentiation,and expands to a number as large as p in the ciphertext.) Argue that encryption is unambiguous:the ciphertext for a bit is either the result of encrypting a 0, or the result of encrypting a 1. In otherwords, no particular ciphertext for a bit can arise in both ways.(e) Explain how the recipient can decrypt the ciphertext efficiently.(f) Suppose that the discrete logarithm problem is easy modulo p: i.e., there is an efficient algorithm Awhich, given a prime p, a generator g, and a value y, finds an x such that y = gxmod p. Show how,by invoking A only once, an adversary can break this cryptosystem entirely.Problem 4-3. Please read the paper about Sebek, “Know Your Enemy: Sebek2,” which is posted on theclass web site. This paper was recently posted on the Internet.(a) Please give a summary of this paper in at most 1/2 page, in your own words. Be careful not toplagiarize or paraphrase the original paper too closely.(b) On balance do you think it is a good idea for such papers to be posted? Are such postings beneficialto society, or harmful? Please give your opinion, and explain your reasoning. Use at most one page.(For grading purposes, we care
View Full Document
Unlocking...