KRYPTOGRAFIA. - zabezpiecz pieniądze finase komputer

szyfrowanie

Kryptografia.

Obecnie technik kryptograficznych używa się głównie do dwóch celów:

szyfrowania komunikatów
uwierzytelniania komunikatów

Do realizacji obu tych celów stosuje się podobne metody, często korzystając z tzw. kluczy publicznych. Niegdyś używano jedynie kluczy tajnych - obecnie nie zarzuca się tego zupełnie, jednak łączy się tę metodę z metodą kluczy publicznych.

Klucz - publiczny lub tajny
       Mówiąc o szyfrowaniu mamy na myśli parę funkcji: f i g, przy czym f będzie szyfrować, a g odszyfrowywać. Nadawca komunikatu K przekazuje odbiorcy f(K), odbiorca zaś obliczy g(f(K))=K. Jeżeli by się używało zawsze tych samych funkcji f i g, to groziłoby, że ktoś wreszcie złamie nasz szyfr. Co więcej, nie wiadomo, jak przekazać sobie opis tych funkcji. Pamiętajmy, że coś takiego, jak np. "zamiast litery 'a' wstaw 'b', zamiast 'b' wstaw 'c'..." jest banalne do złamania. Zachodzi więc potrzeba jakiegoś sparametryzowania funkcji f i g. Wtedy nadawca, mając komunikat K i parametr KLn, wysyła odbiorcy f(K, KLn). Natomiast odbiorca posiada swój parametr KLo i oblicza K=g(f(K, KLn), KLo). Parametry KLn i KLo nazywa się kluczami.
       Powyższe postępowanie ma sens wtedy, gdy wielkość KLn i KLo nie jest przesadna - nadawca i odbiorca muszą się bowiem jakoś umówić co do wartości tych parametrów. Zwykle też funkcje f i g nie są utrzymywane w tajemnicy: ich kod jest dostępny publicznie. Natomiast klucze są zwykle sekretne. Typowy jest przypadek, gdy KLn=KLo jest liczbą o długości kilkudziesięciu (lub kilkuset) bitów. Jeżeli KLn=KLo, to odbiorca i nadawca muszą się jakoś umówić, jaki klucz wybrać. Nie mogą też nigdy zdradzić tego klucza, gdyż każdy mógłby wtedy mieć dostęp do ich tajemnic. Taka metoda szyfrowania nazywa się szyfrowaniem z kluczem tajnym. Kłopot, jaki powstaje przy używaniu tej metody, to konieczność uzgodnienia klucza przez obie strony "na boku", co często nie jest możliwe.
       Inaczej jest przy tak zwanym szyfrowaniu z kluczem publicznym. Wówczas KLn!=KLo, co pozwala na to, by klucz KLn był ogólnie znany. Klucz KLo musi oczywiście być tajny niezależnie od przyjętej metody szyfrowania. W takiej sytuacji KLn nazywa się kluczem publicznym, a KLo kluczem prywatnym.

Idea szyfrowania z kluczem publicznym
       Szyfrowanie z kluczem publicznym zostało po raz pierwszy zaproponowane przez Diffiego i Hellmana jako rozwiązanie problemu przekazywania zwykłych kluczy tajnych. Każdy, kto chce szyfrować swoje komunikaty, wybiera sobie parę kluczy: klucz publiczny (KLn) oraz klucz prywatny (KLo), które mają tę własność, że g(f(K, KLn), KLo)=K dla każdego komunikatu K. Następnie informuje wszystkich o wartości swojego klucza publicznego (KLo).
       Jeżeli Prosiaczek chce nadać komunikat K do Puchatka, to korzysta jedynie z kluczy Puchatka (a nie ze swoich). Po prostu odczytuje z jakiegoś miejsca publiczny klucz Puchatka (KLn) i oblicza SZ=f(K, KLn). Następnie wysyła do Puchatka komunikat SZ. Puchatek po otrzymaniu komunikatu SZ bierze swój klucz tajny (KLo) i oblicza g(SZ, KLo)=K. Widzimy zatem, że Prosiaczek zdołał poinformować Puchatka o czymś, o czym Kłapouchy nigdy się nie dowie (o ile nie zgadnie prywatnego klucza Puchatka).
       Metoda kluczy publicznych w prosty sposób rozwiązuje też drugi poważny problem kryptograficzny - problem weryfikacji tożsamości. O tym jednak napiszę nieco dalej.
       Oczywiście zasadniczym problem implementacji szyfrowania z kluczem publicznym jest zapewnienie, że, znając funkcje f i g oraz wartość klucza publicznego KLn, nie da się obliczyć w rozsądnym czasie wartości klucza prywatnego KLo. A przecież jest to tylko problem rozwiązania pewnego równania: g(f(K, KLn), X)=K dla każdego K. Wystarczy z tego równania obliczyć X, by nic już nie było dla nas tajemnicą.
       Z tej właśnie przyczyny funkcje f i g nie mogą być całkiem dowolne - muszą mieć specjalne własności kryptograficzne. Stąd pochodzi dodatkowy kłopot z szyfrowaniem kluczem publicznym - jest ono dużo wolniejsze niż szyfrowanie z kluczem tajnym. Dlatego często łączy się obie metody, szyfrując komunikat losowym kluczem tajnym, który to klucz szyfruje się następnie kluczem publicznym odbiorcy. Odbiorca najpierw odszyfrowuje klucz tajny za pomocą swojego klucza prywatnego, a następnie odszyfrowuje wiadomość za pomocą odzyskanego klucza tajnego. Tak utworzone komunikaty nazywamy kopertami cyfrowymi (digital envelopes).

