import random
import math

# Euclid's Algorithm. Returns the GCD of a and b.
def Euclid(a, b):
  while b:
    (a, b) = (b, a % b)
  return a

#Euclid's Extended Algorithm. Returns d, the gcd of
#a and b, as well as ud and vd, where
#        d = ud * a + vd * b
def EuclidExtended(a,b):
    c,d = a,b
    uc, vc, ud, vd = 1,0,0,1

    while c:
        q = d//c
        c,d = (d-q*c),c
        uc, vc, ud, vd = (ud-q*uc), (vd-q*vc), uc, vc
        
    return d, ud, vd

# Primality checking using the Sieve of Erastosthenes.
def IsPrime(n):
    if n == 2:
        return True
    if n % 2 == 0 or n <= 1:
        return False

    sqr = int(math.sqrt(n)) + 1

    for divisor in range(3, sqr, 2):
        if n % divisor == 0:
            return False
    return True

#Generates RSA prime number by randomly generating a number between the defined range
#and outputting whether the random number is a prime doing multiple checks

def GenerateRSAPrime(k):
    for r in range(1,101):
        n= random.randrange(pow(2,(k-1)),pow(2,k)-1)
        if (n % 3!=1) and (n % 5!=1) and IsPrime(n)==True:
            return n
    return n

#Generates RSA key by generating two prime numbers and then finding the lcm and then
#then using the extended algorithm to generate a key.
def GenerateRSAKey(k):
    p=int(GenerateRSAPrime(int(k/2)))
    q=int(GenerateRSAPrime(int(k/2)))
    t= ((p-1)*(q-1))/Euclid(p-1,q-1)
    t = int(t)
    g,u,v = EuclidExtended(3,t)
    if g != 1:
        print('ERROR GCD DOES NOT EQUAL 1')
        return 0,0,0,0,0
    d3= u%t
    g,u,v = EuclidExtended(5,t)
    if g != 1:
        print('ERROR GCD DOES NOT EQUAL 1')
        return 0,0,0,0,0
    d5=u%t
    return p,q,p*q,d3,d5

#Main function asks user for the bitsize and terminates if the bitsize is not of the
#correct length and then outputs all values generated by the RSA key.
def main():
    print('RSA modulos Bitsize')
    bitsize = int(input('pick a number between 64 and 128: '))
    if bitsize<64 or bitsize>128:
        print('ERROR BITSIZE NOT IN RANGE')
        return 0
    p,q,n,d3,d5 = GenerateRSAKey(bitsize)
    print ('p = ',p)
    print ('q = ',q)
    print ('n = ',n)
    print ('d3 =',d3)
    print ('d5 =',d5)
    

main()
    
    
