52 lines
1.5 KiB
Python
Executable File
52 lines
1.5 KiB
Python
Executable File
#!/usr/bin/python
|
|
import math
|
|
|
|
from functions import primality_test
|
|
from functions import extended_gcd
|
|
from Cryptodome.Random.random import getrandbits
|
|
|
|
|
|
def generate() -> tuple[int, int, int]:
|
|
# Step 1: Find two large prime number p and q such that their produce has length of at least 1024 bits.
|
|
p = None
|
|
q = None
|
|
|
|
# p*q will certainly be at least 1024 bits long if p and q are at least 1024 bits long each.
|
|
while p == None:
|
|
num_bits = 2048
|
|
random_number = getrandbits(num_bits - 1) | (1 << (num_bits - 1)) # Generate 2047 random bits and add an additional 1-bit to the left to create a random 2048-bit integer
|
|
if random_number >= 2**1023 and primality_test(random_number):
|
|
p = random_number
|
|
|
|
while q == None:
|
|
num_bits = 2048
|
|
random_number = getrandbits(num_bits - 1) | (1 << (num_bits - 1))
|
|
if random_number >= 2**1023 and primality_test(random_number) and p != random_number:
|
|
q = random_number
|
|
|
|
# Step 2: Compute n = p * q
|
|
n = p * q
|
|
|
|
# Step 3: Compute λ(n)
|
|
delta_n = math.lcm(p - 1, q - 1)
|
|
|
|
# Step 4: Choose an integer e such that 1 < e < λ(n) and gcd(e, λ(n)) = 1; that is, e and λ(n) are coprime.
|
|
e = 65537
|
|
|
|
# Step 5: Determine d as d ≡ e^(-1)(mod λ(n)); that is, d is the modular multiplicative inverse of e modulo λ(n).
|
|
_, x, _ = extended_gcd(e, delta_n)
|
|
d = x % delta_n
|
|
|
|
return (n, e, d)
|
|
|
|
|
|
def main():
|
|
(n, e, d) = generate()
|
|
print(f'n: {n}')
|
|
print(f'e: {e}')
|
|
print(f'd: {d}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
main()
|