Kryptografia Yaschenko. Książka: Yashchenko V.V.

Poniżej sumy wyd. V. V. Yashchenko WPROWADZENIE DO KRYPTOGRAFII Autorzy: V. V. Yashchenko (redaktor, rozdział 1), N. P. Varnovsky (rozdziały 2, 3), Yu V. Nesterenko (rozdział 4), G. A Kabatyansky (rozdział 5), P. N. Devyanin, V. G. Proskurin, A. V. Cheremushkin (Rozdział 6), P. A. Gyrdymov, A. Yu Zubov, A. V. Zyazin, V. N Ovchinnikov (Rozdział 7). Książka, po raz pierwszy w języku rosyjskim, przedstawia systematyczną prezentację naukowych podstaw kryptografii od najprostszych przykładów i podstawowych pojęć po współczesne konstrukcje kryptograficzne. Zrozumienie zasad kryptografii stało się dla wielu koniecznością ze względu na powszechne stosowanie narzędzi bezpieczeństwa informacji kryptograficznych. Dlatego książka może być przydatna dla ogólnego czytelnika. Książka przeznaczona jest dla studentów matematyki i specjalistów ds. bezpieczeństwa informacji. Spis treści Przedmowa 5 Rozdział 1. Podstawowe pojęcia kryptografii 7 1. Wprowadzenie 7 2. Przedmiot kryptografii. 8 3. Podstawy matematyczne 15 4. Nowe kierunki 18 5. Wnioski 23 Rozdział 2. Kryptografia i teoria złożoności 25 1. Wprowadzenie 25 2. Kryptografia i przypuszczenie P=/NP 28 3. Funkcje jednokierunkowe 30 4. Generatory pseudolosowe 32 5. Dowody z wiedzą zerową 35 Rozdział 3. Protokoły kryptograficzne 41 1. Wprowadzenie 41 2. Integralność. Protokoły uwierzytelniania i podpis elektroniczny 44 3. Niewykrywalność. Pieniądz elektroniczny 60 4. Protokoły rzutu monetą 67 5. Ponowne dzielenie się sekretem 72 6. Zagrajmy w kości. Protokoły głosowania 76 7. Poza standardowymi założeniami. Poufne 81 Przekazywanie wiadomości 8. Zamiast wniosku 84 Rozdział 4. Problemy algorytmiczne w teorii liczb 86 1. Wprowadzenie 86 2. System szyfrowania RSA 88 3. Złożoność algorytmów teorii liczb 91 4. Jak odróżnić liczbę złożoną od liczby złożonej Liczba pierwsza 96 5. Jak skonstruować duże liczby pierwsze 99 6. Jak przetestować dużą liczbę pod kątem liczby pierwszej 102 7. Jak rozłożyć liczby złożone 107 8. Logarytm dyskretny 110 9. Wniosek 115 Rozdział 5. Matematyka dzielenia się sekretem 118 1. Wprowadzenie 118 2. Współdzielenie sekretu dla dowolnych struktur dostępu 120 3 Liniowe współdzielenie sekretu 123 4. Idealne współdzielenie sekretu i matroidy 125 Rozdział 6. Komputer i kryptografia 130 1. Zamiast wstępu. 130 2. Trochę teorii 132 3. Jak zaszyfrować plik? 140 4. Uczmy się na cudzych błędach 153 5. Zamiast konkluzji 163 Rozdział 7. Olimpiady kryptograficzne dla uczniów 165 1. Wprowadzenie 166 2. Szyfry podstawieniowe 169 3. Szyfry permutacyjne 182 4. Wieloalfabetyczne szyfry podstawieniowe z kluczem okresowym 190 5. Uwarunkowania problemów olimpijskich z matematyki i kryptografii 198 6. Wskazówki i rozwiązania 210 Załącznik: fragment artykułu K. Shannona „Teoria komunikacji w systemach tajnych” 15 4. Nowe wskazówki 18 5. Zakończenie 23 Rozdział 2. Kryptografia i teoria złożoności 25 1. Wprowadzenie 25 2. Kryptografia i hipoteza P^NP 28 3. Funkcje jednokierunkowe 30 4. Generatory pseudolosowe 32 5. Dowody wiedzy zerowej 35 Rozdział 3 Protokoły kryptograficzne 41 1. Wprowadzenie 41 2. Uczciwość. Protokoły uwierzytelniania i podpisu elektronicznego 44 3. Identyfikowalność. Pieniądz elektroniczny 60 4. Protokoły typu „rzucanie monetą przez telefon”... 67 5. Jeszcze raz o dzieleniu się sekretem 72 6. Zagrajmy w „kostkę”. Protokoły głosowania 76 7. Poza standardowymi założeniami. Poufne poufne przesyłanie wiadomości 81 8. Zamiast wniosku 84 Rozdział 4. Problemy algorytmiczne w teorii liczb 86 1. Wprowadzenie 86 2. System szyfrowania RSA 88 3. Złożoność algorytmów teorii liczb 91 4. Jak odróżnić liczbę złożoną od liczby złożonej Liczba pierwsza 96 5. Jak skonstruować duże liczby pierwsze 99 6. Jak przetestować dużą liczbę pod kątem liczby pierwszej 102 7. Jak rozłożyć liczby złożone na czynniki 107 8. Logarytm dyskretny 110 9. Podsumowanie 115 Rozdział 5. Matematyka współdzielenia sekretu 118 1. Wprowadzenie 118 2. Współdzielenie sekretu dla dowolnych struktur dostępu. . 120 3. Liniowe współdzielenie sekretów 123 4. Idealne współdzielenie sekretów i matroidy 125 Rozdział 6. Komputer i kryptografia 130 1. Zamiast wstępu 130 2. Trochę teorii 132 3. Jak zaszyfrować plik? 140 4. Uczmy się na cudzych błędach 153 5. Zamiast konkluzji 163 Rozdział 7. Olimpiady kryptograficzne dla uczniów 165 1. Wprowadzenie 166 2. Szyfry podstawieniowe 169 3. Szyfry permutacyjne 182 4. Wieloalfabetyczne szyfry podstawieniowe z kluczem okresowym 190 5. Uwarunkowania problemów olimpijskich z matematyki i kryptografii. . 198 6. Kierunki i decyzje 210 Aneks: fragment artykułu K. Shannona „Teoria komunikacji w systemach tajnych” 235 Przedmowa do drugiego wydania To drugie wydanie koryguje błędy typograficzne i nieścisłości zauważone w pierwszym wydaniu. Wrzesień 1999 V. Yashchenko Przedmowa do pierwszego wydania Kryptografia - nauka o szyfrach - była od dawna utajniona, ponieważ służyła głównie do ochrony tajemnic państwowych i wojskowych. Obecnie metody i środki kryptografii wykorzystywane są do zapewnienia bezpieczeństwa informacji nie tylko państwa, ale także osób i organizacji. Niekoniecznie jest to kwestia tajemnic. Zbyt wiele informacji „krąży” po całym świecie w formie cyfrowej. A ponad tymi informacjami są groźby nieprzyjaznej znajomości, akumulacji, podmiany, fałszerstwa itp. To właśnie kryptografia dostarcza najbardziej niezawodnych metod ochrony przed takimi zagrożeniami. Do tej pory algorytmy kryptograficzne dla przeciętnego konsumenta to tajemnica z siedmioma pieczęciami, choć wielu musiało już korzystać z niektórych narzędzi kryptograficznych: szyfrowania wiadomości e-mail, inteligentnych kart bankowych itp. Oczywiście głównym pytaniem dla użytkownika jest to, czy to narzędzie kryptograficzne zapewnia niezawodna ochrona. Ale nawet poprawne sformułowanie tego elementarnego, elementarnego pytania nie jest łatwe. Przed jakim wrogiem się bronimy? Jakie są możliwości tego wroga? Jakie cele może realizować? Jak zmierzyć niezawodność ochrony? Lista takich pytań może być kontynuowana. Aby na nie odpowiedzieć, użytkownik potrzebuje znajomości podstawowych pojęć kryptografii. Celem tej książki jest popularna prezentacja naukowych podstaw kryptografii (mówimy tylko o kryptografii „niepaństwowej”; sekcje kryptografii związane z bezpieczeństwem państwa powinny pozostać tajne). Może służyć również jako pomoc dydaktyczna. Nie ma jeszcze podobnych książek w języku rosyjskim. Materiały kilku rozdziałów zostały opublikowane przez autorów wcześniej w innych publikacjach (rozdział 1 - w książce S. A. Dorichenko, V. V. Yashchenko, „25 badań nad szyframi”, M.: TEIS, 1994; rozdziały 1,2,4 , 5 - w czasopiśmie "Edukacja Matematyczna", seria trzecia, numer 2, M.: MTsNMO, 1998; rozdział 7 - w gazecie "Informatyka" (tygodniowy dodatek do gazety "Pervoe wrzesień"), nr 4, styczeń 1998). Przygotowując to wydanie, materiały te zostały poprawione i uzupełnione. Prezentacja materiału przeznaczona jest dla czytelnika o matematycznym sposobie myślenia. W większości rozdziały są od siebie niezależne (osiąga się to poprzez pewne powtórzenia) i można je czytać w dowolnej kolejności. Rozdział 1 – wprowadzający – jest zalecany do przeczytania dla wszystkich, ponieważ wyjaśnia na poziomie popularnym wszystkie podstawowe pojęcia współczesnej kryptografii: szyfr, klucz, bezpieczeństwo, elektroniczny podpis cyfrowy, protokół krypto-kryptograficzny itp. W innych rozdziałach część materiału jest powtórzona, ale już bardziej dogłębnie. Rozdziały 2, 3, 4, 5 wykorzystują niektóre informacje z matematyki wyższej znane uczniom klas matematycznych i studentom. Rozdział 6 skierowany jest do koneserów technologia komputerowa. Rozdział 7 zawiera materiały do ​​olimpiad kryptograficznych dla dzieci w wieku szkolnym, dlatego do jego przeczytania nie jest wymagana wiedza wykraczająca poza program szkolny. Ostrzeżenie: Narzędzia i oprogramowanie kryptograficzne wymienione w tej książce służą wyłącznie do zilustrowania ogólnych idei kryptograficznych; autorzy nie mieli na celu oceny ani porównania dostępnych na rynku narzędzi kryptograficznych. Kryptografia została postawiona na podstawach naukowych w dużej mierze dzięki pracy wybitnego amerykańskiego naukowca Claude'a Shannona. Jego raport „Matematyczna teoria kryptografii” został przygotowany w wariancie tajnym w 1945 r., odtajniony i opublikowany w 1948 r., przetłumaczony na język rosyjski w 1963 r. Od czasu „Prac nad teorią informacji i cybernetyki” A963) K. Shannon stał się bibliograficzną rzadkością, w aneksie zamieściliśmy główną część artykułu autorstwa K. Shannona „Teoria komunikacji w systemach tajnych”. Ta przełomowa praca jest polecana do przeczytania dla wszystkich zainteresowanych kryptografią. Za profesjonalne zrozumienie algorytmów kryptograficznych i umiejętność oceny ich mocnych stron i słabe strony wymagane jest już poważne przygotowanie matematyczne (na poziomie wydziałów matematycznych uniwersytetów). Wynika to z faktu, że współczesna kryptografia opiera się na głębokich wynikach takich działów matematyki, jak teoria złożoności obliczeń, teoria liczb, algebra, teoria informacji itp. Ci, którzy chcą poważnie studiować kryptografię, mogą polecić przeglądową monografię „Kryptografia w bankowości” Anokhin M. I., Varnovsky N. P., Sidelnikova V. M., Yashchenko V. V., M.: MEPhI, 1997. Październik 1998 V. Yashchenko Rozdział 1 Podstawowe pojęcia kryptografii 1. Wprowadzenie Jak przekazać niezbędne informacje do pożądany adresat w tajemnicy przed innymi? Każdy z czytelników w różnym czasie iz różnymi celami prawdopodobnie próbował sam rozwiązać ten praktyczny problem (dla wygody dalszych odniesień nazwiemy go „problemem TP”, czyli problemem Tajnej Transmisji). Wybrawszy odpowiednie rozwiązanie, najprawdopodobniej powtórzył wynalezienie jednej z metod tajnego przekazywania informacji, która ma ponad tysiąc lat. Zastanawiając się nad problemem TP, nietrudno dojść do wniosku, że istnieją trzy możliwości. 1. Stwórz absolutnie niezawodny kanał komunikacji między subskrybentami, niedostępny dla innych. 2. Korzystaj z publicznego kanału komunikacji, ale ukrywaj sam fakt przekazywania informacji. 3. Korzystać z publicznego kanału komunikacji, ale przekazywać za jego pośrednictwem niezbędne informacje w tak przekształconej formie, aby tylko adresat mógł je przywrócić. Skomentuj te trzy możliwości. 1. Przy obecnym poziomie rozwoju nauki i technologii prawie niemożliwe jest stworzenie takiego kanału komunikacji między zdalnymi abonentami w celu wielokrotnego przesyłania dużych ilości informacji. 2. Steganografia zajmuje się opracowywaniem środków i metod ukrywania faktu przekazywania wiadomości. Pierwsze ślady metod steganograficznych giną już w starożytności. Znany jest np. taki sposób ukrywania wiadomości pisanej: ogolono głowę niewolnika, na głowie napisano wiadomość, a po odrośnięciu włosów niewolnika wysłano do adresata. Z prac detektywistycznych dobrze znane są różne metody tajnego pisania między wierszami zwykłego, niezabezpieczonego tekstu: od mleka po złożone odczynniki chemiczne z późniejszym przetwarzaniem. Metodę „mikrodoty” znamy też z detektywów: wiadomość jest zapisywana przy użyciu nowoczesnej technologii na bardzo małym nośniku (mikrodocie), który wysyłany jest zwykłym listem, na przykład pod znaczkiem lub w innym, z góry określonym miejscu. Obecnie, ze względu na powszechne wykorzystanie komputerów, istnieje wiele subtelnych metod „ukrywania” chronionych informacji w dużych ilościach informacji przechowywanych na komputerze. Wizualny przykład ukrywania pliku tekstowego w pliku graficznym można znaleźć w Internecie1”; podano go również w czasopiśmie Computerra, nr 48 B25) z dnia 1 grudnia 1997 r., na str. 62. (Należy zauważyć, że autorzy artykułu w steganografii są błędnie przypisywani kryptografii w czasopiśmie. Oczywiście za pomocą steganografii można ukryć wstępnie zaszyfrowane teksty, ale ogólnie rzecz biorąc, steganografia i kryptografia to zasadniczo różne obszary w teorii i 3. Rozwój metod konwersji (szyfrowania) informacji w celu ich ochrony przed nielegalnymi użytkownikami, zajmuje się kryptografią. proces stosowania szyfru do informacji chronionych, tj. zamiana informacji chronionych (zwykły tekst) na zaszyfrowaną wiadomość (tekst zaszyfrowany, kryptogram) przy użyciu określonych reguł zawartych w szyfrze Deszyfrowanie jest procesem odwrotnym szyfrowanie, czyli przekształcenie zaszyfrowanej wiadomości w informacje chronione przy użyciu określonych reguł zawartych w szyfrze. Kryptografia jest nauką stosowaną, wykorzystuje najnowsze osiągnięcia nauk podstawowych, a przede wszystkim matematyki. Z drugiej strony, wszystkie specyficzne zadania kryptografii zależą zasadniczo od poziomu rozwoju technologii i technologii, stosowanych środków komunikacji i metod przekazywania informacji. 2. Przedmiot kryptografii Czym jest przedmiot kryptografii? Aby odpowiedzieć na to pytanie, wróćmy do problemu TP w celu wyjaśnienia sytuacji i użytych pojęć. Przede wszystkim zauważamy, że ten problem pojawia się tylko w przypadku informacji, które wymagają ochrony. Zwykle w takich przypadkach mówią, że informacja zawiera tajemnicę lub jest chroniona, prywatna, poufna, tajna. Dla najbardziej typowych, często spotykanych sytuacji tego typu wprowadzono nawet specjalne pojęcia: - tajemnica państwowa; - tajemnica wojskowa; ://www.geocities.com/SiliconValley/Vista/6001/ Podstawowe pojęcia kryptografii - tajemnica handlowa; - tajemnica prawna; - tajemnica medyczna itp. Ponadto porozmawiamy o informacjach chronionych, pamiętając o następujących cechach takich informacji: - istnieje pewien krąg legalnych użytkowników, którzy mają prawo do posiadania tych informacji; - istnieją nielegalni użytkownicy, którzy starają się zdobyć te informacje w celu wykorzystania ich dla własnej korzyści i ze szkodą dla legalnych użytkowników. Dla uproszczenia najpierw ograniczymy się do rozważenia tylko jednego zagrożenia – zagrożenia ujawnieniem informacji. Istnieją inne zagrożenia dla informacji chronionych przed nielegalnymi użytkownikami: substytucja, imitacja itp. Omówimy je poniżej. Teraz możemy zobrazować sytuację, w której pojawia się problem TP, za pomocą poniższego diagramu (patrz rys. 1). ALE< т >Rys. 1. Tutaj A i B są zdalnymi uprawnionymi użytkownikami chronionych informacji; chcą wymieniać informacje za pośrednictwem publicznego kanału komunikacji. P - nielegalny użytkownik (przeciwnik), który może przechwytywać wiadomości przesyłane kanałem komunikacyjnym i próbować wydobyć z nich interesujące go informacje. Ten formalny schemat można uznać za modelowy typowa sytuacja w których stosowane są kryptograficzne metody ochrony informacji. Należy zauważyć, że niektóre słowa militarno-wojskowe (wróg, atak na szyfr itp.) są historycznie zakorzenione w kryptografii i najdokładniej odzwierciedlają znaczenie odpowiednich pojęć kryptograficznych. Jednocześnie w kryptografii teoretycznej nie stosuje się już powszechnie znanej terminologii wojskowej opartej na pojęciu kodu (kody marynarki wojennej, kody Sztabu Generalnego, księgi kodów, oznaczenia kodów itp.). Faktem jest, że w ciągu ostatnich dziesięcioleci powstała teoria kodowania - duży kierunek naukowy, który opracowuje i bada metody ochrony informacji przed przypadkowymi zniekształceniami w kanałach komunikacyjnych. A jeśli wcześniej terminy kodowanie i szyfrowanie były używane jako synonimy, teraz nie jest to nie do przyjęcia. Na przykład bardzo powszechne wyrażenie „kodowanie jest rodzajem szyfrowania” staje się po prostu błędne. Kryptografia zajmuje się metodami przekształcania informacji, które nie pozwalają przeciwnikowi na wydobycie ich z przechwyconych wiadomości. W tym przypadku to już nie sama chroniona informacja jest przekazywana kanałem komunikacyjnym, ale wynik jej przekształcenia za pomocą szyfru, a przeciwnik staje przed trudnym zadaniem złamania szyfru. Otwarcie (złamanie) szyfru to proces uzyskiwania chronionych informacji z zaszyfrowanej wiadomości bez znajomości użytego szyfru. Jednak oprócz przechwycenia i otwarcia szyfru przeciwnik może próbować uzyskać chronione informacje na wiele innych sposobów. Najbardziej znaną z tych metod jest tajna metoda, gdy wróg w jakiś sposób przekonuje jednego z legalnych użytkowników do współpracy i za pomocą tego agenta uzyskuje dostęp do chronionych informacji. W takiej sytuacji kryptografia jest bezsilna. Przeciwnik może próbować nie otrzymywać, ale niszczyć lub modyfikować chronione informacje w trakcie ich transmisji. To zupełnie inny rodzaj zagrożenia dla informacji niż podsłuchiwanie i złamanie szyfru. Aby chronić się przed takimi zagrożeniami, opracowywane są ich własne specyficzne metody. Dlatego na drodze od jednego uprawnionego użytkownika do drugiego informacje muszą być chronione na różne sposoby, odporne na różne zagrożenia. Istnieje sytuacja łańcucha heterogenicznych linków, które chronią informacje. Oczywiście wróg będzie starał się znaleźć najsłabsze ogniwo, aby jak najmniejszym kosztem dotrzeć do informacji. Oznacza to, że prawowici użytkownicy powinni również wziąć pod uwagę tę okoliczność w swojej strategii ochrony: nie ma sensu, aby jakieś łącze było bardzo silne, jeśli istnieją oczywiście słabsze łącza („zasada równej siły ochrony”). Nie powinniśmy zapominać o innym ważnym problemie: problemie stosunku ceny informacji, kosztów jej ochrony i kosztów jej pozyskania. Przy obecnym poziomie rozwoju technologicznego same środki komunikacji, jak również rozwój środków przechwytywania od nich informacji oraz środków ochrony informacji, wymagają bardzo wysokich kosztów. Przed obroną informacji zadaj sobie dwa pytania: 1) czy jest ona dla przeciwnika bardziej cenna niż koszt ataku; 2) czy jest dla Ciebie bardziej wartościowy niż koszt ochrony. To właśnie te względy decydują o wyborze odpowiednich środków ochrony: fizycznej, steganograficznej, kryptograficznej itp. Wygodnie jest zilustrować niektóre koncepcje kryptografii przykładami historycznymi, więc zrobimy małą dygresję historyczną. Przez długi czas kryptografia była udziałem samotnych ekscentryków. Wśród nich byli utalentowani naukowcy, dyplomaci, duchowni. Zdarzają się przypadki, kiedy kryptografię uważano nawet za czarną magię. Ten okres rozwoju kryptografii jako sztuki trwał od niepamiętnych czasów aż do początku XX wieku, kiedy pojawiły się pierwsze maszyny szyfrujące. Zrozumienie matematycznego charakteru problemów rozwiązywanych przez kryptografię przyszło dopiero w połowie XX wieku – po pracy wybitnego amerykańskiego naukowca C. Shannona. Historia kryptografii wiąże się z dużą liczbą tajemnic dyplomatycznych i wojskowych i dlatego spowita jest mgłą legend. Najbardziej kompletna książka o historii kryptografii zawiera ponad tysiąc stron. Została wydana w 1967 r. i nie została przetłumaczona na język rosyjski1”. W języku rosyjskim ukazała się niedawno fundamentalna praca z zakresu historii kryptografii w Rosji. o wykorzystaniu szyfrów w sprawach wojskowych związane są z nazwiskiem spartańskiego dowódcy Lysandera ( szyfr „Scitala". Cezar używał w swojej korespondencji szyfru, który przeszedł do historii jako „szyfr Cezara". W starożytnej Grecji wynaleziono rodzaj szyfru, który później stał się znany jako „kwadratowa Politia". pierwsze książki o kryptografii napisał mieszkający w Niemczech opat I. Tritelius A462-1516. W 1566 roku słynny matematyk D. Cardano opublikował pracę opisującą wynaleziony przez niego system szyfrowania („Krata Cardano”). w historii kryptografii szyfry króla Henryka IV i Richelieu. „cyfrowy alfabet” z 1700 r., którego autorem był Piotr Wielki. (Niektóre przykłady z książki podane są na wyklejce.) Niektóre informacje o właściwościach szyfrów i ich zastosowaniu można znaleźć w fikcji, zwłaszcza w przygodowej, detektywistycznej i wojskowej. Metody jej otwierania zawarte są w dwóch znanych opowiadaniach: "The Gold Bug" E. Poe i "The Dancing Men" A. Conan Doyle'a. Rozważmy dwa przykłady bardziej szczegółowo. Szyfr "Scytalus" Ten szyfr znany jest od wojny Sparty przeciwko Atenom w V wiek pne Do jego wykonania użyto rąbka - pręta w kształcie walca.Wąską taśmę papirusową (bez przerw i zakładek) nawinięto wokół cewki scytala do zwoju, a następnie na tej taśmie napisano zwykły tekst wzdłuż osi rwy.Taśma została odwinięta i okazało się (dla niewtajemniczonych), że niektóre litery są napisane bezładnie na wstążce.Następnie wstążka została wysłana do adresata. otrzymany taśmę i przeczytaj wiadomość wzdłuż osi rciciny. Zauważ, że w tym szyfrze przekształcenie tekstu jawnego w tekst zaszyfrowany polega na pewnej permutacji liter tekstu jawnego. Dawida. łamacze kodów. Historia Sekretnego Pisania. Nowy Jork: Macmillan, 1967. 2 „Kryptografia Soboleva T. A. w historii Rosji (Historia służby kryptograficznej Rosji w XVIII - na początku XX wieku). M., 1994. „Scitala” nazywa się szyframi permutacyjnymi Szyfr Cezara Ten szyfr realizuje następującą transformację tekstu jawnego: każda litera tekstu jawnego jest zastępowana przez trzecią po niej literę alfabetu, która jest uważana za zapisaną w kole, tj. po litery buu Po „i” następuje litera „a”. Zauważ, że Cezar zastąpił literę trzecią literą po niej, ale możesz też zastąpić inną. Najważniejsze, aby osoba, do której wysyłana jest zaszyfrowana wiadomość, znała tę wartość przesunięcia. Klasa szyfrów, do której należy szyfr Cezara, nazywa się szyframi podstawieniowymi. Z poprzedniej prezentacji jasno wynika, że ​​wymyślenie dobrego szyfru jest pracochłonnym zadaniem. Dlatego pożądane jest wydłużenie czasu życia dobrego szyfru i wykorzystanie go do zaszyfrowania jak największej liczby wiadomości. Ale jednocześnie istnieje niebezpieczeństwo, że wróg już odgadł (otworzył) szyfr i odczyta chronione informacje. Jeśli szyfr zawiera wymienny klucz, to poprzez wymianę klucza można sprawić, by opracowane przez wroga metody przestały działać. W kryptografii klucz rozumiany jest jako wymienny element szyfru, który służy do szyfrowania określonej wiadomości. Na przykład w szyfrze Scytala kluczem jest średnica kosza, a w szyfrach takich jak szyfr Cezara kluczem jest wielkość przesunięcia liter szyfrogramu względem liter tekstu jawnego. Opisane rozważania doprowadziły do ​​tego, że o bezpieczeństwie chronionych informacji zaczął decydować przede wszystkim klucz. Sam szyfr, maszynę szyfrującą czy zasadę szyfrowania zaczęto uważać za znane wrogowi i dostępne do wstępnych badań, ale pojawił się w nich nieznany wrogowi klucz, od którego w istotny sposób zależą zastosowane przekształcenia informacji. Ci teraz legalni użytkownicy, przed wymianą zaszyfrowanych, zaszyfrowanych wiadomości, muszą potajemnie wymienić klucze z wrogiem lub ustawić ten sam klucz na obu końcach kanału komunikacyjnego. A dla przeciwnika pojawiło się nowe zadanie - ustalenie klucza, po czym łatwo odczytać wiadomości zaszyfrowane na tym kluczu. Wróćmy do formalnego opisu głównego przedmiotu kryptografii kryptograficznej (ryc. 1, s. 9). Teraz trzeba to wpisać znacząca zmiana- dodaj tajny kanał komunikacyjny niedostępny dla wroga do wymiany kluczy (patrz rys. 2). Stworzenie takiego kanału komunikacji jest dość realistyczne, ponieważ obciążenie go, ogólnie rzecz biorąc, jest niewielkie. Zauważ, że nie ma jednego szyfru, który pasowałby do wszystkich przypadków. Wybór metody szyfrowania zależy od charakterystyki informacji, jej wartości oraz zdolności właścicieli do ochrony swoich informacji. Przede wszystkim podkreślamy ogromną różnicę między kluczowymi koncepcjami kryptografii 13<- " сообщения " . „ П Рис. 2. образие видов защищаемой информации: документальная, телефон- телефонная, телевизионная, компьютерная и т. д. Каждый вид информации имеет свои специфические особенности, и эти особенности сильно влияют на выбор методов шифрования информации. Большое зна- значение имеют объемы и требуемая скорость передачи шифрованной информации. Выбор вида шифра и его параметров существенно за- зависит от характера защищаемых секретов или тайны. Некоторые тайны (например, государственные, военные и др.) должны сохра- сохраняться десятилетиями, а некоторые (например, биржевые) - уже че- через несколько часов можно разгласить. Необходимо учитывать так- также и возможности того противника, от которого защищается данная информация. Одно дело - противостоять одиночке или даже бан- банде уголовников, а другое дело - мощной государственной структу- структуре. Способность шифра противостоять всевозможным атакам на него называют стойкостью шифра. Под атакой на шифр понимают попытку вскрытия этого шифра. Понятие стойкости шифра является центральным для криптогра- криптографии. Хотя качественно понять его довольно легко, но получение стро- строгих доказуемых оценок стойкости для каждого конкретного шифра - проблема нерешенная. Это объясняется тем, что до сих пор нет необ- необходимых для решения такой проблемы математических результатов. (Мы вернемся к обсуждению этого вопроса ниже.) Поэтому стойкость конкретного шифра оценивается только путем всевозможных попыток его вскрытия и зависит от квалификации крипто аналитике в, атаку- атакующих шифр. Такую процедуру иногда называют проверкой стойко- стойкости. Важным подготовительным этапом для проверки стойкости шифра является продумывание различных предполагаемых возможностей, с помощью которых противник может атаковать шифр. Появление та- таких возможностей у противника обычно не зависит от криптографии, это является некоторой внешней подсказкой и существенно влияет на стойкость шифра. Поэтому оценки стойкости шифра всегда содержат те предположения о целях и возможностях противника, в условиях ко- которых эти оценки получены. 14 Глава 1 Прежде всего, как это уже отмечалось выше, обычно считается, что противник знает сам шифр и имеет возможности для его предва- предварительного изучения. Противник также знает некоторые характери- характеристики открытых текстов, например, общую тематику сообщений, их стиль, некоторые стандарты, форматы и т. д. Из более специфических приведем еще три примера возможностей противника: - противник может перехватывать все шифрованные сообщения, но не имеет соответствующих им открытых текстов; - противник может перехватывать все шифрованные сообщения и добывать соответствующие им открытые тексты; - противник имеет доступ к шифру (но не к ключам!) и поэтому может зашифровывать и дешифровывать любую информацию. На протяжении многих веков среди специалистов не утихали споры о стойкости шифров и о возможности построения абсолютно стойкого шифра. Приведем три характерных высказывания на этот счет. Английский математик Чарльз Беббидж (XIX в.): «Всякий человек, даже если он не знаком с техникой вскрытия шифров, твер- твердо считает, что сможет изобрести абсолютно стойкий шифр, и чем более умен и образован этот человек, тем более твердо это убеждение. Я сам раз- разделял эту уверенность в течение многих лет.» «Отец кибернетики» Норберт Винер: «Любой шифр может быть вскрыт, если только в этом есть настоятельная необходимость и информация, которую предполагается получить, стоит за- затраченных средств, усилий и времени...» Автор шифра PGP Ф. Зиммерманн («Компьютерра», №48 от 1.12.1997, стр. 45-46): «Каждый, кто думает, что изобрел непробиваемую схему шифрования, - или невероятно редкий гений, или просто наивен и неопытен...» «Каждый программист воображает себя криптографом, что ведет к распро- распространению исключительно плохого криптообеспечения...» В заключение данного раздела сделаем еще одно замечание - о тер- терминологии. В ostatnie czasy wraz ze słowem „kryptografia” często spotyka się słowo „kryptologia”, ale związek między nimi nie zawsze jest poprawnie rozumiany. Obecnie następuje ostateczne formowanie się tych dyscyplin naukowych, doprecyzowanie ich przedmiotu i zadań. Kryptologia to nauka składająca się z dwóch gałęzi: kryptografii i kryptoanalizy. Kryptografia to nauka o sposobie przekształcania (szyfrowania) informacji w celu ochrony przed nielegalnymi użytkownikami. Kryptanaliza to nauka (i praktyka jej stosowania) o metodach i sposobach łamania szyfrów. Podstawowe pojęcia kryptografii 15 Związek między kryptografią a kryptoanalizą jest oczywisty: kryptografia kryptograficzna to ochrona, czyli rozwój szyfrów, a kryptoanaliza to atak, czyli atak na szyfry. Jednak te dwie dyscypliny są ze sobą powiązane i nie ma dobrych kryptografów, którzy nie opanowaliby metod krio-kryptoanalizy. 3. Podstawy matematyczne Duży wpływ na rozwój kryptografii miały prace amerykańskiego matematyka Claude Shan-Shannona, które pojawiły się w połowie XX wieku. W pracach tych położono podwaliny teorii informacji oraz opracowano aparat matematyczny do badań w wielu dziedzinach nauki związanych z informacją. Co więcej, powszechnie przyjmuje się, że teoria informacji jako nauka narodziła się w 1948 r. po opublikowaniu pracy K. Shannona „Matematyczna teoria komunikacji”1). W swojej pracy „Teoria komunikacji w systemach tajnych” Claude Shannon podsumował doświadczenia zdobyte przed nim w rozwoju szyfrów.jest najprostszym, najpopularniejszym szyfrem.Typowymi przykładami są szyfr Cezara, „cyfrowy alfabet” Piotra Wielkiego oraz A. „Tańczący mężczyźni” Conan Doyle'a „części” szyfrogramu. Łatwo jest podać matematyczny opis szyfru podstawieniowego. Niech X i Y będą dwoma alfabetami (odpowiednio tekstem jawnym i tekstem zaszyfrowanym) składającymi się z tej samej liczby znaków Niech q: X -> Y będzie odwzorowaniem jeden-do-jednego X na Y. Wtedy szyfr podstawieniowy działa w następujący sposób: tekst jawny x\x2 ¦¦.xn jest konwertowany na tekst zaszyfrowany q(x1)q( x2) ¦ ¦ -q(xn). z nazwy konwertuje permutację liter w zwykłym tekście. Typowym przykładem szyfru permutacyjnego jest szyfr Scytala. Zwykle tekst jawny jest dzielony na segmenty o równej długości, a każdy segment jest szyfrowany niezależnie. Niech na przykład długość segmentów będzie równa n, a a będzie odwzorowaniem jeden do jednego zbioru (1,2,...,n) na siebie. Wtedy szyfr permutacyjny działa w następujący sposób: segment tekstu jawnego x\ ... xn jest przekształcany w segment tekstu zaszyfrowanego xx\) ... xa(n). ^ Shannon SE Matematyczna teoria komunikacji // Bell System Techn. J.V. 27, nr 3, 1948. str. 379-423; V. 27, nr 4, 1948. S. 623-656. 2” Patrz Aneks. 16 Rozdział 1 Najważniejszym wynikiem dla rozwoju kryptografii był wynik K. Shan-Shannona dotyczący istnienia i wyjątkowości całkowicie bezpiecznego szyfru. Jedynym takim szyfrem jest jakaś forma tzw. -użyj taśmy, w której tekst jawny jest „z całkowicie losowym kluczem o tej samej długości. Wynik ten udowodnił K. Shannon za pomocą opracowanej przez niego informacyjno-teoretycznej metody badania szyfrów. Nie będziemy się tutaj szczegółowo omawiać Zainteresowanym czytelnikom polecamy zapoznanie się z pracą K. Shannona1”. Omówmy cechy budowy szyfru absolutnie bezpiecznego i możliwości jego praktycznego wykorzystania. Typowym i najprostszym przykładem implementacji całkowicie bezpiecznego szyfru jest szyfr Vernama, który dokonuje bitowego dodawania n-bitowego tekstu jawnego i n-bitowego klucza: yi = Xi®ki, i = l,...,n . Tutaj Xi ...xn to tekst jawny, k\,...,kn to klucz, y\ ¦ ¦ .yn to tekst zaszyfrowany. Podkreślamy, że każde z poniższych wymagań dla taśmy jednorazowej jest niezbędne dla absolutnego bezpieczeństwa: 1) całkowita losowość (ekwiprobacja) klucza (w szczególności oznacza to, że klucza nie można wygenerować za pomocą żadnego urządzenia deterministycznego); 2) równość długości klucza i długości tekstu jawnego; 3) jednorazowe użycie klucza. Jeśli choć jeden z tych warunków zostanie naruszony, szyfr przestaje być absolutnie bezpieczny i pojawiają się fundamentalne możliwości jego otwarcia (choć mogą być trudne do zrealizowania). Okazuje się jednak, że to właśnie te warunki sprawiają, że absolutnie silny szyfr jest bardzo drogi i niepraktyczny. Przed użyciem takiego szyfru musimy zapewnić wszystkim subskrybentom wystarczającą ilość kluczy losowych i wykluczyć możliwość ich ponownego wykorzystania. A to jest niezwykle trudne i kosztowne. Jak zauważył D. Kahn: „Problem tworzenia, rejestracji, dystrybucji i anulowania kluczy może nie wydawać się zbyt skomplikowany komuś, kto nie ma doświadczenia w przesyłaniu wiadomości za pośrednictwem wojskowych kanałów komunikacyjnych, ale w czasie wojny ilość przesyłanych wiadomości dezorientuje nawet zawodowych sygnalizatorów . Dziennie można zaszyfrować setki tysięcy słów. Stworzenie milionów znaków kluczowych wymagałoby ogromnych nakładów finansowych i wiązałoby się z dużą inwestycją czasu. Ponieważ każdy tekst musi mieć swój własny, niepowtarzalny i niepowtarzalny klucz, użycie idealnego systemu wymagałoby przesłania co najmniej tylu znaków, ile odpowiada całej objętości informacji wojskowej. przekazywane." Z tych powodów absolutnie silne szyfry są używane tylko w sieciach komunikacyjnych z niewielką ilością przesyłanych informacji, zwykle są to sieci do przesyłania szczególnie ważnych informacji rządowych silne szyfry Takie szyfry, przynajmniej teoretycznie, można złamać. czy przeciwnik ma dość siły, środków i czasu, aby opracować i wdrożyć odpowiednie algorytmy.Zazwyczaj idea ta wyraża się w następujący sposób: przeciwnik z nieograniczonymi zasobami może złamać każdy niecałkowicie silny szyfr. Jak zatem powinien postępować w tej sytuacji uprawniony użytkownik wybierając dla siebie szyfr?Najlepiej byłoby oczywiście udowodnić, że żaden przeciwnik nie może lat i tym samym uzyskać teoretycznego oszacowania oporu.Niestety teoria matematyczna nie podaje jeszcze niezbędnych twierdzeń - odnoszą się do nierozwiązanego problemu dolnych granic złożoności obliczeniowej problemów. \ Dlatego użytkownikowi pozostaje jedyny sposób - uzyskać praktyczne oceny trwałości. Ścieżka ta składa się z następujących etapów: „- zrozumieć i jasno wyartykułować, przed jakim rodzajem przeciwnika będziemy chronić informacje; konieczne jest zrozumienie, co dokładnie przeciwnik wie lub może dowiedzieć się o systemie szyfrów, a także jakie siły i oznacza, że ​​będzie mógł go użyć do jego otwarcia, - mentalnie postawić się w pozycji wroga i spróbować zaatakować szyfr z jego pozycji, tj. opracować różne algorytmy łamania szyfru, podczas gdy konieczne jest dostarczenie modeli do maksymalny zakres - modelowanie sił, środków i możliwości przeciwnika - najlepsze z opracowanych algorytmów można wykorzystać do praktycznej oceny bezpieczeństwa szyfru. szyfr: losowe odgadywanie klucza (działa z małym prawdopodobieństwem, ale ma małą złożoność) i wyliczanie wszystkich kluczy w rzędzie aż do znalezienia prawdy (działa zawsze, ale ma bardzo dużą złożoność). Zwracamy również uwagę, że atak na klucz nie zawsze jest konieczny: w przypadku niektórych szyfrów możliwe jest natychmiastowe odzyskanie tekstu jawnego z tekstu zaszyfrowanego, nawet bez znajomości klucza. 18 Rozdział 1 4. Nowe kierunki W 1983 roku w książce „Kody i matematyka” M. N. Arshinova i L. E. Sa-Sadovsky'ego (biblioteka „Kvant”) napisano: „Istnieje bardzo wiele metod kryptografii, a większość prawdopodobnie jest to obszar, w którym nie ma już potrzeby wymyślania czegoś zasadniczo nowego. Było to jednak kolejne wielkie nieporozumienie dotyczące kryptografii. Już w 1976 roku ukazała się praca młodych amerykańskich matematyków W. Diffie i M. E. Hellmana „New Trends in Cryptography”1”, która nie tylko znacząco zmieniła kryptografię, ale także doprowadziła do pojawienia się i szybkiego rozwoju nowych trendów w matematyce. Centralnym pojęciem „nowa kryptografia” jest pojęcie funkcji jednokierunkowej (więcej na ten temat w Rozdziale 2) Funkcja jednokierunkowa nazywana jest funkcją F:X -> Y, która ma dwie właściwości: a) istnieje algorytm wielomianowy do obliczania wartości F(x), b) nie ma algorytmu wielomianowego do odwracania funkcji F (tzn. rozwiązanie równania F(x) = y względem x, patrz str. 30 dla dokładnej definicji) o ograniczenia złożoności jej obliczania i odwracania. Kwestia istnienia funkcji jednokierunkowych jest wciąż otwarta. Innym nowym pojęciem jest pojęcie funkcji z tajemnicą. Czasami jest również używane funkcja termiczna z pułapką. Funkcja z sekretem K to funkcja Fk: X -> Y, która zależy od parametru K i ma trzy własności: a) istnieje algorytm wielomianowy do obliczania wartości Fk(x) dla dowolnych K i x; b) nie ma algorytmu wielomianowego odwracania Fa dla nieznanego K; c) istnieje wielomianowy algorytm odwracania Fk ze znanym K. O istnieniu funkcji z tajemnicą można powiedzieć to samo, co o funkcjach jednokierunkowych. Dla praktycznych celów kryptografii skonstruowano kilka funkcji, które mogą okazać się funkcjami z tajemnicą. Dla nich właściwość b) nie została jeszcze dokładnie udowodniona, ale uważa się, że problem inwersji jest równoważny z jakimś trudnym problemem matematycznym, który był badany od dłuższego czasu. Najbardziej znaną i najpopularniejszą z nich jest funkcja teoretyczna liczb, na której zbudowany jest szyfr RSA (więcej na ten temat w Rozdziale 4). „” Diffie W., Hellman ME Bezpieczeństwo i odporność na imitacje. Wprowadzenie do kryptografii // TIEER. V. 67, nr 3, 1979. Podstawowe pojęcia kryptografii 19 Wykorzystanie funkcji z tajemnicą w kryptografii pozwala: 1) zorganizować wymianę zaszyfrowanych wiadomości przy użyciu tylko otwartych kanałów komunikacji, tj. odmówić tajnych kanałów komunikacji dla wstępnej wymiana kluczy; 2) włączyć trudny problem matematyczny do problemu złamania szyfru i tym samym zwiększyć ważność zabezpieczenia szyfru; 3) rozwiązywać nowe problemy kryptograficzne inne niż szyfrowanie (elektroniczny podpis cyfrowy itp.). Opiszmy na przykład, jak można wdrożyć punkt 1). Użytkownik A, który chce otrzymywać zaszyfrowane wiadomości, musi wybrać jakąś funkcję Fk z sekretem K. Informuje on wszystkich zainteresowanych (na przykład publikuje) opis funkcji Fk jako swojego algorytmu szyfrowania. Ale jednocześnie nie zdradza nikomu znaczenia tajemnicy K i utrzymuje ją w tajemnicy. Teraz, jeśli użytkownik B chce wysłać chronione informacje do użytkownika A? X, to oblicza y = Fk(x) i wysyła y przez otwarty kanał do użytkownika A. Ponieważ A wie, jak odwrócić Fk dla swojego sekretu K, to oblicza x z otrzymanego y. Nikt inny nie zna K, a zatem ze względu na właściwość b) funkcji z tajemnicą nie będzie w stanie obliczyć chronionej informacji x w czasie wielomianowym ze znanej zaszyfrowanej wiadomości Fk(x). Opisany system nazywany jest kryptosystemem klucza publicznego, ponieważ algorytm szyfrowania Fk jest publiczny lub otwarty. Ostatnio takie kryptosystemy nazywane są również asymetrycznymi, ponieważ mają asymetrię w algorytmach: algorytmy szyfrowania i deszyfrowania są różne. W przeciwieństwie do takich systemów, tradycyjne szyfry nazywane są symetrycznymi: w nich klucz do szyfrowania i odszyfrowywania jest taki sam. W przypadku systemów asymetrycznych algorytm szyfrowania jest dobrze znany, ale nie jest możliwe odtworzenie z niego algorytmu deszyfrowania w czasie wielomianowym. Diffie i Hellman zasugerowali wykorzystanie opisanego powyżej pomysłu również w przypadku elektroniki podpis cyfrowy wiadomości, których nie można sfałszować w czasie wielomianowym. Niech użytkownik A nie musi podpisywać wiadomości x. Znając sekret K znajduje y takie, że Pk(y) - x i razem z komunikatem x wysyła y do użytkownika B jako jego podpis cyfrowy. Użytkownik B przechowuje y jako dowód, że A podpisana wiadomość x. Wiadomość podpisana podpisem cyfrowym można traktować jako parę (x, y), gdzie x jest wiadomością, y jest rozwiązaniem równania Pk(y) - x, Fk"¦ X -> Y jest funkcją z sekretem znanym wszystkim współdziałającym Z definicji funkcji Fk oczywiste są następujące użyteczne właściwości podpisu cyfrowego: 2) każdy subskrybent, który zna klucz publiczny, tj. sama funkcja Fk\ może zweryfikować autentyczność podpisu 3 ) w przypadku sporów nie można odmówić podpisu ze względu na jego niepodrabialność 4) podpisane wiadomości (x, y) można wykonać bez obaw o uszkodzenie, przekazać dowolnymi kanałami komunikacji.Oprócz zasady budowy kryptosystemu z klucz publiczny, Diffie i Hellman w tej samej pracy zaproponowali inny nowy pomysł - dystrybucję klucza publicznego.Zadali sobie pytanie: czy jest możliwe zorganizowanie takiej procedury interakcji subskrybentów? i B za pośrednictwem otwartych kanałów komunikacyjnych w celu rozwiązania następujących zadań: 1) na początku A i B nie mają wspólnych tajnych informacji, ale na koniec procedury taka wspólna tajna informacja (wspólny klucz) pojawia się dla A i B, tj. jest generowany; 2) bierny przeciwnik, który przechwytuje wszystkie transmisje informacji i wie, że A i B chcą odebrać, ale nie może odzyskać wygenerowanego wspólnego klucza A i B. Diffie i Hellman zaproponowali rozwiązanie tych problemów za pomocą funkcji F(x) = ax (mod p), gdzie p jest dużą liczbą pierwszą, x jest dowolną liczbą naturalną, q jest jakimś pierwotnym elementem ciała GF(p). Powszechnie przyjmuje się, że odwrócenie funkcji ax (modp), tj. logarytm dyskretny jest trudnym problemem matematycznym. (Więcej szczegółów w rozdziale 4.) Sama procedura lub, jak mówią, protokół generowania współdzielonego klucza, jest opisany poniżej. Abonenci A i B, niezależnie od siebie, wybierają losowo po jednej liczbie naturalnej - powiedzmy xa i xb. Utrzymują te elementy w tajemnicy. Ponadto każdy z nich oblicza nowy element: y A = otXA (mod p), y b = aXb (mod p). (Liczby p i a są uważane za publiczne. ) Następnie wymieniają te elementy za pośrednictwem kanału komunikacyjnego. Teraz subskrybent A, po otrzymaniu uv i znając swój tajny element xa, oblicza nowy element: uxvA (modp) = (aXB)XA (modp). Abonent B zachowuje się podobnie: uxAv (mod p) = (aXA)Xv (mod p). Podstawowe pojęcia kryptografii 21 Zatem A i B mają wspólny element pola równy aXlXv. Ten element jest deklarowany przez wspólny klucz A i B. Z opisu protokołu jasno wynika, że ​​przeciwnik zna p, a, aXA, aXb, nie zna xa i xts i chce znać aXXb. Obecnie nie ma algorytmów przeciwnika bardziej wydajnych niż logarytm dyskretny i jest to trudny problem matematyczny. Postępy w rozwoju schematów podpisów cyfrowych i dystrybucji klucza publicznego umożliwiły zastosowanie tych pomysłów również do innych problemów interakcji między zdalnymi abonentami. W ten sposób powstał wielki nowy kierunek kryptografii teoretycznej - protokoły kryptograficzne (więcej szczegółów w rozdziale 3). Przedmiotem badań teorii protokołów kryptograficznych jest z reguły interakcja zdalnych abonentów za pośrednictwem otwartych kanałów komunikacyjnych. Celem interakcji subskrybentów jest rozwiązanie jakiegoś problemu. Jest też przeciwnik, który dąży do własnych celów. W takim przypadku wróg w różnych zadaniach może mieć różne możliwości: na przykład może wchodzić w interakcje z subskrybenci-subskrybenci w imieniu innych subskrybentów lub interweniować w wymianę informacji między subskrybentami itp. Wrogiem może być nawet jeden z subskrybentów lub kilku subskrybentów, którzy byli w zmowie. Oto kilka przykładów zadań rozwiązywanych przez zdalnych subskrybentów. (Zalecamy, aby czytelnik wymyślił więcej przykładów według własnego gustu.) 1. Dwóch subskrybentów, którzy nie ufają sobie nawzajem, wchodzi w interakcję. Chcą podpisać umowę. Należy to zrobić w taki sposób, aby zapobiec następującej sytuacji: jeden z subskrybentów otrzymał podpis drugiego, ale sam nie podpisał. Protokół rozwiązania tego problemu nazywany jest zwykle protokołem podpisania umowy. 2. Dwóch subskrybentów, którzy nie ufają sobie nawzajem, wchodzi w interakcję. Chcą rzucać losy monetą. Należy to zrobić w taki sposób, aby użytkownik, który rzuca monetą, nie mógł zmienić wyniku losowania po otrzymaniu odgadnięcia od użytkownika zgadującego ten wynik. Protokół rozwiązania tego problemu nazywa się protokołem rzutu monetą. Opiszmy jeden z najprostszych protokołów rzucania monetą przez telefon (tzw. schemat Blume-Micali). Aby go zaimplementować, abonenci A i B muszą posiadać funkcję jednokierunkową /: X -> Y, która spełnia następujące warunki: 1) X to zbiór liczb całkowitych, który zawiera tę samą liczbę parzystych i nieparzystych; 22 Rozdział 1 2) dowolne liczby xi,X2 ? X posiadające jeden obraz )(x\) - jedna parzystość; 3) biorąc pod uwagę wzorzec f(x), „trudno” jest obliczyć parzystość nieznanego argumentu x. Rolę rzucania monetą odgrywa przypadkowy i równie prawdopodobny wybór elementu x 6 X, a rolę orła i reszki odgrywa odpowiednio parzystość i nieparzystość x. Niech A będzie rzucającym monetą, a B zgaduje. Protokół składa się z następujących kroków: 1) A wybiera x („rzuca monetą”), szyfruje x, czyli oblicza y = f(x) i wysyła y do abonenta B; 2) B otrzymuje y, próbuje odgadnąć parzystość x i wysyła swoje przypuszczenie do abonenta A; 3) A otrzymuje odpowiedź od B i mówi B, czy odgadł poprawnie, wysyłając mu wybraną liczbę x; 4) B sprawdza, czy A nie oszukuje, obliczając wartość f(x) i porównując ją z wartością y uzyskaną w drugim kroku. 3. Dwóch abonentów A i B wchodzi w interakcję (typowy przykład: A to klient banku, B to bank). Abonent A chce udowodnić abonentowi B, że jest A, a nie przeciwnikiem. Protokół rozwiązania tego problemu nazywany jest zwykle protokołem identyfikacji abonenta. 4. Interakcja kilku zdalnych abonentów, którzy otrzymali zamówienia z jednego centrum. Niektórzy subskrybenci, w tym centrum, mogą być przeciwnikami. Konieczne jest wypracowanie jednolitej strategii działania, która jest korzystna dla subskrybentów. Ten problem jest zwykle nazywany problemem bizantyńskich generałów, a protokół jego rozwiązania nazywany jest protokołem bizantyjskiego układu. Opiszmy przykład, któremu ten problem zawdzięcza swoją nazwę. Bizancjum - Bizancjum. Noc przed wielką bitwą. Armia bizantyjska składa się z n legionów, z których każdy podlega własnemu generałowi. Ponadto armia ma naczelnego wodza, który kieruje generałami. Jednak imperium podupada i nawet jedna trzecia generałów, w tym naczelny wódz, może być zdrajcami. W nocy każdy z generałów otrzymuje od głównodowodzącego rozkaz o działaniach na poranek, a dwa va-wariant rozkaz: "atak" lub "odwrót". Jeśli wszyscy uczciwi generałowie zaatakują, wygrywają. Jeśli wszyscy się wycofają, uda im się uratować armię. Ale jeśli niektórzy z nich zaatakują, a inni wycofają się, zostaną pokonani. Jeśli naczelny wódz okaże się zdrajcą, to może wydawać różne rozkazy różnym generałom, więc rozkazy naczelnego wodza nie powinny być bezwzględnie przestrzegane. Jeśli każdy generał działa niezależnie od innych, skutki mogą być katastrofalne. Oczywiście generałowie muszą wymieniać między sobą informacje (dotyczące otrzymanych rozkazów), aby dojść do porozumienia. Podstawowe pojęcia kryptografii 23 Zrozumienie różnych protokołów i metod ich budowy zaowocowało: do pojawienia się dwóch owocnych modeli matematycznych - interaktywnego systemu dowodowego i dowodu z wiedzą zerową. Badania matematyczne tych nowych obiektów dowiodły wielu stwierdzeń, które są bardzo przydatne w rozwoju protokołów kryptograficznych (więcej na ten temat w rozdziale 2). Interaktywny system dowodowy (P, V, S) rozumiany jest jako protokół interakcji dwóch subskrybentów: P (udowadniający) i V (pro- (weryfikujący). Subskrybent P chce udowodnić V, że stwierdzenie 5 jest prawdziwe. jednocześnie subskrybent V samodzielnie, bez pomocy P , nie może zweryfikować twierdzenia S (stąd V nazywany jest weryfikatorem. Subskrybent P może być także przeciwnikiem, który chce udowodnić V, że twierdzenie S jest prawdziwe, chociaż jest fałszywe Protokół może składać się z wielu rund wymiany komunikatów między P i V i musi spełniać dwa warunki: 1) kompletność - jeśli 5 jest rzeczywiście prawdą, to subskrybent P przekona subskrybenta V do jej przyznania; 2) poprawność – jeśli 5 jest fałszywe, to mało prawdopodobne jest, aby subskrybent P przekonał subskrybenta V, że 5 to prawda. Tutaj dla uproszczenia zastąpiliśmy dokładne sformułowanie matematyczne słowami „nieprawdopodobne”. Podkreślamy, że w definicji systemu (P, V, S) nie dopuszczono, aby V mógł być przeciwnikiem. A co by było, gdyby V okazał się przeciwnikiem, który chce „wydobyć” od P jakieś nowe przydatne informacje na temat stwierdzenia 5? W takim przypadku P, oczywiście, może nie chcieć, aby tak się stało w wyniku działania protokołu (P, V, S). Protokół (P, V, S) rozwiązujący taki problem nazywany jest dowodem wiedzy zerowej i musi spełniać, oprócz warunków 1) i 2), warunek: 3) wiedza zerowa - w wyniku operacji protokołu (P, V, S) subskrybent V nie zwiększy swojej znajomości twierdzenia S lub innymi słowy nie będzie w stanie wydobyć żadnej informacji, dlaczego S jest prawdziwe. 5. Podsumowanie W ostatnich latach kryptografia i metody kryptograficzne coraz częściej stają się częścią naszego życia, a nawet codziennego życia. Oto kilka przykładów. Wysyłając e-mail, w niektórych przypadkach odpowiadamy na pytanie menu: „Czy potrzebuję trybu szyfrowania?” Właściciel inteligentnej karty bankowo-bankowej, adresując się do banku przez terminal, w pierwszej kolejności wykonuje protokół uwierzytelniania karty kryptograficznej. Internauci są prawdopodobnie zaznajomieni z dyskusjami na temat możliwego przyjęcia standardu podpisu cyfrowego dla tych stron, które zawierają „krytyczne” informacje (prawne, cenniki itp.). Ostatnio użytkownicy sieci zaczęli wskazywać po swoim nazwisku, obok znanego już „E-mail…” i mniej znanego – „Odcisk palca klucza publicznego…”. Z każdym dniem takich przykładów jest coraz więcej. To właśnie nowe praktyczne zastosowania kryptografii są jednym ze źródeł jej rozwoju. Rozdział 2 Kryptografia i teoria złożoności Celem tego rozdziału jest wyjaśnienie ważnych idei związanych ze stosowaniem podejścia teorii złożoności do kryptografii. Ekspozycja jest z konieczności niedostatecznie formalna - wielostronicowe definicje są typowe dla kryptografii matematycznej. Zakłada się, że czytelnik zna podstawy teorii złożoności obliczeniowej: pojęcia maszyny Turinga, klasy P i NP (patrz ), a także rozdział 1 tej książki. 1. Wprowadzenie W kryptografii teoretycznej istnieją dwa główne podejścia do określania bezpieczeństwa kryptosystemów i protokołów kryptograficznych (w dalszej części będziemy również używać ogólnego terminu schematy kryptograficzne): teoretyka informacji i teoria złożoności. Podejście informacyjno-teoretyczne zakłada, że ​​przeciwnik atakujący schemat kryptograficzny nie ma nawet teoretycznej możliwości uzyskania informacji wystarczających do osiągnięcia swoich celów. Klasycznym przykładem jest tutaj szyfr Vernama z jednorazowymi kluczami, absolutnie odporny na biernego przeciwnika. Zdecydowana większość kryptograficznych schematów kryptograficznych stosowanych w praktyce nie ma tak wysokiego poziomu bezpieczeństwa. Co więcej, zwykle łatwo wskazać algorytm, który wykonuje zadanie stojące przed przeciwnikiem, ale nie praktycznie, ale co do zasady. Rozważmy następujący przykład. Przykład 1 (Kryptosystem klucza publicznego). Kryptosystem - Kryptosystem klucza publicznego jest całkowicie zdefiniowany przez trzy algorytmy - algorytmy: generowanie klucza, szyfrowanie i deszyfrowanie. Algorytm generowania klucza G jest publicznie dostępny; każdy może podać mu jako dane wejściowe losowy ciąg r o odpowiedniej długości i otrzymać parę kluczy (A "1, Xr). Klucz publiczny K \ jest publikowany, a sekret klucz K-i a losowy ciąg z są utrzymywane w tajemnicy. Algorytmy szyfrowania Ekx i deszyfrowania D^2 są takie, że jeśli (K\, K-i) jest parą kluczy wygenerowaną przez algorytm G, to Dk2(Ek1 [m)) = m dla dowolnego tekstu jawnego m. Dla uproszczenia zakładamy, że tekst jawny i kryptogram mają tę samą długość n. Dodatkowo zakładamy, że tekst jawny, kryptogram i oba klucze są ciągami w alfabecie binarnym. Załóżmy teraz, że przeciwnik atakuje ten kryptosystem. Zna klucz publiczny K\, ale nie zna odpowiadającego mu sekret Klucz Ki. Przeciwnik przechwycił kryptogram d i próbuje znaleźć wiadomość m, gdzie d = Ec^(m). Ponieważ algorytm szyfrowania jest dobrze znany, przeciwnik może po prostu iterować przez wszystkie możliwe wiadomości o długości n, obliczyć dla każdej takiej wiadomości TP(kryptogram di = Ekx (mn-r) i porównać di z d. Do wiadomości, dla której di = d i będzie żądanym tekstem jawnym. Jeśli masz szczęście, tekst jawny zostanie znaleziony wystarczająco szybko. W najgorszym przypadku wyliczenie zostanie zakończone w czasie rzędu 2"T(n), gdzie T( n) to czas potrzebny do obliczenia funkcji Ek, z wiadomości o długości n. Jeżeli wiadomości mają długość rzędu 1000 bitów, to takie wyliczenie nie jest możliwe w praktyce na żadnym z najpotężniejszych komputerów. tylko jedna z możliwych metod ataku na system szyfrujący i najprostszy algorytm wyszukiwania tekstu jawnego, zwykle nazywany algorytmem pełnego tekstu. Używana jest też inna nazwa: „metoda brute force”. Innym prostym algorytmem wyszukiwania tekstu jawnego jest zgadywanie. Ten oczywisty algorytm wymaga niewiele obliczenia, ale działa z prawdopodobieństwem znikomym (dla dużych tekstów). W rzeczywistości przeciwnik może próbować zaatakować kryptosystem na różne sposoby i użyć różnych, bardziej wyrafinowanych algorytmów wyszukiwania tekstu jawnego. Uznanie kryptosystemu za bezpieczny jest naturalne, jeśli jakikolwiek taki algorytm wymaga praktycznie niewykonalnej ilości obliczeń lub działa z znikomym prawdopodobieństwem. (W tym przypadku przeciwnik może użyć nie tylko algorytmów deterministycznych, ale także probabilistycznych.) Jest to podejście oparte na teorii złożoności do definicji bezpieczeństwa. Aby zaimplementować go w odniesieniu do tego lub innego rodzaju schematów kryptograficznych, należy wykonać następujące czynności: 1) podać formalną definicję schematu tego typu; 2) podać formalną definicję zabezpieczenia programu; 3) udowodnienie stabilności konkretnego projektu obwodu danego typu. Tutaj natychmiast pojawia się szereg problemów. Po pierwsze, w schematach kryptograficznych zawsze stosuje się oczywiście stałe wartości parametrów. Na przykład systemy kryptografii i teorii złożoności 27 są zaprojektowane dla kluczy o długości, powiedzmy, 256 lub 512 bajtów. Aby zastosować podejście oparte na teorii złożoności, konieczne jest, aby problem, którego złożoność obliczeniowa ma być wykorzystana, był ogromny. Dlatego w kryptografii teoretycznej rozważa się modele matematyczne schematów kryptograficznych. Modele te zależą od pewnego parametru zwanego parametrem security, który może przyjmować dowolnie duże wartości (zwykle dla uproszczenia zakłada się, że parametr security-security może przebiegać przez cały ciąg naturalny). Po drugie, określenie siły schematu kryptograficznego zależy od zadania stojącego przed przeciwnikiem i od tego, jakie informacje o schemacie są dla niego dostępne. Dlatego przychodzi stabilność schematów - konieczne jest ustalenie i zbadanie osobno dla każdego założenia dotyczącego wroga. Po trzecie, konieczne jest wyjaśnienie, jaką ilość obliczeń można uznać za „praktycznie niewykonalne”. Z powyższego wynika, że ​​wartość ta nie może być tylko stałą, musi być reprezentowana przez funkcję rosnącego parametru bezpieczeństwa. Zgodnie z tezą Edmondsa algorytm uważa się za wydajny, jeśli czas jego wykonania jest ograniczony przez pewien wielomian w długości słowa wejściowego (w naszym przypadku na parametrze bezpieczeństwa). W przeciwnym razie mówi się, że obliczenia za pomocą tego algorytmu są praktycznie niemożliwe. Zauważamy również, że same schematy kryptograficzno-kryptograficzne muszą być wydajne, tj. wszystkie obliczenia określone przez ten lub inny schemat muszą być wykonywane w czasie wielomianowym. Po czwarte, konieczne jest określenie, jakie prawdopodobieństwo można uznać za znikome. W kryptografii zwyczajowo uważa się za takie prawdopodobieństwo, że dla dowolnego wielomianu p i dla wszystkich wystarczająco dużych n nie przekracza 1/p(n), gdzie u jest parametrem bezpieczeństwa. Tak więc, w obecności wszystkich powyższych definicji, problem uzasadnienia bezpieczeństwa schematu kryptograficznego został zredukowany do wykazania braku algorytmu wielomianowego, który rozwiązuje problem stojący przed przeciwnikiem. Ale tutaj pojawia się kolejna i bardzo poważna przeszkoda: najnowocześniejszy Teoria złożoności obliczeniowej nie pozwala na udowodnienie superwielomianowych dolnych granic złożoności dla konkretnych problemów rozpatrywanej klasy. Wynika z tego, że w tej chwili siłę schematów kryptograficznych można ustalić tylko przy zaangażowaniu pewnych niesprawdzonych założeń. Dlatego głównym kierunkiem badań jest poszukiwanie najsłabszych warunków wystarczających (idealnie koniecznych i wystarczających) dla istnienia stabilnych schematów każdego typu. 28 Rozdział 2 Zasadniczo rozważane są dwa rodzaje założeń - ogólne (lub teoretyka złożoności) i teoria liczb, czyli założenia dotyczące złożoności konkretnych problemów teorii liczb. Wszystkie te założenia w literaturze nazywa się zwykle kryptografią. Poniżej krótko rozważymy kilka interesujących obiektów matematycznych, które powstały na skrzyżowaniu teorii złożoności i kryptografii. Więcej szczegółowy przegląd na te tematy można znaleźć w książce. 2. Kryptografia i hipoteza Z reguły znajomość niespecjalistycznych matematyków z teorią złożoności obliczeniowej ogranicza się do klas P i NP oraz słynnej hipotezy Przypomnijmy pokrótce niezbędne informacje z teorii złożoności obliczeniowej. Niech?* będzie zbiorem wszystkich skończonych łańcuchów w alfabecie binarnym S = (0,1). Podzbiory L C S* w teorii złożoności są zwykle nazywane językami. Mówi się, że maszyna Turinga M działa w czasie wielomianowym (lub po prostu, że jest wielomianem), jeśli istnieje wielomian p taki, że na dowolnym słowie wejściowym o długości n maszyna M zatrzymuje się po wykonaniu nie więcej niż p(n) operacji . Maszyna Turinga M rozpoznaje (lub akceptuje) język L, jeżeli przy każdym słowie wejściowym x E L, maszyna M zatrzymuje się w stanie akceptującym, a przy każdym słowie x $ L, w stanie odrzucającym. Klasa P to klasa wszystkich języków rozpoznawanych przez maszyny Turinga działające w czasie wielomianowym. Funkcja / : 2* -> 2* jest obliczalna w czasie wielomianowym, jeśli istnieje wielomianowa maszyna Turinga taka, że ​​jeśli słowo x E? Język L należy do klasy NP, jeśli orzeczenie P(x, y) : S* x S* -? (0,1) obliczalna w czasie wielomianu i wielomianu p takim, że L = (x\3yP(x, y)&i\y\ ^ p(|z|)). Tak więc język L należy do NP, jeśli dla dowolnego słowa w L o długości n można odgadnąć jakiś ciąg wielomianu długości w n, a następnie, używając predykatu P, sprawdzić, czy odgadnięcie jest poprawne. Oczywiste jest, że PC NP. To, czy to włączenie jest ścisłe, jest jednym z najbardziej znanych nierozwiązanych problemów w matematyce. Większość ekspertów uważa, że ​​jest ona ścisła (tzw. hipoteza P^NP). W klasie NP wyodrębniono podklasę języków maksymalnie złożonych, zwaną NP-zupełną: każdy język NP-zupełny jest rozpoznawalny w czasie wielomianowym wtedy i tylko wtedy, gdy P=NP. W tym celu będziemy potrzebować również pojęcia probabilistycznej maszyny Turinga. W zwykłych maszynach Turinga (nazywa się je deterministyczno-deterministycznymi, aby odróżnić je od probabilistycznych), nowy stan, w który maszyna przechodzi w następnym kroku, jest całkowicie określony przez stan bieżący i symbol, że głowica na taśmie jest oglądanie. W maszynach probabilistycznych nowy stan może również zależeć od zmiennej losowej, która przyjmuje wartości 0 i 1 z prawdopodobieństwem 1/2. Alternatywnie, kryptografia i teoria złożoności 29 może uznać, że probabilistyczna maszyna Turinga ma dodatkową losową taśmę, na której zapisany jest nieskończony binarny ciąg losowy. Taśmę losową można odczytać tylko w jednym kierunku, a przejście do nowego stanu może zależeć od postaci oglądanej na tej taśmie. Rozważmy teraz następujące naturalne pytanie: czy hipoteza P^NP nie jest koniecznym i wystarczającym warunkiem istnienia silnych schematów kryptograficznych? Potrzeba jest rzeczywiście w wielu przypadkach niemal oczywista. Wróćmy do przykładu 1. Zdefiniuj następujący język L = ((Ki,d,i)\ jest komunikat m taki, że Ek(m) = d i jego i-ty bit to 1). Oczywiste jest, że L? NP: zamiast wyczerpującego wyszukiwania opisanego we wstępie można po prostu odgadnąć tekst jawny m i sprawdzić w czasie wielomianu-wielomianu, że Efdim) = d i i-ty bit m jest równy 1. Jeśli tak, to słowo wejściowe (Ki,d,i) jest akceptowane, w przeciwnym razie jest odrzucane. Przy założeniu P=NP istnieje deterministyczny algorytm wielomianowo-wielomianowy, który rozpoznaje język L. Znając K\ i d, algorytm ten może być użyty do sekwencyjnego obliczania bit po bicie tekstu jawnego rn. Tym samym kryptosystem jest niestabilny. To samo podejście: odgadnij tajny klucz i sprawdź (w czasie wielomianowo-wielomianowym) poprawność odgadnięcia, ma zasadniczo zastosowanie do innych schematów kryptograficznych. Jednak w niektórych przypadkach trudności techniczne wynikają z faktu, że zgodnie z informacjami, które posiada przeciwnik, żądana wartość (tekst jawny, tajny klucz itp.) nie jest jednoznacznie przywracana. Jeśli chodzi o pytanie o wystarczalność założenia P^NP, nasuwa się tu następujące podejście: wybierz jakiś problem NP-zupełny i zbuduj na jego podstawie schemat kryptograficzny, którego problemem łamania (tj. problemem stojącym przed przeciwnikiem) byłby NP -pełny. Takie próby zostały podjęte na początku lat 80., zwłaszcza w odniesieniu do kryptosystemów klucza publicznego, ale nie doprowadziły do ​​sukcesu. Wynikiem wszystkich tych prób było uświadomienie sobie następującego faktu: nawet jeśli P^NP, to każdy problem NP-zupełny może okazać się trudny tylko dla jakiegoś nieskończonego ciągu słów wejściowych. Innymi słowy, definicja klasy NP zawiera miarę złożoności „najgorszego przypadku”. Dla stabilności schematu kryptograficzno-kryptograficznego konieczne jest, aby problem przeciwnika był trudny „prawie wszędzie”. W ten sposób stało się jasne, że dla bezpieczeństwa kryptograficznego potrzebne jest znacznie silniejsze założenie niż P^NP. Mianowicie założenie istnienia funkcji jednokierunkowych. 30 Rozdział 2 3. Funkcje jednokierunkowe Mówiąc nieformalnie, funkcja jednokierunkowa jest funkcją efektywnie obliczalną, dla której nie ma wydajnych algorytmów do odwrócenia. Przez inwersję rozumiemy ogromny problem znalezienia jednej (dowolnej) wartości z danej wartości funkcji z obrazu wstępnego (zauważ, że funkcja odwrotna, ogólnie rzecz biorąc, może nie istnieć). Funkcja -way ma kluczowe znaczenie w kryptografii matematycznej, poniżej podajemy jej formalną definicję. Niech E™ = (0,1)" będzie zbiorem wszystkich ciągów binarnych o długości n. Przez funkcję / rozumiemy rodzinę (/n), gdzie /" : E" -> Em, m = m,( n) Dla uproszczenia zakładamy, że n przebiega przez cały ciąg naturalny i że każda z funkcji /n jest wszędzie zdefiniowana. Funkcja / jest uczciwa jeśli istnieje wielomian q taki, że n $ C q(m(n)) dla wszystkich n Definicja 1. Uczciwa funkcja / jest jednostronna, jeśli 1. Istnieje algorytm wielomianowy, który oblicza f(x) dla dowolny x. 2. Dla dowolnej wielomianowej probabilistycznej maszyny Turinga A obowiązuje następująca zasada: Niech ciąg x zostanie wybrany losowo ze zbioru E" (oznaczony jako x € q X "). wielomian p i wszystkie wystarczająco duże n Pr(f(A(f(x))) = /(*))< l/p(n). Вероятность здесь определяется случайным выбором строки х и слу- случайными величинами, которые А использует в своей работе. Условие 2 качественно означает следующее. Любая полиномиальная вероятностная машина Тьюринга А может по данному у найти х из уравнения f(x) = у лишь с пренебрежимо малой вероятностью. Заметим, что требование честности нельзя опустить. Поскольку длина входного слова f(x) машины А равна т, ей может не хватить полиномиального (от т) времени просто на выписывание строки х, ес- если / слишком сильно «сжимает» входные значения. Ясно, что из предположения о существовании односторонних функ- функций следует, что P^NP. Однако, не исключена следующая ситуация: P^NP, но односторонних функций нет. Существование односторонних функций является необходимым ус- условием для стойкости многих типов криптографических схем. В неко- некоторых случаях этот факт устанавливается достаточно просто. Обра- Обратимся опять к примеру 1. Рассмотрим функцию / такую, что /(г) = К\. Она вычислима с помощью алгоритма G за полиномиальное время. По- Покажем, что если / - не односторонняя функция, то криптосистема Криптография и теория сложности 31 нестойкая. Предположим, что существует полиномиальный вероятност- вероятностный алгоритм Л, который инвертирует / с вероятностью по крайней мере 1/р(п) для некоторого полинома р. Здесь п - длина ключа К\. Противник может подать на вход алгоритму А ключ К\ и получить с указанной вероятностью некоторое значение г" из прообраза. Далее противник подает г" на вход алгоритма G и получает пару ключей (Ki,K2). Хотя К2 не обязательно совпадает с К^, тем не менее, по определению криптосистемы DK* {Екг (тп)) = m для любого открытого текста т. Поскольку К2 найден с вероятностью по крайней мере 1/р(п), которая в криптографии не считается пренебрежимо малой, криптоси- криптосистема нестойкая. Для других криптографических схем подобный результат доказы- доказывается не столь просто. В работе Импальяццо и Луби доказана не- необходимость односторонних функций для существования целого ряда стойких криптографических схем. Из всего сказанного следует, что предположение о существова- существовании односторонних функций является самым слабым криптографи- криптографическим предположением, которое может оказаться достаточным для доказательства существования стойких криптографических схем раз- различных типов. На выяснение того, является ли это условие и в са- самом деле достаточным, направлены значительные усилия специалистов. Трудность задачи построения криптографических схем из односто- односторонних функций можно пояснить на следующем примере. Пусть / - односторонняя функция и нам требуется построить криптосистему с секретным ключом. В такой криптосистеме имеется только один ключ - секретный, который известен и отправителю, и получателю шифрованного сообщения. Алгоритмы шифрования Ец и дешифро- дешифрования Dk оба зависят от этого секретного ключа К и таковы, что Dk(Ek(tti)) = т для любого открытого текста т. Ясно, что если кри- криптограмму d сообщения т вычислять как d = /(m), то противник, перехвативший d, может вычислить m лишь с пренебрежимо малой вероятностью. Но во-первых, непонятно, каким образом сможет вос- восстановить сообщение m из криптограммы законный получатель? Во- вторых, из того, что функция / односторонняя следует лишь, что про- противник не может вычислить все сообщение целиком. А это - весьма низкий уровень стойкости. Желательно, чтобы противник, знающий криптограмму d, не мог вычислить ни одного бита открытого тек- текста. На ten moment Wykazano, że istnienie funkcji jednokierunkowych jest warunkiem koniecznym i wystarczającym istnienia silnych kryptosystemów z tajnym kluczem, a także silnych kilku typów protokołów kryptograficznych, w tym protokołów podpisu elektronicznego. Z drugiej strony mamy wynik Impagliazzo i Rudicha, który jest dość mocnym argumentem, że niektóre rodzaje schematów kryptograficzno-kryptograficznych (w tym protokoły dystrybucji kluczy typu Diffie-Hellman) wymagają silniejszych założeń niż założenie. istnienie funkcji jednokierunkowych. Niestety, wynik ten jest zbyt skomplikowany, aby można go było wyjaśnić w tym rozdziale. 4. Generatory pseudolosowe Istotną wadą szyfru Vernama jest to, że klucze są jednorazowe. Czy można pozbyć się tej wady poprzez nieznaczne zmniejszenie trwałości? Jeden ze sposobów rozwiązania tego próbnego problemu jest następujący. Nadawca i odbiorca mają wspólny tajny klucz K o długości n i za pomocą wystarczająco wydajnego algorytmu q generują z niego ciąg r - q(K) o długości q(n), gdzie q jest jakimś wielomianem. Taki kryptosystem (oznaczamy go jako C r) pozwala zaszyfrować wiadomość m (lub zestaw wiadomości) o długości do q (n) bitów zgodnie ze wzorem d - r (B w, gdzie © jest bitowe dodanie ciągów bitów modulo 2. Deshi- Deszyfrowanie odbywa się według wzoru m = d φ r. Z wyników Shanno-Shannona wynika, że ​​taki kryptosystem nie jest całkowicie bezpieczny, tj. zabezpieczony przed jakimkolwiek adwersarzem (co jednak jest nietrudne do bezpośredniej weryfikacji).Co się stanie, jeśli trzeba będzie bronić się tylko przed wielomianowo ograniczonym przeciwnikiem, który może zaatakować kryptosystem tylko za pomocą wielomianowo-wielomianowych algorytmów probabilistycznych? Pytania te doprowadziły do ​​koncepcji generatora pseudolosowego , którą wprowadzili Blum i Micali. Niech q: (0,1) "-" (0,1)? n" będzie funkcją obliczalną w wielomianu (z p) czas. Taka funkcja nazywa się generatorem. Intuicyjnie generator q jest pseudolosowy, jeśli generowane przez niego ciągi są nie do odróżnienia przez dowolny wielomianowy algorytm weryfikacyjny od ciągów losowych o tej samej długości q(n). Formalnie obiekt ten jest zdefiniowany w następujący sposób. Niech A będzie wielomianową probabilistyczną maszyną Turinga, która otrzymuje jako wejście ciągi binarne o długości q(n) i wyprowadza jeden bit w wyniku działania. Niech P(A, n) = Pr(A(r) = 1|r jednostka (0, Kryptografia i teoria złożoności 33) Prawdopodobieństwo jest tutaj określone przez losowy wybór ciągu r i zmiennych losowych, których A używa w swoim Niech P2 (A,n) = Pr(A(g(s)) = l|e jednostki (0,1)"). Prawdopodobieństwo to jest określone przez losowy wybór wiersza s i zmiennych losowych, które A 2. Generator g nazywamy kryptograficznie bezpiecznym generatorem pseudolosowym, jeśli dla dowolnej wielomianowej probabilistycznej maszyny Turinga A, dla dowolnego wielomianu p i wszystkich wystarczająco dużych n \P,(A,n)-P2 (A, p)\<1/р(п). Всюду ниже мы для краткости будем называть криптографически стойкие псевдослучайные генераторы просто псевдослучайными гене- генераторами. Такое сокращение является общепринятым в криптографи- криптографической литературе. Нетрудно убедиться, что для существования псевдослучайных гене- генераторов необходимо существование односторонних функций. В самом деле, сама функция g должна быть односторонней. Доказательство это- этого простого факта мы оставляем читателю в качестве упражнения. Вопрос о том, является ли существование односторонних функций од- одновременно и достаточным условием, долгое время оставался откры- открытым. В 1982 г. Яо построил псевдослучайный генератор, исходя из предположения о существовании односторонних перестановок, т. е. сохраняющих длину взаимнооднозначных односторонних функций. За этим последовала серия работ, в которых достаточное условие все более и более ослаблялось, пока наконец в 1989-1990 гг. Импальяццо, Левин и Луби и Хостад не получили следующий окончательный резуль- результат. Теорема 1. Псевдослучайные генераторы существуют тогда и толь- только тогда, когда существуют односторонние функции. Псевдослучайные генераторы находят применение не только в крип- криптографии, но и в теории сложности, и в других областях дискретной математики. Обсуждение этих приложений выходит за рамки настоя- настоящей главы. Здесь же в качестве иллюстрации мы рассмотрим описан- описанную в начале данного раздела криптосистему Сг, использующую псев- псевдослучайный генератор в качестве алгоритма д. Прежде всего, нам необходимо дать определение стойкости криптосистемы с секретным ключом. Пусть Ец - алгоритм шифрования криптосистемы с секретным ключом. Обозначим результат его работы d = Ек(т), здесь К - се- секретный ключ длиной п битов, am - открытый текст длиной q(n) 34 Глава 2 битов. Через т* обозначается г-ый бит открытого текста. Пусть А - полиномиальная вероятностная машина Тьюринга, которая получает на вход криптограмму d и выдает пару (г,сг), где г б {1,.. .,q(n)}, а б {0,1}. Интуитивно, криптосистема является стойкой, если ника- никакая машина Тьюринга А не может вычислить ни один бит открытого текста с вероятностью успеха, существенно большей, чем при простом угадывании. Определение 3. Криптосистема называется стойкой, если для лю- любой полиномиальной вероятностной машины Тьюринга А, для любого полинома р и всех достаточно больших п Pr{A(d) = (г,а)ка = пц\Кен {0,1}", т 6д {0,1}*<п)} < J + ~. 2 р(п) Эта вероятность (всюду ниже для краткости мы ее обозначаем про- просто Рг) определяется случайным выбором секретного ключа К, слу- случайным выбором открытого текста т из множества всех двоичных строк длины q(n) и случайными величинами, которые А использует в своей работе. Покажем, что криптосистема Сг с псевдослучайным генератором в качестве д является стойкой в смысле данного определения. Предполо- Предположим противное, т. е. что существуют полиномиальный вероятностный алгоритм А и полином р такие, что Рг ^ 1/2 + 1/р(п) для бесконечно многих п. Рассмотрим алгоритм В, который получает на входе двоич- двоичную строку г длины 0, q - ze zbioru wszystkich takich dzielników pierwszych liczby p - 1, q - ze zbioru wszystkich liczb q takich, że q9 = 1 mod p, a x ∈ Zg. Wtedy funkcja f(x, p, q, g) = (gx mod p, p, q, q) jest jednokierunkowa (patrz rozdział 2). Zalecana

