Kryptografia. W teorii i praktyce - ebook

WSTĘP

Pierwsze wydanie tej książki ukazało się w 1995 roku. Celem było wówczas opracowanie ogólnego podręcznika, który obejmowałby wszystkie podstawowe dziedziny kryptografii, jak również wybrane bardziej zaawansowane tematy. Ostatnio, w 2002 roku, ukazało się drugie wydanie, a w 2006 roku – trzecie.

Od czasu pierwszego wydania tej książki 23 lata temu dokonano wielu ekscytujących postępów w kryptografii. Jednocześnie wiele z „rdzennych” obszarów kryptografii, które były wtedy ważne, jest nadal aktualnych – zapewnienie silnego oparcia na podstawach pozostaje głównym celem tej pracy. Trzeba było podjąć wiele decyzji co do tego, które ze starszych tematów zachować, a które nowe powinny zostać włączone do książki. W naszych wyborach kierowaliśmy się takimi kryteriami, jak znaczenie dla praktycznych zastosowań kryptografii, a także wpływ nowych podejść i technik na projektowanie oraz analizę protokołów kryptograficznych. W wielu przypadkach wiązało się to z prowadzeniem nowatorskich badań i próbą przedstawienia ich w przystępny sposób, odpowiedni do prezentacji w ramach nauczania.

W tym kontekście podstawowy materiał kryptografii klucza tajnego i publicznego traktowany jest w podobny sposób jak w poprzednich edycjach. Do tego wydania zostało jednak dodanych wiele tematów, z których najważniejsze to:

• Całkiem nowy rozdział na temat ekscytującego, rozwijającego się obszaru kryptografii postkwantowej, który obejmuje najważniejsze kryptosystemy, projektowane w celu zapewnienia bezpieczeństwa przed atakami realizowanymi przez komputery kwantowe (rozdział 9).

• Nowy, wysokopoziomowy, nietechniczny przegląd celów i narzędzi kryptografii (rozdział 1).

• Nowy dodatek matematyczny podsumowujący definicje i główne wyniki teorii liczb i algebry, które są wykorzystywane w całej książce. Daje to możliwość szybkiego odwołania się do wszelkich terminów i twierdzeń matematycznych, które czytelnik mógłby chcieć znaleźć (dodatek A).

• Rozszerzone potraktowanie szyfrów strumieniowych, w tym wspólne techniki projektowania wraz z opisem popularnego szyfru strumieniowego znanego jako Trivium.

• Książka przedstawia teraz dodatkowe, ciekawe ataki na kryptosystemy, w tym:

- atak wyroczni (_padding oracle attack_),

- ataki korelacyjne i ataki algebraiczne na szyfry strumieniowe,

- atak na generator bitów losowych DUAL-EC, wykorzystujący zapadki.

• Podajemy sposób postępowania z konstrukcją gąbki funkcji skrótu i jej zastosowanie w nowym standardzie funkcji skrótu SHA-3. Jest to znaczące nowe podejście do projektowania funkcji skrótu.

• Opisano metody dystrybucji kluczy w sieciach czujników.

• Jest też dział poświęcony podstawom kryptografii wizualnej. Pozwala to na bezpieczną metodę dzielenia tajnej wiadomości wizualnej na części (udziały), które mogą być później łączone w celu zrekonstruowania tajemnicy.

• Opisane są podstawowe techniki kryptowalut, stosowane w BITCOIN i blockchain.

• Wyjaśniamy podstawy nowych metod kryptograficznych stosowanych w protokołach komunikacyjnych takich jak _Signal_. Obejmują one takie tematy, jak zaprzeczalność i aktualizacja klucza Diffiego–Hellmana.

Mamy nadzieję, że książka ta może być wykorzystana w różnych kursach. Wstępny kurs na poziomie licencjackim może być oparty na wyborze materiału z pierwszych ośmiu rozdziałów. Należy podkreślić, że w kilku rozdziałach, późniejsze podrozdziały mogą być uważane za bardziej zaawansowane niż wcześniejsze. Mogą one stanowić materiały do kursów dla absolwentów lub do samodzielnej nauki. Materiały z późniejszych rozdziałów mogą być również włączone do kursu wprowadzającego lub uzupełniającego, w zależności od zainteresowań instruktora.

Kryptografia jest szerokim przedmiotem i wymaga znajomości kilku dziedzin matematyki, w tym teorii liczb, grup, pierścieni i ciał, algebry liniowej, prawdopodobieństwa i teorii informacji. Przydatna jest również pewna znajomość złożoności obliczeniowej, algorytmów i teorii zupełności NP. Naszym zdaniem to właśnie szerokość wymaganego tła matematycznego często stwarza trudności osobom studiującym po raz pierwszy kryptografię. Mając to na uwadze, utrzymaliśmy prezentację matematyczną z poprzednich edycji. Jedną z podstawowych zasad jest to, że rozumienie matematyki jest niezbędne do zrozumienia różnych schematów i tematów kryptograficznych. Jednocześnie staramy się unikać niepotrzebnie zaawansowanych technik matematycznych – dostarczamy niezbędne informacje, ale nie przeciążamy czytelnika niepotrzebnymi pojęciami matematycznymi.

Następujące cechy są wspólne dla wszystkich wydań tej książki:

• Tło matematyczne jest podawane na bieżąco tam, gdzie jest potrzebne.

• Nieformalne opisy kryptosystemów są podane wraz z dokładniejszymi opisami pseudokodów.

• Przykłady numeryczne zaprezentowano dla zilustrowania działania większości algorytmów opisanych w tej książce.

• Matematyczne podstawy algorytmów i kryptosystemów zostały wyjaśnione dokładnie i rygorystycznie.

• W książce są też liczne ćwiczenia, a niektóre z nich stanowią spore wyzwanie.

Przygotowując to nowe wydanie, otrzymaliśmy użyteczne opinie od różnych osób na temat treści tej książki. W szczególności chcielibyśmy podziękować Colleen Swanson za wiele pomocnych komentarzy i sugestii. Kilku recenzentów dostarczyło nam przydatne sugestie, a my doceniamy również komentarze Stevena Galbraitha i Jalaja Upadhyaya. Na koniec dziękujemy Roberto De Prisco, który przygotował przykłady udziałów w systemie progów wizualnych zawartych w rozdziale 11.

_Douglas R. Stinson_

_Maura B. Paterson_ROZDZIAŁ 1
WPROWADZENIE DO KRYPTOGRAFII

