Pytania, które pojawiły się na egzaminie z “Ochrony danych” w roku 2006



Pobieranie 266,37 Kb.
Strona2/3
Data14.02.2018
Rozmiar266,37 Kb.
1   2   3

4. Omów algorytm DES.

DES – blokowy, symetryczny algorytm szyfrujący, ten sam klucz jest używany do szyfrowania jak i do deszyfrowania. szyfruje bloki złożone z 64 bitów, odpowiada to 8 literom ASCI. Klucze też składają się z 64 bitów, przy czym 8 z nich to bity parzystości, więc można określić w istocie tylko 56 bitów, reszta jest generowana automatycznie. W pierwszym i ostatnim kroku algorytm dokonuje permutacji. Szyfrowanie składa się z 16 rund. Dokonywane są te same obliczenia w każdej rundzie na wynikach z poprzedniej rundy i podklucza W1. Dane wejściowe rundy i+1 składają się z 2 ciągów 32 bitowych Li i Ri. Li+1=Ri, Ri+1=LiXORf(Ri,Ki+1), gdzie Ki+1 to podklucz. W każdej rundzie wykorzystuje się także S-Boxy, coś w rodzaju czarnej skrzynki, które przerabiającej 6 bitowe wejście na 4 bitowe wyjście. S-Box jest w zasadzie macierzą rozmiaru 4x16 wypełnioną w odpowiedni sposób (nie każde wypełnienie gwarantuje bezpieczeństwo) liczbami z przedziału (0-15). Pierwszy i ostatni bit z wejścia tworzą numer wiersza, zaś środkowe 4 numer kolumny, w tej sposób jest wybierana odpowiednia liczba z macierzy. Ponadto S-Box jest tak zbudowany, aby powodować efekt lawinowy. Deszyfrowanie to odtworzenie całego obliczenia składającego się na szyfrowanie od końca do początku.



5. Przedstaw wybrany protokół dzielenia tajemnic.

Protokoły dzielenia tajemnic:

- algorytm XOR

- algorytm Shamira

- algorytm Blackey

Najłatwiejszy jest algorytm oparty o funkcję XOR.

Wymaga on 100% frekwencji osób między które podzielona jest tajemnica.

M – wiadomość

A1 – Ak – osoby do podziału tajemnicy

1. Wybieramy k-1 losowych ciągów bitów R1, …, Rk-1

2. Liczymy R = M XOR R1 XOR R2 XOR … Rk-1

3. przydzielamy tajemnice Ai -> Ri, dla i należącego do {1, k-1}, Ak = R

R – odkrycie tajemnicy

R XOR R1 XOR R2 … XOR Rk-1 = M

6. Czego nauczył Cię Kerkhoff?

Zasady dobrej maszyny kryptograficznej.(Kerkhoff):

- system praktycznie nie do złamania,

- utajniony jest klucz, a nie sama budowa maszyny,

- klucz powinien być łatwy do zapamiętania,

- kryptogram łatwy do przekazania,

- maszyna szyfrująca łatwa do przenoszenia,

- system łatwy w użyciu.

7. Co to jest 'One-time pad'?

One-time pad – to sposób szyfrowania stosunkowo krótkich, ale bardzo ważnych informacji (rozkazy wojskowe). Szyfrowanie odbywa się za pomocą funkcji XOR, czyli jeśli ciąg znaków A to tekst jawny, a klucz to ciąg bitów B, to kryptogram to A XOR B. Kryptogram jest ciągiem losowym n bitów, a bez znajomości klucza żadna informacja dotycząca txt jawnego nie może być wydedukowana z kryptogramu. Deszyfrowanie odbywa się na 3 łatwych do sprawdzenia równościach : x XOR x=0, x XOR 0=x, x XOR (y XOR z) = (x XOR y) XOR z. Zasady używania: klucz uzgodniony zawczasu przez osoby komunikujące się i każdorazowo wybierany losowo, przechowywany w bezpieczny sposób, musi być co najmniej tak długi jak szyfrowany tekst. Każdy z tych warunków stwarza pewne niedogodności, po za tym klucz można ukraść fizycznie.

