SŁOWO WSTĘPNE

Każdy, kto przeczytał jedną lub dwie książki o bezpieczeństwie komputerowym, mógł spotkać się z powszechnym poglądem na temat kryptografii. Mówi się że "kryptografia to najsilniejsze ogniwo w łańcuchu". To stanowcze sformułowanie, ale nieco lekceważące. Jeśli rzeczywiście kryptografia to najsilniejsza część naszego systemu, to po co inwestować swój czas w jej poprawę, jeśli jest tyle innych obszarów systemu, które mogą więcej skorzystać na poświęceniu im naszej uwagi?

Jeśli jest coś, co należy wynieść z tej książki, to jest to świadomość, że ten pogląd na kryptografię jest wyidealizowany. To w dużej części mit. Kryptografia jest mocna w teorii, ale w praktyce jest tak samo podatna na błędy, jak każdy inny element systemu bezpieczeństwa. Sprawdza się to w szczególności, gdy implementacje kryptograficzne są tworzone przez osoby niebędące ekspertami, bez wystarczającej dbałości lub doświadczenia, jak się to zdarza w wielu wdrażanych dziś systemach kryptograficznych. I sytuacja się pogarsza - gdy już implementacje kryptograficzne zawodzą, często zawodzą w niezwykle spektakularny sposób.

Czemu się tym przejmować i po co jest ta książka?

Gdy niemal dwadzieścia lat temu zacząłem pracować w dziedzinie stosowanej kryptografii, informacje, które mieli twórcy oprogramowania, były często fragmentaryczne i nieaktualne. Kryptografowie tworzyli algorytmy i protokoły, a inżynierowie zajmujący się kryptografią wdrażali je, aby tworzyć nieprzejrzyste, słabo udokumentowane biblioteki kryptograficzne zaprojektowane przede wszystkim z myślą o innych ekspertach. Istniał wtedy duży podział między tymi, którzy znali i rozumieli algorytmy kryptograficzne, i tymi, którzy ich używali (lub ignorowali je na swoją zgubę). Nie ma na rynku wielu porządnych podręczników, a jeszcze mniej jest takich, które dają praktykom użyteczne narzędzia.

Wyniki tego nie były piękne. Mówię o naruszeniach podstawowych algorytmów "CVE" (Common Vulnerabilities and Exposures) i "Severity:High" (Bardzo poważne) oraz kilku alarmujących przypadkach, atakach na prezentacje oznaczone jako "ŚCIŚLE TAJNE". Możecie znać niektóre słynne przykłady choćby dlatego, że uderzyły one w systemy, na których polegacie. Wiele z tych problemów wystąpiło, gdyż kryptografia jest subtelna i elegancka matematycznie, a eksperci z tej dziedziny nie podzielili się swoją wiedzą z inżynierami, którzy pisali oprogramowanie.

Na szczęście zaczęło się to zmieniać i ta książka jest symptomem tych zmian.

Nowoczesna kryptografia została napisana przez jednego z najlepszych ekspertów stosowanej kryptografii, ale nie jest skierowana do ekspertów. Nie znaczy to, że jej celem jest powierzchowny przegląd całej dziedziny. Przeciwnie, zawiera ona pełne i aktualne omówienie inżynierii kryptograficznej, przygotowane jako pomoc dla praktyków, którzy planują lepsze działanie w tej dziedzinie. Z tej książki dowiecie się, nie tylko jak działają algorytmy kryptograficzne, ale jak z nich korzystać w prawdziwych systemach.

Książka zaczyna się od analizy wielu podstawowych pojęć z zakresu kryptografii, w tym podstawowych algorytmów jako szyfry blokowe, systemy szyfrowania publicznego, funkcje skrótu i generatory liczb losowych. Każdy rozdział podaje praktyczne przykłady pracy algorytmów i co należy, a czego nie należy robić. Końcowe rozdziały poruszają zaawansowane tematy, jak TLS, a także przyszłość kryptografii - co robić po nadejściu komputerów kwantowych, które skomplikują nam życie.

Choć ta jedna książka nie jest w stanie rozwiązać wszystkich naszych problemów, to nieco wiedzy może zaprowadzić nas daleko. A ta książka zawiera dużo wiedzy. Zapewne dosyć, aby rzeczywista, wdrażana kryptografia spełniła oczekiwania, jakie wielu z nas z nią wiąże.

Przyjemnego czytania!

Matthew D. Green Profesor

Information Security Institute Johns Hopkins University

WPROWADZENIE

Książkę tę napisałem, gdyż takiej mi brakowało, gdy zaczynałem się uczyć kryptografii. W roku 2005 byłem na studiach magisterskich w pobliżu Paryża i bardzo chciałem zapisać się na kurs kryptografii w kolejnym semestrze. Niestety, zajęcia zostały odwołane z powodu zbyt małej liczby zapisanych na nie studentów. "Kryptografia jest za trudna" mówili studenci i zamiast tego masowo zapisywali się na kursy grafiki komputerowej i baz danych.

Tekst "kryptografia jest trudna" słyszałem od tego czasu wiele razy. Ale czy ona naprawdę jest aż tak trudna? Aby grać na instrumencie, opanować dobrze język programowania lub zrealizować w praktyce zastosowania w jakiejkolwiek dziedzinie, trzeba nauczyć się nieco pojęć i symboli, ale nie wymaga to doktoratu. Wydaje mi się, że to samo dotyczy nabycia kompetencji z zakresu kryptografii. Uważam także, że kryptografia postrzegana jest jako trudna, gdyż kryptografowie nie uczą jej dobrze.

