You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

94 lines
2.1 KiB

Created on Dec 14, 2011
@author: pablocelayes
# -*- 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__":
for i in range(5):
e,n,d = generateKeys()
print ("Clave Publica:")
print("e =")
print("n =")
print ("Clave Privada:")
print("d =")