Question

We are working on Public Key Crypto, RSA, Extended Euclidean algo

Let n = 2419 = 41 ∗ 59 and e = 7. (1) Find the private key d. (2) Encrypt the message 6. (3) Sign the message 10. Assume RSA is used. Use the egcd.py program at the lecture attachments folder, described in section 10.3.3, to compute d. For parts 2 and 3, you only need to show the formula; there is no need to calculate the final results.

egcd.py

#!/usr/bin/python3

def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = egcd(b % a, a)
return (g, y - (b // a) * x, x)

print ('This program gets two integers and calculates their gcd')
print ('Example: input e=18 phi=24, output gcd(18,24)=6 d=-1 y=1')
e = int(input('Input a number for e: '))
phi = int(input('Input a number for phi: '))
g, x, y = egcd(e, phi)

print ('gcd = ', g)
print ('d = ', x)
print ('y = ', y)

Answer 1

• • Generate the RSA modulus (n)

  • Select two large primes, p and q.

  • Calculate n=p*q. For strong unbreakable encryption, let n be a large number, typically a minimum of 512 bits.

• Find Derived Number (e)

  • Number e must be greater than 1 and less than (p − 1)(q − 1).

  • There must be no common factor for e and (p − 1)(q − 1) except for 1. In other words two numbers e and (p – 1)(q – 1) are coprime.

• Form the public key

  • The pair of numbers (n, e) form the RSA public key and is made public.

  • Interestingly, though n is part of the public key, difficulty in factorizing a large prime number ensures that attacker cannot find in finite time the two primes (p & q) used to obtain n. This is strength of RSA.

• Generate the private key

  • Private Key d is calculated from p, q, and e. For given n and e, there is unique number d.

  • Number d is the inverse of e modulo (p - 1)(q – 1). This means that d is the number less than (p - 1)(q - 1) such that when multiplied by e, it is equal to 1 modulo (p - 1)(q - 1).

  • This relationship is written mathematically as follows −

ed = 1 mod (p − 1)(q − 1)

The Extended Euclidean Algorithm takes p, q, and e as input and gives d as output.

Example

An example of generating RSA Key pair is given below. (For ease of understanding, the primes p & q taken here are small values. Practically, these values are very high).

• Let two primes be p = 7 and q = 13. Thus, modulus n = pq = 7 x 13 = 91.

• Select e = 5, which is a valid choice since there is no number that is common factor of 5 and (p − 1)(q − 1) = 6 × 12 = 72, except for 1.

• The pair of numbers (n, e) = (91, 5) forms the public key and can be made available to anyone whom we wish to be able to send us encrypted messages.

• Input p = 7, q = 13, and e = 5 to the Extended Euclidean Algorithm. The output will be d = 29.

• Check that the d calculated is correct by computing −

de = 29 × 5 = 145 = 1 mod 72

• Hence, public key is (91, 5) and private keys is (91, 29).