Innym powodem, dla którego uważałem, że ta książka jest potrzebna, jest fakt, że nie chodzi tylko o kryptografię - rozwinęła się ona w dziedzinę wielodyscyplinarną. Aby zrobić coś potrzebnego i znaczącego w kryptografii, trzeba rozumieć związane z nią pojęcia: jak działają sieci i komputery, czego potrzebują użytkownicy oraz systemy i jak napastnicy mogą zaatakować algorytmy i ich implementacje. Innymi słowy, trzeba być w kontakcie z rzeczywistością.

Stosowane podejście

Początkowo tytuł tej książki brzmiał Crypto for Real (Prawdziwa kryptografia), co miało podkreślić, że przyjęte podejście jest skupione na kwestiach praktycznych, na rzeczywistych zastosowaniach. Nie chciałem sprawić, aby kryptografia stała się przystępna przez jej uproszczenie, ale wolałem powiązać ją z rzeczywistymi zastosowaniami. Podaję kod źródłowy i przykłady, opisując prawdziwe błędy i historie jak z horroru.

Obok nawiązania do nowoczesności atutami tej książki są prostota i nowoczesne podejście Skupiłem się na prostej formie: przedstawiam wiele nietrywialnych pojęć, bez nudnego formalizmu matematycznego. Próbuję wprowadzić zrozumienie najważniejszych pojęć kryptografii, które są ważniejsze od zapamiętywania wielu równań. Aby zapewnić nowoczesność książki, omawiam najnowsze dokonania i zastosowania kryptografii, jak TLS 1.3 oraz kryptografię postkwantową. Nie omawiam szczegółów starych lub mało bezpiecznych algorytmów, jak DES lub MD5. Wyjątek stanowi RC4, ale jest on tu uwzględniony, abym mógł wyjaśnić jak bardzo jest słaby, i aby pokazać, jak działa szyfr strumieniowy tego rodzaju.

Nowoczesna kryptografia nie jest przewodnikiem po oprogramowaniu kryptograficznym ani kompendium specyfikacji technicznych - takie rzeczy można łatwo znaleźć w sieci. Podstawowym celem tej książki jest zaciekawienie was kryptografią, a przy okazji nauczenie podstawowych pojęć z nią związanych.

Dla kogo jest ta książka

Pisząc tę książkę, często wyobrażałem sobie czytelnika jako dewelopera, który spotkał się z szyframi, ale czuł się zagubiony i sfrustrowany po próbach przeczytania niezrozumiałych podręczników i artykułów naukowych. Deweloperzy często potrzebują - i chcą - lepszego zrozumienia szyfrów, aby uniknąć złych wyborów projektowych. Mam nadzieję, że książka ta im w tym pomoże.

Ale jeśli nie piszecie programów, nie martwcie się! Ta książka nie wymaga umiejętności programowania i jest dostępna dla każdego, kto rozumie podstawy informatyki i zna matematykę na poziomie szkoły średniej (pojęcia prawdopodobieństwa, arytmetyki modulo itd.).

Książka ta może jednak onieśmielać i pomimo swej względnej dostępności wymaga nieco wysiłku, aby z niej naprawdę skorzystać. Lubię porównania wspinaczkowe - autor układa ścieżkę, zapewniając nam liny i czekany, aby ułatwić pracę, ale sami musimy wejść na szczyt. Nauka pojęć z tej książki będzie wymagała wysiłku. Ale na końcu czeka nas nagroda.

Układ książki

Książka ma 14 rozdziałów podzielonych na cztery części. Rozdziały są w zasadzie od siebie niezależne, poza rozdziałem 9, który daje podstawy dla trzech kolejnych rozdziałów. Zalecam też przeczytanie trzech pierwszych rozdziałów, przed przejściem do kolejnych.

Podstawy

- Rozdział 1: Szyfrowanie wprowadza pojęcie bezpiecznego szyfrowania, od słabych szyfrów papierowych do silnego szyfrowania probabilistycznego.

- Rozdział 2: Losowość opisuje, jak działa generator pseudolosowy i jakie warunki trzeba spełnić, aby był on bezpieczny, a także jak używać generatorów w sposób bezpieczny.

- Rozdział 3: Bezpieczeństwo kryptograficzne omawia teoretyczne i praktyczne pojęcia bezpieczeństwa i porównuje systemy z dowodami bezpieczeństwa do tych prawdopodobnie bezpiecznych.

Szyfry symetryczne

- Rozdział 4: Szyfry blokowe dotyczy szyfrów, które przetwarzają komunikaty blok po bloku, skupiając się na najbardziej znanym z nich, AES (Advanced Encryption Standard).

- Rozdział 5: Szyfry strumieniowe prezentuje szyfry, które tworzą strumień losowo wyglądających bitów szyfrowanych za pomocą XOR-owania z bitami komunikatów do zaszyfrowania.

- Rozdział 6: Funkcje skrótu dotyczą jedynego algorytmu, który nie działa z tajnym kluczem, a okazuje się blokiem kryptograficznym o najbardziej wszechstronnej budowie.

- Rozdział 7: Funkcje skrótu z kluczem tłumaczy, co się dzieje, gdy połączymy funkcję skrótu z tajnym kluczem, i jak pomaga to w uwierzytelnianiu komunikatów.

- Rozdział 8: Uwierzytelniane szyfrowanie pokazuje, jak niektóre algorytmy mogą zarówno szyfrować, jak i uwierzytelniać komunikaty, na przykładach takich jak AES-GCM.

Szyfry asymetryczne

- Rozdział 9: Trudne problemy wykłada podstawowe pojęcia leżące u podstaw kryptografii klucza publicznego, wykorzystując pojęcia złożoności obliczeniowej.

- Rozdział 10: RSA wykorzystuje problem rozkładu na czynniki w celu zbudowania bezpiecznego szyfrowania i systemów podpisu za pomocą prostych działań arytmetycznych.

- Rozdział 11: Diffie-Hellman rozszerza kryptografię asymetryczną na pojęcia uzgadniania kluczy, gdzie dwie strony uzgadniają tajną wartość, wykorzystując wartości, które nie są tajne.

- Rozdział 12: Krzywe eliptyczne podaje łagodne wprowadzenie do kryptografii krzywych eliptycznych, która jest najszybszym rodzajem kryptografii asymetrycznej.

Zastosowania

- Rozdział 13: TLS skupia się na protokole TLS (Transport Layer Security), który jest uważany za najważniejszy protokół w bezpieczeństwie sieciowym.

- Rozdział 14: Kryptografia kwantowa i postkwantowa kończy książkę nutą science fiction, opisując pojęcia komputerów kwantowych i nowy rodzaj kryptografii.

PODZIĘKOWANIA

Chciałbym podziękować Jan, Annie i pozostałym członkom zespołu No Starch, którzy mają swój wkład w tę książkę, a zwłaszcza Billowi, który wierzył w ten projekt od początku, za jego cierpliwość w przetrawieniu trudnych tematów i przekształcaniu moich niezdarnych prób w nadające się do czytania strony. Jestem też wdzięczny Laurel za to, że książka ta wygląda tak ładnie i za wprowadzenie wielu moich poprawek.

Od strony technicznej książka zawierałaby wiele błędów i niedokładności bez pomocy wymienionych tu osób: Jon Callas, Bill Cox, Niels Ferguson, Philipp Jovanovic, Samuel Neves, David Reid, Phillip Rogaway, Erik Tews, a także wszystkich czytelników wczesnych wersji, którzy zgłosili błędy. Wreszcie dziękuję Mattowi Greenowi za napisanie słowa wstępnego.

Chciałbym też podziękować mojemu pracodawcy, firmie Kudelski Security, za czas, który mogłem przeznaczyć na tę książkę. Wreszcie przekazuję najgłębsze podziękowania Aleksandrze i Melinie za ich wsparcie i cierpliwość.

Lozanna, 17.05.2017 (trzy liczby pierwsze)

SKRÓTY

AE

authenticated encryption, szyfrowanie uwierzytelnione

AEAD

authentication encryption with associated data, szyfrowanie uwierzytelnione z powiązanymi danymi

AES

Advanced Encryption Standard, zaawansowany standard szyfrowania

AES-NI

instrukcje natywne AES

AKA

authenticated key agreement, uwierzytelnione uzgadnianie kluczy

API

application program interface, interfejs programistyczny aplikacji

ARX

add-rotate-XOR, dodawanie-rotacja-XOR

ASIC

application-specific integrated circuit, układ scalony do konkretnych zastosowań

CA

certificate authority, urząd certyfikacyjny, jednostka certyfikująca

CAESAR

Competition for Authenticated Encryption: Security, Applicability, and Robustness, konkurs w szyfrowaniu uwierzytelnionym: bezpieczeństwo, zastosowalność i odporność

CBC

cipher block chaining, wiązanie bloków zaszyfrowanych

CCA

chosen-ciphertext attackers, atak z wybranym szyfrogramem

CDH

computational Diffie-Hellman, obliczeniowy problem Diffiego-Hellmana

CMAC

cipher-based MAC, MAC oparty na szyfrowaniu

COA

ciphertext-only attack, atak z samym szyfrogramem

CPA

chosen-plaintext attack, atak z wybranym tekstem jawnym

CRT

Chinese remainder theorem, chińskie twierdzenie o resztach

CTR

counter mode, tryb licznika

CVP

closest vector problem, problem najbliższego wektora

DDH

decisional Diffie-Hellman, decyzyjny problem Diffiego-Hellmana

DES

Data Encryption Standard, standard szyfrowania danych

DH

Diffie-Hellman

DLP

discrete logarithm problem, problem logarytmu dyskretnego

DRBG

deterministic random bit generator, deterministyczny generator bitów losowych

ECB

electronic codebook, elektroniczna książka kodowa

ECC

elliptic curve cryptography, kryptografia krzywych eliptycznych

ECDH

elliptic curve Diffie-Hellman, protokół Diffiego-Hellmana na krzywej eliptycznej

ECDLP

elliptic-curve discrete logarithm problem, problem logarytmu dyskretnego na krzywej eliptycznej

ECDSA

elliptic-curve digital signature algorithm, algorytm podpisu cyfrowego na krzywych eliptycznych

FDH

Full Domain Hash, skrót pełnodomenowy

FHE

fully homomorphic encryption, szyfrowanie w pełni homomorficzne

FIPS

Federal Information Processing Standards, Federalny Standard Przetwarzania Informacji

FPE

format-preserving encryption, szyfrowanie zachowujące format

FPGA

field-programmable gate array, bezpośrednio programowane macierze bramek

FSR

feedback shift register, rejestr przesuwny ze sprzężeniem zwrotnym

GCD

greatest common divisor, największy wspólny dzielnik (NWD)

GCM

Galois Counter Mode, tryb licznika Galois

GNFS

general number field sieve, ogólne sito ciała liczbowego

HKDF

HMAC-based key derivation function, funkcja wyprowadzania klucza na bazie HMAC

HMAC

hash-based message authentication code, kod uwierzytelniania wiadomości na podstawie skrótu

HTTPS

HTTP Secure, bezpieczny protokół HTTP

IND

indistinguishablity, nierozpoznawalność

IP

Internet Protocol, protokół internetowy

IV

initial value, wartość początkowa

KDF

key derivation function, funkcja wyprowadzania klucza

KPA

known-plaintext attack, atak ze znanym tekstem jawnym

LFSR

linear feedback shift register, rejestr przesuwny z liniowym sprzężeniem zwrotnym

LSB

least significant bit, bit najmniej znaczący

LWE

learning with errors, uczenie się z błędami

MAC

message authentication code, kod uwierzytelniania wiadomości

MD

message digest, skrót wiadomości

MitM

meet-in-the-middle

MQ

multivariate quadratics, równanie kwadratowe wielu zmiennych

MQV

Menezes-Qu-Vanstone

MSB

most significant bit, bit najbardziej znaczący

MT

Mersenne Twister

NFSR

nonlinear feedback shift register, rejestr przesuwny z nieliniowym sprzężeniem zwrotnym

NIST

National Institute of Standards and Technology, Narodowy Instytut Standaryzacji i Technologii

NM

non-malleability, niedeformowalność

OAEP

Optimal Asymmetric Encryption Padding, optymalne dopełnienie w szyfrowaniu asymetrycznym

OCB

offset codebook, książka kodowa z przesunięciem

P

polynomial time, czas wielomianowy

PLD

programmable logic device, programowane urządzenie logiczne

PRF

pseudorandom function, funkcja pseudolosowa

PRNG

pseudorandom number generator, generator liczb pseudolosowych

PRP

pseudorandom permutation, permutacja pseudolosowa

PSK

pre-shared key, wstępnie współdzielony klucz

PSS

Probabilistic Signature Scheme, schemat podpisu probabilistycznego

QR

quarter-round, ćwierć-runda

QRNG

quantum random number generator, kwantowy generator liczb losowych

RFC

request for comments, prośba o komentarze

RNG

random number generator, generator liczb losowych

RSA

Rivest-Shamir-Adleman

SHA

Secure Hash Algorithm, bezpieczny algorytm skrótu

SIS

short integer solution, problem krótkiego rozwiązania w liczbach całkowitych

SIV

Synthetic IV

SPN

substitution-permutation network, sieć podstawieniowo-permutacyjna

SSH

Secure Shell, bezpieczna powłoka

SSL

Secure Socket Layer, bezpieczna warstwa gniazd

TE

tweakable encryption, szyfrowanie dostrajalne

TLS

Transport Layer Security, bezpieczeństwo warstwy transportowej

TMTO

time-memory trade-off, kompromis między czasem a pamięcią

UDP

User Datagram Protocol, protokół pakietów użytkownika

UH

universal hash, uniwersalna funkcja skrótu

WEP

Wired Equivalent Privacy, protokół szyfrowania w sieciach bezprzewodowych

WOTS

Winternitz one-time signature, jednorazowy podpis Winternitza

XOR

exclusive OR, alternatywa wykluczająca

1SZYFROWANIE

Szyfrowanie jest głównym zastosowaniem kryptografii: sprawia, że dane stają się niezrozumiałe, co ma zapewnić ich poufność. W szyfrowaniu stosowany jest algorytm nazywany szyfrem oraz sekretna wartość nazywana kluczem. Jeśli nie znamy klucza, nie możemy odszyfrować ani nawet poznać kawałka informacji z zaszyfrowanego komunikatu - nie może też tego zrobić żaden napastnik.

W tym rozdziale skupimy się na szyfrowaniu symetrycznym, które jest najprostszym rodzajem szyfrowania. W szyfrowaniu symetrycznym klucz używany do odszyfrowania służy jednocześnie do szyfrowania (w przeciwieństwie do szyfrowania asymetrycznego, czyli szyfrowania kluczem publicznym, w którym klucz używany do odszyfrowania różni się od klucza służącego do szyfrowania). Zaczniemy od poznania najsłabszych rodzajów szyfrowania symetrycznego - szyfrów klasycznych, które zabezpieczają tylko przed najbardziej nieudolnymi napastnikami i stopniowo będziemy przechodzić do najmocniejszych szyfrów, które zawsze są bezpieczne.

Podstawy

