4. Rola redundancji w bazach danych.

14. ZAGADNIENIA IDENTYFIKACJI OBIEKTÓW W MODELU OBIEKTOWYM.

18. OBIEKTY WIELOTYPOWE.

24. POZIOMY UPOWAŻNIEŃ.

Udzielenie upoważnienia może być zależne od poziomu upoważnień związanego z zasobami. Odmowa udzielenia dostępu ma miejsce, gdy poziom upoważnień terminala i użytkownika < poziom upoważnień żądanej operacji lub danych. Występuje tu hierarchizacja dostępu. Mamy dane jawne, poufne, tajne i ściśle tajne. Ktoś kto ma dostęp do informacji tajnych ma także dostęp do informacji poufnych, ale nie odwrotnie. Poziomy te i kategorie danych mogą się nawzajem uzupełniać. Można także dokonywać łączenia użytkowników w odpowiednie grupy oraz grupowania danych i dopiero sprecyzować w macierzy grupy danych z podaniem użytkowników i ich stopnia poufności. W przypadku dalszych trudności tworzy się odpowiednie pliki opisujące sposób upoważnień w sensie par: użytkownik-konkretna dana lub dana-użytkownik i stopień upoważnienia.

Przykład:

• mamy trzy poziomy: POUFNE, TAJNE I ŚCIŚLE TAJNE

• mamy 16 różnych kategorii danych C1..C16

Uprawnienia użytkownika: ŚCIŚLE TAJNE i dostęp do danych C2, C3, C4, C7, C13, C14

Uprawnienia terminalu: TAJNE i dostęp do danych C11, C14

to użytkownik posługujący się tym terminalem będzie miał dostęp tylko do POUFNYCH i TAJNYCH danych z kategorii C14

26. SZYFRY SYMETRYCZNE I SZYFRY ASYMETRYCZNE.

Algorytmy symetryczne: klucz do szyfrowania oraz deszyfrowania jest taki sam (lub jeden jest łatwo wyprowadzalny z drugiego).

Algorytmy symetryczne:

1. DES

DES, czyli Data Encryption Structured

2. IDEA

