OCHRONA DANYCH

Literatura:

Czechowski, Sienkiewicz, Przestępcze oblicza komputerów, PWN, Warszawa 1993;

D. E. Denning, Kryptografia i ochrona danych, Warszawa 1992;

D. Ferbrache, Patologia wirusów komputerowych, WNT, Warszawa 1993;

S. Garfunkel, G. Stafford, Practical UNIX and Internet Security;

J. Hrusek, Wirusy komputerowe i ochrona antywirusowa, WKT, Warszawa 1995;

B. Schneier, Kryptografia dla praktyków, WNT, Warszawa 1995;

B. Schneier, Ochrona poczty elektronicznej, WNT, Warszawa 1996;

J. Stokłosa, Algorytmy kryptograficzne, 1994;

J. Stokłosa, Kryptograficzna ochrona danych w systemach komputerowych, NAKOM, Poznań 1994;

J. Stokłosa (red.), Ochrona danych w systemach komputerowych, Poznań 1997;

Wprowadzenie.

Relacja między otoczeniem zewnętrznym a systemem komputerowym przedstawia się następująco:

Programy oddziałujące na otoczenie powinny być bezpieczne - tym zajmuje się inżynieria oprogramowania.

Na wykładach będziemy zajmować się oddziaływaniem otoczenia na systemy komputerowe i zabezpieczeniami stosowanymi w celu przeciwdziałania ”bezprawnemu” i niepożądanemu ich zniszczeniu

Dane są chronione (bezpieczeństwo danych) przed:

zniszczeniem;

ujawnieniem;

modyfikacją.

1. Przeciwdziałanie zagrożeniom (środki):

• prawne;

• organizacyjno-administracyjne - stworzenie takich warunków w firmie, aby dane były chronione; szkolenia pracowników; analiza ryzyka;

• fizyczne - ochrona pomieszczeń, sprzętu, infrastruktury, ochrona przed pożarem, powodzią itp. poprzez archiwizowanie danych, ochrona przed polem magnetycznym;

• techniczne - zasilanie, archiwizacja, nadmiarowość w systemie (macierze dysków), ochrona antywirusowa, kryptografia i ochrona danych.

Środki prawne:

• ustawa o prawie autorskim i prawach pokrewnych Dziennik Ustaw, 4 luty 1994 - program podlega ochronie ale nie algorytmy. W USA niektóre algorytmy są patentowane i w ten sposób chronione. Na podstawie powyższej ustawy ochronie podlega: program komputerowy, pewne rozwiązania zapisane w językach programowania, układ baz danych;

• prawo o ochronie danych osobowych (wchodzi w życie 1 styczeń 1998 r.) (dane niewrażliwe i wrażliwe (wyznanie religijne, poglądy polityczne, stan zdrowia, itp.; z naszego punktu widzenia ochrona tych danych jest bardzo ważna), ustawa dotyczy baz danych, w których przechowywane są dane osobowe) dane osobowe - każda informacja o danej osobie pozwalająca bezpośrednio lub pośrednio ustalić tożsamość tej osoby;

• ustawa o statystyce publicznej, Dziennik Ustaw, 25 czerwiec 1995 (upoważnia do zbierania przez ankieterów następujących danych do celów statystycznych: imiona i nazwisko, płeć, data i miejsce urodzenia, obywatelstwo, stan cywilny, data małżeństwa, adres zamieszkania; przy spisie ludności tylko ankieter zna odpowiedzi na konkretne pytania i nikt inny);

• ustawa o zwalczaniu nieuczciwej konkurencji, Dziennik Ustaw, 16 kwiecień 1993 (czyn nieuczciwej konkurencji to działanie przeciw prawu lub dobrym obyczajom);

• ustawa o rachunkowości, Dziennik Ustaw, wrzesień 1994;

• ustawa o ochronie topografii układów scalonych, Dziennik Ustaw, październik 1992;

• ustawa o wynalazczości, tekst ujednolicony - 17 marca 1993 (nie można opatentować programów i algorytmów, ale można opatentować układ realizujący określony algorytm; trwa przez 20 lat od momentu zgłoszenia patentu);

• ustawa o tajemnicy służbowej i państwowej (jako pracownicy firm jesteśmy zobowiązani do przestrzegania tajemnicy służbowej (określa przełożony) i państwowej;

• ustawa o zasadach szczególnej kontroli obrotu z zagranicą towarami i technologiami 12 grudzień 1993 (państwo może chcieć wiedzieć kto i do jakich celów użytkuje: urządzenie poligraficzne, kryptograficzne, itp.

• W nowym kodeksie karnym występują zapisy o bezpieczeństwie i ochronie informacji (osobny rozdział).

§ 267 Bezprawne uzyskiwanie informacji.

§ 268 Udaremnianie uzyskiwania informacji.

§ 269 Niszczenie zapisów szczególnego znaczenia.

§ 265 Ujawnienie tajemnicy państwowej.

§ 285 Podłączenie się do urządzeń telekomunikacyjnych.

Atrybut danych jest to stopień ochrony jakiej mają te dane podlegać.

Dane można podzielić na: jawne, poufne oraz poufne szczególnego znaczenia.

Poufność danych jest to prawo jednostki do tego z kim chce się podzielić posiadanymi danymi oraz do tego od kogo chce przyjąć informacje.

Autentyczność danych - identyfikacja, uwierzytelnianie.

Przestępstwo komputerowe jest to:

• wszelkie zachowanie przestępcze związane z funkcjonowaniem systemu elektronicznego, a w szczególności z przechowywanymi w nim danymi oraz dostępem do programów z prawami autorskimi;

• wykorzystanie systemu informatycznego do popełniania przestępstw.

Minimalny zbiór czynów uznanych przez Radę Europy za przestępstwa komputerowe:

oszustwa związane z wykorzystaniem komputera (finansowe);

fałszerstwa z wykorzystaniem komputera (fałszywe pieniądze);

niszczenie danych i programów komputerowych;

sabotaż komputerowy (fizyczne niszczenie);

włamania do systemów komputerowych (hacking);

nieuprawnione przechwytywanie informacji (w sieciach);

bezprawne kopiowanie i rozpowszechnianie programów komputerowych prawnie chronionych;

bezprawne kopiowanie topografii układów półprzewodnikowych.

1. Fakultatywny zbiór czynów uznanych przez Radę Europy za przestępstwa komputerowe:

modyfikacja danych lub programów komputerowych;

szpiegostwo komputerowe;

używanie komputerów bez zezwolenia (wykorzystywanie czasu jałowego procesora);

d) używanie prawnie chronionego programu komputerowego bez zezwolenia.

Powyższe zestawy zostały stworzone przez komitet ekspertów dla Rady Europy.

Ochrona dostępu.

W systemach komputerowych ochrona dostępu jest realizowana przez identyfikację użytkownika za pomocą hasła. Hasło jest ciągiem znaków wprowadzanych przez użytkownika z konsoli (Novell: 4-20, UNIX najczęściej 8). Po wprowadzeniu hasła system sprawdza jego prawidłowość na podstawie pliku, w którym hasła są przechowywane w postaci zaszyfrowanej. Szyfrowanie polega na podaniu ciągu znaków - hasła, jako parametr funkcji szyfrującej f. Funkcja ta charakteryzuje się tym, że obliczenie wartości funkcji odwrotnej do f jest bardzo trudne. Administrator systemu posiada narzędzia umożliwiające wykrycie haseł „słabych” w systemie, czyli haseł łatwych do odgadnięcia, np. takich, które znajdują się w słownikach. Hasło modyfikowane przez użytkownika jest również sprawdzane przez system operacyjny. Sprawdzane jest czy hasło to jest różne od poprzednich haseł i czy wprowadzone słowo jest nietrywialne. Istnieje również możliwość wygenerowania losowego hasła przez system operacyjny.

Czas bezpiecznego stosowania hasła określony jest wzorem:

,

co w praktyce daje wzór:

,

gdzie:

|A| - liczba liter alfabetu, którym się posługujemy,

h - długość hasła,

z - liczba znaków wymienianych między systemem a użytkownikiem przy rozpoczynaniu sesji,

v - prędkość przesyłania znaków;

Przykład:

Jeśli |A|=95, h=6 zn, z=20, v=9600 zn/s to , dla |A| = 26 T = 30dni.

Wniosek: należy korzystać ze wszystkich dostępnych znaków.

Prawdopodobieństwo złamania hasła.

P - prawdopodobieństwo znalezienia właściwego hasła (pożądane),

P₀ - najmniejsza wartość prawdopodobieństwa obliczana jako stosunek

t - czas dokonywania systematycznych prób łamania (miesiące ciągłej pracy komputera),

n₁ - liczba haseł, które można złamać w ciągu m miesięcy obliczana jako stosunek ,

n₂ - liczba wszystkich możliwych haseł (|A|^h).

Pozostałe oznaczenia jak wyżej.

P₀ można więc obliczyć następująco:

Stąd wynika, że powinno być:

Z tego wzoru wyznacza się h, np.: dla m = 3 miesiące, P = 10^-6, v=1200zn/s, z=20zn:

|A| = 26 => h = 11, a dla |A| = 95 => h = 8.

Wprowadza się mechanizmy zniechęcania intruzów takie jak: zwiększanie czasu między kolejnymi nieudanymi próbami dostania się do systemu. Algorytm dostępu do systemu może wyglądać np. tak:

W niektórych systemach tworzone są listy haseł. Dla poszczególnych sesji używa się kolejnego hasła z listy.

Łatwo jest również obliczyć wartość funkcji szyfrującej F(F(x) ), F(F(F(x))), ... , Fⁿ(x). Wykorzystuje się to w sposób następujący (przykład dla n=1000): po wprowadzeniu hasła przez użytkownika system porównuje je z plikiem hasłowym i jeśli jest prawidłowe wprowadza do tego pliku postać F⁹⁹⁹(x) hasła. Przy następnym wejściu do systemu następuje ponowne sprawdzenie hasła i jeśli jest poprawne do pliku wprowadzana jest postać F⁹⁹⁸ hasła, itd. Każde nowe hasło niszczy poprzednie.

Zasilanie komputerów.

Sprzęt komputerowy powinien być podłączony z oddzielnym bezpiecznikiem z oddzielnej sieci.

Zasilanie elektryczne komputera powinno być pozbawione takich zjawisk jak:

spadki napięcia - 84%,

zaniki napięcia - 5%

wahania częstotliwości ,

przepięcia - 1%,

zakłócenia impulsowe (pojawianie się pików),

zakłócenia komutacyjne (iskrzenie) - 7%,

zakłócenia radiowe (wysokiej częstotliwości) - 2%,

zniekształcenia nieliniowe (kształtu sinusoidy),

pojawienie się składowej stałej.

Zakłócenia 4, 6, 7 można wyeliminować przy pomocy dławika dolnoprzepustowego separującego sieć energetyczną od komputera (listwy zasilające np.: Acar, Liza, itp.). Spadki napięcia można wyeliminować przy użyciu autotransformatorów (np. LineR firm APC). Żadne jednak z tych urządzeń nie pozwala pracować na komputerze przy całkowitym zaniku napięcia. Do ich wyeliminowania służą urządzenia zasilania awaryjnego potocznie nazwane UPS (ang. Uninterruptable Power Supply). Pozwalają one wyeliminować też pozostałe zakłócenia.

UPS off-line:

W momencie gdy płynie prąd jest on przepuszczany tylko przez filtr, w przypadku zaniku napięcia układ sterowania przełącza przełącznik.

Wady:

• musi się on przełączać w tryb awaryjny

• jeśli osiągnie dolny próg np. 190V, to nie wie co zrobić, co chwilę włącza się i wyłącza, co bardzo szybko rozładowuje baterie

• impuls w czasie przełączania jest szkodliwy dla komputera

Zalety: cena.

UPS on-line:

Prąd jest cały czas podawany na baterie. Bateria musi być wysokiej jakości, bo jest ciągle ładowana i rozładowywana. Gwarantują izolację galwaniczną. Są w stanie zrównoważyć obniżone napięcie nawet do 70V. Technologia bardzo droga.

Zasilacze hybrydowe - nie mają przełącznika na wyjściu, lecz falownik zasilany prądem stałym z prostownika w trybie normalnym i z baterii w trybie awaryjnym.

Parametr	Zasilacz idealny	Off-line	on-line
Stabilizowanie napięcia	Tak	Nie lub skokowo	Tak
Stabilizacja częstotliwości	Tak	Nie	Tak
Tolerancja napięcie we.	0-µ	187V-242V	130V-250V
Zniekształcenie przebiegu	Brak	Tak	<2%
Tłumienie zniekształceń sieciowych	Tak	Nie lub częściowo	Tak
Izolacja galwaniczna	Tak	Nie	Tak
Praca przy częstych zanikach	Tak	Nie	Tak
Masa i wymiary	1	1	1,5

Charakterystyka zasilaczy.

Moc zasilaczy mierzymy w volto-amperach (VA), przelicznik VA*cosj ->W zależy od firmy (cosj należy do przedziału: 0,6-0,9). Czas podtrzymywania gwarantowany przez większość UPS-ów wynosi ok. 15min. W razie potrzeby ciągłej pracy stosowana jest kombinacja: UPS + generator. Generator nie musi być tej samej mocy co UPS.

Metody kryptograficzne (krypto grafos - grec. ukryte pismo)

Symetryczny system kryptograficzny (klasyczny, konwencjonalny, z tajnym kluczem) :

Klucz deszyfrujący nie powinien być istotnie różny od szyfrującego (w 99% takie same). Jeżeli się różnią to do różnicy można dojść w czasie wielomianowym.

Asymetryczny system kryptograficzny (publiczny, z publicznym kluczem) :

zaszyfrować może każdy, odszyfrować tylko posiadacz klucza k*.

Warunki na to, aby system kryptograficzny był bezwarunkowo bezpieczny:

Klucz musi być stosowany jednokrotnie.

Klucz musi być co najmniej tak długi jak szyfrowana wiadomość.

Klucz musi być losowy.

Nic nie można powiedzieć o kluczu obserwując kryptogram.

System kryptograficzny jest obliczeniowo bezpieczny jeżeli :

używamy funkcji jednokierunkowej.

Def. Funkcja jednokierunkowa (one-way function)

f : X Y

dla każdego x należącego do X - wartość f(x) wyznacza się w czasie wielomianowym

dla każdego y należącego do Y - wartość f ^-1(y) wyznacza się w czasie wykładniczym, nawet jeżeli funkcja f jest znana

Dotychczas nie udowodniono, że istnieje chociaż jedna funkcja jednokierunkowa.

Funkcje uważane za jednokierunkowe :

rozkład liczby na czynniki pierwsze

Łatwo jest pomnożyć dwie długie liczby przez siebie, trudno jest je rozłożyć na czynniki pierwsze. Na razie najdłuższa liczba jaką udało się rozłożyć to liczba 130-cyfrowa.

2. y = x² mod n

też używa się liczb rzędu 100 cyfr

3. y = a^x mod n

też używa się liczb rzędu 100 cyfr

Kryptoanalityka:

Atak na tekst zaszyfrowany — dysponowanie tylko szyfrogramem;

Atak poprzez tekst częściowo znany — wiadomo, że pewne słowa zostały użyte;

Atak poprzez wybrany tekst jawny — kryptoanlityk może posłać coś do deszyfratora i obejrzeć wynik;

Atak poprzez wybrany tekst zaszyfrowany

Algorytmy kryptograficzne = szyfry.

Szyfry przestawieniowe.

1) można wykorzystać schemat :

macierz

tekst jawny figura geometryczna tekst zaszyfrowany

matryca

np. : (zapisujemy rzędami, odczytujemy kolumnami)

P	R	Z	E
S	T	A	W
I	E	N	I
O	W	Y	*

PSIO RTEW ZANY EWI*

2) inny rodzaj przestawiania (wykorzystanie klucza)

