In [1]:

    

import math
import random
import timeit


    

In [2]:

    

def euclideEsteso(a, b):
    x0, x1, y0, y1 = 1, 0, 0, 1
    bStart = b
    while b != 0:
        quotient = a // b
        a, b = b, a % b
        x0, x1 = x1, x0 - quotient * x1
        y0, y1 = y1, y0 - quotient * y1
    return (a, x0, y0) if a != 1 else (a, x0, y0, x0 % bStart)


    

In [3]:

    

euclideEsteso(5, 11)


    

    
Out[3]:





(1, -2, 1, 9)

In [51]:

    

euclideEsteso(12, 28)


    

    
Out[51]:





(4, -2, 1)

In [58]:

    

def expVeloce(a, n, m):
    d = 1
    binN = "{0:b}".format(n)
    for i in binN:
        d = (d * d) % m
        if i == '1':
            d = (d * a) % m
    return d


    

In [59]:

    

expVeloce(3, 11, 10)


    

    
Out[59]:





7

In [72]:

    

def rabinTest(x, n):
    m = n - 1
    r = 0
    while m % 2 == 0:
        m //= 2
        r += 1
    xr = expVeloce(x, m, n)
    if xr == 1 or xr == n - 1:
        return False
    for i in range(r):
        xr = expVeloce(xr, 2, n)
        if xr == n - 1:
            return False
    return True

def rabinTestSample(x, n):
    m = n - 1
    r = 0
    while m % 2 == 0:
        m //= 2
        r += 1
    xr = expVeloce(x, m, n)
    if xr == 1 or xr == n - 1:
        print 'x0 ', xr
        return False
    print 'x0 ', xr
    for i in range(r):
        xr = expVeloce(xr, 2, n)
        print 'x' + str(i + 1), '', xr
        if xr == n - 1:
            return False
    return True


    

In [76]:

    

rabinTestSample(2, 41)


    

    




x0  32
x1  40






    
Out[76]:





False

In [144]:

    

def isPrime(r, k):
    for i in range(k):
        baton = random.randint(1, r)
        if rabinTest(baton, r) is True:
            return False
    return True


def generatePrime(bottom, top, k):
    r = random.randint(bottom, top)
    while r % 2 == 0 or not isPrime(r, k):
        r = random.randint(bottom, top)
    return r


    

In [145]:

    

prime = generatePrime(pow(10, 1), pow(10, 2), 8)
print prime
print 'cifre', len(str(prime))


    

    




89
cifre 2

In [148]:

    

def wrapper():
    return generatePrime(10**100, (10**(100 + 1)), 16)
    
print "Tempo impiegato ",(timeit.timeit(wrapper, number=1))


    

    




Tempo impiegato  0.0601627826691

In [84]:

    

def encrypt(m, keyPub):
    e = keyPub[0]
    n = keyPub[1]
    return expVeloce(m, e, n)


def decrypt(c, keyPriv):
    d = keyPriv[0]
    n = keyPriv[1]
    return expVeloce(c, d, n)


def coPrime(n):
    c = 2
    while euclideEsteso(c, n)[0] != 1 or euclideEsteso(c, n)[1] < 1:
        c += 1 
    return c


def generateKey(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    d = coPrime(phi)
    e = euclideEsteso(d, phi)[1]
    kPub = (e, n)
    kPriv = (d, n)
    return kPub, kPriv


    

In [86]:

    

public_key, private_key = generateKey(3, 11)
print "Chiave pubblica",public_key
print "Chiave privata",private_key
print "Cyphertext", encrypt(8, public_key)
print "Plaintext", decrypt(encrypt(8, public_key), private_key)


    

    




Chiave pubblica (7, 33)
Chiave privata (3, 33)
Cyphertext 2
Plaintext 8

In [85]:

    

def generateKeyCrt(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    d = coPrime(phi)
    e = euclideEsteso(d, phi)[1]
    invPmodQ = euclideEsteso(q, p)[3]
    invQmodP = euclideEsteso(p, q)[3]
    kPub = (e, n)
    kPriv = (d, p, q, invPmodQ*q, invQmodP*p, n)
    return kPub, kPriv


def decryptCrt(c, keyPriv):
    mP = expVeloce(c, keyPriv[0], keyPriv[1])
    mQ = expVeloce(c, keyPriv[0], keyPriv[2])
    return ((mP*keyPriv[3]) + (mQ*keyPriv[4])) % keyPriv[5]


    

In [87]:

    

public_key, private_key = generateKeyCrt(3, 11)
print "Chiave pubblica",public_key
print "Chiave privata",private_key
encr = encrypt(8, public_key)
print(encr)
print(decryptCrt(encr, private_key))


    

    




Chiave pubblica (7, 33)
Chiave privata (3, 3, 11, 22, 12, 33)
2
8

In [27]:

    

def testRsa(listC, keyPriv):
    return [decrypt(listC[i], keyPriv) for i in range(sampleSize)]
        
def testRsaCrt(listC, keyPrivCrt):
    return [decryptCrt(listC[i], keyPrivCrt) for i in range(sampleSize)]


    

In [138]:

    

sampleSize = 100
primeC = 512

p = generatePrime(10**primeC, (10**(primeC + 1)), 2)
print 'p generato'
q = generatePrime(10**primeC, (10**(primeC + 1)), 2)
print 'q generato'
n = p * q
phi = (p - 1) * (q - 1)
d = coPrime(phi)
keyPub, keyPriv = generateKey(p, q)
keyPubCrt, keyPrivCrt = generateKeyCrt(p, q)
listPlaintext  = [random.randint(1, 10) for _ in range(sampleSize)]
listCiphertext = [encrypt(listPlaintext[i], keyPub) for i in range(sampleSize)]

print "Tempi rsa standard"
resultStandard = testRsa(listCiphertext, keyPriv)
testTimeStandard = %%timeit -n1 -r100 -o testRsa(listCiphertext, keyPriv)

print "Tempi rsa crt"
resultCrt = testRsaCrt(listCiphertext, keyPrivCrt)
testTimeCrt = %%timeit -n1 -r100 -o testRsaCrt(listCiphertext, keyPrivCrt)

print "Tutti i decrypt sono uguali ai plain di partenza?", resultCrt == resultStandard == listPlaintext


    

    




p generato
q generato
Tempi rsa standard
1 loop, best of 100: 7.3 ms per loop
Tempi rsa crt
1 loop, best of 100: 6.92 ms per loop
Tutti i decrypt sono uguali ai plain di partenza? True

In [136]:

    

def percent(time1, time2):
    return ((time1 / time2)-1)*100
mediaStandard = sum(testTimeStandard.all_runs) / testTimeStandard.repeat
mediaCrt = sum(testTimeCrt.all_runs) / testTimeCrt.repeat
print percent(mediaStandard, mediaCrt), "%"


    

    




16.4245900237 %

In [ ]: