Wykład 1

Podstawowe pojęcia kryptologii

1.1

Co to jest kryptologia?

Szyfrem lub systemem kryptograficznym nazywamy system ukrywania znaczenia wiado-

mości przez zastąpienie każdego znaku oryginalnej wiadomości w ustalony sposób przez

inny znak, przy czym zastąpienie to powinno być możliwe do jednoznacznego odwrócenia

(odszyfrowania) przynajmniej dla adresata wiadomości.

Elementy kryptosystemu

• algorytm szyfrowania —niezmienny w obrębie danego kryptosystemu

• klucz — dowolnie wymieniany, służący do zainicjowania konkretnej procedury

przekształcenia tekstu jawnego w tekst tajny.

Kryptologia jest nauką o wszystkich aspektach tajnego zapisywania wiadomości.

Składowe kryptologii

• kryptografia, czyli nauka o szyfrowaniu wiadomości, tzn. o ukrywaniu jej znaczenia;

• kryptoanaliza, czyli nauka o odczytywaniu zaszyfrowanego tekstu bez uprzedniej

znajomości klucza;

• steganografia, czyli nauka o ukrywaniu wiadomości (i ich istnienia).

1

Kilka użytecznych pojęć — podejście nieformalne

• Tekst jawny to oryginalna wiadomość przed zaszyfrowaniem.

• Tekst tajny (szyfrogram, kryptogram) jest to wiadomość po zaszyfrowaniu.

• Szyfrowaniem nazywamy przekształcanie wiadomości jawnej w tekst zaszyfrowany.

• Deszyfrowanie to przekształcanie tekstu tajnego w jawny, również w przypadku,

gdy klucz nie jest znany osobom dokonującym deszyfracji (mówi się wtedy o ła-

maniu szyfru).

1.2

Klasyfikacja szyfrów

Podstawowe typy szyfrów

• Szyfr podstawieniowy jest szyfrem, w którym każda litera (lub ciąg liter) zostaje

zastąpiony pewnym umownym znakiem, ale nie zmienia swojego miejsca w tekście.

• Szyfr przestawieniowy to szyfr, w którym każda litera tekstu jawnego zmienia swoją

pozycję w tekście, ale zachowuje swoją tożsamość; w wyniku stosowania takiego

szyfru otrzymujemy anagram tekstu jawnego.

• Szyfry mieszane.

Szyfry podstawieniowe

dzielą się na

• szyfry monoalfabetyczne (bez homofonów), w których każdemu znakowi alfabetu

jawnego odpowiada zawsze ten sam znak alfabetu tajnego;

• szyfry monoalfabetyczne z homofonami, w których każdemu znakowi alfabetu jaw-

nego odpowiada zawsze ten sam zbiór znaków alfabetu tajnego, przy czym pew-

nym znakom alfabetu jawnego przyporządkowane zostały zbiory znaków alfabetu

tajnego zawierające więcej, niż jeden element;

• szyfry polialfabetyczne, w których używa się wielu alfabetów tajnych i każdy znak

tekstu jawnego jest szyfrowany za pomocą jednego z tych alfabetów, wybranego

w pewien ustalony sposób.

2

Klasyfikacja ze względu na wielkość przekształcanych jednostek tekstu

jawnego

• szyfry blokowe,

• szyfry strumieniowe.

Klasyfikacja ze względu na postać klucza

• szyfry symetryczne,

• szyfry asymetryczne.

1.3

Formalna definicja systemu kryptograficznego

Systemem kryptograficznym nazywamy uporządkowaną piątkę

(P, C , K , E, D),

w której

• P jest skończonym zbiorem nazywanym przestrzenią tekstów jawnych,

• C

jest skończonym zbiorem nazywanym przestrzenią tekstów tajnych,

• K

jest skończonym zbiorem nazywanym przestrzenią kluczy,

• E = {E

k

: k ∈ K } jest zbiorem reguł szyfrowania,

• D = {D

k

: k ∈ K } jest zbiorem reguł deszyfrowania,

przy czym spełniony jest warunek

∀

k

∈K

∀

x

∈P

D

k

(E

k

(x)) = x.

Elementy zbioru P nazywamy tekstami jawnymi lub otwartymi, elementy zbioru C

—

kryptogramami, tekstami tajnymi lub zaszyfrowanymi, zaś elementy zbioru K

— klu-

czami. Elementy zbiorów E i D są, na ogół, funkcjami. Pierwsze nazywamy funkcjami

szyfrującymi, a drugie — funkcjami deszyfrującymi.

3