m = WLAZŁ KOTEK NA PŁOTEK I MRUGA ŁADN

k = MARYSIA

Zapisujemy klucz (słowo MARYSIA) a pod nim cyfry (kolejność jak w alfabecie, jeżeli litery w słowie się powtórzą to pierwsza ma mniejszy numer) :

Cyfry wyznaczą kolumny.

Następnie zapisujemy poniżej tekst jawny wierszami, tak żeby pisząc w wierszu o numerze x nie przekroczyć kolumny o numerze x.

M A R Y S I A

4 1 5 7 6 3 2

1 W L

2 A Z Ł K O T E

3 K N A P Ł O

4 T

5 E K I

6 M R U G A

7 Ł A D N

Po takim zapisaniu odczytujemy kolumnami (najpierw pierwsza kolumna, potem druga ...)

c = LZNKRA E TO WAKTEMŁ ŁAIUD OŁA KPGN

W rzeczywistym szyfrogramie spacje są usuwane.

Szyfry podstawieniowe (klasa bardzo bogata w przykłady). f : a β

(26 znaków)

α	A B C D E F G H I ... Z
β	Z O S I A B C D E ... Y

m = A B B C D I A

c = Z O O S I E Z

szyfr Cezara.

n - liczba liter w alfabecie

k - przesunięcie

szyfrowanie : c=(m+k) mod n

np. : n = 27

k = 3

m = Z A P I E K A N K A

c = C D T L H N D R N D

Jest to przykład „czystego” szyfru Cezara, w którym występuje przesunięcie liter o trzy.

3)

szyfrowanie : c=(m*k) mod n

np.: n = 27

k = 3

m = 1 2 9 10 ( 1 * 3 ) mod 27 = 3 itd...

c = 3 6 0 3

Ponieważ to przekształcenie jest niejednoznaczne (kłopoty podczas deszyfracji), trzeba nałożyć warunki :

NWD (k,n) = 1

np.: n = 27

k = 7

m = 2 3 4 5 6 ( 2 * 7 ) mod 27 = 14 itd...

c = 14 21 1 8 15

Jak obliczyć z powrotem m?

m=(c*k ^-1 ) mod n

UWAGA ! to jest arytmetyka modularna, taka że :

( a ^-1 * a ) mod n = 1

np.: dla n = 27

7 ^-1 = 4 bo ( 7 * 4 ) mod 27 = 1

5 ^-1 = 11 bo ( 5 * 11) mod 27 = 1

funkcja Eulera : ϕ: NN

ϕ(n) = ilość liczb mniejszych od n, względnie pierwszych z n.

Dwie liczby p i q są względnie pierwsze jeżeli NWD(p,q)=1.

N	ϕ(n)	liczby mniejsze od n, względnie pierwsze z n
1	0	-
2	1	1
3	2	1, 2
4	2	1, 3
5	4	1, 2, 3, 4
6	2	1, 5
7	6	1, 2, 3, 4, 5, 6
8	4	1, 3, 5, 7
9	6	1, 2, 4, 5, 7, 8

Własności funkcji Eulera :

1) Jeżeli p jest liczbą pierwszą to :

ϕ(p)=p-1

ϕ(p^a)=p^a-1(p-1)

2) Jeżeli p i q są liczbami pierwszymi to :

ϕ(pq)=(p-1)(q-1)

3) Jeżeli p₁, p₂, ... , p_n są względnie pierwsze to :

ϕ(p_1, p_2, ..., p_n)=ϕ(p₁)ϕ(p₂) ... ϕ(p_n)

Algorytm obliczania a^t mod n aÎ{0,1,2,...,n-1}, t- liczba całkowita dodatnia.

Trzeba rozłożyć t na postać dwójkową : t=t _j*2 ^j+t _j-1*2 ^j-1+...+t ₁*2+t ₀

i zastosować algorytm:

w := 1

for i = j downto 0 do

begin

w := w² mod n

if t _i = 1 then w := (w * a) mod n

end

write (w) // w = a^t mod n

a^-1 mod n = a^{ϕ(n) - 1} mod n

Przykład ( przy obliczaniu wykorzystano własność funkcji Eulera):

ϕ (27) = ϕ (3³) = 3² * (3-1) = 18

7^-1 mod 27 = 7¹⁷ mod 27

t = 17 = 10001b

i=4, w=1, w=1*7 mod 27=7;

i=3, w=7² mod 27=22;

i=2, w=22² mod 27=484 mod 27=25;

i=1, w=25² mod 27=625 mod 27=4;

i=0, w=4² mod 27=16, w=16*7 mod 27=112 mod 27=4

Szyfry homofoniczne (wieloznaczeniowe)

homonimy morze może

Bóg Bug buk

f : a 2^B

Znaki alfabetu jawnego zastępujemy homofonami. Jednemu znakowi przypisujemy od 1 do kilku homofonów. Wtedy wiadomość jawną można zapisać na różne sposoby (prowadzi to do tego, że przestaje działać analiza częstotliwości występowania liter). Jeśli ktoś złamie szyfr to nie wie, którą wiadomość odszyfrował.

Przykład :

Alfabet jawny	Homofony
A	c, 9, $
B	X, g, 0, 8
C	s, t, 6, j

Wiadomość jawną m = ABBAC można zapisać różnie :

m = A B B A C

c 0 g $ j

9 0 0 $ 6

$ g X 9 s

Szyfry polialfabetyczne (wieloalfabetyczne)

Jeden alfabet wejściowy, wiele alfabetów wyjściowych. Korzystają ze zbioru przekształceń:

{f_i : aB_i}

W praktyce korzystamy ze znanych przekształceń i korzystamy z nich wielokrotnie.

Szyfr Veginre

c = (m + k_i) mod 27 i = {1,2,3,4,5}

Przykład : k = NARTY

m = A B B C X O U R S A V

k = N A R T Y N A R T Y N

O C T ...

Łamanie: indeks koincydencji, badanie okresu klucza.

Szyfr Vernama (1917 r.)

Szyfr ten zachowuje się tym lepiej im dłuższy jest okres klucza (np. 10¹⁰⁰). Klucz wygenerowany przez rejestr przesuwny ma dobre właściwości statystyczne. Klucz jest pseudolosowy, stosowany jednokrotnie. Szyfr ten jest dość wolny, ale przy spełnieniu podkreślonych warunków jest szyfrem bezwarunkowo bezpiecznym.

Szyfry wieloliterowe

Jednocześnie przekształca się wiele znaków.

Szyfr Playfair'a

Stosowano 25 znaków alfabetu. Klucz - układ znaków w tablicy (wygenerowany losowo), ilość możliwych kluczy 25!

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

Każdą parę liter tekstu jawnego m₁m₂ szyfruje się wg następujących reguł:

Jeśli m₁ i m₂ znajdują się w tym samym wierszu, to c₁ i c₂ są znakami z prawej strony m₁ i m₂, przy czym pierwszą kolumnę traktuje się jako położoną na prawo od ostatniej kolumny.

Jeśli m₁ i m₂ znajdują się w tej samej kolumnie, to c₁ i c₂ są znakami położonymi poniżej m₁ i m₂, przy czym pierwszy wiersz traktuje się jako położony pod ostatnim wierszem.

Jeśli m₁ i m₂ znajdują się w różnych wierszach i kolumnach, to c₁ i c₂ są brane z przeciwległych rogów prostokąta wyznaczonego przez m₁ i m₂, przy czym c₁ pochodzi z wiersza zawierającego m₁, c₂ zaś - z wiersza zawierającego m₂.

Jeśli m₁=m₂, to do tekstu jawnego między te litery wstawia się nieznaczącą literę (np. X), co eliminuje powtórzenia.

Jeśli tekst jawny ma nieparzystą liczbę znaków, to na końcu tekstu jawnego dopisuje się nieznaczącą literę.

np. :

m = U N I W E R S Y T E T X X - znak pusty

c = I E O A K I H G I X G Z

2) Hill 1929

przekształca liczbę liter o długości t na tyle samo liter

Ogólnie :

c = (K * m ) mod n

Przykład t = 2

