SYSTEMY SZYFROWANIA Z KLUCZEM JAWNYM

Konwencjonalnie - szyfrowanie i deszyfrowanie to ten sam klucz(hasło)

Można inaczej szyfrowanie-- pierwszy klucz(A), deszyfrowanie inny B=B(A)

Co to daje

1. Nie można „obliczyć” klucza deszyfrującego znając jedynie klucz A i algorytm szyfrujący

2. Są algorytmy, dla których każdy ze związanych ze sobą kluczy A i B można użyć do szyfrowanie i deszyfrowania

1. SYSTEMY KOŃCOWE GENERUJĄ PARĘ KLUCZY DO SZYFROWANIA I DESZYFROWANIA

2. KAŻDY SYSTEM UDOSTĘPNIA, PUBLIKUJE SWÓJ KLUCZ SZYFRUJĄCY, JEST TO KLUCZ JAWNY. DRUGI KLUCZ JEST PRYWATNY

3. JEŻELI A WSYLA TO SZYFRUJE DANE KLUCZEM JAWNYM ODBIORCY B

4. ODBIORCA B DESZYFRUJE DANE ZA POMOCĄ SWEGO KLUCZA PRYWATNEGO. TYLKO ON MOŻE TO WYKONAĆ.

Taki sposób posługiwania się kluczami zapewnia poufność. Kryptoanalityk musi wygenerować bardzo wiele hipotetycznych kluczy prywatnych B aby rozszyfrować dane.

Jeśli użyjemy algorytmu umożliwiającego przestawianie kluczy to możemy zrealizować funkcję uwierzytelnienia. A swój komunikat szyfruje go za pomocą swego klucza prywatnego i przesyła go do B, ten zaś odszyfrowuje go za pomocą klucza jawnego pochodzącego od A. Odbiorca B ma pewność, że tylko A mógł wysłać komunikat. Nikt po drodze nie może przechwycić komunikatu w celu jego podmiany bo nie zna klucza prywatnego nadawcy A. Ale każdy, kto ma dostęp do bazy z kluczem publicznym nadawcy A może łatwo odszyfrować tekst czyli nie jest to poufne.

Należy zastosować podwójne szyfrowanie

• Nadawca szyfruje komunikat za pomocą swojego klucza prywatnego.

• Nadawca szyfruje otrzymany wynik drugi raz za pomocą klucza jawnego odbiorcy

• Otrzymane dane może odszyfrować tylko B swoim kluczem prywatnym czyli jest zapewniona poufność bo wiadomość jest tylko dla niego.

• Jawny tekst otrzyma stosując klucz publiczny nadawcy.

Ale aż 4 razy trzeba stosować algorytm szyfrowania.

Wymagania dla algorytmów szyfrująco / deszyfrujących z wykorzystaniem kluczy prywatnych i publicznych są wysokie. Na dziś powszechnie akceptowalny jest algorytm RSA (system Rivesta-Shamira-Adlemana)

*******************************************************************

Przedstawione poniżej algorytmy szyfrowania danych są szyframi blokowymi.

Omówione zostaną:

1)z grupy szyfrów wykładniczych szyfr Pohliga-Hallmana

2)z grupy szyfrów wykładniczych szyfr RSA(Rivest-Shamir-Adleman)

W grupie szyfrów wykładniczych i plecakowych w celu zrozumienia zasad szyfrowania i ewentualnej próby złamania szyfru należy wprowadzić niezbędne definicje i twierdzenia z zakresu teorii liczb.

Wstęp do arytmetyka modularnej:

Definicja1:

Dwie liczby całkowite a i b przystają do siebie według modułu n tzn.

a_{nb ,}

gdzie n jest liczbą całkowitą różną od 0 wtedy i tylko wtedy, gdy istnieje

liczba całkowita k, dla której:

a-b = kn.

Np. 17₅7, ponieważ 17-7 =2*5. tą liczbą k jest 2

