RSAPrivatKeyComputing.py

# RSA salauksen murtaminen onnistuu, kun ensin
# lasketaan julkisen kokonaislukuavaimen n tulontekijät p ja q
# Sitten alkulukujen p ja q sekä julkisen eksponentin e avulla
# lasketaan privaatti purkuavain d
# Edellytyksenä on, että julkinen avain n on tarpeeksi lyhyt
# jolloin sen alkulukutekijät voidaan laskea

# Juhani Kaukoranta 8.8.2019
import math
import time
# numba-kääntä & njit nopeuttaa laskentaa 10-kertaiseksi
# jolloin risuaidat numban ja njit edestä pois
# pienillä avaimilla < 32 bit ei hyötyä
# suurilla avaimilla laskenta-aika kasvaa todella suureksi
#from numba import njit

# Avaimen n factorointi
#@njit
def factor(n):
    for x in range(3, int(math.sqrt(n)) + 1,2):
        if n % x == 0:
            p = x
            q = n // x
            factors = [p,q]
    		return factors

# apufunktio extended euclidean algoritm
# ax + by = gcd(a,b)
# käytetään  modular inverse modinv(a,m)-funktiossa
def extended_gcd(aa, bb):
    lastremainder, remainder = abs(aa), abs(bb)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
        x, lastx = lastx - quotient*x, x
        y, lasty = lasty - quotient*y, y
    return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

# least common multiple tarvitaan privaatin purkuavaimen d laskemiseen
def lcm(x, y):
   return x*y // math.gcd(x,y)

# modular inverse tarvitaan privaatin purkuavaimen d laskemiseen
def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise ValueError
    return x % m

# *** Pääohjelma ***
e = 65537     # julkinen suositeltu eksponentti
n = int(input("Anna julkinen salausavain n: "))
time0 = time.perf_counter() # timer begin
[p,q] = factor(n)
print("Avaimen n alkulukutekijät = ",[p,q])
time1 = time.perf_counter() # timer stop
print("Aikaa kului ",time1 - time0," sekuntia")
print("p = ",p)
print("q = ",q)
print("Tarkistus p * q = ",p,"*",q," = ",p*q)

# Saatujen alkulukujen p ja q sekä eksponentin avulla
moduli = lcm(p-1,q-1)  # "Carmichaelin totientti"
d = modinv(e,moduli)  # purkuavain d
print("Privaatti purkuavain d = ",d)
# Avaimet
print("Julkinen avain n = ",n)
print("Julkinen eksponentti e = ",e)
print("Privaatti purkuavain d = ",d)