Wprowadzenie

do Kryptografii

Janusz Szmidt

Wojskowa Akademia Techniczna
[e-mail]



Kryptografia – sztuka lub nauka
zapisywania tekstu jawnego w tajny
sposób



Kryptoanaliza – analiza
i odszyfrowywanie tajnego pisma



Kryptologia – naukowe badanie
kryptografii i kryptoanalizy

Wojskowa Akademia Techniczna
[e-mail]

Nadawca

klucz

klucz

tekst jawny

tekst jawny

algorytm

algorytm

tekst zaszyfrowany

Adresat

jawny

kanał

Przeciwnik

(kryptoanalityk)

Wojskowa Akademia Techniczna
[e-mail]



Steganografia – metoda ukrywania
tekstu jawnego (bez jego
przekształcania):



Atrament sympatyczny



Metody fotograficzne



Metody elektronicznego ukrywania
danych

Wojskowa Akademia Techniczna
[e-mail]

Po odwinięciu skórzanego paska z pręta
nadawcy widać na nim jedynie pozornie
przypadkowy ciąg liter S, T, S, F…Dopiero po
nawinięciu paska na sctytale o właściwej
średnicy można odczytać wiadomość: send
more troops to southern flank and…(wyślij
więcej żołnierzy na południową flankę i…)

Wojskowa Akademia Techniczna
[e-mail]



Szyfr Juliusza Cezara (I w. p.n.e., 100-
40 p.n.e) – pierwszy algorytm szyfrujący
(z jednym kluczem).

j u l i u s z c e z a r

MXOLXVCFHCDU

a b c d e f g h i j k l m

D E F G H I J K L M N O P

n o p q r s t u v w x y z

Q R S T U V W X Y Z A B C

Wojskowa Akademia Techniczna
[e-mail]

Dysk

szyfrowy

używany

przez

stany

Konfederacji w czasie wojny.

Wojskowa Akademia Techniczna
[e-mail]



Szyfr przesuwający – stosujemy
różne (cykliczne) przesunięcia alfabetu



K jest tzw. przestrzenią klucza



Przesunięcie k wybierane (ustalane) jest
w sposób tajny dla komunikujących się
stron.



Szyfr ten jest łatwy do złamania stosując
sprawdzanie wszystkich możliwych
k (tzw. przeszukanie przestrzeni klucza)
lub metody analizy częstościowej języka,
w którym napisany jest tekst jawny.

K

k





}

25

,...,

2

,

1

