RSA is an encryption algorithm where a sender, Bob, sends an encrypted message to a receiver, Alice. The process followed by RSA to create the encryption methods follows a somewhat complex mathematical reasoning that we summarize in the following image:

The first thing Bob does is to generate three values , , and following the four steps shown in the image. Then, he will share and , which allows Alice to encode the message following the formula in box (I). For example, if Alice wants to send the message and we have that and , the encoded message will be . That is, Alice sends over the channel (II). After that Bob, who is the only one who knows (in this case ), applies the decoding formula, obtains that , which matches the desired message (III).

If a third person intercepts the channel, they still won't know since it is not shared, so they will not be able to decode even if they have access to it.

Create a function that, given two primes and returns valid values of , and .

Hint.

One way to calculate the inverse of modulo is to use the python function pow(e, -1, theta).

Hint.

Remember that two numbers are coprime if the 'gcd' between them is equal to 1.

Hint.

Random values of must be taken until certain property is satisfied.

def create_keys(p, q):
"""Returns the characteristic e, d and N values of RSA

Args:
p (int): First prime number of the algorithm.
q (int): Second prime number of the algorithm.

Returns:
(int, int, int): a tuple consisting of the 'e' value of the RSA codification. 'd' value of the RSA codification.
and 'N', the product of p and q.
"""

##################
# YOUR CODE HERE #
##################


print(create_keys(3, 53))

or to submit your code

To interact with codercises, please switch to a larger screen size.

Learning Objectives:

  • Define what a public key cryptographic system is.
  • Describe the RSA encryption system.
  • Illustrate the importance of prime factorization in this algorithm.