Wówczas dla a_nb, b jest nazywane residuum a modulo n.

Definicja2:

Zbiór liczb całkowitych (r_1,...,rn) nazywamy zbiorem zupełnym residuów modulo n, jeśli dla każdej liczby całkowitej a istnieje w tym zbiorze dokładnie jeden element r_i, dla którego zachodzi a _nri

Można zauważyć, że dla dowolnego modulo n zbiór liczb (0,1,....,n-1) stanowi zbiór zupełny residuów modulo n.

W arytmetyce modularnej liczb całkowitych modulo n obowiązują te same prawa łączności, rozdzielności i przemienności działań co w arytmetyce liczb całkowitych.

Twierdzenie1

Niech a1 i a2 będą liczbami całkowitymi ,zaś op jest operatorem: +,-, lub *. Wtedy:

(a1 op a2) mod n= [(a1 mod n) op (a2 mod n)] mod n.

Czyli prawdziwe są działania:

(a1 +a2) mod n=[(a1 mod n) +(a2 mod n)] mod n

i

(a1*a2) mod n=[(a1 mod n) * (a2 mod n)] mod n

oraz co najważniejsze możliwe jest skuteczne potęgowanie to znaczy że:

gdzie 0  t  n-1

Kolejne mnożenia modulo n zmniejszają wielkość pośrednich wyników. W praktyce dla k-bitowej liczby n to znaczy takiej ze 2^k-1 n < 2^k wynik odejmowania, dodawania lub mnożenia nie przekroczy długości 2k bitów. To oznacza wykonywanie operacji potęgowania modulo n bez konieczności rezerwowania zbyt dużej pamięci na wyniki pośrednie.

Dowód twierdzenia 1:

niech a1=k1*n+r1 oraz a2=k2*n+r2 wtedy:

(a1+ a2) mod n= [(k1*n+r1)+(k2*n+r2)] mod n=

