Massachusetts Institute of Technology Handout 126.857: Network and Computer Security September 26, 2002Professor Ronald L. RivestProblem Set 3This problem set is due on Thursday, October 3, 2002 at the beginning of class. Late homeworkswill not be accepted. This entire problem set is a group problem set. You must, however, continueto cite your sources properly.At the end of each problem, tell us how each person contributed (writing, designing, coding,proof reading, never showed up, etc).Problem 3-1. All your PRIMES is belong to us1You are a new technical lead at PRIMES Computer, Inc. Your job is to manufacture groovy primes.Your boss, Austin M. Powers2, has generated a special task for your group.In a 6.857 lecture secretly simulcast at PRIMES Computer, Inc., you learned about primality testingand generators of a group Z∗pwhere p is prime. Austin has assigned you the task of generatingsuch values.Austin says you may use any programming language you like, though we recommend Java becauseof its BigInteger package. The numbers you will be working with are quite large – plain old long orinteger types won’t be large enough. If you use C or C++, you could try the GNU mp package.If you use this package, you are on your own though.In this problem, you may not use any built-in procedures for primality testing, prime numbergeneration, or generator discovery. You can assume you have a source of randomness. If youborrow any code, cite the appropriate authors. Moreover, you must explain how and why anyborrowed code works with inline comments.We recommend you read Chapter 31 of CLRS [1] and perhaps pages 160–164 of HAC [3].(a) Generators of Z∗pWrite a function to generate a b-bit prime given parameters b and a source of randomness. Yourfunction should produce a b-bit number that has an overwhelming probability of being prime. Writea second function that given g, p, and the prime factorization of p − 1 tests whether the element gis a generator of Z∗pwhere p is prime.Using these functions, write a program that given a list of names, a number b, and a source ofrandomness, produces a b-bit prime number p for such that each name (treated as an element ofZp) is a generator of Z∗p.A potentially comforting fact is that the number of generators of Z∗pis φ(φ(p)) where φ is Euler’sphi function. In the special case where your prime p = 2q + 1 and q is prime, then φ(φ(p)) = q − 1.If you generate a prime p with this form3, then you already know the factors of p − 1.To encode names as elements, take the hexadecimal ASCII representation. Then combine the digitsinto a single number. The first letter of a name is the high order byte, the last letter of the name1Somebody set us up the factors at http://www.planettribes.com/allyourbase/index.shtml2Modular is his middle name.3You have no chance to factor, make your time.2 Handout 12: Problem Set 3is the low order byte, etc. If your group consisted of members Kevin, Thien-Loc, and Ron, yournames and elements would be:Name ASCII Hex Element in decimalKevin 0x4B 65 76 69 6E 323824806254Thien-Loc 0x54 68 69 65 6E 2D 4C 6F 63 1557050158367982251875Ron 0x52 6F 6E 5402478Print out and submit your code. Please make sure there are no line-wrap problems.(b) Expected amount of work to find primes and generatorsFor a random prime number p, what is the approximate probability of a random element g ∈ Zpbeing a generator of Z∗p? You can assume p is large.How many trials do you expect to make for your group to find a suitable prime p such that eachof your names is a generator of Z∗p? Give your estimate in terms of b (the size of a b-bit prime p)and the number of students in your group s.(c) Find a primeUsing your program from part (a), find a prime number p where your first names are generators ofZ∗p. (1) Tell us this prime. You can try for any size prime. We recommend trying small bit sizes(e.g., 64) for testing. If you finish early, try to generate a 1024-bit prime (this could take a lot oftime especially in Java, so only do this for fun if you have time).(2) In your final run of the working program, how many trials did it take to find a suitable prime?That is, how many random numbers did you try before finding a suitable prime?(d) Finding co-Sophie-Germain primesWe alluded to Sophie-Germain primes in part (a). A number q is a Sophie-Germain prime if 2q + 1is also prime. We then call the value 2q+1 a co-Sophie-Germain prime (or sometimes a safe prime).While we know there are an infinite number of primes, it’s an open problem whether there are aninfinite number of Sophie-Germain primes. It turns out that in practice, however, Sophie-Germainprimes are not too rare.Assuming that the likelihood of q being prime and 2q+1 being prime is independent, approximatelyhow many 1024-bit Sophie-Germain primes would you expect to exist?Problem 3-2. A MAC based on a block cipherAlice missed Professor Rivest’s lecture recommending that to obtain both confidentiality and au-thentication, one should first encrypt the message, then append a MAC of the ciphertext to theend of the ciphertext.So, for her project she implements the following procedure. In her project all messages are asequence of 128-bit blocks exactly (no partial blocks). She first appends a checksum block tothe end of the message, where the checksum block is the XOR of the message blocks. Then sheencrypts the message/checksum sequence using AES in CBC mode using a randomly-chosen IV.The unencrypted IV, as usual, becomes the first block of ciphertext.The recipient Bob first decrypts the message/checksum sequence, and then checks that the checksumis correct. If the checksum is not correct, Bob concludes that the ciphertext was forged or alteredHandout 12: Problem Set 3 3in some manner; it is not authentic. Of course, Alice and Bob share a secret key for the encryptionoperation.Alice figures that since the message and checksum are encrypted, an adversary who doesn’t knowthe encryption key should not be able to forge a ciphertext that Bob will accept as authentic.Show that Alice’s scheme is insecure against a chosen plaintext attack, in which an adversary canarbitrarily choose a number of plaintext queries, and obtain Alice’s encryption of each of them (withchecksum). The adversary is judged to have succeeded if he can then produce a new ciphertext,not identical to any that Alice returned to him, that Bob would nonetheless accept as authentic.The attack may or may not need to be adaptive,
View Full Document
Unlocking...