m = m₁ c = c₁ K = k₁₁ k₁₂

m₂ c₂ k₂₁ k₂₂

c₁ = ( k₁₁ m₁ + k₁₂ m₂ ) mod n jeśli t = 3 to 3 równania itd...

c₂ = ( k₂₁ m₁ + k₂₂ m₂ ) mod n

Łatwe do złamania, wystarczy przechwycić cztery pary (m,c). Wiedząc, że c=K*m mod n

można wyznaczyć K=cm^-1 mod n.

Deszyfracja następuje za pomocą macierzy odwrotnej K^-1.

D_K(c)=K^-1c mod n=K^-1Km mod n=m, przy czym:

K^-1K mod n=I (macierz jednostkowa).

Szyfry produktowe (kaskadowe)

produkt funkcji - złożenie funkcji

Enigma (lata 20-te)

1919 - maszyna szyfrująca do celów handlowych, wycofana po pewnych zmianach do celów wojskowych

1929 - kurs kryptologów w Poznaniu

Rajewski, Różycki, Zygalski - złamali Enigmę w 1930 r.

Maszyna powstała w Niemczech

Składała się z 5 do 8 walców (wirników) każdy z nich permutował 26 elementów - na wejście walca wchodziło 26 cyfr i wychodziło w zmienionym, przypadkowym porządku.

Połączenie kilku takich walców dawało dużo kombinacji.

Kluczem było początkowe ustawienie walców.

Jakie błędy popełnili Niemcy ? Te same słowa na początku i końcu komunikatów, przesyłanie klucza tym samym kanałem, którym przesyłali wiadomość.

Lucifer (lata 70-te IBM)

Wykonywane są na przemian podstawienia S_i i permutacje P_i. Każde podstawienie S_i jest funkcją klucza K.

P - permutacja

s - skrzynka

Działanie skrzynki s (uproszczony schemat dla dwóch wejść) :

Dla każdej skrzynki są ustalone dwie możliwe permutacje (ustawienie 0 lub 1).

Klucz to podanie ustawienia dla wszystkich skrzynek (jest ich 32 * 16 = 512). Klucz jest jednak 128 - bitowy, powielony do 512 bitów

Algebraiczna postać normalna funkcji boolowskiej :

Funkcja liniowa:

Przykład:

x1	x2	f(x1,x2)=a1x1⊕ a2x2
0	0	f(x1,x2)=0
0	1	f(x1,x2)=x1
1	0	f(x1,x2)=x2
1	1	f(x1,x2)=x1x2

Funkcja afiniczna:

2ⁿ⁺¹ — liczba wszystkich funkcji afinicznych n-argumentowych

— liczba wszystkich funkcji boolowskich

Nieafiniczną funkcję boolowską nazywamy funkcją nieliniową. Rzędem nieliniowości funkcji boolowskiej nazywamy liczbę zmiennych w najdłuższym iloczynie ze współczynnikiem 1.

Funkcja 4-go rzędu

Przy n wejściach skrzynka może realizować n funkcji boolowskich. Żeby szyfr był dobry muszą one być nieliniowe (patrz wyżej).

Dla skrzynek S :

- 2 wejścia - wszystkie funkcje są liniowe

- 3 wejścia - 3% funkcji liniowych

- 4 wejścia - wszystkie funkcje są nieliniowe (dlatego skrzynki są w Luciferze 4-wejściowe).

DES - rozwinięcie Lucifera

NBS (dzisiaj NIST - National Institution of Standard and Technology) ogłosiła konkurs na szyfr blokowy

Wygrał IBM, w 1997 r DES został uznany za standard w USA.

DES pracuje na 64-bitowych blokach tekstu jawnego. Po początkowej permutacji blok wejściowy jest dzielony na lewą i prawą połowę, każda o długości 32 bitów. Następnie jest wykonywanych 16 cykli jednakowych operacji, nazywanych funkcjami f, w czasie których dane są łączone z kluczem. Po szesnastym cyklu lewa i prawa połowa są łączone z kluczem. Po szesnastym cyklu lewa i prawa połowa są łączone i końcowa permutacja (będąca odwrotnością permutacji początkowej) kończy przebieg algorytmu.

Klucz ma długość 56 bitów. (Zwykle klucz jest zapisany za pomocą 64 bitów, przy czym każdy co ósmy jest bitem parzystości, który jest pomijany). Kluczem może być dowolna liczba o długości 56 bitów, która może być zmieniona w dowolnej chwili. Kilka z tych liczb jest uważane za klucze słabe, lecz mogą one być pominięte. Całe bezpieczeństwo spoczywa na kluczu.

W każdym cyklu bity klucza są przesuwane, a następnie jest wybierane 48 bitów z 56 bitów klucza. Prawa połowa bloku danych jest rozszerzona do 48 bitów za pomocą permutacji z rozszerzeniem, łączona za pomocą poelementowej sumy modulo 2 z 48 bitami przesuniętego i spermutowanego klucza, jest dokonywane podstawienie bloku 32 nowych bitów za pomocą algorytmu podstawiania, a potem jeszcze raz jest dokonywana permutacja. Te cztery operacje tworzą funkcje f. Ciąg wyjściowy funkcji f jest dalej łączony z lewą połową za pomocą poelementowej sumy modulo 2. Wynikiem tych operacji jest nowa lewa połowa bloku; stara lewa połowa staje się nową prawą .

Permutacja początkowa dokonuje transpozycji bloku wejściowego np.:

58	50	42	34	26	18	10	2	60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6	64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1	59	51	43	35	27	19	11	3
61	53	45	37	29	21	13	5	63	55	47	39	31	23	15	7

Jeden krok algorytmu wygląda następująco :

L_i+1 = R_i R_{i =} L_i+1

R_i+1 = L_i ⊕ f (R_i , k_i) L_{i =} R_i+1 ⊕ f (R_i , k_i)

Szyfrowanie i deszyfrowanie następuje w tą samą stronę (przy deszyfrowaniu zamieniana jest kolejność kluczy - w 1-ej iteracji wybieramy K₁₆, potem K₁₅ itd., aż do K₁).

Schemat całego algorytmu + schemat generowania kluczy cząstkowych :

Liczba możliwych kluczy to 2⁵⁶.

Średnia liczba bezpiecznych kluczy przy ataku brutalnym (całościowe przeszukiwanie to 2⁵⁴).

Kryptoanaliza różnicowa (zakłada możliwość wykonania eksperymentu - przesyłania wiadomości jawnej i odczytania zaszyfrowanej) pozwala zmniejszyć przestrzeń bezpiecznych kluczy do 2⁴⁷. Dokonuje się jej przez wprowadzenie dwóch wejść różniących się o ustaloną liczbę bitów i obserwuje wyjście.

Analiza liniowa (również atak przez tekst jawny) pozwala zmniejszyć przestrzeń bezpiecznych kluczy do 2⁴³ - to już nie jest bezpieczna liczba (można złamać w kilka dni).

Rozwiązaniem jest częste zmienianie kluczy.

Gdyby klucz był 128 - bitowy, byłoby 2¹²⁸ kluczy - nie do złamania (dzisiaj).

W przypadku DESA znane są cztery klucze słabe(k₁=k₂) i sześć półsłabych (k₁<> k₂) takie, że :

triple DES - odmiana DES'a :

W 1980 r. ISO zaproponowała DES jako standard międzynarodowy DEA-1.

Amerykanie sprzeciwili się żeby ten szyfr został standardem - do zeszłego roku można było importować do USA urządzenia szyfrujące z kluczem do 40 bitów (DES ma klucz o długości 64).

FEAL - N

Algorytm wykorzystuje 64-bitowe bloki i 64 lub 128 - bitowy klucz. Zamiarem jego twórców było opracowanie algorytmu podobnego do DES, lecz takie, żeby każdy cykl był mocniejszy niż w DES. Algorytm taki, składający się z mniejszej liczby cykli, byłby szybszy.

(Fast Encipherment Algorithm, japońska firma NTT)

Podstawowy krok jak w DESie :

Liczbę kroków N ustala użytkownik.

N>= 4

