Microsoft Word - HAC1.doc

&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&

WYŁĄCZNOŚĆ DO PUBLIKOWANIA TEGO TŁUMACZENIA

POSIADA

RAG

oraz

P & S

HTTP://WWW.R-AG.PRV.PL

http://www.win32asm.civ.pl/

„HANDBOOK OF APPLIED CRYPTOGRAPHY”

tłumaczone by KREMIK

wankenob@priv5.onet.pl

&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&

ROZDZIAŁ PIERWSZY: OGÓLNY OPIS KRYPTOGRAFII

1.1 WPROWADZENIE

Kryptografia ma długą i fascynującą historię. Najbardziej kompletnym, nie technicznym omówieniem tego
tematu jest „The Codebreakers’ Kahn’a. Książka ta śledzi kryptografię od jej początków i ograniczonego
zastosowania przez Egipcjan jakieś 4000 lat temu, do wieku dwudziestego, gdzie odegrała kluczową rolę i
wpłynęła na wyniku obu wojen światowych. Zakończona na 1963 roku, książka Kahn’a pokazuje te aspekty jej
historii , które były bardziej znaczące (do tego czasu) dla rozwoju tego tematu. Dominującymi zastosowaniami
tej sztuki były te powiązane z wojskowością, służbą dyplomatyczną i rządem. Kryptografia była używana jako
narzędzie do ochrony tajemnic narodowych i strategii.

Rozpowszechnienie komputerów i systemów komunikacyjnych w 1960 przyniosło żądanie z sektora

prywatnego w znaczeniu ochrony informacji w postaci cyfrowej i usług bezpieczeństwa. Po pierwsze prace
Feistela w IBM we wczesnych latach siedemdziesiątych i kończące się w 1977 przyjęciem przez U.S Federal
Information Processing Standard dla szyfrowania niezastrzeżonej informacji, DES, Data Encryption Standard
(standard szyfrowania DES), jako najbardziej znanego mechanizmu kryptograficznego w historii. Pozostaje on
standardowym środkiem dla bezpieczeństwa handlu elektronicznego dla wielu instytucji finansowych na
świecie.

Najbardziej znaczące zdarzenie w historii kryptografii nadeszło w 1976 roku kiedy Diffie i Hellman

opublikowali New Directions in Cryptography. Wprowadzili rewolucyjną koncepcję kryptografii klucza
publicznego i dostarczyli również nową i pomysłową metodę wymiany klucza., której bezpieczeństwo oparte
jest na trudnym do rozwiązania problemie logarytmu dyskretnego. Chociaż autorzy nie mieli w tym czasie
praktycznej realizacji schematu kryptografii klucza publicznego, pomysł był jasny i szeroko zainteresował i
zmusił do działania społeczność kryptograficzną. W 1978, Rivest, Shamir i Adleman odkryli pierwszy
praktyczny schemat szyfrowania klucza publicznego i podpisu , teraz oznaczony jako RSA. Schemat RSA jest
oparty na innym ,trudnym problemie matematycznym, rozkładu na czynniki pierwsze dużych liczb
całkowitych. To zastosowanie trudnego matematycznego problemu do kryptografii ożywia wysiłki dla
znajdowania bardziej wydajnych metod rozkładu. Lata osiemdziesiąte przyniosły znaczący postęp w tym
obszarze, ale nie przyniosły żadnego rozwiązania, który zastąpiłby RSA. Inną klasą efektywnych i praktycznych
schematów klucza publicznego byłe te wynaleziony przez ElGamala w 1985. Były one również oparte o
problem logarytmu dyskretnego.

Jednym ze znaczących wkładów dostarczanym przez kryptografię klucza publicznego jest podpis

cyfrowy. W 1991 roku został zaadoptowany pierwszy międzynarodowy standard podpisu cyfrowego (ISO/IEC
9796). Został oparty na schemacie klucza publicznego RSA. W 1994 roku rząd USA przyjął Standard Podpisu
Cyfrowego, mechanizm oparty na schemacie klucza publicznego ElGamal.

Poszukiwanie nowych schematów klucza publicznego, poprawiające istniejące mechanizmy

kryptograficzne i dowodzące bezpieczeństwa posuwały się szybkim krokiem. Różne standardy i infrastruktury
dotyczące kryptografii zostały przedstawione w tym miejscu. Produkty związane z bezpieczeństwem zostały
stworzone i adresowane na potrzeby bezpieczeństwa informacji społeczeństwa,

Celem tej książki jest dostarczenie nowoczesnej rozprawy naukowej o zasadach, technikach i

algorytmach interesujących w praktyce kryptograficznej. Nacisk zostanie położony na te aspekty które są
najpraktyczniejsze i najbardziej stosowane. Czytelnik będzie uświadomiony co do podstawowych kwestia i
zostaną wskazane pokrewne badania w literaturze gdzie można będzie znaleźć pogłębione omówienia. Z
powodu objętości materiału jaki jest przedstawiany, większość wyników będzie przedstawionych bez dowodów.
Służy to również odsłonięciu bardzo stosowanej naturze tego tematu. Książka ta z zamierzenia jest skierowana
do implementatorów i badaczy. Opisuje algorytmy , systemy i ich interakcje.
Rozdział 1 jest przewodnikiem po wielu różnych aspektach kryptografii. Nie próbuje przekazać
wszystkich szczegółów i subtelności właściwych temu tematowi. Jego celem jest wprowadzenie do
podstawowych kwestii i zasad i wskazanie czytelnikowi właściwych rozdziałów w książce , które w pełni
traktują o tej kwestii. Unikamy w tym rozdziale specyficznych technik.

1.2 BEZPIECZEŃSTWO INFORMACJI I KRYPTOGRAFIA

Koncepcję informacji będziemy traktować jako ustaloną wielkość. Generalnie, przy wprowadzeniu do
kryptografii, zrozumienie kwestii powiązanych z bezpieczeństwem informacji jest konieczne. Bezpieczeństwo
informacji objawia się na wiele sposobów , wedle sytuacji i wymagań. Bez względu kogo dotyczy, i w jakim
stopniu, wszystkie strony transakcji muszą być przekonane, że spotkają pewne obiektywy powiązane z
bezpieczeństwem informacji . Niektóre z tych obiektywów są pokazane w Tabeli 1.1

Od wieków zawiłe zbiory protokołów i mechanizmów było tworzonych dla działania w kwestii

bezpieczeństwa informacji, kiedy informacje były dokumentami fizycznymi. Często obiektywy bezpieczeństwa
informacji nie mogą wyłącznie osiągane przez same algorytmy matematyczne i protokoły., ale wymagają
technik proceduralnych i trwania praw odnoszących się do żądanego wyniku. Na przykład, prywatność listów
jest gwarantowana przez zaklejone koperty dostarczane przez pocztę. Fizyczne bezpieczeństwo koperty jest,
praktyczna konieczność, ograniczenia i prawa są uchwalone aby zabezpieczać przed przestępstwami
kryminalnymi otwierania listów przez osoby do tego nie upoważnione.

Prywatność lub poufność

Przechowywanie tajnych informacji, ale tylko te które
są autoryzowane są do obejrzenia

Integralność danych

Zapewnienie ,że informacja nie będzie zmieniona w
nieautoryzowany lub nieznany sposób

Uwierzytelnianie jednostki lub
identyfikacja

Potwierdzenie tożsamości jednostki (np. osoby,
terminala komputerowego, karty kredytowej itp.)

Uwierzytelnianie wiadomości Potwierdzenie

źródła informacji, znane również jako

uwierzytelnianie źródła danych

Podpis Sposób

łączenia informacji z jednostką

Autoryzacja Przeniesienie ,na inną jednostkę, formalnej sankcji

robienia czegoś lub bycia czymś

Kontrola poprawności

Sposób dostarczenia poprawnego czasu autoryzacji, lub
manipulacji informacją lub zasobów

Kontrola dostępem Ograniczenie

dostępu do zasobów jednostkom

uprzywilejowanym

Certyfikacja Zaaprobowanie informacji przez zaufaną jednostkę
Datowanie Zarejestrowanie

czasu stworzenia lub istnienia

informacji

Świadczenie

Weryfikacja stworzone lub istniejącej informacji przez
jednostkę inną niż twórca

Potwierdzenie Potwierdzenie,

że informacja została odebrana

Zatwierdzenie Potwierdzenie,

że dostarczono obsługę

Posiadanie

Sposób dostarczenia jednostki z legalnego źródła lub
transfer zasobu do innych

Ukrywanie tożsamości Ukrywanie

tożsamości jednostki wymagane w jakimś

procesie

Nie- zaprzeczalność Zapobieżenie zaprzeczeniu poprzedniej transakcji lub

akcji

Unieważnienie Cofnięcie certyfikacji lub autoryzacji

Tabela

1.1

Pewne

obiektywy bezpieczeństwa informacji

Czasami jest przypadek ,że bezpieczeństwo jest osiągane nie przez samą informację ale przez zapisujący ją
dokument fizyczny. Na przykład, papierowa waluta wymaga specjalnego atramentu i materiału aby zapobiec
fałszerstwu.

Podczas gdy informacja była typowo przechowywana i przekazywana na papierze, teraz rezyduje na

nośnikach magnetycznych i przekazywana poprzez systemy telekomunikacyjne, bezprzewodowo. Coś zmieniło
się dramatycznie w zdolności do kopiowania i zmieniania informacji. Za jednym razem możemy zrobić tysiące
kopii części informacji przechowywanej elektronicznie a każda nie dająca się odróżnić od oryginału. Z
informacja na papierze jest to dużo trudniejsze. Co jest potrzebne społeczeństwu, gdzie informacja jest
przechowywana i przekazywana głównie w formie elektronicznej, jako sposób zapewnienia bezpieczeństwa
informacji, która jest niezależna od zapisujących mediów fizycznych lub przekazania jej tak, że obiektywy
bezpieczeństwa informacji zależą jedynie od samej informacji cyfrowej.

Jednym z fundamentalnych narzędzi używanych w zabezpieczeniu informacji jest podpis. Jest to

zbudowany blok dla wielu innych usług takich jak nie zaprzeczalność, uwierzytelnianie źródła danych,
identyfikacja i świadczenie, mówiąc o kilku. Nauczywszy się podstaw piania, lepiej indywidualnie nauczyć się
jak tworzyć ręczne podpisy dla celów identyfikacji. W przeciągu wieku podpis rozwijał się stając się częścią
tożsamości osoby. Podpis ten był planowany jako wyłączna cecha indywidualna i służyć miała jako środek
identyfikacji, autoryzacji i poprawności. Przy informacji elektronicznej, koncepcja podpisu musi być
wyrównana; nie może być po prostu czymś unikalnym dal podpisującego i niezależne od podpisywanej
informacji. Elektroniczne jego powtarzanie jest tak proste, że dołączanie podpisu do dokumentu nie podpisanego
przez autora sygnatury jest prawie błahostką.

Analogicznie są wymagane „papierowe protokoły” obecnie w użyciu. Miejmy nadzieję, że te nowe

protokoły elektroniczne są przynajmniej tak dobre jak te, które zastępują. Jest to unikalna sposobność dla
społeczeństwa dla wprowadzenia nowych i bardziej wydajnych sposobów zabezpieczenia bezpieczeństwa
informacji. Wiele można się nauczyć z ewolucji systemu opartego o papier, naśladując te aspekty, które służyły
nam dobrze i usunąć te niewydajne.
Osiągnięcie bezpieczeństwa informacji w społeczeństwie elektronicznym wymaga szerokiego
wachlarza technicznych i prawnych umiejętności. To jednak nie gwarantuje że wszystkie obiektywy
bezpieczeństwa informacji uznają konieczność bycia właściwie obecne. Te techniczne sposoby są dostarczone
przez kryptografię.

1.1 Definicja Kryptografia jest nauką technik matematycznych nawiązującą do aspektów bezpieczeństwa
informacji takich jak poufność, integracja danych, uwierzytelnianie jednostki i uwierzytelnienie źródła danych.

Kryptografia nie jest jedynie sposobem dostarczania bezpieczeństwa informacji, ale raczej jedynie zbiorem
technik.

Cele kryptografii

Ze wszystkich obiektywów bezpieczeństwa informacji wypisanych w Tabeli 1.1, z poniższych czterech form
wywodzić się będą pozostałe: (1) prywatność lub poufność (§ 1.5, § 1.8); (2) integralność danych (§ 1.9); (3)
uwierzytelnianie (§ 1.7) i (4) nie – zaprzeczalność (§ 1.6).

1. Poufność jest usługą używaną do przechowywania zawartości informacji od wszystkich, ale ma

upoważnienie do nich. Tajność jest terminem równoznacznym z poufnością i prywatnością. Są
liczne podejścia dostarczania poufności, począwszy od ochrony fizycznej do algorytmów
matematycznych co czyni dane niezrozumiałymi.

2. Integralność danych jest usługą, która kieruje nieautoryzowaną zmianą danych. Zapewniając

integralność danych, musimy mieć zdolność wykrycia manipulacji danymi przez części
nieautoryzowane. Manipulacja danymi zawiera takie rzeczy jak wprowadzenie, skreślenie i
zastępowanie.

3. Uwierzytelnianie jest usługą odnoszącą się do identyfikacji. Funkcja ta stosuje obie jednostkę i

samą informację. Dwie części wprowadzone do komunikacji powinny rozpoznawać się nawzajem.
Informacja dostarczona poza kanałem powinna być uwierzytelniona jako początkowe, dane
źródłowe, zawartość danych itp. Z tych powodów ten aspekt kryptografii jest zazwyczaj dzielony
na dwie główne klasy : uwierzytelnianie jednostki i uwierzytelnienie źródła danych.
Uwierzytelnienie źródła danych implikuje dostarczanie integralności danych (jeśli wiadomość jest
zmodyfikowana, zmienia się źródło)

4. Nie-

zaprzeczalność jest usługą która uniemożliwia jednostce zaprzeczenie poprzedniej transakcji

lub akcji. Kiedy dyskutujemy pojawiającą się w związku z tym jednostkę zaprzeczającą, która
wykonał jakąś akcję, jest konieczny sposób rozwiązania tej sytuacji. Na przykład, jedna jednostka
może autoryzować własność kupna przez inną jednostkę a później zaprzeczyć takiej autoryzacji .
Procedura wymagająca zaufanej trzeciej jednostki jest potrzebna do rozwiązania tej dyskusji.

Fundamentalnym celem kryptografii jest właściwie zastosowanie tych czterech obszarów w teorii i praktyki.
Kryptografia jest o zapobieganiu i wykrywaniu oszustw i innych złośliwych działań.
Książka ta opisuje liczne podstawowe narzędzia kryptograficzne (prymitywy) używane przy
dostarczaniu bezpieczeństwa informacji. Przykłady tych elementarnych narzędzi zawierają schematy
szyfrowania (§1.5 i §1.8), funkcje kodujące (§1.9) i schematów podpisu cyfrowego (§1.6). Rysunek 1.1
dostarcza schematycznego rozrysowania tych rozważanych części elementarnych i ich relacji. Wiele z nich

będzie krótko wprowadzone w tym rozdziale, z omówieniem szczegółów wstrzymamy się do późniejszych
rozdziałów. Te części elementarne powinny ewaluować w związku z różnymi kryteriami takimi jak:

Rysunek 1.1 Klasyfikacja prymitywów kryptograficznych

1. poziom bezpieczeństwa: Jest to zazwyczaj trudne do skwantyfikowania. Często jest to dane pod

względem liczby operacji wymaganych (używając najlepszych metod znanych obecnie) do pokonania
zamierzonych obiektywów. Typowo poziom bezpieczeństwa jest definiowany przez górną granicę w
ilości pracy koniecznej do pokonania obiektywu

2. sposób działania. Prymitywy będą musiały być połączeniem różnych informacji obiektywów

bezpieczeństwa. Które prymitywy są bardziej wydajne dla danego obiektywu będzie określone poprzez
podstawowe właściwości tych funkcji pierwotnych

Funkcje pierwotne
identyfikacji

Podpisy

Dowolna długość funkcji
kodującej

Szyfr klucza publicznego

Prymitywy identyfikacji

Permutacja jednokierunkowa

Sekwencja losowa

Szyfr klucza symetrycznego

Dowolna długość funkcji
kodującej (MAC)

Podpisy

Sekwencje pseudolosowe

Funkcje
pierwotne
Bezkluczowe

Funkcje
pierwotne
Klucza
symetrycznego

Bezpieczeństwo
elementarne

Funkcje
pierwotne klucza
publicznego

Szyfr
strumieniowy

Szyfr blokowy

3. metody działania. Funkcje pierwotne, kiedy stosuje się je na różny sposób i z różnymi danymi

wejściowymi ,będą wykazywały różne charakterystyki; a zatem jedna funkcja pierwotna może
dostarczyć bardzo różnych sposobów działania w zależności od jego trybu działania lub użycia

4. wydajność. Odnosi się to do wydajności funkcji pierwotne w szczególnym trybie działania. (Na

przykład, algorytm szyfrujący może być oceniany przez liczbę bitów na sekundę którą może
zaszyfrować)

5. łatwość implementacji. Odnosi się to do trudności realizacji funkcji pierwotnej w praktycznej instancji.

Może to zawierać złożoność implementacji tej funkcji pierwotnej albo w środowisku oprogramowania
albo w środowisku sprzętowym

Względna ważność różnych kryteriów bardzo zależy od aplikacji i dostępnych zasobów. Na przykład, w
środowisku gdzie moc komputerowa jest ograniczona, można musieć przehandlować wysoki poziom
bezpieczeństwa za lepszą wydajność systemu jako całości.

Kryptografia, przez wieki, była sztuką praktykowaną przez wielu, którzy ad hoc obmyślali techniki

