Python - Group home

The very first step is to generate two prime numbers, p and q. We are going to use the SymPy built-in Python module. SymPy has a method called randprime() that can generate a random prime between two numbers. We need to ensure that the two prime numbers generated are different.

Once we have the two (different) prime numbers, we should calculate the RSA modulus r. r = p*q (remember that the fundamental basis of the RSA Asymmetric Encryption Process is the fact that it is extremely easy to compute the RSA modulus r = p*q, but very difficult to reverse). And, as we know, the RSA modulus r is used later on in the encryption and decryption processes.

IMPORTANT NOTE: - Talking about the key size (in bits), it is the RSA modulus r that is constrained. For example, if we want to use a 8-bit key, the RSA modulus r cannot exceed 2^8 = 256. Therefore, we need to check in our code that the RSA modulus r is not too large for the desired key size. Our code should have the logic to ensure that the RSA modulus r is less than 2^KeySize.

#Importing the SymPy library
from sympy import randprime

#Importing the greatest common divisor method from math
from math import gcd

#The following two functions will return a value of d when you pass it the parameters public-key exponent and totient.
def extended_gcd(aa, bb):
    lastremainder, remainder = abs(aa), abs(bb)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
        x, lastx = lastx - quotient*x, x
        y, lasty = lasty - quotient*y, y
    return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

#We produce the private-key exponent by finding the modular inverse of the public-key exponent, using the totient as the modulus.
def modinv(a, m):
	g, x, y = extended_gcd(a, m)
	if g != 1:
		raise ValueError
	return x % m

#Try not to go for more than a 24 bit key because Python is too slow for larger numbers
print(" Please do not go for more than a 24 bit key because Python is too slow for larger numbers. ")
key_size = int(input(" Please enter the desired key size: "))
key_size_string = str(key_size)
print(" Thank You!!! You have chosen the desired key size to be of " + key_size_string + " bits.")

#Set the two prime numbers to 0 so that they are declared before the loop
prime1 = 0 
prime2 = 0

#The Loop will keep on generating prime numbers until both the following conditions are met.
#   1. Both the prime numbers are unique.
#   2. Their product is not larger than the key size (2^key_size)
while prime1 == prime2 or (prime1 * prime2) > 2**key_size:
    prime1 = randprime(3, 2**key_size/2)
    prime2 = randprime(3, 2**key_size/2)
    
#Display the two prime numbers
print("  1st Prime Number -----> " + str(prime1))
print("  2nd Prime Number -----> " + str(prime2))

#Calculate and display the RSA modulus r
RSA_modulus = prime1 * prime2
print("  RSA Modulus r -----> " + str(RSA_modulus))

 Please do not go for more than a 24 bit key because Python is too slow for larger numbers. 
 Please enter the desired key size: 16
 Thank You!!! You have chosen the desired key size to be of 16 bits.
  1st Prime Number -----> 599
  2nd Prime Number -----> 101
  RSA Modulus r -----> 60499

We will now have to calculate the Euler’s totient φ = (p-1)(q-1).

#Calculate and display the Euler’s totient.
totient = (prime1 - 1)*(prime2 -1)
print("  Euler's totient -----> " + str(totient))

Euler's totient -----> 59800

We will now have to select a number e (for ‘encryption’) that will be our public-key exponent. The number e must obey the following two properties.

(i) 1 < e < totient

(ii) e must be co-prime with RSA_modulus and totient. In other words, e should be a number that doesn’t have a common factor with RSA_modulus or totient. In simple words, the number e should be relatively prime to the totient value, which means that e and the totient value should share no common factors except 1. Now, in order to test whether two numbers are relatively prime, the highest common factor needs to be worked out between the two numbers. If the largest number that goes into both of them evenly is 1, then the two numbers are relatively prime. We will use the gcd() function of the in-built Python library math.

#Choosing the public-key exponent
public_exponent = 0

for e in range(3, totient-1):
  if gcd(e, totient) == 1:
    public_exponent = e
    break
    #Aim for the lowest possible value, thus saving computation time

#Display the public-key exponent e
print("  Public-Key exponent, e -----> " + str(e))

#Display the public key
print("  Public Key -----> (" + str(public_exponent) + ", " + str(RSA_modulus) + ")")

  Public-Key exponent, e -----> 3
  Public Key -----> (3, 60499)

We would now have to choose a number d (for ‘decryption’), such that d*e (mod 𝜙) = 1.

#Find the modular inverse of the public-key exponent and use as the private-key exponent
private_exponent = modinv(public_exponent, totient)

#Display the private-key exponent e
print("  Private-Key exponent, d -----> " + str(private_exponent))

#Display the private key
print("  Private Key -----> (" + str(private_exponent) + ", " + str(RSA_modulus) + ")")

  Private-Key exponent, d -----> 39867
  Private Key -----> (39867, 60499)

Now that our Public and Private Key pairs have been generated, we can use those to encrypt and decrypt messages.

Encryption: - cipher text = c = ENCRYPT (message, m) = m^e mod r. When we use a number as a power, the number is called an exponent. Therefore, we call the number e the public-key exponent.

For the sake of simplicity, we are going to encrypt a single character. Before encrypting a character, we will first encode the character as a number - we will use ASCII encoding. We can convert a character to the number used to represent it in ASCII, by using the Python function ord().

#ENCRYPTION
#Plain text setup
print(" For the sake of simplicity, we are going to encrypt a single character. Please enter below a single character only. ")
plain_text = str(input(" Please enter the character that you would want to encrypt: "))

#Using ord to get ASCII encoding of the character entered
#chr is used to generate a character from an ASCII encoding
cipher_text = chr((ord(plain_text)**public_exponent) % RSA_modulus)

print("  Plain Text " + plain_text + " encrypted to " + cipher_text)

 For the sake of simplicity, we are going to encrypt a single character. Please enter below a single character only. 
 Please enter the character that you would want to encrypt: M
  Plain Text M encrypted to 脐

Decryption: - original message, m = DECRYPT (cipher text, c) = c^d mod r.

#DECRYPTION
message = chr((ord(cipher_text)**private_exponent) % RSA_modulus)

print("  Cipher Text " + cipher_text + " decrypted to " + message)

  Cipher Text 脐 decrypted to M

*******************************************************************************************************************************************************
The author, Subhasish Sarkar (SS), is an IBM Z Champion for 2020.
*******************************************************************************************************************************************************