W tym rozdziale przedstawiamy krótki przegląd rodzajów problemów badanych w kryptografii oraz technik ich rozwiązywania. Problemy te oraz narzędzia kryptograficzne, które są stosowane w ich rozwiązywaniu, zostały omówione bardziej szczegółowo i ściśle w dalszej części tej książki. Wprowadzenie to może służyć jako nieformalne, nietechniczne, niematematyczne podsumowanie poruszanych tematów. Jako takie można je uznać za lekturę opcjonalną.

1.1. Kryptosystemy i podstawowe narzędzia kryptograficzne

W tej części omawiamy podstawowe pojęcia związane z szyfrowaniem. Obejmują one kryptografię klucza tajnego i publicznego, szyfry blokowe i strumieniowe oraz kryptografię hybrydową.

1.1.1. Kryptosystemy z kluczem tajnym

Kryptografia jest stosowana od tysięcy lat w celu zapewnienia poufnej komunikacji między wzajemnie zaufanymi stronami. W jej najbardziej podstawowej formie, dwie osoby, często określane jako _Alicja_ i _Bob_, uzgodniły konkretny _tajny klucz_. W późniejszym czasie Alicja może chcieć wysłać sekretną wiadomość do Boba (lub Bob może chcieć wysłać wiadomość do Alicji). Klucz jest używany do przekształcenia oryginalnej wiadomości (zazwyczaj nazywanej _tekstem jawnym_) w zaszyfrowaną formę, która jest niezrozumiała dla każdego, kto nie posiada tego klucza. Proces ten jest nazywany _szyfrowaniem_, a zaszyfrowana wiadomość jest nazywana tekstem zaszyfrowanym lub _szyfrogramem_ (_ciphertext_). Gdy Bob odbierze zaszyfrowany tekst, może użyć tego klucza do przekształcenia zaszyfrowanego tekstu z powrotem w oryginalny tekst jawny. Jest to proces _odszyfrowywania_. _Kryptosystem_ stanowi pełną specyfikację kluczy i sposobu, w jaki są one wykorzystywane do szyfrowania i odszyfrowywania informacji.

Różne typy kryptosystemów o coraz większym stopniu zaawansowania były wykorzystywane do wielu celów w historii. Ważne zastosowania obejmowały poufną komunikację między przywódcami politycznymi i/lub członkami rodziny królewskiej, manewry wojskowe itp. Jednak wraz z rozwojem Internetu i zastosowań takich jak handel elektroniczny pojawiło się wiele nowych, różnorodnych zastosowań. Obejmują one takie scenariusze, jak szyfrowanie haseł, numerów kart kredytowych, poczty elektronicznej, dokumentów, plików i nośników cyfrowych.

Należy także wspomnieć, że techniki kryptograficzne są również szeroko stosowane w celu ochrony przechowywanych danych, oprócz danych przekazywanych przez jedną stronę do drugiej. Na przykład użytkownicy mogą chcieć szyfrować dane przechowywane na laptopach, zewnętrznych twardych dyskach, w chmurze, bazach danych itp. Dodatkowo użyteczna może być możliwość wykonywania obliczeń na zaszyfrowanych danych (bez uprzedniego ich odszyfrowania).

Opracowanie i wdrożenie kryptosystemu musi uwzględniać kwestię bezpieczeństwa. Tradycyjnie zagrożenie kryptograficzne stanowiło zagrożenie ze strony podsłuchującego przeciwnika, który mógłby przechwycić szyfrowany tekst i spróbować go odszyfrować. Jeśli okaże się, że przeciwnik ma klucz, to nic nie da się zrobić. Tak więc główne względy bezpieczeństwa dotyczą przeciwnika, który nie ma klucza, a mimo to nadal próbuje odszyfrować zaszyfrowany tekst. Techniki stosowane przez przeciwnika w celu „złamania” kryptosystemu nazywane są _kryptoanalizą_. Najbardziej oczywistym rodzajem analizy kryptograficznej jest próba odgadnięcia klucza. Atak, w którym przeciwnik próbuje rozszyfrować zaszyfrowany tekst za pomocą każdego możliwego klucza, nazywany jest _wyczerpującym poszukiwaniem klucza_. Gdy przeciwnik spróbuje znaleźć właściwy klucz, zostanie znaleziony tekst jawny, ale gdy zostanie użyty jakikolwiek inny klucz, „odszyfrowany”, szyfrogram będzie prawdopodobnie przypadkowym bełkotem. Tak więc oczywistym pierwszym krokiem w projektowaniu bezpiecznego kryptosystemu jest określenie bardzo dużej liczby możliwych kluczy, tak wielu, że przeciwnik nie będzie w stanie przetestować ich wszystkich w rozsądnym czasie.

Opisany powyżej model kryptografii jest zwykle nazywany _kryptografią klucza tajnego_. Oznacza to, że istnieje jeden tajny klucz, który jest znany zarówno Alicji, jak i Bobowi. To znaczy, że klucz ten jest „tajemnicą”, która jest znana dwóm stronom. Klucz ten jest wykorzystywany zarówno do szyfrowania otwartych tekstów, jak i do odszyfrowywania szyfrogramów. Rzeczywiste funkcje szyfrowania i odszyfrowywania są więc wzajemnie odwrotne. Niektóre podstawowe kryptosystemy klucza tajnego są wprowadzane i analizowane w odniesieniu do różnych pojęć bezpieczeństwa w rozdziałach 2 i 3.

Wadą kryptografii tajnego klucza jest to, że Alicja i Bob muszą jakoś wcześniej uzgodnić tajny klucz (zanim będą chcieli wysyłać do siebie nawzajem jakiekolwiek wiadomości). Może to być proste, jeśli Alicja i Bob są w tym samym miejscu, kiedy wybierają swój tajny klucz. Ale co jeśli Alicja i Bob są daleko od siebie, powiedzmy na różnych kontynentach? Jednym z możliwych rozwiązań jest wykorzystanie przez Alicję i Boba kryptosystemu klucza publicznego.

1.1.2. Kryptosystemy klucza publicznego

Rewolucyjny pomysł _kryptografii klucza publicznego_ został wprowadzony w latach 70. XX wieku przez Diffiego i Hellmana. Ich pomysł polegał na tym, że być może uda się stworzyć kryptografię, w której istnieją dwa odrębne klucze. _Klucz publiczny_ służyłby do szyfrowania tekstu jawnego, a _klucz prywatny_ umożliwiałby odszyfrowanie zaszyfrowanego tekstu. Należy zauważyć, że klucz publiczny może być znany „każdemu”, podczas gdy klucz prywatny jest znany tylko jednej osobie (a mianowicie odbiorcy zaszyfrowanej wiadomości). Tak więc kryptosystem klucza publicznego umożliwiłby każdemu zaszyfrowanie wiadomości, która ma być przesłana, powiedzmy, do Boba, a tylko Bob mógłby ją odszyfrować. Pierwszym i najbardziej znanym przykładem kryptosystemu klucza publicznego jest kryptosystem __ RSA, który został wynaleziony przez Rivesta, Shamira i Adlemana. Różne typy kryptosystemów klucza publicznego zostały przedstawione w rozdziałach 6, 7 i 9.

Kryptografia klucza publicznego eliminuje konieczność uzgadniania przez dwie strony wcześniej udostępnionego klucza tajnego. Nadal jednak konieczne jest opracowanie metody bezpiecznej dystrybucji kluczy publicznych. Nie jest to wcale trywialny cel do osiągnięcia, a główną kwestią jest poprawność i autentyczność domniemanych kluczy publicznych. Certyfikaty, które omawiamy nieco później, są jedną z powszechnych metod radzenia sobie z tym problemem.

1.1.3. Szyfry blokowe i strumieniowe

Kryptosystemy są zazwyczaj klasyfikowane jako _szyfry blokowe_ lub _szyfry strumieniowe_. W szyfrze blokowym tekst jawny jest podzielony na fragmenty o stałej wielkości, zwane _blokami_. Blok jest określony jako ciąg bitów (tzn. ciąg zer i jedynek) o określonej długości (np. 64 lub 128 bitów). Szyfr blokowy szyfruje (lub odszyfrowuje) jeden blok naraz. W przeciwieństwie do tego szyfr strumieniowy najpierw używa klucza do skonstruowania strumienia szyfrującego (_keystream_), który jest ciągiem bitowym o dokładnie tej samej długości co tekst jawny (tekst jawny jest ciągiem bitowym o dowolnej długości). Operacja szyfrowania konstruuje szyfrogram jako alternatywę wykluczającą tekstu jawnego i strumienia klucza. Odszyfrowywanie uzyskuje się przez obliczenie alternatywy wykluczającej (XOR) szyfrogramu i strumienia szyfrującego. Kryptosystemy klucza publicznego są zawsze szyframi blokowymi, natomiast kryptosystemy klucza tajnego mogą być szyframi blokowymi lub strumieniowymi. Szyfr blokowy jest szczegółowo omówiony w rozdziale 4.

1.1.4. Kryptografia hybrydowa

Jedną z wad kryptosystemów z kluczem publicznym jest to, że są one znacznie wolniejsze niż kryptosystemy z kluczem tajnym. W konsekwencji kryptosystemy klucza publicznego są wykorzystywane głównie do szyfrowania małych ilości danych, np. numeru karty kredytowej. Istnieje jednak ładny sposób na połączenie kryptografii z kluczem tajnym i publicznym, aby wykorzystać zalety obu tych rozwiązań. Technika ta nazywana jest _kryptografią hybrydową_. Załóżmy, że Alicja chce zaszyfrować „długą” wiadomość i wysłać ją do Boba. Załóżmy, że Alicja i Bob nie mają wcześniej wspólnego tajnego klucza. Alicja może wybrać losowy tajny klucz i zaszyfrować tekst jawny, używając (szybkiego) tajnego klucza kryptograficznego. Następnie Alicja szyfruje ten klucz niejawny przy użyciu klucza publicznego Boba. Alicja wysyła zaszyfrowany tekst i zaszyfrowany klucz do Boba. Bob najpierw używa swojego prywatnego klucza szyfrującego do odszyfrowania tajnego klucza, a następnie używa tego tajnego klucza do odszyfrowania zaszyfrowanego tekstu.

Zauważmy, że „powolny” kryptosystem klucza publicznego jest używany tylko do szyfrowania krótkiego tajnego klucza. Znacznie szybszy kryptosystem klucza tajnego jest używany do szyfrowania dłuższego tekstu jawnego. W ten sposób kryptografia hybrydowa (prawie) osiąga efektywność kryptografii tajnego klucza, ale może być stosowana w sytuacji, gdy Alicja i Bob nie mają wcześniej ustalonego klucza tajnego.

1.2. Integralność wiadomości

W tym podrozdziale omówiono różne narzędzia, które pomagają osiągnąć integralność danych, w tym kody uwierzytelniania wiadomości (MAC), schematy podpisów i funkcje skrótu.

Kryptosystemy zapewniają _tajność_ (inaczej _poufność_) przed podsłuchującym przeciwnikiem, który jest często nazywany _pasywnym przeciwnikiem_. Zakłada się, że pasywny przeciwnik jest w stanie uzyskać dostęp do wszelkich informacji przesyłanych przez Alicję do Boba (patrz rysunek 1.1). Istnieje jednak wiele innych zagrożeń, przed którymi chcielibyśmy się chronić, zwłaszcza gdy obecny jest _aktywny przeciwnik_. Aktywny przeciwnik to taki, który może zmienić informacje przesyłane od Alicji do Boba.

Rysunek 1.2 przedstawia niektóre z możliwych działań aktywnego przeciwnika. Aktywny przeciwnik może

• zmienić informacje, które są wysyłane od Alicji do Boba,

• wysyłać informacje do Boba w taki sposób, aby Bob uważał, że informacje pochodzą od Alicji, lub

• przekierowywać informacje wysłane od Alicji do Boba w taki sposób, aby osoba trzecia (Charlie) otrzymała te informacje zamiast Boba.

Możliwe cele aktywnego przeciwnika mogą obejmować oszukiwanie Boba, aby (powiedzmy) zaakceptował „fałszywe” informacje, lub wprowadzenie Boba w błąd co do tego, kto wysłał mu te informacje.

Należy zauważyć, że samo szyfrowanie nie może chronić przed tego typu aktywnymi atakami. Na przykład szyfr strumieniowy jest podatny na _atak przełączania bitów_ (_bit-flipping attack_). Jeśli niektóre bity szyfru zostaną „odwrócone” (tzn. zera zostaną zastąpione jedynkami i na odwrót), to efektem jest odwrócenie odpowiadających im bitów zwykłego tekstu. W ten sposób przeciwnik może modyfikować tekst jawny w sposób przewidywalny, nawet jeśli nie wie, jakie są bity jawne.

Istnieją różne rodzaje gwarancji „integralności”, które możemy próbować wykorzystać w celu ochrony przed ewentualnymi działaniami aktywnego przeciwnika. Taki przeciwnik może zmienić informacje, które są przekazywane od Alicji do Boba (i należy pamiętać, że informacje te mogą, ale nie muszą być szyfrowane). Alternatywnie przeciwnik może próbować „podrobić” wiadomość i wysłać ją do Boba, mając nadzieję, że ten pomyśli, iż pochodzi ona od Alicji. Narzędzia kryptograficzne, które chronią przed tymi i podobnymi rodzajami zagrożeń, mogą być konstruowane w ustawieniach zarówno klucza tajnego, jak i publicznego. W systemach klucza tajnego omawiamy krótko pojęcie kodu uwierzytelniania wiadomości (lub MAC – _Message Authentication Code_). W rozwiązaniach klucza publicznego, narzędziem służącym do mniej więcej podobnego celu jest _schemat podpisu cyfrowego_.

RYSUNEK 1.1. Przeciwnik pasywny

RYSUNEK 1.2. Przeciwnik aktywny

1.2.1. Kody uwierzytelniania wiadomości

Kod uwierzytelniania wiadomości wymaga, aby Alicja i Bob współdzielili tajny klucz. Gdy Alicja chce wysłać wiadomość do Boba, używa tajnego klucza do utworzenia _znacznika_, który dołącza do wiadomości (znacznik zależy zarówno od klucza, jak i od wiadomości). Kiedy Bob odbierze wiadomość i znacznik, użyje klucza do ponownego obliczenia znacznika i sprawdzi, czy jest on taki sam jak znacznik, który otrzymał. Jeśli tak, to Bob akceptuje wiadomość jako autentyczną wiadomość od Alicji, a jeśli nie, to Bob odrzuca wiadomość jako niepoprawną. Zwracamy uwagę, że wiadomość może być szyfrowana lub nie. Kody MAC zostały omówione w rozdziale 5.

Jeśli nie ma potrzeby zachowania poufności, wiadomość może być wysłana jako tekst jawny. Jeśli jednak pożądana jest poufność, to tekst jawny zostanie zaszyfrowany, a następnie znacznik zostanie obliczony na podstawie szyfru. Bob najpierw zweryfikuje poprawność znacznika. Jeśli znacznik jest poprawny, Bob odszyfrowałby wówczas tekst szyfrujący. Proces ten jest często określany jako _szyfruj-potem-MAC_ (bardziej szczegółowe omówienie tego tematu znajduje się w punkcie 5.5.3).

Aby MAC został uznany za bezpieczny, przeciwnik nie powinien mieć możliwości obliczenia prawidłowego znacznika dla żadnej wiadomości, dla której nie widział jeszcze prawidłowego znacznika. Załóżmy, że bezpieczny MAC jest wykorzystywany przez Alicję i Boba (i załóżmy, że przeciwnik nie zna tajnego klucza, którego używają). Wtedy, jeśli Bob otrzyma wiadomość i ważny znacznik, może być pewien, że Alicja utworzyła znacznik na danej wiadomości (pod warunkiem, że Bob nie utworzył go sam) i że ani wiadomość, ani znacznik nie zostały zmienione przez przeciwnika. Podobny wniosek może wyciągnąć Bob, gdy otrzyma wiadomość od Alicji wraz z poprawnym znacznikiem.

1.2.2. Schematy podpisów

W systemach klucza publicznego schemat podpisu zapewnia podobną funkcjonalność co MAC. W schemacie podpisu klucz prywatny określa _algorytm podpisywania_, którego Alicja może użyć do podpisania wiadomości. Podobnie jak w przypadku MAC, algorytm podpisywania zwraca wynik, który w tym przypadku nazywany jest _podpisem_, zależny od podpisywanej wiadomości i klucza. Podpis jest następnie dołączany do wiadomości. Zauważmy, że algorytm podpisywania jest znany tylko Alicji. Z drugiej strony, istnieje _algorytm weryfikacyjny_, który jest kluczem publicznym (znanym wszystkim). Algorytm weryfikacyjny przyjmuje na wejściu wiadomość i podpis, a na wyjściu wskazuje wartość _true_ lub _false_, zależnie od tego, czy podpis ma być zaakceptowany jako ważny, czy nie. Jedną z ładnych cech schematu podpisu jest to, że każdy może zweryfikować podpisy Alicji na wiadomościach, pod warunkiem, że ma autentyczną kopię klucza weryfikacyjnego Alicji. Natomiast w ustawieniu MAC tylko Bob może weryfikować znaczniki utworzone przez Alicję (gdy Alicja i Bob mają wspólny tajny klucz). Schematy podpisów są analizowane w rozdziale 8.

Wymogi bezpieczeństwa dotyczące schematów podpisu są podobne do tych dla MAC-ów. Przeciwnik nie powinien mieć możliwości złożenia ważnego podpisu na żadnej wiadomości, która nie została wcześniej podpisana przez Alicję. Dlatego też, jeżeli Bob (lub ktokolwiek inny) otrzyma wiadomość i ważny znacznik (tzn. taki, który może być zweryfikowany przy użyciu algorytmu publicznej weryfikacji Alicji), odbiorca może być pewien, że podpis został utworzony przez Alicję i ani wiadomość, ani podpis nie zostały zmodyfikowane przez przeciwnika.

Jednym z powszechnych zastosowań podpisów jest ułatwianie bezpiecznych aktualizacji oprogramowania. Gdy użytkownik kupuje oprogramowanie na stronie internetowej, zazwyczaj zawiera ono algorytm weryfikacji schematu podpisu. Później, gdy pobierana jest zaktualizowana wersja oprogramowania, zawiera ona podpis (na zaktualizowanym oprogramowaniu). Podpis ten można zweryfikować za pomocą algorytmu weryfikacyjnego, który został pobrany podczas zakupu oryginalnej wersji oprogramowania. Dzięki temu komputer użytkownika może zweryfikować, czy aktualizacja pochodzi z tego samego źródła co oryginalna wersja programu.