napotykając potrzeby zabezpieczenia informacji. Ostatnie dwadzieścia lat było okresem przechodzenia tej
dziedziny ze sztuki do nauki. Jest teraz kilka międzynarodowych konferencji poświęconych wyłącznie
kryptografii i również międzynarodowa organizacja naukowa, Międzynarodowe Stowarzyszenie nad Badaniami
Kryptograficznymi (IACR), ukierunkowane na popieranie badań w tym obszarze.
Książka ta jest o kryptografii: teorii, praktyce i standardach

1.3 PODSTAWY O FUNKCJACH

Chociaż ta książka nie traktuje o matematyce abstrakcyjnej, znajomość podstawowych koncepcji
matematycznych dostarczonych tu, będzie użyteczna. Jedną koncepcją, która jest absolutnym fundamentem
kryptografii jest funkcja w sensie matematycznym. Funkcja jest kolejno odniesieniem do odwzorowywania lub
transformacji.

1.3.1 FUNKCJE (1-1, JEDNOKIERUNKOWA, JEDNOKIERUNKOWA Z ZAPADKĄ)

Zbiór składa się z różnych obiektów, które s a nazywane elementami tego zbioru. Na przykład, zbiór X może
składać się z elementów a, b, c a jest to oznaczone jako X = {a, b, c}

1.2 Definicja Funkcja jest zdefiniowana przez dwa zbiory X i Y i zasadę f , która przydziela każdemu
elementowi w X dokładnie jeden element w Y Zbiór X jest nazywany dziedziną funkcji a Y przeciwdziedziną.
Jeśli x jest elementem X (zazwyczaj zapisywane x Є X) obraz x jest elementem w Y wedle zasady f powiązanej
z x; obraz y z x jest oznaczony przez y = f(x). Standardowa notacja dla funkcji f ze zbioru X do zbioru Y to f:
X

→ Y. Jeśli y Є Y wtedy przeciw obraz y jest elementem x Є X dla którego f(x) = y. Zbiór wszystkich

elementów w Y, który ma przynajmniej jeden przeciw obraz jest nazywane obrazem f, oznaczonym Im(f).

1.3 Przykład (funkcji). Rozważmy zbiór X = {a ,b ,c}, Y = {1,2,3,4}, a zasada f z X do Y zdefiniowana jest
jako f(a) =2, f(b)=4, f(c)= 1. Rysunek 1.2 pokazuje schematycznie zbiór X, Y i funkcję f. Przeciwobrazem
elementu 2 jest a. Obrazem f jest {1,2,4}
Myśląc o funkcji pod względem schematycznym (czasami zwanym diagramem funkcjonalnym) danym
na rysunku 1.2, każdy element w dziedzinie X ma dokładnie jedną strzałkę wychodzącą z niej. Każdy element
w przeciwdziedzinie Y może mieć jakąś liczbę strzałek wchodzących do niej (wliczając w to zero linii) .

°1

a ° °2

b°

°3

c °

°4

Rysunek 1.2 Funkcja f z trzy elementowym zbiorem X i czteroelementowym zbiorem Y

Często tylko dziedzina X i zasada f jest dana, a przeciwdziedzina jest z założenia obrazem f. Ten punkt
zilustruje dwa przykłady.

1.4 Przykłady (funkcja) Mamy X = {1 ,2, 3,...., 10} i będzie zasada f, która dla każdego x Є X, f(x0 = r

, gdzie

jest resztą kiedy x

jest dzielone przez 11. Zatem

f(1) =1 f(2) = 4 f(3) = 9 f(4) = 5 f(5) = 3

f(6) = 3 f(7) = 5 f(8) = 9 f(9) = 4 f(10) = 1

Obrazem f jest zbiór Y= {1,3,4,5,9}

1.5 Przykład (funkcja) X = {1,2 ,3,4 ...., 10

} i zasadę f (x) = r

, gdzie r

jest resztą kiedy x2 dzielimy przez

+1 dla wszystkich x Є X . Nie jest tu do zrealizowania zapisanie f dokładnie jak w przykładzie 1.4, ale

pomimo to funkcja jest zupełnie określona przez dziedzinę i matematyczny opis zasady f.

(i) funkcja 1-1

1.6 Definicja Funkcja (lub transformacja) jest 1 – 1 (jeden do jednego) jeśli każdy element w przeciwdziedzinie
Y jest obrazem najwyżej jednego elementu w dziedzinie X

1.7 Definicja Funkcja (lub transformacja) jest onto jeśli każdy element w przeciwdziedzinie Y jest obrazem
przynajmniej jednego elementem w dziedzinie. Odpowiednio funkcja f: X

→Y jest onto jeśli Im(f) =Y.

1.8 Definicja Jeśli funkcja f: X

→Y jest 1 – 1 a Im(f) = Y, wtedy f jest nazywana bijekcją

1.9 Fakt Jeśli f: X

→ Y to 1 –1 wtedy f: X → Im(f) jest bijekcją. W szczególności, jeśli f: X → Y to 1 –1 , a X i

Y są skończonymi zbiorami o tych samych rozmiarach, wtedy f jest bijekcją.

Pod

względem reprezentacji schematycznej, jeśli f jest bijekcją, wtedy każdy element w Y ma

dokładnie jedną strzałkę z niej wychodząca. Funkcje opisane w Przykładzie 1.3 i 1.4 nie są bijekcjami. W
Przykładzie 1.3 element 3 nie jest obrazem żadnego z elementów w dziedzinie. W przykładzie 1.4 każdy element
w przeciwdziedzinie ma dwa przeciwobrazy.

1.10 Definicja Jeśli f jest bijekcją z X do Y wtedy jest prostą sprawą zdefiniować bijekcję g z Y do X jak
następuje: dla każdego y Є Y definiujemy g(y) = x gdzie x Є X i f(x) = y Ta funkcja g uzyskana z f jest
nazywana funkcją odwróconą f i oznaczana przez g =f

–1

Rysunek

1.3

Bijekcja f i jej inwersja g = f

-1

1.11 Przykład (funkcja odwrotna) X = {a, b, c, d, e} a Y = {1, 2, 3, 4, 5} i rozważmy zasady f dane przez
strzałki na Rysunku 1.3. f jest bijekcją a jej odwrotność g jest sformowana po prostu przez odwrócenie strzałek
na brzegach . Dziedziną g jest Y a przeciwdziedziną jest X.
Odnotujmy,

że jeśli f jest bijekcją , tak więc jest f

-1

. W kryptografii bijekcje są używane jako narzędzia

dla szyfrowania wiadomości a odwrócone transformacje są używane do deszyfracji . Stanie się to jaśniejsze w §

1.4 kiedy zostaną wprowadzone podstawową terminologię Odnotujmy, że jeśli transformacje nie były bijekcjami
wtedy nie byłoby możliwe odszyfrowanie unikalnej informacji.

(ii) Funkcje jednokierunkowe

Jest pewien typ funkcji, które odgrywają znaczącą rolę w kryptografii. Kosztem rygoru, dana jest intuicyjna
definicja funkcji jednokierunkowej

1.12 Definicja Funkcja f od zbioru X do zbioru Y jest nazywana funkcją jednokierunkową jeśli f(x) jest „łatwa”
do obliczenia dla wszystkich x Є X ale dla „zasadniczo wszystkich” elementów y Є Im(f) jest „obliczeniowo
nie wykonalna” aby znaleźć takie x Є X, że f(x) = y.

1.13 Notka (wyjaśnienie terminów z definicji 1.12)

(i)

Rygorystyczna definicja terminów „łatwa” i „obliczeniowo nie wykonalna” jest konieczna ale
byłaby umniejszeniem prostej idei, która została przekazana. Dla celów tego rozdziału
wystarczające będzie znaczenie intuicyjne.

(ii)

Fraza „dla zasadniczo wszystkich elementów w Y” odnosi się do faktu, że jest kilka wartości y
Є Y dla których łatwo znaleźć x Є X takie , że y =f(x). Na przykład, możemy obliczyć y =
f(x) dla malej liczby z wartości x a potem odwrócenie jej poprzez tablicę przeglądową.
Alternatywny sposób opisujący tą właściwość funkcji jednokierunkowej jest następujący: dla
losowego y Є Im(f) jest obliczeniowo niemożliwe znalezienie żadnego x Є X takiego , że

f(x) = y

Koncepcja funkcji jednokierunkowej jest zilustrowana przez następujący przykład.

1.14 Przykład (funkcja jednokierunkowa) Bierzemy X = {1, 2,3 ,4 ,..., 16} i definiujemy f9x) = r

dla

wszystkich x Є X gdzie r

jest resztą kiedy 3

jest dzielone przez 17. Jaśniej,

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

f (x)

3 9 10 13 5 15 11 16 14 8 7 4 12 2 6 1

Podając liczbę miedzy 1 a 16 jest relatywnie łatwo znaleźć jej obraz w f. Jednak, podając liczbę taką jak 7, bez
posiadania tejże tablicy, trudniej jest znaleźć x biorąc pod uwagę f(x) =7. Oczywiście, jeśli liczba jaką podajemy
to 3, wtedy jest jasne, że x =1, czyli to co potrzebujemy,; ale dla większości elementów w przeciwdziedzinie nie
jest to takie łatwe.

Jedno co trzeba zapamiętać, to to ,że jest to przykład, który używa bardzo małych liczb; ważnym

punktem tu jest to, że jest różnica w ilości pracy przy obliczeniu f(x) a ilością pracy w znalezieniu x danej f(x).
Nawet dla bardzo dużych liczb, f(x0 może być obliczona wydajnie przy zastosowaniu ponawianego algorytmu
podnoszenia do kwadratu - i – mnożenia (Algorytm 2.143), podczas gdy proces znajdowania x z f(x) jest dużo
trudniejszy.

1.15 Przykład (funkcja jednokierunkowa) Liczba pierwsza jest to liczba dodatnia, całkowita, większa niż 1,
której dodatnimi całkowitymi dzielnikami jest 1 i ona sama. Wybieramy liczby pierwsze p = 48611, q = 53933 ,
formujemy n = pq = 2624653723 i X ={1,2,3,..., n-1}. Definiujemy funkcję f z X przez f(x) = r

dla każdego x Є

X, gdzie r

jest resztą z x

dzielonego przez n. Na przykład, f(2489991) = 1981394214 ponieważ 2489991

5881949859*n +1981394114. Obliczenie f(x) jest relatywnie prostsze, ale odwrócenie procedury jest dużo
bardziej trudniejsze; to znaczy z danej reszty znaleźć wartość x , która pierwotnie była sześcianem (podniesiona
do trzeciej potęgi). Procedura ta odnosi się do obliczania modularnego pierwiastka sześciennego z modułu n.
Jeśli współczynniki z n są nieznane i duże, jest to trudny problem; jednakże, jeśli współczynniki p i q są znane
wtedy jest to wydajny algorytm dla obliczania modularnych pierwiastków sześciennych (Zobacz §8.2.2(i) po
szczegóły)

Przykład 1.15 pozostawił do rozważenia inny typ funkcji, który będzie udowadniał swoją przydatność
w późniejszych wydarzeniach.

(iii) Funkcja jednokierunkowa z zapadką

1.16 Definicja Funkcja jednokierunkowa z zapadką jest to funkcja jednokierunkowa f: X → Y z dodatkowymi
właściwościami , które dają kilka dodatkowych informacji (nazywanych informacjami zapadkowymi) i staje się
wykonywalna po znalezieniu dla danego y ε Im(f), x ε X takiego , że f(x) = y.

Przykład 1.15 ilustruje koncepcję jednokierunkowej funkcji z zapadką. Z dodatkowymi informacjami
współczynników z n = 2624653723 ( mianowicie, p= 48611 i q = 53933, każdy z nich jest długi na pięć cyfr
dziesiętnych) co staje się dużo łatwiejsze przy odwracaniu funkcji. Współczynniki 2624653723 są dosyć duże
aby znaleźć je poprzez ręczne obliczenia, co może być trudne. Oczywiście, każdy sensowny program
komputerowy może znaleźć współczynniki relatywnie szybko. Jednak, z drugiej strony, wybierając p i q jako
bardzo duże liczby pierwsze (każda mająca po 100 cyfr dziesiętnych) wtedy na dzisiejsze standardy, jest to
złożony problem, nawet z najmocniejszymi komputerami, wydedukować p i q po prostu z n. Jest to dobrze
znany problem rozkładu na czynniki pierwsze liczb całkowitych (zobacz § 3.2) i źródło wielu funkcji
jednokierunkowych z zapadką.

Pozostawmy rygorystycznie przyjęte czy są to rzeczywiście (prawdziwe) funkcje jednokierunkowe.

Można powiedzieć, że nie ma jeszcze dostarczonego rozstrzygnięcia istnienia takich funkcji pod rozsądną ( i
rygorystyczną) definicją „łatwa” i „obliczeniowo niewykonalna” Ponieważ istnienie funkcji jednokierunkowych
jest jeszcze nieznane, istnienie funkcji jednokierunkowych z zapadką jest również nieznane Jednakże są liczni
dobrzy kandydaci na funkcje jednokierunkowe i jednokierunkowe z zapadką. Wiele z nich jest omawianych w
tej książce, z położonym naciskiem na te , które są praktyczne.

Funkcje jednokierunkowe i jednokierunkowe z zapadką są podstawowe dla kryptografii klucza

publicznego (omawianej w § 1.8) Ważniejsze sprawy tej koncepcji staną się jaśniejsze, kiedy będziemy
rozważać aplikacje technik kryptograficznych. Będzie to warte zachodu zapamiętanie abstrakcyjnych koncepcji
z tej sekcji, jako konkretnych metod.

1.3.2 PERMUTACJE

Permutacje są funkcjami, które są często używane w różnych kryptograficznych konstrukcjach.

1.17 Definicja S jest skończonym zbiorem elementów. Permutacją p z S jest bijekcją (Definicja 1.8) z S do
samej siebie (tj. p: S

→ S)

1.18 Przykład (permutacja) S ={1,2,3,4,5}. Permutacja p: S

→ S jest zdefiniowana jak następuje:

p(1) = 3, p(2) = 5, p(3) = 4, p(4) = 2, p(5) = 1

Permutacja może być opisana na różne sposoby. Może być wyświetlona jak powyżej lub jako tablica:

1 2 3 4 5

P =

3 5 4 2 1

gdzie górny wiersz w tablicy jest dziedziną a dolny wiersz jest obrazem odwzorowanym p. Oczywiście, obie
reprezentacje są możliwe.
Ponieważ permutacje są bijekcjami, mają odwrotności. Jeśli permutacja jest zapisana jako tablica
(zobacz 1.1) jej odwrotność jest łatwo znaleźć poprzez wymianę wierszy w tablicy i przestawienie elementów w
nowym górnym wierszu jeśli jest to żądane (dolny wiersz będzie przeporządkowany odpowiednio) Odwrotność
p z przykładu 1.18 to

1 2 3 4 5

-1

5 4 1 3 2

1.19 Przykład (permutacja) Niech X będzie zbiorem liczb całkowitych {0,1,2,3,...pq –1} gdzie p i q są różnymi
liczbami pierwszymi (na przykład p i q są każda, długa na 10 cyfr dziesiętnych) i przypuśćmy ,że ani p-1 ani q –
1 nie są podzielne przez 3. wtedy funkcja p(x) = r

, gdzie r

jest resztą kiedy x

jest dzielone prze pq, można

uznać za permutację. Ustalenie odwrotności permutacji jest obliczeniowo niewykonalne przy dzisiejszych
standardach chyba ,ze p i q są znane (Przykład 1.15).

1.3.3 Inwolucje

Innym typem funkcji, do których się będziemy odnosić w § 1.5.3 jest inwolucja. Inwolucje mają właściwość
taka, że same są swoimi odwrotnościami.

1.20 Definicja Niech S będzie skończonym zbiorem a f bijekcją z S do S (tj. f: S

→ S). Funkcja f jest nazywana

inwolucją jeśli f = f

-1

. Odpowiednim sposobem zapisu tego jest f(f(x)) = x dla wszystkich x

ε S

1.21 Przykład (inwolucja) Rysunek 1.4 jest przykładem inwolucji. W diagramie inwolucji, zauważ ,że jeśli j
jest obrazem i wtedy i jest obrazem j

°1

°2

S 3

°3 S

°4

°5

Rysunek 1.4 Inwolucja 5 elementowego zbioru S

1.4 PODSTAWOWA TERMINOLOGIA I KONCEPCJE

Naukowe studiowanie jakiejś dyscypliny musi być zbudowane na rygorystycznych definicjach powstałych z
fundamentalnych koncepcji. Poniżej znajduje się lista terminów i podstawowych koncepcji używanych w całej
tej książce. Gdzie właściwie rygor uświęcono (tu w Rozdziale 1) w imię jasności.

Szyfrowanie dziedziny i przeciwdziedziny

• A oznacza skończony zbiór nazywany definicją alfabetu. Na przykład , A = {0,1} , alfabet binarny, jest

często używaną definicją alfabetu. Zanotujmy ,ze każdy alfabet może być zakodowany pod względem
alfabetu binarnego. Na przykład, są 32 binarne ciągi o długości pięć, wiec każda litera angielskiego
alfabetu może być powiązana z unikalnym ciągiem o długości pięć.

• M oznacza zbiór nazwany przestrzenią informacji. M składa się z ciągów symboli z definicjo alfabetu.

Element M jest nazwany informacją tekstem jawnym lub po prostu tekstem jawnym. Na przykład M
może składać się z ciągów binarnych, tekstu angielskiego, kodu komputerowego itd.

• C oznacza zbiór nazwany przestrzenią tekstu zaszyfrowanego. C skalda się z ciągów symboli z

definicji alfabetu, które mogą różnić się od definicji alfabetu dla M. Element C jest nazywany tekstem
zaszyfrowanym

Transformacje szyfrowani i deszyfrowania

• K oznacza zbiór nazwany przestrzenią klucza. Element K jest nazywany kluczem
• Każdy element e ε K unikalnie określa bijekcję z M do C, oznaczoną przez E

. E

jest nazywane

funkcją szyfrującą lub transformacją szyfrowania. Zauważmy , że E

musi być bijekcją jeśli proces jest

odwracany a unikalna informacja tekstem jawnym odzyskiwana dla każdego odrębnego tekstu
zaszyfrowanego.

• Dla każdego d ε K, D

oznacza bijekcję z C do M (tj. D

: C

→ M). D

jest nazywane funkcją

deszyfrującą lub transformacją deszyfracji.

• Proces stosowany dla transformacji E

do informacji m

ε M jest zazwyczaj odnoszony do szyfrowani m

lub szyfrowania z m

• Proces stosowany dla transformacji D

do tekstu zaszyfrowanego c jest zazwyczaj odnoszony do

deszyfrowani c lub deszyfrowania z c

• Schemat szyfrowania skała się ze zbioru { E

: e

ε K}transformacji szyfrowania i odpowiedniego zbioru

: d

ε K} transformacji deszyfrowania z taką właściwością , że dla każdego e ε K jest unikalny klucz

