Next, let’s look at RSA encryption, which only uses the public key. (which, in turn, used the extended_euclidean_gcd Modular_inverse function we defined in the last chapter
Once we haveĮ, we can finally calculate the last part of our private Phi_n have a greatest common divisor of 1. Generate an e, but the while loop ensures that theĮ we finally choose is valid. The algorithm makes use of both a while loop and the # Notice that we're using our modular_inverse from our work in the last chapter! d = modular_inverse(e, phi_n) return ((p, q, d), (n, e)) e = random.randint( 2, phi_n - 1) while math.gcd(e, phi_n) != 1: e = random.randint( 2, phi_n - 1) # Choose d such that e * d % phi_n = 1. phi_n = (p - 1) * (q - 1) # Since e is chosen randomly, we repeat the random choice # until e is coprime to phi_n. Preconditions: - p and q are prime - p != q ''' # Compute the product of p and q n = p * q # Choose e such that gcd(e, phi_n) = 1. The second tuple is the public key, containing (n, e).
The first tuple is the private key, containing (p, q, d). The return value is a tuple containing two tuples: 1. \newcommandĭef rsa_generate_key(p: int, q: int) -> \ tuple, tuple]: '''Return an RSA key pair generated using primes p and q.
