W tej lekcji skupimy się na zastosowaniu liczb pierwszych w kryptografii (gałąź wiedzy o szyfrowaniu wiadomości). Omówimy najczęściej dziś stosowany algorytm szyfrowania, jakim jest RSA. Jego nazwa pochodzi od pierwszych liter nazwisk jego twórców, czyli Rona Rivesta, Adiego Shamira oraz Leonarda Adlemana.

Zanim jednak opiszemy działanie algorytmu, wprowadzimy pojęcia matematyczne, które są przydatne do jego dokładnego omówienia.

Kongruencje i arytmetyka modularna

Przypomnijmy sobie dzielenie z resztą i bez reszty w zbiorze liczb naturalnychPodzielność w zbiorze liczb naturalnych – dzielenie z resztą i bez reszty.dzielenie z resztą i bez reszty w zbiorze liczb naturalnych.

Wprowadźmy oznaczenie. Niech n będzie liczbą naturalną większą od 1. Fakt, że liczby naturalne a b dają z dzielenia przez n tę samą resztę będziemy zapisywać następująco:

abmod n.

Powyższy napis można odczytać jako “a przystaje do b modulo n” albo “liczby ab przystają modulo n”. Jeżeli któraś spośród liczb ab jest mniejsza od liczby n, wówczas jest ona równa reszcie z dzielenia każdej z liczb ab przez n.

Przykład 1

Ponieważ liczby 59 z dzielenia przez 2 dają resztę 1, więc prawdą jest, że 591mod 2.

Ponieważ liczby 823 z dzielenia przez 3 dają resztę 2, więc prawdą jest, że 8232mod 3.

Ponieważ liczby 5510 z dzielenia przez 5 dają resztę 0, więc prawdą jest, że 55100mod 5.

Ponieważ liczby 2438 z dzielenia przez 7 dają resztę 3, więc prawdą jest, że 24383mod 7.

Kongruencje (relacja przystawania liczb modulo) mają wiele własności analogicznych do własności relacji równości, ale nie będziemy ich tutaj szczegółowo omawiać.

Rozważmy zbiór n=0, 1, 2, 3,, n-1 wszystkich możliwych reszt z dzielenia przez liczbę naturalną n większą od 1.

W zbiorze tym zdefiniujemy dwa działania:

  • dodawanie modulo n (oznaczane symbolem +n),

  • mnożenie modulo n (oznaczane symbolem ·n).

Niech ab będą liczbami ze zbioru n=0,1,2,3,,n-1. Wówczas sumą modulo n liczb ab nazywamy resztę z dzielenia liczby a+b przez n, zaś iloczynem modulo n liczb ab nazywamy resztę z dzielenia liczby ab przez n.

Przykład 2

Rozważmy zbiór 7=0, 1, 2, 3, 4, 5, 6.

0+72 jest równe reszcie z dzielenia liczby 0+2=2 przez 7, czyli 2.

4+72 jest równe reszcie z dzielenia liczby 4+2=6 przez 7, czyli 6.

4+75 jest równe reszcie z dzielenia liczby 4+5=9 przez 7, czyli 2.

6+72 jest równe reszcie z dzielenia liczby 6+2=8 przez 7, czyli 1.

Cała tabliczka dodawania modulo 7 znajduje się poniżej i zawiera wszystkie możliwe sumy dwóch liczb ze zbioru 7=0, 1, 2, 3, 4, 5, 6.

+7

0

1

2

3

4

5

6

0

0

1

2

3

4

5

6

1

1

2

3

4

5

6

0

2

2

3

4

5

6

0

1

3

3

4

5

6

0

1

2

4

4

5

6

0

1

2

3

5

5

6

0

1

2

3

4

6

6

0

1

2

3

4

5

Przykład 3

Rozważmy zbiór 5=0, 1, 2, 3, 4.

052 jest równe reszcie z dzielenia liczby 02=0 przez 5, czyli 0.

153 jest równe reszcie z dzielenia liczby 13=3 przez 5, czyli 3.

352 jest równe reszcie z dzielenia liczby 32=6 przez 5, czyli 1.

354 jest równe reszcie z dzielenia liczby 34=12 przez 5, czyli 2.