Książki. Pobierz książki DJVU, PDF za darmo. Bezpłatna biblioteka elektroniczna
W.W. Jaszczenko, Wprowadzenie do kryptografii

Możesz (program zaznaczy to na żółto)
Możesz zobaczyć listę książek o matematyce wyższej posortowaną alfabetycznie.
Możesz zobaczyć listę książek o wyższej fizyce posortowaną alfabetycznie.

• Bezpłatne pobieranie książki, objętość 1,69 Mb, format .djvu
Wydanie drugie, wyd. Yashchenko V.V., wrzesień 1999

Panie i Panowie!! Aby pobrać pliki publikacji elektronicznych bez „błędów”, kliknij podkreślony link z plikiem Prawy przycisk myszy, wybierz polecenie "Zapisz cel jako ..." ("Zapisz cel jako...") i zapisz plik e-pub na lokalnym komputerze. Publikacje elektroniczne są zazwyczaj w formatach Adobe PDF i DJVU.

Rozdział 1. Podstawowe pojęcia kryptografii
1. Wstęp
2. Przedmiot kryptografii
3. Podstawy matematyczne
4. Nowe kierunki
5. Wniosek

Rozdział 2. Kryptografia i teoria złożoności
1. Wstęp
2. Kryptografia i hipoteza
3. Funkcje jednokierunkowe
4. Generatory pseudolosowe
5. Dowody wiedzy zerowej

Rozdział 3 Protokoły kryptograficzne
1. Wstęp
2. Uczciwość. Protokoły uwierzytelniania i podpisu elektronicznego
3. Nie do wyśledzenia. Pieniądz elektroniczny
4. Protokoły typu „rzucanie monetą przez telefon”
5. Jeszcze raz o dzieleniu się sekretem
6. Zagrajmy w „kubki”. Protokoły głosowania
7. Poza standardowymi założeniami. Poufne wiadomości
8. Zamiast konkluzji

Rozdział 4
1. Wstęp
2. System szyfrowania RSA
3. Złożoność algorytmów teorii liczb
4. Jak odróżnić liczbę złożoną od liczby pierwszej?
5. Jak zbudować duże liczby pierwsze
6. Jak przetestować dużą liczbę pod kątem pierwszości?
7. Jak rozkładać liczby złożone na czynniki?
8. Dyskretny logarytm
9. Wniosek

Rozdział 5. Matematyka dzielenia się tajemnicą
1. Wstęp
2. Udostępnianie tajne dla arbitralnych struktur dostępu
3. Liniowe udostępnianie sekretów
4. Idealne udostępnianie sekretów i matroidy

Rozdział 6
1. Zamiast wstępu
2. Trochę teorii
3. Jak zaszyfrować plik?
4. Ucz się na błędach innych
5. Zamiast konkluzji