ε K taki , że D

= E

-1

; to znaczy, że D

(m)) = m dla wszystkich m

ε M. Do schematu szyfrowani

czasami odnosi się jako do teksty zaszyfrowanego.

• Klucze e i d w poprzednich definicjach stanowiły parę kluczy i czasami są oznaczane przez (e, d).

Odnotujmy ,że e i d mogą być takie same.

• Budowa schematu szyfrowania wymaga jednego wyboru przestrzeni informacji M , przestrzeni tekstu

zaszyfrowanego C i przestrzeni klucza K, zbioru transformacji szyfrowania { E

: e

ε K}, i

odpowiadającego zbioru transformacji deszyfrowania {D

: d

ε K}

Osiąganie poufności

Schemat szyfrowania może być zastosowany dla celu osiągnięcia poufności. Alice i Bob najpierw po cichu
wybierają lub po cichu wymieniają parę kluczy (e, d). W późniejszym czasie jeśli Alice życzy sobie wysłać
wiadomość m

ε M do Boba, oblicza c = E

(m) i wysyła to do Boba. Przy odbiorze c Bob oblicza D

( c) = m i w

związku z tym uzyskuje oryginalną wiadomość.

Powstaje pytanie dlaczego klucze są potrzebne.(Dlaczego nie wybrać tylko jednej funkcji szyfrującej i

jej odpowiedniej funkcji deszyfrującej?) Posiadanie transformacji które są bardzo podobne ale
charakteryzowane przez klucze oznacza ,że jeśli jakaś szczególna transformacja szyfrowania / deszyfrowania
jest ujawniona, wtedy nie musi przeprojektować schematu wejścia ale po postu zmienia się klucz . Jest dobrą
praktyką kryptograficzną częsta zmiana klucza (transformacja szyfrowania / deszyfrowania). Jako fizyczną
analogię rozważmy zwykłą kombinację blokad. Struktura blokady jest dostępna każdemu kto życzy sobie
nabyć jedną, ale kombinacja jest wybrana i ustawiona przez właściciela. Jeśli właściciel podejrzewa, że
kombinacja została ujawniona może łatwo zmienić ją bez zmian w mechanizmie fizycznym.

1.22 Przykład (schemat szyfrowania) Niech M = {m

, m

,m3} a C = {c

, c

}. Jest dokładnie 3! = 6 bijekcji z

M do C. Przestrzeń klucza K = {1,2,3,4,5,6} ma sześć elementów w nim, każdy określony jedną transformacją.
Rysunek 1.5 ilustruje sześć funkcji szyfrujących, każda oznaczona przez E

, 1

≤ i ≤ 6. Alicja i Bob zgadzają się

na transformację

°c

Rysunek 1.5 Schematy prostego schematu szyfrującego

powiedzmy E

. Szyfrując wiadomość m

, Alice oblicza E

) = c

i wysyła c

do Boba. Bob deszyfruje c

poprzez odwrócenie strzałek na diagramie dla E

i zauważa, że c

wskazuje na m

Kiedy M jest małym zbiorem, diagram funkcjonalny jest prostym wizualnym sposobem opisu odwzorowania. W
kryptografii, zbiór M jest zazwyczaj ogromną liczbą i , tak jak, opis wizualny jest nie wykonalna. To co jest
wymagane, w tych przypadkach, jest jakimś innym, prostym sposobem opisu transformacji szyfrowania i
deszyfrowania, takich jak algorytmy matematyczne.

Rysunek 1.6 dostarcza prostego modelu dwu jednostkowej komunikacji używającej szyfrowania

Rysunek 1.6 Schemat dwu jednostkowej komunikacji używającej szyfrowania

Uczestnicy komunikacji

Poniższa terminologii jest zdefiniowana w odniesieniu do rysunku 1.6

• Jednostka lub strona, jest to ktoś lub coś, co wysyła, odbiera lub manipuluje informacją. Alice i Bob są

jednostkami w Przykładzie 1.22. Jednostką może być osoba , terminal komputerowy itd.

• Nadawcą jest jednostka dwu jednostkowej komunikacji który zajmuje się przekazywaniem informacji.

Na rysunku 1.6 Nadawcą jest Alice

• Odbiorca jest to jednostka w dwu jednostkowej komunikacji, który jest uprawniony do odebrania

informacji. Na rysunku 1.6 Odbiorcą jest Bob

• Przeciwnikiem jest jednostką w dwu jednostkowej komunikacji, który nie jest ani nadawcą ani

odbiorcą, i który próbuje pokonać bezpieczeństwo przekazywanej informacji pomiędzy nadawcą a
odbiorcą. Różne inne nazwy są synonimami przeciwnika takie jak wróg, atakujący, intruz, włamywacz.
Przeciwnik często o próbuje odgrywać rolę albo potwierdzonego nadawcy lub potwierdzonego
odbiorcy.

Kanały

• Kanał jest to sposób przekazywani informacji od jednej jednostki do drugiej

• Fizycznie bezpieczny kanał lub bezpieczny kanał jest tym , który nie jest fizycznie dostępnym dla

przeciwnika

• Kanał pozbawiony bezpieczeństwa, jest tą częścią, inną niż ta dla której informacja jest przeznaczona i

może być przestawiana, usuwana, wprowadzana lub czytana

• Kanał bezpieczny jest to ta część w której przeciwnik nie może przestawiać, usuwać, wprowadzać lub

czytać

Jedna rzecz powinieneś odnotować, subtelną różnicę pomiędzy fizycznie bezpiecznym kanałem a bezpiecznym
kanałem – kanał bezpieczny może być zabezpieczony poprzez fizyczne lub kryptograficzne techniki, ten ostatni
stanowi temat tej książki. Pewne kanały z założenia są bezpieczne fizycznie. Te wprowadzające zaufanych
kurierów, personel kontaktujący się pomiędzy częściami komunikacji i specjalistyczne odnośniki do kilku nazw.

Bezpieczeństwo

Fundamentalną przesłanką w kryptografii jest to ,że zbiory M,C,K, {E

: e

ε K}, {D

: d

ε K}są publicznie

dostępne. Kiedy dwie jednostki życzą sobie skomunikować się bezpiecznie używając schematu szyfrowania,
jedyną rzeczą zachowującą tajemnicę jest szczególna para kluczy (e, d), której użyją i którą muszą wybrać.
Można zyskać dodatkowe bezpieczeństwo poprzez zachowanie klasy transformacji szyfrowani lub

deszyfrowania w tajemnicy, ale nie powinniśmy bazować na bezpieczeństwie schematu jednostki przy tym
podejściu. Historia pokazuje ,że zachowanie tajemnicy transformacji jest rzeczywiście bardzo trudne.

1.23 Definicja. Schemat szyfrowania jest złamany jeśli trzecia jednostka, bez wcześniejszej znajomości pary
kluczy (e, d) może systematycznie odzyskiwać tekst jawny z odpowiedniego tekstu zaszyfrowanego wewnątrz
właściwego odcinka czasu.

Właściwy odcinek czasu będzie funkcją użytecznego czasu życia danej będącej chronioną. Na przykład,

instrukcja zakupu pewnych akcji ,może tylko musieć przechować tajemnicę przez kilka minut podczas gdy stan
tajemnicy może będzie musiał pozostawać poufnym bez końca.

Schemat szyfrowania może być łamany poprzez próby wszystkich możliwych kluczy aby zobaczyć ,

która z jednostek komunikacji używa ich (zakładając, że klasa funkcji szyfrowania jest publicznie znana). Jest
to nazywane przeszukiwaniem pełnym, wyczerpującym przestrzeni klucza. Oznacza to ,że liczba kluczy (tj,
rozmiar przestrzeni klucza) powinna być na tyle duża aby uczynić to podejście obliczeniowo niewykonalnym.
Jest to obiektyw projektanta schematu szyfrowania, który jest najlepszym podejściem do łamania systemu
Często w literaturze są wymieniane dezyderaty Kerckhoff’a, zbiór wymagań dotyczących systemu
szyfrowania. Tu mamy podane zasadnicze, pierwotne stany Kerckhoffa:

1. System powinien być, jeśli nie teoretycznie nie do złamania, nie do złamania w praktyce ;
2. Kompromis

szczegółów systemu nie powinien sprawiać kłopotów korespondentom;

3.  Klucz powinien być zapamiętywalny bez zapisywania i łatwy do zmiany;
4.  Kryptogram powinien być możliwy do transmisji poprzez telegraf
5.  Aparat szyfrowania powinien być przenośny i operowalny poprzez pojedynczą osobę; i
6.  System powinien być łatwy, wymagający albo znajomości długiej listy zasad albo obciążenia umysłu.

Lista tych wymagań została wyrażona w 1883 roku i, większość tych części, jest użyteczna do dzisiaj. Punkt 2
pozwala na to , że klasa transformacji szyfrowania była znana publicznie a bezpieczeństwo systemu powinno
tkwić tylko w zmianie klucza

Ogólne informacje o bezpieczeństwie

Jak dotąd terminologia była ograniczona do szyfrowania i deszyfrowania w celach prywatnych. Informacje
bezpieczeństwa są dużo szersze, obejmując takie sprawy jak uwierzytelnianie i integralność danych. Kilka
ogólnych definicji na ten temat omówimy później w tej książce.

• Informacje o usłudze zabezpieczeń jest metodą dostarczającą kilku specyficznych aspektów

bezpieczeństwa. Na przykład integralność przesyłanych danych jest obiektywem bezpieczeństwa a
metoda zapewniając ten aspekt jest informacją o usłudze zabezpieczeń.

• Łamanie informacji o usłudze zabezpieczeń (która często dotyczy więcej niż tylko prostego

szyfrowania) implikuje niepowodzenie obiektywu zamierzonej usługi.

• Przeciwnik pasywny jest to przeciwnik, który jest zdolny tylko do czytania informacji z

niezabezpieczonego kanału.

• Przeciwnik aktywny jest to przeciwnik, który może również wysyłać, zmieniać, lub usuwać

informacje z niezabezpieczonego kanału.

Kryptologia

• Kryptoanaliza jest to nauka technik matematycznych służących pokonaniu technik kryptograficznych, i

bardziej ogólnie, informacji o usłudze zabezpieczeń.

• Kryptoanalityk jest to ktoś, kto zajmuje się kryptoanalizą

• Kryptologia jest to nauka kryptografii (Definicja 1.1) i kryptoanalizy

• System kryptograficzny jest ogólnym terminem odnoszącym się do zbioru wyrażeń pierwotnych

użytych przy dostarczaniu informacji o usłudze zabezpieczeń. Dosyć często ten termin jest stosowany
wraz z wyrażeniami pierwotnymi dostarczającymi poufności np. szyfrowaniem

Techniki kryptograficzne są zazwyczaj dzielone na dwie główne grupy: klucz symetryczny i klucz

publiczny. Metody szyfrowania tych typów będą omawiane oddzielnie w § 1.5 i § 1.8. Inne definicje i
terminologia będą wprowadzane wedle wymagań.

1.5 SZYFROWANIE KLUCZEM SYMETRYCZNYM

1.5.1 Ogólne omówienie bloku szyfrowego i szyfru strumieniowego

1.24 Definicja Rozpatrzmy schemat szyfrowania składający się ze zbioru transformacji szyfrowania i
deszyfrowania, odpowiednio, {Ee : e

ε K} i {Dd: d ε K}, gdzie K jest przestrzenią klucza. Schemat

szyfrowania byłby kluczem symetrycznym jeśli dla każdej powiązanej pary kluczy szyfrowania / deszyfrowania
(e, d) jest „łatwe” obliczeniowo ustalenie d znając tylko e i określenie e z d.
Ponieważ e = d w większości praktycznych schematów szyfrowania kluczem symetrycznym, termin
klucz symetryczny wydaje się poprawnym. Innym terminem używanym w literaturze są klucz pojedynczy, klucz
–jeden, , klucz prywatny i szyfrowanie symetryczne. Przykład 1.25 ilustruje ideę szyfrowania kluczem
symetrycznym.
Przykład 1.25 (szyfrowanie kluczem symetrycznym) Niech A = {A,B,C,...,X,Y,Z} będzie angielskim
alfabetem. Niech M i C będą zbiorem wszystkich ciągów o długości pięć nad A. Klucz e jest wyborem będącym
permutacją z A. Szyfrując, angielska informacja jest dzielona na grupy każda mająca pięć liter (z właściwym
uzupełnieniem jeśli długość informacji nie jest wielokrotnością pięciu) a permutacja e jest używana dla każdej
litery w tym czasie. Deszyfrując, odwracamy permutację d = e

-1

stosując dla każdej litery tekstu

zaszyfrowanego. Na przykład przypuśćmy ,że klucz e jest permutacją, która odwzorowuje każdą literę do
litery, która jest trzecią pozycją na prawo, jak pokazano poniżej

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

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

wiadomość

m = THISC IPHER ISCER TAINL YNOTS ECURE

jest szyfrowana do

c = E

(m) = WKLVF LSKHU LVFHU WDLQO BQRWV HFXUH

Dwu jednostkowa komunikacja używająca klucza symetrycznego może być opisana poprzez diagram blokowy z
rysunku 1.7, który jest rysunkiem 1.6 z dodanym zabezpieczonym (oboma poufnym i uwierzytelnienia)
kanałami

Rysunek 1.7 Dwu jednostkowa komunikacja używająca szyfrowani, z bezpiecznym kanałem dla wymiany
klucza. Klucz deszyfrujący d może być sprawnie obliczony z klucza szyfrującego e

Jedną z głównych kwestii z systemem klucza symetrycznego jest znalezienie wydajnej metody uzgodnionej na
bezpieczną wymianę kluczy. Do problemu tego odnosimy się jako problemu dystrybucji klucza (zobacz
Rozdział 12 i 13)
Zakładamy, że wszystkie części znają zbiór transformacji szyfrowania / deszyfrowania (tzn. znają
wszystkie schematy szyfrowania). Jak już było zaakcentowane kilka razy jedynie informacje które powinny być
wymagane będą zachowywać tajemnicę klucza d. Jednakże w szyfrowaniu kluczem symetrycznym oznacza to
,że klucz e musi być również zachowany w tajemnicy, ponieważ d może zostać wydedukowany z e. Na rysunku
1.7 klucz szyfrujący e jest przenoszony od jednej jednostki do innej ze zrozumieniem, że oboje mogą zbudować
klucz deszyfrujący d.

Są dwie klasy schematów szyfrowania kluczem symetrycznym, które są powszechnie rozpoznawane:

szyfr blokowy i szyfr strumieniowy.
1.26 Definicja Szyfr blokowy jest schematem szyfrowania, który łamie wiadomości tekstu jawnego
przekazywanego do ciągów (nazywanych blokami) o stałej długości t ponad alfabetem A i szyfrującym jeden
blok w jednym czasie.

Wiele dobrze znanych technik szyfrowani a kluczem symetrycznym to szyfr blokowy. Liczba

przykładów tego jest podana w rozdziale 7. Dwie ważne klasy szyfru blokowego to szyfr zastępowania i szyfr
transpozycji (§ 1.5.2). Tworząc szyfr (§ 1.5.3) łączymy je. Szyfr strumieniowy jest omówiony w § 1.5.4, a
komentarze na temat przestrzeni klucza występują w § 1.5.5.

1.5.2 Szyfr zastępowania i szyfr transpozycji

Szyfry zastępowania są szyframi blokowymi, które zastępują symbole (lub grupy symboli) przez inne symbole
lub grupy symboli.

Prosty szyfr zastępowania

1.27 Definicja Niech A będzie alfabetem q symboli a M zbiorem wszystkich ciągów długich na t ponad A.
Niech K będzie zbiorem wszystkich permutacji na zbiorze A. Definiujemy dla każdego e

ε K transformację

szyfrowania E

tak:

(m)= (e(m

)e(m

)....e(m

)) = (c

...c

) = c

Gdzie m = (m

...m

)

ε M. Innymi słowy dla każdego symbolu t -krotnego, zamienia (zastępuje) go przez inny

symbol z A zgodnie ze stałą permutacją e. Deszyfrując c = (c

...c

) obliczamy odwrotność permutacji d = e

-1

( c) =(d(c

)d(c

)...d(c

)) = (m

...m

) = m

jest nazywane prostym szyfrem zastępowania lub monoalfabetycznym szyfrem zastępowania

Liczba

różnych szyfrów zastępowania to q! i jest niezależnym rozmiarowo szyfrem blokowym.