Zalecane, żeby N było parzyste, a najlepiej 2^x.

Realizację algorytmu rozpoczyna się od 64- bitowego bloku danych (może to być zarówno tekst jawny jak i szyfrogram ). Najpierw blok danych jest sumowany modulo 2 z 64 bitami klucza. Następnie blok danych jest dzielony na lewą i prawą połowę. Lewa jest sumowana modulo 2 z prawą, tworząc nową prawą połowę, i te dwie połowy przechodzą przez N cykli (na początku przez cztery). W każdym cyklu prawa połowa jest łączona z szesnastoma bitami klucza (przy użyciu funkcji f) i sumowana modulo 2 z lewą połową, tworząc nową prawą połowę. Oryginalna prawa połowa (sprzed rozpoczęcia cyklu) tworzy nową lewą połowę. Po N cyklach (nie należy zamieniać lewej i prawej połowy po N cyklach) lewa połowa jest sumowana modulo 2 z prawą połową, formując nową prawą połowę, a następnie lewa i prawa połowa podlegają konkatenacji i tworzą jeden 64-bitowy blok. Blok ten jest sumowany modulo 2 z 64-bitowym blokiem klucza i na tym realizacja algorytmu się kończy.

N - liczba iteracji w algorytmie

funkcja f

Realizacja funkcji f polega na pobieraniu 32 bitów danych oraz 16 bitów klucza i mieszaniu ich. Najpierw blok danych jest dzielony na części po 8 bitów, które są następnie sumowane modulo 2 i zastępowane każdy każdym, aż osiągną stan wyjściowy. Występujące tam funkcje są zdefiniowane następująco:

S₀(a_, b)= przesunąć cyklicznie w lewo 2 bity ((a + b) mod 256)

S₁(a, b)= przesunąć cyklicznie w lewo 2 bity ((a + b + 1) mod 256)

Ten sam algorytm może być użyty zarówno do szyfrowania jak i do deszyfrowania. Różnica polega na odwrotnej kolejności podawania klucza.

Układ służący do generowania kluczy jest podobny.

Kryptoanaliza różnicowa

przy czterech krokach 8 kluczy (wystarczy zbadać)

8	128
12	2^21
16	2^29
20	2^37
24	2^45
28	2^56
30	2^60
32	2^63

wniosek: liczba kroków co najmniej 32

IDEA - International Data (Encryption) Encipherment Algorithm

Odporność na analityki kryptograficzne - nie jest znana metoda nawet ograniczenia przestrzeni kluczy w sposób istotny.

Szyfry wykładnicze

klucz szyfrujący to para e, n

m, c ∈{0,1,...,n-1}

c = m^e mod n k_e = (e, n) - klucz szyfrujący

m = c^d mod n k_d = (d, n) - klucz deszyfrujący

e, d ∈ N

Szyfrowanie jednym kluczem, deszyfrowanie drugim = system asymetryczny

warunki:

(m^e mod n)^d mod n = m — warunek oczywisty potrzebny do deszyfracji

(c^d mod n)^e mod n = c

Jakie warunki muszą spełniać e, d, n, aby przemienność m i c była możliwa?

Tw. Fermata

Jeżeli m i n spełniają warunki:

NWD(m, n)=1 {wzgl. pierwsze }

to m^ϕ(n) mod n =1

Tw. Jeżeli

1° e d mod ϕ(n) = 1, gdzie ϕ jest funkcją Eulera

2° m ∈ [0, n-1], przy czym NWD(m, n)=1

to:

(m^e mod n)^d mod n = m

(m^d mod n)^e mod n = m

Z 1° wynika, że dla pewnej liczby całkowitej r:

e d = r ϕ(n) + 1

wobec tego

Wybór d i e:

Wybieramy d z zadanego wcześniej przedziału (d musi być liczbą względnie pierwszą z ϕ(n)). Wyznaczamy e jako odwrotność d, co oznaczamy e=inv(d, ϕ(n)) na podstawie równania:

ed mod ϕ(n)=1

w sposób następujący:

e=d^ϕ(ϕ(n))-1mod ϕ(n).

Można oczywiście wybrać na początku e i analogicznie wyliczyć d.

Konstruując system kryptograficzny musimy mieć na uwadze warunki 1° i 2°.

Implementacje

szyfr Pohlinga — Hellmana { Moc algorytmu leży w złożoności — trudności w logarytmowaniu dyskretnym dla dużych n}

n - duża liczba pierwsza

ϕ(p) = p -1

e d mod (p - 1) = 1 → d = e^-1 mod (p-1)= e^{ϕ(p-1) -1} mod (p-1)

Klucze do szyfrowania k_e=(e, p) i deszyfrowania k_d=(d, p)

{ten szyfr traktować jako ciekawotkę}

Szyfr RSA (Rirest, Shamir, Adleman) (To trzeba znać)

c= m^e mod n

m = c^d mod n

n = p q — iloczyn dwóch pierwszych liczb p, q — kilkusetcyfrowe, wybierane losowo

d ∈ [max (p, q)+1, n-1] - jest „dowolną” liczbą pierwszą z tego przedziału, ale musi być względnie pierwsza z ϕ(n),

1. NWD (d, ϕ(n))=1; ϕ(n)=(p-1)(q-1) {info: chodzi o to, aby klucz deszyfrujący był długi}

1. Jeśli po wyznaczeniu na podstawie d liczby e=inv(d, ϕ(n)) i e<log₂n to trzeba wybrać inną wartość d.

-1. e d mod ϕ(n) = 1 → e d mod (p-1)(q-1) = 1

1. k_e=(e, n); k_d=(d, n);

1. ponownie mamy do czynienia z szyfrem asymetrycznym.

Można ujawnić klucz szyfrujący k_e.

Z każdym użytkownikiem wiążemy parę (k_e; k_d). Każdy może zaszyfrować, zdeszyfrować może ten kto ma klucz k_d — (dokładnie ten, kto zna d)

W tym przypadku są 2 możliwości ataku:

• logarytmowanie dyskretne - znając parę m, c można obliczyć e=log_mc

• rozkład modułu n na czynniki pierwsze dlatego liczby p i q muszą być duże, losowe, nie mogą być blisko siebie.

Przykład:

_ A B ... Z

0 1 2 ... 26

szyfrujemy BOAT m = 02 15 01 20 = m₁ m₂ m₃ m₄

generujemy klucze p=7, q=79

n=7*79=553

d=[max(7,79)+1,552]

(p-1)(q-1)=6*78=468

d=401

401*e mod 468 =1

e=401^ϕ(468)-1mod 468

ϕ(468)= ϕ(2²3²13)=144 ⇒ e=401¹⁴³ mod 468 =461

k_e=(461, 553), k_d=(401, 553);

BOAT m= 02 15 01 20 = m₁ m₂ m₃ m₄

c₁ = 2⁴⁶¹ mod 553=445

c₂ = 15⁴⁶¹ mod 553=148

c₃ = 1⁴⁶¹ mod 553 = 1

c₄ = 20⁴⁶¹ mod 553 = 426

c = 445 148 001 426

Nie stosuje się RSA do szyfrowania - jest zbyt wolny. Używa się go do podpisu cyfrowego.

Szyfr Elgamal'a {wystarczy 200 cyfr}

g ∈ {0,1, ..., q-1}; q — liczba pierwsza

Każdy użytkownik wybiera sobie losowo liczbę całkowitą a, gdzie a ∈ {0,1,..., q-1}

k_d = (a, q);

k_e = (g^a, q)

m - wiadomości

r - całkowite, losowo wybrane

przesyłamy (g ^r mod q, m g ^ar mod q)

odbiorca oblicza:

(g^r)^q mod q = g^ar mod q

(m g ^ar mod q)( g^ar)^-1 mod q = m

Skąd wziąć duże liczby pierwsze? {sita są nieefektywne}

Przykładowe tw.

Liczba n jest pierwsza ⇔ istnieje x:

1° x^n-1 mod n =1

2° x^(n-1)/p. mod n ≠ 1; dla każdego p/(n-1)