[((k1+k2)*n +(r1+r2)]mod n= (r1+r2) mod n=

[(a1 mod n)+(a2 mod n)] mod n.

Poniżej podano przykładową funkcję w C szybkiego potęgowania liczb mod n

long int fastexp(long a, long z, long n)

{

 long z1=z;
 long x=1;
 long a1=a;
 while (z1)
{
 while(!(z1%2))
 {
  z1=(int)(z1/2);
  a1=((int)(a1*a1)) % n;
 }
 z1-=1;
 x=((int)(x*a1)) % n;
}
return(x);
}

Bardzo ważnym zagadnieniem w arytmetyce modularnej jest obliczanie odwrotności iloczynowych modulo n. Np. liczby 3 i 7 są odwrotnościami mod 10 ponieważ:

3*7 mod 10 =1
 
 

Twierdzenie 2

Można dowieść że dla równania : ax mod n = 1 jeśli tylko gcd(a,n)=1 (greatest common divisor) to znaczy: że liczby a i n są liczbami wzajemnie pierwszymi, to istnieje pewna liczba 0< x < n, która jest odwrotnością liczby a modulo n.

Twierdzenie powyższe jedynie stwierdza możliwość istnienia odwrotności liczby, ale nie określa sposobu wyliczenia tejże odwrotności. W tym celu wprowadźmy pewne dodatkowe definicje:

Definicja3:

Zbiorem zredukowanym residuów mod n nazywamy podzbiór residuów {0,1,...,n-1} względnie pierwszych z n

Na przykład zbiorem zredukowanym residuów mod 10 jest zbiór {1,3,7,9}

Uwaga do definicji 3:

Jeśli n jest liczbą pierwszą, to zredukowany zbiór jest równoważny zbiorowi zupełnemu residuów o elementach {1,...,n-1}, z wyłączeniem zera!

Definicja4:

Funkcja Eulera (n) określa liczbę elementów w zredukowanym zbiorze residuów modulo n, czyli (n) jest liczbą całkowitych liczb dodatnich mniejszych od n i względnie pierwszych z n.

Na przykład (  , a (  , czyli funkcja Eulera dla n=11 wynosi n-1, ponieważ wszystkie elementy zbioru residuum zupełnego są względnie pierwsze względem 11.

Twierdzenie 3

Dla pewnej liczby n będącej iloczynem liczb pierwszych p i q zachodzi zależność: (n = (p * (q =(p-1) *(q-1)

Na przykład: ( = ( * ( = (7-1)*(3-1) =12, czyli występuje 12 elementów w granicach {1,...,21-1} względnie pierwszych z 21.

Twierdzenie4

Niech dana będzie liczba pierwsza p, wtedy dla każdej liczby a względnie pierwszej z p tj. gcd(a,p)=1 zachodzi równość:

a ^p-1mod p =1

Z uogólnienia Eulera wynika, że rozwiązanie równości:

ax mod n =1 ma postać:

x=a ^(n)-1 mod n

Uwaga do rozwiązania powyższej równości:

Jeśli liczba n jest liczbą pierwszą to obliczenie odwrotności liczby a upraszcza się

do postaci:

x=a^n-2 mod n

Przykład:

dla a=3, n=7, czyli dla równania: 3x mod 7=1 otrzymujemy rozwiązanie:

x=3⁵ mod 7 co równa się 5

ponieważ: 3*5 mod 7 =1.

Uwaga:

Do obliczania odwrotności x w stosunku do liczby a modulo n, jeśli tylko znana jest wartość funkcji Eulera (n), można się posłużyć przytoczoną powyżej funkcją szybkiego potęgowania, fastexp(a,z,n), która zwraca wartość określoną wzorem:

a^z mod n

Inny sposób obliczania odwrotności x liczby a modulo n polega zastosowaniu rozszerzonego algorytmu Euklidesa do obliczania gcd(największego wspólnego podzielnika). W przykładzie podano funkcję liczącą według algorytmu Euklidesa gcd dwóch liczb całkowitych a i n.

long gcd(long a, long n)

{
 long g0=n;
 long g1=a;
 long g2;
 long i=1;
while(g1)
{
 g2=g0 % g1;
 g0=g1;
 g1=g2;
 i++;
}
return(g0);
}

Do obliczania odwrotności liczby a modulo n przydałby się rozszerzony algorytm Euklidesa:

Program nr.3

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
long inv(long a, long n)
{
long g0=n;
long g1=a;
long g2;
long u0=1;
long u1=0;
long u2;
long v0=0;
long v1=1;
long v2;
long i=1;
long y;
while(g1)
{
 y=(int)(g0/g1);
 g2=g0-(int)(y*g1);
 u2=u0-(int)(y*u1);
 v2=v0-(int)(y*v1);
 g0=g1;
 g1=g2;
 u0=u1;
 u1=u2;
 v0=v1;
 v1=v2;
 i++;
}
if(v0>=0)
 return(v0);
else
 return(v0+n);
}

Przeciętna liczba dzieleń wykonywanych w tym algorytmie została oszacowana przez Knutha na około (0,843 ln n + 1,47).

Oczywiście omawiany algorytm można rozszerzyć, w celu obliczania liczby x z bardziej ogólnego równania:

ax mod n =b , gdzie a i n spełniają równanie gcd(a,n)=1

W tym celu:

1)należy obliczyć x_o z równania axo mod n = 1

2)po przekształceniu tego powyższego równania otrzymamy:

abx_o mod n =1 skąd :

x=bx_o mod n

Do obliczenia liczby x może posłużyć zdefiniowane wcześniej funkcje w postaci wyrażenia dla nieznanej funkcji Eulera:

x=(b*inv(a,n)) mod n

lub też dla znanej funkcji Eulera:

x=(b*fastexp(a, (n) -1,n)) mod n

Szyfry potęgowe:

Obydwa szyfry potęgowe, które zostaną tutaj omówione realizują szyfrowanie bloku tekstu jawnego M od długości co najmniej 200 bitów.

1)Szyfr Pohliga-Hallmana realizuje szyfrowanie w następujący sposób:

(1) C=M^emod n, gdzie:

M (message)- oznacza tekst jawny

C - oznacza tekst zaszyfrowany

e - pewien wykładnik wynikający z uogólnienia Eulera

n - pewna duża liczba, której wybór zależy od metody szyfrowania wykładniczego.

Uwaga:

M musi należeć do przedziału [0,...,n-1] , stąd też po długości bloków tekstu poddawanego szyfrowaniu można w przybliżeniu określić wielkość liczby n.

Deszyfracja polega na wykonaniu następującej operacji:

(2) M=C^dmod n, gdzie:

d - to pewien wykładnik wynikający z uogólnienia Eulera

Z uogólnienia Eulera twierdzenia Fermata wynika, że dla każdej liczby M względnie pierwszej z n M^{(n)mod n =} 1 zachodzi zależność:
 
(3)   ed mod (n) =1

Można udowodnić, ze dla e i d spełniających zależność (3) równania (1) i (2) realizują operacje wzajemnie odwrotne.

Twierdzenie5:

Dla danych e i d spełniających równanie (3) oraz wiadomości M zawierającej się w przedziale [0,..,n-1] oraz względnie pierwszej z n to znaczy: gcd(M,n)=1

(4) (M^emod n)^d mod n=M

Znając wartość funkcji Eulera (n) dla danej liczby n, z łatwością można wygenerować parę liczb e i d . W tym celu dokonuje się wyboru liczby d względnie pierwszej z (n) po czym zgodnie z zależnością (3) dokonuje się wyliczenia odwrotności e liczby d modulo (n), na przykład korzystając z algorytmu rozszerzonego Euklidesa:

e=inv(d,(n)).

Uwagi co do łamalności przedstawionego szyfru wykładniczego:

Mając d łatwo można obliczyć e mając (n). Tajemnicę szyfru można więc ukryć zachowując w tajemnicy (n) i d, liczby potrzebne do deszyfracji, podczas gdy e wykładnik potrzebny do szyfracji tekstu może być powszechnie znany.

Ewentualnie zachowując e i d, czyli szyfr ten może posłużyć jedynie do klasycznego szyfrowania (bez klucza jawnego)

Przykład:
 
 

1. Niech n=11, czyli jest to liczba pierwsza, czyli (n)=n-1=10,

2. wybieramy d=7, a więc zgodnie z równaniem 7*e mod 10=1, odwrotnością liczby 7 modulo 10 jest 3. Można to obliczyć :

e=inv(7,10)=3
 

3. Niech M=5 będzie tekstem jawnym do zaszyfrowania, w takim razie:

C=M^emod n = 5³ mod 11 = 4

oraz

M =C^dmod n = 4⁷mod 11=5

Bezpieczeństwo powyższego szyfru opiera się na złożoności obliczania logarytmów dyskretnych w postaci:

e=log_MC

lub

d=log_CM, przy czym kryptoanalityk musi dysponować tekstem jawnym i zaszyfrowanym.

Wzór szacunkowej liczby operacji niezbędnych do wykonania celem złamania szyfru Pohliga-Hallamana:
Najszybszy ze znanych algorytmów obliczania logarytmów dyskretnych przy zadanym n będącym liczbą pierwszą potrzebuje wykonania około:

exp(sqrt(sqrt(ln(n)ln(ln(n)))) operacji tj.

dla liczby n 200-bitowej potrzeba:2,7*10¹¹ operacji do wykonania.

Zakładając, ze potrzeba 100 nS na wykonanie jednej takiej operacji, cała operacja deszyfracji będzie trwała około 0.1 dnia.Dla n o długości 664 bitów, liczba operacji wynosi ok. 1.2*10²³ czyli zajmuje to ok. 10¹¹ dni, czyli cośok. miliard lat.
 
 
 
 

Szyfr RSA(Rivest-Shamir-Adleman)

 

Realizacja szyfru RSA:
Róznica między tym szyfrem a poprzednio omawianą odmianą szyfru wykładniczego polega na odmiennym doborze liczby n. Dobierana ona jest jako iloczyn dwóch wielkich liczb pierwszych p i q .

n=pq, z czego zgodnie z twierdzeniem 3 funkcja Eulera dla n wynosi:
 

(n)=(p-1)*(q-1).

 

Wówczas:

1)zalecane jest wybór liczby d względnie pierwszej z (n) oraz takiej, ze zawiera się ona w przedziale [(max(p.,q)+1,n-1]

2)wartość e oblicza się analogicznie jak w poprzednim algorytmie szyfrowania:

e=inv(d,(n))

z tym ,że jeśli e<log₂n, to nie nastąpi dla każdego szyfrogramu w czasie deszyfracji operacja redukcji modulo n. To oznacza pewne podobieństwo bloków szyfrogramu do tekstu jawnego. Dlatego należy wybrać w tym przypadku nową liczbę d powtórzyć algorytm od punktu 1).

Przykład:

1)Niech p.=5 i q=7, czyli n=35 a (n)=(p-1)(q-1)=24

2)wybieramy d=11

3)obliczamy e=inv(11,24)=11, co oznacza akurat jednakowy wykładnik szyfracji i deszyfracji.

4)Niech M.=2(tekst jawny), wówczas:

C=M^emod n = 2¹¹ mod 35 = 2048 mod 35 = 18

i oczywiście:

M=C^dmod n = 18¹¹ mod 35 = 2 = M

Bezpieczeństwo tego szyfru opiera się na trudności wyliczenia F(n), czyli na faktoryzacji liczby n na czynniki pierwsze(Twierdzenie 3). Liczba operacji potrzebna do rozkładu liczby n na czynniki pierwsze według najszybszego algorytmu Schroeppela równa się szacunkowo liczbie operacji obliczania algorytmów dyskretnych czyli:

exp(sqrt(ln(n)ln(ln(n)))).

W takim razie w przeciwieństwie do algorytmu Pohliga-Hallmana w tym algorytmie można podać całą procedurę szyfracji czyli liczby n i e, ponieważ z liczby n nie wynika w sposób prosty liczba (n), a ta liczba jest właśnie potrzebna do wyliczenia d- wykładnika potrzebnego do deszyfracji.

Protokół wymiany klucza w algorytmie szyfrowania RSA:

Załóżmy, że wymiany informacji chcą dokonać dwie osoby mianowicie: Alicja i Beata, przy czym Alicja jest osobą nadającą informację, a Beata jest osobą odbierającą zaszyfrowaną informację. W takim razie protokół wymiany kluczy może być następujący:

1) Beata generuje dwie wielkie liczby pierwsze p i q i oblicza ich iloczyn n=p*q

