COMP 4109: Assignment #4

Assignment #4 was distributed on March 3th, 2005. It is due on March 14th at 2:30 PM in class. Please email program code and outputs to Mohammad Mannan (mannan at ccsl.carleton.ca), packaged as a zip file with the name "<your name>-<your student ID>-COMP4109-4.zip". Be sure to turn in all new code that you have written to answer these questions.

Partial solutions for Assignment #4

CHANGES IN ASSIGNMENT:

1. Question 1f (the PSS signature problem) is now extra credit, worth 25% of one assignment.
2. For parts b,d, and e of Question 2, assume that we want to choose t in terms of P(Miller-Rabin(x)=prime|x is composite). This basic bound is given by Fact 4.25 (p.140). The question as written actually refers to P(x is composite|M-R says prime), which is much more difficult to calculate. If you successfully solve these parts as written, it is worth extra credit of 25% of one assignment (no partial extra credit).

Here is the information you will need to complete the assignment:

• The assignment (PDF).
• The PKCS #1 version 2.1 document (PDF).
• The test document for problem #3, rsa-sign-test.txt. (If you've been wondering where the test documents have been coming from, you should read this one.)
• SHA-1 source code.
• The RSA key generation parameters (problem #1):

    p = (dec) 1294997164453275944271109799884135233106204830\
              9213822599057506383296279033782883353979096786\
              4090389251134097992454536767993842043269970116\
              42790179637598851
        (hex) f742249204e574135f7330a81a96c3fff98083d9329d65\
              90b53d78e8c4d27db0e3112c2615cbd56f96b2b3aefe66\
              18a8f7f6d1596c773d0b7c8019115ed49a83
  
    q = (dec) 1288600485749245557933298383947751213491770270\
              7975303156187635235084614583990561763410593759\
              1370840989511888148884146251757136701500808326\
              62017402087949187
        (hex) f6097ace575dcc8b226db9956d4d9351f9e3a84079c893\
              12f18ffa50e7bc8ce6d37b9f79f84bdc88de88ef011210\
              965518533d576a051cb077b873fd33944383
  
    e = (dec) 65537
        (hex) 10001
  

  (The parameter values p and q were obtained by running the command "openssl dhparam -dsaparam -text 512".)

Remember to show your work for all problems. For 1a (RSA key generation), this means that you will need to implement the extended Euclidean algorithm in a way that supports big integers. (Running this algorithm by hand would be very difficult.) Rather than doing this in C, I suggest that you do your work in a higher-level language such as Perl or Java. Here is an example Perl program that shows how to perform basic operations with big integers. For more documentation, look up Math::BigInt. On the other hand, If you prefer to program in C, I would suggest that you use the GNU multiprecision library (gmp) rather than implement your own big integer package.

One other tip: when the assignment says "manually," that means that you must show the appropriate intermediate computations. While you may write a program to help accomplish the task, you will need to walk through the process step-by-step and show your work.

Good luck!