8. Przedstaw algorytm 3DES?

3DES – to algorytm polegający na zaszyfrowaniu wiadomości algorytmem DES trzy razy: 1) szyfrujemy pierwszym kluczem, 2) deszyfrujemy drugim kluczem 3) szyfrujemy trzecim kluczem. Użycie deszyfrowania jako drugiej fazy nie wpływa na siłę algorytmu (deszyfrowanie w DES jest identyczne jak szyfrowanie, tylko ma odwróconą kolejność rund), ale umożliwia używania 3DES w trybie kompatybilności z DES – za klucz pierwszy i drugi, lub drugi i trzeci przyjmujemy dowolny taki sam klucz, a za ostatni zwykły klucz DES.

3DES używa takich samych rozmiarów bloków oraz trybów jak zwykły DES, czyli 64 bity.

3DES z trzema różnymi kluczami (3TDES) ma siłę 168 bitów: trzykrotne szyfrowanie DES kluczem 56-bitowym (wliczając bit parzystości siła 3DES wynosi 192 bity), jednak ze względu na atak typu Meet-in-the-middle siła 3DES-a wynosi 2112.

Natomiast 3DES z dwoma kluczami (2TDES) ma siłę 112 bitów.

9. Na czym polega atak słownikowy na bazę haseł użytkowników i jak można się przed nim bronić?

Atak słownikowy - tworzony jest słownik najczęściej używanych „słabych” haseł – np. imiona, nazwy, login + jakieś cyfry), obliczane są dla nich wartości funkcji hashującej, następnie porównywane są one z hasłami zapisanymi w systemie. Dobry słownik może mieć nawet setki MB danych, więc jest to powolna metoda. Obronić się można przed tą metodą stosując losową „sól” dodawaną do funkcji hashującej, co zmniejsza podatność na złamanie hasła lub po prostu stosować w miarę długie i losowe hasła (litery duże i małe, cyfry oraz znaki specjalne).



10. Co to jest błąd przepełnienia bufora i jak jego unikać?

Przepełnienie bufora (ang. Buffer overflow) – błąd programistyczny polegający na pobraniu do wyznaczonego obszaru pamięci (bufora) większej ilości danych, niż zarezerwował na ten cel programista. Taka sytuacja może często prowadzić do zamazania danych znajdujących się w pamięci bezpośrednio za buforem, a w rezultacie do błędnego działania programu. W wielu sytuacjach, zwłaszcza gdy dane, które wpisywane są do bufora podlegają kontroli osoby o potencjalnie wrogich intencjach, może dojść do nadpisania struktur kontrolnych programu w taki sposób, by zaczął on wykonywać operacje określone przez atakującego. Przyczyną powstawania takich błędów jest najczęściej brak odpowiedniej wiedzy lub należytej staranności ze strony autora oprogramowania.

Błędu uniknąć można stosując powszechnie znane bezpieczne funkcje lub biblioteki funkcji, które biorą pod uwagę rozmiar przyjmowanych danych. Należy uważnie programować i kontrolować ilość danych wprowadzanych do bufora.

11. Korzystając z algorytmu Euklidesa oblicz największy wspólny dzielnik dla liczb 35 i 144.: 1

12. Omów przykład szyfru monoalfabetycznego poligraficznego.

Szyfr monoalfabetyczne:

Powiedzmy, że mamy alfabet ABCDEFGHIJKLMNOPQRSTUVWXYZ_. Jego przeciwdziedziną będzie pewna permutacja tego zbioru: _QWERTYUIOPASDFGHJKLZXCVBNM. W ten sposób otrzymujemy przyporządkowanie wzajemne jednoznaczne.

Nasza wiadomość, którą będziemy szyfrowali : OSIOLKOWI_DANO_OWIES. Robi się to w taki sposób, że w dziedzinie szuka się kolejnych liter i do tekstu zaszyfrowanego przepisuje się ich odpowiedniki z przeciwdziedziny.

Wynik tej operacji: FKIFAPFCIME_DFMFCIRK. Aby móc odszyfrować ta wiadomość należy stworzyć funkcję odwrotną.