Przykład 1.25 jest przykładem prostego bloku szyfru zastępowania o długości pięć. Prosty szyfr zastępowania z
małym rozmiarowo blokiem dostarcza niewystarczającego bezpieczeństwa nawet kiedy przestrzeń klucza jest
bardzo duża. Jeśli alfabet jest alfabetem angielskim, jak w przykładzie 1.25, wtedy rozmiar przestrzeni klucza to
26!

≈ 4 x10

, a mimo to używany klucz może być określony całkiem łatwo poprzez przeanalizowanie skromnej

ilości tekstu zaszyfrowanego. To wynika z prostej obserwacji, że jest zachowana częstotliwość występowania
liter w tekście zaszyfrowanym. Na przykład litera E występuje częściej niż inne litery w angielskim tekście., W
związku z tym częstsze występowanie litery w sekwencji bloku tekstu zaszyfrowanego jest bardzo
prawdopodobne, że odpowiada literze E w tekście jawnym. Poprzez obserwację skromnej ilości bloków tekstu
zaszyfrowanego, kryptoanalityk może określić klucz

Homofoniczne szyfry zastępowania
1.28 Definicja Każdy symbol a

ε A , powiązany ze zbiorem H(a) ciągów t symboli, z takim ograniczeniem ,że

zbiory H(a), a

ε A są PAIRWISE DISJOINT. Homofoniczny szyfr zastępowania zamienia miejscami każdy

symbol a z bloku wiadomości tekstu jawnego z losowo wybranym ciągiem z H(a). Deszyfrując ciąg c z t
symboli, musimy określić a

ε A takie ,że c ε H(a). Klucz do szyfru składa się ze zbiorów H(a).

1.29 Przykład (homofoniczny szyfr zastępowania) Rozważmy A = {a, b}, H(a) = {00, 10{ i H9b) = {01, 11}.
Blok wiadomości tekstu jawnego ab szyfrujemy do jednego z następujących : 0001, 0011, 1001, 1011.
Zauważmy , że przeciwdziedzina funkcji szyfrującej (dla wiadomości o długości dwa) składa się z poniższych
PAIRWISE DISJOINT zbirów czteroelementowych ciągów bitowych:

aa

→

{0000, 0010, 1000, 1010}

→

{0001, 0011, 1001, 1011}

→

{0100, 0110, 1100, 1110}

→

{0101, 0111, 1101, 1111}

Każdy 4 bitowy ciąg jednoznacznie identyfikuje element przeciwdziedziny , a stąd wiadomości tekstu jawnego.
Często symbole nie występują z równą częstotliwością w wiadomości tekstu jawnego. Z pojedynczym
szyfrem zastępowania ta właściwość niejednolitej częstotliwości jest odzwierciedlona w tekście zaszyfrowanym
w Przykładzie 1.25. szyfr homofoniczny może być zastosowany aby uczynić częstotliwość wystąpień symboli
tekstu zaszyfrowanego bardziej jednolitą, przy kosztownym wzroście danej. Deszyfrowanie nie jest zadaniem
tak łatwym jak dla prostego szyfru zastępowania

Polialfabetyczny szyfr zastępowania

1.30 Definicja Polialfabetyczny szyfr zastępowania jest blokiem szyfrowym z blokiem o długości t ponad
alfabet A mającym następujące właściwości :

(i) Przestrzeń klucza K składa się ze wszystkich uporządkowanych zbiorów permutacji t (p

, p

, ..., p

)

gdzie każda permutacja p

jest zdefiniowana w zbiorze A;

(ii) Szyfrowanie

wiadomości m =(m

...m

) pod kluczem e =(p

...p

) jest dane poprzez E

(m) =

)...p

)); i

(iii)

Deszyfrowanie klucza powiązanego z e =(p

,...p

) to d =(p

-1

, p

-1

,...p

-1

)

1.31 Przykład (szyfr Vigenère’a) Niech A ={A,B,C,...,X,Y,Z} a t =3. Wybieramy e =(p

) gdzie p

odwzorowuje każdą literę do litery o trzy pozycje na prawo w alfabecie, p

o siedem pozycji na prawo a p

dziesięć pozycji w prawo. Jeśli

m = THI SCI PHE RIS CER TAI NLY NOT SEC URE

wtedy

c = E

(m) = WOS VJS SOO UPC FLB WHS QSI QVD VLM XYO

Szyfr polialfabetyczny ma tą zaletę w stosunku do prostego szyfru zastępowania, że nie jest zachowywana
częstotliwość symboli. W powyższym przykładzie litera E jest szyfrowana do O jak i L. Jednakże, szyfr
polialfabetyczny nie jest znacząco trudniejszy do kryptoanalizy , przy podejściu podobnym do prostego szyfru
zastępowania. Faktycznie, ponieważ blok długości t jest określony, litery tekstu zaszyfrowanego mogą być
dzielone na t grup (gdzie grupa 1 ,1

≤ i ≤ t, składające się z liter tekstu zaszyfrowanego używających permutacji

) a analiza częstotliwości może zostać wykonana na każdej z grup.

Szyfr transpozycji

Inna klasą szyfrów klucza symetrycznego jest prosty szyfr transpozycji, który po prostu przestawia symbole w
bloku
1.32 Definicja Rozważmy schemat szyfrowania bloku klucza symetrycznego z blokiem o długości t. Niech K
będzie zbiorem wszystkich permutacji w zbiorze {1,2...,t}. Dla każdego e

ε K definiujemy funkcję szyfrującą

(m) = (m

e(1)

e(2)

...m

e(t)

)

Gdzie m =(m

..m

)

ε M, przestrzeni informacji. Zbiór wszystkich takich transformacji jest nazywany prostym

szyfrem transpozycji. Klucz deszyfrujący odpowiedni dla e jest odwrotnością permutacji d = e

-1

. Deszyfrujemy

c =(c

...c

), obliczamy D

( c) = (c

d(1

d(2)

...c

d(t)

Prosty szyfr transpozycji zachowuje liczbę symboli danego typu wewnątrz bloku a zatem jest łatwy do

kryptoanalizy.

1.5.3 Kompozycje szyfru

Aby opisać tworzenie szyfru, potrzebne jest wprowadzenie kompozycji funkcji. Budowy są dogodnym
sposobem konstruowania bardziej złożonych funkcji z prostszych.

Kompozycje funkcji
1.33 Definicja Niech S, T i U będą skończonymi zbiorami a f: S

→ T i g : T → U funkcjami. Kompozycja g z

f oznaczona g

° f (lub prościej gf), jest funkcją z S do U jak przedstawia rysunek 1.8 i zdefiniowana poprzez (g °

f)(x) = g(f(x)) dla wszystkich x

ε S

Rysunek 1.8 kompozycja funkcji g

° f z funkcji g i f

Kompozycja może być łatwo poszerzona do więcej niż dwóch funkcji. Dla funkcji

, f

, ...f

, można zdefiniować

kompozycję f

°....° f

°f

, pokazując ,że dziedzina f

równa się przeciwdziedzinie f

t-1

i tak dalej.

Kompozycje i inwolucje

Inwolucje zostały wprowadzone w § 1.3.3 jako prosta klasa funkcji z interesującą właściwością: E

(x)) = x

dla wszystkich x w dziedzinie E

; to jest E

° E

są funkcjami identycznymi.

1.34 Uwaga (kompozycje i inwolucje) Kompozycja dwóch inwolucji nie jest koniecznie inwolucją, jak ilustruje
to rysunek 1.9. Jednakże, inwolucje mogą być skomponowane do pobierania bardziej skomplikowanych funkcji,
których odwrotność jest łatwa do znalezienia. Jest to ważna cecha przy deszyfrowaniu. Na przykład jeśli E

,...E

są inwolucjami wtedy inwersja E

....E

to E

-1

= E

kt-1

...E

, kompozycja inwolucji w

porządku odwrotnym

°1 1°

°1

°2 2°

°2

°3 3°

°3

°4 4°

°4

° f

Rysunek 1.9 Kompozycja g

°f z inwolucji g i f nie jest inwolucją

Szyfr kaskadowy
Pojedynczo prosty szyfr zastępowania i szyfr transpozycji nie dostarczają bardzo wysokiego poziomu
bezpieczeństwa. Jednakże poprzez połączenie tych transformacji jest możliwe uzyskać silny szyfr. Jak
zobaczymy w Rozdziale 7 jest wiele praktycznych i wydajnych systemów klucza symetrycznego szyfru
kaskadowego. Przykładem szyfru kaskadowego jest kompozycja z t

≥ 2 transformacji E

, E

....E

gdzie każde

, 1

≤ i ≤ t jest albo szyfrem zastępowania albo szyfrem transpozycji, Dla celów tego wprowadzenia

kompozycja z zastępowania i transpozycji będzie nazywana zaokrągleniem
1.35 Przykład (szyfr kaskadowy) Niech M = C = K będą zbiorem wszystkich ciągów binarnych o długości
sześć. Liczba elementów w M to 2

= 64. Niech m = (m

...m

) i zdefiniowane

(1)

(m) = m

⊕ k, gdzie k ε K,

(2)

(m) = (m4m5m6m1m2m3)

Tu,

⊕ jest operacją LUB wykluczającego (XOR) zdefiniowaną jak następuje: 0 ⊕ 0 = 0, 0 ⊕ 1 = 1, 1 ⊕ 0 = 1,

⊕ 1 = 0. E

(1)

jest polialfabetycznym szyfrem zastępowania a E

(2)

jest szyfrem transpozycji (nie wymagającego

klucza). Produkt E

(1)

(2)

jest zaokrągleniem. Tu szyfr transpozycji jest bardzo prosty i nie określony przez klucz

1.36 Uwaga (zamieszanie i dyfuzja). Zastępowanie w zaokrągleniu dodaje zamieszania do procesu szyfrowania
podczas gdy transpozycja dodaje dyfuzji. Zamieszanie jest zamierzone aby uczynić związek pomiędzy kluczem
a tekstem zaszyfrowanym tak złożonym jak to możliwe. Dyfuzja odnosi się do przestawiania lub rozdzielania
bitów w informacji, tak ,ze każdy nadmiarowy w tekście jawnym jest rozdzielany przy tekście zaszyfrowanym.
Zaokrąglenie może dodać oba , zamieszanie i dyfuzję do szyfrowania Większość nowoczesnych systemów
szyfrów blokowych dołącza liczbę zaokrągleń po kolei do szyfrowanego tekstu jawnego.

1.5.4 Szyfr strumieniowy

Postać szyfru strumieniowego jest ważną klasą schematów szyfrowania kluczem symetrycznym. Są one , w
pewnym sensie, bardzo prostym szyfrem blokowym o długości bloku równym jeden. To co czyni je użytecznymi
to fakt ,że transformacja szyfrowania może zmieniać się dla każdego symbolu tekstu jawnego będącego
szyfrowanym. W sytuacji gdzie transmisja błędów jest wysoce prawdopodobna, szyfr strumieniowy są korzystne
ponieważ nie mają propagacji błędów. Mogą również być użyte kiedy dana musi być przetwarzana jeden symbol
w czasie (np. jeśli brakuje pamięci lub buforowanie danych jest ograniczone)

1.37 Definicja Niech K będzie przestrzenią klucza dla zbioru transformacji szyfrowania. Sekwencja symboli
e

....e

ε K jest nazywana strumieniem klucza.

1.38 Definicja Niech A będzie alfabetem q symboli a E

prostym szyfrem zastępowania z blokiem długości 1

gdzie e

ε K m

....będą ciągiem tekstu jawnego a e

... będą strumieniem klucza z K. Szyfr strumieniowy

pobiera ciąg tekstu jawnego i tworzy ciąg tekstu zaszyfrowanego c

...gdzie c

= E

). Jeśli d

oznacza

odwrotność e

wtedy D

) = mi deszyfruje ciąg tekstu zaszyfrowanego.

Szyfr strumieniowy stosuje prostą transformację szyfrowania zgodną z używanym strumieniem klucza. Strumień
klucza może być generowany losowo lub poprzez algorytm generujący strumień klucza z początkowego małego
strumienia klucza (nazywanego ziarnem) lub ziarna i poprzednich symboli tekstu zaszyfrowanego. . Taki
algorytm jest nazywany generatorem strumienia klucza.

Szyfr Vernam’a

Współczynnik motywacji dla szyfru Vernam’a był jego uproszczeniem i łatwą implementacją.

1.39 Definicja Szyfr Vernam’a jest szyfrem strumieniowym zdefiniowanym w alfabecie A={0,1]. Informacja
binarna m

...m

działa na binarnym strumieniu klucza k

...k

tej samej długości tworząc ciąg tekstu

zaszyfrowanego c

....c

gdzie

= m

⊕ k

, 1

≤ i ≤ t

Jeśli strumień klucza jest wybierany losowo i nigdy później nie używany, szyfr Vernam’a jest nazywany
szyfrem z kluczem jednorazowym.
Aby

zobaczyć jak szyfr Vernam’a odpowiada Definicji 1.38, zaobserwuj ,że są dokładnie dwa szyfry

zastępowania w zbiorze A. Jeden jest po prostu identyczny ze wzorem E

, który wysyła 0 do 0 i 1 do 1; drugi E

wysyła 0 do 1 i 1 do 0. Kiedy strumień klucza zawiera 0 , stosujemy E

dla odpowiadającego mu symbolu tekstu

jawnego, w przeciwnym razie stosujemy E

Jeśli strumień klucza jest użyty ponownie, jest sposób na zaatakowanie systemu. Na przykład jeśli
c

...c

i c

’c

’...c

’ są dwoma ciągami tekstu zaszyfrowanego tworzącymi ten sam strumień klucza k

...k

wtedy

= m

⊕ k

, c

’ = m

’

⊕ k

a c

⊕ c

’ = m

⊕ m

’ .Redundancja w tym ostatnim przypadku może umożliwić kryptoanalizę.

Szyfr z kluczem jednorazowym może być pokazany jako teoretycznie nie do złamania. To znaczy, jeśli

kryptoanalityk ma ciąg teksty zaszyfrowanego c

...c

zaszyfrowany przy użyciu losowego strumienia klucza,

który był użyty tylko raz , kryptoanalityk może zrobić nie więcej niż tylko zgadywać tekst jawny będący
binarnym strumieniem o długości t(tj. t bitowy ciąg binarny jest równy prawdopodobnie tekstowi jawnemu).
Świadczy to, że zrealizowanie systemu nie do złamania wymaga klucza losowego o tej samej długości co
wiadomość . Redukuje to praktyczność systemu, z wyjątkiem kilku specjalistycznych sytuacji. Podobno dopóki
bardzo niedawno komunikacja liniowa pomiędzy Moskwą a Waszyngtonem była zabezpieczona poprzez szyfr z
kluczem jednorazowym. Transport klucza odbywał się za pomocą zaufanego kuriera.

1.5.5 Przestrzeń klucza

Rozmiar przestrzeni klucza jest liczbą pary kluczy szyfrowania / deszyfrowania, które są dostępne w systemie
szyfrowania. Klucz jest zazwyczaj zwartym sposobem określającym transformację szyfrowania (ze zbioru
wszystkich transformacji szyfrowania) będącą w użyciu . Na przykład, blok szyfru transpozycyjnego o
długości t ma t! Funkcji szyfrujących do wyboru. Każda może być po prostu opisana poprzez permutację, która
jest nazywana kluczem.
Jest

wielką pokusą związanie bezpieczeństwa schematu szyfrowania z rozmiarem przestrzeni klucza.

Poniższa informacja jest ważna, zapamiętaj.

1.40 Fakt Koniecznym, ale zazwyczaj nie wystarczającym, warunkiem dla schematu szyfrowania będącego
bezpiecznym, jest to, żeby przestrzeń klucza była wystarczająco duża do wykluczenia przeszukiwania
wyczerpującego.
Na

przykład, prosty szyfr zastępowania w Przykładzie 1.25 ma przestrzeń klucza o rozmiarze 26!

≈ 4 x

. Polialfabetyczny szyfr zastępowania z Przykładu 1.31 ma przestrzeń klucza o rozmiarze (26!)

≈ 7 x 10

Przeszukiwanie wyczerpujące całej przestrzeni klucza jest zupełnie niewykonalne, a oba szyfry są relatywnie
słabe i dostarczają kruchego bezpieczeństwa.

1.6 Podpisy cyfrowe.
Kryptograficzna funkcja pierwotna, która jest fundamentalna w uwierzytelnianiu, autoryzacji i nie
zaprzeczalności jest podpisem cyfrowym .Celem podpisu cyfrowego jest dostarczenie oznaczenia dla jednostki
powiązanej swoją tożsamością z fragmentem informacji. Proces podpisu pociąga za sobą transformację
wiadomości i tajnych informacji przechowywanej przez jednostkę w znaczniku nazywanym podpisem. Ogólny
opis poniżej.

Nazewnictwo i ustawienia

• M jest zbiorem wiadomości, które mogą być podpisane

• S jest zbiorem elementów nazywanych podpisami, być może binarne ciągi o stałej długości

• S

jest transformacja z wiadomości ze zbioru M do podpisu zbioru S i jest nazywany podpisywaniem

transformacji dla jednostki A. Transformacja S

jest utrzymaną tajemnicą przez A i będzie użyta do

stworzenia podpisów dla wiadomości z M

• V

jest transformacją ze zbioru M x S do zbioru {true, false}. V

jest nazywane weryfikacją

transformacji dla podpisów A, jest publicznie znana i jest używana przez inne jednostki do weryfikacji
podpisów stworzonych przez A

1.41 Definicja Transformacje S

i V

dostarczają schematu podpisu cyfrowego dla A. Czasami jest używany

termin mechanizm podpisu cyfrowego
1.42 Przykład (schemat podpisu cyfrowego) M = {m

, m

} i S={s

, s

}. Lewa strona rysunku 1.10

wyświetla funkcje podpisu S

ze zbioru M i, a prawa strona, odpowiadająca funkcję weryfikacji V

