Des szkic des przekształcenie klucza



Pobieranie 75.26 Kb.
Data08.05.2016
Rozmiar75.26 Kb.
DES

Szkic DES




Przekształcenie klucza




Funkcja f(R,K)

DES jest szyfrem blokowym z blokami o długości 64 bitów. Do szyfrowania i deszyfrowania danych wykorzystywanych jest 56 bitów klucza, który zapisany jest w postaci 64 bitowego ciągu, w którym co 8 bit jest bitem kontrolnym i może służyć do kontroli parzystości. Kilka z kluczy uważanych jest za klucze słabe oraz klucze półsłabe


Algorytm szyfrowania danych jest następujący: na początku tekst jawny, który ma zostać zaszyfrowany, dzielony jest na bloki 64-bitowe. Następnie dla każdego bloku wykonywane są następujące operacje:

- dokonywana jest permutacja początkowa bloku przestawiająca bity w pewien określony sposób - nie zwiększa ona bezpieczeństwa algorytmu a jej początkowym celem było ułatwienie wprowadzania danych do maszyn szyfrujących używanych w czasach powstania szyfru

- blok wejściowy rozdzielany jest na dwie 32-bitowe części: lewą oraz prawą

- wykonywanych jest 16 cykli tych samych operacji, zwanych funkcjami Feistela, podczas których dane łączone są z kluczem. Operacje te wyglądają następująco:

bity klucza są przesuwane a następnie wybieranych jest 48 z 56 bitów klucza

-- prawa część danych rozszerzana jest do 48-bitów za pomocą permutacji rozszerzonej

-- rozszerzona prawa połowa jest sumowana modulo 2 z wybranymi wcześniej (i przesuniętymi) 48 bitami klucza

-- zsumowane dane dzielone są na osiem 6-bitowych bloków i każdy blok podawany jest na wejście jednego z S-bloków (pierwszy 6-bitowy blok na wejście pierwszego S-bloku, drugi 6-bitowy blok na wejście drugiego S-bloku, itd.). Wynikiem działania każdego S-bloku są 4 bity wyjściowe – tworzą one 32-bitowe wyjście S-bloków. Każdy S-Blok ma inną strukturę

-- wyjście S-bloków poddawane jest permutacji w P-blokach

-- bity tak przekształconego bloku sumowane są z bitami lewej połowy danych

-- tak zmieniony blok staje się nową prawą połową, poprzednia prawa połowa staje się natomiast lewą połową. Cykl dobiega końca

- po wykonaniu 16 cykli operacji lewa i prawa połowa danych jest łączona

- dokonywana jest permutacja końcowa
Deszyfrowanie polega na zastosowaniu tych samych operacji w odwrotnej kolejności (różni się od szyfrowania tylko wyborem podkluczy, który teraz odbywa się od końca).

RSA

RSA - jeden z pierwszych i obecnie jeden z najpopularniejszych asymetrycznych algorytmów kryptograficznych, zaprojektowany w 1977 przez Rona Rivesta, Adi Shamira oraz Leonarda Adlemana. Pierwszy, który można stosować zarówno do szyfrowania jak i do podpisów cyfrowych. Bezpieczeństwo szyfrowania opiera się na trudności faktoryzacji dużych liczb złożonych.
Generowanie kluczy

W celu wygenerowania pary kluczy (prywatnego i publicznego) należy posłużyć się algorytmem:

- Wybieramy losowo dwie duże liczby pierwsze p i q (najlepiej w taki sposób, aby obie miały zbliżoną długość w bitach, ale jednocześnie były od siebie odległe wartościami - maksymalizuje to bezpieczeństwo klucza)

- Obliczamy wartość n = pq

- Obliczamy wartość funkcji Eulera dla n:

- Wybieramy liczbę e (1 < e < φ(n)) względnie pierwszą z φ(n)

- Znajdujemy liczbę d odwrotną do e mod φ(n):

Klucz publiczny jest definiowany jako para liczb (n, e), natomiast kluczem prywatnym jest para (n, d).
Szyfrowanie i deszyfrowanie

Zanim zaszyfrujemy wiadomość dzielimy ją na bloki mi długości nie większej niż n a następnie każdy z bloków szyfrujemy według wzoru:


Zaszyfrowana wiadomość będzie się składać z kolejnych bloków ci. Tak stworzony szyfrogram przekształcamy na tekst jawny odszyfrowując kolejne blok ci według wzoru:

.


Możliwe jest także zaszyfrowanie wiadomości za pomocą klucza tajnego d a następnie jej odszyfrowanie za pomocą klucza publicznego e. To właśnie ta własność sprawia, że RSA może zostać wykorzystany do cyfrowego podpisywania dokumentów.
Zastosowanie przy podpisie cyfrowym:

M – dokument

M’ - szyforgram

S = skrót dołączony do wiadomości

Po stronie nadawcy: S = h(M)^d mod n

Po stronie odbiorcy: h’(M)=S e mod n

Sprawdzenie czy ważnyi: h(M’) ?= h’(M)
Szyfr blokowy

Potrafi szyfrować blokowy potrafi szyfrować blok danych o określonej długości. Szyfr jest określony parą funkcji Ek i Dk. Jedna słuzy do szyfrowania, druga odszyfrowania. Obie pobierają w parametrze klucz potrzebny do operacji. Typowe klucze i bloki maja rozmiary 64,128,192 lub 256 bitów. Najczęściej szyfrowane dane są większe od bloku, daltego należy podzieliś dane na wiele bloków. Do szyfrowania bloków stosuje się kilka trybów:


- ECB – każdy z bloków jest szyfrowany osobno. Zmiana w jednym z bloków szyfrogramu posoduje błędne odszyfrowanie tylko tego bloku. Tryb ten zapewnia najmniejszy poziom bezpieczeństwa

- CBC – każdy z bloków jest przekształcony funkcją XOR z blokiem szyfrogramu poprzedniego. Pierwszy blok jest przekształcany z wektorem inicjującym(IV), będącym losowym – losowanym na początku. Ponadto IV jest dołaczany do wiadomości. Tryb ten w przypadku zmiany 1 bitu posowuje niepoprawne zdekodowanie aktualnego i następnego bloku

- CFB – Tryb ten także uzywa wektora inicjującego, który jest poddawany szyfrowaniu z kluczem. Nastepnie uzyskany fragment szyfrogramu jest uzywany jako klucz dla następnego bloku

-OFB – Na początku generowany jest IV, który jest szyfrowany, a następnie przekształcony operacją COR z blokiem wejściowym dając fragment szyfrogramu. W kolejnym kroku zamiast wektora inicjującego uzywany jest fragment szyfrogramu uzyskany w wyniku szyfrowania obecnego kroku


DSA

Digital Signature Algorithm jest standardem dla cyfrowego podpisu z roku 1991. Został stworzony przez NIST i wprowadzony w 1993. W kolejnych latach był rozwijany i rozszerzony. Etap generowania kluczy ma 2 fazy. Pierwszą z nich jest wybór ustawień algorytmów, które będą użyte w trakcie tworzenia podpisu.

-Należy wybrać funkcję skrótu H. Dostępne są np.: SHA-1, SHA-2

- wybrać długość kluczy L i N. Długość ta definiuje siłę całego podpisu. N musi być mniejsze niż długość wyniku funkcji skrótu

- wybrać liczbę pierwszą q o długości N bitów

- wybrać liczbę pierwszą p, tak aby p-1 było wielokrotnością q, p musi mieć długość L bitów

- wybrać liczbę g, wybierając dowolną liczbę z przedziału(1,p-1) i podstawiając do wzoru g = h(p-1/q)
Parametry pq,g mogą być współdzielone miedy użytkownikami. Faza druga to generowanie kluczy publicznego i prywatnego użytkownika

- Należy wybrać x z przedziału(0,q)

- Wyznaczyć y =g x mod p

- Klucz publiczny zawiera parametry p,q,g,y, kluczem prywatnym jest x


Etapy podpisywania:

Losujemy liczbę k z przedziału (0,q), obliczamy:

r = (g^k mod p) mod q

s = ( k-1 * ( H(m)+x*r ) ) mod q

Gdy r =s = 0 należy powtórzyć cału etap podpisywania. Podpisem wiadomości m jest para (r,s)
Weryfikacja:

Sprawdzenie następujacyh danych:

Czy r,s c ͼ (0,q)?

Obliczyć:

W=s-1

v1=( H(m)*w ) mod q

v2=(r*w) mod q

v (( q v1 * y v2) mod p) mod q

Podpis jest prawidłowy jełi v = r
ElGamal

ElGamal to jeden z dwóch najważniejszych algorytmów kryptografii asymetrycznej (obok RSA). System jest oparty na trudności problemu logarytmu dyskretnego w ciele liczb całkowitych modulo duża liczba pierwsza. Algorytm w połowie lat 80. XX wieku przedstawił Egipcjanin Taher Elgamal. Algorytm ElGamala umożliwia szyfrowanie oraz obsługę podpisów cyfrowych. Setki modyfikacji algorytmu ElGamala (podobnie jak modyfikacje algorytmu RSA) mają różne inne zastosowania.



Generowanie klucza: wybieramy dowolną liczbę pierwszą p, dowolny generator α podgrupy multiplikatywnej, tzn. taki element, którego rząd jest równy p − 1 oraz dowolne k takie, że: 1 < k < p. Liczymy β: β = αk mod p, co potrafimy zrobić szybko za pomocą potęgowania przez podnoszenie do kwadratu.

Zobaczmy, co by było gdyby α było dowolne. Weźmy dla przykładu: p=41, α=41, k=16, wówczas: β=1416 mod 41 = 1, co spowodowałoby, że kryptosystem byłby bezużyteczny (gdyż przy szyfrowaniu, zawsze otrzymywalibyśmy 1).


Następnie publikujemy (p,α,β) jako klucz publiczny, i zachowujemy (p,α,β,k) jako klucz prywatny.

Szyfrowanie: mając do zaszyfrowania wiadomość m przedstawiamy ją jako element grupy [1 < m < p − 1] wybieramy losowo liczbę x i liczymy (modulo p): (αx, m × βx)

Deszyfrowanie: podnosimy otrzymane αx do potęgi k:

x)k = αkx = (αk)x = βx


Następnie znajdujemy odwrotność βx (oczywiście nadal modulo p) rozszerzonym algorytmem Euklidesa:
γβx + δp = 1
γβx ≡ 1 mod p
γ ≡ (βx)-1 mod p
W końcu dzielimy m × βx przez βx, czyli mnożymy przez jej odwrotność – γ: (m × βx) × γ ≡ m × (βx × γ) ≡ m × 1 ≡ m mod p

Podpis cyfrowy:
Klucz jest generowany w ten sam sposób. Żeby wygenerować podpis wiadomości m losujemy liczbę r i liczymy:
y = αr(mod p)
s = (H(m) − ky)r−1 (oczywiscie mod(p-1)), gdzie H jest funkcją haszującą. Podpisem jest para (y,s)

Żeby zweryfikować podpis sprawdzamy równanie: βyys = αH(m)


Co dla prawidłowego podpisu będzie się zgadzać:
αkyαrs = αH(m)
αky + r((H(m)-ky)r-1) = αH(m)
αky + H(m) − ky = αH(m)
αH(m) = αH(m)
Ważne jest zachowanie tajności wylosowanego r. Jeśli r byłoby znane, to można odzyskać klucz prywatny z podpisu:
y-1(H(m) – sr) = y-1 (H(m) – (H(m) – ky)r-1r) = y-1ky = k

Bezpieczeństwo:
Jeżeli rząd grupy multiplikatywnej jest iloczynem liczb pierwszych, spośród których nawet jedna nie jest odpowiednio duża, istnieje efektywna metoda obliczania wykładnika. Nie jest znana 'ogólna' metoda szybkiego liczenia logarytmu dyskretnego, więc nie wiemy jak za pomocą αx i α uzyskać x, które w pełni wystarczyłoby do odszyfrowania wiadomości. Nie ma jednak dowodu, że taka nie istnieje. To ostatnie nie może raczej dziwić, gdyż takich dowodów nie ma dla żadnego znanego szyfru asymetrycznego.
Nie mamy jednak dowodu, że złamanie problemu logarytmu dyskretnego jest jedynym sposobem złamania tego szyfru. Być może istnieje szybki algorytm, który znając α, β, p i αx, m×βx (czyli klucz publiczny i szyfrogram wiadomości) jest w stanie odzyskać m obchodząc w jakiś sposób ten problem.

Szyfr strumieniowy
nazywany także algorytmem strumieniowym, algorytmem potokowym lub szyfrem strumieniowym; jest to algorytm symetryczny, który szyfruje oddzielnie każdy bit wiadomości. Algorytm ten składa się z generatora strumienia bitowego, będącego kluczem szyfrującym oraz elementu dodającego (na przykład operacji XOR).

Wykorzystując operację XOR szyfrowanie wiadomości wygląda następująco: Ci = Si (+) Mi, gdzie Si to strumień bitów będący kluczem, Mi to tekst jawny a Ci to szyfrogram.


Odszyfrowywanie zakodowanej wiadomości odbywa się w identyczny sposób – generujemy strumień szyfrujący i XOR-ujemy go z szyfrogramem: Si (+) Ci = Si (+) Si (+) Mi = Mi

Istnieją szyfry strumieniowe oparte na generatorach liczb pseudolosowych – jeśli generator jest kryptograficznie silny, to ziarno generatora może służyć jako klucz, a generowany strumień pseudolosowych liczb jako strumień szyfrujący. Blum Blum Shub jest przykładem generatora, dla którego istnieje dowód, że złamanie go jest co najmniej równie trudne jak rozbicie liczby stanowiącej klucz na czynniki.
Szyframi strumieniowymi są też tryby CFB, OFB i CTR szyfrów blokowych. Generują one z samego klucza i z wektora inicjalizującego (nie korzystając z danych) strumień szyfrujący, po czym XOR-ują go z danymi.
IDEA
W ramach wspólnego projektu ETH Zurich i firmy Ascom Systec AG podjęto próbę położenia pod nowy algorytm solidnych teoretycznych fundamentów. W pierwotnej formie został on zaprezentowany w 1990 roku pod nazwą PES (Proposed Encryption Standard). Bihamowi i Shamirowi udało się go zaatakować przy użyciu kryptoanalizy różnicowej. W odpowiedzi na to Lai i Massey zabezpieczyli swój algorytm przed kryptoanalizą różnicową; dodali też literę „I" przed nazwą (od ang. improved, poprawiony). Od roku 1992 algorytm znany jest pod nazwą IDEA -Intemational Data Encryption Algorithm. Algorytm IDEA został wykorzystany do szyfrowania symetrycznego w bardzo popularnym pakiecie PGP i głownie dzięki temu stał się sławny. W znacznie mniejszym stopniu zwraca się uwagę na to, że jest chroniona patentem (w Europie do 16 maja 2011 roku; Amerykanie będą ją mogli stosować bezpłatnie rok wcześniej).

Budowa algorytmu
- IDEA operuje na 64-bitowych blokach wykorzystując klucz 128-bitowy. Na podstawie tego klucza generowane są 52 podklucze, każdy po 16 bitów. Generowanie odbywa się w następujący sposób:
1. W pierwszej kolejności klucz rozbijany jest na osiem 16-bitowych kawałków. Stanowią one pierwsze 8 kluczy.
2. Następnie klucz 128-bitowy przesuwany jest cyklicznie o 25 bitów w lewo (tj. 25 najstarszych bitów wchodzi zatem ponownie po prawej stronie) i natychmiast rozbijane jest na kolejne 8 podkluczy.
3. Kolejno wykonywane jest jeszcze 15 takich rund.
4. W siedemnastej rundzie wybierane są już tylko 4 klucze od strony najstarszych bitów.
- Szyfrowanie przy użyciu IDEI przebiega w 8 rundach, jest to więc algorytm złożony, choć nie jest siecią typu Feistela. W każdej rundzie wykorzystuje się 6 kluczy.
- W każdej z rund blok rozbijany jest na 16-bitowe ćwiartki, które łączone są trzema niekompatybilnymi ze sobą operacjami; każda z tych operacji przetwarza wyłącznie 16-bitowe liczby. Dzięki temu IDEĘ łatwiej zaimplementować sprzętowo, a co więcej, działa efektywnie nawet na 16-bitowych procesorach.
- Na zakończenie na 4 blokach 16-bitowych wykonujemy końcową transformację przy użyciu ostatnich 4 kluczy i łączymy je w kryptogram.
- Operacje wykorzystywane w algorytmie IDEA, to: xor (), dodawanie modulo 216 () oraz mnożenie modulo 216 + 1.

Szyfrowanie
- 64 bitowy blok jest dzielony na 4 bloki po 16 bitów: X1, X2, X3, X4, które stanowią dane wejściowe dla pierwszej rundy algorytmu.
- Algorytm składa się z 8 rund.
- W każdej rundzie wykonywane są wymienione wyżej 3 typy operacji na 16 bitowych blokach z 16 bitowymi podkluczami (każda runda wymaga 6 podkluczy).
- W wyniku otrzymuje się 4 bloki po 16 bitów: Y1, Y2, Y3, Y4.
- Pomiędzy rundami blok 2 i 3 są zamieniane.
- Algorytm kończy przekształcenie końcowe, które wymaga 4 podkluczy.

Generowanie podkluczy
- IDEA używa klucza 128 bitowego i wymaga 8*6+4=52 podklucze.
1. 128 bitowy klucz jest dzielony na bloki 16 bitowe, co daje 8 podkluczy.
2. Na kluczu wykonuje się przesunięcie cykliczne o 25 pozycji i znowu dzieli na bloki 16 bitowe, co daje kolejne 8 podkluczy.
3. Operację z punktu 2 powtarza się tak długo aż wygeneruje się wszystkie podklucze.

Deszyfrowanie
- Deszyfrowanie algorytmem IDEA przebiega wg schematu przedstawionego na rys. a, w którym zamiast : X1, X2, X3, X4, na wejściu podaje się bloki Y1, Y2, Y3, Y4 kryptogramu oraz klucz K (ten sam co przy szyfrowaniu).
- Z klucza K generuje się podklucze Ki(r).
- Generuje się podklucze deszyfrujęce Ki(r) wg schematu przedstawionego w tablicy b.

Tablica b. Tworzenie podkluczy deszyfrujących Ki(r) na podstawie podkluczy szyfrujących Ki(r) w algorytmie IDEA (dla Ki = 0 przyjmuje się (Ki)-1 = 0, 216 ≡ -1 mod 216 + 1).

Szybkość działania. Perspektywy.
W implementacjach programowych IDEA jest niemal dwukrotnie szybsza niż DES. Sprzętowo jest jednak trudniejsza do zrealizowania niż DES, przede wszystkim z uwagi na operację „”. Opracowany na ETH Zurich IDEA-Chip osiągnął prędkość 22 MB/s, nie rozpoczęto jednak jego seryjnej produkcji. Główną przeszkodą jest tutaj niechęć biznesu spowodowana opłatami licencyjnymi. Bezpieczeństwo nie uzyskało jeszcze takiego znaczenia, by przedsiębiorstwo zatrudniające 100 pracowników gotowe było zapłacić 1000 dolarów za szyfrowanie danych we własnej sieci wewnętrznej. Na przykład, za wykorzystanie IDEI w swoim oprogramowaniu producent musi odprowadzać 2% obrotów z tego tytułu do Ascom Systec AG - to jest zdecydowanie zbyt wiele. Sama nazwa IDEA nie jest wystarczającą reklamą.

Funkcja jednokierunkowa

funkcja, która jest łatwa do wyliczenia, ale trudna do odwrócenia. "Łatwa do wyliczenia" oznacza tu, że istnieje algorytm wielomianowyktóry ją wylicza. "Trudna do odwrócenia" oznacza, że żaden wielomianowy algorytm probabilistyczny nie potrafi znaleźć elementu przeciwobrazu f(x) z prawdopodobieństwem większym niż zaniedbywalne, jeśli x jest wybrane losowo. Trudność dotyczy zatem średniego przypadku, a nie pesymistycznego, jak w większości problemów w teorii złożoności obliczeniowej (np. w problemach NP-trudnych).

Formalna definicja
Formalnie, funkcje jednokierunkowe definiuje się na dwa sposoby:

Funkcja silnie jednokierunkowa to funkcja  taka że:

  • f jest obliczalna w czasie wielomianowym

  • Dla dowolnego  i dowolnego wielomianowego algorytmu probabilistycznego A, jeśli k jest wystarczająco duże, to:

Pr

Innymi słowy, żaden algorytm probabilistyczny nie jest w stanie zgadnąć wartości argumentu z prawdopodobieństwem, które nie byłoby zaniedbywalnie małe.



Funkcja słabo jednokierunkowa to funkcja  taka że:

  • f jest obliczalna w czasie wielomianowym

  • Istnieje , takie że dla dowolnego wielomianowego algorytmu probabilistycznego A, jeśli k jest wystarczająco duże, to:

Pr

Innymi słowy, każdy algorytm probabilistyczny który ją odwraca, podaje błędną wartość z prawdopodobieństwem, które nie jest zaniedbywanie małe.


Funkcje silnie jednokierunkowe są oczywiście również słabo jednokierunkowe. Choć istnienie tych drugich wydaje się znacznie bardziej prawdopodobne, można pokazać że jeśli istnieją funkcje słabo jednokierunkowe, to istnieją również silnie jednokierunkowe.

Istnienie funkcji jednokierunkowych
Istnienie funkcji jednokierunkowych jest otwartym problemem w informatyce. Z faktu że istnieją, wynikałoby automatycznie że P≠NP, rozstrzygając najsłynniejszy problem w informatyce. Implikacja w drugą stronę nie jest znana – nie wiadomo czy z faktu że P≠NP wynikałoby automatycznie istnienie funkcji jednokierunkowych. Wiąże się to z różnicą pomiędzy rozważaniem średniego a najgorszego przypadku w tych problemach.

Istnienie tych funkcji pozwoliłoby uzyskać wiele przydatnych w kryptografii narzędzi, między innymi:



Generatory liczb pseudolosowych
Protokoły zobowiązania bitowego
Bezpieczne kody uwierzytelniające wiadomości
Bezpieczne podpisy elektroniczne

Kandydaci na funkcje jednokierunkowe

Ponieważ do tej pory nie wiadomo czy funkcje jednokierunkowe istnieją, w praktyce używa się kilku funkcji które są o to podejrzewane: funkcji, dla których pomimo wysiłku wielu badaczy nie udało się znaleźć efektywnych algorytmów odwracających.



Mnożenie vs. Faktoryzacja
Mnożenie liczb naturalnych jest łatwe algorytmicznie. Z drugiej strony, jeśli pomnożymy przez siebie dwie duże liczby pierwsze, znalezienie ich na podstawie iloczynu może być trudne. Mnożenie może być więc funkcją słabo jednokierunkową. Na tej funkcji opiera się w dużej mierze kryptosystem RSA.

Obecnie najlepszym znanym algorytmem faktoryzacji jest GNFS, którego złożoność wynosi .



Funkcja Rabina
Jeśli dla danego N i x < N wyliczymy y = x2 (mod N), to można pokazać że znalezienie x na podstawie y jest algorytmicznie równie trudne jak faktoryzacja N. Podnoszenie do kwadratu jest więc równie dobrym kandydatem na funkcję jednokierunkową jak mnożenie. Na tej funkcji oparty jest kryptosystem Rabina.

Potęgowanie vs. logarytm dyskretny
Jeśli dla danej liczby pierwszej p oraz g < p i x < p wyliczymy y = gx(mod p), to okazuje się że nie znamy efektywnego algorytmu pozwalającego znaleźć właściwe x na podstawie g, y i p. Potęgowanie w ciele skończonym jest więc kandydatem na funkcję jednokierunkową. Opiera się na nim kryptosystem ElGamal.

Inne funkcje
Wszystkie trzy podane wyżej funkcje mogą być funkcjami jednokierunkowymi, ale wiadomo już że można je łatwo odwracać jeśli ma się do dyspozycji komputer kwantowy (używając Algorytmu Shora do faktoryzacji i kwantowej transformaty Fouriera do wyliczenia logarytmu dyskretnego). Istnieją inne funkcje podejrzewane o bycie funkcjami jednokierunkowymi, np. bazujące na różnych problemach NP-zupełnych (np. system Merkle-Hellman) lub na składaniu permutacji (VMPC). W praktyce ich bezpieczeństwo jest jednak znacznie słabiej zbadane.

Funkcja "skrótu"
 funkcja mieszająca lub funkcja haszująca - funkcja, która przyporządkowuje dowolnie dużej liczbie (wiadomości) krótką, zwykle posiadającą stały rozmiar niespecyficzną, a quasi-losową wartość (tzw. "skrót" nieodwracalny wiadomości).

informatyce funkcje skrótu pozwalają na ustalenie krótkich i łatwych do weryfikacji sygnatur dla dowolnie dużych zbiorów danych. Takie sygnatury mogą chronić przed przypadkowymi lub celowo wprowadzonymi modyfikacjami danych (sumy kontrolne), a także mają zastosowania przy optymalizacji dostępu do struktur danychw programach komputerowych (tablice haszujące).



Bezpieczne funkcje skrótu
Szczególną podgrupą funkcji skrótu są funkcje uznawane za bezpieczne do zastosowań kryptologicznych (jak np. SHARIPEMD-160). Kryptograficzna funkcja skrótu powinna spełniać następujące kryteria:

  1. Brak praktycznej możliwości wygenerowania wiadomości o takim samym skrócie jak zadana wiadomość (Preimage resistanceSecond preimage resistance)

  2. Brak praktycznej możliwości wygenerowanie dwóch wiadomości o takim samym skrócie (Kolizje). Warto zauważyć, że w związku z atakiem urodzinowymproblem ten jest istotnie łatwiejszy niż poprzedni. Własność ta nie jest wymagana w niektórych zastosowaniach.

  3. Brak możliwości wnioskowania o wiadomości wejściowej na podstawie wartości skrótu (jednokierunkowość). Zmiana dowolnego pojedynczego bitu wiadomości powinna zmieniać średnio połowę bitów skrótu w sposób, który nie jest istotnie podatny na kryptoanalizę różnicową.

Należy zauważyć, że uznanie funkcji za bezpieczną do zastosowań kryptograficznych opiera się zawsze wyłącznie na domniemanej odporności na znane ataki kryptoanalityczne, nie zaś na matematycznych dowodach gwarantujących niemożność złamania. W szczególności bezpieczna funkcja skrótu musiałaby być funkcją jednokierunkową, a istnienie takich funkcji nie zostało dotychczas dowiedzione. Poważne słabości znaleziono w wielu funkcjach skrótu, które historycznie uchodziły za bezpieczne - m.in. w MD2MD4SHAMD5.

