Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 747 Assignment 3
Problems:
The aim of this assignment is to implement the RSA algorithm. Specifically, the implementation should include the following functions:
1 keyGen(r) →PU = (E,N),PR = (d,n)– 40 points
The key generation function takes as input a range r and outputs a public/private key pair. This function should have the following four sub-functions:
a. prime(r) → p, q: this function takes as input a range r and outputs two randomly selected primes p, q both of which are smaller than r Check divisibility of integers 2 through p− 1 (or q− 1) to confirm primality. Repeat until satisfied.
b. Phi(p, q) → Φ (n): this function takes as input previously selected two primes p, q and returns (p − 1) × (q − 1).
c. public(Φ(n)) → e: this function takes as input Φ(n) and outputs e which is a relative prime to Φ(n). The function first randomly select e then check whether the value is a relative prime to Φ(n) using the Euclidean Algorithm. Repeat until satisfied.
d.private(e,Φ(n)) → d: this function finds and returns e −1 modΦ (n) using the
brute-force strategy. A single for loop will be sufficient.
* There are no restrictions on the type of parameters and return values.
2. RSA(M,PU) → C,OR RSA(C,PR) → M– 15 points
The encryption function (note that RSA uses the same function for both encryption and decryption) takes as input a plaintext and a public key then outputs a ciphertext. Also, it takes as input a ciphertext and a private key then outputs a plaintext.
To find a multiplicative inverse, Extended Euclidean Algorithm should be implemented.
Please refer to: Extended Euclidean algorithm - Wikipedia
Note: For all other requirements and specifications not defined here, please refer to them in the textbook.
3. Combining with Assignment 1 – 15 points
Improve your implementation for 1 by using your Text Converter, so it can handle a string from a user and output a string.
Hint: you can execute the RSA function once for each letter, i.e., the plaintext “hello” needs five executions. For example, the input “hello” will be encrypted as follows:
(a) “hello” is converted to a list of characters: [‘h’,’e’,’l’,’l’,’o’](b) the list of characters is converted to a list of decimals as per ASCII code: [104, 101, 108, 108, 111]
(c) each decimal in the list is encrypted by the “RSA” function implemented for 2.
4. Add some testing codes of “Encryption” and “Digital Signature” to demonstrate the validity of the implementation – 10 points
5. Conduct some experiments to answer the following questions “How big primes can your computer handle?”, and “How fast does the computation overhead increase as the primes are getting bigger?” – 20 points
Complier requirement:
The text converter must be implemented using Python version 3.11.x or higher. Students must use Python official libraries that are accessible from the webpage (https://docs.python.org/3/library/index.html). All used libraries and their purpose should be described in the report.
Submission instructions:
Please submit your deliverables to the Webcampus Assignments folder:
- “HW 3”: create a txt file, copy and paste your entire Python code, save, and then submit with a written report explaining your implementation. The report should have some test inputs and screenshots of execution results, which verify the correctness of your implementation.
Once you submit, Webcampus will perform a similarity check for your submission and show you the result. Your similarity score must be lower than 50% unless valid reasons for a high score described in the report. Otherwise, (the score -50%) will be deducted.