#!/usr/bin/env python # -*- coding: utf-8 -*- # import random def exgcd(a, b): """ Extended Euclidean algorithm Input: integers a >= b >= 0, not both equal to zero Output: triple (g,x,y) such that g = gcd(a,b) and g = a*x + b*y """ return a,1,0 def modexp(x,a,N): """ Fast modular exponentiation Input: integers x, a >= 0, N >= 2 Output: x**a mod N """ return 1 def primalitytest_single(N): """ Miller-Rabin probabilistic primality test, single round Input: integer N Output: True if possibly prime, False if N is known to be composite Never output False for a prime; Probability of output False when N is composite is at most 1/2 """ return True def primalitytest(N): """ Miller-Rabin probabilistic primality test Input: integer N Output: True if prime with high probability, False if N is known to be composite Never output False for a prime; probability of output False when N is composite is at most 2**-100 """ for j in range(100): if not primalitytest_single(N): return False return True def generateprime(bits): """ Output: Random prime between 2**bits and 2**(bits+1). There is a small (less than 2**-100) chance that the returned number is composite """ while True: N = random.randint(2**(bits-1), 2**bits-1) if primalitytest(N): return N def rsa_generate_key(bits): """ Output: (N,d,e), where N is the RSA modulus of the given number of bits, d is the private exponent, e is the public exponent """ return 15,3,3 def testgcd(): for i in range(100): a = random.randint(1,100000) b = random.randint(1,100000) if a < b: tmp = b b = a a = tmp g,x,y = exgcd(a,b) if a%g != 0 or b%g != 0: print "Error in exgcd:", g, "is not a divisor of", a, "and", b return if g != x*a + y*b: print "Error in exgcd:", g, "!=", x, "*", a, "+", y, "*", b return print "exgcd tests done" def testprimetest(): for N in range(2,10000): isprime = True for p in range(2,N): if p*p > N: break if N % p == 0: isprime = False break if primalitytest(N) != isprime: print "Error in primality test: N =", N, "isprime:", isprime return print "primalitytest tests done" def testrsa(): for i in range(10): N,d,e = rsa_generate_key(100) for j in range(20): m = random.randint(1, N-1) c = modexp(m, e, N) if m != modexp(c, d, N): print "Error in RSA test:", N, d, e, m, c return print "RSA test done" def testall(): testgcd() testprimetest() testrsa() def interactive_rsa(): print "Number of bits:", bits = input() N,d,e = rsa_generate_key(bits) print "N =", N print "d =", d print "e =", e print "Message:", m = input() c = modexp(m, e, N) print "Ciphertext:", c decr = modexp(c, d, N) print "Decrypted message:", decr def rsa_attack(N,d,e): """ One round of the attack in Exercise 6. Input: RSA private and public key Output: factor of N or None if unsuccessful """ return None def testattack(): for i in range(10): N,d,e = rsa_generate_key(128) for j in range(20): p = rsa_attack(N,d,e) if p != None: break if p == None: print "Attack was unsuccessful" else: q = N / p if N == p*q: print "Attack successful after", j+1, "rounds" else: print "Attack incorrect" if __name__ == "__main__": testall() #testattack() while True: interactive_rsa()