Liczby Mersenne'a M_n=2ⁿ-1. Znamy ich 29 (ostatnia n=132049), jeżeli M_n liczbą pierwszą, to n jest liczbą pierwszą.

Algorytmy probabilistyczne

Solorey & Strassen (1977) — bada czy duża liczba n jest pierwsza

• nie ma absolutnie gwarancji, że wygenerujemy liczbę pierwszą;

• możemy ustalić dowolnie małe prawdopodobieństwo tego, że liczba nie będzie pierwsza {satysfakcjonujące 2^-100}

Nie dokonujemy rozkładu na czynniki pierwsze.

Stosujemy funkcję - symbol Jacobiego (oznaczenie J(b, n) lub (b/n))

b, n *n - liczba nieparzysta

* b≤n

* NWD (b, n) =1

J(7,13) = J(13 mod 7, 7)(-1)^(6*12)/4 = J(6,7) = -1

{INFO: J(6673, 15693) — obliczyć dla wprawy}

Algorytm sprawdzania czy n jest liczbą pierwszą:

b ∈(1, n-1) ← wybieramy losowo

testujemy:

NWD (b, n) = 1;

J(b, n) mod n = b^(n-1)/2 mod n lub J(b, n)≡b^(n-1)/2 mod n

Losowo generujemy 100 prób (100 liczb b). Jeśli n jest liczbą pierwszą to punkty 1 i 2 są spełnione dla każdego b. W przeciwnym przypadku 1 i 2 są spełnione z prawdopodobieństwem co najwyżej 0.5 dla każdej wartości b, a więc najwyżej 1/2¹⁰⁰ dla 100 wartości b.

Prościej - jeżeli n nie będzie liczbą pierwszą to jeden z dwóch warunków nie będzie spełniony.

Algorytm Merklego-Hellmana. Szyfr „plecakowy” (korzystamy z problemu upakowania)

Mamy dodatnią liczbę całkowitą b oraz wektor dodatnich liczb całkowitych I=(i₁, i₂, ..., i_n). Czy istnieje taki podciąg elementów ∈I, żeby ich suma była równa b?

(Z₁, Z₂, ..., Z_n) - wektor zero-jedynkowy taki, żeby

m= (m₁, m₂, ..., m_n) — wiadomość jawna zero-jedynkowa

k = (k₁, k₂, ..., k_n) — klucz — wektor 0 - 1

— szyfrogram

Problem wyznaczenia klucza:

Algorytm wyboru klucza:

a = (a₁, a₂, ..., a_n) ciąg superwzrastający

; 1 ≤ i ≤ n

np.: (1, 2, 4, 8, 16)

wybieramy parę liczb (r, w) 1< w < r;

; NWD(r, w) = 1;

for i=1 to n do

k_i := w a_i mod r — klucz szyfrujący jawny k_e

k_d = (a₁, a₂, ..., a_n, w^-1, r) — klucz deszyfrujący {INFO: (a₁, a₂, ..., a_n, w^-1) — tajne elementy klucza}

Algorytm deszyfrowania:

wejście S

wyjście m(m₁, m₂, ..., m_n)

S'=Sw^-1 mod r

if S'≥a_n then m_n=1 else m_n=0;

for i:=n-1 downto 1 do

if (S_i=S-) then m_i=1 else m_i=0;

S=Sw^-1 mod r =

k_i = wa_i mod r

w^-1k_i mod r = a_i mod r

Przykład:

n = 5

m = (0,1,0,1,1)

r = 8443

a = (171, 196, 457, 1191, 2410)

w = 2550

w^-1 mod r = 3950 ;w^-1=inv(w,r)

k_e = (5457, 1663, 216, 6013, 7439)

m k_e = 1663 + 6013 + 7439 = 15115

deszyfrowanie:

S'=15114 * 3950 mod 8443 = 3797

W połowie lat 80-tych wykazano, że można go złamać w czasie wielomianowym. Istnieje podejrzenie, że osłabia go ciąg superwzrastający. Multiplikatywny nie został jeszcze złamany.

Techniki kryptograficzne

m = m₁, m₂, ...

k - stałe lub k = k_1, k₂, ...

Szyfry:

• blokowy — dzieli tekst wejściowy na bloki (więcej niż 1 bit, zwykle 32, 64, 128) i każdy z nich szyfruje używając takiego samego klucza K, tzn.: E_K(m)=E_K(m₁)E_K(m₂)...

• Przykłady: przestawieniowy, Playfair'a, Hilla, DES, plecakowy.

• strumieniowy — dzieli tekst wejściowy na bity (lub bajty) a następnie każdy element jest szyfrowany kluczem k_i należącym do strumienia kluczy K=k₁,k₂,...,tzn.: E_K(m)=E_k1(m₁)E_k2(m₂).... Należy zachować synchronizację kluczy (klucz generowany na bieżąco).

Przykłady: Vigenere'a, Vernama.

Szyfry strumieniowe:

• synchroniczne - strumień klucza jest generowany niezależnie od strumienia wiadomości. Zgubienie jednego znaku zaszyfrowanego tekstu wymusza konieczność zsynchronizowania przez nadawcę i odbiorcę generatorów kluczy przed wznowieniem transmisji. Proces ten powinien być realizowany w sposób zapewniający brak powtarzalności (generator klucza nie powinien być „ustawiany” do poprzedniego stanu).

• samosynchronizujące się - każdy znak klucza jest generowany na podstawie stałej liczby n wcześniej zaszyfrowanych znaków. Jeśli zatem podczas transmisji jakiś zaszyfrowany znak zostanie zgubiony lub wstawiony, to powstały błąd podlega propagacji przez n następnych znaków. Jednakże po odebraniu n poprawnie zaszyfrowanych znaków synchronizacja zostaje ponownie osiągnięta. Te szyfry nie są okresowe ponieważ każdy znak klucza funkcjonalnie zależy od całego poprzedzającego strumienia znaków.

Losowość klucza - podejście statystyczne - musi spełniać testy statystyczne.

Golomb (60-te) trzy testy losowości ciągów binarnych.

Definicje:

Seria w ciągu (x_n) to podciąg identycznych elementów takich, że poprzedza go i następuje po nim inny element.

Funkcja autokorelacji — określa stopień zgodności ciągu oryginalnego i przesuniętego (przesuwanie cykliczne).

0 w ciągu = 1

1 w ciągu = -1

; T — okres

Postulaty Golomba

ciąg o długości T

Jeżeli T jest parzyste to liczba zer i jedynek jednakowa.

1. Jeżeli T jest nieparzyste to liczba zer i jedynek różna o ± jeden

-1. W cyklu o długości T połowa serii ma długość 1, 1/4 długość 2, 1/8 długość 3,....

Funkcja autokorelacji:

Złożoność strukturalna ciągu (co do losowości)

x₀, f(x₀), f(f(x₀)), f(f(f(x₀))), ... — ciągi strukturalnie losowe

f — funkcja jednokierunkowa

Łatwo wyznaczyć ten ciąg

Podejście teoretyczne — ciągi algorytmicznie losowe

Złożoność Kołmogorowa

• długość najkrótszego programu maszyny Turinga za pomocą, którego możemy wygenerować dany ciąg.

Jeżeli ciąg ma długość n, k(x)≥n; k(x) — ciąg Kołmogorowa

Ten problem jest nierozstrzygalny - nie można orzec, że ciąg jest algorytmicznie losowy.

Urządzenia generujące ciągi liczbowe:

Rejestr przesuwający (n-stopniowy).

dla uproszczenia zakładamy, że rejestr jest binarny

f — funkcja boolowska najlepiej

• nieliniowa

• afiniczna

Rejestr liniowy (ze sprzężeniem zwrotnym) - LFSR.

trójstopniowy

1 0 1 1 1 0 0

0 1 1 1 0 0 1

1 1 1 0 0 1 0

1 0

0 1

1 0

1 0

0 0

0 1

T=2ⁿ-1 maksymalny okres jaki można uzyskać w rejestrach liniowych; pseudolosowy maksymalny ciąg wygenerowany przez rejestr n-stopniowy