2) Następnie Beata na podstawie obliczonej wartości funkcji Eulera tj.

(n)=(p-1)*(q-1) generuje liczbę e

3) Beata, na podstawie wygenerowanej liczby e takiej, że e>log_2n, z równania:
 

ed mod (n) = 1,

 

oblicza wartość liczby d

4) Beata przekazuje liczby e i n Alicji jako swój klucz publiczny, a liczbę d

zachowuje jako swój klucz prywatny.

5) Na podstawie liczb n i e Alicja szyfruje wiadomość i wysyła ją do Beaty

5) Beata posiada tylko sobie znany klucz prywatny d, komplementarny do klucza publicznego e i n i deszyfruje wiadomość otrzymaną od Alicji.

Problem wiarygodności przesłanej wiadomości

Załóżmy, że w trakcie przesyłania wiadomości od Alicji do Beaty, Tomek przechwycił wiadomość przesyłaną przez Alicję i podmienił ją swoją informacją szyfrowaną ( klucz publiczny Beaty e i n jest przecież powszechnie dostępny).

Występuje więc problem potwierdzenia wiarygodności otrzymanej wiadomości.

Rozwiązuje się go przez stosowanie podpisów albo inaczej nazwanych sygnatur elektronicznych. W opisanym powyżej przypadku wymiany informacji między Alicją a Beatą, wiadomość szyfrowaną Alicja podpisuje dodatkowo, stosując swój klucz prywatny (zakładamy, że Beata posiada komplementarny do tego klucza prywatnego Alicji, klucz publiczny Alicji w swojej bazie kluczy publicznych osób z którymi chcę się kontaktować). W takim razie Beata posługując się kluczem publicznym Alicji potwierdzi autentyczność informacji.

