Requirement:

You need to finish this assignment independently.

1. In the process of implementing RSA, exponentiation in modular arithmetic is an important issue in computing

M^e mod n.

Read paragraphs in page 289 in the textbook (6th edition) and make sure you fully understand the technical content and implement the Algorithm in Figure 9.8. You are required to do the following:

- You code this algorithm in one programming language and make sure it can be used to compute a^b mod n for positive integer numbers a, b n with length less than 10 digits. Hand in the hard copy of your code with the demonstration of the following specific question.

- Use your code to compute 236²³⁹⁷²¹mod 2491 and print out the final result.

2. Implement RSA as described in the following steps.

- Select two prime numbers p and q using the algorithm in Question 3 of lab 2. The range of p and q is required to be between 1000 and 10000.
- Using the Extended Euclid Algorithm to select
{e, n} satisfying gcd(e, Φ(n))=1.
- Using the Extended Euclid Algorithm to solve a private key d.
- Covert each symbol on keyboard to its ASCII code for RSA encryption and decryption.
- Implement RSA encryption and decryption using the algorithm in Question 1 of this assignment.
- When you finish all steps above, you are required to encrypt and decrypt a text file. 1) In your hard copy, state each step clearly with explanations in your code. 2) The test file will be the same for S-DES in Assignment One which can be found in the unit website. Hand in the one page of the original text, the ciphertext and decrypted text to validate the effectiveness of your code. 3) If your code is not working, address the difficulties you have.

3. Assuming that Alice signed a document m using RSA signature scheme. (You should describe RSA signature structure first). The signature is sent to Bob. Accidentally Bob found m' such that H(m)=H(m'), where H() is the hash function used in the signature scheme. Describe clearly how Bob can forge a signature of Alice's with such m'. Justify your forgery with the knowledge you learned from this unit.

4. In page 36 of lecture 9, Please prove the verification stage for DSS. Make sure that you understand each step in your proof with detail comments for justification. For example, justify why k^-1 mod q exists.

5. Based on lecture 8, please prove the following assertion.

In a group of 23 randomly selected people, the probability that two of them share the same birthday is larger than 50%.