4. Programming assignment

Begin by loading the code for problem set 2, using the Edwin command M-x load problem set.

Note on debugging procedures that use randomness: Many of the procedures you will be working with this assignment depend on selecting random numbers, and so will give different answers each time you run them. Such procedures can be confusing to debug, since it's hard to tell whether things are changing due to your modifications or just due to selecting different random numbers. To help you in debugging, we've provided a procedure reset-random! (which takes no arguments). Whenever you run (reset-random!) the random number generator will be returned to its initial state. This permits you to do repeatable experiments.

Computer exercise 1:

Implement the decrypt procedure, which takes as arguments an encrypted message and a key system and produces the unencrypted message (assuming the key system is the correct one for decrypting the message). For testing your procedure, we've provided a key-system ks-ex-1 and a test encrypted message, enc-message-ex-1. Turn in a listing of your procedure and demonstrate that you can decrypt the message.

Check the 6.001 discussion forum for computer-ex-01

Look here for information about the forum.

Computer exercise 2:

Define the procedures find-generator and choose-safe-prime, which you wrote for tutorial exercise 1. Test them by finding a safe prime (use size equal to 5) and a generator for it. Once you think this is working, you should be able to run the procedure generate-key-system. Generate a key system and the corresponding public key. Demonstrate that you can use the public key to encrypt messages and then use the key system to decrypt them.

Check the 6.001 discussion forum for computer-ex-02

Look here for information about the forum.

Computer exercise 3:

Implement the verify procedure for ElGamal digital signatures. To test your code, we've pre-defined a public key pk-ex-3 and two signed messages: m1-ex-3 with signature s1-ex-3, and m2-ex-3 with signature s2-ex-3. Determine which message is authentic.

Check the 6.001 discussion forum for computer-ex-03

Look here for information about the forum.

Computer exercise 4:

Define the procedure solve-ax+by=1. It takes two non-negative integer arguments a and b whose GCD is assumed to be 1 and returns the list consisting of integers x and y. Demonstrate that your procedure works by finding integers x and y that satisfy the equation:

Don't forget to check your answer! Once this is working, you should be able to generate a key system and use this to sign a message with the sign procedure. Demonstrate that you can sign messages and then verify the signatures with the corresponding public key.

Check the 6.001 discussion forum for computer-ex-04

Look here for information about the forum.

Computer exercise 5:

Write a procedure find-discrete-log that solves the discrete log problem by brute-force search. It should take as arguments values for y, g, and p, and return an x such that . Once this has been defined, you should be able to run the supplied procedure crack-public-key that cracks a public key, returning the original key system. Test your procedure by cracking the public key pk-ex-5 of size 4, which is predefined in this problem set to be p=19079, g=362, y=6843.

Check the 6.001 discussion forum for computer-ex-05

Look here for information about the forum.

Computer exercise 6:

How long does it take to crack the ElGamal system? To help you determine this, we've included a procedure called timed, which, if you place at the beginning of a combination, will evaluate the rest of the combination (as if the timed weren't there) and return the value along with the time required for the evaluation. Thus, evaluating

(timed crack-public-key pk)

will apply the procedure crack-public-key to the argument pk (or whatever argument you want to use) and return the result, together with the time (in seconds) required to do the computation. Crack some public keys of size 4. Remember that all the random choices will result in a wide range of results, but you should be able to get some sort of average time. How do you expect the time to crack the key to grow as the size of the prime increases? Suppose you had a million times the computational resources that you are now using in working on this problem set, and that all these resources could be dedicated to cracking a single key. How long would it take to crack a key of size 50? Of size 100? Give your answer in seconds, minutes, days, or years, whichever seems most appropriate.

Check the 6.001 discussion forum for computer-ex-06

Look here for information about the forum.

Computer exercise 7:

It was a dark and stormy night. A 6.001 lecturer sat hunched over his terminal. Suddenly there was a crash as a rock flew through the window. Attached to the rock was a note:

Our network sniffer has just intercepted the following e-mail
addressed to Dean Williams. -- A friend
  13998
  \232\211\351\216\3509m\025\327\234V\203v\354=F\tw\026\004~\335\264\234
  \234\233bU\223b\206/\310\276\356\331\240\256I\262\360\317\266I\002\373
  J\221eq<\001\301\236\303\375\372\373OFj\331\000\325c&z\306x\216\243\b
  \341\250\006\026\367X\r\302\343b~\t\271\222rkE\030C\325\033\372z\3245n
  \3506\025{[)\313+p\350x;%u\006\262\225\331\237\272K\202u1\257\331\305
  \235e5(\327,\231\255\306\223\3345\370\262h\337\242.\211|\325\3736c\004
  D84iOH\322eLl\000\267\036\371\313V(\376H\312\270\001\234\203\220b\330
  \265\354\020k$= X&\250? \372

The Dean's office is working on better security, but due to reengineering, they have been unable to issue public keys of size greater than 5. William's public key and the above cipher-text are defined for you as pk-ex-7 and secret-ex-7. Crack the key and decrypt the message. It sounds ominous, doesn't it? (Be patient in cracking the key, which may take a minute or two. Note that this is a longer key than the ones you cracked in exercise 6.)

Check the 6.001 discussion forum for computer-ex-07

Look here for information about the forum.

Turn in answers to the following questions along with your answers to the questions in the problem set:

1. About how much time did you spend on this homework assignment? (Reading and preparing the assignment plus computer work.)
2. Which scheme system(s) did you use to do this assignment (for example: 6.001 lab, your own NT machine, your own Win95 machine, your own Linux machine)?
3. We encourage you to work with others on problem sets as long as you acknowledge it (see the 6.001 General Information handout).
   • If you cooperated with other students, LA's, or others, or found portions of your answers for this problem set in references other than the text (such as some of the archives), please indicate your consultants' names and your references. Also, explicitly label all text and code you are submitting which is the same as that being submitted by one of your collaborators.
   • Otherwise, write ``I worked alone using only the reference materials,'' and sign your statement.