# RSAtools.py                                      David MacQuigg 13-March-2010
'''
Python is great for crypto.
  1) Easy interactive environment for prototyping and experimentation.
  2) Long integers for public keys, etc.

Run this file in Python 2.6.  Try the commands in the >>> examples.
~'''

### Random Bits
from random import getrandbits

a,b,m = getrandbits(512), getrandbits(512), getrandbits(384)  # long integers
'''
>>> a
87638194511408989261438753250719754638828743912429765499507120091357674569882808
90862859998699808605307665820696568046132523175744106743803372585080828726L
>>> b
57579891920620594921553065324099857848201813159629630310669085501543819427295796
09887603084816533251318617299467986239404540879435342090928431485352784952L
>>> m
33980144669810108281160822352744739279623941703077092883034667556498921065193304
60680842427694402677672470050075321L
'''

### Huge exponentials like a ** b (mod m) are common in crypto systems.

exp = pow(a, b, m)  # pow() is a function written in C - very fast.
'''
>>> pow(a, b, m)
26616164385017850397090293477494464399221960596510492575571803619978316656538353
42475518596170907523282061732994456L
'''

### Define functions

from simple_crypto import factors, factorial, primes, primefactors,\
                          isPrime, sieve, inverse

from Crypto.Util.number import getPrime
from random import randint

def getPrimes(n1, n2, isPrime):
    ls = []
    for n in range(n1, n2+1, 2):
        if isPrime(n):
            ls.append(n)
    return ls

n1 = getPrime(256)
n2 = getPrime(256)
n3 = n1 * n2
n4 = getPrime(512)

def sieveTest(N):
    '''Sieve test only from simple_crypto.isPrime()'''
    if N <= 1: return False
    if N in sieve: return True
    for i in sieve:
        if (N % i) == 0: return False
    return True

def mrTest(N):
    '''Miller-Rabin test only, no sieve'''
    # Miller-Rabin algorithm (Stinson p.188)
    
    # Find m,k: m*2**k = N-1, with m odd.    # N   = 111001
    m,r = N-1, 0                             # N-1 = 111000
    k = 0
    while (m & 1) == 0:                      # m & 1      0
        m,r = divmod(m, 2)                   # m,r    11100, 0
        k += 1                               # k          1

    a = randint(1, N-1)
    b = pow(a, m, N)  # a**m (mod N)
    if b == 1:
        return True
    for i in range(0, k):
        if b == N-1:  # -1 (mod N)
            return True
        b = b*b % N
        
    return False


### RSA Example (Stinson p.174)
p = 101; q = 113; n = p*q  # 11413
phi = (p-1)*(q-1)          # 11200
b = 3533                           # public key
a = inverse(b, phi)        # 6597  # private key
x = 9726                           # plaintext
y = pow(x, b, n)           # 5761  # ciphertext
z = pow(y, a, n)           # 9726  # decrypted plaintext

def keydata(p, q, e):
    '''
    Given two large primes, and a public key e, return modulus n and
    private key d.
    '''
    n = p * q
    phi = (p-1) * (q-1)  # Euler function
    d = inverse(e, phi)
    return (n, d)


from Crypto.PublicKey import RSA
# from Crypto.Util.number import getPrime, getRandomNumber, isPrime

# Generate a 512-bit key pair as a private object
keys = RSA.generate(512)  # <_RSAobj @0x754328 n(512),e,d,p,q,u,private>
# The public part
kpub = keys.publickey()   # <_RSAobj @0x745788 n(512),e>
'''
>>> keys.n
10234627198605513639397634685673808088862885727436246123175195869546876043619\
177469648169969957996459717595131085472587737664700976414283898364959753144431L
>>> keys.e
65537L
>>> kpub.n
10234627198605513639397634685673808088862885727436246123175195869546876043619\
177469648169969957996459717595131085472587737664700976414283898364959753144431L
>>> kpub.e
65537L
>>> keys.d
25064584362668186507214556159889012287143036136129476521195949418836284923033\
48455100437453295920795995642901835947770124620525487363485041044782436782273L
>>> keys.p
96742629864732603418864512406761098475238631440988147476367753084012776627793L
>>> keys.q
105792319403718559888423419116790072822332865896274893402668847153102331071167L

>>> phi = (keys.p - 1) * (keys.q - 1)
>>> phi
10234627198605513639397634685673808088862885727436246123175195869546876043618\
974934698901518794689171786071579914175016240327437935535247298127844645445472L
>>> (keys.e * keys.d) % phi
1L
>>> keys.p * keys.q
10234627198605513639397634685673808088862885727436246123175195869546876043619\
177469648169969957996459717595131085472587737664700976414283898364959753144431L
>>> n,d = keydata(keys.p, keys.q, keys.e)
>>> n
10234627198605513639397634685673808088862885727436246123175195869546876043619\
177469648169969957996459717595131085472587737664700976414283898364959753144431L
>>> d
25064584362668186507214556159889012287143036136129476521195949418836284923033\
48455100437453295920795995642901835947770124620525487363485041044782436782273L

>>> x = 12345678987654
>>> y = pow(x, keys.e, keys.n)
>>> y
30265197677604831928111872062026166837484863311372420565956699732727257718633\
08128760539488324408005664686810761373457968796412747320091540601398665932855L
>>> z = pow(y, keys.d, keys.n)
>>> z
12345678987654L
'''