-
Notifications
You must be signed in to change notification settings - Fork 1
/
rsa.py
64 lines (49 loc) · 2.01 KB
/
rsa.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
from secrets import SystemRandom
from random import randrange
from math import gcd
from decimal import Decimal
from miller_rabin import miller_rabin
# Public exponent e shall be 2**16 < e < 2**256. FIPS 186-4. B.3.1
E = 65537
def getprime(bits: int) -> int:
"""Generate a random bits size prime number"""
secure_randrange = SystemRandom().randrange
# Prime shall be (lowlimit < p < 2**bits-1). FIPS 186-4. B.3.1
lowlimit = int(Decimal(2**0.5) * Decimal(2**(bits - 1)))
lowlimit |= 1 # n += 1 if n is odd
highlimit = 2**bits
while True:
p = secure_randrange(lowlimit, highlimit, 2)
# (p–1) shall be relatively prime to e. FIPS 186-4. B.3.1
if gcd(E, p - 1) == 1:
if miller_rabin(p):
return p
def rsa_keys(nlen: int) -> (int, int):
"""Get public and private keys.
Method: FIPS 186-4, Appendix B.3.3.
Using these method p, q may be generated with lengths of 1024 or 1536 bits
(512 bits shall not). FIPS186-4. Appendix B.3.1. Criteria for IFC Key Pairs
"""
if nlen not in (2048, 3072):
print('Error. Use bits == 2048 or 3072')
return 0, 0
bits = nlen//2
p = getprime(bits)
while True:
q = getprime(bits)
# FIPS 186-4. B.3.1
if abs(p - q) > 2**(bits-100):
# Euler's totient function.
phi = (p - 1) * (q - 1)
# Verify that phi and e are coprime. FIPS 186-4. B.3.1
if gcd(E, phi) == 1:
n = p * q
# Private (or decryption) exponent d
d = pow(E, -1, phi)
# If phi ≤ d ≤ 2**(nlen//2), new p, q, d shall be determined.
if 2**bits < d < phi:
public_key = (E, n)
private_key = (d, n)
return public_key, private_key
if __name__ == '__main__':
print(rsa_keys(3072))