RSA with Python

rsa.py

from secrets import randbits

class PrimeGenerator:
    def __init__(self):
        self.prevs = []
    
    def nextPrime(self):
        if len(self.prevs) == 0:
            self.prevs.append(2)
            return 2
        else:
            num = self.prevs[-1]
            isPrime = False
            while not isPrime:
                isPrime = True
                num += 1
                for prime in self.prevs:
                    if num % prime == 0:
                        isPrime = False
                        break
            self.prevs.append(num)
            return num

def areCoprime(nums):
    minItem = min(nums)
    generator = PrimeGenerator()
    nextPrime = generator.nextPrime()

    while nextPrime <= minItem:
        isFactorOfOne = False
        for coprimeCandidate in nums:
            if coprimeCandidate % nextPrime == 0:
                if not isFactorOfOne:
                    isFactorOfOne = True
                else:
                    return False
        nextPrime = generator.nextPrime()
    
    return True

def eed(num, mod):
    a, b = num, mod
    x0, x1, y0, y1 = 0, 1, 1, 0

    while a != 0:
        q = b // a
        a, b = b % a, a
        y0, y1 = y1, y0 - q * y1
        x0, x1 = x1, x0 - q * x1
    
    return (x0 + mod) % mod

def randPrime():
    x = 2 # Not a valid prime according to pow() below
    while pow(2, x-1, x) != 1:
        x = randbits(1024)
    return x

print('Generating the 1st prime...')
p = randPrime()

print('Generating the 2nd prime...')
q = randPrime()

n = p * q
fi = (p - 1) * (q - 1)

e = 65537
while not areCoprime([ e, n, fi ]):
    e += 1

d = eed(e, fi)

print(f'Public: {hex(e)}, {len(bin(e))-2} bits long')
print(f'Private: {hex(d)}, {len(bin(d))-2} bits long')
print(f'N: {hex(n)}, {len(bin(n))-2} bits long')

plaintext = 577534657
encrypted = pow(plaintext, e, n)
decrypted = pow(encrypted, d, n)

print(plaintext == decrypted)