Massachusetts Institute of Technology Handout 66.857: Network and Computer Security October 5, 2004Professor Ronald L. Rivest Due: October 12, 2004Problem Set 4Submit 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].We may distribute our favorite solution to each problem as the “official” solution. If you do not wish foryour homework to be used as an official solution, or if you wish that it only be used anonymously, pleasenote this on your homework.Problem 4-1. MoogleTMWant Ads [Group]Flush with cash after its recent IPO, MoogleTMhas launched a campaign to hire top computer sciencestudents. To attract talented students, Mo ogleTMposts the following puzzle on a billb oard:{ First 20-digit Sophie Germain Prime in e}.comA Sophie Germain prime is a prime number p such that 2p + 1 is also prime. Similarly, what is referred toas a safe prime is a prime q such that (q − 1)/2 is a prime. We have provided Python code for basic numbertheory functions at http://crypto.csail.mit.edu/classes/6.857/code/numbthy.py. Code to generatea fixed number of digits of e is available at http://crypto.csail.mit.edu/classes/6.857/code/e.py.(a) What URL would MoogleTM’s billboard lead to?(b) Find the longest Sophie Germain prime you can that occurs as a sequence of consecutive digits inthe digits of e = 2.718281828459045235 . . .. Turn in the length of the prime (in digits), the value ofthe prime, and its position in the decimal expansion of e. For example the Sophie Germain prime 23has length 2 and is at position 17, and the Sophie Germain prime 6059563073 has length 10 and is atposition 150.(c) Estimate the length of the longest Sophie Germain prime p you would expect to find among the firstmillion digits of e, using the known density of primes as a guide.(d) Now find the longest safe prime p0you can in the digits of e such that 3 is a generator modulo p0.That is, find the biggest p0you can in e such that p0= 2p + 1 and h3i = Z∗p0.(e) Estimate the length of the longest safe prime p0= 2p + 1 you would expect to find among the firstmillion digits of e such that 3 is a generator modulo p0.Problem 4-2. ElGamal Signatures [Individual]Recall the ElGamal public-key cryptosystem presented in class. Given s ystem parameters prime p andgenerator g, individuals will generate a public key y by choosing a random secret key x ∈ Z∗pand computingy = gxmod p. Given a public key y, message m is encrypted by selecting a random r ∈ Z∗pand computingE(m, r, y) → (grmod p, yrm mod p). Someone who knows y’s corresponding secret key x can decrypt aciphertext (u, v) by computing D(u, v, x) →vuxmod p.(a) Ben Bitdiddle gets lazy and reuses the s ame r to encrypt multiple messages with ElGamal. SupposeAlyssa P. Hacker happens to know the plaintext message corresponding to one of Ben’s ciphertexts.Explain how Alyssa is able to read all of Ben’s messages.2 6.857 : Handout 6: Problem Set 4One can also compute digital signatures in the ElGamal cryptosystem. To sign a message m, someone whoknows the private key x first selects a random r ∈ Z∗pand computes the signature:S(m, r, x) : s ← grmod pt ←m − sxrmod (p − 1)Return signature (s, t)A signature (s, t) on message m is verified as follows:V (m, s, t) : V1← stysmod pV2← gmmod pAccept signature if V1= V2(b) Ben gets lazy and stops generating new random values r for each signature. He signs two messagesm1and m2using the same random value r. This produces two signatures (s1, t1) and (s2, t2). Showhow given m1, m2and Ben’s signatures, Alyssa can recover Ben’s secret key x. Assume that (t1− t2)and s1are relatively prime to (p − 1).Problem 4-3. Voter-Verifiable Elections [Group](a) In Chaum’s system presented in lecture, the voter gets two ballots at the polling place. One is used toactually vote; the other is used to test that the (hidden) mappings on the bulletin board are correct.Why is this more desirable than having precinct officials test a bunch of random ballots initially andthen only give a single ballot to each voter?(b) Recall that the “bulletin board” in Chaum’s system as presented in lecture contains two separatebatches of envelopes and a batch of unobscured ballots. The first trustee reveals the mapping betweenhalf of the ballots in the first batch and the corresponding half in the second batch; the second trusteereveals the mapping betwe en the other half of the second batch and the corresponding unobscuredballots.In his paper linked from the course website, however, Chaum desc ribes a system that uses manytrustees in the chain; each reveals half of the mappings they know in such a way that a complete pathfrom the first envelope to the unobscured ballot is never revealed. What is benefit of using more thantwo levelsof trustees?(c) What is one security property of an electronic voting system that is not addressed by Chaum’s
View Full Document
Unlocking...