"Kryptografia. W teorii i praktyce"

Spis treści

Wstęp 12

1. Wprowadzenie do kryptografii 14

1.1 Kryptosystemy i podstawowe narzędzia kryptograficzne 14

1.1.1 Kryptosystemy z kluczem tajnym 14

1.1.2 Kryptosystemy klucza publicznego 15

1.1.3 Szyfry blokowe i strumieniowe 16

1.1.4 Kryptografia hybrydowa 16

1.2 Integralność wiadomości 17

1.2.1 Kody uwierzytelniania wiadomości 18

1.2.2 Schematy podpisów 19

1.2.3 Niezaprzeczalność 20

1.2.4 Certyfikaty 20

1.2.5 Funkcje skrótu 21

1.3 Protokoły kryptograficzne 22

1.4 Bezpieczeństwo 23

1.5 Uwagi i źródła 26

2. Klasyczna kryptografia 27

2.1 Wprowadzenie: niektóre proste kryptosystemy 27

2.1.1 Szyfr przestawieniowy 29

2.1.2 Szyfr podstawieniowy 32

2.1.3 Szyfr afiniczny 33

2.1.4 Szyfr Vigenere’a 38

2.1.5 Szyfr Hilla 39

2.1.6 Szyfr permutacyjny 44

2.1.7 Szyfry strumieniowe 46

2.2 Kryptoanaliza 50

2.2.1 Kryptoanaliza szyfru afinicznego 52

2.2.2 Kryptoanaliza szyfru podstawieniowego 53

2.2.3 Kryptoanaliza szyfru Vigenere’a 56

2.2.4 Kryptoanaliza szyfru Hilla 60

2.2.5 Kryptoanaliza szyfru strumieniowego z LFSR 61

2.3 Uwagi i źródła 62

Ćwiczenia 63

3. Teoria Shannona, tajność doskonała i szyfr z kluczem jednorazowym 70

3.1 Wprowadzenie 70

3.2 Podstawowa teoria prawdopodobieństwa 71

3.3 Tajność doskonała 74

3.4 Entropia 79

3.4.1 Cechy entropii 81

3.5 Fałszywe klucze i długość krytyczna 84

3.6 Uwagi i źródła 88

Ćwiczenia 89

4. Szyfry blokowe i szyfry strumieniowe 92

4.1 Wprowadzenie 92

4.2 Sieci podstawieniowo-permutacyjne 93

4.3 Kryptoanaliza liniowa 98

4.3.1 Lemat nawarstwiania 98

4.3.2 Liniowe aproksymacje S-boksów 100

4.3.3 Liniowy atak na SPN 103

4.4 Kryptoanaliza różnicowa 107

4.5 Data Encryption Standard 114

4.5.1 Opis DES 114

4.5.2 Analiza DES 116

4.6 Advanced Encryption Standard 118

4.6.1 Opis AES 119

4.6.2 Analiza AES 124

4.7 Tryby działania 125

4.7.1 Atak wyroczni dopełnienia w trybie CBC 129

4.8 Szyfry strumieniowe 131

4.8.1 Atak korelacyjny na generator kombinacji 132

4.8.2 Atak algebraiczny na generator filtrów 135

4.8.3 Trivium 138

4.9 Uwagi i źródła 139

Ćwiczenia 140

5. Funkcje skrótu i uwierzytelnianie wiadomości 145

5.1 Funkcje skrótu i integralność danych 145

5.2 Bezpieczeństwo funkcji skrótu 147

5.2.1 Model losowej wyroczni 149

5.2.2 Algorytmy w modelu losowej wyroczni 150

5.2.3 Porównanie kryteriów bezpieczeństwa 154

5.3 Iterowane funkcje skrótu 157

5.3.1 Konstrukcja Merkle’a-Damgarda 159

5.3.2 Kilka przykładów iterowanych funkcji skrótów 164

5.4 Konstrukcja gąbki 165

5.4.1 SHA-3 168

5.5 Kody uwierzytelniania wiadomości 169

5.5.1 Zagnieżdżone kody MAC i HMAC 171

5.5.2 CBC-MAC 174

5.5.3 Szyfrowanie uwierzytelnione 175

5.6 Bezwarunkowo bezpieczne kody MAC 178

5.6.1 Silnie uniwersalne rodziny skrótów 181

5.6.2 Optymalność prawdopodobieństwa oszustwa 183

5.7 Uwagi i źródła 185

Ćwiczenia 186

6. Kryptosystem RSA i rozkład liczb całkowitych na czynniki 194

6.1 Wprowadzenie do kryptografii klucza publicznego 194

