-
Notifications
You must be signed in to change notification settings - Fork 125
/
RSAvulnerableKeyGenerator.py
94 lines (74 loc) · 2.11 KB
/
RSAvulnerableKeyGenerator.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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
'''
Created on Dec 14, 2011
@author: pablocelayes
'''
#!/usr/bin/python
# -*- coding: utf-8 -*-
"""\
This module generates RSA-keys which are vulnerable to
the Wiener continued fraction attack
(see RSAfracCont.pdf)
The RSA keys are obtained as follows:
1. Choose two prime numbers p and q
2. Compute n=pq
3. Compute phi(n)=(p-1)(q-1)
4. Choose e coprime to phi(n) such that gcd(e,n)=1
5. Compute d = e^(-1) mod (phi(n))
6. e is the publickey; n is also made public (determines the block size); d is the privatekey
Encryption is as follows:
1. Size of data to be encrypted must be less than n
2. ciphertext=pow(plaintext,publickey,n)
Decryption is as follows:
1. Size of data to be decrypted must be less than n
2. plaintext=pow(ciphertext,privatekey,n)
-------------------------------
RSA-keys are Wiener-vulnerable if d < (n^(1/4))/sqrt(6)
"""
import random, MillerRabin, Arithmetic
def getPrimePair(bits=512):
'''
genera un par de primos p , q con
p de nbits y
p < q < 2p
'''
assert bits%4==0
p = MillerRabin.gen_prime(bits)
q = MillerRabin.gen_prime_range(p+1, 2*p)
return p,q
def generateKeys(nbits=1024):
'''
Generates a key pair
public = (e,n)
private = d
such that
n is nbits long
(e,n) is vulnerable to the Wiener Continued Fraction Attack
'''
# nbits >= 1024 is recommended
assert nbits%4==0
p,q = getPrimePair(nbits//2)
n = p*q
phi = Arithmetic.totient(p, q)
# generate a d such that:
# (d,n) = 1
# 36d^4 < n
good_d = False
while not good_d:
d = random.getrandbits(nbits//4)
if (Arithmetic.gcd(d,phi) == 1 and 36*pow(d,4) < n):
good_d = True
e = Arithmetic.modInverse(d,phi)
return e,n,d
if __name__ == "__main__":
print("hey")
for i in range(5):
e,n,d = generateKeys()
print ("Clave Publica:")
print("e =")
print(e)
print("n =")
print(n)
print ("Clave Privada:")
print("d =")
print(d)
print("-----------------------")