Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Generoidaan kaksi suurta alkulukua p ja q
- # Näiden tulo n= p * q on toinen julkinen avain
- # Avain n määrittää viestin pituuden ylärajan
- # Jos viesti on muutettu numeroiksi, pituus on numeroiden määrä
- # Toiseksi julkiseksi avaimeksi eksponentti e = 65537
- # Alkuluvun testauksessa käytetään Miller-Rabinin menetelmää,
- # joka on virheetön lukua 341550071728321 pienemmille
- # ja sitä suuremmille virheen mahdollisuus äärimmäisen pieni
- # Suuria alkulukuja käytetään julkisen avaimen salauksessa
- # Alkulukujen generoinnissa käytetty lähdettä https://inventwithpython.com/hacking/chapter23.html
- # Selväkielinen viesti salataan julkisilla avaimilla n ja e
- # Salaus puretaan privaatilla purkuavaimella d - yhdessä julkisen avaimen n kanssa
- # Alla oleva ohjelma käyttää suositeltua eksponentti e = 65537 ja luo avaimen n
- # ja laskee näistä purkuavaimen d
- # Juhani Kaukoranta 7.8.2019
- import random
- import math
- import time
- import binascii
- # *** Pääohjelman käyttämät funktiot ***
- # alkuluvun generointi käyttäen annettua bittipituutta
- def generateLargePrime(keysize):
- # Return a random prime number of keysize bits in size.
- while True:
- num = random.randrange(2**(keysize-1), 2**(keysize))
- if is_prime(num):
- return num
- # Miller-Rabin correct and probabilistic composite, prime test
- # correct answers for n less than 341550071728321
- # and then reverting to the probabilistic form
- # source https://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test#Python
- def _try_composite(a, d, n, s):
- if pow(a, d, n) == 1:
- return False
- for i in range(s):
- if pow(a, 2**i * d, n) == n-1:
- return False
- return True # n is definitely composite
- def is_prime(n, _precision_for_huge_n=16):
- # _known_lowprimes are primes < 1000
- if n in _known_lowprimes:
- return True
- if any((n % p) == 0 for p in _known_lowprimes) or n in (0, 1):
- return False
- d, s = n - 1, 0
- while not d % 2:
- d, s = d >> 1, s + 1
- # Returns exact according to http://primes.utm.edu/prove/prove2_3.html
- if n < 1373653:
- return not any(_try_composite(a, d, n, s) for a in (2, 3))
- if n < 25326001:
- return not any(_try_composite(a, d, n, s) for a in (2, 3, 5))
- if n < 118670087467:
- if n == 3215031751:
- return False
- return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7))
- if n < 2152302898747:
- return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11))
- if n < 3474749660383:
- return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13))
- if n < 341550071728321:
- return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17))
- # otherwise
- return not any(_try_composite(a, d, n, s)
- for a in _known_lowprimes[:_precision_for_huge_n])
- # lasketaan valmiiksi _known_lowprimes eli alkuluvut < 1000
- # nopeuttaa huomattavasti tarkistusta, onko luku alkuluku
- _known_lowprimes = [2, 3]
- _known_lowprimes += [x for x in range(5, 1000, 2) if is_prime(x)]
- # extended euclidean algoritm
- # ax + by = gcd(a,b)
- # used in modular inverse modinv(a,m)
- 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***
- # Luodaan kaksi alkulukua p ja q. Suositeltu eksponentti e=65537 ei saa olla
- # luvun moduli = lcm(p-1,q-1) tekijänä
- e = 65537 # sertifioitu exponentti joka toimii toisena julkisena avaimena
- print("Ohjelma generoi kaksi bittimäärältään halutunkokoista alkulukua")
- print("Näistä saadun avaimen n bittimäärä on noin 2-kertainen")
- bittipituus = int(input("Haluttu bittimäärä, esim 256, 512,1024,2048 "))
- p = generateLargePrime(bittipituus)
- q = generateLargePrime(bittipituus)
- moduli = lcm(p-1,q-1)
- while moduli % e == 0: # moduli ei saa olla jaollinen e:llä
- p = generateLargePrime(bittipituus)
- q = generateLargePrime(bittipituus)
- moduli = lcm(p-1,q-1)
- print("Alkuluku p = ",p)
- print("Alkuluku q = ",q)
- print("Alkulukujen bittipituus = ",bittipituus)
- n = p * q # julkinen avain
- print(" Julkinen avain n = ",n)
- print("Julkisen avaimen n pituus = ",len(str(n))," numeroa")
- print ("Julkisen avaimen n bittipituus = ", math.log(n,2))
- print("Eksponentti e = ",e)
- # Nyt meillä on eksponentti e ja laskettu kelvollinen n ja moduli
- # Lasketaan e:n ja modulin avulla salauksen privaatti purkuavain d
- d = modinv(e,moduli)
- print("Salauksen privaatti purkuavain d = ",d)
- print(" ")
- print(" ****** viestin kirjoitus, salaus, purku selväkieliseksi *****")
- selko_text = input("Kirjoita selväkielinen teksti: ")
- hex_text = binascii.hexlify(selko_text.encode()) # selkoteksti heksadesimaalimuodossa, 2 hex/asciimerkki
- int_text = int(hex_text,16) # selkoteksti kokonaislukuna
- if int_text > n:
- raise Exception("teksti on liian pitkä avaimelle n, jaa teksti vaikka lyhyempiin pätkiin!")
- print("Selväkielinen teksti kokonaislukuna = ",int_text)
- crypt_text = pow(int_text,e,n) # salattu teksti
- print("salattu teksti = ",crypt_text)
- avattu_inttext = pow(crypt_text,d,n)
- print("Avattu teksti kokonaislukuna = ",avattu_inttext)
- avattu_selkotext = binascii.unhexlify(hex(avattu_inttext)[2:]).decode()
- print("Avattu teksti luettavassa muodossa = ",avattu_selkotext)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement