Lab 2: Implementation and Analysis of RSA Cryptosystem
Assigned: Thursday, February 7
Due: Thursday, February 28
Purpose
- To have a deep understanding of RSA algorithm and number theory.
- To practice the empirical evaluation of the algorithms
Description
In this lab, You will write a program to implement the RSA public-key cryptosystem that we have discussed in this two weeks. You are also required to empirically analyze its time complexity. One assumption of RSA is that p, q need to be large prime (hundred/thousands of bits). However, the built-in C only support upto 64 bit integers. Though there are some libraries such as gmb for C programming, java.math.BigInteger for Java programming. You are required to design an self-defined data type that is capable of manipulating much larger integers, and then use this data type to implement RSA to encrypt and decrypt messages. There are three phases for this project:
- Implement a basic extended precision arithmetic data type and basic arithmetic operations (addition and subtraction are provided. You need finish multiplication and division). It is due on Feb 14.
- Implement Euclid's gcd algorithm and extended-Euclid algorithm to generate a pair of keys. For this project, you can simply pick two fixed large primes from http://primes.utm.edu/lists/2small/100bit.html as p, q (which should not be too close). The extra credit is to generate two random primes (randomly generate a number and then go through prime test). Implement modular exponentiation to enable encryption and decryption of the message. It is due on Feb 21.
- Integrate all the components into a complete RSA system. You need also implement a function to break the message into fragments in order to encrypt or decrypt. Empirically evaluate your algorithm's complexity, in terms of both time and number of basic operations. You can specify the basic operation, e.g per digit addition). It is due on Feb 28.
This assignment is referenced from http://www.cs.princeton.edu/courses/archive/spr03/cs126/assignments/rsa.html, where you can find more detailed information. A basic header file and several basic function is provide in xp.h and xp.c. And here is a sample test file test.c. You can use Java if you want. Here is a sample file for XP.java XPtest.java. You are not allowed to use Java library to implement RSA.
Other interesting links:
Submission
- A hard copy of the source code and output of all your programs. You should use command ``a2ps'' or ``enscript -2rG'' to print them in two columns.
- A hard copy of your lab report written in Latex. It should include the following contents:
- Section 1 Introduction: a brief description of the problem and the purpose of the lab.
- Section 2 Implementation: a brief description of how to implement the algorithms to calculate Fibonacci numbers, and how to measure the time overhead.
- Section 4 Analysis: a brief description of the theoretical analysis of the algorithm.
- Section 3 Empirical Evaluation: a detailed description of your experiment setup, performance metrics, sample input, and analysis of experiment result.
- Section 5 Conclusion
Link to this Page