Jest to algorytm konkurencyjny w stosunku do DES-a, (choć dużo młodszy (pierwsze wersje pojawiły się w 1990 roku pod nazwą PES). IDEA operuje na 64 bitowych blokach (podobnie jak DES), ale długość klucza równa jest 128 bitom. Blok 64 bitowy dzielony jest na cztery 16 bitowe podbloki, które stają się danymi wejściowymi dla pierwszej rundy algorytmu. IDEA wykorzystuje 8 rund do szyfrowania informacji. Ciekawą własnością tego algorytmu jest szybkość - w przypadku rozwiązań programowych IDEA jest prawie dwa razy szybsza od DES-a.

Zdaniem wielu kryptografów na całym świecie, IDEA jest bezpieczniejsza od DES-a. NSA nie miała wpływu na wygląd i siłę tego algorytmu, ponieważ powstał on w Szwajcarii.

Gdyby przeprowadzić atak brutalny na ten algorytm, to do sprawdzenia byłoby 1038 zaszyfrowanych tekstów.

Możliwy jest atak inną metodą, lecz IDEA jest zbyt młoda, aby można było znać jakiś skuteczny sposób. Dodatkowo IDEA była zaprojektowana tak, by oprzeć się kryptoanalizie różnicowej.

ALGORYTMY ASYMETRYCZNE - RSA

27. SZYFRY BLOKOWE I SZYFRY STRUMIENIOWE.

Szyfrowanie strumieniowe

W szyfrowaniu strumieniowym szyfrowane są pojedyncze bity i bezpośrednio po zaszyfrowaniu gotowe do wysłania. Szyfrowanie strumieniowe może być zrealizowane poprzez jednoczesne wykorzystanie ciągów pseudokosowych i idei one-time pad. Szyfrowanie za pomocą klucza x ma następujący przebieg:

1. Klucz x traktujemy jako zarodek i generujemy pseudolosowy ciąg bitów s1, s1, s3,...,

2. Tekst jawny a1, a2, a3,... pozostaje zaszyfrowany jako ciąg wartości s1 xor a1, s2 xor a2, s3 xor a3,... .

W powyższym algorytmie pseudolosowe algorytmy są generowane w momencie, kiedy są niezbędne do zaszyfrowania kolejnej porcji tekstu jawnego.

RC4

RC4 jest przykładem szyfrowania strumieniowego szeroko stosowanego w praktyce. Był on przedstawiony w 1987 r. i od tego czasu używany w wielu komercjalnych produktach. Poza nazwą i osobą, od której pochodzi idea algorytmu, (R. Rivest), nie ma on nic wspólnego z RC5. W odróżnieniu od DES-a, algorytm, na jakim oparty jest RC4, nie był podany do publicznej wiadomości. Nie był on znany dopóty, dopóki na liście dyskusyjnej (sci.crypt) nie pojawił się program w „C” dający dokładnie takie same rezultaty jak RC4. Zakończyło to erę utajnienia budowy RC4. Program realizujący szyfrowanie RC4 zamieszczony był anonimowo, z pewnością ze względu na obawy przed odwetem właściciela patentu.

Przedstawiony algorytm jest zaskakująco prosty i dobrze nadaje się do implementacji software'owej. Ciąg pseudolosowy używany do szyfrowania generowany jest jako ciąg bajtów. Opiszę pokrótce jego konstruowanie:

• w każdej fazie algorytmu generowany jest jeden bajt ciągu pseudolosowego, jednocześnie uaktualniane są parametry i,j<=256 oraz permutacja pi na zbiorze liczb {1,...,256}. Parametry są nazywane wewnętrznymi kluczami.

• Pojedyncza faza algorytmu wykonuje następujące operacje:
  i:=i+1 mod 256
  j:=j+pi(i) mod 256
  zmień wartości pi dla argumentów i oraz j
  k:=pi(pi(i)+pi(j))
  liczba k jest kolejnym bajtem ciągu pseudolosowego generowanego w tej fazie

• Wewnętrzne klucze i, j, pi są inicjalizowane za pomocą ciągu bajtów s0s1...sm-1. Najpierw wewnętrzne klucze inicjalizowane są w następujący sposób: i:=0, j:=0 oraz pi(h)=h dla h<=256.
  Następnie 256 razy wykonywane są następujące operacje:
  j:=jj+pi(i)+si mod 256
  Zamień następujące wartości pi dla argumentów j oraz pi
  i:=i+1 mod m

Operacje wykonywane na pi w pojedynczej fazie zmierzają do zmiany pi w pseudolosowy sposób. Zauważmy, iż w ciągu kolejnych 245 faz każda wartość pi(i) ulega zamianie. Sposób dokonywania modyfikacji (zamiana wartości) znany jest jako skuteczna metoda szybkiej zmiany postaci pi. Ponadto, bajty k wybierane są jako wartości permutacji pi w miejscu dynamicznie wskazywanym poprzez wartości pi(i) oraz pi(j).

28. TECHNIKI SZYFROWANIA DANYCH (TRYBY PRACY).

29. SZYFR DES.

DES

DES, czyli Data Encryption Structured, to jeden z najbardziej rozpowszechnionych algorytmów kryptograficznych. Jest bardzo stary - ma ponad dwadzieścia lat i do niedawna w miarę skutecznie opierał się różnym atakom.

Twóórcą tego algorytmu była firma IBM, choć część zasługi należy przypisać NSA. To właśnie National Security Agency przeprojektowała S-boxy (zwane czasem S-skrzynkami), które są sercem DES.

DES jest szyfrem blokowym. Dzieli informację na fragmenty długości 64 bitów, a później jeszcze na lewą i prawą połowę (każda o długości 32 bitów). Standardowa długość klucza wynosi 56 bitów. Jednak wraz z postępem kryptografii zaczęto uważać, że taki klucz jest zbyt krótki. Zaowocowało to stworzeniem mutacji DES-a, zwanej 3DES lub Tripple DES.

W przypadku 3DES-a informacja jest szyfrowana trzy razy. Oznacza to, że długość klucza została powiększona do 168 bitów. Jednak niektóre implementacje stosują tylko dwa klucze 56 bitowe.

MUTACJE DES-A

3DES nie jest jedyną modyfikacją Data Encryption Standard. Na przykład firma RSA opracowała algorytm zwany DESX, który jest częścią pakietu BSAFE. Ta wersja algorytmu ma dodatkowy 64-bitowy klucz, za pomocą którego przeprowadzana jest operacja XOR na tekście jawnym przed pierwszą rundą szyfrowania (DES standardowo ma ich 16). Dzięki temu DESX jest bardziej odporny na atak brutalny oraz lepiej opiera się kryptoanalizie różnicowej i liniowej.

CRYPT(3) to wersja DES-a używana w systemach UNIX. Jej wzmocnienie pokega na uniemożliwieniu opracowania urządzenia do łamania haseł.

Tego typu modyfikacji jest najwięcej. Niektóre S-boxy są tak zaprojektowane, by lepiej bronić się przed kryptoanalizy różnicową, inne zaś wzmacniają algorytm przed atakami ze strony kryptoanalizy liniowej. Generalnie nie udało się jednak stworzyć S-boxów lepszych od zaprojektowanych przez NSA.

Wyjątkiem może być s³DES z odwróconymi S-boxami numer 1 i 2. Dzięki temu są one odporne na ataki za pomocą kryptoanalizy różnicowej i liniowej. Istnieje również wersja DES-a, w której S-boxy są zależne od klucza szyfrującego.

BEZPIECZEŃSTWO DES-A

Dzisiaj 56-bitowy klucz nie jest już żadną rewelacją. Wszystko zależy już od wagi samej informacji i czasu jej życia. W połowie lipca 1998r. Electronic Frontier Foundation ogłosiła stworzenie maszyny łamiącej DES-a. Koszty wyprodukawania takiego sprzętu nie przekroczyłyby 250 tysięcy dolarów. Widać więc, że łamanie informacji zaszyfrowanych za pomocą DES-a jest już w zasięgu średniej wielkości firmy. Natomiast 3DES jest rozwiązaniem nadal bezpiecznym. Wszystko zależy jednak od czasu życia informacji - jeśli nie przekracza 24 godzin, to DES jest bardzo bezpieczny.

DES, czyli Data Encryption Structured, to jeden z najbardziej rozpowszechnionych algorytmów kryptograficznych. Jest bardzo stary - ma ponad dwadzieścia lat i do niedawna w miarę skutecznie opierał się różnym atakom.

Twórcą tego algorytmu była firma IBM, choć część zasługi należy przypisać NSA. To właśnie National Security Agency przeprojektowała S-boxy (zwane czasem S-skrzynkami), które są sercem DES.

DES jest szyfrem blokowym. Dzieli informację na fragmenty długości 64 bitów, a później jeszcze na lewą i prawą połowę (każda o długości 32 bitów). Standardowa długość klucza wynosi 56 bitów. Jednak wraz z postępem kryptografii zaczęto uważać, że taki klucz jest zbyt krótki. Zaowocowało to stworzeniem mutacji DES-a, zwanej 3DES lub Tripple DES.

W przypadku 3DES-a informacja jest szyfrowana trzy razy. Oznacza to, że długość klucza została powiększona do 168 bitów. Jednak niektóre implementacje stosują tylko dwa klucze 56 bitowe.

Istnieje kilka trybów działania DES:

• EBC (Electronic Codebook) - każdy 64-bitowy blok koduje się osobno,

• CBC (Cipher Block Chaining) - przed zakodowaniem kolejnego 64-bitowego bloku wykonuje się XOR tego bloku z wynikiem kodowania poprzedniego,

• CFB (Cipher Feedback) - używany do kodowania tekstów z inn± wielko¶ci± bloku niż 64 bity.

• OFB (Output Feedback) - kolejna modyfikacja - błędy w czasie transmisji nie uniemożliwiaj± odczytania tekstu.

Często stosowanym sposobem szyfrowania jest tzw. potrójny DES, który polega na trzykrotnym zastosowaniu DES z trzema różnymi kluczami. Udowodniono, że DES nie ma struktury grupowej, zatem potrójne szyfrowanie ma szanse rzeczywi¶cie być lepsze niż szyfrowanie pojedyncze. Często stosuje się szyfrowanie całych tekstów pojedynczym DES w trybie CBC, natomiast jeżeli konieczne jest zaszyfrowanie klucza, to używa się potrójnego DES w trybie EBC.

Szyfrowanie dowolnych tekstów

Wiadomo, że DES szyfruje tylko bardzo krótkie teksty (8 liter ASCII). Aby DES uczynić użytecznym, trzeba znaleźć sposób na szyfrowanie tekstów dowolnej długości. Poniżej przedstawiam trzy takie metody, rozszerzające szyfrowanie tekstów ustalonej długości, powiedzmy k, na dowolne teksty.

1. Elektroniczna książka kodowa

Elektroniczna książka kodowa (inaczej ECB - Electronic Codebook) funkcjonuje jak następuje:
tekst jawny dzielony jest na bloki długości k (rys 1.1). Każdy z tych bloków jest oddzielnie szyfrowany, za pomocą tego samego klucza.

Tekst
jawny

Kryptogram

Rys 1.1 Schemat trybu ECB.

Tryb ECB ma tę zaletę, że uszkodzenie lub utrata pojedynczych bloków nie ma wpływu na możliwość deszyfrowania pozostałych części kryptogramu. Z drugiej strony, możliwy jest atak nie wymagającyzłamania szyfru. Prześledźmy to na następującym przykładzie:

Załóżmy, że komunikacja pomiędzy dwoma bankami odbywa się w trybie ECB. W ten sposób szyfrowane są przelewy między kontami obu banków. Załóżmy, że specyfikacja kont, na jakie należy dokonać przelewów, ma następującą postać:

Przelew= kon- |na |odbior- |ca |kwo- |ta

Kryptogram= blok1 |blok2 |blok3 |blok4 |blok5 |blok6

Przestępca Kowalski, który jest w stanie modyfikować treść kryptogramów napływających do banku, może przeprowadzać następujący atak:

1. Kowalski dokonuje 17 przelewów na swoje konto i zawsze tę samą kwotę pieniędzy. Następnie identyfikuje w przesłanych kryptogramach taki kryptogram konta, na który dokonano dokładnie 17 przelewów i w dodatku na tę samą kwote. Kowalski może w tym momencie założyć, że chodzi tu o jego konto. W ten sposób poznaje kryptogram numeru swego konta, mimo iż nie ma klucza użytego do szyfrowania.

2. Kowalski zamienia kod numeru konta w pewnej liczbie przepływających kryptogramów, wstawiając na to miejsce kryptogram numeru swego konta. Dzięki temu bank dopisuje do konta Kowalskiegokwoty przeznaczone pierwotnie dla kogo innego.

3. Kowalski wybiera pieniądze ze swego konta i znika.

Aby uniknąć sytuacji opisanej powyżej, trzeba użyć bezpieczniejszego trybu szyfrowania.

Jako ciekawostkę dodać należy, że mimo wskazanych powyżej zagrożeń instytucje finansowe często lekkomyślnie użtwają trybu ECB do transmisji ważnych danych.

2.Cipher Block Chaining

Cipher Book Chainig (CBC) jest metodą, dzięki której ten sam blok tekstu jawnego jest szyfrowany w różnych miejscach i w różny sposób. Osiągane jest to w następujący sposób:
Rozważmy algorytm szyfrujący blok długości k. Niech E_K(X) oznacza kryptogram uzyskany z tekstu jawnego X za pomocą klucza K. Jeśli tekst jawny składa się z bloków P1, P2, P3,... o długości k,to kryptogram uzyskany za pomocą klucza K składa się z bloków C1, C2, C3,... również długości k) zdefiniowanych następująco:

C1= E_K(P1 XOR I) (2.a)

C_i= E_K=(Pi XOR C_i-1)

Ciąg I występujący w powyższym wzorze jest generowany losowo i przesyłany w sposób niezaszyfrowany. Zauważmy, że tym razem kryptogramy poszczególnych bloków są ze sobą powiązane: dla otrzymania C_i wykorzystujemy C_i-1, a nie tylko P_i. Ponieważ C_i zależy od C_i-1, a C_i+1 od C_i więc pośrednio C_i+1 zależy od C_i-1.

Zależności tego typu przenoszą się dalej i ostatecznie każdy blok C_j jest zależny od wszystkich bloków C₁,C₂,... C_i-1, a co za tym idzie również od każdego z ciągów I, P₁,P₂,...P_j-1.

Deszyfrowanie tak uzyskanych kryptogramów jest stosunkowo proste (poniżej D oznacza funkcję deszyfrującą dla bloków długości k).

P1= D_K(C1) XOR I (2.b)

P_i= D_K=(C_i) XOR C_i-1.

Własności szyfrowania w trybie CBC:

• (zaleta) takie same bloki są reprezentowane z reguły przez bloki różnej postaci w kryptogramie. Co więcej ten sam tekst jawny jest szyfrowany w inny sposób, o ile wtbierzemy inny ciąg początkowy I;

• (wada) nie można żadnego bloku C_i usunać z kryptogramu. Stwarza to kłopoty, o ile pragnęlibyśmy za pomocą CBC szyfrować zawartość baz danych. Podobne problemy napotykamy przy próbie wprowadzenia dodatkowego bloku w środku tekstu jawnego: od tego miejsca cały kryptogram musi być utworzony na nowwo;

• (wada) podział na bloki musi być odporny na zakłócenia (dodatkowy bit lub utrata pojedynczego bitu prowadzą do desynchronizacji szyfrowania i deszyfrowania);

• (zaleta) przekłamania wewnątrz jednego bloku (bez zmiany liczby bitów) prowadzą do przekłamań po deszyfrowaniu, ale jedynie w bloku, w którym nastąpiło przekłamanie i bloku następującym po nim (własność ta wynika bezpośrednio z wzoru 2.a);

3.Cipher Feedback

CFB czyli cipher feedback, jest drugim bezpiecznym trybem szyfrowania długich tekstów. W odróżnieniu od CBC szyfrowane są niecałe bloki, ale fragmenty złożone, na przykład, z 8-u bitów, czyli w praktyce jedna litera. Tryb ten może być użyty, na przykład, dla zabezpieczenia komunikacji pomiędzy klawiaturą i serwerem. Oczywiste jest, że w tej sytuacji niezbędne jest natychmiastowe przesyłanie pojedynczych znaków bez czekania na zgromadzenie 8 znaków, jak to miało miejsce w przypadku korzystania z trybu CBC. Możliwe jest również przesyłanie tą metodą na przykład pojedynczych bitów.