Gdy szyfrujemy komunikat, tekst jawny oznacza komunikat niezaszyfrowany, a szyfrogram to komunikat zaszyfrowany. Szyfr ma zatem dwie funkcje: szyfrowanie zamienia jawny tekst w szyfrogram, a odszyfrowanie zamienia szyfrogram z powrotem w jawny tekst. Często jednak mówimy "szyfr", gdy tak naprawdę mamy na myśli "szyfrowanie". Na przykład na rysunku 1.1 pokazano szyfr E, w postaci ramki, do której wchodzi tekst jawny P oraz klucz K, który tworzy na wyjściu szyfrogram C. Zapisujemy tę zależność jako C = E(K, P). Podobnie, gdy szyfr jest w trybie odszyfrowywania, zapisujemy to jako D(K, C).

Rysunek 1.1. Podstawowe szyfrowanie i odszyfrowanie

UWAGAW przypadku niektórych szyfrów szyfrogram ma taki sam rozmiar jak tekst jawny, a dla innych jest on nieco dłuższy. Szyfrogramy nie są jednak nigdy krótsze od tekstów jawnych.

Szyfry klasyczne

Szyfry klasyczne to szyfry, które powstały wcześniej niż komputery i dlatego działają na literach, a nie na bitach. Są znacznie prostsze od nowoczesnych szyfrów, takich jak DES - w starożytnym Rzymie lub podczas I wojny światowej nie można było wykorzystywać możliwości układów scalonych, aby szyfrować komunikat, więc wszystko trzeba było robić za pomocą pióra i papieru. Istnieje wiele klasycznych szyfrów, a najbardziej znanymi są szyfr Cezara oraz szyfr Vigen?re'a.

Szyfr Cezara

Szyfr Cezara został tak nazwany, ponieważ według rzymskiego historyka, Swetoniusza, z szyfru tego korzystał Juliusz Cezar. Szyfruje on komunikat, przesuwając każdą z liter o trzy pozycje w dół alfabetu, wracając z powrotem do A, jeśli przesunięcie dojdzie do Z. Na przykład szyfrogramem ZOO jest CRR, FDHVDU to zaszyfrowane słowo CAESAR itd., jak pokazano na rysunku 1.2. Liczba 3 nie jest wartością szczególną; po prostu łatwiej dodać w pamięci 3 niż 11 lub 23.

Szyfr Cezara jest niezwykle łatwo złamać: aby to zrobić, przesuwamy tylko litery o trzy pozycje do tyłu, aby odtworzyć jawny tekst. Mówi się, że szyfr Cezara mógł być wystarczająco mocny w czasach Krassusa i Cycerona. Ponieważ nie zawiera on żadnego sekretnego klucza (jest nim zawsze 3), korzystający z szyfru Cezara musieli jedynie założyć, że napastnicy byli niepiśmienni lub zbyt słabo wykształceni, aby na to wpaść - dziś to założenie jest znacznie mniej realistyczne. (Faktycznie, w 2006 r. włoska policja aresztowała szefa mafii po tym, gdy zaszyfrował wiadomości zapisane na małych skrawkach papieru, korzystając z odmiany szyfru Cezara: na przykład ABC było szyfrowane jako 456 zamiast DEF).

Rysunek 1.2. Szyfr Cezara

Czy można sprawić, że szyfr Cezara będzie trudniejszy do złamania? Można - wyobraźmy sobie na przykład wersję z sekretnym przesunięciem zamiast zawsze 3, lecz to niewiele by pomogło, ponieważ napastnicy mogliby z łatwością wypróbować tych 25 możliwych przesunięć, aż zaszyfrowana wiadomość nabierze sensu.

Szyfr Vigen?re'a

Dopiero po 1500 latach, w XVI w., powstało ważne ulepszenie szyfru Cezara w postaci szyfru Vigen?re, którego twórcą był Włoch, Giovan Battista Bellaso. Nazwa "Vigen?re'a" pochodzi od nazwiska Francuza, Blaise'a de Vigen?re, któremu błędnie przypisano autorstwo tego szyfru, choć w tym samym stuleciu opracował on inny szyfr. Tak czy inaczej, szyfr Vigen?re'a stał się popularny i był później używany m.in. przez konfederatów podczas wojny secesyjnej oraz przez wojsko szwajcarskie podczas I wojny światowej.

Szyfr Vigen?re'a jest podobny do szyfru Cezara, z tą różnicą, że litery nie są przesunięte o trzy miejsca, lecz o wartości zdefiniowane przez klucz, zbiór liter reprezentujący liczby na podstawie ich położenia w alfabecie. Jeśli na przykład kluczem jest DUH, litery w tekście jawnym są przesuwane o wartości 3, 20, 7, ponieważ D jest trzecią literą za A, U jest 20 literą po A, a H jest 7 literą po A. Schemat 3, 20, 7 powtarza się, aż zostanie zaszyfrowany cały tekst. Dla przykładu, używając DUH jako klucza, można zaszyfrować słowo CRYPTO jako FLFSNV: C jest przesunięte o trzy pozycje do F, R jest przesunięte o 20 pozycji do L itd. Na rysunku 1.3 pokazano tę zasadę przy szyfrowaniu zdania THEY DRINK THE TEA.

Rysunek 1.3. Szyfr Vigen?re'a