6.2 Więcej teorii liczb 197

6.2.1 Algorytm Euklidesa 197

6.2.2 Chińskie twierdzenie o resztach 201

6.2.3 Inne przydatne fakty 203

6.3 Kryptosystem RSA 205

6.3.1 Implementowanie RSA 207

6.4 Testowanie pierwszości 210

6.4.1 Symbole Legendre’a i Jacobiego 212

6.4.2 Algorytm Solovaya-Strassena 215

6.4.3 Algorytm Millera-Rabina 218

6.5 Pierwiastki kwadratowe modulo n 220

6.6 Algorytmy rozkładu na czynniki 221

6.6.1 Algorytm Pollardap - 1 222

6.6.2 Algorytm rho Pollarda 223

6.6.3 Algorytm losowych kwadratów Dixona 226

6.6.4 Algorytmy rozkładu na czynniki w praktyce 231

6.7 Inne ataki na RSA 232

6.7.1 Obliczanie ^(n) 233

6.7.2 Wykładnik odszyfrowywania 233

6.7.3 Atak Wienera z małym wykładnikiem odszyfrowywania 238

6.8 Kryptosystem Rabina 242

6.8.1 Bezpieczeństwo kryptosystemu Rabina 244

6.9 Bezpieczeństwo semantyczne RSA 246

6.9.1 Częściowe informacje dotyczące bitów tekstu jawnego 247

6.9.2 Uzyskanie bezpieczeństwa semantycznego 249

6.10 Uwagi i źródła 254

Ćwiczenia 255

7. Kryptografia klucza publicznego i logarytmy dyskretne 264

7.1 Wprowadzenie 264

7.1.1 Kryptosystem ElGamala 265

7.2 Algorytmy dla problemu logarytmu dyskretnego 267

7.2.1 Algorytm Shanksa 267

7.2.2 Algorytm logarytmu dyskretnego rho Pollarda 269

7.2.3 Algorytm Pohliga-Hellmana 272

7.2.4 Metoda rachunku indeksowego 275

7.3 Dolne granice złożoności algorytmów genetycznych 277

7.4 Ciała skończone 281

7.4.1 Analiza indeksu Jouxa dla ciał o niewielkich wyróżnikach 285

7.5 Krzywe eliptyczne 287

7.5.1 Krzywe eliptyczne na liczbach rzeczywistych 287

7.5.2 Krzywe eliptyczne modulo liczba pierwsza 290

7.5.3 Krzywe eliptyczne na ciałach skończonych 293

7.5.4 Własności krzywych eliptycznych 294

7.5.5 Parowanie krzywych eliptycznych 295

7.5.6 Kryptosystem ElGamala na krzywych eliptycznych 298

7.5.7 Obliczanie wielokrotności punktów na krzywych eliptycznych 300

7.6 Algorytmy logarytmu dyskretnego w praktyce 303

7.7 Bezpieczeństwo systemów ElGamala 304

7.7.1 Bitowe bezpieczeństwo logarytmów dyskretnych 304

7.7.2 Semantyczne bezpieczeństwo systemów ElGamala 308

7.7.3 Problemy Diffiego-Hellmana 308

7.8 Uwagi i źródła 310

Ćwiczenia 311

8. Schematy podpisów 317

8.1 Wprowadzenie 317

8.1.1 Schemat podpisu RSA 318

8.2 Wymogi bezpieczeństwa dla schematów podpisu 320

8.2.1 Podpisy i funkcje skrótu 321

8.3 Schemat podpisu ElGamala 322

8.3.1 Bezpieczeństwo schematu podpisu ElGamala 325

8.4 Warianty schematu podpisu ElGamala 328

8.4.1 Schemat podpisu Schnorra 328

8.4.2 Algorytm podpisu cyfrowego 330

8.4.3 DSA krzywej eliptycznej 332

8.5 Funkcja skrótu o pełnej dziedzinie 334

8.6 Certyfikaty 338

8.7 Podpisywanie i szyfrowanie 339

8.8 Uwagi i źródła 341

Ćwiczenia 342

9. Kryptografia postkwantowa 347

9.1 Wprowadzenie 347

9.2 Kryptografia oparta na kratach 350

9.2.1 NTRU 350

9.2.2 Kraty i bezpieczeństwo NTRU 354

9.2.3 LWE 357

9.3 Kryptografia oparta na kodzie i kryptosystem McEliece’a 359

9.4 Kryptografia wielu zmiennych 364

9.4.1 Równania ciała ukrytego 365

9.4.2 Schemat podpisu oliwa i ocet 369

9.5 Schematy podpisu oparte na skrócie 373