Dodatkowo w pakietach szyfracji i wymiany informacji szyfrowanej takich jak PGP(Pretty Good Privacy), stosuje się skrót z informacji przesyłanej, generowany za pomocą jednokierunkowej funkcji skrótu (one - way hash function). Właściwością takiej funkcji jest to, że otrzymana informacja jest trudna do podrobienia. Tzn: że generacja tego "odcisku palca" na podstawie funkcji skrótu jest mało czasochłonna, ale stworzenie dokumentu fałszywego, który posiadałby taką samą wartość funkcji skrótu nastręcza fałszerzowi poważne problemy, związane z wielkimi nakładami obliczeniowymi. Inaczej mówiąc dla funkcji jednokierunkowych nie istnieje funkcja odwrotna, którą można by przedstawić w sposób jawny.

Problem generowania wielkich liczb pierwszych:

Gdy n jest liczbą 200-cyfrową(w układzie dziesiętnym, czyli ok. 600-bitową), to zachodzi potrzeba wygenerowania wielkich liczb pierwszych p i q o długości około 100- cyfr. Oczywiście liczbę taką generuje się z prawdopodobieństwem bliskim jedności.

W tym celu: 

• generujemy liczbę b, która jest “prawdopodobnie liczbą pierwszą

• generujemy 100 liczb a z przedziału [1,b-1]