Schemat działania CFB przedstawiony jest na rysunku 2.1, przy czym użyto DES jako metodę szyfrowania pojedynczych bloków. Jednym z zasadniczych składników CFB jest rejestr przesuwający. Na początku zawiera on losowo wygenerowany ciąg, który jest przesyłany w niezaszyfrowanej postaci. W trakcie każdego taktu pracy CFB przy użyciu klucza K wykonywane są następujące operacje:

1. Zawartość rejestru przesuwającego jest szyfrowana za pomocą klucza K.

2. Z wytworzonego kryptogramu przesyłanych jest pierwszych 8 bitów, bity te służą do operacji XOR z 8 bitami kodującymi następną literę P podawaną na wejściu. W wyniku otrzymujemy ciąg ośmiu bitów Z.

3. Ciąg Z tworzy osiem kolejnych bitów kryptogramu. Ponadto w rejestrze przesuwającym wykonujemy przesunięcie o 8 pozycji. Przesunięcie to jest niecykliczne - 8 bitów z lewej strony ulega usunięciu. Z kolei na ośmiu zwolnionych pozycjach zapisywany jest ciąg Z.

Klucz K

Następna litera

8 bitów
Z wyjście

Deszyfrowanie odbywa się za pomocą tego samego układu, jedynie role wejścia i wyjścia są odwrócone.