w(x) = xⁿ + a_n-1x^n-1 + ... + a₁x + a_0­ (?????) - książka podaje taką wersję: w(x)=a_nxⁿ+a_n-1x^n-1+...+a₁x+1

Tw. Największa liczba całkowita T taka, że w(x) dzieli x^T+1 wyznacza okres ciągu generowanego przez liniowy rejestr zwrotny z wielomianem sprzężenia zwrotnego w(x)

w(x) — wielomian nierozkładalny {nie można go przedstawić za pomocą iloczynu wielomianów}

Jeżeli rejestr generuje ciąg maksymalny to jego wielomian jest nierozkładalny. {W drugą stronę nie zachodzi!}

Tw. Niech w(x) nędzie wielomianem charakterystycznym nLFSR. Najmniejsza liczba całkowita p., taka że x^p⊕1|w(x) określa okres generowanego przez ten rejestr ciągu.

Dla ustalonego n ile jest wielomianów gen. ciąg maks.

λ(5)=6

λ(8)=16

λ(10)=60

λ(16)=2048

λ(32)=67108864

wszystkich wielomianów jest 2ⁿ {a₀, a₁, ...,a_n ∈{0,1}}

Rejestry liniowe nie są dobre !

wystarczy przechwycić ciąg o długości 2n, można wyznaczyć wszystkie współczynniki a₀, a₁, ...,a_n

Należy skomplikować urządzenie i zrobić nieliniową funkcję sprzężenia zwrotnego...

Nieliniowe rejestry przesuwające (z liniową funkcją sprzężenia zwrotnego)

okres = 2ⁿ jest maksymalny (tutaj można dopuścić same zera w stanie początkowym)

Ciąg de Bruijn'a — T=2ⁿ

graf de Bruijn'a - opisuje wszystkie możliwe zachowania rejestru generującego ciągi maksymalne

G_n(V, E)

V=X⁽ⁿ⁾ - zbiór wierzchołków to zbiór n - elementów ciągów

1. Cyklem de Bruijna grafie G_n nazywamy cykl przechodzący przez każdy wierzchołek grafu dokładnie jeden raz. Cykl de Bruijna w grafie G_n jest więc cykl o okresie T=2ⁿ. W G_n istnieje cykli. Każdemu cyklowi de Bruijna odpowiada ciąg maksymalny generowany przez nNFSR. Będziemy go nazywać ciągiem de Bruijna rzędu n. Dla grafu G₄ cykl (0001, 0010, 0100, 1001, 0011, 0110, 1101, 1010, 0101, 1011, 0111, 1111, 1110, 1100, 1000, 0000) jest cyklem de Bruijna. Odpowiada mu ciąg maksymalny 000100110101111... generowany przez 4NFSR.

x= x₁, x₂, ..., x_n ; y= y₁, y₂, ..., y_n;; x, y ∈E

y= x₂x₃ ... x_ny_n

Przykład n=3:

B(3)=2

B(4)=16

B(6)=67108884

B(7)≈1,4*10¹⁷

B(8)≈1,33*10³⁶

B(16)=10⁹²⁵⁹

Trudność w syntezie funkcji f

(Konstrukcja funkcji sprzężenia zwrotnego nNFSR)

WEJŚCIE: Funkcja sprzężenia zwrotnego f(x₀, x₁, ..., x_n-1) określona dla nLFSR generującego ciąg maksymalny.

1. METODA:

1. f^*(x₀, x₁, ..., x_n-1) = f(x₀, x₁, ..., x_n-1) ⊕

1. WYJŚCIE:

1. Funkcja sprzężenia zwrotnego f^*(x₀, x₁, ..., x_n-1) dla nNFSR generującego ciąg maksymalny.

Zauważmy, że w przypadku nLFSR ciąg maksymalny oznacza ciąg o okresie 2ⁿ-1, natomiast dla nNFSR jest to ciąg o okresie 2ⁿ. Funkcja nieliniowa dodana do funkcji sprzężenia zwrotnego nLFSR generującego ciąg maksymalny sprawia, że rejestr może znaleźć się w stanie 00...0 i opuścić go tworząc w ten sposób cykl o okresie Y=2ⁿ.

1. Przykład:

x0 x1 x2	f(x0 x1 x2)	f^*(x0 x1 x2)
0 0 0	0	1
0 0 1	0	1
0 1 0	1	0
0 1 1	1	1
1 0 0	1	0
1 0 1	1	0
1 1 0	0	1
1 1 1	0	0

0 0 0 → 0 0 1 → 0 1 1 → 1 1 1 → 1 1 0 → 1 0 1 → 0 1 0 → 1 0 0 → 0 0 0

Algorytm Prefer-one

WEJŚCIE:

Liczba naturalna n.

METODA:

Wpisz n zer.

Aby otrzymać k-ty bit ciągu, k>n, dopisz 1. Jeśli utworzona w ten sposób n-tka nie wystąpiła dotąd w ciągu, to k:=k+1 i powtarzaj krok 2. W przeciwnym przypadku.

Dopisz 0. Jeśli utworzona w ten sposób n-tka nie wystąpiła dotąd w ciągu, to k:=k+1 i przejdź do kroku 2. Jeśli wystąpiła, zatrzymaj się.

WYJŚCIE:

Ciąg maksymalny o okresie 2ⁿ.

Przykład:

Stosując algorytm dla n=4 otrzymujemy:

00001111011001010000,

a zatem cykl (0000, 0001, 0011, 0111, 1111, 1110, 1101, 1011, 0110, 1100, 1001, 0010, 0101, 1010, 0100, 1000) jest cyklem de Bruijna. W celu otrzymania następnego cyklu, w otrzymanym ciągu zamieniamy ostatnią 1na 0:

0000111101100100

i kontynuujemy postępowanie począwszy od kroku 2 algorytmu otrzymując ciąg

00001111011001001

nie będący maksymalnym. Wobec tego kont. postępowanie:

000011110110000

00001111010110010000, ←

by w rezultacie uzyskać ciąg wskazany strzałką. Postępując w sposób dalej uzyskujemy kilka następnych ciągów (strzałką ← oznaczono ciągi wynikowe):

00001111010110000

00001111010101

00001111010010110000 ←

00001111010010000

00001111010010000

00001111010000

00001111001011010000 ←

...

Pytanie: czy ciąg wygenerowany przez rejestr nieliniowy można wygenerować za pomocą rejestru liniowego?

TAK, bardzo łatwo!

16 stopni (?)

Każdy ciąg można uzyskać za pomocą rejestru liniowego.

Pytanie o jego najmniejszą liczbę stopni?

L(x) — złożoność linowa ciągu x

Tw.

Niech x będzie ciągiem de Bruijn'a generowanym przez n-stopniowy nieliniowy rejestr przesuwający.

Wówczas

2^n-1+n ≤ L(x) ≤ 2ⁿ-1

n=4 L(x)≥12

n=8 L(x)≥136

n=16 L(x)≥2^16-1+16 > 32000

Będziemy używać rejestry liniowe w konfiguracjach ... (?)

x1	x2	y
0	0	0
0	1	0
1	0	0
1	1	1

Generator pani Vera Pless

NWD (m, n) = 1 ⇒ T =T₁*T₂= (2ⁿ-1) (2^m-1)

T₁=2ⁿ-1; T₂=2^m-1

Wykorzystanie szyfrów blokowych

Metoda licznikowa.

I₀ - wartość początkowa rejestru

Kolejne bloki wejściowe do E są generowane przez prosty licznik. Za pomocą tej metody jest możliwe generowanie i-tego znaku klucza k_i bez konieczności generowania pierwszych i-1 znaków klucza przez ustawienie licznika na wartość I₀+i-1 - jest to szczególnie przydatne przy dostępie do i-tego znaku w pliku o dostępie bezpośrednim.

Output - block - feedback mode — OBF

