Admin: rsa

2022-09-30T14:27:01Z

rsa

Nowa strona

Algorytm RSA jest jednym z najważniejszych algorytmów związanych z bezpieczeństwem.

== Podstawy teoretyczne ==

# Funkcja Eulera: fi(n) - ilość liczb całkowitych dodatnich mniejszych od n i względnie pierwszych z n. 1.1. fi(n) = n-1, gdy n jest liczbą pierwszą (bo każda liczba jest względnie pierwsza z liczbą pierwszą). 1.2. Gdy n =p*q, gdzie p, q - liczby pierwsze, fi(n) = (p-1)*(q-1) Dowód:
#* wszystkich liczb mniejszych od n jest p*q-1
#* liczby mające z n wspólny podzielnik p: p, 2*p, 3*p, ... (q-1)*p - jest ich q-1
#* liczby mające z n wspólny podzielnik q: q, 2*q, 3*q, ... (p-1)*q - jest ich p-1
#* a więc: fi(n) = p*q - (p-1) - (q-1) -1 = p*q - p - q + 1 = (p-1) * (q-1) = fi(p)*fi(q)
# Twierdzenie Eulera: Dla każdych (a, n), takich, że gcd(a,n) = 1 mamy (a^fi(n)) mod n =1 ^ oznacza potęgowanie gcd = największy wspólny podzielnik mod = reszta z dzielenia (modulo), ale określona na liczbach dodatnich (-1 mod 10 = 9 !!!). Dowód:
#* R = {r1, r2,... rfi(n) } - zbiór liczb całkowitych dodatnich, mniejszych od n i względnie pierwszych z n (residuów) (zob. Funkcję Eulera)
#* jeśli każdą z liczb ri pomnożymy przez a modulo n ( (ri * a) mod n ), otrzymamy fi(n) różnych wyników; gdyby bowiem zachodziło: ri * a mod n = rj * a mod n = r, mielibyśmy (ri-rj)*a mod n =0, a więc a i n nie byłyby względnie pierwsze.
#* mamy więc (a*r1)*(a*r2)*....*(a*rfi(n)) = r1*r2*...*rfi(n) czyli (a^fi(n) mod n) * r1*r2*...*rfi(n) = r1*r2*...*rfi(n) a po uproszczeniu a^fi(n) mod n = 1
# Szyfr wykładniczy polega na szyfrowaniu poprzez potęgowanie modulo n. C = M^e mod n Odszyfrowanie można wykonać poprzez potęgowanie używając innego wykładnika (klucza)!: M=C^d mod n Powyższe równania są swoją odwrotnością (czyli pomnożenie ich daje w wyniku 1, albo inaczej (M^e mod n) ^d mod n = M), pod warunkiem, że e*d mod fi(n) = 1 Dowód:
#* (M^e mod n) ^d mod n = M^(e*d) mod n
#* ale:e*d = t * fi(n) +1
#* mamy więc M^e*d mod n = M^(t*fi(n)+1) mod n = M*M^(t*fi(n) mod n = M* (M^(t*fi(n)) mod n) mod n
#* na mocy twierdzenia Eulera mamy M^(t*fi(n)) mod n = ((M^fi(n) mod n)^t) mod n = 1^t mod n = 1
#* a więc M^(e*d) mod n = (M*1) mod n = M
# Generowanie kluczy:
#* wybieramy d względnie pierwsze z fi(n)
#* obliczamy e = inv(d, fi(n)) gdzie inv = odwrotność, czyli (x * inv(x, fi(n)) ) mod fi(n)=1

Najprostsza implementacja (Python):<syntaxhighlight lang="py3">
import numpy as np
import primesieve
from random import randint

def gen_prime(min, max):
"""
Eratosthenes sieve http://code.activestate.com/recipes/117119/
https://github.com/hickford/primesieve-python
"""
prime_list = primesieve.primes(min, max)
while (not prime_list):
min=max
max+=100
prime_list = generate_primes(min, max)
n=randint(0, len(prime_list)-1)
return prime_list[n]

# The greatest common divisor (GCD) - Euclides
def gcd(x, y):
while y != 0:
(x, y) = (y, x % y)
return x

# result == x: a*x mod n == 1, 0 < a < n
# extended Euclides
# https://anh.cs.luc.edu/331/notes/xgcd.pdf
def inv(a,n):
v0 = 0
v1 = 1
r0=n
r1=a
while r1 != 0:
d = r0 // r1
(r0, r1) = r1, r0 - d * r1
(v0, v1) = v1, v0 - d * v1
if v0>0:
return v0
else:
return v0+n

def rsa_keys(p, q): # p<q
# return: d, e, p * q
n=p*q
fi=(q-1)*(p-1)
# wybieramy d wzglednie pierwsze wzgledem fi z przedzialu [q + 1 .. n-1]
d=q+1
wd=-1
while (wd != 1 ) and (d<n):
wd=gcd(d, fi)
if wd != 1:
d+=1
if wd != 1:
print('nie znaleziono kluczy')
exit(-1)
e = inv(d, fi)
return (d, e, n)

def rsa(M, d, n):
return (M ** d) % n

if __name__=="__main__":
# przykładowe dane startowe
min=779
d=88
# liczby pierwsze
p=gen_prime(min,min+d)
q=gen_prime(p,p+d)
# klucze
d, e, n = rsa_keys(p, q)
print ('d=%s, e=%s, n=%s' % (d, e, n))
# test
M=input('Liczba=')
Mcrypt=rsa(M,d,n)
print("zaszyfrowana=%s" % Mcrypt)
print("odszyfrowana=%s" % rsa(Mcrypt,e,n))
</syntaxhighlight>Ta implementacja nie nadaje się do praktycznego zastosowania, gdyż program działa zbyt wolno, a przy generowaniu kluczy nie są sprawdzane dodatkowe wymogi odpowiedniej złożoności. Powyższy program służy jedynie do zilustrowania algorytmu. W praktyce stosuje się gotowe biblioteki takie jak OpenSSL.

RSA - Historia wersji

Admin: rsa