Systemy podpisu mogą być łączone z systemami szyfrowania klucza publicznego w celu zapewnienia poufności wraz z gwarancjami integralności systemu podpisu. Załóżmy, że Alicja chce wysłać podpisaną, zaszyfrowaną (krótką) wiadomość do Boba. W tej sytuacji najpowszechniej stosowaną techniką jest dla Alicji najpierw utworzenie podpisu na zwykłym tekście przy użyciu jej prywatnego algorytmu podpisywania, a następnie zaszyfrowanie zwykłego tekstu i podpisu przy użyciu publicznego klucza szyfrującego Boba. Gdy Bob otrzymuje wiadomość, najpierw ją odszyfrowuje, a następnie sprawdza ważność podpisu. Proces ten nazywa się _podpisz-potem-szyfruj_ (_sign-then-encrypt_). Należy pamiętać, że jest to w pewnym sensie odwrotna część procedury „szyfruj-potem-MAC” (_encrypt-then-MAC_), która jest używana w systemach klucza tajnego.

1.2.3. Niezaprzeczalność

Istnieje subtelna różnica między MAC a schematami podpisów. W schemacie podpisu algorytm weryfikacji jest jawny. Oznacza to, że podpis może być zweryfikowany przez każdego. Jeśli więc Bob otrzyma od Alicji wiadomość zawierającą jej ważny podpis, może on pokazać wiadomość i podpis każdemu i mieć pewność, że osoba trzecia również zaakceptuje podpis jako ważny. W związku z tym Alicja nie może podpisać wiadomości, a następnie próbować twierdzić, że nie podpisała wiadomości, co jest właściwością określaną mianem _niezaprzeczalności_. Jest to przydatne przy zawieraniu umów, w których nie chcemy, aby ktoś mógł odmówić wykonania podpisanej umowy, twierdząc (nieprawdziwie), że jego podpis został „sfałszowany”.

Jednak w przypadku MAC nie ma możliwości weryfikacji przez osoby trzecie, ponieważ tajny klucz jest wymagany do weryfikacji poprawności znacznika, a klucz jest znany tylko Alicji i Bobowi. Nawet jeśli tajny klucz zostanie ujawniony stronie trzeciej (np. w wyniku nakazu sądowego), nie ma możliwości ustalenia, czy znacznik został utworzony przez Alicję, czy przez Boba, ponieważ wszystko, co może zrobić Bob, może zrobić również Alicja i na odwrót. Tak więc MAC nie zapewnia niezaprzeczalności i z tego powodu MAC jest czasami określany jako „zaprzeczalny”. Interesujące jest jednak to, że istnieją sytuacje, w których zaprzeczenie jest pożądane. Może to mieć miejsce w przypadku komunikacji w czasie rzeczywistym, gdzie Alicja i Bob chcą mieć pewność co do autentyczności ich komunikacji w trakcie jej trwania, ale nie chcą, aby istniał trwały, możliwy do sprawdzenia zapis tej komunikacji. Taka komunikacja jest analogiczna do rozmowy „poza protokołem”, np. między dziennikarzem a anonimowym źródłem. MAC jest przydatny w kontekście tego typu rozmów, zwłaszcza jeśli po ich zakończeniu zadbamy o skasowanie tajnych kluczy, które były używane podczas komunikacji.

1.2.4. Certyfikaty

Wspomnieliśmy, że ważne jest sprawdzanie autentyczności kluczy publicznych, zanim zostaną one użyte. _Certyfikat_ jest wspólnym narzędziem, które pomaga w osiągnięciu tego celu. Certyfikat będzie zawierał informacje o konkretnym użytkowniku lub, co bardziej powszechne, o stronie internetowej, w tym o jej kluczach publicznych. Te klucze publiczne będą podpisywane przez zaufany organ. Zakłada się, że każdy ma publiczny klucz weryfikacyjny zaufanego organu, dzięki czemu każdy może zweryfikować podpis zaufanego organu na certyfikacie. Więcej informacji na temat certyfikatów znajduje się w podrozdziale 8.6.

Technika ta jest stosowana w Internecie w protokole _bezpieczeństwa warstwy transportu_ (_Transport Layer Security_), powszechnie nazywanym TLS. Gdy użytkownik łączy się z bezpieczną stroną internetową, na przykład należącą do firmy zajmującej się handlem elektronicznym, strona internetowa firmy prześle użytkownikowi certyfikat, aby mógł on zweryfikować autentyczność kluczy publicznych strony. Te klucze publiczne będą następnie wykorzystywane do ustanowienia bezpiecznego kanału między użytkownikiem a stroną internetową, w którym wszystkie informacje są szyfrowane. Należy zauważyć, że klucz publiczny zaufanego organu, który jest używany do weryfikacji klucza publicznego strony internetowej, jest zazwyczaj zakodowany w przeglądarce internetowej.

1.2.5. Funkcje skrótu

Systemy podpisywania są zwykle znacznie mniej wydajne niż MAC. Dlatego też nie jest wskazane, aby używać schematu podpisu do podpisywania „długich” wiadomości. (Właściwie większość schematów podpisu jest zaprojektowana do podpisywania tylko krótkich wiadomości o stałej długości). W praktyce wiadomości są „mieszane” przed ich podpisaniem. _Kryptograficzna funkcja skrótu_ jest używana do kompresji wiadomości o dowolnej długości na krótki, losowo wyglądający skrót o stałej długości (_message digest_). Zauważmy, że funkcja skrótu jest funkcją publiczną i zakłada się, że jest znana wszystkim. Co więcej, funkcja skrótu nie ma żadnego klucza. Funkcje skrótu są omówione w rozdziale 5.

Po tym, jak Alicja zmiesza wiadomość, podpisuje jej skrót, używając swojego prywatnego algorytmu podpisywania. Oryginalna wiadomość, wraz z podpisem, jest następnie przekazywana powiedzmy do Boba. Proces ten nazywany jest _skróć-potem-podpisz_ (_hash-then-sign_). W celu weryfikacji podpisu Bob oblicza skrót wiadomości przez zastosowanie funkcji skrótu. Następnie używa publicznego algorytmu weryfikacji do sprawdzenia ważności podpisu na skrócie wiadomości. Gdy podpis jest używany wraz z szyfrowaniem klucza publicznego, proces ten jest nazywany _skróć-potem-podpisz-potem-szyfruj_ (_hash-then-sign-then-encrypt_). Oznacza to, że wiadomość jest mieszana, skrót wiadomości jest następnie podpisywany, a na koniec wiadomość i podpis są szyfrowane.