Szyfr Vigen?re'a jest oczywiście mocniejszy od szyfru Cezara, lecz nadal dość łatwo go złamać. Pierwszym krokiem do jego złamania jest ustalenie długości klucza. Na przykład na rysunku 1.3 THEY DRINK THE TEA zaszyfrowano jako WBLBXYLHRWBLWYH za pomocą klucza DUH. (Odstępy są zazwyczaj usuwane, aby ukryć granice słów). Zwróćmy uwagę, że w szyfrogramie WBLBXYLHRWBLWYH grupa trzech liter WBL pojawia się dwukrotnie w odstępie 9-literowym. To sugeruje, że to samo słowo trzyliterowe było zaszyfrowane przy użyciu tego samego przesunięcia, tworząc za każdym razem WBL. Kryptoanalityk może wtedy wydedukować, iż długością klucza jest dziewięć bądź wartość podzielna przez dziewięć. Ponadto można odgadnąć, iż tym powtarzającym się słowem trzyliterowym jest THE i stąd ustalić, że możliwym kluczem szyfrowania jest DUH.

Drugim etapem łamania szyfru Vigen?re'a jest ustalenie rzeczywistego klucza przy użyciu analizy częstotliwości, w której wykorzystuje się nierówny rozkład liter w językach. Na przykład najpopularniejszą literą w języku angielskim jest E, jeśli więc okaże się, że w szyfrogramie najczęściej powtarza się X, najprawdopodobniej w jawnym tekście na tym miejscu jest E.

Pomimo pewnych słabości szyfr Vigen?re'a może być wystarczająco dobry, aby bezpiecznie zaszyfrować wiadomości. Po pierwsze, ponieważ opisany właśnie atak wymaga przynajmniej kilku zdań komunikatu i nie działa, jeśli szyfr był użyty do szyfrowania tylko krótkich komunikatów. Po drugie, większość komunikatów musi być tajna tylko przez krótki okres, nie ma więc znaczenia, że szyfrogramy w końcu zostaną odszyfrowane przez wroga. (XIX-wieczny kryptograf August Kerckhoffs oszacował, że większość zaszyfrowanych wiadomości z czasów wojny wymagało poufności tylko przez trzy do czterech godzin).

Jak działają szyfry

Na podstawie uproszczonych szyfrów, takich jak szyfr Cezara i Vigen?re'a, możemy próbować zdefiniować pojęcia dotyczące działania szyfru - najpierw identyfikując jego dwa główne komponenty: permutację oraz tryb pracy. Permutacja jest funkcją, która przekształca obiekt (w kryptografii literę lub grupę bitów) w taki sposób, że każdy obiekt ma jednoznaczną odwrotność (na przykład w cyfrze Cezara jest to przesunięcie o trzy litery). Tryb pracy to algorytm, który wykorzystuje permutację do przetwarzania wiadomości o dowolnym rozmiarze. Tryb szyfru Cezara jest trywialny: powtarza tylko tę samą permutację dla każdej litery, lecz jak widzieliśmy, szyfr Vigen?re'a ma bardziej złożony tryb, w którym to litery na różnych pozycjach są poddawane innym permutacjom.

W następnych rozdziałach omówiono bardziej szczegółowo, czym są te komponenty oraz jak są powiązane z bezpieczeństwem szyfru. Przy użyciu każdego z tych komponentów pokazujemy, dlaczego klasyczne szyfry są skazane na porażkę jako łatwe do złamania, w przeciwieństwie do nowoczesnych szyfrów, które działają na szybkich komputerach.

Permutacja

Działanie większości szyfrów klasycznych polega na zastąpieniu każdej litery inną - innymi słowy, na wykonaniu podstawienia. W szyfrach Cezara i Vigen?re'a zastąpienie jest przesunięciem w alfabecie, jednak alfabet lub zestaw symboli mogą się różnić: zamiast angielskiego alfabetu może być to alfabet arabski, zamiast liter mogą być na przykład słowa, liczby lub ideogramy. Reprezentacja lub kodowanie informacji jest oddzielną sprawą, która nie ma związku z bezpieczeństwem. (Bierzemy pod uwagę tylko alfabet łaciński, ponieważ jest on używany w klasycznych szyfrach).

Podstawianie w szyfrach nie może być dowolnym podstawieniem. Powinno być permutacją, czyli takim przestawieniem liter od A do Z, żeby każda litera miała jednoznaczną odwrotność. Na przykład podstawienie, które przekształca litery A, B, C i D odpowiednio na C, A, D i B, jest permutacją, ponieważ każda litera jest odwzorowywana na inną pojedynczą literę. Ale podstawienie, które przekształca A, B, C, D na D, A, A, C, nie jest permutacją, ponieważ zarówno B, jak i C są odwzorowane na A. W przypadku permutacji każda litera ma dokładnie jedną odwrotność.

Jednak nie każda permutacja jest bezpieczna. Aby tak było, permutacja szyfru powinna spełniać trzy kryteria:

- Permutacja powinna być określona przez klucz, tak aby utrzymywać ją w tajemnicy, dopóki klucz jest tajny. W szyfrze Vigen?re'a, jeśli nie znamy klucza, nie wiemy, która z 26 permutacji została użyta; dlatego nie można łatwo go odszyfrować.