Podstawową wadą szyfrów monoalfabetycznych jest ich niewielka skuteczność. Są one podatne na kryptoanalizę częstościową, która polega na "zgadywaniu" znaczenia pewnych liter na podstawie częstości ich występowania w szyfrowanym tekście w stosunku do statystyk dla języka.

Szyfr polialfabetyczny:

Szyfry polialfabetyczne (wieloalfabetyczne) znacznie utrudniają stosowanie tej techniki kryptoanalizy, gdyż jedna litera alfabetu jawnego może być zaszyfrowana na wiele sposobów, skutecznie "rozbijając" statystykę liter. Szyfr taki składa się z n przekształceń, takich że pierwszą literę szyfrujemy pierwszym przekształceniem, drugą drugim itd., po czym powtarzamy przekształcenia od początku począwszy od litery n + 1-wszej

Przykładem szyfru polialfabetycznego jest szyfr Vigenere’a oparty na następującej tablicy:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

B C D E F G H I J K L M N O P Q R S T U V W X Y Z A

C D E F G H I J K L M N O P Q R S T U V W X Y Z A B

D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

E F G H I J K L M N O P Q R S T U V W X Y Z A B C D

F G H I J K L M N O P Q R S T U V W X Y Z A B C D E

Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

Jak można zauważyć, każdy z wierszy tablicy odpowiada szyfrowi Cezara, przy czym w pierwszym wierszu przesunięcie wynosi 0, w drugim 1 itd. Aby zaszyfrować pewien tekst, potrzebne jest słowo kluczowe. Słowo kluczowe jest tajne i mówi, z którego wiersza (lub kolumny) należy w danym momencie skorzystać.

Przypuśćmy, że chcemy zaszyfrować prosty tekst, np.:

TO JEST BARDZO TAJNY TEKST

Do tego celu użyjemy znanego tylko nam słowa kluczowego, np. TAJNE

Na początku zauważamy, że użyte słowo kluczowe jest zbyt krótkie, by wystarczyło do zaszyfrowania całego tekstu, więc należy użyć jego wielokrotności. Będzie to miało następującą postać:

TO JEST BARDZO TAJNY TEKST

TA JNET AJNETA JNETA JNETA

Następnie wykonujemy szyfrowanie w następujący sposób: litera szyfrogramu odpowiada literze z tabeli znajdującej się na przecięciu wiersza, wyznaczanego przez literę tekstu jawnego i kolumny wyznaczanej przez literę słowa kluczowego, np. po kolei T i T daje M, O i A daje O itd. W efekcie otrzymujemy zaszyfrowany tekst:

MO SRWM BJEHSO CNNGY CROLT

Warto zauważyć, że tak naprawdę nie ma znaczenia, czy litera tekstu jawnego będzie wyznaczała wiersz, a słowa kluczowego kolumnę, czy na odwrót, efekt szyfrowania będzie zawsze taki sam.



13. Na czym polega i przed czym chroni protokół 'interlock'?

- wzajemne uwierzytelnianie, wykrywanie ataku Man-in-the-middle


- nie deszyfruje się klucza mając tylko połowę kryptogramu ( ½ krypto=> ½ tekstu jawnego)

1. A wysyła do B swój klucz publiczny i na odwrót

2. B szyfruje wiadomość tekstową za pomocą klucza publicznego A i wysyła pierwszą połowę kryptogramu

3. A otrzymuje ½ kryptogramu, tworzy swoja wiadomość tekstowa, szyfruje ją i tez wysyła do B ½ kryptogramu

4. B otrzymuje ½ kryptogramu od A i przesyła swoja drugą połowę

5. A otrzymuje druga połowę i deszyfruje klucz prywatny swoim, A sprawdza czy wiadomość ma sens, jak dobrze to kanał jest dobry, wiec wysyłamy 2 połowę do B

6. B deszyfruje ją, jeśli ma sens to dobrze.

Protokół Interlock chroni przed atakami typu Man-in-the-middle. Dla podsłuchującego możliwe jest przechwycenie treści kryptogramu, ale w zasadzie niemożliwe jest jego rozszyfrowanie. Teoretycznie istnieje możliwość oszukania tego protokołu, gdyby udało się wysłać obu komputerom klucz publiczny atakującego, lecz niemożliwym staje się przekazanie treści, która nie wywoływała by podejrzeń choć jednej ze stron komunikujących się ze sobą.



14. Przedstaw metodę generowania kluczy w algorytmie RSA.

1. Aby otrzymać parę kluczy (publiczny i prywatny) wybieramy dwie losowe, duże liczby pierwsze p i q

2. Wybieramy losowo klucz szyfrujący e taki, że e i (p-1)*(q-1) są względnie pierwsze (nie mają wspólnych dzielników).

3. Jeśli źle to powtarzamy losowanie e.

4. Wyznaczamy za pomocą algorytmu Euklidesa d będące odwrotnością e modulo (p-1)(q-1), tzn:

d = e-1 mod (p-1)(q-1)

5. Obliczamy iloczyn liczb pierwszych: n = p * q

6. Zapominamy liczby p i q i usuwamy je.

7. Liczby [e, n] tworzą klucz publiczny, zaś [d, n] są kluczem prywatnym.



15. Omów wybrany algorytm szyfrowania strumieniowego.

RC4 – jest popularnym szyfrem strumieniowym. Używany jest w protokołach, takich jak SSL oraz WEP. Pomimo, że RC4 jest odporny na kryptoanalizę liniową i kryptoanalizę różnicową to jest obecnie uznawany za niezbyt bezpieczny kryptosystem. RC4 generuje pseudolosowy strumień bitów. W celu zaszyfrowania wykonywana jest operacja XOR na tekście oryginalnym i strumieniu szyfrującym. W celu odszyfrowania analogicznie wykonywana jest operacja XOR na tekście zaszyfrowanym i strumieniu szyfrującym.

W celu wygenerowania strumienia szyfrującego wykorzystuje się tajny stan początkowy, składający się z dwóch części:

1. Permutacji 256-elementowej wszystkich możliwych stanów (oznaczanej później S).

2. Dwóch 8-bitowych wskaźników (oznaczanych "i" i "j").

Permutacja jest zainicjalizowana za pomocą klucza o długości zazwyczaj pomiędzy 40 i 256 bit (procedura inicjowania klucza). Następnie tworzony jest strumień bitów wyjściowych za pomocą algorytmu pseudolosowej generacji.

Elementy to: KSA (inicjalizacja rejestru na podstawie klucza o długości 40-128 bitów), PRGA (pseudolosowy generujący algorytm).

Procedura inicjalizacji klucza (KSA) jest używana w celu stworzenia początkowej permutacji liczb w 256-elementowej tablicy "S". Długość klucza jest wyznaczona poprzez liczbę bajtów w kluczu. Typowo wynosi pomiędzy 5 a 16 bajtów (pomiędzy 40 a 128 bitów).

Początkowo w tablicy "S" tworzona jest permutacja identycznościowa. Następnie "S" jest przetwarzane w 256 iteracjach (podobnie jak w algorytmie pseudolosowej generacji) i mieszane jednocześnie z bajtami klucza.

Algorytm pseudolosowej generacji (PRGA) modyfikuje stan tablicy S i generuje bajt strumienia szyfrującego tyle razy, ile wynosi długość tekstu oryginalnego. Za każdym razem algorytm zwiększa i o 1, dodaje do j wartość w S wskazywaną przez i, zamienia ze sobą wartości S[i] i S[j] oraz jako wynik daje wartość z S wskazywaną przez S[i] + S[j] (modulo 256). Każda wartość S jest zamieniana co najmniej raz na każde 256 iteracji.

16. Na czym polega i kiedy jest skuteczna kryptoanaliza lingwistyczno-statystyczna?

Kryptoanaliza statystyczna – zbiór metod kryptoanalitycznych opierających się na fakcie nierównomiernego występowania poszczególnych liter i sylab w językach naturalnych. Powoduje to również nierównomierny rozkład liter i zlepków literowych w tekście zaszyfrowanym. Na ataki z tej grupy podatne są szczególnie szyfry podstawieniowe.