Szyfr RSA
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:

Wybiera sobie dwie liczby pierwsze p i q.
Puchatek oblicza n=p*q.
Puchatek wybiera liczbę e < n i względnie pierwszą z (p-1)*(q-1).
Puchatek znajduje taką liczbę d, że (p-1)*(q-1) dzieli e*d-1.
Prywatnym kluczem Puchatka jest KLo=(n, d).
Publicznym kluczem Puchatka jest KLn=(n, e).
Liczby p i q można zniszczyć.

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

Przedstawia ten komunikat w postaci liczby K.
Sprawdza, jaki jest publiczny klucz Puchatka KLn=(n,e).
Oblicza SZ=K^e mod n.
Wysyła Puchatkowi komunikat (liczbę) SZ.

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

Bierze swój klucz prywatny KLo=(n, d).
Oblicza K=(SZ)^d mod n.
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:

FI(n)=(p-1)*(q-1) jest to liczba liczb względnie pierwszych z n=p*q i mniejszych od tej liczby.
Obliczony przez Puchatka komunikat to (K^e mod n)^d mod n, czyli po prostu K^e*d mod n.
Korzystając z tego, że e*d=1 mod FI(n), otrzymujemy, że wynik Puchatka to (K^FI(n))^a*K mod n.
Twierdzenie Eulera mówi, że jeżeli K jest względnie pierwsze z n, to K^FI(n)=1 mod n.
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.
Jeżeli K nie jest względnie pierwsze z n, to albo K dzieli p, albo K dzieli q.
Rozważmy przypadek K=b*p (b jest względnie pierwsze z q). Drugi przypadek jest analogiczny.
Chcemy udowodnić, że (b*p)^e*d=b*p mod p*q, czyli: b^e*d*p^e*d-1=b mod q.
Po skróceniu przez b dostajemy: (b*p)^{a*(p-1)*(q-1)}=1 mod q (to pozostaje do udowodnienia).
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)
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ą.
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.

Inne szyfry z kluczem publicznym
Inaczej niż RSA wygląda metoda zaproponowana przez Diffiego i Hellmana. Służy ona do uzgodnienia wspólnego tajnego klucza. Opiera się ona na tym, że obliczenie dyskretnego logarytmu jest zapewne bardzo trudne. Wygląda to następująco:

Korzysta się z dwóch publicznych wartości: n i g. Będziemy liczyć modulo n, więc g należy do Z_n.
Prosiaczek wybiera losową liczbą a należącą do Z_n.
Puchatek wybiera losową liczbą b należącą do Z_n.
Liczby a i b są tajne.
Prosiaczek oblicza A=g^a mod n i wysyła A do Puchatka.
Puchatek oblicza B=g^b mod n i wysyła B do Prosiaczka.
Prosiaczek oblicza C=B^a mod n.
Puchatek oblicza C=A^b mod n.
Zarówno Puchatek, jak i Prosiaczek, otrzymują tę samą liczbę C. Ta liczba jest uzgodnionym tajnym kluczem.
Osoba podsłuchująca nie jest w stanie wydobyć wartości C, o ile nie umie obliczyć dyskretnego logarytmu. Uznaje się, że ten problem jest wystarczająco trudny.