- Różne klucze powinny dawać różne permutacje. W przeciwnym wypadku odszyfrowanie bez klucza stałoby się łatwiejsze: różne klucze dawałyby identyczne permutacje, a więc mniejszą liczbę różnych kluczy niż różnych permutacji, a zatem mniej możliwości do wypróbowania podczas odszyfrowywania bez klucza. W szyfrze Vigen?re'a każda litera z klucza determinuje zastąpienie; jest 26 różnych liter i tyleż różnych permutacji.

- Permutacja powinna wyglądać na losową. Po dokonaniu permutacji w szyfrogramie nie powinno być żadnego wzorca, gdyż sprawiłby, że napastnik przewidzi permutację, a więc jest ona mniej bezpieczna. Na przykład podstawianie w szyfrze Vigen?re'a jest dość przewidywalne: jeśli ustalimy, że A jest szyfrowane jako F, możemy wysnuć wniosek, że wartością przesunięcia jest 5, i będziemy także wiedzieć, że B jest szyfrowane jako G, C jako H itd. Jednak w przypadku permutacji wybranej losowo informacja, że A jest szyfrowane na F, oznacza jedynie, iż B nie jest szyfrowane jako F.

Permutację, która spełnia te kryteria, nazywamy bezpieczną permutacją. Jak się jednak zaraz przekonamy, bezpieczna permutacja jest konieczna, lecz niewystarczająca do zbudowania bezpiecznego szyfru. Szyfr będzie także wymagał trybu działania obsługującego komunikaty o dowolnej długości.

Tryb działania

Powiedzmy, że mamy bezpieczną permutację, która na przykład przekształca A w X, B w M oraz N w L. Słowo BANANA jest zatem szyfrowane jako MXLXLX, w którym każde wystąpienie A jest zastępowane przez X. Użycie tej samej permutacji do wszystkich liter w jawnym tekście ujawnia więc wszelkie zdublowane w nim litery. Analizując te duplikaty, może nie poznamy całego komunikatu, ale dowiemy się czegoś na jego temat. W przykładzie BANANA nie potrzebujemy klucza, aby odgadnąć, że jawny tekst ma tę samą literę na pozycjach X i tę samą literę na dwóch pozycjach L. Jeśli na przykład wiemy, że komunikat jest nazwą owocu, możemy stwierdzić, że jest to raczej BANANA niż CHERRY, LYCHEE lub inny owoc na sześć liter.

Tryb działania (lub po prostu tryb) szyfru zmniejsza możliwość ujawnienia zdublowanych liter w jawnym tekście poprzez użycie różnych permutacji dla powtarzających się liter. Tryb szyfru Vigen?re'a częściowo rozwiązuje to tak: jeśli klucz ma długość N liter, wtedy N różnych permutacji będzie użytych dla każdych N kolejnych liter. Nadal jednak jego rezultatem są schematy w szyfrogramie, ponieważ każda N-ta litera wiadomości używa tej samej permutacji. Dlatego analiza częstotliwości pomaga złamać szyfr Vigen?re'a, jak wcześniej widzieliśmy.

Analiza częstotliwości może nie dać rezultatów, jeśli szyfr Vigen?re'a szyfruje jedynie teksty o takiej samej długości jak klucz. Lecz nawet wtedy jest inny problem: kilkukrotne użycie tego samego klucza ujawnia podobieństwa między jawnymi tekstami. Na przykład słowa TIE i PIE będą odpowiednio zaszyfrowane jako DGR i ZGR przy użyciu klucza KYN. Oba kończą się na dwie takie same litery (GR), co pokazuje, że jawne teksty także miały jednakowe dwie ostatnie litery. Znajdowanie tych wzorców nie powinno być możliwe w bezpiecznym szyfrze.

Aby stworzyć bezpieczny szyfr, trzeba połączyć bezpieczną permutację z bezpiecznym trybem. Najlepiej, żeby to połączenie uniemożliwiało napastnikom dowiedzenie się czegokolwiek na temat komunikatu poza jego długością.

Dlaczego szyfry klasyczne nie są bezpieczne

Szyfry klasyczne nie są bezpieczne z natury, ponieważ są ograniczone do działań, które można wykonać w pamięci lub na kartce papieru. Nie mają mocy obliczeniowej komputera i łatwo je złamać za pomocą prostych programów komputerowych. Przyjrzyjmy się podstawowemu powodowi, dla którego ta prostota powoduje, iż nie są one bezpieczne w dzisiejszym świecie.

Pamiętajmy, że permutacja szyfru powinna wyglądać na losową, aby była bezpieczna. Oczywiście najlepszą metodą, aby wyglądała ona na losową jest to, aby była losowa - czyli, aby wybrać każdą permutację w sposób losowy ze zbioru wszystkich permutacji. A jest wiele permutacji do wyboru. W przypadku 26-literowego angielskiego alfabetu istnieje około 288 permutacji:

26! = 403291461126605635584000000 ? 288

Tutaj wykrzyknik (!) jest symbolem silni, zdefiniowanej jako:

n! = n × (n - 1) × (n - 2) × . . . × 3 × 2

(Aby zobaczyć, dlaczego otrzymujemy taką liczbę, policzmy permutacje jako listę przestawionych liter: jest 26 wyborów dla pierwszej możliwej litery, następnie 25 możliwości dla drugiej, 24 dla trzeciej itd.). Ta liczba jest wielka: jest tego samego rzędu wielkości co liczba atomów w ludzkim ciele. Ale klasyczne szyfry mogą wykorzystywać tylko mały ułamek tych permutacji - mianowicie te, które potrzebują tylko prostych działań (takich jak przesunięcia) oraz mają krótki opis (jak krótki algorytm lub mała tabela do przeglądania). Problem jest taki, że bezpieczna permutacja nie może spełnić obu tych ograniczeń.