Typowymi jej przykładami są: analiza entropii, analiza współinformacji, poszukiwanie kolizji. Kryptoanaliza statystyczna jest obecnie podstawowym narzędziem służącym sprawdzaniu jakości algorytmów szyfrujących.



18. Co to jest efekt lawinowy? Wyjaśnij na przykładzie funkcji skrótu.

Efekt lawinowy – to efekt, który jest realizowany między innymi w funkcjach skrótu, polega on na tym, że każda nawet najmniejsza zmiana w tekście jawnym powoduje, że funkcja skrótu zwraca całkiem inną wartość. Efekt ten jest bardzo pożądany, ze względu na możliwość kontroli zawartości tekstu jawnego pod kątem jego niezmienności.

19. Ile czasu zająłby atak brutalnej siły na hasło składające się z małych liter i cyfr o długości 6 znaków, jeśli system zezwala na jedną próbę w ciągu 1 sekundy? 36^6

20. Na czym polega uznaniowa polityka bezpieczeństwa? Jakie ma zalety, a jakie wady?

DAC – (ang. Discretionary Access Control) - sposób kontroli dostępu do obiektów w systemie plików. DAC pozwala użytkownikowi na całkowite ustalenie uprawnień dostępu do swoich zasobów. Kontrola dostępu do danych obiektów bazuje na sprawdzeniu tożsamości właścicieli/grup, do których on należy.

Podstawowy model bezpieczeństwa w większości systemów operacyjnych. Obiekty użytkownika i procesu domyślnie dziedziczą po nim prawa dostępu.



21. Oblicz wartość 28−1mod 75 (Co to znaczy x = y-1 mod n ?)

a

b

[a/b]

d

x

y

28 mod 75 = 1 = (-8) * 28 + 3 * 75

a−1mod b = x mod b = -8 mod 75 = 67


67 * 28 ≡1 (mod 75)

1876 ≡1 (mod 75) c.n.d.




28

75

-

1

-8

3

75

28

2

1

3

-8

28

19

1

1

-2

3

19

9

2

1

1

-2

9

1

9

1

0

1

1

0

-

1

1

0

22. Omów szyfr o nazwie “rot13”.

ROT-13 – to prosty szyfr przesuwny, polegający na zamianie każdego znaku alfabetu łacińskiego na znak występujący 13 pozycji po nim, przy czym wielkość liter nie ma przy przekształcaniu znaczenia. Najważniejszą cechą kodowania w porównaniu z innymi szyframi jest to, że sam jest swoją odwrotnością, to znaczy tej samej funkcji używa się do kodowania i dekodowania wiadomości.

Dla niektórych wyrażeń w języku polskim kodowanie ROT-13 nie spełnia swojego zadania. Przykładowo, tekst "hejnal urwany" po zakodowaniu brzmi "urwany hejnal".

23. Przedstaw metodę szyfrowania/deszyfrowania w algorytmie RSA.

Żeby wygenerować klucz RSA losujemy dwie duże liczby pierwsze p i q, oraz liczbę e względnie pierwszą z

(p − 1)(q − 1).

Następnie obliczamy d = e-1 mod (p - 1)(q - 1)

(ponieważ wybraliśmy względnie pierwsze e, ma ono odwrotność i obliczyć ją możemy szybko rozszerzonym algorytmem Euklidesa).

Obliczamy też n = p * q. Klucz publiczny to para (e, n), klucz prywatny zaś to para (d, n). Liczby p i q należy zniszczyć.



Szyfrowanie:

Żeby szyfrować podnosimy liczbę reprezentującą wiadomość do potęgi e modulo n:

c = me mod n

Deszyfrowanie:

Żeby ją zdeszyfrować podnosimy zaszyfrowaną wiadomość do potęgi d. Zgodnie z twierdzeniem Eulera dostaniemy oryginalną wiadomość (o ile m nie jest wielokrotnością p lub q):

cd = med = m mod n

Nie znając d nie potrafimy łatwo odzyskać wiadomości z kryptogramu. Nie znając faktoryzacji n na p i q nie znamy też prostej metody odtworzenia d z e.



24. Na czym polega tryb pracy CBC? Omów propagacje błędów.

CBC – ten sam blok txt jawnego jest szyfrowany w różnych miejscach w różny sposób. Wszystkie kolejne bloki kryptogamu są ze sobą powiązane – każdy blok tekstu jawnego jest przed zaszyfrowaniem XORowany z poprzednim blokiem kryptogramu. Natomiast pierwszy jest XORowany z losowym wektorem inicjalizującym.

Schematycznie: P – blok tekstu jawnego, C – blok kryptogramu.

DES ( P1 XOR IV ) = C1

DES ( P2 XOR C1) = C2

DES ( Pn XOR Cn-1 ) = Cn

Takie same bloki tekstu jawnego dają różne kryptogramy ze względu na losowy wektor inicjalizujący. Wadą jest iż nie można dodać lub usunąć żadnego bloku z kryptogramu. Propagacja błedów z przekłamania w jednym bloku ogranicza się do przekłamań przy deszyfrowaniu w tym bloku i następnym po nim.



26. Czy istnieje szyfr doskonały? Jak go sobie wyobrażasz?

… (pewnie tego nie będzie)



27. Porównaj algorytmy IDEA i DES.

DES - Data Encryption Standard

IDEA - International Data Encryption Algorithm

Standard USA do celów militarnych z lat 70

Europejska odpowiedź na DES z lat 90

Blokowy, blok długości 64 bitów

Blokowy, blok długości 64 bitów

Klucz 64-bitowy

Klucz 128-bitowy

Szybki w implementacji sprzętowej

Szybki w implementacji sprzętowej

Szyfrowanie:

- 16 rund (każda wykonywana jest na wynikach poprzedniej, ale z innym podkluczem)

- permutacja początkowa i końcowa (ustalona w standardzie)

- podklucze: ustalona metoda wyboru 16 podkluczy o długości 48 bitów z 56 bitowego klucza

- 8 sztuk S-Boxów.


Szyfrowanie:

- 8 rund: we/wy 4 bloki po 16 bitów

- przekształcenie końcowe

- klucz główny 128 bitowy, z którego generowane są podklucze 16 bitowe

- nie posiada S-Boxów.



28. Zaproponuj algorytm funkcji jednokierunkowej, określ jego podatność na kolizje.

… (pewnie tego nie będzie)



30. Omów macierzowy model opisu uprawnień.

Macierzowy model opisu uprawnień jest złożonym modelem kontroli dostępu opartym na opisie interakcji między dowolną kombinacją podmiotów i obiektów. Jest rozszerzeniem ACL.



31. W jaki sposób można rozszyfrować proste szyfry monoalfabetyczne?

Podstawową wadą szyfrów monoalfabetycznych jest ich niewielka skuteczność. Są one podatne na kryptoanalizę statystyczną, która polega na "zgadywaniu" znaczenia pewnych liter na podstawie częstości ich występowania w szyfrowanym tekście w stosunku do statystyk dla języka.



32. Opisz sposoby sprawdzenia, czy duża liczba p jest pierwsza.

Aby znaleźć wszystkie liczby pierwsze w zadanym przedziale liczbowym można posłużyć się algorytmem sito Eratostenesa: jeśli liczba naturalna N większa od 1 nie jest podzielna przez żadną z liczb pierwszych nie większych od pierwiastka z N, to N jest liczbą pierwszą.

Natomiast metoda, która daje odpowiedź na pytanie, czy dana liczba naturalna jest pierwsza, czy nie - nosi nazwę testu pierwszości. Wśród takich metod praktyczne zastosowanie mają testy probabilistyczne, to znaczy takie, które pozwalają określić pierwszość liczby z dostatecznie dużym prawdopodobieństwem np: test pierwszości Fermata, test pierwszości Millera-Rabina, test pierwszości Solovay-Strassena.

Millera-Rabina:

Wejście: n > 1: nieparzysta liczba naturalna do przetestowania; k: parametr określający dokładność testu

Wyjście: złożona jeśli n jest złożona, prawdopodobnie pierwsza jeśli nie uda się stwierdzić złożoności wylicz maksymalną potęgę dwójki dzielącą n − 1 i przedstaw n − 1 jako 2s*d;

powtórz k razy: wybierz a losowo z przedziału [1, n - 1]