Cała tabliczka mnożenia modulo 5 znajduje się poniżej i zawiera wszystkie możliwe iloczyny dwóch liczb ze zbioru 5=0, 1, 2, 3, 4.

5

0

1

2

3

4

0

0

0

0

0

0

1

0

1

2

3

4

2

0

2

4

1

3

3

0

3

1

4

2

4

0

4

3

2

1

Można udowodnić wiele własności działań modulo n w zbiorze n=0, 1, 2, 3,, n-1 analogicznych do własności dodawania i mnożenia w zbiorze liczb całkowitych.

Niektóre można zaobserwować na powyższych przykładach:

  • zbiór n=0, 1, 2, 3,, n-1 jest zamknięty na dodawanie modulo n, co oznacza, że wynik tego działania należy do zbioru n,

  • zbiór n=0, 1, 2, 3,, n-1 jest zamknięty na mnożenie modulo n, co oznacza, że wynik tego działania należy do zbioru n,

  • 1 jest elementem neutralnym mnożenia modulo n,

  • 0 jest elementem neutralnym dodawania modulo n,

  • dodawanie modulo n jest działaniem przemiennym,

  • mnożenie modulo n jest działaniem przemiennym.

Ponadto możemy wprowadzić definicje liczb (elementów) przeciwnych i liczb (elementów) odwrotnych.

Liczby (elementy) przeciwne
Definicja: Liczby (elementy) przeciwne

Mówimy, że liczby ab ze zbioru n są liczbami przeciwnymi modulo n, jeśli ich suma modulo n jest równa 0.

Liczby (elementy) odwrotne
Definicja: Liczby (elementy) odwrotne

Mówimy, że liczby ab ze zbioru n są liczbami odwrotnymi modulo n, jeśli ich iloczyn modulo n jest równy 1.

Przykład 4

W zbiorze 7 parami liczb przeciwnych modulo 7 są: 16, 25, 34, bo 1+76=0, 2+75=0, 3+74=0. Zero jest liczbą przeciwną do samego siebie, bo 0+70=0.

W zbiorze 7 parami liczb odwrotnych modulo 7 są: 24, 35, bo 274=1, 375=1.
Jedynka jest liczbą odwrotną do samej siebie, bo 171=1. Podobnie liczba 6 jest odwrotna sama do siebie, bo 676=1.

Funkcja φ Eulera

Funkcja φ przyporządkowuje liczbie naturalnej n liczbę liczb względnie pierwszych z n, które nie są od niej większe.

Przykład 5

φ10 oznacza liczbę liczb naturalnych nie większych od 10, które są z dziesiątką względnie pierwsze.
Są to liczby: 1, 3, 7, 9 i jest ich 4, zatem φ10=4.

φ11 oznacza liczbę liczb naturalnych nie większych od 11, które są z jedenastką względnie pierwsze.
Są to liczby: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 i jest ich 10, zatem φ11=10.

Zauważmy, że liczb względnie pierwszych z liczbą 11 jest znacznie więcej, niż liczb względnie pierwszych z liczbą 10, pomimo że obie liczby różnią się tylko o 1. Powodem tego jest fakt, że liczba 11 jest liczbą pierwszą, czyli poza jedynką nie ma dzielników mniejszych od siebie.

Ponieważ liczba pierwszaliczba pierwszaliczba pierwsza p nie ma poza jedynką dzielników mniejszych niż p, zatem wszystkie liczby naturalne mniejsze niż p są z nią względnie pierwsze. Wynika stąd, że dla każdej liczby pierwszej p zachodzi

φp=p-1
Przykład 6

Wyznaczymy φ49.

Zauważmy, że liczba 49 jest kwadratem liczby pierwszej 7 (49=72).

Zatem jedyne liczby nie większe od liczby 49, które nie są z nią względnie pierwsze to wielokrotności liczby 7, czyli 7=71, 14=72, 21=73, 28=74, 35=75, 42=76, 49=77. Jest ich dokładnie 7.

Zatem φ49=49-7=42.

Przykład 7

Wyznaczymy φp2 dla dowolnej liczby pierwszej p.

Zauważmy, że jedyne liczby nie większe od p2, które nie są względnie pierwsze z p2 to wielokrotności liczby p, czyli liczby p, 2p, 3p, 4p, , p-1p, p2. Jest ich dokładnie p.

Zatem φp2 możemy otrzymać odejmując od liczby wszystkich liczb naturalnych od 1 do p2 liczbę wielokrotności liczby p nie większych od liczby p2, zatem φp2=p2-p=pp-1.

Przykład 8

Wyznaczymy φpq dla dowolnych liczby pierwszych pq.

Zauważmy, że jedyne liczby nie większe od pq, które nie są względnie pierwsze z pq to wielokrotności liczby p i wielokrotności liczby q, czyli liczby p, 2p, 3p, 4p, , q-1p, qp oraz liczby q, 2q, 3q, 4q, , p-1q, pq.

Tych pierwszych jest dokładnie p, zaś tych drugich dokładnie q, ale liczba pq jest wielokrotnością i liczby p, i liczby q, co oznacza, że razem tych liczb jest p+q-1.

Zatem φpq możemy otrzymać odejmując od liczby wszystkich liczb naturalnych od 1 do pq liczbę wielokrotności liczby p nie większych od liczby pq oraz liczbę wielokrotności liczby q mniejszych od pq.

Zatem φpq=pq-p+q-1=pq-p-q+1=pq-1-q-1=q-1p-1.

Przykład 9

Wyznaczymy wartość funkcji φ dla wybranych liczb naturalnych:

φ20liczby względnie pierwszeliczby względnie pierwszeliczby względnie pierwsze z liczbą 20 i nie większe od niej to 1, 3, 7, 9, 11, 13, 17, 19, zatem φ20=8

φ25 – liczba 25 jest kwadratem liczby 5, więc możemy wykorzystać zależność z przykładu 7: φ25=25-5=20

φ35 – liczba 35 jest iloczynem dwóch liczb pierwszych (57), więc możemy skorzystać z zależności z przykładu 8: φ35=φ57=5-17-1=46=24

Twierdzenie Eulera
Twierdzenie: Twierdzenie Eulera

Jeśli am są względnie pierwszymi liczbami naturalnymi dodatnimi, to m dzieli liczbę

aφm-1.

Równoważnie twierdzenie można sformułować następująco:

Jeśli am są względnie pierwszymi liczbami naturalnymi dodatnimi, to

aφm1mod m.

Dowód powyższego twierdzenia pominiemy, ale ma ono zasadnicze znaczenie w algorytmie RSA.

Przykład 10

Rozważmy a=22m=35. Ponieważ a=211m=57, więc liczby 2235 są względnie pierwsze.

Na mocy twierdzenia Eulera 22φ351mod 35.

Ponieważ φ35=φ57=5-17-1=46=24, więc 22241mod 35, co oznacza, że liczba 2224 z dzielenia przez 35 daje resztę 1.

Szyfrowanie RSA

Opiszemy teraz krok po kroku działanie algorytmu RSA.

  1. Losujemy dwie liczby pierwsze pq.

  2. Obliczamy iloczyn liczb pq: n=pq.

  3. Obliczamy φn=φpq=p-1q-1.

  4. Wybieramy liczbę J, która spełnia warunki: 1<J<φn oraz J jest względnie pierwsze z φn (J nie jest dzielnikiem φn).

  5. Szyfrogramem (który zostaje przesłany) liczby m jest liczba c obliczona ze wzoru cmJmod n.

  6. Obliczamy T tak, aby TJ1mod𝜑𝑛.

  7. Aby odkodować otrzymany szyfrogram c, obliczamy resztę z dzielenia liczby cT przez n. Z własności kongruencji wynika, że m=cTmod n.

Parę liczb n, J nazywamy kluczem publicznym (jawnym), zaś parę n, T nazywamy kluczem prywatnym (tajnym).

1
Przykład 11

Przyporządkujmy literom alfabetu liczby wg poniższego wzoru:

a

b

c

d

e

f

g

h

i

j

k

l

01

02

03

04

05

06

07

08

09

10

11

12

ł

m

n

o

p

r

s

t

u

w

y

z

13

14

15

16

17

18

19

20

21

22

23

24