Bezpieczne permutacje można uzyskać za pomocą prostych działań, wybierając losową permutację, przedstawiając ją jako tabelę 25 liter (wystarczającą, aby przedstawić permutację 26 liter bez 26) i stosując ją poprzez przeglądanie liter w tej tablicy. Wtedy jednak nie miałaby ona krótkiego opisu. Na przykład opisanie 10 różnych permutacji wymaga 250 liter, a nie 10 liter używanych w szyfrze Vigen?re'a.

Możemy także tworzyć bezpieczne permutacje z wykorzystaniem krótkiego opisu. Zamiast samego przesuwania alfabetu można stosować bardziej złożone działania, takie jak dodawanie, mnożenie itd. Nowoczesne szyfry działają następująco: mając klucz o długości zazwyczaj 128 lub 256 bitów, wykonują setki działań bitowych, aby zaszyfrować pojedynczą literę. Ten proces jest szybki na komputerze, który może wykonywać miliardy operacji bitowych na sekundę, lecz zrobienie tego ręcznie może zająć godziny i nadal będzie podatne na analizę częstotliwości.

Idealne szyfrowanie - klucz jednorazowy

Zasadniczo klasyczny szyfr nie może być bezpieczny, chyba że ma wielki klucz, lecz szyfrowanie za pomocą wielkiego klucza jest niepraktyczne. Takim szyfrem jest jednak szyfr z kluczem jednorazowym i jest to szyfr najbardziej bezpieczny. W rzeczywistości gwarantuje to doskonałą tajność: nawet jeśli napastnik ma nieograniczoną moc obliczeniową, nie może dowiedzieć się niczego o jawnym tekście poza jego długością.

W następnych punktach pokażemy, jak działa szyfr z kluczem jednorazowym, i podamy zarys dowodu jego bezpieczeństwa.

Szyfrowanie za pomocą klucza jednorazowego

Szyfr z kluczem jednorazowym bierze jawny tekst P oraz losowy klucz K, który ma taką samą długość jak P1 i tworzy szyfrogram C zdefiniowany jako

C = P ? K

gdzie C, P oraz K są ciągami bitów tej samej długości, a ? jest bitową alternatywą wykluczającą (XOR), zdefiniowaną następująco: 0 ? 0 = 0, 0 ? 1 = 1, 1 ? 0 = 1, 1 ? 1 = 0.

UWAGAPrzedstawiam klucz jednorazowy w jego zwykłej postaci, jako działający na bitach, lecz może być on przystosowany do innych symboli. W przypadku liter otrzymalibyśmy odmianę szyfru Cezara z indeksem przesunięcia wybieranym losowo dla każdej litery.

Odszyfrowanie klucza jednorazowego jest identyczne jak szyfrowanie. To tylko działanie XOR: P = C ? K. Rzeczywiście możemy sprawdzić, że C ? K = P ? K ? K = P, ponieważ wykonywanie działania XOR na K z nim samym daje łańcuch złożony z samych zer 000 . . . 000. I o to chodzi - jest to nawet prostsze od szyfru Cezara.

Na przykład, jeśli P = 01101101 oraz K = 10110100, wtedy można obliczyć co następuje:

C = P ? K = 01101101?10110100 = 11011001

Szyfrowanie odtwarza P za pomocą następującego obliczenia:

P = C ? K = 11011001?10110100 = 01101101

Ważne jest to, że każdy klucz jednorazowy K może być użyty jeden raz. Jeśli tego samego klucza K użyjemy do zaszyfrowania P1 i P2 jako C1 i C2, wtedy podsłuchujący może wykonać następujące obliczenie:

C1 ? C2 = (P1 ? K) ? (P2 ? K ) = P1 ? P2 ? K ? K = P1 ? P2

Podsłuchujący mógłby wówczas poznać różnicę między XOR P1 i P2, czyli informację, która powinna być utrzymana w tajemnicy. Ponadto, jeśli znany jest któryś z jawnych tekstów wiadomości, wtedy można odtworzyć inną wiadomość.

Oczywiście szyfr z jednorazowym kluczem jest bardzo niewygodny w użyciu, ponieważ wymaga klucza o długości szyfrowanego tekstu oraz nowego, losowego klucza dla każdej nowej wiadomości lub grupy danych. Do zaszyfrowania dysku twardego o pojemności jednego terabajta potrzebny byłby inny dysk 1 TB, aby przechować na nim klucz! Niemniej szyfr z kluczem jednorazowym był używany na przestrzeni dziejów. Na przykład korzystało z niego Brytyjskie Kierownictwo Operacji Specjalnych (British Special Operations Executive) podczas II wojny światowej, szpiedzy KGB, NSA i nadal jest używany w szczególnych kontekstach. (Słyszałem o szwajcarskich bankierach, którzy nie potrafilii się zgodzić na szyfr zaufany przez obie strony i w rezultacie stosowali szyfry z kluczem jednorazowym, lecz ja tego nie polecam).