Rysunek 1.10 Funkcja podpisu i weryfikacji dla schematu podpisu cyfrowego

Procedura podpisu

Jednostka A (podpisujący) tworzy podpis dla wiadomości m

ε M poprzez wykonanie:

1. Obliczenia s =S

(m)

2. Przekazania pary (m, s) s jest nazywane podpisem dla wiadomości m

Procedura weryfikacji

Weryfikując ten podpis s w wiadomości m stworzonej przez A, jednostka B (weryfikujący) wykonuje
następujące kroki;

1. Uzyskuje

funkcję weryfikującą V

z A

2. Oblicza u = V

(m, s)

3. Akceptuje podpis stworzony przez A jeśli u = true, i odrzuca podpis jeśli u = false

1.43 Uwaga (zwięzłe przedstawienie) Transformacje S

. i V

są zazwyczaj charakteryzowane zwięźlej przez

klucz to znaczy, jest klasa algorytmów podpisywania i weryfikacji publicznie znanych, a każdy algorytm jest
identyfikowany przez klucz. Zatem algorytm podpisywania S

z A jest określony przez klucz k

a A jest tylko

wymagane do zachowania tajnego k

. Podobnie algorytm weryfikacji V

z A określany przez klucz l

, który

jest uczyniony publicznym.

1.44 Uwaga (podpisy odręczne). Podpisy odręczne mogą być interpretowane jako specjalna klasa podpisów
cyfrowych. Zobaczmy to biorąc zbiór podpisów S zawierających tylko jeden element którym jest podpis
odręczny z A oznaczony przez s

. Funkcja weryfikacji po prostu sprawdza czy podpis na wiadomości

zapewniony przez A to s

Niepożądaną cechą w uwadze 1.44 jest to ,że podpis nie jest uzależniony od wiadomości. W związku z
tym są narzucane dalsze ograniczenia na mechanizmy podpisu cyfrowego, które kolejno omówimy.

Wymagane właściwości dla funkcji podpisu i weryfikacji

Jest kilka właściwości, które muszą spełnić transformacje podpisu i weryfikacji.

(a) s jest poprawnym podpisem A na wiadomości m jeśli i tylko if V

(m, s) = true

(b) Jest obliczeniowo niemożliwe dla żadnej jednostki oprócz A znaleźć, dla m

ε M, s ε S takie, że V

(m,

s) = true

Rysunek 1.10 graficznie pokazuje właściwość (a). Są strzałki w diagramie dla V

z (m

, s

) ,do true są strzałki z

do s

w diagramie dla S

. Właściwość (b) dostarcza bezpieczeństwa dla metody – związuje unikalny podpis A

z wiadomością, która jest podpisywana.

Nie ma jeszcze formalnie dowiedzione, że schematy podpisu cyfrowego satysfakcjonujące (b) istnieją

(chociaż istnienie jest uznawane szeroko za prawdę); jednakże jest kilku dobrych kandydatów. § 1.8.3
wprowadza określoną klasę podpisów cyfrowych, które biorą się z technik szyfrowania kluczem publicznym .
Rozdział11 opisuje liczbę mechanizmów podpisów cyfrowych, które uwiarygodniają te dwie właściwości
omówione powyżej. Chociaż opis podpisów cyfrowych podany w tej sekcji jest trochę ogólny, może być
poszerzony dalej, jak przedstawiono to w § 11.2

1.7 Uwierzytelnianie i identyfikacja

Uwierzytelnianie jest terminem, który jest używany (i często nadużywany) w bardzo szerokim znaczeniu. Sam
ma znaczenie inne niż to, że jest środkiem dostarczającym gwarancję, że jednostki są tymi za które się podają,
lub ,że informacja nie będzie manipulowana przez jednostkę nieautoryzowana. Uwierzytelnienie jest
określonym obiektywem do którego próbujemy się odnosić. Przykładami określonych obiektywów są sterowanie
dostępem, uwierzytelnianie jednostki, uwierzytelnianie wiadomości, integralność danych ,nie zaprzeczalność i
uwierzytelnianie klucza. Te instancje uwierzytelniania są pokazane wreszcie w Rozdziale 9 do 13. Dla potrzeb
tego rozdziału wystarczy podać krótkie wprowadzenie do uwierzytelniania poprzez opis kilku najoczywistszych
aplikacji.

Uwierzytelnianie jest jednym z ważniejszych obiektywów bezpieczeństwa informacji. Aż do połowy

lat 70’tych uważano generalnie, że tajemnica i uwierzytelnianie były nierozłącznie połączone. Wrz z odkryciem
funkcji kodujących ( § 1.9) i podpisów cyfrowych (§1.6) uświadomiono sobie ,że naprawdę tajemnica i
uwierzytelnianie były oddzielnymi i niezależnymi obiektywami bezpieczeństwa informacji. Może na początku
nie wydaje się ważne ich rozdzielenie ale są sytuacje gdzie jest to nie tylko użyteczne ale i wskazane. Na
przykład komunikacja dwuczęściowa pomiędzy Alice i Bobem ma miejsce wtedy kiedy Alice jest w jednym
kraju a Bob w innym, krajowe stacje mogą nie zezwolić na tajemnice na kanale; jeden lub oba kraje mogą
chcieć możliwości monitorowania całej komunikacji. Alice i Bob, jednak, chcieliby zapewnienia identyfikacji
każdy każdego, i integralności i pochodzenia informacji ,które wysyłają i odbierają.
Przedstawiony

scenariusz ilustruje kilka niezależnych aspektów uwierzytelniania. Jeśli Alice i Bob

żądają zapewnienia identyfikacji jeden drugiego, są dwie możliwości do rozważenia:

1. Alice i Bob mogą komunikować się bez znaczących opóźnień czasowych. To znaczy, oboje są aktywni

w komunikacji w „czasie rzeczywistym”

2. Alice lub Bob mogą wymieniać wiadomości z pewnym opóźnieniem. To znaczy, wiadomość może

przechodzić przez różne sieci, przechowalnie i wysyłanie w późniejszym czasie

W pierwszym przypadku Alice i Bob mogą chcieć weryfikować tożsamość w czasie rzeczywistym. Może

to być osiągnięte poprzez wysłanie prze Alice Bobowi wezwania, na które to Bob jako jedyna jednostka może
odpowiedzieć poprawnie . Bob może wykonać podobną akcję dla identyfikacji Alice. Ten typ uwierzytelniania
powszechnie odnosi się do uwierzytelniania jednostki lub po prostu identyfikacji.

W drugim przypadku wezwanie nie jest odpowiednie i oczekiwanie na odpowiedź, a poza tym ścieżka

komunikacyjna może być tylko w jednym kierunku Różne techniki są teraz wymagane dla uwierzytelnienia
autora wiadomości. Ta postać uwierzytelniania jest nazywana uwierzytelnieniem danej początkowej.

1.7.1 Identyfikacja

1.45 Definicja Technika identyfikacji, lub uwierzytelniania jednostki zapewnia jedną część (poprze nabycie
świadectwa potwierdzającego) obu tożsamości od wymaganej drugiej części, a druga byłą aktywna w czasie
tworzenia potwierdzenia lub nabywania

Zazwyczaj jedynie transmisja danych jest konieczna dla identyfikacji części komunikacji. Obie

jednostki są aktywne w procesie komunikacji, dając gwarancję czasowości.

1.46 Przykład (identyfikacja) A wywołuje B przez telefon. Jeśli A i B znają się wzajemnie wtedy
uwierzytelnienie jednostki jest dokonywane poprzez rozpoznanie głosu. Chociaż nie jest to do końca bezpieczne
działa skutecznie w praktyce.
1.47 Przykład (identyfikacja) Osoba A wprowadza do bankomatu swój PIN wraz z kartą magnetyczną
zawierającą informacje o A. Bankomat używa danych zawartych na karcie i PIN’u do weryfikacji tożsamości
użytkownika karty. Jeśli weryfikacja się powiodła, A uzyskuje dostęp do różnych usług oferowanych przez
maszynę.
Przykład 1.46 jest przypadkiem uwierzytelniania wzajemnego podczas gdy Przykład 1.47 dostarcza tylko
uwierzytelniania jednokierunkowego. Mechanizmy numeryczne i protokoły stosowane przy uwierzytelnianiu
wzajemnym i jednokierunkowym są opisane w Rozdziale 10.

1.7.2 Uwierzytelnianie źródła danych

1.48 Definicja Techniki uwierzytelniania źródła danych lub uwierzytelniania wiadomości dostarczają jednej
części, która odbiera wiadomość zapewniając (przez nabycie potwierdzenia) tożsamości części wysyłającej
wiadomość
Często wiadomość jest dostarczana do B wraz z dodatkową informacją tak aby B mógł określić
tożsamość jednostki wysyłającej wiadomość. Ta postać uwierzytelniania nie gwarantuje czasowości, ale jest
użyteczna w sytuacjach gdzie jedna z części nie jest aktywna w komunikacji.

1.49 Przykład (potrzebne przy uwierzytelnianiu źródła danych) A wysyła B wiadomość mailem (e-mail).
Wiadomość może podróżować przez różne sieciowe systemy komunikacyjne i być przechowywana dla B dla
późniejszego odtworzenia. A i B nie są zazwyczaj w stanie komunikacji bezpośredniej. B chciałby jakiś środek
dla weryfikacji, która otrzymana wiadomość została stworzona i wysłana przez A.
Uwierzytelnianie

źródła danych pośrednio dostarcza danych zintegrowanych ponieważ, jeśli wiadomość

była zmodyfikowana podczas transmisji, nie była dziełem autora.

1,8 Kryptografia klucza publicznego.

Koncepcja szyfrowania kluczem publicznym jest prosta i elegancka ale ma daleko idące konsekwencje

1.8.1 Szyfrowanie kluczem publicznym

Niech {E

: e

ε K} będzie zbiorem transformacji szyfrowania a {D

: d

ε K} będzie zbiorem odpowiednich

transformacji deszyfrowania, gdzie K jest przestrzenią klucza. Rozpatrzmy parę powiązanych transformacji
szyfrowania / deszyfrowania (E

, D

) i przypuśćmy, że każda para ma właściwość , że poznanie E

jest

obliczeniowo niewykonalne, dany losowo tekst zaszyfrowany c

ε C znajduje wiadomość m ε M taką , że E

(m)

= c. Właściwość ta sugeruje ,że dane e jest niewykonalne dla określenia odpowiedniego klucza deszyfrującego d
(Oczywiście e i d są po prostu środkiem do opisania funkcji szyfrowani i deszyfrowania, odpowiednio) E

jest ty

przedstawiane jak funkcja jednokierunkowa z zapadką (definicja 1.16) z d będącym konieczną informacją
zapadkową do obliczenia funkcji odwrotnej i w związku z tym pozwala na deszyfrację. Jest to niepodobne do
szyfru klucza symetrycznego gdzie e i d są zasadniczo takie same.

Przy tych założeniach rozważmy dwukierunkową komunikację pomiędzy Alice i Bobem zilustrowaną

na rysunku 1.11. Bob wybiera parę kluczy (e, d). Wysyła klucz szyfrujący e (nazywany kluczem publicznym) do
Alice poprzez kanał ale zachowuje klucz deszyfrujący d (nazywany kluczem prywatnym) bezpieczny i tajny.
Alice może wysłać później wysłać wiadomość m do Boba stosując transformację szyfrowania określoną przez
klucz publiczny Boba pobierając c =E

(m). Bob zdeszyfruje tekst zaszyfrowany c przez zastosowanie odwrotnej

transformacji Dd szczególnie określone przez d

Rysunek 1.11 Szyfrowanie przy użyciu technik klucza publicznego

Zauważ jak rysunek 1.11 różni się od rysunku 1.7 dla szyfru klucza symetrycznego. Tu, klucz szyfrujący jest
przekazywany do Alice kanałem niezabezpieczonym. Ten niezabezpieczony kanał może być tym samym,
kanałem, którym będzie przekazywany tekst zaszyfrowany (ale zobacz § 1.8.2)
Ponieważ klucz szyfrujący e nie musi być utajniony, może być ukazany publicznie. Jednostka może
później wysłać zaszyfrowaną wiadomość do Boba, którą odszyfrować może jedynie Bob. Rysunek 1.12 ilustruje
tą ideę, gdzie A

, A

i A

są różnymi jednostkami. Zauważ, że jeśli A

zniszczy wiadomość m

po zaszyfrowaniu

do c

, wtedy nawet A

nie może odzyskać m

z c

Jako

fizyczną analogię rozważmy metalowe pudełko z wieczkiem zabezpieczonym zamek

kombinacyjny. Kombinacja jest znana tylko Bobowi. Jeśli zamek jest pozostawionym otwartym i uczynionym
publicznie dostępnym wtedy każdy może umieścić informację wewnątrz i zamknąć wieko. Tylko Bob może
odtworzyć wiadomość. Nawet jednostki ,które umieszczają wiadomość wewnątrz nie jest w stanie jej odtworzyć.

Szyfrowanie kluczem publicznym, jak opisano tutaj, zakłada, że znasz klucz publiczny e nie

pozwalającego na obliczenie klucza prywatnego d. Innymi słowy, zakłada istnienie jednokierunkowej funkcji z
zapadką (§ 1.3.1 (iii)).

1.50 Definicja Rozważmy schemat szyfrowani składający się ze zbiorów transformacji szyfrowania i

Rysunek 1.12 Schematyczne użycie szyfrowania kluczem publicznym

i deszyfrowania {E

: e

ε K} i {D

: d

ε K} odpowiednio. Metoda szyfrowania jest schematem szyfrowania

klucza publicznego jeśli dla każdej powiązanej pary szyfrowania/ deszyfrowania (e, d), jeden klucz e (klucz
publiczny) jest uczyniony dostępnym publicznie, podczas gdy drugi d (klucz prywatny) jest zachowany w
tajemnicy. Dla schematu bycia bezpiecznym, musi być obliczeniowo niewykonalne obliczenie d z e
1.51 Uwaga (klucz prywatny kontra klucz tajny) Unikając niejasności powszechną konwencją jest używanie
terminu klucz prywatny w powiązaniu z kryptosystemem klucza publicznego a klucz tajny w powiązaniu z
kryptosystemem klucza symetrycznego. Może to być umotywowane następującym sposobem myślenia:
bierzemy dwie lub więcej osób dzielące tajemnice, ale klucz jest naprawdę prywatny tylko kiedy jedna osoba
sama go zna.

Jest wiele znanych schematów które są szeroko uznawane za bezpieczne metody szyfrowania kluczem

publicznym, ale żadna nie byłą matematycznie udowodniona, że jest bezpieczna niezależnie od założeń
kwalifikujących. Nie jest to podobne do przypadku klucza symetrycznego gdzie jedynie system, który
udowodnił bezpieczeństwo jest szyfrem z kluczem jednorazowym. (§ 1.5.4)

1.8.2 Konieczność uwierzytelniania w systemie klucza publicznego

Przyjmijmy, że kryptografia klucza publicznego jest systemem idealnym, nie wymagającym bezpiecznego
kanału dla przekazania klucza szyfrującego. Implikuje to to, że dwie jednostki mogłyby się komunikować przez
niezabezpieczony kanał bez napotkania wymiany klucza. Niestety nie jest tak. Rysunek 1.13 ilustruje jak
aktywny przeciwnik może zafałszować ten system (deszyfrując wiadomość przeznaczoną dla drugiej jednostki)
bez łamania systemu szyfrowania. Jest to typ podszywania się i jest przykładem uszkodzenia protokołu (zobacz
§ 1.10) W tym scenariuszu przeciwnik podszywa się pod jednostkę B poprzez wysłanie do jednostki A klucza
publicznego e’, który to jednostka A uznaje (niepoprawnie) za klucz publiczny od B. Przeciwnik przechwytuje
zaszyfrowaną wiadomość od A do B, deszyfruje swoim własnym kluczem prywatnym d’, ponownie szyfruje
wiadomość kluczem publicznym B e i wysyła ją do B. Podkreśla to konieczność uwierzytelniania kluczy
publicznych odnosząc się do uwierzytelniania danych źródłowych samych kluczy publicznych. A musi być
przekonany ,że jest szyfrowana przez legalny klucz publiczny od B. Na szczęście, techniki klucza publicznego
również zezwalają na eleganckie rozwiązanie tego problemu (zobacz § 1.11).

Rysunek 1.13:Atak przez podszywanie w dwustronnej komunikacji

1.8.3 Podpisy cyfrowe z odwracalnego szyfrowania kluczem publicznym

Sekcja ta rozważy klasę schematu podpisu cyfrowego, który jest oparty na systemie szyfrowania kluczem
publicznym określonego typu.
Przypuśćmy, że E

jest transformacją szyfrowania kluczem publicznym z przestrzenią wiadomości M i

przestrzenią tekstu zaszyfrowanego C. Przypuśćmy dalej, że M = C. Jeśli D

jest transformacją deszyfrującą

odpowiadającą E

wtedy E

i D

obie są permutacjami

(m)) = E

(m)) = m dla wszystkich m

ε M

Schemat szyfrowania kluczem publicznym tego typu nazywany jest odwracalnym Zauważ, że jest niezbędne
,żeby M = C dla tej poprawnej równości dla wszystkich m

ε M; w przeciwnym razie D

(m) będzie bezsensowny

dla m

∉ C.

Konstrukcja dla schematu podpisu cyfrowego

1.  Niech M będzie przestrzenią wiadomości dla schematu podpisu
2.  Niech C = M będzie przestrzenią podpisu S
3.  Niech (e, d) będzie parą dla schematu szyfrowania kluczem publicznym
4. Definiujemy

funkcję podpisu S

będącą D

d .

To jest, podpis dla wiadomości m

∈ M jest to s = D

(m).

5. Definiujemy

funkcję weryfikacji V

poprzez