Rozdział 7
1. Wstęp
2. Szyfry podstawieniowe
3. Szyfry permutacyjne
4. Wieloalfabetyczne szyfry podstawieniowe z kluczem okresowym
5. Uwarunkowania problemów olimpiad z matematyki i kryptografii
6. Kierunki i decyzje

Dodatek: fragment artykułu K. Shannona „Teoria komunikacji w systemach tajnych”

Krótkie streszczenie książki

Poniżej sumy wyd. V.V.Yashchenko. Autorzy: V. V. Yashchenko (redaktor, rozdział 1), N. P. Varnovsky (rozdziały 2, 3), Yu. V. Nesterenko (rozdział 4), G. A. Kabatyansky (rozdział 5), P. N Devyanin, V. G. Proskurin, A. V. Cheremushkin (rozdział 6 ), P. A. Gyrdymov, A. Yu. Zubov, A. V. Zyazin, V. N. Ovchinnikov (rozdział 7).

Książka, po raz pierwszy w języku rosyjskim, przedstawia systematyczną prezentację naukowych podstaw kryptografii od najprostszych przykładów i podstawowych pojęć po współczesne konstrukcje kryptograficzne. Zrozumienie zasad kryptografii stało się dla wielu koniecznością ze względu na powszechne stosowanie narzędzi bezpieczeństwa informacji kryptograficznych. Dlatego książka może być przydatna dla ogólnego czytelnika. Książka przeznaczona jest dla studentów matematyki i specjalistów ds. bezpieczeństwa informacji.

Kryptografia – nauka o szyfrach – była przez długi czas utajniona, ponieważ służyła głównie do ochrony tajemnic państwowych i wojskowych. Obecnie metody i środki kryptografii wykorzystywane są do zapewnienia bezpieczeństwa informacji nie tylko państwa, ale także osób i organizacji. Niekoniecznie jest to kwestia tajemnic. Zbyt wiele różnych informacji „krąży” po świecie w formie cyfrowej. A ponad tymi informacjami są groźby nieprzyjaznej znajomości, akumulacji, podmiany, fałszerstwa itp. To właśnie kryptografia dostarcza najbardziej niezawodnych metod ochrony przed takimi zagrożeniami.

Do tej pory algorytmy kryptograficzne dla przeciętnego konsumenta to tajemnica z siedmioma pieczęciami, choć wielu musiało już korzystać z niektórych narzędzi kryptograficznych: szyfrowania wiadomości e-mail, inteligentnych kart bankowych itp. Oczywiście głównym pytaniem dla użytkownika jest to, czy to narzędzie kryptograficzne zapewnia niezawodna ochrona. Ale nawet poprawne sformułowanie tego podstawowego pytania nie jest łatwe. Przed jakim wrogiem się bronimy? Jakie są opcje dla tego wroga? Jakie cele może realizować? Jak zmierzyć niezawodność ochrony? Lista takich pytań może być kontynuowana. Aby na nie odpowiedzieć, użytkownik potrzebuje znajomości podstawowych pojęć kryptografii.

Celem tej książki jest popularna ekspozycja naukowych podstaw kryptografii (mówimy tylko o kryptografii „niepaństwowej”; sekcje kryptografii związane z bezpieczeństwem państwa powinny pozostać tajne). Może służyć również jako pomoc dydaktyczna. Nie ma jeszcze podobnych książek w języku rosyjskim. Materiały kilku rozdziałów zostały opublikowane przez autorów wcześniej w innych publikacjach (rozdział 1 - w książce S. A. Dorichenko, V. V. Yashchenko, „25 badań nad szyframi”, M.: TEIS, 1994; rozdziały 1,2,4 ,5 - w czasopiśmie "Edukacja Matematyczna", seria trzecia, nr 2, M.: MTsNMO, 1998; rozdział 7 - w gazecie "Informatika" (dodatek tygodniowy do gazety "Pervoe wrzesień"), N 4, styczeń 1998 ). Przygotowując to wydanie, materiały te zostały poprawione i uzupełnione. Prezentacja materiału przeznaczona jest dla czytelnika o matematycznym sposobie myślenia.

W większości rozdziały są od siebie niezależne (osiąga się to poprzez pewne powtórzenia) i można je czytać w dowolnej kolejności. Rozdział 1 – wprowadzający – jest zalecany do przeczytania przez wszystkich, ponieważ wyjaśnia wszystkie podstawowe pojęcia współczesnej kryptografii na popularnym poziomie: szyfr, klucz, bezpieczeństwo, elektroniczny podpis cyfrowy, protokół kryptograficzny itp. W innych rozdziałach część materiału powtarza się, ale głębiej. Rozdziały 2, 3, 4, 5 wykorzystują niektóre informacje z matematyki wyższej znane uczniom klas matematycznych i studentom. Rozdział 6 jest skierowany do ekspertów w dziedzinie technologii komputerowych. Rozdział 7 zawiera materiały do ​​olimpiad kryptograficznych dla dzieci w wieku szkolnym, dlatego do jego przeczytania nie jest wymagana wiedza wykraczająca poza program szkolny.

Ostrzeżenie: Narzędzia i oprogramowanie kryptograficzne wymienione w tej książce służą wyłącznie do zilustrowania ogólnych idei kryptograficznych; autorzy nie mieli na celu oceny ani porównania dostępnych na rynku narzędzi kryptograficznych.

Kryptografia została postawiona na podstawach naukowych w dużej mierze dzięki pracy wybitnego amerykańskiego naukowca Claude'a Shannona. Jego raport „Matematyczna teoria kryptografii” został przygotowany potajemnie w 1945 r., odtajniony i opublikowany w 1948 r., przetłumaczony na rosyjski w 1963 r. Od kiedy „Prace o teorii informacji i cybernetyce” (1963) C. Shannona stały się rzadkością bibliograficzną, włączyliśmy w załączniku główna część artykułu K. Shannona „Teoria komunikacji w systemach tajnych”. Ta przełomowa praca jest polecana do przeczytania dla wszystkich zainteresowanych kryptografią.

Do profesjonalnego zrozumienia algorytmów kryptograficznych i umiejętności oceny ich mocnych i słabych stron wymagane jest poważne szkolenie matematyczne (na poziomie wydziałów matematycznych uniwersytetów). Wynika to z faktu, że współczesna kryptografia opiera się na głębokich wynikach takich działów matematyki, jak teoria złożoności obliczeń, teoria liczb, algebra, teoria informacji itp. Ci, którzy chcą poważnie studiować kryptografię, mogą polecić przeglądową monografię „Kryptografia w bankowości” Anokhin MI, Varnovsky N. P., Sidelnikova V. M., Yashchenko V. V., M.: MEPhI, 1997.

Jak przekazać niezbędne informacje niezbędnemu adresatowi w tajemnicy przed innymi? Każdy z czytelników w różnym czasie iz różnymi celami prawdopodobnie próbował sam rozwiązać ten praktyczny problem (dla wygody dalszych odniesień nazwiemy go „problemem TP”, czyli problemem Tajnej Transmisji). Po wybraniu odpowiedniego rozwiązania najprawdopodobniej powtórzył wynalezienie jednej z metod tajnego przekazywania informacji, która ma już ponad tysiąc lat.

Zastanawiając się nad problemem TP, nietrudno dojść do wniosku, że istnieją trzy możliwości.
1. Stwórz absolutnie niezawodny kanał komunikacji między subskrybentami, niedostępny dla innych.
2. Korzystaj z publicznego kanału komunikacji, ale ukrywaj sam fakt przekazywania informacji.
3. Korzystać z publicznego kanału komunikacji, ale przekazywać za jego pośrednictwem niezbędne informacje w tak przekształconej formie, aby tylko adresat mógł je przywrócić.

Skomentuj te trzy możliwości.
1. Przy obecnym poziomie rozwoju nauki i technologii prawie niemożliwe jest stworzenie takiego kanału komunikacji między zdalnymi abonentami w celu wielokrotnego przesyłania dużych ilości informacji.
2. Steganografia zajmuje się opracowywaniem środków i metod ukrywania faktu przekazywania wiadomości.

Pierwsze ślady metod steganograficznych giną już w starożytności. Znany jest np. taki sposób ukrywania wiadomości pisanej: ogolono głowę niewolnika, na głowie napisano wiadomość, a po odrośnięciu włosów niewolnika wysłano do adresata. Z prac detektywistycznych dobrze znane są różne metody tajnego pisania między wierszami zwykłego, niezabezpieczonego tekstu: od mleka po złożone odczynniki chemiczne z późniejszym przetwarzaniem.

Metodę „mikrodoty” znamy też z detektywów: wiadomość jest zapisywana przy użyciu nowoczesnej technologii na bardzo małym nośniku (mikrodocie), który wysyłany jest zwykłym listem, na przykład pod znaczkiem lub w innym, z góry określonym miejscu.

Obecnie, ze względu na powszechne stosowanie komputerów, znanych jest wiele subtelnych metod „ukrywania” chronionych informacji w dużych ilościach informacji przechowywanych na komputerze. Obrazowy przykład ukrywania pliku tekstowego w grafice można znaleźć w Internecie; jest on również podany w czasopiśmie Computerra, N48 (225) z 1 grudnia 1997 r., na stronie 62. (Należy zauważyć, że autorzy artykułu w czasopiśmie błędnie odnoszą steganografię do tekstów kryptograficznych, ale ogólnie rzecz biorąc, steganografia i kryptografia to zasadniczo różne obszary w teorii i praktyce bezpieczeństwa informacji.)

3. Kryptografia zajmuje się opracowywaniem metod konwersji (szyfrowania) informacji w celu ich ochrony przed nielegalnymi użytkownikami. Takie metody i sposoby przetwarzania informacji nazywamy szyframi.

Szyfrowanie (szyfrowanie) to proces stosowania szyfru do chronionych informacji, tj. Konwersja chronionych informacji (zwykły tekst) na zaszyfrowaną wiadomość (zaszyfrowany tekst, kryptogram) przy użyciu określonych reguł zawartych w szyfrze.

Deszyfrowanie to proces będący odwrotnością szyfrowania, czyli konwersją zaszyfrowanej wiadomości na informacje chronione przy użyciu określonych reguł zawartych w szyfrze.

Kryptografia jest nauką stosowaną, wykorzystuje najnowsze osiągnięcia nauk podstawowych, a przede wszystkim matematyki. Z drugiej strony, wszystkie specyficzne zadania kryptografii zależą zasadniczo od poziomu rozwoju technologii i technologii, wykorzystywanych środków komunikacji i sposobów przekazywania informacji.

Przedmiot kryptografii. Jaki jest przedmiot kryptografii? Aby odpowiedzieć na to pytanie, wróćmy do problemu TP w celu wyjaśnienia sytuacji i użytych pojęć. Przede wszystkim zauważamy, że ten problem pojawia się tylko w przypadku informacji wymagających ochrony. Zwykle w takich przypadkach mówi się, że informacja zawiera tajemnicę lub jest chroniona, prywatna, poufna, tajna. Dla najbardziej typowych, często spotykanych sytuacji tego typu wprowadzono nawet specjalne pojęcia:
- tajemnica państwowa;
- tajemnica wojskowa;
- tajemnica handlowa;
- tajemnica prawna;
- tajemnica medyczna itp.

Dalej porozmawiamy o informacjach chronionych, pamiętając o następujących cechach takich informacji:
- istnieje pewien krąg legalnych użytkowników, którzy mają prawo do posiadania tych informacji;
- istnieją nielegalni użytkownicy, którzy starają się zdobyć te informacje w celu wykorzystania ich dla własnej korzyści i ze szkodą dla legalnych użytkowników.

Książki, pobieranie książek, pobieranie książek, książki online, czytanie online, pobieranie książek za darmo, czytanie książek, czytanie książek online, czytanie, biblioteka online, czytanie książek, czytanie online za darmo, czytanie książek za darmo, ebook, czytanie książek online, najlepsze książki matematyka i fizyka, ciekawe książki matematyka i fizyka, e-książki, książki do pobrania za darmo, książki do pobrania za darmo, książki do pobrania za darmo matematyka i fizyka, całkowicie za darmo pobierz książki, biblioteka online, książki do pobrania za darmo, czytaj książki online za darmo bez rejestracji matematyka i fizyka, czytaj książki online za darmo matematyka i fizyka, elektroniczna biblioteka matematyki i fizyki, książki do czytania matematyka i fizyka online, świat książek matematyka i fizyka, czytaj matematykę i fizykę za darmo, biblioteka matematyki i fizyki online, czytanie książek matematyka i fizyka, książki online za darmo matematyka i fizyka, popularne książki matematyka i fizyka, biblioteka bezpłatnych książek matematyka i fizyka, pobierz elektr. bezpłatna książka do matematyki i fizyki, bezpłatna biblioteka do matematyki i fizyki online, e-książki do pobrania, podręczniki do matematyki i fizyki online, biblioteka e-książek do matematyki i fizyki, e-książki do pobrania za darmo bez rejestracji matematyka i fizyka, dobre książki do matematyki i fizyki, pobierz pełne książki matematyka i fizyka, elektroniczna biblioteka czytaj za darmo matematyka i fizyka, elektroniczna biblioteka do pobrania za darmo matematyka i fizyka, strony do pobierania książek matematyka i fizyka, inteligentne książki matematyka i fizyka, szukaj książek matematyka i fizyka, pobierz e-książki za darmo matematyka i fizyki, e-book do pobrania matematyka i fizyka, najlepsze książki o matematyce i fizyce, elektroniczna biblioteka bezpłatnej matematyki i fizyki, czytaj online bezpłatne książki o matematyce i fizyce, witryna z książkami o matematyce i fizyce, biblioteka elektroniczna, książki online do czytać, książka o elektronicznej matematyce i fizyce, strona do pobierania książek za darmo i bez rejestracji , bezpłatną bibliotekę internetową matematyki i fizyki, z której można bezpłatnie pobrać książki z matematyki i fizyki, czytać książki za darmo i bez rejestracji matematyka i fizyka, pobrać podręczniki do matematyki i fizyki, pobrać bezpłatne e-podręczniki z matematyki i fizyki, pobierz całkowicie darmowe książki, biblioteka online za darmo, najlepsze e-książki matematyka i fizyka, biblioteka online książek matematyki i fizyki, pobierz e-książki za darmo bez rejestracji, biblioteka online do pobrania za darmo, skąd pobrać darmowe książki, e- biblioteki za darmo, e-książki za darmo, darmowe e-biblioteki, biblioteka online za darmo, książki za darmo do czytania, książki online za darmo do czytania, czytać za darmo online, ciekawe książki do czytania matematyka i fizyka online, czytanie książek online matematyka i fizyka, elektroniczna biblioteka online matematyka i fizyka, bezpłatna biblioteka książek elektronicznych matematyka i fizyka, biblioteka online do czytania, czytania za darmo i bez rejestracji i matematyki i fizyki, znajdź książkę z matematyki i fizyki, katalog książek z matematyki i fizyki, pobierz książki online za darmo matematyka i fizyka, biblioteka online matematyki i fizyki, pobierz bezpłatne książki bez rejestracji matematyka i fizyka, skąd możesz pobrać darmowe książki z matematyki i fizyki, z których można pobierać książki, witryny do bezpłatnego pobierania książek, online do czytania, biblioteka do czytania, książki do czytania online za darmo bez rejestracji, biblioteka książek, bezpłatna biblioteka online, biblioteka online do czytania za darmo , książki do czytania za darmo i bez rejestracji, elektroniczna biblioteka do pobierania książek za darmo, czytanie online jest bezpłatne.

,
Od 2017 roku wznawiamy mobilną wersję serwisu na telefony komórkowe (skrócony projekt tekstu, technologia WAP) - górny przycisk w lewym górnym rogu strony. Jeśli nie masz dostępu do Internetu za pośrednictwem komputera osobistego lub terminala internetowego, możesz skorzystać z telefonu komórkowego, aby odwiedzić naszą stronę internetową (projekt skrócony) i w razie potrzeby zapisać dane ze strony internetowej w pamięci telefonu komórkowego. Zapisuj książki i artykuły na swój telefon komórkowy (mobilny internet) i pobieraj je z telefonu na komputer. Wygodne pobieranie książek przez telefon komórkowy (do pamięci telefonu) oraz na komputer przez interfejs mobilny. Szybki Internet bez zbędnych tagów, za darmo (w cenie usług internetowych) i bez haseł. Materiał jest udostępniany do wglądu. Bezpośrednie linki do plików książek i artykułów na stronie oraz ich sprzedaż przez osoby trzecie jest zabronione.

Notatka. Wygodny link tekstowy do forów, blogów, cytowania materiałów na stronie, kod html można skopiować i po prostu wkleić na swoje strony internetowe podczas cytowania materiałów z naszej strony. Materiał jest udostępniany do wglądu. Zapisuj również książki na telefon komórkowy przez Internet (istnieje wersja mobilna strony - link znajduje się w lewym górnym rogu strony) i pobieraj je z telefonu na komputer. Bezpośrednie linki do plików książek są zabronione.

Książka, po raz pierwszy w języku rosyjskim, przedstawia systematyczną prezentację naukowych podstaw kryptografii od najprostszych przykładów i podstawowych pojęć po współczesne konstrukcje kryptograficzne. Zrozumienie zasad kryptografii stało się dla wielu koniecznością ze względu na powszechne stosowanie narzędzi bezpieczeństwa informacji kryptograficznych. Dlatego książka może być przydatna dla ogólnego czytelnika.
Książka przeznaczona jest dla studentów matematyki i specjalistów ds. bezpieczeństwa informacji.

Przedmiot kryptografii.
Jaki jest przedmiot kryptografii? Aby odpowiedzieć na to pytanie, wróćmy do problemu TP w celu wyjaśnienia sytuacji i użytych pojęć.

Przede wszystkim zauważamy, że ten problem pojawia się tylko w przypadku informacji wymagających ochrony. Zwykle w takich przypadkach mówi się, że informacja zawiera tajemnicę lub jest chroniona, prywatna, poufna, tajna. Dla najbardziej typowych, często spotykanych sytuacji tego typu wprowadzono nawet specjalne pojęcia:
- tajemnica państwowa;
- tajemnica wojskowa;
- tajemnica handlowa;
- tajemnica prawna;
- tajemnica medyczna itp.

Dalej porozmawiamy o informacjach chronionych, pamiętając o następujących cechach takich informacji:
- istnieje pewien krąg legalnych użytkowników, którzy mają prawo do posiadania tych informacji;
- istnieją nielegalni użytkownicy, którzy starają się zdobyć te informacje w celu. aby wykorzystać je dla własnych korzyści i ze szkodą dla legalnych użytkowników.

Dla uproszczenia najpierw ograniczymy się do rozważenia tylko jednego zagrożenia – groźby ujawnienia informacji. Istnieją inne zagrożenia dla informacji chronionych przed nielegalnymi użytkownikami: substytucja, imitacja itp. Omówimy je poniżej.

Spis treści
Przedmowa
Rozdział 1. Podstawowe pojęcia kryptografii
§jeden. Wstęp
§2. Przedmiot kryptografii
§3. Podstawy matematyczne
§4. Nowe kierunki
§5. Wniosek
Rozdział 2. Kryptografia i teoria złożoności
§jeden. Wstęp
§2. Kryptografia i hipoteza P = NP
§3. Funkcje jednokierunkowe
§4. Generatory pseudolosowe
§5. Dowody o zerowej wiedzy
Rozdział 3 Protokoły kryptograficzne
§jeden. Wstęp
§2. Uczciwość. Protokoły uwierzytelniania i podpisu elektronicznego
§3. Niewykrywalność. Pieniądz elektroniczny
§4. Protokoły rzutu monetą
§5. Więcej o dzieleniu się sekretem
§6. Zagrajmy w kości. Protokoły głosowania
§7. Poza standardowymi założeniami. Poufne wiadomości
§osiem. Zamiast konkluzji
Rozdział 4
§jeden. Wstęp
§2. System szyfrowania RSA
§3. Złożoność algorytmów teorii liczb
§4. Jak odróżnić liczbę złożoną od liczby pierwszej?
§5. Jak budować duże liczby pierwsze
§6. Jak sprawdzić, czy duża liczba jest liczbą pierwszą?
§7. Jak rozkładać liczby złożone na czynniki?
§osiem. Dyskretny logarytm
§9. Wniosek
Rozdział 5. Matematyka dzielenia się tajemnicą
§jeden. Wstęp
§2. Udostępnianie tajne dla arbitralnych struktur dostępu
§3. Liniowe udostępnianie sekretów
§4. Idealne oddzielenie sekretu i matroidu
Rozdział 6
§jeden. Zamiast wstępu
§2. Trochę teorii
§3. Jak zaszyfrować plik?
§4. Uczmy się na błędach innych
§5. Zamiast konkluzji
Rozdział 7
§jeden. Wstęp
§2. Szyfry podstawieniowe
§3. Szyfry permutacyjne
§4. Wieloalfabetyczne szyfry podstawieniowe z kluczem okresowym
§5. Uwarunkowania problemów olimpiad z matematyki i kryptografii
§6. Kierunki i rozwiązania
Dodatek A. Fragment artykułu K. Shannona „Teoria komunikacji w systemach tajnych”
Dodatek B. Lista zalecanych lektur z adnotacjami
Załącznik B. Słownik terminów kryptograficznych
Indeks alfabetyczny terminów rosyjskich
Indeks alfabetyczny terminów angielskich.

Pobierz bezpłatnie e-booka w wygodnym formacie, obejrzyj i przeczytaj:
Pobierz książkę Wprowadzenie do kryptografii, Yaschenko V.V., 2012 - fileskachat.com, szybkie i bezpłatne pobieranie.

Ściągnij PDF
Poniżej możesz kupić tę książkę w najlepszej obniżonej cenie z dostawą na terenie całej Rosji.

W kryptografii przez losową liczbę pierwszą rozumie się liczbę pierwszą zawierającą określoną liczbę bitów w notacji binarnej, na algorytm generowania nałożone są pewne ograniczenia. Uzyskiwanie losowych liczb pierwszych to ... ... Wikipedia

Martin Hellman Martin Hellman (Martin E. Hellman; ur. 2 października 1945) to amerykański kryptograf. Zyskał sławę dzięki opracowaniu pierwszego asymetrycznego kryptosystemu we współpracy z Whitfieldem Diffie i Ralphem Merklem (1976). Jeden z ... ... Wikipedii

Niemiecka kryptomaszyna Lorenz była używana podczas II wojny światowej do szyfrowania najbardziej tajnych wiadomości Kryptografia (z innych greckich ... Wikipedia

Niemiecka kryptomaszyna Lorenz była używana podczas II wojny światowej do szyfrowania najbardziej tajnych wiadomości Kryptografia (z greckiego κρυπτός ukryty i γράφω piszę) nauka o matematycznych metodach zapewnienia poufności ... ... Wikipedia

Faktoryzacja liczby naturalnej to jej rozkład na iloczyn czynników pierwszych. Istnienie i jednoznaczność (w kolejności czynników) takiej dekompozycji wynika z podstawowego twierdzenia arytmetyki. W przeciwieństwie do ... ... Wikipedii

Składa się z procedur zapewniających: włączenie użytkowników do systemu; generowanie, dystrybucja i wprowadzanie kluczy do urządzeń; kontrola użycia klucza; zmiana i zniszczenie kluczy; archiwizacja, przechowywanie i przywracanie kluczy ... ... Wikipedia

Ten artykuł musi zostać całkowicie przepisany. Na stronie dyskusji mogą znajdować się wyjaśnienia. Istnieją dwie klasy systemów komunikacyjnych: cyfrowe i analogowe ... Wikipedia

Liczba pierwsza to liczba naturalna, która ma dokładnie dwa różne dzielniki naturalne: jeden i samą siebie. Wszystkie inne liczby naturalne, z wyjątkiem jednej, nazywane są złożonymi. Tak więc wszystkie liczby naturalne są większe niż jeden ... ... Wikipedia

Probabilistyczny test pierwszości wielomianów. Test Millera Rabina pozwala skutecznie określić, czy dana liczba jest złożona. Nie można jej jednak użyć do rygorystycznego udowodnienia, że ​​liczba jest liczbą pierwszą. Niemniej jednak test Millera Rabina jest często ... ... Wikipedia

Test pierwszości to algorytm, który przy danej liczbie naturalnej określa, czy dana liczba jest liczbą pierwszą. Istnieją testy deterministyczne i probabilistyczne. Wyznaczenie prostoty danej liczby w ogólnym przypadku nie jest tak trywialnym zadaniem. Tylko ... ... Wikipedia

Tryb szyfrowania Metoda zastosowania szyfru blokowego do konwersji sekwencji zwykłych bloków danych na sekwencję zaszyfrowanych bloków danych. Jednocześnie dane z innego można wykorzystać do zaszyfrowania jednego bloku ... Wikipedia