RSA

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

Podstawy teoretyczne

1. 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)
2. 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
3. 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
4. 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):

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))

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.