true, if E

(s) =m

(m, s)

false,

innym

przypadku

Schemat podpisu może być upraszczany dalej jeśli A tylko podpisuje wiadomość mającą specjalną strukturę a
struktura ta jest publicznie znana. Niech M’ będzie podzbiorem M gdzie element z M’ ma dobrze zdefiniowaną
specjalną strukturę, taką, ze M’ zawiera tylko nieistotny ułamek wiadomości ze zbioru. Na przykład,
przypuśćmy ,że M składa się tylko z binarnych ciągów o długości 2t dla liczb dodatnich całkowitych t. Niech M’
będzie podzbiorem M składającym się z ciągów gdzie pierwsze t bitów replikuje ostatnią pozycję t (np. 10110
będzie w M’ dla t = 3). Jeśli A tylko podpisuje wiadomość wewnątrz podzbioru M’, są one łatwo rozpoznawane
przez weryfikującego.

Przedefiniujemy funkcję weryfikującą V

następująco

true, if E

(s)

∈ M’

(s) =

false,

innym

przypadku

W tym nowym scenariuszu A tylko musi przesłać podpis s ponieważ wiadomość m = E

(s) może być odzyskana

przez wykorzystanie funkcji weryfikującej . Taki schemat jest nazywany schematem podpisu cyfrowego z
odzyskiwaniem wiadomości. Rysunek 1.14 ilustruje jak taka funkcja podpisu jest stosowana Właściwość
wyboru wiadomości ze specjalnej struktury odnosi się do wyboru wiadomości z redundancją.

Rysunek 1.14 Schemat podpisu cyfrowego z odzyskaniem wiadomości

Modyfikacja przedstawiona powyżej jest więcej niż uproszczeniem; jest całkowicie kluczowa jeśli ma się
nadzieję na spotkanie wymaganej właściwości (b) funkcji podpisu i weryfikacji . Zobacz dlaczego jest to ten
przypadek, odnotuj ,że jednostka B może wybrać element losowy s

∈ S jako podpis i stosuje E

do uzyskania u

= E

(s), ponieważ S = M i E

jest publicznie znane. B może potem pobrać tą wiadomość m = u i podpis z m

będącym s i przekazać (m,s). Jest to łatwe do sprawdzenia, ze s będzie zweryfikowane jako podpis stworzony
przez A dla m ale w którym A nie był jednostką. W tym przypadku B ma sfałszowany podpis A. Jest to przykład
nazwany fałszerstwem egzystencjalnym (B stworzył podpis A na wiadomości prawdopodobnie nie wybranej
przez B)
Jeśli M’ zawiera tylko nieistotne części z wiadomość z M, wtedy prawdopodobieństwo ,że jednostka
sfałszuje podpis A w ten sposób jest małe.

1.52 Uwaga (podpis cyfrowy kontra poufność). Chociaż schematy podpisu cyfrowego opierające się na
odwracalnym szyfrowaniu kluczem publicznym są atrakcyjny, wymagają metody szyfrowania jako funkcji
pierwotnej. Są sytuacje gdzie mechanizm podpisu cyfrowego jest wymagany ale szyfrowanie jest zabronione. W
takich przypadkach te schematy podpisu cyfrowego są nieodpowiednie.

Podpisy cyfrowe w praktyce

Dla podpisów cyfrowych używanych w praktyce, konkretna realizacja koncepcji poprzedzającej powinna mieć
pewne dodatkowe właściwości. Podpis cyfrowy musi:

1. być łatwy do obliczenia przez podpisującego (funkcja podpisywania powinna być łatwa do stosowania)
2. być łatwa do weryfikacji (funkcja weryfikacji powinna być łata w stosowaniu)
3. ma

właściwy czas życia tj. być obliczeniowo bezpieczna przed fałszerstwem dopóki podpis nie będzie

dłużej potrzebny dla jego podstawowego celu.

Rozwiązanie sporu

Celem podpisu cyfrowego (lub metody podpisu) jest zezwolenia na rozwiązanie sporu .Na przykład, jednostka A
może w tym miejscu odmówić podpisania wiadomości lub inna jednostka B może nieprawidłowo twierdzić , że
podpis na wiadomości został stworzony przez A. Żeby przezwyciężyć te problemy jest wymagana trzecia
strona godna zaufania (TTP) lub sędzia. TTP musi być jakąś jednostką, na którą wszystkie części wyrażają
zgodę z wyprzedzeniem.
Jeśli A zaprzecza ,że wiadomość m otrzymana przez B została podpisana przez A, wtedy B powinien
przedstawić podpis s

z m TTP wraz z m. TTP potwierdzi B jeśli V

(m ,s

) = true lub potwierdzi A w

przeciwnym wypadku. B zaakceptuje decyzję jeśli B ma zaufanie ,że TTP ma taką samą transformację
weryfikacji V

jak A. A zaakceptuje decyzję jeśli A ma zaufanie ,że TTP stosuje V

i że S

nie będzie narażone.

Dlatego też zadowalające rozwiązanie sporu wymaga poniższych kryteriów.

Wymagania dla rozwiązania sporu podpisów

1. S

i V

