Algorithm Works

In this part of the assignment you are to give a demonstration about how the Asymmetric RSA algorithm works. You can find information about the RSA algorithm in the Ciampa textbook 4^th edition p. 427, or in Chapter 8 of the Handbook of Applied Cryptography (Menezes et al., 1996).  A summarised description of the algorithm follows.

1. Choose two large random and distinct prime numbers p and q
2. Compute the value of n as: n=p*q. In terms of RSA, n is called the modulus.
3. Compute f as: f =(p-1)*(q-1)
4. Select a random integer e, 1<e< f, such that the greatest common divisor (gcd) between e and f is 1. That is to say: gcd(e, f)=1. This implies that e is such that e and f have no common positive divisors other than 1. In terms of RSA, e is called the encryption exponent.
5. Choose d so that e*d º 1 (mod f), where º is known as the congruence operator and (mod f) is known as the integer module. This implies that e*d – 1 is evenly divisible by f. In other words if the integer module is k, then [e*d – 1]/ f should be k. In terms of RSA, d is called the decryption exponent.

The Public Key is the combination of (e,n), used to encrypt the message. The Private Key is the combination of (d,n) used to decrypt the ciphertext and reveal the original message.

Given a Message M, to encrypt into ciphertext C, we use the following formula:
C = M^e mod n.

Given a Ciphertext C, to decrypt into plaintext message M we use the following formula:
M = C^d mod n.

1. Based on the information given, illustrate the RSA algorithm using the information extracted from your student number to obtain the message M, and to choose p and q. To do that follow these steps:

1. Take your student number and add all the numbers in it. From the result, take the least significant digit. This will be the message to encrypt. For example if your student number is s0209593, then the addition of the numbers is: 0+2+0+9+5+9+3 = 28 with the least significant digit being 8. The message is then M=8.
2. Take the two least significant digits of your student number and from there choose p and q such that: p< two least significant digits <q. In our example, the two least significant digits of the student number are 9 and 3, therefore p<93<q.

Once you have chosen M, p and q, fill the following Table:

Student Number
M
p
q
n
f
e
d
C= Me mod n
M = Cd mod n

Do not forget to show your working. If you do not show your working then you will not have marks. To calculate C= M^emod n and M = C^d mod n you may need to use the Modular Exponentiation algorithm. Information about this algorithm can be found in the web using a search engine like Google and searching for “Modular Exponentiation”) (2 marks)

1. Based on your illustration of RSA and your research in the field, write a 200 word essay that addresses the following questions: what are the weaknesses of the RSA algorithm? How close p and q should be. How big are they supposed to be? How is n supposed to be in terms of factoring? What happens when e is small? What are the optimum values for e and d? All your references should be cited using the Harvard or APA format (3 marks)