Question

Alice and Bob are going to communicate using the RSA system. Alice has chosen primes p and q and public exponent e. Bob wishes to send the message m to Alice.

The numbers are p = 11 , q = 23, e = 147 and m = 4.
Show all calculations and explain how Alice generates their public key

Answer 1

Alice calculates her public key for the RSA system by first finding the modulus by multiplying primes p and q.

Then, she selects an exponent e that should be relatively prime to (p-1)(q-1) and uses it with the modulus to form the public key.

Step-by-step explanation:

Alice is generating a public key using the RSA algorithm with the given primes p and q, and a public exponent e.

The public key is a part of the RSA system used for secure communication between two parties.

First, Alice calculates the modulus n by multiplying p and q:

n = p × q

= 11 × 23

= 253

Then, to create the public key, Alice will use the modulus n and the public exponent e.

However, since e must be less than φ(n) (where φ is Euler's totient function) and relatively prime to it, Alice needs to ensure that 147 is a valid choice for e.

The totient of an n is calculated as:

φ(n) = (p - 1) × (q - 1)

= (11 - 1) × (23 - 1)

= 10 × 22

= 220

However, for this exercise, if e is 147, then Alice's public key is (e, n) = (147, 253).