mają właściwości (a0 i (b)

2. TTP ma autentyczną kopię V

3. Transformacja podpisu S

przechowywać ma tajemnice i pozostawać bezpieczną

Właściwości te są konieczne ale w praktyce może nie być możliwe ich zagwarantowania. Na przykład,
zakładając , że S

i V

mają różne charakterystyki dane we właściwości 1 mogą okazać się fałszywe dla

określonego schematu podpisu. Inną możliwością jest to ,że A błędnie stwierdzi ,że S

był narażony.

Przezwyciężając ten problem wymaga uzgodnionej metody zatwierdzającej okres czasu dla którego A
zaakceptuje odpowiedzialność za transformację weryfikacji. Analogią tej sytuacji może okazać się
unieważnienie karty kredytowej. Posiadacz karty jest odpowiedzialny posiadacz nie poinformuje
wystawiającego kartę, że została ona zgubiona lub skradziona. § 13.8.2 poddaje głębszej dyskusji te
problemy i możliwe rozwiązania.

1.8.4 Kryptografia klucza symetrycznego kontra klucza publicznego

Schematy szyfrowania kluczem symetrycznym i kluczem publicznym mają różne zalety i wady, ale popularne są
oba. Sekcja ta zaznaczy liczbę tych i podsumuje cechy wskazywane w poprzednich sekcjach.

(i) Zalety kryptografii klucza symetrycznego

1. Szyfry

klucza

symetrycznego mogą być zaprojektowane aby miały wysoki poziom przepustowości.

Niektóre implementacje sprzętowe osiągają stopień szyfrowania stu megabajtów na sekundę, podczas
gdy implementacja programowa może osiągnąć stopień przepustowości w megabajtach na sekundę

2. Klucze dla szyfru klucza symetrycznego są relatywnie krótkie
3. Szyfry klucza symetrycznego mogą być stosowane jako funkcje pierwotne do budowania rożnych

mechanizmów kryptograficznych wliczając w to pseudolosowe generatory liczb (zobacz Rozdział 5),
funkcje szyfrujące (Rozdział 9) i wydajne obliczeniowo schematy podpisów cyfrowych (Rozdział 11).

4. Szyfry

klucza

symetrycznego mogą być elementami tworzącymi silne szyfry. Prosta transformacja,

która jest łatwa do analizy, ale na ich własnej słabości, mogą być użyte do konstrukcji silnego kodu
kaskadowego.

5. Szyfrowanie kluczem symetrycznym jest postrzegane jako mające rozległą historię, chociaż trzeba

przyznać ,że mimo wszystko wcześniej wynaleziono silnik, wiele z wiedzy w tym obszarze
wykorzystano później do wynalezienia komputera cyfrowego i w szczególności, projektu DES
(Standardu Szyfrowania Danych) we wczesnych latach 70’tych.

(ii) Wady kryptografii klucza symetrycznego

1. W dwu częściowej komunikacji, klucz musi pozostać tajny po obu końcach.
2. W

dużej sieci, musi być wiele par kluczy będących zarządzanymi. W rezultacie, efektywne zarządzanie

wymaga użycia bezwarunkowego zaufanego TTP (Definicja 1.65)

dwu

częściowej komunikacji pomiędzy jednostkami A i B dobra kryptograficzna dyktuje, żeby

klucz był zmieniany często, i być może dla każdej sekcji komunikacyjnej.

4. Mechanizm podpisu cyfrowego powstający z szyfrowania kluczem symetrycznym wymaga albo

dużego klucza dla publicznej funkcji weryfikacji lub użycia TTP (Rozdział 11)

(iii) Zalety kryptografii klucza publicznego

1. Tylko klucz prywatny musi być zachowany w tajemnicy (jednak musi być zagwarantowane

uwierzytelnianie kluczy publicznych)

2. Administrowanie

kluczami

w sieci wymaga tylko obecności funkcjonalnego, zaufanego TTP (definicja

1.66) jako przeciwieństwo bezwarunkowego zaufanego TTP. W zależności od użytego trybu, TTP
może być tylko wymagany w sposób „off-line”, jako przeciwieństwo czasu rzeczywistego.

3. W

zależności od trybu zastosowania, para klucz prywatny / klucz publiczny może pozostawać nie

zmieniana prze znaczny okres czasu np. wiele sesji (nawet kilka lat)

4. Wiele schematów klucza publicznego daje względnie wydajny mechanizm podpisu cyfrowego. Klucz

używany do opisu publicznej funkcji weryfikacyjnej jest zazwyczaj dużo mniejszy niż dla
odpowiedniego klucza symetrycznego.

5. W

dużych sieciach, konieczna liczba kluczy może być znacznie mniejsza niż w scenariuszu z kluczem

symetrycznym

(iv) Wady szyfrowania kluczem publicznym

1. Wskaźnik przepustowości dla większości metod szyfrowani kluczem publicznym jest kilka rzędów

wielkości wolniejszy niż najlepszy znany schemat klucza symetrycznego

2. Rozmiary klucza są zazwyczaj dużo większe niż te wymagane dla szyfrowania kluczem symetrycznym

(zobacz Uwaga 1.53) a rozmiar podpisów klucza publicznego jest większy niż te znaczniki
dostarczające uwierzytelnienia danych źródłowych dla technik klucza symetrycznego.

3. Schematy nie publicznego klucza udowodniły swoje bezpieczeństwo (to samo można powiedzieć o

szyfrach blokowych). Większość wydajnych schematów szyfrowania kluczem publicznym znajduje
dane mające swoje bezpieczeństwo oparte na przyjęciu różnych małych zbiorów liczb – problem
teoretyczny.

4. Kryptografia klucza publicznego nie ma bogatej historii jak szyfrowanie kluczem symetrycznym,

zaczyna się w połowie lat 70’ tych.

Podsumowanie porównania

Szyfrowanie kluczem symetryczny i kluczem publicznym ma kilka łącznych zalet. Bieżące systemy
kryptograficzne wykorzystują siłę każdego z nich. Przykładem służyć będą ilustracje
Techniki

szyfrowani

kluczem publicznym mogą być używane do ustalania klucza dla systemu klucza

symetrycznego będącego używanym w komunikacji pomiędzy jednostkami A i B. W tym scenariuszu A i B
mogą wykorzystywać naturę kluczy prywatnego / publicznego schematu klucza publicznego i wydajność
schematu klucza symetrycznego Ponieważ szyfrowanie danych jest częstą i czasochłonną częścią procesu
szyfrowania, schemat klucza publicznego dla ustalania klucza jest małą cząstką całkowitego procesu
szyfrowania pomiędzy A i B.

Obliczeniowo wydajne szyfrowanie kluczem publicznym jest niższa niż od szyfrowania kluczem

symetrycznym. Jednakże, nie ma dowodu ,że to musi być przypadek. Ważnymi punktami w praktyce są:

1. Kryptografia klucza publicznego ułatwia wydajność podpisów (zwłaszcza nie zaprzeczalności) i

zarządzania kluczem

2. Kryptografia klucza symetrycznego jest wydajna dla szyfrowani i pewnej integralności danych aplikacji

1.53 Uwaga (rozmiar klucza: klucz symetryczny kontra klucz publiczny) Klucze prywatne w systemach klucza
publicznego muszą być duże (np. 1024 bitów dla RSA) niż tajny klucz w systemach klucza symetrycznego (np.
64 lub 128 bitów) ponieważ podczas gdy (dla algorytmów bezpieczeństwa) najwydajniejszym atakiem na
systemy klucza symetrycznego jest klucz przeszukiwania wyczerpującego, wszystkie znane systemy klucza są
tematem ataków „skrótem” (np. rozkładu na czynniki pierwsze, bardziej wydajne niż przeszukiwanie
wyczerpujące. A konsekwencji dla równoważnego bezpieczeństwa, klucze symetryczne mają znacznie mniejszą
długość bitów niż te z klucza prywatnego w systemach klucza publicznego) np. współczynnik 10 lub więcej.

1.9 Funkcje rozproszone

Jedną z fundamentalnych funkcji pierwotnych w nowoczesnej kryptografii jest kryptograficzna funkcja
rozproszona, często nieoficjalnie nazywana jednokierunkową funkcją rozproszoną. Uprościmy definicję dla
potrzeb naszego omówienia

1.54 Definicja Funkcja rozproszona jest obliczeniowo wydajną funkcją odwzorowującą ciągi binarne o
przypadkowej długości do binarnego ciągu o pewnej stałej długości, nazywanej wartością klucza haszującego
(mieszającego) .

Dla funkcji rozproszonej z wyjściowymi n –bitową wartością haszująca (np. n = 128 lub 160) i ma

wskazane właściwości, prawdopodobieństwo, że losowo wybrany ciąg odwzoruje do określonej n –bitowej
wartości haszującej (obraz) to 2

-n

. Podstawowy pomysł jest taki ,że wartość haszująca służy jako zwarty

przedstawiciel ciągu wejściowego. W zastosowaniu kryptograficznym, funkcja rozproszona h jest zazwyczaj tak
wybrana, że jest obliczeniowo niewykonalnym znaleźć dwie odrębne dane wejściowe , które mieszają się we
wspólną wartość (tj. dwie zderzające się dane wejściowe x i y takie ,że h(x0 = h(y)), i przy danej, określonej
wartości haszująca y jest obliczeniowo niewykonalne znalezienie (przeciw obrazu) x takiego ,że h(x) = y.
Większość popularnych kryptografii używa funkcji rozproszonych przy podpisach cyfrowych i
integralności danych, Przy podpisach cyfrowych długa wiadomość jest zazwyczaj haszowana (używając
publicznie dostępnej funkcji rozproszonej) i tylko wartość haszująca jest podpisana Jednostka odbierająca
wiadomość haszuje potem odebraną wiadomość i weryfikuje czy ten podpis odebrany jest poprawny z tą
wartością haszującą. Ta zachowuje obie, czas i miejsce porównując bezpośrednio podpisaną wiadomość, która
zazwyczaj wymaga podzielenia wiadomości na właściwych rozmiarów bloki i podpisuje każdy blok
indywidualnie. Odnotujmy tu, że niemożliwe jest znalezienie dwóch wiadomości z taką samą wartością
haszującą , jest to wymóg bezpieczeństwa, ponieważ w innym przypadku podpisy na wiadomości wartości
haszujacej byłyby takie same jak na innej, pozwalając podpisującemu podpisać jedną wiadomość a później
utrzymywać podpis na innych.

Funkcje rozproszone mogą być używane również przy integralności danych. Wartość haszująca

odpowiadająca określonej danej wejściowej jest obliczana we właściwym momencie. Integralność takiej
wartości haszujacej jest chroniona w ten sam sposób. Później, weryfikując tą daną wejściową nie może być
zmieniana, wartość haszująca jest ponownie obliczana przy zastosowaniu danej wejściowej ręcznie, i
porównywana z oryginalną wartością haszująca . Określone aplikacje zawierają ochronę antywirusową i
dystrybucje oprogramowania.

Trzecim zastosowaniem funkcji rozproszonych jest ich użycie w protokołach wymagających

wcześniejszego zatwierdzenia, wliczając w to pewne schematy podpisów cyfrowych i protokołów identyfikacji
(Rozdział 10)

Funkcje rozproszone omawiane powyżej są zazwyczaj publicznie znane i nie wymagają żadnych

tajnych kluczy. Kiedy używamy ich do wykrycia czy wiadomość wejściowa została zmieniona, są nazywane
znacznikami integralności (MDC). Odnosimy się do nich jako funkcji rozproszonych które wymagają tajnego
klucza i dostarczają uwierzytelnienia danych źródłowych (§ 9.76) również jako integralności danych; są one
nazywane kodami uwierzytelniającymi wiadomość (MAC).

1.10 Protokoły i mechanizmy

1.55 Definicja Protokół kryptograficzny (protokół) jest rozproszonym algorytmem zdefiniowanym poprzez
sekwencję kroków dokładnie określających wymagane działanie dwóch lub więcej jednostek stosujących
określony obiektyw   bezpieczeństwa.
1.56 Uwaga (protokoły kontra mechanizmy) jako przeciwieństwo protokołu, mechanizm jest bardziej ogólnym
terminem obejmującym protokoły, algorytmy (określone kroki po których porusza się pojedyncza jednostka) i
techniki nie kryptograficzne (np. ochrona sprzętowa i sterownie proceduralne) osiągające określone obiektywy
bezpieczeństwa.
Protokoły odgrywają  główną rolę w kryptografii i są niezbędne w wykonywaniu celów kryptografii
jakie omówiono w § 1.2. Schematy szyfrowania, podpisy cyfrowe, funkcje rozproszone i generatory liczb
losowych są wśród funkcji pierwotnych które mogą być wykorzystane do budowy protokołu.
1.57 Przykład (prosty protokół uzgadniania klucza) Alice i Bob wybrali schemat szyfrowani kluczem
symetrycznym do stosowania w komunikacji kanałem niezabezpieczonym. Szyfrowanie informacji wymaga
klucza. Protokół komunikacji jest następujący:

1.  Bob buduje schemat szyfrowania kluczem publicznym i wysyła klucz publiczny do Alice kanałem.
2.  Alice generuje klucz dla schematu szyfrowania kluczem symetrycznym
3.  Alice szyfruje klucz używając klucz publiczny Boba i wysyła zaszyfrowany klucz do Boba
4.  Bob odszyfrowywuje go używając klucza prywatnego i odtwarza (tajny) klucz symetryczny

5. Alice i Bob zaczynają komunikację prywatną poprzez użycie systemu klucza symetrycznego i

wspólnego tajnego klucza

Taki protokół  używa funkcji podstawowych próbujących zrealizować prywatną komunikację
niezabezpieczonym kanałem.  Podstawowe funkcje pierwotne są schematami szyfrowania kluczem
symetrycznym i kluczem publicznym. Protokół ma niedoskonałości obejmujące atak podszywania z § 1.8.2 ,ale
pokazuje ideę protokołu.
Często rolą szyfrowania kluczem publicznym w prywatnej komunikacji jest dokładne wskazywanie
poprzez protokół – szyfrowanie kluczem publicznym jest używane jako środek do wymiany kluczy do
późniejszego użycia w szyfrowaniu kluczem symetrycznym, motywowane przez różnice wydajności pomiędzy
szyfrowaniem kluczem symetrycznym a kluczem publicznym.

Niedomagania protokołu i mechanizmu

1.58 Definicja Niepowodzenie protokołu lub niepowodzenie mechanizmu kiedy mechanizm nie spełnił swojego
zdania do którego były przeznaczone, w sposób dzięki któremu przeciwnik nie zyskuje przewagi poprze
łamanie prymitywów takich jak bezpośredni algorytm szyfrowania, ale przez manipulowanie samym
protokołem lub mechanizmem
1.59 Przykład (niedomagania mechanizmu) Alice i Bob komunikują się przy użyciu szyfru strumieniowego.
Wiadomości , które oni szyfrują  są znane jako mające specjalną postać: pierwsze dwadzieścia bitów niesie
informację która przedstawia wartość pieniężną. Aktywny przeciwnik może po prostu zXORować właściwy
ciąg bitów pierwszych dwudziestu bitów tekstu zaszyfrowanego i zmienić wartość. Podczas gdy przeciwnik nie
może odczytać stosownej wiadomości, może zmienić transmisję. Szyfrowanie nie będzie narażone na szwank ale
protokół zakończy się niepowodzeniem wykonując się  właściwie.; założenie ,że szyfrowanie dostarcza
integralności jest niepoprawna.
1.60 Przykład  (atak przedniego przeszukiwania) Przypuśćmy ,że w transakcji bankowości elektronicznej 32
bitowe pole z rekordami, wartość transakcji jest szyfrowana przy użyciu schematu klucza publicznego. Ten
prosty protokół jest zaplanowany do dostarczania prywatnej  wartości pola – ale czy tak? Przeciwnik może łatwo
pobrać wszystkie 2

możliwych wejść, które mogą być tekstem jawnym w tym polu i zaszyfrować je przy

użyciu publicznej funkcji szyfrującej (Pamiętaj, że z natury rzeczy szyfrowanie kluczem publicznym tej funkcji
musi być dostępne przeciwnikowi) Poprzez porównanie każdego z 2

tekstów zaszyfrowanych z tym , który

jest aktualnie szyfrowany w transakcji, przeciwnik może określić tekst jawny. Tutaj funkcja szyfrowania
kluczem publicznym nie jest narażona, ale raczej sposób jej użycia. Dokładnie powiązany atak, który stosuje się
bezpośrednio do uwierzytelniania dla celów sterowania dostępem jest atakiem słownikowym (zobacz § 10.2.2)
1.61 Uwaga (powody niedomagań protokołów) Protokoły i mechanizmy mogą być niezgodne z kilku powodów:

1. słabości w określonych kryptograficznych funkcjach pierwotnych , które mogą być wzmocnione przez

protokół lub mechanizm;

2. żądanie lub założenie gwarancji bezpieczeństwa, które są wyolbrzymiane lub nie do końca zrozumiałe
3. niedopatrzenie podstawowych zasad szerokiej klasy funkcji pierwotnych takich jak szyfrowanie

Przykład 1.59 ilustruje pozycję 2 jeśli szyfr strumieniowy jest szyfrem z kluczem jednorazowym, i również
pozycję 1
Przykład 1.60 ilustruje pozycję 3

1.62 Uwaga (projekt protokołu) Kiedy projektujemy protokoły kryptograficzne i mechanizmy , wykonujemy to
w dwóch krokach:

1. Identyfikujemy wszystkie założenia w projekcie protokołu lub mechanizmu
2. Dla

każdego założenia, określamy wpływ na obiektyw bezpieczeństwa jeśli to założenie jest zakłócone

1.11 Ustalanie klucza, zarządzanie i poświadczanie

Sekcja ta daje krótkie wprowadzenie do metodologii zapewniającej bezpieczną dystrybucję kluczy dla celów
kryptograficznych
1.63 Definicja Ustalanie klucza jest procesem dzięki któremu dzielimy tajny klucz stający się dostępnym
pomiędzy dwie lub więcej jednostek, dla późniejszego kryptograficznego zastosowania

1.64 Definicja Zarządzanie kluczem jest zbirem procesów i mechanizmów, które wspierają ustalanie klucza i
utrzymania trwających kluczowych związków pomiędzy jednostkami , obejmujące wymianę starszych kluczy
na nowsze jeśli to konieczne

Ustalanie klucza może być dalej podzielone na uzgadnianie klucza i przekazanie klucza. Wiele różnych

protokołów można zaproponować jako dostarczyciela ustalania klucza. Rozdział 12 opisuje kilka z ich
szczegółowo. Na potrzeby tego rozdziału przedstawimy tylko krótko kwestie odnoszące się do ustalania klucza.
Prostą architekturę opartą na krytptografi klucza symetrycznego i publicznego wraz z koncepcją poświadczania.
Jak

odnotowałeś w § 1.5, główną istotą kiedy używamy technik klucza symetrycznego jest ustalenie

pary tajnych kluczy. Staje się to bardziej widoczne kiedy rozpatrzymy jednostki w sieci, dwóch, które mogą
życzyć sobie komunikacji. Rysunek 1.15 ilustruje sieć składającą się z 6 jednostek. Strzałki wskazują 15
możliwych dwukierunkowych komunikacji , które mogą mieć miejsce. Ponieważ każda para jednostek życzy
sobie komunikacji, ta małą sieć wymaga bezpiecznej wymiany (

) = 15 par kluczy. W sieci z n jednostkami

liczba bezpiecznych wymian kluczy to (

) =

n(n-1)

Rysunek 1.15: Kluczowe związki w prostej 6 jednostkowej sieci

Diagram sieci przedstawiony na rysunku 1.15 jest po prostu połączeniem 15 dwu kierunkowych

komunikacji jakie przedstawiono na rysunku 1.7. W praktyce, sieci są bardzo duże i problem ustalanie klucza
jest krytycznym tematem. Jest kilka sposobów obsługi tego problemu Dwie najprostsze będą omówione; jedna
oparta o techniki klucza symetrycznego a druga o techniki klucza publicznego

1.11.1 Zarządzanie kluczem technikami klucza symetrycznego

Jednym z rozwiązań jakie stosują techniki klucza symetrycznego wymagają jednostki w sieci, która jest zaufaną
dla wszystkich jednostek.. Jak w § 1.8.3, do jednostki tej odnosimy się jako trzeciej strony godnej zaufania
(TTP). Każda jednostka A

dzieląca wyraźnie klucz symetryczny k

z TTP Klucze te z założenia będą

przekazywane przez kanał bezpieczny. Jeśli dwie jednostki później zażyczą sobie komunikacji , TTP wygeneruje
klucz k (czasami nazywanym kluczem sesyjnym) i wyśle go do zaszyfrowania przez każdy stały klucz jak
przedstawiono na Rysunku 1.16 dla jednostek A

i A

Rysunek 1.16: Zastosowanie zarządzania kluczem przez TTP

Do zalet takiego podejścia zaliczamy:

1. Łatwo jest dodawać i usuwać jednostki z sieci.
2. Każda jednostka musi przechowywać tylko jeden długoterminowy tajny klucz

Wady:

1. Całą komunikacja wymaga interakcji inicjalizującej przez TTP
2. TTP musi przechowywać n długoterminowych tajnych kluczy
3. TTP ma możliwość czytania wszystkich wiadomości
4. Jeśli TTP jest narażony, cała komunikacja jest nie zabezpieczona

1.11.2 Zarządzanie kluczem technikami klucza publicznego

Jest kilka sposobów adresowania zarządzania kluczem technikami klucza publicznego. Rozdział 13 opisuje
wiele z tych szczegółów. Dla celów tego rozdziału jest rozważany bardzo prosty model.
Każda jednostka w sieci ma parę szyfrujących kluczy prywatny / publiczny. Klucz publiczny wraz z
tożsamością jednostki jest przechowywany w centralnej składnicy nazywanej plikiem ogólnie dostępnym. Jeśli
jednostka A

życzy sobie wysłać zaszyfrowaną wiadomość do jednostki A

, A

wyszukuje klucz publiczny e

z pliku ogólnie dostępnego, szyfruje wiadomość używając tego klucza i wysyła tekst zaszyfrowany do A

Rysunek 1.17 przedstawia taką sieć

Rysunek 1.17; Zarządzanie kluczem przy użyciu technik klucza publicznego

Zalety takiego podejścia:

1.  Nie jest wymagany żaden TTP
2.  Plik publicznie dostępny może rezydować u każdej jednostki
3.  Tylko n kluczy publicznych musi być przechowywanych pozwalając na bezpieczną komunikację

pomiędzy każdą parą jednostek, zakładając atak tylko przez przeciwnika pasywnego

Problem zarządzania kluczem staje się trudniejszy kiedy musimy brać pod uwagę przeciwnika który jest
aktywny (tj. przeciwnik który może zmieniać plik ogólnie dostępny zawierający klucze publiczne) Rysunek
1.18 ilustruje jak aktywny przeciwnik może narazić powyższy dany schemat zarządzania kluczem. (Jest to
bezpośrednia analogia do ataku w § 1.8.2). Na rysunku, przeciwnik zmienia plik ogólnie dostępny przez

podmianę klucza e

jednostki A

przez klucz publiczny przeciwnika e*. Każda wiadomość szyfrowana dla A

używa klucza publicznego z pliku ogólnie dostępnego, który może być deszyfrowany tylko przez przeciwnika.
Mając odszyfrowaną i odczytaną wiadomość przeciwnik może ją teraz zaszyfrować używając klucza
publicznego A

i ponownie wysłać tekst zaszyfrowany. A

jednak wierzy , że tylko A

zdeszyfrował tekst

zaszyfrowany c.

Rysunek 1.18 Podszywanie się pod A6 przez aktywnego przeciwnika z kluczem publicznym e*

Chroniąc się przed tego typu atakiem, jednostka może użyć TTP do poświadczenia klucza publicznego
każdej jednostki. TTP ma prywatny algorytm S

i algorytm weryfikacji V

(zobacz § 1.6) zakładając ich

znajomość przez każdą jednostkę. TTP ostrożnie weryfikuje tożsamość każdej jednostki i podpisaną wiadomość
składające się na identyfikator i uwierzytelniony klucz publiczny jednostki. Jest to prosty przykład
poświadczenia, wiążąc tożsamość jednostki z jej kluczem publicznym (zobacz § 1.11.3) Rysunek 1.19 ilustruje
sieć przy tych warunkach. A

użyje klucza publicznego A

tylko jeśli poświadczony podpis zweryfikuje

pomyślnie.

Rysunek 1.19 Uwierzytelnianie klucza publicznego przez TTP || oznacza połączenie

Zalety użycia TTP do opieki nad integralnością pliku ogólnego dostępu:

1. Zapobiega aktywnemu przeciwnikowi podszywanie się w sieci
2. TTP nie może monitorować komunikacji . jednostki muszą ufać TTP tylko wiążąc poprawnie

tożsamości z kluczami publicznymi

3. Interakcja pre – komunikacji z plikiem ogólnie dostępnym może być wyeliminowana jeśli jednostki

przechowują poświadczenia lokalnie

Nawet z TTP pozostają pewne obawy:

1. Jeśli podpisany klucz przez TTP jest narażony, cała komunikacja staje się nie zabezpieczona
2. Całe zaufanie jest położone w jednej jednostce

1.11.3 Trzecia strona godna zaufania i poświadczenia klucza publicznego

Trzecią stronę godną zaufania wspomniano w § 1.8.3 i ponownie tutaj w § 1.11. Zaufanie położone w tej
jednostce mienia się w zależności od sposobu jak jest używana, a zatem powoduje następująca klasyfikację

1.65 Definicja TTP jest obdarzonym bezwarunkowym zaufaniem jeśli jest zaufany we wszystkich sprawach. Na
przykład może mieć dostęp do tajnych i prywatnych kluczy użytkowników, jak również pobierać z
powiązanych kluczy publicznych identyfikatory.
1.66 Definicja TTP jest obdarzony zaufaniem funkcjonalnym jeśli jednostka jest z założenia uczciwa i fair ale
nie ma dostępu do tajnych i prywatnych kluczy użytkowników

§ 1.11.1 dostarcza scenariusza który stosuje zaufanie bezwarunkowe dla TTP. § 1.11.2 używa zaufania
funkcjonalnego do TTP opiekującego się integralnością pliku ogólnie dostępnego. Zaufany funkcjonalnie TTP
może być użyty do rejestracji lub poświadczenia użytkowników i zawartości dokumentów lub jak w § 1.8.3, jako
sędzia.

Poświadczenia klucza publicznego

Przekazywani kluczy publicznych jest generalnie łatwiejsze niż kluczy symetrycznych ,ponieważ nie jest
wymagana tajemnica. Jednakże, integralność (uwierzytelnienie) kluczy publicznych jest krytyczne (§ 1.8.2)
Poświadczenie klucza publicznego skalda się z części danych i części podpisu . Cześć danych składa
się z nazwy jednostki, odpowiadającego jej klucza publicznego, możliwych dodatkowych istotnych informacji
(np. ulica jednostki lub adres sieciowy, poprawny okres dla publicznego klucza i różne inne atrybuty). Część
podpisu składa się z podpisu TTP pod częścią danych.

Aby jednostka B zweryfikowała autentyczność klucza publicznego jednostki A, B musi mieć

zweryfikowaną kopię publicznie podpisanej funkcji weryfikującej od TTP. Dla uproszczenia załóżmy, że
uwierzytelniona funkcja weryfikująca jest dostarczona B w sposób nie kryptograficzny, na przykład B dostał ją
osobiście od TTP. B może potem wykonać następujące kroki:

1. nabyć poświadczenie klucza publicznego A przez jakiś niezabezpieczony kanał, albo z centralnej bazy

danych poświadczeń albo bezpośrednio od A lub inaczej

2. Użyć funkcji weryfikacyjnej TTP do zweryfikowania podpisu TTP na poświadczeniu A
3. Jeśli weryfikacja podpisu jest poprawna, akceptuje klucz publiczny w poświadczeniu jako

uwierzytelnienie klucza publicznego A; w przeciwnym razie, zakłada ,że klucz jest niepoprawny

Przed stworzeniem poświadczenia klucza publicznego dla A, TTP musi stosownie zmierzyć weryfikację
tożsamości A i fakt, że klucz publiczny będący poświadczanym w rzeczywistości należy do A. Metoda wymaga,
żeby A pojawił się przed TTP z konwencjonalnym kluczem jako dowodem tożsamości, i uzyskać klucz
publiczny A od A osobiście wraz z dowodem, że A zna odpowiedni klucz prywatny. Ponieważ TTP tworzy
poświadczenia dla części, zaufanie, które wszystkie jednostki mają dla uwierzytelnionego klucza publicznego
TTP ,może być użyte do przejścia w zaufanie w uwierzytelnioną tą część klucza publicznego, która nabywa i
weryfikuje poświadczenie

1.12 Liczby pseudo losowe i sekwencje

Generacja liczb pseudolosowych jest ważną funkcją pierwotną w wielu mechanizmach kryptograficznych. Na
przykład, klucze dla transformacji szyfrowania muszą być wygenerowane w sposób, który jest

nieprzewidywalny dla przeciwnika. Generowanie klucza losowego zazwyczaj wymaga wyboru liczb losowych
lub sekwencji bitów. Generowanie liczb losowych jest obecnym tematem.
Krótkie wprowadzenie jest tu, szczegóły w Rozdziale 5
Często w aplikacjach kryptograficznych, musi być wykonany jeden z następujących kroków:

(i) Ze

skończonego zbioru n elementów(np. {1,2,3..., n} wybieramy losowo element)

(ii)

E zbioru wszystkich sekwencji (ciągów) o długości m przy skończonym alfabecie A z n
symbolami wybieramy losową sekwencję.

(iii) Generujemy

losową sekwencję (ciąg) symboli o długości m ze zbioru n symboli

Nie jest jasne co dokładnie oznacza wybór losowy czy generacja losowa. Wywołanie liczby losowej bez
kontekstu powoduje sensowność. Czy liczba 23 jest liczbą losową? Nie ale jeśli 49 identycznych kul opisanych
od 1 do 49 jest w pojemniku, i zamieszamy tym kontenerem, potem wyjmiemy kulkę, a ta kulka szczęśliwie
będzie opisana numerem 23, wtedy można powiedzieć ,że 23 zostało wygenerowane losowo z jednolitego
rozdziału. Prawdopodobieństwo ,że 23 zostanie wyciągnięte jest jak 1 do 49 lub 1/49.

Jeśli liczba na kulce, która została wyciągnięta z pojemnika jest zapisywana a piłka wraca z powrotem
do pojemnika i proces jest powtarzany 6 razy, wtedy będzie generowana losowa sekwencja o długości 6
definiująca alfabet A ={1,2,...,49}. Jaka jest szansa ,że wystąpi sekwencja 17, 45, 1, 7, 23 ,35? Ponieważ każdy
element w tej sekwencji ma prawdopodobieństwo 1/49, prawdopodobieństwo wystąpienia sekwencji 17, 45, 1
,7 23 ,35 to

1/49 x 1/49 x 1/49x 1/49 x 1/49x 1/49 = 1/13841287201

Jest dokładnie 13841287201 sekwencji o długości 6 w alfabecie A. Jeśli każda z tych sekwencji jest zapisana na
jednej z 13841287201 kulek i są one umieszczone w pojemniku (najpierw usuwamy 49 kulek oryginalnych)
wtedy szansa, że podana sekwencja zostanie wylosowana jest taka sama jak gdybyśmy generowali jedną piłkę na
raz. A zatem (ii) i (iii) są zasadniczo takimi samymi instrukcjami. Znalezienie dobrej metody generowania
losowych sekwencji jest trudne

1.67 Przykład (generator losowych sekwencji) Generując losową sekwencję z ‘0’ i ‘1’, rzucamy monetą, i jeśli
wypadnie reszka zapisujemy ‘1’ a jeśli orzeł ‘0’. Jest to założenie w którym moneta jest bezstronna, co oznacza
,ze prawdopodobieństwo 1 to ½. Zależy to od tego jak dobrze jest zrobiona moneta i jak jest wykonywane
podrzucanie. Metoda ta może być wartościowa w systemie gdzie sekwencje losowe muszą być generowane
szybko i często. Nie ma praktycznej wartości innej niż służyć za przykład idei generowani liczb losowych.
1.68 Przykład (generator sekwencji losowych) Dioda może być użyta do tworzenia losowych binarnych
sekwencji. Jest to rozsądne jeśli mamy sposób na przekonane ,że 1 będzie stworzone przy danej próbie to 1/3. To
założenie powinno być fałszywe, generowane sekwencja nie powinna być wybierana z jednolitych dystrybucji i
nie wszystkie sekwencje o danej długości będą jednakowo równe Jedyny sposób zapewnienia niezawodności
tego typu źródła losowości jest wykonanie testów statystycznych na ich zakończenie. Są one rozpatrywane
Rozdziale 5. Jeśli dioda jest źródłem jednolitej dystrybucji w zbiorze wszystkich binarnych sekwencji o danej
długości, dostarcza ona efektywnego sposobu generowani sekwencji losowych

Ponieważ większość prawdziwych źródeł (jeśli jest taka rzecz) pochodzi ze środków fizycznych, mają
w zwyczaju być albo kosztowne albo wolne przy generowaniu. Przezwyciężając te problemy, metody obmyśliły
konstrukcję pseudolosowej sekwencji w sposób deterministyczny z krótkiej losowej sekwencji nazywanej
ziarnem Sekwencje pseudolosowe pojawiają się by wygenerować prawdziwe źródło losowe dla każdego
znającego metody generacji. Często algorytm generowania jest znany wszystkim, ale ziarno jest nieznane z
wyjątkiem jednostki generującej sekwencje. Zaprojektowano mrowie algorytmów dla generowania
pseudolosowych sekwencji bitowych różnych typów. Wiele z nich okazało się nieodpowiednich dla celów
krytptografi a inne musiały być ostrożnie stosowane przez tworzących takie algorytmy z natury rzeczy danych
wyjściowych.

1.13 Klasy ataków i modele bezpieczeństwa

Przed laty zidentyfikowano wiele różnych typów ataków na funkcje pierwotne kryptografii i protokoły.
Omawiamy tu ograniczone czynniki ataków na szyfrowanie i protokoły. Ataki na inne funkcje pierwotne
kryptografii będą podane we właściwych rozdziałach. W § 1.11 byłą omówiona rola aktywnego i pasywnego
przeciwnika. Ataki tych przeciwników mogą zaklasyfikowane jak następuje:

1. Atak pasywny jest atakiem gdzie przeciwnik tylko monitoruje kanał komunikacyjny .Pasywny

przeciwnik tylko zagraża poufności danych.

2. Atak aktywny jest atakiem gdzie przeciwnik próbuje usunąć, dodać lub w jakiś inny sposób zmienić

transmisję w kanale. Aktywny atakujący zagraża integralności danych i uwierzytelnianiu jak również
poufności.

Atak pasywny może być dalej podzielony na bardziej specjalizowane ataki dla wydedukowania tekstu jawnego z
tekstu zaszyfrowanego, jak pokazano w § 1.13.1

1.13.1 Ataki na schematy szyfrowania

Obiektywem tych ataków jest systematycznie odzyskiwanie tekstu jawnego z tekstu zaszyfrowanego lub nawet
drastyczniej, wywnioskowanie klucza deszyfrującego.

1. Atak zaszyfrowanym tekstem jest atakiem gzie przeciwnik (lub kryptoanalityk) próbuje wywnioskować

klucz deszyfrujący lub tekst jawny tylko przez obserwowanie tekstu zaszyfrowanego. Schemat
szyfrowania trudny do obrony przed takim typem obrony jest uważany za niepewny.

2. Atak tekstem jawnym jest atakiem gdzie przeciwnik ma wielkość tekstu jawnego i odpowiadający mu

tekst zaszyfrowany. Ten typ ataku jest zazwyczaj tylko nieznacznie trudniejszy do przeprowadzenia.

3. Atak za pomocą wybranego tekstu jawnego jest atakiem gdzie przeciwnik wybiera tekst jawny a potem

dodaje odpowiedni tekst zaszyfrowany. Później, przeciwnik używa informacji wywnioskowanej aby
odtworzyć tekst jawny odpowiadający wcześniej niewidocznemu tekstowi zaszyfrowanemu.

4. Atak adaptacyjny wybranym tekstem jawnym jest atakiem wybranym tekstem jawnym w którym

wybrany tekst jawny może zależeć od tekstu zaszyfrowanego odebranego z poprzedniej prośby.

5. Atak za pomocą wybranego tekstu zaszyfrowanego jest atakiem gdzie przeciwnik wybiera tekst

zaszyfrowany i dany odpowiadający mu tekst jawny Jedyny sposób przeprowadzenia takiego ataku
przez przeciwnika to uzyskać dostęp do środowiska używanego do deszyfrowania (ale nie klucza
deszyfrującego, który może być bezpiecznie osadzony w środowisku) Obiektywem jest wtedy możność,
bez dostępu do takiego środowiska, wywnioskowania tekstu jawnego z (różnego) tekstu
zaszyfrowanego.

6. Atak adaptacyjny za pomocą wybranego tekstu zaszyfrowanego jest atakiem za pomocą wybranego

tekstu zaszyfrowanego gdzie wybór tekstu zaszyfrowanego może zależeć od tekstu jawnego
odebranego z poprzednie prośby.

Większość z tych ataków również stosuje kody schematy podpisu cyfrowego i uwierzytelniania wiadomości. W
tym przypadku, obiektywem atakującego jest sfałszowanie wiadomości lun MCS’ów, co będzie omawiane w
Rozdziale 11 i 9, odpowiednio.

1.13.2 Ataki na protokoły

Poniżej jest częściowa lista ataków, które mogą być przeprowadzone na różnych protokołach.

1. Atak znanym kluczem. W tym ataku przeciwnik uzyskuje jakieś klucze używane poprzednio a potem

używa tych informacji do określenia nowego klucza.

2. Atak metoda powtórzenia. W ataku tym przeciwnik nagrywa sesję komunikacyjną i odtwarza sesję

jednostki lub jej część, w późniejszym czasie

3. Atak za pomocą podszywania. Tutaj przeciwnik zakłada tożsamość jednej z poprawnych jednostek w

sieci.

4. Atak słownikowy. Jest to zazwyczaj atak na hasła Typowo, hasło jest przechowywane w pliku

komputera jako obraz niekluczowej funkcji rozproszonej. Kiedy użytkownik loguje się i wprowadza
hasło, jest haszowane a obraz jest porównywany z przechowywaną wartością. Przeciwnik może pobrać
listę prawdopodobnych haseł, haszuje wszystkie wejścia w tej liście a potem porównuje to do
prawdziwej listy zaszyfrowanych haseł z nadzieją że znajdzie wzorzec.

5. Przeszukiwanie w przód. Atak ten jest podobny w duchu do ataku słownikowego i jest używany do

deszyfrowania wiadomości. Przykład tej metody był wymieniony w Przykładzie 1.60

6. Atak przelotowy. Ten typ ataku zazwyczaj wymaga pewnej formy podszycia w protokole

uwierzytelniania (zobacz § 12.9.1)

1.13.3 Modele dla oceny bezpieczeństwa

Bezpieczeństwo funkcji pierwotnych kryptografii i protokołów może być obliczone dla kilku różnych modeli.
Najpraktyczniejszym miernikiem bezpieczeństwa są metodologie obliczeniowe, możliwe do udowodnienia i
improwizowane .,chociaż to ostatnie jest często niebezpieczne. Poziom zaufania w ilości bezpieczeństwa
dostarczonym przez funkcje pierwotne lub protokoły oparte są obliczeniowych lub improwizowanych
zwiększeniach bezpieczeństwa z czasem i dochodzeniu schematu. Jednakże czasu nie jest dość jeśli kilku ludzi
dostał metody ostrożnej analizy
(i) Bezpieczeństwo bezwarunkowe
Większość surowych pomiarów jest informacji – mierzoną teoretycznie – czy lub nie system ma bezwarunkowe
bezpieczeństwo. Przeciwnik zakłada ,że ma nieograniczone obliczeniowe zasoby, a pytanie jest czy lub nie jest
dosyć informacji dostępnych dla oszukania systemu. Bezpieczeństwo bezwarunkowe dla systemów szyfrowania
jest nazywane poufnością doskonałą. Dla poufności doskonałej, niepewność w tekście jawnym, po obserwacji
tekstu zaszyfrowanego musi być równa wcześniejszej niepewności w tekście jawnym – obserwacja tekstu
zaszyfrowanego nie dostarcza jakichkolwiek informacji przeciwnikowi.

Koniecznym warunkiem dla schematu szyfrowania dla bycia bezpiecznym bezwarunkowo jest to ,żeby

klucz był przynajmniej tak długi jak wiadomość. Szyfr z kluczem jednorazowym (§ 1.5.4) jest przykładem
algorytmu szyfrowania bezpieczeństwa bezwarunkowego. Generalnie, schematy szyfrowania nie oferują
poufności doskonałej, a każdy tekst zaszyfrowany obserwowany zmniejsza teoretyczną niepewność w tekście
jawnym i kluczu szyfrującym. Schematy szyfrowani kluczem publicznym będą bezpieczne bezwarunkowo
ponieważ przy danym tekście zaszyfrowanym c, tekst jawny może zasadniczo być odtworzony poprzez
zaszyfrowanie wszystkich możliwych tekstów jawnych dopóki nie uzyskamy c.
(ii) Bezpieczeństwo teoretycznie złożone
Właściwy model obliczeniowy jest zdefiniowany a przeciwnicy mają modele silne obliczeniowo
wielomianowo.(Przeprowadzają ataki wymagające czasu i przestrzeni wielomianowej w rozmiarze właściwych
parametrów bezpieczeństwa ) . wtedy jest konstruowany dowód bezpieczeństwa w stosunku do modelu.
Obiektyw projektuje metodę kryptograficzną w oparciu o słabość założeń możliwych przewidywań siły
przeciwnika. Analiza asymptotyczna i zazwyczaj gorszy przypadek analizy i musi być ostrożnie wykorzystana
do określenia kiedy dowody mają praktyczne znaczenie. W przeciwieństwie ataki wielomianowe które są
wykonalne pod modelem mogą , w praktyce być jeszcze obliczeniowo niewykonalne.
Analiza

bezpieczeństwa tego typu, chociaż nie ma praktycznej wartości w wielu wypadkach, może

pomimo to utorować drogę lepszemu zrozumieniu bezpieczeństwa. Analiza teoretycznej złożoności jest
nieoceniona przy formułowaniu fundamentalnych zasad i potwierdzenia intuicji. Jest to jak wiele innych nauk,
których praktyczne techniki są odkrywane wcześniej w rozwoju, przed teoretycznymi podstawami i
zrozumieniem ich osiągnięć.
(iii) Udowadnialnie bezpieczny
Metoda kryptograficzna można by powiedzieć jest udowadnialnie bezpieczna jeśli trudność w jej pokonaniu
może być pokazana jako będącą w gruncie rzeczy tak trudną jak rozwiązanie dobrze znane jako problem
trudności rzekomej (typowo teoria liczb), tak ,jak rozkład na czynniki pierwsze liczb całkowitych lub obliczanie
logarytmu dyskretnego. Zatem, „udowadnialnie „ oznacza” tu udowadnialny przedmiot założeń.
Takie

podejście jest rozważane przez będące uznanymi za dobre, praktyczne techniki analizy jakie

istnieją. Udowadnialne bezpieczeństwo może być rozpatrywane jako część specjalnej pod –klasy dużej klasy
bezpieczeństwa obliczeniowego
(iv) Bezpieczeństwo obliczeniowe
Mierzy ilość wymaganego wkładu obliczeniowego przez najnowsze metody ,pokonania systemu; musi być tu
założenie, ze system został dobrze zbadany dla określenia które ataki są istotne. Proponowane techniki będą
bezpieczne obliczeniowo jeśli postrzegany poziom obliczeniowy wymagany do pokonania go (przy użyciu
najlepiej znanych ataków) przekracza, poza wygodny margines, zasoby obliczeniowe hipotetycznego
przeciwnika.
Częstymi metodami w tej klasie są odniesienia do trudnych problemów, ale ,w odróżnieniu od
udowadnianego bezpiecznie, nie jest znany żaden równoważny dowód. Większość z dobrze znanych schematów
klucza publicznego i klucza symetrycznego jest rozpowszechnionych w tej klasie. Klasa ta jest czasami również
znana jako bezpieczeństwo praktyczne.
(v) Bezpieczeństwo improwizowane
To podejście składa się z rozmaitych przekonywujących argumentów, że każdy atak zakończony powodzeniem
wymaga poziomu zasobu np. czasu i przestrzeni) większej niż stałe zasoby dostrzeżonego przeciwnika. Funkcje
pierwotne kryptografii i protokoły które przetrwają taką analizę są nazywane bezpieczeństwem heurystycznym;
z bezpieczeństwem typowym w sensie obliczeniowym. Funkcje pierwotne i protokoły są zazwyczaj
projektowane do zliczania standardowych ataków takich jak te podane w §1.13. Podczas gdy być może jest to
najbardziej powszechne używane podejściem (zwłaszcza dla protokołów) które jest najmniej satysfakcjonujące.
Żądanie bezpieczeństwa generalnie pozostaje wątpliwe a nieprzewidziane ataki stają się groźne.
1.13.4 Perspektywy bezpieczeństwa obliczeniowego
Przy wyliczaniu bezpieczeństwa schematu kryptograficznego są często rozważane pewne wielkości
1.69 Definicja Współczynniki roboczy W

jest to minimalna ilość pracy (mierzonej we właściwych jednostkach

takich jak operacje elementarne czy cykle zegarowe) wymaganej do obliczenia klucza prywatnego d danego
kluczem publicznym e lub w przypadku schematu klucza symetrycznego, określającego tajny klucz k. .Ściślej
można rozważać pracę wymaganą przez atak tekstem zaszyfrowanym danym n zaszyfrowanymi tekstami,
oznaczane W

(n).

Jeśli W

ma t lat wtedy dla wystarczająco dużego t schemat kryptograficzny jest , we wszystkich

praktycznych celów, systemem bezpieczeństwa. System klucza niepublicznego odnajduje gdzie można
udowodnić wystarczająco dużą dolną granicę współczynnika pracy W

. Najlepsze jest to ,że możliwe datowanie

polega na podstawach bezpieczeństwa.
1.70 Definicja Historyczny współczynnik pracy W^

jest to minimalna ilość pracy wymagana do obliczenia

prywatnego klucza d z publicznego klucza e używając najlepiej znane algorytmy w danym punkcie czasu.

Historyczny

współczynniki pracy W^

zmieniają się w czasie jako algorytmy i poprawianie technologii.

Odpowiada to bezpieczeństwu obliczeniowemu , podczas gdy W

odpowiada prawdziwemu poziomowi

bezpieczeństwa chociaż nie może być to zazwyczaj określone.
Jak duże jest duże?
§1.4 opisywał jak zaprojektować system szyfrujący próbując stworzyć schemat dla najlepszego podejścia
przełamania go poprzez przeszukiwani wyczerpujące przestrzeni klucza. Przestrzeń klucza musi wtedy być
dosyć duża aby uczynić przeszukiwanie wyczerpujące zupełnie niewykonalne. Ważnym pytaniem jest „Jak duże
jest duże?” Żeby rzucić jakąś perspektywę na rząd wielkości liczb Tablica 1.2 pokazuje różne z nich wraz z
powiązanymi wielkościami.

Tablica 1.2 Odniesienie liczb porównujących relatywne rzędy wielkości

Niektóre potęgi 10 odnoszą się do prefiksów. Na przykład, szybkie komputery mają teraz współczynniki pod
względem teraflopów, gdzie teraflop jest to 10

operacji zmienno przecinkowych na sekundę. Tablica 1.3

dostarcza listy powszechnie używanych prefiksów

Tablica 1.3 Prefiksy używane dla różnych potęg 10