Szyfry z kluczem tajnym
       Ponieważ RSA i inne szyfry z kluczem publicznym nie są wystarczająco szybkie, więc zwykle korzysta się z klucza tajnego do szyfrowania komunikatu, by następnie klucz tajny zaszyfrować kluczem publicznym. Jak dotychczas przedstawione algortymy szyfrowały liczby. Powstaje problem, jak szyfrować dużo dłuższe komunikaty. Ten problem dotyczy sytuacji, gdy mamy już dany klucz (tajny), i chcemy zaszyfrować długą wiadomość tak, żeby analiza kryptograficzna nie pozwoliła z szyfrogramu uzyskać tekst oryginalny nie posiadając klucza. Będziemy rozpatrywać przypadki, gdy klucz odbiorcy jest równy kluczowi nadawcy.
       Zakładamy, że wiadomość do zaszyfrowania jest podzielona na bloki ustalonej długości (np. 64 bity). Długość tych bloków będzie zależała od rodzaju szyfru. Najprostsza metoda polega na szyfrowaniu każdego bloku z osobna (szyfr prosty). Bardziej skomplikowana metoda polega na wykonaniu szyfrowania w paru kolejkach (szyfr iterowany). Najpierw szyfrujemy tekst kluczem K1, następnie kluczem K2, it. Często klucze następne pochodzą w jakiś sposób od klucza pierwszego.
       Przykładem szyfru iterowanego jest tzw. szyfr Feistela. W tym szyfrze najpierw dzielimy tekst na połowy. Następnie szyfrujemy lewą połowę za pomocą K1. Nową lewą połową będzie stara prawa połowa, natomiast nową prawą połową będzie wykonanie operacji XOR na starej prawej połowie oraz zaszyfrowanej starej lewej połowie. W następnej kolejce robimy to samo używają innego klucza K2, itd. Zaletą tego systemu jest fakt, że do odkodowania wiadomości używa się tego samego algorytmu, tylko klucze trzeba brać w odwrotnej kolejności.

Łamanie szyfrów z kluczem tajnym
Zanim opiszę bardziej szczegółowo metody szyfrowania z kluczem tajnym, przedstawię możliwe rodzaje ataków na te szyfry. Im lepszy szyfr, tym trudniej będzie wykonać na niego atak i osiągnąć sukces. Ataki mogą być m.in. następujących rodzajów:

Napastnik wybiera sobie tekst i czyta jego zaszyfrowaną wersję. Jest to najtrudniejszy od odparcia rodzaj ataku. Dość trudno go jednak wykonać w praktyce (trzeba zmusić szyfrującego do zaszyfrowania naszego tekstu).
Napastnik zna tekst i jego zaszyfrowaną wersję, ale nie może sobie sam tekstu wybrać. Oznacza to, że ma on do dyspozycji jakąś próbkę tekstów i szyfrogramów, której nie może sobie wybrać.
Napastnik zna tylko szyfrogram. Odgadnięcie oryginału z szyfrogramu wymaga w sposób konieczny jakiejś wiedzy o typie oryginału - w jakim jest języku itp. Takie ataki są bardzo trudne do wykonania.

Metody badania szyfrów i szyfrogramów mogą być różnorodne. Najprostsza polega po prostu na przejrzeniu wszystkich możliwych kluczy. Nie jest to już takie całkiem niemożliwe, o ile np. będziemy mieli specjalny rodzaj komputera do tego przeznaczony. Inna metoda działa na szyfry iterowane. Stosuje się tu tak zwaną analizę różnicową (ang. differential analysis). Polega ona na analizie różnic między podanym tekstem a szyfrogramem. Każdemu kluczowi przypisuje się prawdopodobieństwo, że jest poprawny i wybiera najprawdopodobniejszy klucz. Jedną z ciekawszych metod jest metoda algebraiczna, która wykorzystuje pewne matematyczne własności danego szyfru. Jeżeli na przykład zbiór wszystkich tekstów wraz z szyfrem jako operacją ma strukturę grupy, to atak jest ułatwiony. Wynika stąd na przykład, że wielokrotne szyfrowanie paroma kluczami daje ten sam rezultat, co szyfrowanie jakimś jednym innym kluczem.

DES
Najpopularniejszym szyfrem stosowanym obecnie jest szyfr DES (Data Encryption Standard), który jest oficjalnym standardem szyfrowania przyjętym przez rząd USA. Jest to szyfr z kluczem tajnym (klucz nadawcy=klucz odbiorcy), który łączy się często z RSA (tzn. klucz przekazuje się za pomocą RSA).
DES jest szyfrem typu Feistela. Wykonuje się w 16 kolejkach, korzystając z 56-bitowego klucza. W każdej kolejce używa się innego 48-bitowego klucza wyliczonego z głównego klucza 56-bitowego. Oryginał jest dzielony na bloki wielkości 64 bitów. Jak dotychczas jedyna udana próba złamania DES polegała na "nakarmieniu" go 2⁴³ oryginałami i analizie pochodzących stąd szyfrogramów. Kosztowało to 50 dni pracy 12 stacji roboczych HP 9735. Wykonanie takiego ataku w praktyce wydaje się niemożliwe. DES jest powszechnie uważany za bezpieczny, choć dużo mówi się o konieczności zwiększenia rozmiaru klucza (w obawie przed atakiem "na chama").
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.