Kryptograficzna funkcja skrótu bardzo się różni od funkcji skrótu, która jest używana na przykład do konstruowania tabeli skrótów. W kontekście tabel skrótu, funkcja skrótu jest zazwyczaj wymagana tylko do uzyskania kolizji z wystarczająco małym prawdopodobieństwem. Z drugiej strony, jeżeli używana jest kryptograficzna funkcja skrótu, powinno być obliczeniowo niemożliwe znalezienie kolizji, choć muszą one istnieć. Kryptograficzne funkcje skrótu są zazwyczaj wymagane w celu spełnienia dodatkowych właściwości bezpieczeństwa, jak to omówiono w podrozdziale 5.2.

Kryptograficzne funkcje skrótu mają również inne zastosowania, na przykład do _wyprowadzania kluczy_ (_key derivation_). W przypadku gdy funkcja skrótu zostanie użyta do wyprowadzenia klucza, będzie stosowana do długiego ciągu losowego w celu utworzenia krótkiego klucza losowego.

Na koniec należy podkreślić, że funkcje skrótu nie mogą być wykorzystywane do szyfrowania z dwóch podstawowych powodów. Pierwszym z nich jest fakt, że funkcje skrótu nie mają klucza. Drugim jest to, że funkcje skrótu nie mogą być odwracane (nie są to funkcje różnowartościowe), więc nie można „odszyfrować” skrótu wiadomości, aby uzyskać jednoznaczny tekst jawny.

1.3. Protokoły kryptograficzne

Narzędzia kryptograficzne, takie jak kryptosystemy, schematy podpisów, funkcje skrótu itp., mogą być wykorzystywane samodzielnie w celu osiągnięcia określonych celów bezpieczeństwa. Narzędzia te są jednak również używane jako komponenty w bardziej skomplikowanych protokołach. (Oczywiście protokoły mogą być również projektowane „od zera”, bez korzystania z wcześniejszych wersji pierwotnych).

Ogólnie rzecz biorąc, _protokół_ (lub _protokół interaktywny_) odnosi się do określonej sekwencji komunikatów wymienianych między dwiema (lub ewentualnie więcej) stronami. _Sesja_ protokołu, powiedzmy między Alicją a Bobem, będzie się składać z jednego lub więcej _przepływów_, gdzie każdy przepływ składa się z wiadomości wysłanej od Alicji do Boba lub odwrotnie. Pod koniec sesji zaangażowane strony mogą ustalić pewną wspólną informację lub potwierdzić posiadanie pewnych współdzielonych wcześniej informacji.

Jednym z ważnych typów protokołów jest _schemat identyfikacji_, w którym jedna strona „udowadnia” swoją tożsamość drugiej stronie, na przykład przez wykazanie posiadania hasła. Bardziej zaawansowane protokoły identyfikacyjne będą zamiast tego składać się z dwóch (lub więcej) przepływów, na przykład wyzwanie, po którym następuje odpowiedź, przy czym odpowiedź jest obliczana z wyzwania przy użyciu pewnego tajnego lub prywatnego klucza. Schematy identyfikacji są tematem rozdziału 10.

Istnieje wiele rodzajów protokołów związanych z różnymi aspektami wyboru kluczy lub przekazywania kluczy od jednej strony do drugiej. W _schemacie dystrybucji kluczy_ klucze mogą być wybierane przez podmiot zaufany i przekazywane jednemu lub kilku członkom danej sieci. Inne podejście, które nie wymaga udziału aktywnego, zaufanego organu, nazywane jest _uzgadnianiem klucza_. W systemie uzgadniania klucza Alicja i Bob (powiedzmy) są w stanie ostatecznie ustalić wspólny, tajny klucz, który nie powinien być znany przeciwnikowi. Te i związane z nimi tematy są omówione w rozdziałach 11 i 12.

_Schemat dzielenia się tajną informacją_ polega na tym, że zaufany organ rozprowadza „części” informacji (zwane „udziałami”) w taki sposób, że niektóre podzbiory udziałów mogą być odpowiednio łączone w celu odtworzenia pewnej wcześniej określonej tajemnicy. Jednym z powszechnych rodzajów schematu tajnego udostępniania informacji jest _schemat progowy_. W schemacie (_k_, _n_)-progowym występuje _n_ udziałów, a każde _k_ udziałów pozwala na odtworzenie tajemnicy. Z drugiej strony, _k_ – 1 lub mniej udziałów nie daje żadnej informacji o wartości tajemnicy. Schematy tajnego udostępniania są analizowane w rozdziale 11.

1.4. Bezpieczeństwo

Podstawowym celem kryptosystemu, schematu podpisu itp. jest jego „bezpieczeństwo”. Ale co to znaczy być bezpiecznym i jak możemy zyskać pewność, że coś jest rzeczywiście bezpieczne? Prawdę mówiąc, chcielibyśmy powiedzieć, że przeciwnik nie może na przykład „złamać” kryptosystemu, ale musimy sprecyzować to pojęcie. Bezpieczeństwo w kryptografii wymaga uwzględnienia trzech różnych aspektów: _modelu ataku_, _celu przeciwnika_ i _poziomu bezpieczeństwa_. Omówmy każdy z nich po kolei.

Model ataku określa informacje, które są dostępne dla przeciwnika. Zawsze zakładamy, że przeciwnik zna schemat lub protokół, który jest używany (nazywa się to _zasadą Kerckhoffa_). Zakłada się również, że przeciwnik zna klucz publiczny (jeśli system jest systemem klucza publicznego). Z drugiej strony, zakłada się, że przeciwnik nie zna używanego tajnego lub prywatnego klucza. Ewentualne dodatkowe informacje przekazywane przeciwnikowi powinny być określone w modelu ataku.

Cel przeciwnika określa dokładnie, co to znaczy „złamać” kryptosystem. Co przeciwnik próbuje zrobić i jakie informacje próbuje określić? Zatem cel przeciwnika definiuje „udany atak”.

Poziom bezpieczeństwa próbuje oszacować wysiłek wymagany do złamania kryptosystemu. Inaczej mówiąc, do jakich zasobów obliczeniowych przeciwnik ma dostęp i ile czasu zajęłoby przeprowadzenie ataku z wykorzystaniem tych zasobów?

Oświadczenie o bezpieczeństwie dla schematu kryptograficznego będzie stwierdzeniem, że przy określonych zasobach obliczeniowych nie można osiągnąć konkretnego celu przeciwnika w określonym modelu ataku.

