Question

IN PYTHON

1. Generate valid keys (e, n) for the RSA cryptosystem.
2. Use the sieve of Eratosthenes to find all primes less than 10,000.
3. Find all of the positive divisors of a positive integer from its prime factorization.

Answer 1

1. The solution as per the requirement is given in the code snippet block below:

# Module Cryptomath:
def gcd(a, b):
    while a != 0:
        a, b = b % a, a
    return b

def findModInverse(a, m):
    if gcd(a, m) != 1:
        return None
    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, m

    while v3 != 0:
        q = u3 // v3
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
    return u1 % m
# ------------------------------------------------------------------------------------------------
# Module rabinMiller
import random
def rabinMiller(num):
   s = num - 1
   t = 0
   
   while s % 2 == 0:
      s = s // 2
      t += 1
   for trials in range(5):
      a = random.randrange(2, num - 1)
      v = pow(a, s, num)
      if v != 1:
         i = 0
         while v != (num - 1):
            if i == t - 1:
               return False
            else:
               i = i + 1
               v = (v ** 2) % num
      return True

def isPrime(num):
    if (num < 2):
        return False
    lowPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,317, 331, 337, 347, 349, 
        353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 
        797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
        
    if num in lowPrimes:
        return True
    for prime in lowPrimes:
        if (num % prime == 0):
            return False
    return rabinMiller(num)
def generateLargePrime(keysize = 1024):
    while True:
        num = random.randrange(2**(keysize-1), 2**(keysize))
        if isPrime(num):
            return num

# ------------------------------------------------------------------------------------------------

import random, sys, os, rabinMiller, cryptomath

def generateKey(keySize):
    # Step 1: Create two prime numbers, p and q. Calculate n = p * q.
    print('Generating p prime...')
    p = rabinMiller.generateLargePrime(keySize)
    print('Generating q prime...')
    q = rabinMiller.generateLargePrime(keySize)
    n = p * q
        
    # Step 2: Create a number e that is relatively prime to (p-1)*(q-1).
    print('Generating e that is relatively prime to (p-1)*(q-1)...')
    while True:
        e = random.randrange(2 ** (keySize - 1), 2 ** (keySize))
        if cryptomath.gcd(e, (p - 1) * (q - 1)) == 1:
            break
   
    # Step 3: Calculate d, the mod inverse of e.
    print('Calculating d that is mod inverse of e...')
    d = cryptomath.findModInverse(e, (p - 1) * (q - 1))
    publicKey = (n, e)
    privateKey = (n, d)
    print('Public key:', publicKey)
    print('Private key:', privateKey)
    return (publicKey, privateKey)

2. The sieve of Eratosthenes to find all primes less than 10,000. In the code snippet given below, we have enabled the user to input the number upto which the prime numbers are to be found. The output attached has the value of n = 30.

# Python program to print all primes smaller than or equal to 
# n using Sieve of Eratosthenes 
  
def SieveOfEratosthenes(n): 
      
    # Create a boolean array "prime[0..n]" and initialize 
    #  all entries it as true. A value in prime[i] will 
    # finally be false if i is Not a prime, else true. 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n):  
        # If prime[p] is not changed, then it is a prime 
        if (prime[p] == True): 
            # Update all multiples of p 
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1

    # Print all prime numbers 
    for p in range(2, n+1): 
        if prime[p]: 
            print(p, end = " ") 
  
# driver program 
if __name__=='__main__': 
    n = int(input())   # change this and type 10000 to get your desired output
    print("Following are the prime numbers smaller than or equal to", n)
    SieveOfEratosthenes(n) 

Output:

3. Python program to find all of the positive divisors of a positive integer from its prime factorization:

# Recursive function to generate all the  
# divisors from the prime factors  
def generateDivisors(curIndex, curDivisor, arr): 
      
    # Base case i.e. we do not have more  
    # primeFactors to include  
    if (curIndex == len(arr)): 
        print(curDivisor, end = ' ') 
        return
      
    for i in range(arr[curIndex][0] + 1): 
        generateDivisors(curIndex + 1, curDivisor, arr)  
        curDivisor *= arr[curIndex][1] 
      
# Function to find the divisors of n  
def findDivisors(n): 
      
    # To store the prime factors along  
    # with their highest power  
    arr = [] 
      
    # Finding prime factorization of n  
    i = 2
    while(i * i <= n): 
        if (n % i == 0): 
            count = 0
            while (n % i == 0): 
                n //= i  
                count += 1
                  
            # For every prime factor we are storing  
            # count of it's occurenceand itself.  
            arr.append([count, i])  
      
    # If n is prime  
    if (n > 1): 
        arr.append([1, n])  
      
    curIndex = 0
    curDivisor = 1
      
    # Generate all the divisors  
    generateDivisors(curIndex, curDivisor, arr)  
  
# Driver code  
n = int(input("Enter the positive number: "))
findDivisors(n)  

Output: