Dr inż. Robert Wójcik



Pobieranie 122,08 Kb.
Data13.06.2018
Rozmiar122,08 Kb.

Dr inż. Robert Wójcik, p. 313, C-3, tel. 320-27-40
Katedra Informatyki Technicznej

Wydział Elektroniki

Politechnika Wrocławska
E-mail: robert.wojcik@pwr.edu.pl

Strona internetowa: google: Wójcik Robert
Ochrona i poufność danych
Wykład 4.


  1. Matematyczne podstawy kryptografii




    1. Podzielność liczb, własności, twierdzenia




    1. Arytmetyka modularna




    1. Testy pierwszości




    1. Reszty i pierwiastki kwadratowe




    1. Systemy algebraiczne




    1. Ciała skończone




    1. Wielomiany nad ciałami i sekwencje pseudolosowe




    1. Generatory sekwencji pseudolosowych




    1. Ciała rozszerzone, generowanie elementów ciał

Podzielność liczb


  • Dla danych liczb całkowitych a i b mówimy, że liczba b jest podzielna przez a lub, że liczba a dzieli liczbę b, jeżeli istnieje taka liczba całkowita d, że b = ad. Liczbę a nazywamy dzielnikiem liczby b, a fakt ten zapisujemy a|b.




  • Każda liczba b > 1, ma co najmniej dwa dzielniki dodatnie: 1 i b.




  • Dzielnikiem nietrywialnym liczby b nazywamy dzielnik dodatni różny od 1 i b.




  • Liczba pierwsza p, to liczba większa od 1, nie posiadająca innych dzielników dodatnich niż 1 i p.




  • Liczba, która ma co najmniej jeden nietrywialny dzielnik jest liczbą złożoną.


Rozkład na czynniki pierwsze
Każda liczba naturalna n może być przedstawiona jednoznacznie (z dokładnością do kolejności czynników), jako iloczyn potęg liczb pierwszych, np. 24 = 8 * 3 = 23 * 31.
Największy wspólny dzielnik — NWD(a, b)
Największy wspólny dzielnik, NWD(a, b), dla danych dwóch liczb całkowitych (nie będących jednocześnie zerami), to największa liczba całkowita d będąca dzielnikiem zarówno a, jak i b.

Przykład: NWD(24, 18) = 6


Najmniejsza wspólna wielokrotność — NWW(a, b)
Najmniejsza wspólna wielokrotność, NWW(a, b), to najmniejsza dodatnia liczba całkowita, którą dzielą a i b. Zachodzi:

NWW(a, b) = a · b / NWD(a, b).

Przykład: NWW(24, 18) = 24 · 18 / NWD(24, 18) = 72.

Liczby względnie pierwsze
Liczby a i b są względnie pierwsze jeżeli NWD(a, b) = 1, tzn. liczby a i b nie mają wspólnego dzielnika większego od 1.

Przykład: NWD(3, 11) = 1, zatem liczby 3 i 11 są względnie pierwsze.


Własności relacji podzielności
1. Jeśli a|b i c jest dowolną liczbą całkowitą, to a|bc.

2. Jeśli a|b i b|c, to a|c

3. Jeśli a|b i a|c, to a|b ± c

4. Jeśli liczba pierwsza p dzieli ab, to p|a lub p|b

5. Jeśli m|a i n|a oraz m i n nie mają wspólnych dzielników

większych od 1, to mn|a.



Algorytm Euklidesa
Algorytm Euklidesa pozwala znaleźć NWD(a,b) w czasie wielomianowym.
Dla a > b, dzielimy a przez b otrzymując iloraz q1 i resztę r1,

tzn. a = q1b + r1, w następnym kroku b gra rolę a, zaś r1 gra rolę b, tj. b = q2r1 + r2. Postępowanie to kontynuujemy dzieląc kolejne reszty, ri−2 = qiri−1 + ri, aż do momentu, gdy otrzymamy resztę, która dzieli poprzednią resztę. Ostatnia niezerowa reszta jest NWD(a, b).


Przykład. NWD(26,7) = 1, gdyż:
26 = 3*7 + 5,

7 = 1*5 + 2,

5 = 2*2 + 1,

2 = 2*1.


Rozszerzony algorytm Euklidesa
Jeśli d = NWD(a,b), to NWD można przedstawić w postaci kombinacji liniowej liczb a i b ze współczynnikami całkowitymi, to jest d = u a + v b, gdzie u, v – liczby całkowite. Przy czym liczby u, v można znaleźć w czasie wielomianowym.
Korzystając z ciągu równości w algorytmie Euklidesa (idąc w przeciwną stronę) otrzymujemy z rozszerzonego algorytmu
NWD (a,b) = NWD(26,7) = 1 = 5 – 2*2 = 5 – 2*(7 – 1*5) =

(5 + 2*5) – 2*7 = 3*5 – 2*7 = 3*(26 – 3*7) – 2*7 = 3*26 – 11*7.


Ostatecznie: 1 = 3*26 – 11*7, stąd wynika u = 3 oraz v= -11.
Kongruencje
Dla danych trzech liczb całkowitych a, b i m mówimy, że liczba a przystaje do liczby b modulo m i piszemy a ≡ b (mod m), gdy różnica a − b jest podzielna przez m. Liczbę m nazywamy modułem kongruencji. Własności:

1. a ≡ a (mod m);

2. a ≡ b (mod m) wtedy i tylko wtedy, gdy b ≡ a (mod m);

3. Jeśli a ≡ b (mod m) oraz b ≡ c (mod m), to a ≡ c (mod m);


Kongruencje względem tego samego modułu można dodawać, odejmować i mnożyć stronami.
4. Jeśli a ≡ b (mod m) i c ≡ d (mod m),

to a ± c ≡ b ± d (mod m) oraz ac ≡ bd (mod m);


5. Jeśli a ≡ b (mod m), to a ≡ b (mod d) dla każdego dzielnika d|m;
6. Jeśli a ≡ b (mod m), a ≡ b (mod n), oraz m i n są względnie

pierwsze, to a ≡ b (mod mn);


Kongruencji nie można dzielić stronami. Ale elementy kongruencji można dzielić przez wspólny podzielnik. Dla wszystkich liczb całkowitych a, b i każdej liczby naturalnej m:


jeśli a ≡ b (mod m) i a, b, m mają wspólny podzielnik k, to
a / k ≡ b / k (mod m / k)
7. Dla ustalonej liczby m, każda liczba całkowita przystaje

modulo m do jednej liczby zawartej pomiędzy 0 i m − 1.


Np. 7 ≡ 1 (mod 3), 7 ≡ −2 (mod 3), 6 ≡ 0 (mod 3).

Obliczanie odwrotności modularnej
Liczbami a, dla których istnieje liczba u taka, że a*u ≡ 1 (mod m), są dokładnie te liczby a, dla których NWD(a,m) = 1.
Taka liczba odwrotna u = a−1 może być znaleziona w czasie

wielomianowym z równania: a*u = v*m + 1.


Niech a = 26; m = 7, wówczas kongruencja:
26 *u ≡ 1 (mod 7),
ma nieskończenie wiele rozwiązań, gdyż u = u + k*7 (mod 7),

k – liczba całkowita.

Dla celów kryptograficznych potrzebny jest pierwiastek, będący najmniejszą liczbą dodatnią.
Np. NWD(26, 7) = 1 (patrz poprzedni przykład), to istnieje liczba odwrotna u = 26-1 (mod 7). Liczbę tę można obliczyć za pomocą rozszerzonego algorytmu Euklidesa. Ponieważ 1 = 3*26 – 11*7, to
a*u = 26*3 = 11*7 + 1 = v*m + 1.
Tak, wiec u = 3 = a-1.

Chińskie twierdzenie o resztach
Niech x będzie dowolną liczbą naturalną lub zerem. Dla m naturalnego przez x mod m oznaczamy resztę z dzielenia x przez m.
Zbiór reszt modulo m, czyli {0, 1, …, m-1} oznaczamy Zm.
Niech liczby
m1, m2, …, ms będą parami względnie pierwsze, tj. NWD(mi,mj)=1,
liczby a1, a2, …, as, będą dowolnymi liczbami takimi, że ai < mi.
Wtedy istnieje dokładnie jedna liczba x < m, gdzie
m = m1* m2* …*ms, taka, że dla każdego i <= s zachodzi
x = ai (mod mi), tj. x mod mi = ai.
Inaczej mówiąc, układ równań
x = a1 (mod m1),
x = a2 (mod m2),

x = ai (mod mi),



x = as (mod ms),


ma wspólne, jednoznaczne rozwiązanie x < m, gdzie
m = m1*m2*…*ms.
Z twierdzenia wynika, że wybierając dowolne ai < mi dla i <= s wyznaczamy jednoznacznie liczbę x  Zm, taką, że x = ai (mod mi), dla i <= s.

Np. m1 = 2; m2 = 3; m3 = 5;


m = 2*3*5 = 30;
a1 = 1; a2 = 2; a3 = 3.
Układ równań:
x = 1 (mod 2);

x = 2 (mod 3);

x = 3 (mod 5);
ma dokładnie jedno rozwiązanie x = 23 należące do zbioru

Z30 = { 0, 1, …, 29 }.



Małe twierdzenie Fermata
Niech p będzie liczbą pierwszą. Wtedy każda liczba całkowita a spełnia kongruencję
ap ≡ a (mod p)
i każda liczba całkowita a niepodzielna przez p spełnia kongruencję
ap−1 ≡ 1 (mod p).
np.

a = 4; p = 2; wariant, gdy a podzielne przez p;


41  1 (mod 2) ; nie jest spełnione ap-1 ≡ 1 (mod p);

42 ≡ 4 (mod 2) ; spełnione ap ≡ a (mod p);


a = 4; p = 3; wariant, gdy a niepodzielne przez p;
42 ≡ 1 (mod 3) ; spełnione ap-1 ≡ 1 (mod p) ;

43 ≡ 4 (mod 3) ; spełnione ap ≡ a (mod p) ;


Funkcja Eulera
Dla n ≥ 1, niech φ(n) będzie liczbą tych nieujemnych liczb a mniejszych od n, tj. a  { 1, 2, ..., n-1}, które są względnie pierwsze z n.
Funkcja φ(n) nazywa się funkcją Eulera.
Funkcja Eulera φ jest „multiplikatywna”, tzn. φ(mn) = φ(m)φ(n), jeśli tylko NWD(m, n) = 1.
Np. φ(8) = 4, gdyż w zbiorze liczb mniejszych od 8 tylko 1, 3, 5, 7 są

względnie pierwsze z 8; podobnie φ(7) = 6, gdyż w zbiorze liczb mniejszych od 7 wszystkie liczby są względnie pierwsze z 7. Generalnie dla liczby pierwszej p jest zawsze φ(p) = p-1.


Np. dla liczb m=8 i n=3, zachodzi NWD(8,3) = 1. Wówczas,
φ(mn) = φ(8*3) = φ(8)φ(3) = 4 * 2 = 8 = φ(24),
1, 5, 7, 11, 13, 17, 19, 23 – liczby względnie pierwsze z x = 24.
Testy pierwszości
Istnieją probabilistyczne testy pierwszości liczb, które pozwalają z dużym prawdopodobieństwem w skończonym czasie dać odpowiedź czy dana liczba jest pierwsza.
Test Fermata
Testujemy, czy liczba p jest pierwsza. Wybieramy losowo liczbę

a < p − 1. Wówczas, na pewno a nie dzieli się przez p.


Obliczamy r = ap−1 (mod p), jeśli r  1, to p jest liczbą złożoną.
Test przeprowadzamy t-krotnie, t ≥ 1. Jeśli wszystkie testy wypadną pomyślnie, tzn. r = 1, to liczbę uznajemy za pierwszą, choć może tak nie być.
Test Millera-Rabina
Testujemy, czy liczba n jest pierwsza.
Zapisujemy n−1 = 2sr, gdzie r jest nieparzyste.
Wybieramy losowo liczbę całkowitą a, z przedziału 1 < a < n − 1.
Obliczamy b = a*r (mod n). Jeśli b ≡ ±1 (mod n), to uznajemy,

że n jest pierwsza.


W przeciwnym przypadku obliczamy ak*r (mod n), gdzie k = 2j

(k = 2 do potęgi j) dla kolejnych j z przedziału 0 < j < s.


Jeśli dla pewnego j < s otrzymamy ak*r ≡ −1 (mod n), to uznajemy, że liczba n jest pierwsza.
W przeciwnym przypadku liczba n jest złożona.
Test przeprowadzamy t-krotnie losując różne a.
Np. n=17; n – 1 = 16 = 24*1 = 2s * r; s = 4; r = 1;
Niech a = 3, będzie losową liczbą z przedziału 1 < 3 < 16.
Obliczamy b = a * r (mod n) = 3 * 1 (mod 17) = 3.
Liczba b = 3 nie przystaje do ±1 (mod 17).
Wybieramy kolejno j z przedziału 0 < j < 4=s.
Są to wartości: j=1; j=2; j=3.
Dla j=1 jest k = 2, oraz k*r = 2; stąd ak*r = 32 ≡ 9 (mod 17);

Dla j=2 jest k = 4, oraz k*r = 4; stąd ak*r = 34 ≡ 5 (mod 17);

Dla j=3 jest k = 8, oraz k*r = 8; stąd ak*r = 38 ≡ 16 ≡ -1 (mod 17).
Tak, więc spełniony jest warunek pierwszości liczby n = 17.
Reszty i pierwiastki kwadratowe mod n
Niech dany będzie zbiór reszt Zn = {0, 1, …, n-1}.
Mówimy, że liczba całkowita y jest resztą kwadratową modulo n,

jeśli istnieje taka liczba całkowita x, że x2 = y (mod n).


W takim przypadku mówimy też, że x jest

pierwiastkiem kwadratowym z y modulo n.
Jeżeli y nie jest resztą kwadratową według modułu n, to y

nazywamy nieresztą kwadratową.


Reszty kwadratowe są zatem liczbami, dla których istnieją pierwiastki stopnia 2 względem kongruencji modulo n.
W szczególności liczby y=0 i y=1 są resztami kwadratowymi dla dowolnego n naturalnego, gdyż
02 = 0 mod n ; x = 0 - pierwiastek kwadratowy modulo n;
12 = 1 mod n; x = 1 - pierwiastek kwadratowy modulo n;
Ponieważ dowolna liczba całkowita x daje mod n jedną z reszt należących do zbioru Zn = {0, 1, …, n-1} wystarczy analizować reszty kwadratowe dla elementów x należących do zbioru reszt Zn.
Dla elementów x ze zbioru Z7 = {0, 1, 2, 3, 4, 5, 6 } obliczmy reszty kwadratowe y = x2 (mod 7):
x=0; y = 02 (mod 7) = 0;

x=1; y = 12 (mod 7) = 1;

x=2; y = 22 (mod 7) = 4;

x=3; y = 32 (mod 7) = 2;

x=4; y = 42 (mod 7) = 2;

x=5; y = 52 (mod 7) = 4;

x=6; y = 62 (mod 7) = 1;
Resztami kwadratowymi w Z7 = { 0, 1, 2, 3, 4, 5, 6 } są liczby {0, 1, 2, 4}, natomiast pozostałe liczby {3, 5, 6} są nieresztami.
Natomiast:
x = 0; - pierwiastek z 0 mod 7;
x=1, x=6 – pierwiastki z 1 modulo 7;
x=2, x=5 – pierwiastki z 4 modulo 7;
x=3, x=4 – pierwiastki z 2 modulo 7.

Niech Z(n) oznacza podzbiór tych niezerowych elementów zbioru reszt Zn, = {0, 1, ..., n-1}, które są względnie pierwsze z n, np. Z(5) = {1, 2, 3, 4}


Liczba elementów zbioru Z(n) jest równa wartości funkcji Eulera φ(n), np. dla n=5, φ(5)=4.
Prawdziwa jest następująca własność.
Jeśli n = pq jest iloczynem dwóch dużych, różnych liczb pierwszych, to znajdowanie pierwiastków kwadratowych w zbiorze Z(n) należy do problemów trudnych obliczeniowo.
Trudność ta jest równoważna trudności problemu faktoryzacji liczby n (faktoryzując n znajdujemy liczby pierwsze p i q, następnie znajdujemy pierwiastki kwadratowe w Z(p) oraz Z(q), a z kolei korzystając z chińskiego twierdzenia o resztach znajdujemy pierwiastki w Z(n).


Logarytm dyskretny
Niech p będzie liczbą pierwszą, natomiast Zp* oznacza zbiór liczb {1,...,p−1} i niech g będzie generatorem Zp*, tzn. takim elementem, że dla każdej liczby x ∈ Zp* istnieje takie i∈Zp*, że
x ≡ gi (mod p) (wszystkie elementy mogą być wygenerowane z g).
Problem logarytmu dyskretnego polega na znalezieniu dla danej liczby 0 < b < p oraz znanego g, takiej liczby całkowitej i, że

gi ≡ b (mod p).


Np. Niech p=11, czyli zbiór Z11* = {1, 2, ..., 10}, oraz g = 2.
Niech b = 2i mod 11, dla kolejnych i należących do zbioru

{1, 2, ..., 10} mamy:


i =1; b = 21 mod 11 = 2;

i =2; b = 22 mod 11 = 4;

i =3; b = 23 mod 11 = 8;

i =4; b = 24 mod 11 = 5;

i =5; b = 25 mod 11 = 10;

i =6; b = 26 mod 11 = 9;

i =7; b = 27 mod 11 = 7;

i =8; b = 28 mod 11 = 3;

i =9; b = 29 mod 11 = 6;

i =10; b = 210 mod 11 = 1;

i =11; b = 211 mod 11 = 2; istnieje wiele rozwiązań całkowitych.
Stąd, np. log210 = 5, bo 25 = 10 (mod 11).

Inne rozwiązania t = 5 + m*(p-1).


Problem znajdowania logarytmu dyskretnego jest problemem trudnym obliczeniowo (nie jest wielomianowy względem bitów wejścia, np. gdy liczba b jest k-bitowa, b < 2k, to liczba wszystkich możliwych przypadków (i) może wynieść 2k; np. dla b <= 10, jest

k < 3.5 – sprawdzamy maksymalnie i=10 przypadków).


Ciała skończone
Pojęcie ciała skończonego wprowadzono do matematyki w XIX wieku. Do powstania tego pojęcia przyczynił się matematyk francuski Evariste Galois, stąd nazwa ciała Galois (oznaczane GF(n) – n jest liczbą elementów ciała).
System algebraiczny
Zbiór z określonymi działaniami nazywamy systemem algebraicznym. Do najczęściej stosowanych klas systemów algebraicznych należą:
- grupy,
- pierścienie,
- ciała.
Ciałem nazywamy zbiór A, zawierający więcej niż jeden element, dla którego zdefiniowano operacje dodawania i mnożenia, oraz spełniający niżej podane aksjomaty:
A1. zamkniętość dodawania,

A2. przemienność dodawania,

A3. łączność dodawania,

A4. istnienie zera,

A5. istnienie elementu przeciwnego,

M1. zamkniętość mnożenia,

M2. przemienność mnożenia,

M3. łączność mnożenia,

M4. istnienie jedynki,

M5. istnienie elementu odwrotnego do a  0



D.

rozdzielność mnożenia względem dodawania.



©operacji.org 2017
wyślij wiadomość

    Strona główna