Ilustrujemy teraz niektóre z powyższych koncepcji w odniesieniu do kryptosystemu. Istnieją cztery powszechnie uznawane modele ataków. W _ataku ze znanym szyfrogramem_ przeciwnik ma dostęp do pewnej ilości szyfrogramów, które są tym samym nieznanym kluczem. W _ataku ze znanym jawnym tekstem_ przeciwnik uzyskuje dostęp do pewnej ilości tekstu jawnego, a także do odpowiadającego mu szyfru (wszystkie są zaszyfrowane tym samym kluczem). W _ataku z wybranym tekstem jawnym_ przeciwnik ma możliwość wybrania tekstu jawnego, a następnie otrzymuje odpowiadający mu szyfrogram. W końcu, w _ataku z wybranym szyfrogramem_ przeciwnik wybiera jakiś szyfrogram, a następnie otrzymuje odpowiadający mu tekst jawny.

Zdecydowanie to atak z wybranym tekstem jawnym lub wybranym szyfrogramem dostarcza przeciwnikowi więcej informacji niż atak ze znanym szyfrogramem. Dlatego są one uważane za silniejsze modele ataku niż atak ze znanym szyfrogramem, ponieważ potencjalnie ułatwiają pracę przeciwnikowi.

Następnym aspektem, który należy zbadać, jest cel przeciwnika. Przy _całkowitym złamaniu_ kryptosystemu przeciwnik określa klucz prywatny (lub tajny). Istnieją jednak inne, słabsze cele, które przeciwnik mógłby potencjalnie osiągnąć, nawet jeśli całkowite złamanie nie jest możliwe. Na przykład przeciwnik może być w stanie odszyfrować nieznany mu wcześniej szyfrogram z określonym niezerowym prawdopodobieństwem, nawet jeśli nie był w stanie określić klucza. Albo przeciwnik może być w stanie określić pewne częściowe informacje o tekście jawnym z pewnym określonym niezerowym prawdopodobieństwem. „Informacje częściowe” mogą zawierać wartości niektórych bitów tekstu jawnego. W końcu, jako przykład słabego celu, przeciwnik może być w stanie rozróżnić szyfrogramy dwóch podanych tekstów jawnych.

Inne podstawowe elementy kryptograficzne będą miały różne modele ataku i cele przeciwnika. W schemacie podpisu model ataku określałby, do jakiego rodzaju (ważnych) podpisów przeciwnik ma dostęp. Być może przeciwnik widzi tylko niektóre z wcześniej podpisanych wiadomości, a może poprosić sygnatariusza o podpisanie kilku konkretnych wiadomości, które wybrał. Celem przeciwnika jest zazwyczaj podpisanie jakiejś „nowej” wiadomości (tzn. takiej, dla której przeciwnik nie zna już ważnego podpisu). Być może przeciwnik może znaleźć ważny podpis jakiejś konkretnej wiadomości, którą wybierze, lub może znajdzie ważny podpis dla dowolnej wiadomości. Stanowiłyby one odpowiednio słabe i silne cele przeciwnika.

Często badane są trzy poziomy bezpieczeństwa, które nazywane są _bezpieczeństwem obliczeniowym_, _bezpieczeństwem możliwym do udowodnienia_ i _bezpieczeństwem bezwarunkowym_.

Bezpieczeństwo obliczeniowe oznacza, że określony algorytm łamania systemu jest niewykonalny obliczeniowo, tzn. nie może być wykonany w rozsądnym czasie przy użyciu aktualnie dostępnych zasobów obliczeniowych. Oczywiście system, który jest dziś bezpieczny obliczeniowo, może nie być bezpieczny obliczeniowo w nieskończoność. Na przykład mogą zostać odkryte nowe algorytmy, komputery mogą stać się szybsze, a podstawowe nowe paradygmaty obliczeniowe, takie jak obliczenia kwantowe, mogą stać się wykonalne. Obliczenia kwantowe, jeśli staną się dostępne w praktyce, mogą mieć ogromny wpływ na bezpieczeństwo wielu rodzajów kryptografii klucza publicznego. Kwestia ta jest omawiana bardziej szczegółowo w podrozdziale 9.1.

W rzeczywistości bardzo trudno jest przewidzieć, jak długo coś, co dziś uznawane jest za bezpieczne, pozostanie bezpieczne. Istnieje wiele przykładów, w których wiele schematów kryptograficznych nie przetrwało tak długo, jak pierwotnie oczekiwano, ze względu na wspomniane wyżej powody. Doprowadziło to do dość częstych przypadków zastępowania standardów przez ulepszone standardy. Na przykład dla funkcji skrótu pojawiła się seria proponowanych i/lub zatwierdzonych standardów, oznaczonych jako SHA-0, SHA-1, SHA-2 i SHA-3, ponieważ znaleziono nowe ataki i stare standardy stały się niepewne.

Ciekawym przykładem dotyczącym błędnych prognoz jest _kryptosystem RSA_ z kluczem publicznym. W wydaniu _Scientific American_ z sierpnia 1977 roku wybitny badacz matematyczny Martin Gardner napisał artykuł na temat nowo opracowanego kryptosystemu RSA z kluczem publicznym, zatytułowany „Nowy rodzaj szyfru, którego złamanie zajęłoby miliony lat”. W artykule znalazł się szyfrogram stanowiący wyzwanie – tekst zaszyfrowany przy użyciu klucza 512-bitowego. Wyzwanie to zostało jednak rozwiązane 17 lat później, 26 kwietnia 1994 roku, przez rozkład podanego klucza publicznego na czynniki (tekst jawny brzmiał: „the magic words are squeamish ossifrage”, czyli „magiczne słowa to piskliwy rybołów”). Stwierdzenie, że złamanie szyfru zajmie miliony lat, odnosiło się prawdopodobnie do tego, ile czasu zajmie uruchomienie najlepszego algorytmu rozkładu znanego w 1977 roku na najszybszym dostępnym komputerze. Jednak między rokiem 1977 a 1994 nastąpiło kilka zmian, w tym następujące:

• komputery stały się o wiele szybsze,

• znaleziono ulepszone algorytmy oraz

• rozwój Internetu ułatwił prowadzenie rozproszonych obliczeń na dużą skalę.

Oczywiście w zasadzie nie da się przewidzieć, kiedy zostaną odkryte nowe algorytmy. Również trzeci z wymienionych powyżej punktów może być uważany za „zmianę paradygmatu”, o którym prawdopodobnie nikt nawet nie myślał w 1977 roku.