9.5.1 Schemat podpisu Lamporta 373

9.5.2 Schemat podpisu Winternitza 375

9.5.3 Schemat podpisu Merkle’a 378

9.6 Uwagi i źródła 380

10. Schematy identyfikacji i uwierzytelnianie jednostki 383

10.1 Wprowadzenie 383

10.1.1 Hasła 385

10.1.2 Bezpieczne schematy identyfikacji 387

10.2 Wyzwanie i odpowiedź w kryptografii klucza tajnego 388

10.2.1 Model ataku i cele przeciwnika 393

10.2.2 Wzajemne uwierzytelnianie 395

10.3 Wyzwanie i odpowiedź dla kryptografii klucza publicznego 398

10.3.1 Schematy identyfikacji klucza publicznego 398

10.4 Schemat identyfikacji Schnorra 401

10.4.1 Bezpieczeństwo schematu identyfikacji Schnorra 404

10.5 Schemat identyfikacji Feige’a-Fiata-Shamira 410

Ćwiczenia 415

10.6 Uwagi i źródła 415

11. Dystrybucja kluczy 419

11.1 Wprowadzenie 419

11.1.1 Modele ataku i cele przeciwników 422

11.2 Wstępna dystrybucja kluczy 423

11.2.1 Wstępna dystrybucja kluczy Diffiego-Hellmana 423

11.2.2 Schemat Bloma 425

11.2.3 Wstępna dystrybucja klucza w sieciach czujnikowych 432

11.3 Schematy dystrybucji klucza sesji 436

11.3.1 Schemat Needhama-Schroedera 436

11.3.2 Atak Denninga-Sacca na schemat NS 437

11.3.3 Kerberos 439

11.3.4 Schemat Bellare’a-Rogawaya 442

11.4 Ponowne tworzenie klucza i logiczna hierarchia kluczy 445

11.5 Schematy progowe 448

11.5.1 Schemat Shamira 449

11.5.2 Uproszczony schemat (t, t)-progowy 452

11.5.3 Wizualne schematy progowe 453

Ćwiczenia 457

11.6 Uwagi i źródła 457

12. Schematy uzgadniania klucza 463

12.1 Wprowadzenie 463

12.1.1 Bezpieczeństwo warstwy transportu (TLS) 463

12.2 Uzgodnienie klucza Diffiego-Hellmana 465

12.2.1 Schemat uzgadniania klucza STS (station-to-station) 467

12.2.2 Bezpieczeństwo STS 468

12.2.3 Ataki ze znanym kluczem sesji 471

12.3 Funkcje wyprowadzania klucza 473

12.4 Schematy MTI uzgadniania klucza 475

12.4.1 Ataki na MTI/A0 ze znanym kluczem sesji 477

12.5 Zaprzeczalne schematy uzgadniania klucza 479

12.6 Aktualizacja kluczy 482

12.7 Konferencyjne schematy uzgadniania klucza 485

Ćwiczenia 488

12.8 Uwagi i źródła 488

13. Różne tematy 491

13.1 Kryptografia oparta na tożsamości 491

13.1.1 Kryptosystem Cocksa oparty na tożsamości 492

13.1.2 Kryptosystem Boneha-Franklina oparty na tożsamości 498

13.2 Kryptosystem Pailliera 503

13.3 Ochrona praw autorskich 506

13.3.1 Odciski palca 507

13.3.2 Identyfikowalna własność nadrzędna 509

13.3.3 Kody 2-IPP 511

13.3.4 Śledzenie nielegalnej redystrybucji kluczy 514

13.4 Bitcoin i technologia blockchain 518

13.5 Uwagi i źródła 522

Ćwiczenia 523

A. Teoria liczb i algebraiczne koncepcje kryptografii 526

A.1 Arytmetyka modularna 526

A.2 Grupy 527

A.2.1 Rzędy elementów grupy 529

A.2.2 Grupy cykliczne i elementy pierwotne 530

A.2.3 Podgrupy i warstwy 531

A.2.4 Izomorfizmy i homomorfizmy grup 532

A.2.5 Reszty kwadratowe 533

A.2.6 Algorytm Euklidesa 534

A.2.7 Iloczyny proste 535

A.3 Pierścienie 536

A.3.1 Chińskie twierdzenie o resztach 537

A.3.2 Ideały i pierścienie ilorazowe 539

A. 4 Ciała 540

B. Pseudolosowe generowanie bitów dla kryptografii 543

B.1 Generatory bitów 543

B.2 Bezpieczeństwo pseudolosowych generatorów bitów 548

B.3 Uwagi i źródła 550

Bibliografia 551

Indeks 561