• liczba a jest prawie na pewno liczbą pierwszą, gdy spełnione są warunki:

        a) gcd(a,b)=1 co jest oczywiste, bo liczby a i b muszą względnie pierwsze.
        b) spełniona musi być równość:

                J(a/b)mod b=a^(b-1)/2 mod b

gdzie: J(a/b) jest symbolem Jacobiego.

Gdy więc b nie jest liczbą pierwszą równania mogą być niespełnione z prawdp.1/2 co dla 100 udanych prób daje prawdp. wystąpienia liczby b, która nie jest liczbą pierwszą równe: 1/2¹⁰⁰

Przykład

long J(long a, long b)
{
 long Jac;
 if(a==1)
  Jac=1;
else
  if((a%2)==0)
{
 if((( (((int)(b*b-1))>>3) )%2)==0)
 Jac=J(a>>1,b);
else
 Jac=-J(a>>1,b);
}
else if(((((int)(a-1)*(b-1))>>2)%2)==0)
 Jac=J(b%a,a);
else
 Jac=-J(b%a,a);
return(Jac);
}

Przy użyciu powyżej zdefiniowanych w C funkcji należałoby 100-krotnie sprawdzic czy następujące wyrazenie jest spełnione(jest prawdziwe):

(J(a,b) %b)= =fastexp(a,(b-1)>>1,b) //w notacji języka C.

Klucz prywatny B

Klucz jawny B

Tekst

zaszyfrowany

Użytkownik B

Użytkownik A

Tekst jawny

Tekst

jawny

Algorytm

deszyfrujący

Algorytm

szyfrujący

---