30. SZYFR RSA.

RSA

Pierwszy i do tej pory jedyny powszechnie akceptowany algorytm z kluczem jawnym, jest dziełem Rona Rivesta, Adi Shamira i Lena Adlemana. Powstał w 1977 roku i rok później został po raz pierwszy opublikowany. RSA jest najbardziej znanym algorytmem asymetrycznym. Pomysł polegał na wykorzystaniu bardzo dużych liczb pierwszych. Algorytm może być stosowany z kluczami o bardzzzo różnej długości (np. 512 lub 1024 bity). Sama RSA zaleca używanie kluczy o długości 2048 bitów do szyfrowania najważniejszych informacji. Zdaniem ekspertów z tej firmy, klucz 768 bitowy powinien być bezpieczny do 2004 roku.

RSA jest akgorytmem bezpiecznym - przy założeniu, że nie zostanie w nim znaleziona jakaś dziura lub błąd. Najbardziej skuteczną metodą ataku na algorytm RSA byłoby opracowanie szybkiego rozkładu na czynniki pierwsze (faktoryzacja). Istnieją co prawda inne metody ataku na RSA, ale w wielu przypadkach dotyczą konkretnej implementacji, pozostałe zaś wymagają pełnego zrozumienia działania algorytmu.

Pierwszy i do tej pory jedyny powszechnie akceptowany algorytm z kluczem jawnym, jest dziełem Rona Rivesta, Adi Shamira i Lena Adlemana. Powstał w 1977 roku i rok później został po raz pierwszy opublikowany. RSA jest najbardziej znanym algorytmem asymetrycznym. Pomysł polegał na wykorzystaniu bardzo dużych liczb pierwszych. Algorytm może być stosowany z kluczami o bardzzzo różnej długości (np. 512 lub 1024 bity). Sama RSA zaleca używanie kluczy o długości 2048 bitów do szyfrowania najważniejszych informacji. Zdaniem ekspertów z tej firmy, klucz 768 bitowy powinien być bezpieczny do 2004 roku. RSA jest algorytmem bezpiecznym - przy założeniu, że nie zostanie w nim znaleziona jakaś dziura lub błąd. Najbardziej skuteczną metodą ataku na algorytm RSA byłoby opracowanie szybkiego rozkładu na czynniki pierwsze (faktoryzacja). Istnieją co prawda inne metody ataku na RSA, ale w wielu przypadkach dotyczą konkretnej implementacji, pozostałe zaś wymagają pełnego zrozumienia działania algorytmu.

Nazwa RSA pochodzi od twórców szyfru: Rivest, Shamir, Adleman. Jest to metoda z kluczem publicznym. Metoda ta działa następuj±co:

• Je¶li Puchatek chce otrzymywać tajne komunikaty, to:

1. Wybiera sobie dwie liczby pierwsze p i q.

2. Puchatek oblicza n=p*q.

3. Puchatek wybiera liczbę e < n i względnie pierwsz± z (p-1)*(q-1).

4. Puchatek znajduje tak± liczbę d, że (p-1)*(q-1) dzieli e*d-1.

5. Prywatnym kluczem Puchatka jest KLo=(n, d).

6. Publicznym kluczem Puchatka jest KLn=(n, e).

7. Liczby p i q można zniszczyć.

• Je¶li Prosiaczek chce wysłać do Puchatka tajny komunikat, to:

1. Przedstawia ten komunikat w postaci liczby K.

2. Sprawdza, jaki jest publiczny klucz Puchatka KLn=(n,e).

3. Oblicza SZ=K^e mod n.

4. Wysyła Puchatkowi komunikat (liczbę) SZ.

• Je¶li Puchatek otrzymał od Prosiaczka zaszyfrowany komunikat (liczbę) SZ, to:

1. Bierze swój klucz prywatny KLo=(n, d).

2. Oblicza K=(SZ)^d mod n.

3. Czyta K, wiedz±c, że Kłapouchy na pewno nie ma do tego dostępu.

Dlaczego odszyfrowany przez Puchatka komunikat jest tym samym komunikatem, które nadał Prosiaczek? W tym celu rozumujemy następuj±co:

1. FI(n)=(p-1)*(q-1) jest to liczba liczb względnie pierwszych z n=p*q i mniejszych od tej liczby.

2. Obliczony przez Puchatka komunikat to (K^e mod n)^d mod n, czyli po prostu K^e*d mod n.

3. Korzystaj±c z tego, że e*d=1 mod FI(n), otrzymujemy, że wynik Puchatka to (K^FI(n))^a*K mod n.

4. Twierdzenie Eulera mówi, że jeżeli K jest względnie pierwsze z n, to K^FI(n)=1 mod n.

5. Jeżeli K było względnie pierwsze z n, to z twierdzenia Eulera mamy taki wynik Puchatka: K mod n, czyli po prostu K (zawsze zakładamy, że K < n), zatem jest OK.

6. Jeżeli K nie jest względnie pierwsze z n, to albo K dzieli p, albo K dzieli q.

7. Rozważmy przypadek K=b*p (b jest względnie pierwsze z q). Drugi przypadek jest analogiczny.

8. Chcemy udowodnić, że (b*p)^e*d=b*p mod p*q, czyli: b^e*d*p^e*d-1=b mod q.

9. Po skróceniu przez b dostajemy: (b*p)^{a*(p-1)*(q-1)}=1 mod q (to pozostaje do udowodnienia).

10. Twierdzenie Fermata mówi: jeżeli q jest pierwsze, a x jest względnie pierwsze z q, to zachodzi równo¶ć x^q-1=1 mod q (wniosek z twierdzenia Eulera)

11. W twierdzeniu Fermata używamy x=b*p (to jest względnie pierwsze z q). Otrzymujemy 1^a*(p-1)=1 mod q, co jest niew±tpliwie prawd±.

12. Zatem w obu (wła¶ciwie trzech) przypadkach Puchatek dostaje od Prosiaczka poprawny komunikat.

Udowodnili¶my, że RSA jest poprawny. Ale dlaczego jest to algorytm zapewniaj±cy bezpieczeństwo? Innymi słowy, dlaczego z klucza publicznego (n, e) nie da się obliczyć klucza prywatnego (n, d)? Zakłada się, że takie obliczenie byłoby zbyt kosztowne, ale tego nie udowodniono. W rzeczywisto¶ci nie udowodniono istnienia żadnej bezpiecznej metody szyfrowania z kluczem publicznym. Zauważmy, że gdyby¶my znali rozkład n na czynniki pierwsze, to nie mieliby¶my kłopotu z odnalezieniem klucza prywatnego. Również umiejętno¶ć liczenia pierwiastków w arytmetyce modularnej pozwoliłaby złamać RSA.

Jaka jest poż±dana wielko¶ć liczby n w algorytmie RSA? Obecnie używa się zwykle liczb o 128 lub 512 bitach. Można przeczytać, że koszt złamania klucza 512-bitowego to około $1,000,000 i osiem miesięcy pracy. W zwi±zku z tym uważa się, że za jaki¶ czas będzie trzeba przej¶ć do kluczy większych rozmiarów.

Liczby p i q zwykle się losuje, sprawdzaj±c następnie, czy s± pierwsze. Często nie wykonuje się dokładnego sprawdzenia, a jedynie zapewnia się, że s± one pierwsze z bardzo dużym prawdopodobieństwem.

31. METODA ELGAMALA.

ElGamala - szyfr ten polega na tym, że dla zadanej wartości q  {0,....,q-1} każdy użytkownik wybiera wielkość 0<a<q-1 (tajna część klucza), wtedy kluczem szyfrującym jest [qa,q] gdzie qa {1,....,q-1}. Klucz deszyfrujący definiujemy z twierdzenia Gaussa. Każdy znak zastępowany jest znakiem wynikającym z jego uporządkowania

32. METODA MERKLEGO - HELLMANA.

35. SYSTEMY ROZPROSZONE - OCENA SYSTEMU.

BLOK 3

BLOK 2

BLOK 1

DES

DES

DES

Rejestr przesuwający

P

XOR

Kryptogram

DES

---