Massachusetts Institute of Technology Handout 96.857: Network and Computer Security October 23, 2006Professor Ronald L. Rivest Due: October 30, 2006Problem Set 5This problem set is due via email, to [email protected] on Monday, October 30 by thebeginning of class.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, let us know.Homework must be submitted electronically! Each problem answer must appear on a separate page. Markthe top of each page with your group member names, the course number (6.857), the problem set numberand question, and the date. We have provided templates for LATEX and Microsoft Word on the course website(see the Resources page).Grading and Late Policy: Each problem is worth 10 points. Late homework will not be acceptedwithout prior approval. Homework should not be submitted by email except with prior approval. (Somebodyfrom 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 use d anonymously, please note this on your homework.Problem 5-1. Elliptic Curve Digital Signature AlgorithmFor this problem you will implement an Elliptic Curve (EC) analogue of the Digital Signature Algorithm(DSA), so you will be working in an elliptic curve group E(Zp). Note that for historical reasons the groupoperation for an elliptic curve has been called addition, so for instance the discrete log problem is: givenP ∈ E(Zp) and Q = aP , find a.The algorithms for ECDSA are given below (taken from Johnson and Menezes, “Elliptic Curve DSA: AnEnhanced DSA”).ECDSA key generation.1.Select an elliptic curve E defined over Zp. The number of points in E(Zp) should be divisible by a largeprime n.2.Select a point P ∈ E(Zp) of order n.3.Select a statistically unique and unpredictable integer d in the interval [1, n − 1].4.Compute Q = dP .5.output the public key (E, P, n, Q), and secret key d.ECDSA Signature generation. To sign a message m:1.Select a statistically unique and unpredictable integer k in the interval [1, n − 1].2.Compute kP = (x1, y1) and r = x1mod n. If r = 0, then go to step 1.3.Compute k−1mod n.4.Compute s = k−1{h(m) + dr} mod n, where h is the Secure Hash Algorithm (SHA-1).5.If s = 0, then go to step one.6.Output the signature (r, s) for the message m.ECDSA Signature verification. To verify a signature (r, s) on a message m:1.Obtain the public key (E, P, n, Q).2 6.857 : Handout 9: Problem Set 52.Verify that r and s are integers in the interval [1, n − 1].3.Compute w = s−1mod n and h(m).4.Compute u1= h(m)w mod n and u2= rw mod n.5.Compute u1P + u2Q = (x0, y0) and v = x0mod n.6.Accept the signature if and only if v = r.In the above key generation algorithm, we need to calculate the number of points on an elliptic curve.Although this can be computed in polynomial time, it is a bit messy, so we will follow the guideline of NIST(FIPS PUB 186-2, “Digital Signature Standard (DSS)”), and use one of its suggested curves, curve P-192(page 29). Note that the group size (called r by NIST) is prime for P-192. Also note that NIST calls thebase point P by the name G (with comp onents Gxand Gy).(a) Read Appendix 6.4: Generation of pseudo-random curves(prime case), page 63 of the NIST document.Argue that the choice of a and b satisfies 4a3+ 27b26≡ 0 mod p.(b) Implement the key generation (with E and P as suggested by NIST), signature generation andverification algorithms using Python. Turn in your code.(c) Using your implementation, generate a signature on some message m and verify that the signature isaccepted. Turn in your message and the signature generated.Problem 5-2. Evil Key GeneratorsAlice has been hired by BitDiddle Software to write the RSA key generation routines for their new software.Alice’s routine will take as input a number k (e.g. k = 1024) and produce a k-bit integer n that is theproduct of two primes p, q of approximately k/2 bits each. Alice’s routine will also produce values e andd that are multiplicative inverses of each other modulo φ(n). Alice’s software will be used by BitDiddle’scustomers to produces their RSA keypairs. (Of course, Alice’s software also has available a good source ofrandom bits.)Unknown to the higher-ups at BitDiddle, however, Alice has been recently corrupted by BitDiddle’s com-petitor, BitTwiddle (Bob, who runs BitTwiddle, has offered Alice some nicely developed beach property inSecond Life if Alice cooperates...)Bob asks Alice to “fix things” so that BitDiddle’s key generation routine produces “weak” RSA keys thatBob can easily ”break”.Alice thinks of three approaches.1. Use a ”crippled” random number generator that can only produce 109different primes p or q. (Thus,there are about 1018different moduli n that could be produced; p and q are produced independentlywith this crippled generator.) Bob can build a table of the possible primes, and easily figure out whichones divide the public n of each BitDiddle customer.2. Alice’s software picks a value of e randomly, and then uses that as a seed for a pseudorandom numbergenerator to generate the starting values in the search for the primes p and q. (If e turns out notto be relatively prime to φ(n), the process is restarted.) Bob knows the code for the pseudorandomgenerator, which is embedded in Alice’s software, and so can regenerate the primes himse lf once he seesa customer’s e.3. Alice’s software includes Bob’s public RSA key PKB. When a BitDiddle customer requests a publickey, Alice’s software generates primes p and q randomly as usual, and then computes e = E(P KB, p).That is, the customer’s e is just the encryption of the customer’s p, under Bob’s public RSA key. (Aminor point: if this number e is not relatively prime to (p − 1)(q − 1), the process is restarted.)6.857 : Handout 9: Problem Set 5 3Answer each of the following problem parts.(a) Discuss the possible ways for Alice’s treachery to become discovered with these three methods.(b) Discuss the difference in c onsequences for
View Full Document
Unlocking...