Funkcje mieszające - wstęp
Kryptograficzną funkcją mieszającą nazywamy taką funkcję H, że:

Dziedziną H jest zbiór wszystkich możliwych tekstów (dowolnej długości)
H(x) jest zawsze tej samej długości
H(x) jest proste do wyliczenia na komputerze
H jest funkcją "w jedną stronę"
H jest funkcją "bezkolizyjną"

H nazywa się "w jedną stronę", jeśli mając dane y nie da się w rozsądnym czasie znaleźć takiego x, by y=H(x). Funkcja H nazywa się "słabo bezkolizyjna", jeśli dla danego yekstu x nie da się w rozsądnym czasie znaleźć takiego tekstu y, by H(x)=H(y). Funkcja H nazywa się "silnie bezkolizyjna", jeśli w ogóle nie da się w rozsądnym czasie znaleźć takich x, y, by H(x)=H(y).
Kryptograficzne funkcje mieszające znajdują zastosowanie m.in. w tworzeniu elektronicznych podpisów oraz w generatorach liczb losowych. Również jeżeli chcemy uzyskać stempel czasowy, tzn. dać komuś tekst i uzyskać u niego potwierdzenie, że danego dnia ten tekst daliśmy, to funkcje mieszające się przydają. Jeżeli bowiem nie chcemy ujawnić tego tekstu, to stemplujemy tylko wartość otrzymaną z funkcji mieszającej. Zauważmy tu, że istota funkcji mieszającej polega na dwóch rzeczach:

z wartości funkcji na tekście nie da się w żadnym wypadku odzyskać informacji o tekście
nie da się znaleźć tekstu, który dawałby zamówioną z góry wartość mieszającą

Do funkcji mieszających jeszcze powrócę po omówieniu metod potwierdzania tożsamości komunikatów.

Weryfikacja tożsamości
Funkcje mieszające wraz z szyframi typu RSA pozwalają na elektronicznę kontrolę tożsamości nadawcy komunikatu. Przypuśćmy, że Puchatek chce wysłać do Prosiaczka komunikat K (niezaszyfrowany), ale nie jest pewien, czy Prosiaczek uwierzy, że to on napisał. Żeby udowodnić swoją tożsamość skorzysta z wersji RSA. Zachowujemy wszystkie oznaczenia z opisu algorytmu RSA - (n, e) to klucz publiczny, (n, d) to klucz prywatny (oba należą do Prosiaczka). Kontrola tożsamości wygląda następująco:

Prosiaczek wysyła K do Puchatka
Prosiaczek oblicza H(K), a następnie P=(H(K))^d mod n i wysyła P jako swój podpis do Puchatka
Puchatek odbiera K i P
Puchatek rówmież oblicza H(K), a następnie sprawdza, czy P=(H(K))^d mod n. Jeżeli ta zależność jest spełniona, to K zostanie uznany za komunikat od Prosiaczka

Jeżeli dodatkowo chce się zapewnić, że komunikat przekazywany jest tajnie, to wystarczy go najpierw zaszyfrować (np. przez RSA: zaszyfrować go kluczem publicznym Puchatka). Jak widać jest ważne, żeby funkcja H była "bezkolizyjna". Inaczej ktoś mógłby się podszyć pod Prosiaczka.
Istnieją jeszcze nieco inne metody weryfikacji tożsamości, ale wszystkie działają według podobnego schematu (użycie tu funkcji mieszającej jest związane z efektywnością - kodowanie całego komunikatu byłoby zbyt kosztowne).

Funkcje mieszające - cd
Funkcje mieszające buduje się zwykle na fundamencie tzw. funkcji kompresujących. Funkcja kompresująca pobiera dane ustalonej długości i jakoś je skraca. Funkcję mieszającą tworzy się przez iterowane obliczanie funkcji kompresujących, tzn. H(a1,...,an)=C(C(..(C(s,a1),a2)..),an), gdzie C jest funkcją kompresującą dwukrotnie, a s jest wektorem startowym. Jeżeli funkcja C ma kolizje, to nazywamy je pseudokolizjami. Istnienie pseudokolizji nie jest uważane za dowód bezużyteczności funkcji, np. funkcja MD5 (opisana dalej), ma odkryte pseudokolizje, a mimo to jest uważana za bezpieczną.
Najpopularniejsze obecnie funkcje mieszające to MD4, MD5 oraz SHA i SHA-1. Spośród nich MD4 nie jest uważana za bezpieczną, a SHA-1, która jest modyfikacją SHA (Secure Hash Algorithm), jest uważana za najbezpieczniejszą z nich (choć jest nieco wolniejsza niż MD5).

Źródło:
http://rainbow.mimuw.edu.pl/SO/LabLinux/WEJSCIE-WYJSCIE/PODTEMAT_1/crypto.html