Niekiedy zamiast wyspecjalizowanych funkcji skrótu do realizacji podobnych funkcji stosuje się algorytmy zbudowane na bazie szyfrów blokowych - zwłaszcza wkodach uwierzytelniania wiadomości (MAC).



Ataki na funkcje skrótu
Nawet bezpieczne funkcje skrótu mogą być obiektem ataków kryptograficznych, wykorzystujących miejsce gdzie funkcje te są wykorzystywane w strukturach danych. Wiele struktur danych działa bardzo efektywnie w przeciętnym przypadku, ale słabo w przypadku pesymistycznym. Atakujący może za pomocą niewielkiej ilości specjalnie w tym celu przygotowanych danych przeciążyć system (atak DoS).

Zabezpieczenia
Możliwe zabezpieczenia przed atakami to między innymi:

  • używanie struktur danych o lepszej złożoności pesymistycznej, pomimo gorszych wyników przeciętnych (np. drzew czerwono-czarnych zamiast tablic mieszających)

  • wykrywanie ataków tego typu lub uniemożliwienie ich powstawania przez odrzucanie patologicznych danych

  • używanie kryptograficznie bezpiecznych funkcji skrótu dodatkowo wzmocnionych przeciwko takim atakom (np. funkcji skrótu z kluczem jak HMAC-MD5, HMAC-SHA1)

  • randomizacja skrótów (NIST SP 800-107)

Zalecenia
Amerykański instytut NIST publikuje zalecenia dotyczące stosowania poszczególnych funkcji skrótu w zależności od pożądanego czasu ochrony informacji. Zgodnie z tymi wytycznymi od 1999 roku nie powinna być stosowana funkcja MD5, zaś funkcja SHA-1 powinna być stosowana co najwyżej do 2010 roku[1].

Aktualnie zalecane do nowych aplikacji są funkcje z rodziny SHA-2. W toku jest konkurs NIST na nową funkcję skrótu (SHA-3)[2]



Szyfr Rijndael/AES
Trochę historii
W 1997 roku rozpoczęły się oficjalne przygotowania do zastąpienia szyfru DES przez nowocześniejszy. W styczniu 1997 NIST (National Institute of Standards and Technology) ogłosił swego rodzaju konkurs "Call for Algorithms" aby po około 20 miesiącach wyłonić 15 kandydatów (pierwsza runda), po kolejnych 8 miesiącach lista ta została zawężona do 5 kandydatów:

1) Nowy szyfr z firmy IBM – MARS


2) Szyfr Ronalda Rivest'a - RC6
3) Rijandel - autorstwa dwu Belgów (Joan Daemen i Vincent Rijmen)
4) SERPENT - szyfr międzynarodowego zespołu z Anglii, Izraela i Norwegii
5) TwoFish - Bruce'a Schneiera (twórca BlowFish)

Wygrał Rijndael (89 punktów), drugi był SERPENT (59 punktów). Nie jest wykluczone, że najbezpieczniejszym szyfrem był SERPENT, ale był wolniejszy w działaniu od Rijndael.



Opis działania szyfru Rijndael/AES
Szyfr AES może operować na bloku o zmiennej długości, używając kluczy zmiennej długości. Oficjalna specyfikacja dopuszcza użycie bloków 128-, 192- lub 256-cio bitowych, szyfrowanych kluczami 128-, 192- lub 256-cio bitowymi. Dopuszczalne są wszystkie z 9 kombinacji.

Rijndael jest "iterowanym szyfrem blokowym", co oznacza, że blok wejściowy oraz klucz przechodzą wielokrotne RUNDY transformacji, zanim wyprodukują wynik. Po każdej rundzie, powstaje szyfr pośredni, zwany STANEM (State).



Reprezentacja danych
 W szyfrze Rijndael, zarówno blok jak i szyfr reprezentowane są przez macierze skonstruowane w następujący sposób:

1) elementem macierzy jest 8-bitów (bajt)


2) mają zawsze 4 wiersze
3) liczba kolumn wynosi tyle ile długość bloku podzielona przez 32:

Fazy i Rundy

Liczba rund (przebiegów transformacji) w szyfrze Rijndael jest określona w następujący sposób: klucz 128 – 10, 192 - 12, 256 - 14


 W przyjętej jako standard AES wersji szyfru Rijndael, ograniczono tę różnorodność do możliwości występowania zmiennej liczby kluczy, ale ustalono stałą wielkość bloku na 128 bitów. Wersje z różnymi długościami kluczy nawano AES-128, AES-192 oraz AES-256.

