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:
Here is the information you will need to complete the assignment:
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.