jeśli ad <> 1 mod n i a2^r*d <> -1 mod n dla wszystkich r z przedziału [0, s - 1], zwróć wynik złożona

zwróć wynik prawdopodobnie pierwsza.



Solovay-Strassen:

Wejście: n: wartość do testu pierwszości; k: parametr określający dokładność testu



Wyjście: złożona jeśli n jest liczbą złożoną, w przeciwnym wypadku prawdopodobnie pierwsza

powtórzyć k razy:

wybierz losowo a z przedziału [1,n-1] x ←

jeżeli x = 0 lub a(n − 1)/2 mod n ≠ x wtedy zwróć złożona

zwróć prawdopodobnie pierwsza.



Fermata:

Działanie algorytmu polega na szukaniu pary liczb a i b takich że

n = a2 − b2.

Tę różnicę można przedstawić jako iloczyn (a + b)(a − b); Jeśli żaden z tych czynników nie jest równy jeden, otrzymujemy faktoryzację n. Warto zauważyć że dla każdego nieparzystego n istnieje taka para liczb. Jeśli n=cd, to

n = [(c + d) / 2]2 − [(c − d) / 2]2.

33. Udowodnij, że gdyby został znaleziony efektywny algorytm faktoryzacji (rozkładu iloczynu liczb pierwszych), to szyfrowanie RSA stałoby się bezużyteczne.

Posiadamy e. Na podstawie n uzyskujemy p i q, a następnie obliczamy d bezpośrednio odwracając równanie.

Co daje złamanie szyfrowania.

34. Na czym polega 'paradoks urodzinowy'? I jak może on zostać wykorzystany do ataku na MAC?

Paradoks dnia urodzin ma znaczenie w kryptografii i jest podstawą działania tzw. ataku urodzinowego; np. jeśli funkcje haszujące zwracają 2k możliwych odpowiedzi, to znalezienie kolizji, czyli dwóch takich wiadomości m1 i m2, że H(m1) = H(m2) wymaga sprawdzenia stosunkowo niewielkiej liczby kombinacji (c2k / 2, gdzie c jest stałą).

Celem ataku urodzinowego jest znalezienie kolizji funkcji hashującej. Jest to atak siłowy. U jego podstaw leży jednak paradoks dnia urodzin, który pozwala oczekiwać, że kolizja zostanie znaleziona znacznie szybciej niż sugerowałby to rozmiar przeciwdziedziny funkcji hashującej. Liczba potrzebnych do tego sprawdzeń rośnie bowiem proporcjonalnie do pierwiastka z liczby wszystkich możliwych wyników funkcji hashującej.

36. Przedstaw wybrany protokół podpisu cyfrowego (opisz wszystkie trzy czynności).

Niezaprzeczalny podpis elektroniczny to podpis cyfrowy spełniający warunki:

a) Weryfikacja podpisu jest możliwa jedynie przy współudziale autora podpisu

b) W przypadku sfałszowania podpisu jego właściciel ma możliwość udowodnienia fałszerstwa.



Przebieg algorytmu:

  1. p, q – liczby pierwsze, ponadto p = 2q + 1, G – zbiór liczb m < p zawierający q elementów postaci g2i mod p, takich że mq = 1 mod p, α – generator G

W celu wygenerowania klucza wybieramy losowo x < q i obliczamy β = αx mod p. Liczby p, α, β są podawane do wiadomości publicznej, a liczba x stanowi tajny klucz. Podpisywane mogą być liczby ze zbioru G.

2) Tworzenie podpisu: Podpis pod m należącym do G jest liczbą y = mx mod p.

3) Weryfikacja podpisu:

Osoba A wybiera losowe 2 liczby naturalne 0 < e1, e2 < q,

Oblicza c = ye1 βe2 mod p i wysyła do osoby B

Osoba B oblicza z = x-1 mod q oraz d = cz mod p i wysyła d do osoby A.



Osoba A sprawdza, czy d = me1 αe2 mod p

Jeżeli osoba B prawidłowo utworzyła podpis, to:

1   2   3


©operacji.org 2017
wyślij wiadomość

    Strona główna