Using the RSA algorithm, if p = 13, q = 19, and e = 11. a. Encrypt a message M = 4. b. Calculate the encryption key d. 

As a starting point for RSA choose two primes p and q.

1st prime p=13

2nd prime q=19

For the algorithm to work, the two primes must be different.

For demonstration we start with small primes. To make the factorization difficult, the primes must be much larger. Currently, values of n with several thousand binary digits are used for secure communication.

n = p × q

247 (8 Bit)

The product n is also called module in the RSA method. The public key consists of the module n and an exponent e.?. ????e??=??????11????????

Encrypting a message m (number) with the public key (n, e) is calculated:

m' := me (mod n)

plaintext

4

ciphertext

244

??Secret key

RSA uses the Euler φ function of n to calculate the secret key. This is defined as?

?

φ(n) = (p − 1) × (q − 1)?

216?

?

Here it is used that p and q are different. Otherwise, the φ function would calculate differently.?

?

It is important for RSA that the value of the φ function is coprime to e (the largest common divisor must be 1).?

?

gcd(e, φ(n))?

1?

?

To determine the value of φ(n), it is not enough to know n. Only with the knowledge of p and q we can efficiently determine φ(n).?

?

The secret key also consists of n and a d with the property that e × d is a multiple of φ(n) plus one.?

?

Expressed in formulas, the following must apply:?

?

e × d = 1 (mod φ(n))?

?

In this case, the mod expression means equality with regard to a residual class. It is x = y (mod z) if and only if there is an integer a with x − y = z × a.?

?

For the chosen values of p, q, and e, we get d as:?

?

d?=59??

?This d can always be determined (if e was chosen with the restriction described above)—for example with the extended Euclidean algorithm??