W tej metodzie rejestr (bufor) służy jako wejście do algorytmu E_B szyfru blokowego z kluczem B. Podczas i-tej iteracji jest realizowany algorytm E_B(bufor), młodszy znak (prawy) bloku wyjściowego jest wygenerowany znakiem klucza k_i. Otrzymany w wyniku algorytmu blok znaków jest ponownie umieszczany w buforze. Każdy element k_i jest znakiem a nie bitem. Redukuje to liczbę szyfrowań z użyciem algorytmu E_B. Wiadomość wejściowa jest dzielona na strumień znaków i szyfrowana z jednoczesnym generowaniem klucza.. Technika ta jest również nazywana wewnętrznym sprzężeniem zwrotnym, ponieważ sprzężenie jest wewnętrzne w stosunku do procesu generowania strumienia klucza, w przeciwieństwie do metody samosynchronizującej, w której pętla sprzężenia zwrotnego wychodzi do strumienia już zaszyfrowanego.

Szyfr samosynchronizujący:

CFB — Cipher Feedback Mode

Rejestr sprzężenia zwrotnego R jest rejestrem przesuwającym, w którym każdy zaszyfrowany znak c_i natychmiast po jego wygenerowaniu jest przesuwany w jeden koniec (znak z drugiego końca jest po prostu odrzucany). Rejestr jest inicjowany wartością początkową I₀. Podczas każdej iteracji algorytm E szyfru blokowego generuje na podstawie rejestru R blok wyjściowy, z którego najmniej znaczący znak jest następnym znakiem klucza.

W metodzie tej błędy transmisji wpływają na pętlę sprzężenia zwrotnego. Jeśli podczas transmisji znak zostanie zmieniony lub zgubiony to rejestr przesuwający odbiorcy będzie miał inną wartość niż nadawcy (tekst nie zostanie poprawnie odszyfrowany). Ponieważ rejestry synchronizują się co n cykli (n-liczba znaków w bloku) tekst będzie ponownie poprawnie deszyfrowany.

Aby zdeszyfrować i-ty znak c_i zaszyfrowanego tekstu wystarczy umieścić w rejestrze R n poprzednich znaków zaszyfrowanego tekstu c_i-n,...,c_i-1 i wykonać jeden cykl sprzężenia zwrotnego w celu otrzymania klucza k_i.

Ostatni blok jest zwykle sumą kontrolną, zależną od każdego bitu szyfrowanej wiadomości.

m = ORGANIZACJA

k = SGYEFTBABEO

c = GYEFTABABEOP

O + S mod 27 = G

Techniki szyfrowania blokowego.

Do tej pory rozpatrywaliśmy taki schemat (na rysunku nie zaznaczono klucza).

Code Book Mode — tak nazywamy ten tryb stosowania szyfru; jednakowe bloki będą miały taką samą postać zaszyfrowaną.

Wniosek:

Nie szyfrujemy wiadomości dłuższych od długości bloku (DEC 64bity)

Cipher Block Chaining — szyfrowanie wiązane blokowe (CBC)

C₀=I₀

C_i+1=E(c_i⊕m_i+1)

m_i+1= c_i⊕D(c_i+1)=

=c_i⊕D(E(c_i⊕m_i+1))= m_i+1

Metoda podobna do CFB z tą różnicą, że do rejestru przesuwającego jest ładowany przez pętlę sprzężenia cały zaszyfrowany blok, którego znaki wraz ze znakami następnego zaszyfrowanego bloku uczestniczą w obliczaniu różnicy symetrycznej. Następnie wynik tej różnicy jest przesyłany do szyfru blokowego realizującego algorytm E z kluczem K.

Ponieważ każdy zaszyfrowany blok c_i jest obliczany z m_i oraz z poprzedniego bloku c_i-1, zatem jeden błąd, który może wystąpić podczas transmisji, ma wpływ najwyżej na dwa bloki. Podobnie jak w CFB ostatni blok jest sumą kontrolną.

Podstawowe usługi kryptograficzne

• poufność kontroli dostępu

• integralność danych — odpowiada na pytanie czy nasze dane nie zostały zmienione w sposób przypadkowy lub celowy

• podpis cyfrowy (uwierzytelnianie)

• kontrola dostępu

• niezaprzeczanie

Integralność danych

Jednokierunkowa funkcja skrótu — argumentem jednokierunkowej funkcji skrótu H(M) jest wiadomość M o dowolnej długości. Wartością tej funkcji jest liczba h o ustalonej długości.

h = H(M), przy czym h jest liczbą o długości m

Istnieje wiele funkcji, których argumentem są liczby o dowolnej długości i które przyjmują wartości będące liczbami o ustalonej długości, lecz jednokierunkowe funkcje skrótu mają dodatkowe właściwości:

• Mając dane M, łatwo jest obliczyć h

• Mając dane h, trudno jest obliczyć M

• Mając dane M, trudno jest znaleźć inną wiadomość M' taką, że H(M)=H(M').

Znaczenie słowa trudno zależy od określenia wymagań bezpieczeństwa w danej sytuacji, lecz dla większości rzeczywistych implementacji definiuje się pojęcie trudny problem jako wymagający wykonania 2⁶⁴ operacji, a niekiedy nawet więcej.

Jednokierunkowa funkcja skrótu zależna od klucza jest często oznaczana jako MAC (Message Authentication Code - ciąg uwierzytelniania wiadomości). Tylko osoba mająca identyczny klucz może zweryfikować skrót. Są one bardzo użyteczne w zabezpieczaniu autentyczności bez wprowadzania tajności. Przykład takiej funkcji:

m = m₁m₂m₃...m_n-1

H = H_n = h(m)

H_i=p(H_i-1, m_i)

MAC na bazie szyfru blokowego

Najprostszym sposobem utworzenia jednokierunkowej funkcji skrótu zależnej od klucza jest szyfrowanie wiadomości za pomocą algorytmu blokowego w trybie szyfrowego sprzężenia zwrotnego (CFB) (ANSI X9.9, ISO9797). Funkcja RIPE-MAC bazuje na normie ISO9797 i korzysta z algorytmu DES jako blokowej funkcji szyfrującej. Istnieją dwie odmiany funkcji RIPE-MAC: jedna wykorzystująca zwykły algorytm DES (RIPE-MAC1), druga wykorzystująca trzykrotne szyfrowanie algorytmem DES w celu uzyskania jeszcze większego bezpieczeństwa (RIPE-MAC3). Funkcja RIPE-MAC1 wykonuje szyfrowanie 64 bitów bloku wiadomości alg. DES jednokrotnie, RIPE-MAC3 - trzykrotnie.

Algorytm składa się z trzech części. Najpierw wiadomość jest poszerzana do długości będącej wielokrotnością 64 bitów. Następnie poszerzona wiadomość jest dzielona na 64-bitowe bloki. Do skracania tych bloków używa się funkcji kompensującej z kluczem, sterowanej przez klucz tajny, która daje pojedynczy blok 64 bitów. W tym bloku można użyć alg. DES, jednorazowo lub trzykrotnie. Ostatecznie ciąg wyjściowy jest poddawany szyfrowaniu na bazie alg. DES z innym kluczem, otrzymanym z klucza wykorzystywanego w procesie kompensacji.

Jednokierunkowa funkcja skrótu bez klucza, z wykorzystaniem alg. szyfru blokowego (ISO10118-2)

Przekształcenie U nie jest konieczne, natomiast musi być kiedy klucz jest dłuższy od szyfrowanej wiadomości.

Dwa powyższe rozwiązania tworzą skróty 64-bitowe (niedobre - powinno być min. 128 bitów)

Inne funkcje skrótu:

MD4, MD5, SHA (secure Hash Alghoritm na bazie MD5), RIPEMD (128 bit), RIPEMD-160 (160 bit.)

Podpis cyfrowy

związany z układem asynchronicznym (inne klucze szyfrujący i deszyfrujący)

sign(m) = D_k^*(m)

podpis jest związany z kluczem i podpisującym

Podpisuje się skrót wiadomości

Problem w wygenerowaniu par kluczy (k, k^*) dla każdego użytkownika.

Dwie filozofie PGP każdy użytkownik generuje sobie klucze

autorytet generuje i rozsyła klucze

26

Ochrona danych — prof. J. Stokłosa.

---