Kolejnym „poziomem” bezpieczeństwa, którym się zajmujemy, jest bezpieczeństwo dające się udowodnić (zwane również _bezpieczeństwem redukcjonistycznym_) odnoszące się do sytuacji, w której złamanie kryptosystemu (tj. osiągnięcie celu przez przeciwnika) może zostać zredukowane w sensie teoretycznej złożoności do rozwiązania jakiegoś podstawowego (z założenia trudnego) problemu matematycznego. Pokazałoby to, że złamanie kryptosystemu jest co najmniej tak samo trudne jak rozwiązanie danego trudnego problemu. Bezpieczeństwo możliwe do udowodnienia często wiąże się z ograniczeniem problemu rozkładu na czynniki lub problemu logarytmów dyskretnych (problemy te zostały omówione odpowiednio w podrozdziałach 6.6 i 7.2).

Wreszcie, bezwarunkowe bezpieczeństwo oznacza, że kryptosystemu nie da się złamać (tzn. cel przeciwnika nie jest osiągalny) nawet przy nieograniczonych zasobach obliczeniowych, ponieważ przeciwnik nie ma wystarczającej ilości dostępnych informacji (jak określono w modelu ataku), aby mógł to zrobić. Najsłynniejszym przykładem bezwarunkowo bezpiecznego kryptosystemu jest _szyfr z kluczem jednorazowym_ (_one-time pad_). W tym kryptosystemie kluczem jest losowy ciąg bitów o tej samej długości co tekst jawny. Szyfr jest tworzony jako alternatywa wykluczająca (XOR) tekstu jawnego i klucza. W przypadku _one-time pad_ można matematycznie udowodnić, że przeciwnik nie może uzyskać żadnych częściowych informacji o tekście jawnym (poza jego długością), biorąc pod uwagę tekst jawny, pod warunkiem, że klucz jest używany do szyfrowania tylko jednego ciągu tekstu jawnego i ma taką samą długość jak tekst jawny. _Szyfr z kluczem jednorazowym_ jest omówiony w rozdziale 3.

Celem naszej analizy schematu kryptograficznego jest wykazanie, że przeciwnik nie może osiągnąć _słabego_ celu w _silnym_ modelu ataku, biorąc pod uwagę _znaczne_ zasoby obliczeniowe.

Wcześniejsza dyskusja na temat bezpieczeństwa dotyczyła głównie sytuacji kryptograficznego elementu pierwotnego, jakim jest kryptosystem. Kryptograficzne elementy pierwotne są jednak na ogół łączone w skomplikowany sposób podczas definiowania i ostatecznego wdrażania protokołów. Nawet pozornie proste decyzje implementacyjne mogą prowadzić do nieoczekiwanych luk w zabezpieczeniach. Na przykład, gdy dane są szyfrowane przy użyciu szyfru blokowego, najpierw należy je podzielić na kawałki o stałej długości, np. bloki 128-bitowe. Jeśli dane nie wypełniają dokładnie całkowitej liczby bloków, należy wprowadzić pewne wypełnienia. Okazuje się, że standardowa technika uzupełniania, stosowana w popularnym trybie pracy CBC, jest podatna na atak znany jako _atak wyroczni dopełnienia_ (_padding oracle attack_), który został odkryty przez Vaudenaya w 2002 roku (opis tego ataku znajduje się w punkcie 4.7.1).

Istnieją również różne rodzaje ataków na fizyczne implementacje kryptografii, które są znane jako ataki _bocznym kanałem_ (_side channel attacks_). Przykładem mogą być _ataki czasowe_ (_timing attacs_), _ataki analizy błędów_ (_fault analysis attacks_), _ataki z analizą zużycia mocy_ (_power analysis attacks_) oraz ataki typu _cache_. Chodzi o to, że informacja o tajnym lub prywatnym kluczu może wyciec przez obserwację lub fizyczną manipulację urządzeniem (np. kartą inteligentną), na którym zaimplementowano konkretny schemat kryptograficzny. Jednym z przykładów może być obserwowanie czasu, jaki zajmuje urządzeniu wykonanie pewnych obliczeń (tzw. atak czasowy). Ten wyciek informacji może nastąpić nawet wtedy, gdy schemat jest „bezpieczny”.

1.5. Uwagi i źródła

Istnieje wiele monografii i podręczników na temat kryptografii. Wymienimy tu kilka ogólnych pozycji, które mogą być przydatne dla czytelników.

W celu uzyskania dostępnego, niematematycznego podejścia, polecamy:

• _Everyday Cryptography: Fundamental Principles and Applications_, wyd. 2, K. Martin .

Dla bardziej matematycznego punktu widzenia pomocne są następujące najnowsze teksty:

• _An Introduction to Mathematical Cryptography_, J. Hoffstein, J. Pipher, J. Silverman .

• _Introduction to Modern Cryptography_, wyd. 2, J. Katz, Y. Lindell .

• _Understanding Cryptography: A Textbook for Students and Practitioners_, C. Paar, J. Pelzl .

• _Cryptography Made Simple_, Nigel Smart .

• _A Classical Introduction to Cryptography: Applications for Communications Security_, S. Vaudenay .

Jeśli chodzi o podstawy matematyczne, zwłaszcza w kryptografii klucza publicznego, polecamy

• _Mathematics of Public Key Cryptography_, S. Galbraith .

Na koniec warto wspomnieć o poniższej pozycji, mimo że jest dość nieaktualna:

• _Handbook of Applied Cryptography_, A.J. Menezes, P.C. Van Oorschot i S.A. Vanstone .PRZYPISY

Kolizja dla funkcji _h_ zachodzi wtedy, gdy _h_(_x_) = _h_(_y_) dla jakiegoś _x_ ≠ _y_.

Inną kwestią jest oczywiście to, czy tego rodzaju ograniczone informacje mogą być wykorzystane przez przeciwnika w złośliwy sposób, czy też nie.

Inna nazwa tej funkcji to tocjent (przyp. tłum.).

P. Mayle, _A Year in Provence_, A. Knopf, Inc., 1989 (_Rok w Prowansji_, Prószyński, Warszawa 2010).

_Symbol Newtona_ = _n_!/(_k_!(_n_ – _k_)!) wyznacza liczbę sposobów wybrania podzbioru _k_ obiektów ze zbioru _n_ obiektów.