Szyfr AES/Rijndael składa się z trzech operacyjnych faz:



I. Transformacja klucza "AddRoundKey"

II. Nr-1 rund składających się z:
Transformacja SubBytes
Transformacja ShiftRows
Transformacja MixColumn
Transformacja AddRoundKey

III. Runda finałowa składająca się z:
Transformacja SubBytes
Transformacja ShiftRows
Transformacja AddRoundKey

Transformacja SubBytes
Transformacja "podstawienie bajtów" (substitute bytes) operuje na każdym bajcie stanu niezależnie i zmienia wartość tego bajtu. S-box (tabela podstawień - substitution box) kontroluje całą transformację. Operacyjnie, S-box to macierz 16*16. Bajt wynikowy odnajdywany jest pod adresem wiersza i kolumny uzyskanym za pomocą 4-bitowego adresu (młodsza i starsza połówka bajtu).

Można to przedstawić: s'i,j = S-box (si,j)

















Transformacja ShiftRows
Transformacja ShiftRows przesuwa cyklicznie bajty w 3 dolnych wierszach macierzy Stanu. Zgodnie z bardziej uogólnioną specyfikacją szyfru Rijandael'a, wiersze 2,3 i 4 są przesuwane cyklicznie o C1, C2 i C3 bajty, zgodnie z tabelą: 

Transformacja MixColumns
Transformacja MixColumn używa pewnej funkcji matematycznej do wykonania transformacji całej kolumny macierzy stanu. Działa ona w taki sposób, jakby wszystkie 4 bajty kolumny reprezentowały współczynniki pewnego wielomianu o czterech członach.

Można to zapisać tak: s'i,c = MixColumns (si,c)


Operacja ta polega na przemnożeniu wielomianu utworzonego z bajtów kolumny,

np. W(X) = s0,0*x+ s1,0*x+ s2,0*x+ s3,0
przez stały wielomian: C(X) = '03'*x+ '01'*x+ '01'*x+ '02'

Mnożenie to wykonywane jest modulo X4+1


W praktyce, operacja mnożenia wielomianów została zaimplementowana jako mnożenie macierzy S przez macierz C

Generacja klucza rundy i transformacja AddRoundKey
Klucz szyfrujący może być 128-, 192- lub 256-cio bitowy. Klucz szyfrujący używany jest wewnątrz algorytmu do otrzymania odrębnego klucza w każdej rundzie procesu szyfrowania. Klucze takie są zwane kluczami rundy i mają długość taką jak długość bloku danych.

Operacja AddRoundKey polega jedynie na wykonaniu operacji XOR w każdej rundzie pomiędzy całym blokiem a kluczem rundy.


Każde słowo W powyżej słowa wynikającego z długości klucza, np. powyżej W5 dla AES-192, powstaje poprzez oblicznia na podstawie wartości poprzedzających słów W:

KeyExpansion(byte Key[4*Nk] word W[Nb*(Nr+1)]){
    for(i = 0; i < Nk; i++)
        W[i] = (Key[4*i],Key[4*i+1],Key[4*i+2],Key[4*i+3]);
for(i = Nk; i < Nb * (Nr + 1); i++){
        temp = W[i - 1];
        if (i % Nk == 0)
            temp = SubByte(RotByte(temp)) ^ Rcon[i / Nk];
       W[i] = W[i - Nk] ^ temp;
}}

Funkcja SubByte zwraca 4 bajtowe słowo, w którym każdy bajt jest wynikiem zastosowania transformacji S-box.


Funkcja RotByte zwraca słowo, w którym bajty zostały poddane cyklicznej transformacji takiej, gdzie słowo (a,b,c,d) daje w wyniku słowo (b,c,d,a).
Pierwsze Nk słów powstaje bezpośrednio z Klucza.
Każde następne słowo W[i] powstaje poprzez zastosowanie XOR (oznaczony powyżej ^) poprzedniego słowa W[i-1] i słowa Nk pozycji wcześniej, W[i-Nk]. Dla słów na pozycjach będących wielokrotnością Nk, najpierw W[i-1] poddawane jest transformacji oraz dodawana jest pewna stała dla rundy (Round Constant - Rcon). Transformacja ta składa się z przesunięcia cyklicznego bajtów (RotByte) i zastosowaniem S-box'u - (SubByte)


©absta.pl 2016
wyślij wiadomość

    Strona główna