Zaszyfrujemy słowo “rak”:

  1. Wybieramy liczby pierwsze p=3q=11.

  2. Obliczamy n=311=33.

  3. Obliczamy φ33=3-111-1=20.

  4. Wybieramy J większe od 1 i mniejsze od 20 względnie pierwsze z 20. Niech J=3.

  5. Odczytujemy liczby odpowiadające literom słowa “rak”:

Litera

r

a

k

Liczba odpowiadająca (z tabeli powyżej)

18

01

11

I etap szyfrowania – podnoszenie do potęgi J=3

183=5832

13=1

113=1331

II etap szyfrowania – obliczanie reszty z dzielenia przez 33

583224mod 33

11mod 33

133111mod 33

Liczby do przesłania

24

01

11

Zatem szyfrogram do przesłania to 24 01 11.

1
Przykład 12

Chcemy odczytać szyfrogram 09 03 26, znając klucz publiczny n, J=33,3.

  1. Osoba, która chce szyfrogramszyfrogramszyfrogram odczytać, potrzebuje klucza prywatnego, czyli takiej liczby T, dla której J·T1mod 𝜑𝑛. W naszym przypadku 3T1mod 20.
    Ponieważ 37=211mod 20, więc T=7.

  2. Możemy deszyfrowaćdeszyfrowaćdeszyfrować wiadomość:

Otrzymane liczby

09

03

26

I etap szyfrowania – podnoszenie do potęgi T=7

97=4782969

37=2187

267=8031810176

II etap szyfrowania – obliczanie reszty z dzielenia przez 33

478296915mod 33

21879mod 33

80318101765mod 33

Liczby po odszyfrowaniu

15

09

05

Litery odpowiadające odszyfrowanym liczbom

n

i

e

Otrzymana wiadomość to “nie” – wstrzymujemy się zatem z działaniem, o którym była mowa z nadawcą szyfrogramu...

W przykładzie 12, aby odczytać treść szyfrogramu, potrzebowaliśmy wartości T. Znając klucz publiczny, mogliśmy ją obliczyć.
Można w takim razie zadać pytanie, na czym polega szyfrowanie, skoro wszystko można obliczyć...
Zwróć uwagę na to, że aby wyznaczyć T, potrzebowaliśmy φn, czyli rozkład liczby n na czynniki pierwsze.
Skuteczność algorytmu RSA opiera się na tym, że nawet superkomputery mają problemy z rozkładaniem naprawdę dużych liczb na czynniki pierwsze. Gdy ktoś chce włamać się do jakiejś bazy danych i potrzebuje złamać hasło, musi zrobić to na tyle szybko, aby nikt nie zdążył się zorientować, a rozkładanie liczby na czynniki pierwsze może zająć przynajmniej kilka dni. Z tego też powodu ciągle trwają poszukiwania coraz większych liczb pierwszych – im większe liczby pierwsze pq pomnożymy, tym większą liczbę n otrzymamy. Zaś im większe n, tym trudniej rozłożyć je na czynniki.

Przykład 13

Spróbuj rozłożyć na czynniki pierwsze liczby:

a) 2627,

b) 56153.

Udało się? Ile czasu Ci to zajęło?

Odpowiedzi:

a) 3771=2627,

b) 241233=56153.

Ciekawostka

Największa odkryta dotąd (styczeń 2019) liczba pierwsza to 282589933-1 i liczy sobie 24 862 048 cyfr w zapisie dziesiętnym. Wyobraź sobie rozkład na czynniki liczb będących iloczynem liczb pierwszych tego rzędu.

Słownik

liczby względnie pierwsze
liczby względnie pierwsze

mówimy, że liczby naturalne km są względnie pierwsze, jeśli ich największym wspólnym dzielnikiem jest 1

liczba pierwsza
liczba pierwsza

liczba naturalna, która ma dokładnie 2 różne dzielniki: 1 i samą siebie

szyfrogram
szyfrogram

wiadomość, która została zaszyfrowana

deszyfrować
deszyfrować

odszyfrowywać wiadomość, która wcześniej została zaszyfrowana

Podzielność w zbiorze liczb naturalnych – dzielenie z resztą i bez reszty.