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:

- Question 1f (the PSS signature problem) is now extra credit, worth 25% of one assignment.
- 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!

Created by soma at scs.carleton.ca.

Last modified: March 3, 2005.