{

Wojskowa Akademia Techniczna
[e-mail]



Szyfr Vigenere’a (XV w.) – zastosowanie
różnych przesunięć dla danego tekstu
jawnego,



Przesunięcia wyznaczane są przez hasło
(klucz), na przykład:

k = „szyfr” = (18, 25, 24, 5, 17),

Tekst jawny:

tenkr yptos ystem nieje stbez piecz ny

Szyfrogram:

LDLPI QORTJ QRRJD FHCOV KSZJQ HHCHQ FX



Szyfr ten został złamany w XIX w.
zaawansowanymi metodami analizy
częstościowej języka.

Wojskowa Akademia Techniczna
[e-mail]



Szyfr z kluczem bieżącym – kluczem
jest inny tekst z języka naturalnego (np.
fragment jakiejś książki), np.:

Tekst jawny:

tajneaktaznajdująsię

Klucz:

kluczemjestfragmentk

Szyfrogram:

ĆLĆÓCEWBEPFFADĄVĘEBÓ



Szyfr taki poddaje się w pewnym stopniu
analizie częstościowej; w szczególności,
jeśli ten sam klucz został wielokrotnie
użyty do różnych tekstów jawnych.

Wojskowa Akademia Techniczna
[e-mail]



Szyfr Vernama (1917 r.)



Klucz ma długość tekstu jawnego



Klucz jest losowym ciągiem znaków



Dany klucz jest użyty tylko raz do
określonego tekstu jawnego



Twierdzenie Shannona (1949 r.)



Szyfr Vernama jest absolutnie
bezpieczny

Wojskowa Akademia Techniczna
[e-mail]

Wojskowa maszyna Enigma gotowa do

użycia.

Wojskowa Akademia Techniczna
[e-mail]

Ruchomy

punkt

dowodzenia

generała

Heinza Guderiana. U dołu z lewej strony
widać maszynę Enigma.

Wojskowa Akademia Techniczna
[e-mail]

Marian Rejewski

Wojskowa Akademia Techniczna
[e-mail]

W

sierpniu

1939

roku

główni

angielscy

kryptoanalitycy odwiedzili Bletchley Park, aby
ocenić, czy nadaje się na siedzibę nowej instytucji,
Government Code and Cypher School. Nie chcąc
zwracać uwagi okolicznych mieszkańców, goście
udawali, że przyjechali na polowanie.

Wojskowa Akademia Techniczna
[e-mail]

Alan Turing

Wojskowa Akademia Techniczna
[e-mail]

Bomba z Bletchley Park

Wojskowa Akademia Techniczna
[e-mail]



Idea kryptografii klucza publicznego (Diffie,
Hellman, 1976 r.)



Każdy z użytkowników kryptosystemu np.
użytkownik A (Alicja) ma dwa różne klucze: e

A

tzw. Klucz publiczny (jawny), który ogłasza
publicznie oraz klucz d

A

tzw. Klucz prywatny

(tajny),

który

trzyma

w tajemnicy. Odpowiednio inny użytkownik
systemu
B (Bolek) posiada inną parę kluczy e

B

, d

B

o podobnym znaczeniu.



Przekształcenia tekstu odpowiadające każdej
parze kluczy są wzajemnie odwrotne, np.:

ść

identyczno

e

d

A

A





Wojskowa Akademia Techniczna
[e-mail]



Poufna komunikacja między

użytkownikami:



Szyfrowanie



Bolek pobiera klucz jawny e

A

Alicji



B szyfruje wiadomość M kluczem e

A

otrzymując szyfrogram C = e

A

(M).

(Ewa)

C = e

A

(M)

(Bolek)

(Alicja)

Wojskowa Akademia Techniczna
[e-mail]



Deszyfrowanie



Alicja deszyfruje szyfrogram C swoim
kluczem prywatnym (tajnym) otrzymując
wiadomość M:

d

A

(C) = d

A

(e

A

(M)) = id(M) = M



Bezpieczeństwo



Przeciwnik (krytpoanalityk) Ewa zna klucz
publiczny e

A

, ale nie zna prywatnego klucza

d

A

Alicji.



Z założeń kryptosystemu klucz d

A

nie może

być (praktycznie) wyliczony z klucza e

A.

Wojskowa Akademia Techniczna
[e-mail]



Kryptosystem klucza publicznego
RSA (1977 r.) – nazwa pochodzi od
nazwisk autorów: Rivest, Shamir,
Adleman.



Szyfr ten spełnia wszystkie wymagania
postawione wyżej. Bezpieczeństwo oparte
jest na trudności faktoryzacji (rozkładu na
liczby pierwsze) dużych liczb naturalnych.
Jest to bezpieczeństwo warunkowe, zależne
od posiadanych mocy obliczeniowych.

Wojskowa Akademia Techniczna
[e-mail]



Przykład (z 1978 r.)



q

= 3 490 529 510 847 650 949 147 849 619 903 898 133 417

764 638 493 387 843 990 820 577



p =

32 769 132 993 266 709 549 961 988 190 834 461 413

177 642 967 992 942 539 798 288 533



N = p*q =

114 381 625 757 888 867 669 235 779 976

146 612 010 218 296 721 242 362 562 561 842 935 706

935 245 733 897 830 597 123 563 958 705 058 989 075

147 599 590 026 879 543 541



Liczby pierwsze p, q znane są tylko danemu

użytkownikowi systemu (np. Alicji). Używane są

jedynie na wstępnym etapie generowania

kluczy e

A

, d

A

, później są kasowane. Moduł N

znany jest publicznie. Bezpieczeństwo szyfru

oparte jest na trudności obliczeniowej rozkładu

modułu N na czynniki pierwsze p, q.

Wojskowa Akademia Techniczna
[e-mail]



Komercyjne zastosowania
kryptografii



Systemy telefonii komórkowej GSM



Karty bankomatowe i karty dostępu



Internetowe konta bankowe



Internetowe operacje finansowe



Handel elektroniczny



Bezpieczna poczta elektroniczna



Podpis elektroniczny



Zabezpieczenie danych elektronicznych

Wojskowa Akademia Techniczna
[e-mail]

Dziękuję za uwagę