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

Algorytm
szyfrujący

Algorytm
deszyfrujący

Tekst
zaszyfrowany

Tekst
jawny

Tekst
jawny

Użytkownik A

Użytkownik B

Klucz jawny B

Klucz prywatny
B

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
1

Nadawca szyfruje komunikat za pomocą swojego klucza prywatnego.

2

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

3

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

4

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

≡

5

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

≡

n

ri

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:

∏

−

=

t

i

t

n

n

e

n

e

1

mod

)]

mod

(

[

mod

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

Φ(10) = 4,

a

Φ(11) = 10,

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:

φ(21)

=

φ(7)

*

φ(3)

= (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-1

mod 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

5

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

e

mod 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

d

mod 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

e

mod 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

e

mod n = 5

3

mod 11 = 4

oraz

M =C

d

mod n = 4

7

mod 11=5

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

e=log

M

C

lub

d=log

C

M, 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

11

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

23

czyli zajmuje to ok. 10

11

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

2

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

e

mod n = 2

11

mod 35 = 2048 mod 35 = 18

i oczywi

ś

cie:

M=C

d

mod n = 18

11

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
p

u

blicznym 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

100

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 prawdz

iwe):

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