Criptografia Yaschenko. Cartea: Iascenko V.V.

Sub total ed. V.V. Yashchenko INTRODUCERE ÎN CRIPTOGRAFIE Autori: V. V. Yashchenko (editor, capitolul 1), N. P. Varnovsky (capitolele 2, 3), Yu. V. Nesterenko (capitolul 4), G. A Kabatyansky (capitolul 5), P. N. Devyanin, G. Proskurin, V. A. V. Cheremushkin (Capitolul 6), P. A. Gyrdymov, A. Yu. Zubov, A. V. Zyazin, V. N Ovchinnikov (Capitolul 7). Pentru prima dată în limba rusă, cartea oferă o prezentare sistematică a fundamentelor științifice ale criptografiei de la cele mai simple exemple și concepte de bază până la construcții criptografice moderne. Înțelegerea principiilor criptografiei a devenit o necesitate pentru mulți datorită utilizării pe scară largă a instrumentelor de securitate a informațiilor criptografice. Prin urmare, cartea poate fi utilă cititorului general. Cartea este destinată studenților de la matematică și specialiști în securitatea informațiilor. Cuprins Prefaţă 5 Capitolul 1. Concepte de bază ale criptografiei 7 1. Introducere 7 2. Subiectul criptografiei. 8 3. Fundamente matematice 15 4. Noi direcții 18 5. Concluzie 23 Capitolul 2. Criptografia și teoria complexității 25 1. Introducere 25 2. Criptografia și conjectura P=/NP 28 3. Funcții unidirecționale 30 4. Generatori Pseudorandom 28 5. Dovezi cu cunoștințe zero 35 Capitolul 3. Protocoale criptografice 41 1. Introducere 41 2. Integritate. Protocoale de autentificare și semnatura electronica 44 3. Imposibil de urmărire. Bani electronici 60 4. Protocoale de aruncare a monedelor 67 5. Împărtășirea din nou a unui secret 72 6. Să jucăm zaruri. Protocoale de vot 76 7. Dincolo de ipotezele standard. Confidențial 81 Transmiterea mesajelor 8. În loc de o concluzie 84 Capitolul 4. Probleme algoritmice în teoria numerelor 86 1. Introducere 86 2. Sistemul de criptare RSA 88 3. Complexitatea algoritmilor teoretici ai numerelor 91 4. Cum să distingem un număr compus de un număr compus Număr prim 96 5. Cum se construiesc numere prime mari 99 6. Cum se testează un număr mare pentru caracterul prim 102 7. Cum se factorizează numerele compuse 107 8. Logaritm discret 110 9. Concluzie 115 Capitolul 5. Matematica partajării secrete 118 1. Introducere 118 2. Partajare secretă pentru structuri de acces arbitrare 120 3 Partajare liniară a secretelor 123 4. Partajare secretă ideală și matroizi 125 Capitolul 6. Computer și criptografie 130 1. În loc de o introducere. 130 2. Câteva teorii 132 3. Cum se criptează un fișier? 140 4. Să învățăm din greșelile altora 153 5. În loc de o concluzie 163 Capitolul 7. Olimpiade în criptografia pentru școlari 165 1. Introducere 166 2. Cifre de substituție 169 3. Cifre de permutare 182 4. Cifre de substituție periodică alfabetică190 4. 5. Condițiile problemelor olimpiadei în matematică și criptografie 198 6. Direcții și soluții 210 Anexă: un extras din articolul lui K. Shannon „Teoria comunicării în sistemele secrete” 15 4. Noi direcții 18 5. Concluzie 23 Capitolul 2. Criptografia și teoria complexității 25 1. Introducere 25 2. Criptografia și conjectura P^NP 28 3. Funcții unidirecționale 30 4. Generatoare pseudo-aleatorie 32 5. Demonstrații de cunoștințe zero 35 Capitolul 3 Protocoale criptografice 2 Introducere 41411. Integritate. Protocoale de autentificare și semnătură electronică 44 3. Trasabilitate. Bani electronici 60 4. Protocoale precum „aruncarea unei monede prin telefon” ... 67 5. Încă o dată despre împărtășirea unui secret 72 6. Să jucăm „zaruri”. Protocoale de vot 76 7. Dincolo de ipotezele standard. Mesaje confidențiale confidențiale 81 8. În loc de o concluzie 84 Capitolul 4. Probleme algoritmice în teoria numerelor 86 1. Introducere 86 2. Sistemul de criptare RSA 88 3. Complexitatea algoritmilor teoretici numeric 91 4. Cum să distingem un număr de un număr compus Număr prim 96 5. Cum se construiesc numere prime mari 99 6. Cum se testează un număr mare pentru caracterul prim 102 7. Cum se factorizează numerele compuse 107 8. Logaritm discret 110 9. Concluzie 115 Capitolul 5. Matematica partajării secrete 118 1. Introducere 118 2. Partajarea secretelor pentru structurile de acces arbitrare. . 120 3. Partajarea liniară a secretelor 123 4. Partajarea ideală a secretelor și matroizii 125 Capitolul 6. Calculatoare și criptografie 130 1. În loc de o introducere 130 2. O teorie 132 3. Cum se criptează un fișier? 140 4. Să învățăm din greșelile altora 153 5. În loc de o concluzie 163 Capitolul 7. Olimpiade în criptografia pentru școlari 165 1. Introducere 166 2. Cifre de substituție 169 3. Cifre de permutare 182 4. Cifre de substituție periodică alfabetică190 4. 5. Condiţiile problemelor olimpiadei la matematică şi criptografie. . 198 6. Direcții și decizii 210 Anexă: extras din articolul lui K. Shannon „Teoria comunicării în sistemele secrete” 235 Prefață la ediția a doua Această a doua ediție corectează erorile și inexactitățile tipografice observate în prima ediție. Septembrie 1999 V. Yashchenko Prefață la prima ediție Criptografia - știința cifrurilor - a fost clasificată de mult timp, deoarece a fost folosită în principal pentru a proteja secretele de stat și militare. În prezent, metodele și mijloacele de criptare sunt folosite pentru a asigura securitatea informațiilor nu numai a statului, ci și a persoanelor și organizațiilor. Aceasta nu este neapărat o chestiune de secrete. Prea multă informație „se plimbă” în toată lumea în formă digitală. Și deasupra acestor informații există amenințări de cunoaștere neprietenoasă, acumulare, înlocuire, falsificare etc. Criptografia este cea care oferă cele mai fiabile metode de protecție împotriva unor astfel de amenințări. Până acum, algoritmii criptografici pentru consumatorul mediu sunt un secret cu șapte sigilii, deși mulți au fost deja nevoiți să folosească unele instrumente criptografice: criptarea e-mailului, carduri bancare inteligente etc. Desigur, principala întrebare pentru utilizator este dacă acest instrument criptografic oferă protecţie fiabilă. Dar nici să formulezi corect această întrebare elementară, elementară, nu este ușor. De ce dușman ne apărăm? Care sunt posibilitățile acestui inamic? Ce obiective poate urmări? Cum se măsoară fiabilitatea protecției? Lista cu astfel de întrebări poate fi continuată. Pentru a le răspunde, utilizatorul are nevoie de cunoștințe despre conceptele de bază ale criptografiei. O prezentare populară a fundamentelor științifice ale criptografiei (vorbim doar despre criptografia „non-statală”; secțiunile criptografiei legate de securitatea statului ar trebui să rămână secrete) este scopul acestei cărți. Poate fi folosit și ca ajutor didactic. Nu există încă cărți similare în rusă. Materialele unui număr de capitole au fost publicate de autori mai devreme în alte publicații (capitolul 1 - în cartea lui S. A. Dorichenko, V. V. Yashchenko, „25 de studii asupra cifrurilor”, M .: TEIS, 1994; capitolele 1,2,4; , 5 - în revista „Educația matematică”, seria a treia, numărul 2, M.: MTsNMO, 1998; capitolul 7 - în ziarul „Informatică” (supliment săptămânal la ziarul „Pervoe septembrie”), nr. 4, ianuarie 1998). În pregătirea acestei ediții, aceste materiale au fost revizuite și completate. Prezentarea materialului este concepută pentru un cititor cu mentalitate matematică. În cea mai mare parte, capitolele sunt independente unele de altele (acest lucru se realizează printr-o anumită repetiție) și pot fi citite în orice ordine. Capitolul 1 - introductiv - este recomandat pentru toata lumea, deoarece explica la nivel popular toate conceptele de baza ale cripto-criptografiei moderne: cifru, cheie, securitate, semnatura digitala electronica, protocol cripto-criptografic etc. In alte capitole, o parte din material se repetă, dar deja mai în profunzime. Capitolele 2, 3, 4, 5 folosesc unele informații din matematica superioară cunoscute elevilor claselor de matematică și studenților. Capitolul 6 se adresează cunoscătorilor tehnologia calculatoarelor. Capitolul 7 conține materiale pentru olimpiadele de criptografie pentru școlari și, prin urmare, nu sunt necesare cunoștințe dincolo de programa școlară pentru a-l citi. Avertisment: Instrumentele criptografice și produsele software menționate în această carte sunt folosite doar pentru a ilustra idei criptografice generale; autorii nu și-au propus să evalueze sau să compare instrumentele criptografice disponibile pe piață. Criptografia a fost pusă pe o bază științifică, în mare parte datorită muncii remarcabilului om de știință american Claude Shannon. Raportul său „Teoria matematică a criptografiei” a fost întocmit într-o variantă secretă în 1945, desecretizat și publicat în 1948, tradus în rusă în 1963. De când „Lucrările despre teoria informației și cibernetica” A963) K. Shannon au devenit o raritate bibliografică, am au inclus în anexă partea principală a articolului lui K. Shannon „Teoria comunicării în sistemele secrete”. Această lucrare fundamentală este lectură recomandată pentru oricine este interesat de criptografie. Pentru o înțelegere profesională a algoritmilor criptografici și capacitatea de a le evalua punctele forte și părțile slabe este necesară o pregătire matematică deja serioasă (la nivelul departamentelor de matematică ale universităților). Acest lucru se datorează faptului că criptografia modernă se bazează pe rezultatele profunde ale unor ramuri ale matematicii precum teoria complexității calculelor, teoria numerelor, algebra, teoria informației etc. Cei care doresc să studieze serios criptografia pot recomanda monografia de revizuire. „Cryptography in Banking” de Anokhin M. And ., Varnovsky N. P., Sidelnikova V. M., Yashchenko V. V., M .: MEPhI, 1997. Octombrie 1998 V. Yashchenko Capitolul 1 Concepte de bază ale criptografiei 1. Introducere Cum se transferă informațiile necesare către destinatarul dorit în secret de alții? Fiecare dintre cititori, în momente diferite și cu scopuri diferite, probabil a încercat să rezolve singuri această problemă practică (pentru comoditatea referințelor ulterioare, o vom numi „problema TP”, adică problema transmisiei secrete). După ce a ales o soluție potrivită, cel mai probabil a repetat invenția uneia dintre metodele de transmitere secretă a informațiilor, care are mai mult de o mie de ani. Reflectând la problema TP, nu este greu să ajungem la concluzia că există trei posibilități. 1. Creați un canal de comunicare absolut fiabil între abonați, inaccesibil celorlalți. 2. Folosiți un canal de comunicare public, dar ascundeți însuși faptul transferului de informații. 3. Folosiți un canal de comunicare public, dar transmiteți prin acesta informațiile necesare într-o formă atât de transformată încât doar destinatarul să le poată restaura. Să comentăm aceste trei posibilități. 1. Cu nivelul actual de dezvoltare a științei și tehnologiei, este aproape imposibil să se realizeze un astfel de canal de comunicare între abonații la distanță pentru transmiterea repetată a unor cantități mari de informații. 2. Steganografia este angajată în dezvoltarea mijloacelor și metodelor de ascunderea faptului transmiterii unui mesaj. Primele urme ale metodelor steganografice se pierd în vremuri străvechi. De exemplu, o astfel de metodă de a ascunde un mesaj scris este cunoscută: capul unui sclav a fost bărbierit, a fost scris un mesaj pe scalp, iar după ce părul a crescut din nou, sclavul a fost trimis destinatarului. Din lucrările polițiste sunt binecunoscute diverse metode de scriere secretă între rândurile unui text obișnuit, neprotejat: de la lapte la reactivi chimici complecși cu prelucrare ulterioară. Metoda „microdot” este cunoscută și de la detectivi: un mesaj este înregistrat folosind tehnologia modernă pe un mediu foarte mic (microdot), care este trimis cu o scrisoare obișnuită, de exemplu, sub o ștampilă sau în alt loc, într-un loc prestabilit. În prezent, datorită utilizării pe scară largă a computerelor, există multe metode subtile de „ascundere” a informațiilor protejate în cantități mari de informații stocate într-un computer. Un exemplu vizual de ascundere a unui fișier text într-un fișier grafic poate fi găsit pe Internet1"; este dat și în revista Computerra, Nr. 48 B25) din 1 decembrie 1997, la pagina 62. (De remarcat că autorii articolului din steganografie sunt atribuiți în mod greșit criptografiei într-o revistă. Desigur, cu ajutorul steganografiei este posibil să ascundeți textele pre-criptate, dar, în general, steganografia și criptografia sunt domenii fundamental diferite în teorie și practica de securitate a informațiilor.) 3. Dezvoltarea metodelor de conversie (criptare) a informațiilor pentru a le proteja de utilizatorii ilegali, este angajată cripto-criptografia. Astfel de metode și metode de conversie a informațiilor se numesc cifruri. Criptarea (criptarea) este proces de aplicare a unui cifr la informațiile protejate, adică conversia informațiilor protejate (text simplu) într-un mesaj criptat (text cifrat, criptogramă) folosind anumite reguli conținute în cifr. Decriptarea este procesul invers al criptare, adică transformarea unui mesaj criptat în informații protejate folosind anumite reguli conținute în cifr. Criptografia este o știință aplicată, folosește cele mai recente realizări ale științelor fundamentale și, în primul rând, matematica. Pe de altă parte, toate sarcinile specifice criptografiei depind în mod esențial de nivelul de dezvoltare a tehnologiei și tehnologiei, de mijloacele de comunicare și de metodele de transfer de informații utilizate. 2. Subiectul criptografiei Care este subiectul criptografiei? Pentru a răspunde la această întrebare, să revenim la problema TP pentru a clarifica situația și conceptele folosite. În primul rând, observăm că această problemă apare doar pentru informațiile care trebuie protejate. De obicei, în astfel de cazuri se spune că informația conține un secret sau este protejată, privată, confidențială, secretă. Pentru situaţiile cele mai tipice, frecvent întâlnite de acest tip, au fost introduse chiar şi concepte speciale: - secret de stat; - un secret militar; ://www.geocities.com/SiliconValley/Vista/6001/ Concepte de bază ale criptografiei - secret comercial; - secretul juridic; - secretul medical, etc. În continuare, vom vorbi despre informații protejate, ținând cont de următoarele caracteristici ale acestor informații: - există un anumit cerc de utilizatori legitimi care au dreptul de a deține aceste informații; - exista utilizatori ilegali care cauta sa achizitioneze aceste informatii pentru a le valorifica in propriul beneficiu, si in detrimentul utilizatorilor legitimi. Pentru simplitate, ne vom limita mai întâi să luăm în considerare o singură amenințare - amenințarea dezvăluirii de informații. Există și alte amenințări la adresa informațiilor protejate de la utilizatorii ilegali: înlocuirea, imitarea etc. Despre ele vom vorbi mai jos. Acum putem descrie situația în care apare problema TP cu următoarea diagramă (vezi Fig. 1). DAR< т >B P Fig. 1. Aici A și B sunt utilizatori legitimi la distanță ai informațiilor protejate; doresc să facă schimb de informații printr-un canal de comunicare public. P - un utilizator ilegal (adversar) care poate intercepta mesajele transmise printr-un canal de comunicare și încearcă să extragă din acestea informațiile de interes pentru el. Această schemă formală poate fi considerată ca un model situație tipică în care se aplică metode criptografice de protecţie a informaţiilor. De remarcat că unele cuvinte militaro-militare (inamic, atac asupra cifrului etc.) s-au înrădăcinat istoric în criptografie, reflectând cel mai exact sensul conceptelor criptografice corespunzătoare. În același timp, terminologia militară larg cunoscută bazată pe conceptul de cod (coduri navale, coduri ale Statului Major General, cărți de coduri, desemnări de coduri etc.) nu mai este folosită în criptografia teoretică. Cert este că în ultimele decenii s-a format o teorie a codificării - o direcție științifică mare care dezvoltă și studiază metode de protejare a informațiilor de distorsiuni aleatorii în canalele de comunicare. Și dacă mai devreme termenii codificare și criptare erau folosiți ca sinonimi, acum acest lucru nu este inacceptabil. Deci, de exemplu, expresia foarte comună „codificarea este un fel de criptare” devine pur și simplu greșită. Criptografia se ocupă de metode de transformare a informațiilor care nu ar permite unui adversar să o extragă din mesajele interceptate. În acest caz, nu mai este informația protejată în sine cea care este transmisă prin canalul de comunicare, ci rezultatul transformării acesteia cu ajutorul unui cifru, iar adversarul se confruntă cu sarcina dificilă de a sparge cifrul. Deschiderea (cracarea) unui cifr este procesul de obținere a informațiilor protejate dintr-un mesaj criptat fără a cunoaște cifrul utilizat. Cu toate acestea, pe lângă interceptarea și deschiderea cifrului, adversarul poate încerca să obțină informațiile protejate în multe alte moduri. Cea mai cunoscută dintre aceste metode este sub acoperire, atunci când inamicul îl convinge într-un fel pe unul dintre utilizatorii legitimi să coopereze și, cu ajutorul acestui agent, obține acces la informații protejate. Într-o astfel de situație, criptografia este neputincioasă. Adversarul poate încerca să nu primească, ci să distrugă sau să modifice informațiile protejate în cursul transmiterii acesteia. Acesta este un tip foarte diferit de amenințare la adresa informațiilor decât interceptarea și spargerea cifrului. Pentru a se proteja împotriva unor astfel de amenințări, sunt dezvoltate propriile metode specifice. Prin urmare, pe drumul de la un utilizator legitim la altul, informațiile trebuie protejate în diverse moduri, rezistând diverselor amenințări. Există situația unui lanț de legături eterogene care protejează informațiile. Desigur, inamicul va căuta să găsească cea mai slabă verigă pentru a ajunge la informații cu cel mai mic cost. Aceasta înseamnă că utilizatorii legitimi ar trebui să ia în considerare și această circumstanță în strategia lor de protecție: nu are sens să facem o legătură foarte puternică dacă există în mod evident legături mai slabe („principiul forței egale a protecției”). Nu trebuie să uităm de o altă problemă importantă: problema raportului dintre prețul informațiilor, costurile protejării acesteia și costurile obținerii acesteia. Odată cu nivelul actual de dezvoltare tehnologică, mijloacele de comunicare în sine, precum și dezvoltarea mijloacelor de interceptare a informațiilor de la acestea și a mijloacelor de protejare a informațiilor, necesită costuri foarte mari. Înainte de a apăra informația, puneți-vă două întrebări: 1) este mai valoroasă pentru adversar decât costul atacului; 2) dacă este mai valoros pentru tine decât costul protecției. Aceste considerații sunt decisive la alegerea mijloacelor de protecție adecvate: fizică, steganografică, criptografică etc. Este convenabil să ilustrăm unele concepte de criptografie cu exemple istorice, așa că vom face o mică digresiune istorică. Multă vreme, criptografia a fost lotul excentricilor singuratici. Printre ei s-au numărat și oameni de știință talentați, diplomați, duhovnici. Există cazuri când criptografia a fost considerată chiar magie neagră. Această perioadă de dezvoltare a criptografiei ca artă a durat din timpuri imemoriale până la începutul secolului al XX-lea, când au apărut primele mașini de criptare. Înțelegerea naturii matematice a problemelor rezolvate prin criptografie a venit abia la mijlocul secolului al XX-lea - după munca remarcabilului om de știință american C. Shannon. Istoria criptografiei este asociată cu un număr mare de secrete diplomatice și militare și, prin urmare, este învăluită într-o ceață de legende. Cea mai completă carte despre istoria criptografiei conține peste o mie de pagini. A fost publicată în 1967 și nu a fost tradusă în rusă1". O lucrare fundamentală despre istoria criptografiei în Rusia a fost publicată recent în limba rusă. despre utilizarea cifrurilor în afacerile militare sunt asociate cu numele comandantului spartan Lysander ( cifrul „Scitala”). Cezar a folosit un cifr în corespondența sa, care a intrat în istorie drept „cifrul Cezar”. În Grecia antică a fost inventat un tip de cifru, care mai târziu a devenit cunoscut sub numele de „politia pătrată”. primele cărți despre criptografie au fost scrise de starețul I. Tritelius A462-1516), care a trăit în Germania. În 1566, celebrul matematician D. Cardano a publicat o lucrare în care descrie sistemul de criptare pe care l-a inventat („Greolă Cardano”). Franța XVI a plecat în istoria criptografiei cifrurile regelui Henric al IV-lea și Richelieu. „alfabet digital” din 1700, al cărui autor a fost Petru cel Mare. (Câteva exemple din carte sunt date pe flyleaf.) Câteva informații despre proprietățile cifrurilor și aplicarea lor pot fi găsite în ficțiune, în special în aventură, detectiv și militar.metodele de deschidere a acesteia sunt cuprinse în două povestiri binecunoscute: „The Gold Bug" de E. Poe și „The Dancing Men" de A. Conan Doyle. Să luăm în considerare două exemple mai detaliat. Cifrul „Scytalus" Acest cifr este cunoscut încă de la războiul Spartei împotriva Atenei din secolul al V-lea. secolul î.Hr. Pentru implementarea sa, a fost folosită o scytala - o tijă în formă de cilindru. O bandă îngustă de papirus (fără goluri și suprapuneri) a fost înfășurată în jurul bobinei scitale pentru a se bobina, iar apoi a fost scris un text simplu pe această bandă de-a lungul axul scitalei.Banda a fost desfășurată și s-a dovedit (pentru cei neinițiați) că unele litere au fost scrise în dezordine peste panglică.Apoi panglica a fost trimisă destinatarului.Destinatarul a luat aceeași scitala, în același mod înfășurată. cele primite bandă și citiți mesajul de-a lungul axei scitalei. Rețineți că în acest cifr transformarea textului simplu în text cifrat constă într-o anumită permutare a literelor textului simplu. David. spărgătoare de coduri. Povestea Scrierii secrete. New York: Macmillan, 1967. 2 „Soboleva T. A. Criptografia în istoria Rusiei (Istoria serviciului criptografic al Rusiei în secolele XVIII – începutul secolelor XX). M., 1994. „Scitala” se numește cifruri de permutare Cifrul Caesar Acest cifru implementează următoarea transformare a textului simplu: fiecare literă a textului simplu este înlocuită cu a treia literă după ea în alfabet, care se consideră scrisă în cerc, adică după scrisori huidui„i” este urmat de litera „a”. Rețineți că Cezar a înlocuit litera cu a treia literă după ea, dar puteți înlocui și alta. Principalul lucru este ca persoana căreia i se trimite mesajul criptat ar trebui să cunoască această valoare de schimbare. Clasa de cifruri căreia îi aparține cifrul Caesar se numește cifre de substituție. Din prezentarea anterioară este clar că inventarea unui cifr bun este o sarcină laborioasă. Prin urmare, este de dorit să creșteți durata de viață a unui cifr bun și să-l folosiți pentru a cripta cât mai multe mesaje. Dar, în același timp, există pericolul ca inamicul să fi ghicit (deschis) deja cifrul și să citească informațiile protejate. Dacă cifrul conține o cheie înlocuibilă, atunci, prin înlocuirea cheii, este posibil să se facă astfel încât metodele dezvoltate de inamic să nu mai aibă efect. În criptografie, o cheie este înțeleasă ca un element înlocuibil al unui cifr care este utilizat pentru a cripta un anumit mesaj. De exemplu, în cifrul Scytala, cheia este diametrul scitalei, iar în cifrurile precum cifrul Caesar, cheia este cantitatea de deplasare a literelor din text cifrat în raport cu literele text clar. Considerentele descrise au condus la faptul că securitatea informațiilor protejate a început să fie determinată în primul rând de cheie. Cifrul în sine, mașina de cifrare sau principiul criptării au început să fie considerate cunoscute inamicului și disponibile pentru studiu preliminar, dar în ele a apărut o cheie necunoscută de inamic, de care depind în mod semnificativ transformările informaționale aplicate. Acei utilizatori legitimi Now, înainte de a schimba mesaje criptate-criptate, trebuie să schimbe în secret chei de la inamic sau să seteze aceeași cheie la ambele capete ale canalului de comunicare. Și pentru adversar, a apărut o nouă sarcină - să determine cheia, după care este ușor să citești mesajele criptate pe această cheie. Să revenim la descrierea formală a obiectului principal al criptografiei criptografice (Fig. 1, p. 9). Acum trebuie introdus schimbare semnificativă- adăugați un canal secret de comunicare inaccesibil inamicului pentru schimbul de chei (vezi Fig. 2). Este destul de realist să creați un astfel de canal de comunicare, deoarece sarcina pe acesta, în general, este mică. Rețineți acum că nu există un cifr unic care să se potrivească tuturor cazurilor. Alegerea metodei de criptare depinde de caracteristicile informațiilor, de valoarea acesteia și de capacitatea proprietarilor de a-și proteja informațiile. În primul rând, subliniem marea diferență dintre conceptele cheie ale criptografiei 13<- " сообщения " . „ П Рис. 2. образие видов защищаемой информации: документальная, телефон- телефонная, телевизионная, компьютерная и т. д. Каждый вид информации имеет свои специфические особенности, и эти особенности сильно влияют на выбор методов шифрования информации. Большое зна- значение имеют объемы и требуемая скорость передачи шифрованной информации. Выбор вида шифра и его параметров существенно за- зависит от характера защищаемых секретов или тайны. Некоторые тайны (например, государственные, военные и др.) должны сохра- сохраняться десятилетиями, а некоторые (например, биржевые) - уже че- через несколько часов можно разгласить. Необходимо учитывать так- также и возможности того противника, от которого защищается данная информация. Одно дело - противостоять одиночке или даже бан- банде уголовников, а другое дело - мощной государственной структу- структуре. Способность шифра противостоять всевозможным атакам на него называют стойкостью шифра. Под атакой на шифр понимают попытку вскрытия этого шифра. Понятие стойкости шифра является центральным для криптогра- криптографии. Хотя качественно понять его довольно легко, но получение стро- строгих доказуемых оценок стойкости для каждого конкретного шифра - проблема нерешенная. Это объясняется тем, что до сих пор нет необ- необходимых для решения такой проблемы математических результатов. (Мы вернемся к обсуждению этого вопроса ниже.) Поэтому стойкость конкретного шифра оценивается только путем всевозможных попыток его вскрытия и зависит от квалификации крипто аналитике в, атаку- атакующих шифр. Такую процедуру иногда называют проверкой стойко- стойкости. Важным подготовительным этапом для проверки стойкости шифра является продумывание различных предполагаемых возможностей, с помощью которых противник может атаковать шифр. Появление та- таких возможностей у противника обычно не зависит от криптографии, это является некоторой внешней подсказкой и существенно влияет на стойкость шифра. Поэтому оценки стойкости шифра всегда содержат те предположения о целях и возможностях противника, в условиях ко- которых эти оценки получены. 14 Глава 1 Прежде всего, как это уже отмечалось выше, обычно считается, что противник знает сам шифр и имеет возможности для его предва- предварительного изучения. Противник также знает некоторые характери- характеристики открытых текстов, например, общую тематику сообщений, их стиль, некоторые стандарты, форматы и т. д. Из более специфических приведем еще три примера возможностей противника: - противник может перехватывать все шифрованные сообщения, но не имеет соответствующих им открытых текстов; - противник может перехватывать все шифрованные сообщения и добывать соответствующие им открытые тексты; - противник имеет доступ к шифру (но не к ключам!) и поэтому может зашифровывать и дешифровывать любую информацию. На протяжении многих веков среди специалистов не утихали споры о стойкости шифров и о возможности построения абсолютно стойкого шифра. Приведем три характерных высказывания на этот счет. Английский математик Чарльз Беббидж (XIX в.): «Всякий человек, даже если он не знаком с техникой вскрытия шифров, твер- твердо считает, что сможет изобрести абсолютно стойкий шифр, и чем более умен и образован этот человек, тем более твердо это убеждение. Я сам раз- разделял эту уверенность в течение многих лет.» «Отец кибернетики» Норберт Винер: «Любой шифр может быть вскрыт, если только в этом есть настоятельная необходимость и информация, которую предполагается получить, стоит за- затраченных средств, усилий и времени...» Автор шифра PGP Ф. Зиммерманн («Компьютерра», №48 от 1.12.1997, стр. 45-46): «Каждый, кто думает, что изобрел непробиваемую схему шифрования, - или невероятно редкий гений, или просто наивен и неопытен...» «Каждый программист воображает себя криптографом, что ведет к распро- распространению исключительно плохого криптообеспечения...» В заключение данного раздела сделаем еще одно замечание - о тер- терминологии. В timpuri recente împreună cu cuvântul „criptografie” se întâlnește adesea cuvântul „criptologie”, dar relația dintre ele nu este întotdeauna înțeleasă corect. Acum are loc formarea finală a acestor discipline științifice, se precizează subiectul și sarcinile acestora. Criptologia este o știință formată din două ramuri: criptografie și criptoanaliza. Criptografia este știința modului în care informațiile sunt transformate (criptate) pentru a le proteja de utilizatorii ilegali. Criptanaliza este o știință (și practica aplicării acesteia) despre metodele și modalitățile de spargere a cifrurilor. Conceptele de bază ale criptografiei 15 Relația dintre criptografie și criptoanaliza este evidentă: criptografia criptografică este protecție, adică dezvoltarea cifrurilor, iar criptoanaliza este un atac, adică un atac asupra cifrurilor. Cu toate acestea, aceste două discipline sunt legate între ele și nu există criptografi buni care să nu stăpânească metodele crio-criptoanalizei. 3. Bazele matematice Lucrările matematicianului american Claude Shan-Shannon, apărute la mijlocul secolului al XX-lea, au avut o mare influență asupra dezvoltării criptografiei. În aceste lucrări s-au pus bazele teoriei informației și s-a dezvoltat un aparat matematic pentru cercetarea în multe domenii ale științei legate de informație. Mai mult, este general acceptat că teoria informației ca știință a luat naștere în 1948 după publicarea lucrării lui K. Shannon „Teoria matematică a comunicării”1). În lucrarea sa „Teoria comunicării în sistemele secrete”, Claude Shannon a rezumat experiența acumulată înaintea sa în dezvoltarea cifrurilor.este cel mai simplu și mai popular cifr.Exemple tipice sunt cifrul Caesar, „alfabetul digital” al lui Petru cel Mare și A. „Bărbații dansatori” ai lui Conan Doyle. „părți” ale textului cifrat. Este ușor să dați o descriere matematică a cifrului de substituție. Fie X și Y două alfabete (text simplu și, respectiv, text cifrat) constând din același număr de caractere Fie, de asemenea, q: X -> Y o mapare unu-la-unu a lui X la Y. Atunci cifrul de substituție funcționează după cum urmează: textul simplu x\x2 ¦¦.xn este convertit în textul cifrat q(x1)q( x2) ¦ ¦ -q(xn). din nume, convertește permutarea literelor în textul simplu. Un exemplu tipic de cifru de permutare este cifrul Scytala. De obicei, textul simplu este împărțit în segmente de lungime egală și fiecare segment este criptat independent. Fie, de exemplu, lungimea segmentelor egală cu n și a fi o mapare unu-la-unu a mulțimii (1,2,...,n) în sine. Atunci cifrul de permutare funcționează astfel: segmentul de text simplu x\ ... xn este transformat în segmentul de text cifrat xx\) ... xa(n). ^ Shannon S. E. O teorie matematică a comunicării // Bell System Techn. J. V. 27, Nr. 3, 1948. P. 379-423; V. 27, nr. 4, 1948. P. 623-656. 2 „Vezi Anexa. 16 Capitolul 1 Cel mai important rezultat pentru dezvoltarea criptografiei a fost rezultatul lui K. Shan-Shannon privind existența și unicitatea unui cifr absolut sigur. Singurul astfel de cifr este o formă a așa-numitului unic. -utilizați bandă, în care textul simplu este „cu o cheie complet aleatorie de aceeași lungime. Acest rezultat a fost dovedit de K. Shannon folosind metoda teoretică informațională de studiere a cifrurilor dezvoltată de el. Nu ne vom opri aici în detaliu asupra acestui lucru. , recomandăm cititorului interesat să studieze opera lui K. Shannon1”. Să discutăm caracteristicile structurii unui cifr absolut sigur și posibilitățile de utilizare practică a acestuia. Un exemplu tipic și cel mai simplu de implementare a unui cifr absolut sigur este cifrul Vernam, care efectuează adăugarea pe biți a unui text simplu de n biți și a unei chei de n biți: yi = Xi®ki, i = l,...,n . Aici Xi ...xn este textul simplu, k\,...,kn este cheia, y\ ¦ ¦ .yn este textul cifrat. Subliniem că fiecare dintre următoarele cerințe pentru o bandă de unică folosință este esențială pentru securitatea absolută: 1) aleatorie (echiprobabilitatea) completă a cheii (aceasta, în special, înseamnă că cheia nu poate fi generată folosind niciun dispozitiv determinist); 2) egalitatea lungimii cheii și a lungimii textului simplu; 3) o singură utilizare a cheii. Dacă cel puțin una dintre aceste condiții este încălcată, cifrul încetează să mai fie absolut sigur și apar posibilități fundamentale de deschidere a acestuia (deși pot fi dificil de implementat). Dar se dovedește că tocmai aceste condiții fac ca un cifru absolut puternic să fie foarte scump și nepractic. Înainte de a utiliza un astfel de cifru, trebuie să oferim tuturor abonaților o cantitate suficientă de chei aleatorii și să excludem posibilitatea reutilizarii acestora. Și acest lucru este extrem de dificil și costisitor de făcut. După cum a remarcat D. Kahn: „Problema creării, înregistrării, distribuirii și anulării cheilor poate să nu pară prea complicată pentru cineva care nu are experiență în transmiterea de mesaje prin canale de comunicații militare, dar în timp de război volumul mesajelor transmise încurcă chiar și semnalizatorii profesioniști. . Sute de mii de cuvinte pot fi criptate pe zi. Crearea a milioane de semne cheie ar necesita cheltuieli financiare uriașe și ar fi asociată cu o investiție mare de timp. Întrucât fiecare text trebuie să aibă o cheie proprie, unică și inimitabilă, utilizarea unui sistem ideal ar necesita transmiterea a cel puțin atâtea caractere cât este echivalent cu întregul volum de informații militare. transmis”. Din aceste motive, cifrurile absolut puternice sunt folosite numai în rețelele de comunicații cu o cantitate mică de informații transmise, de obicei acestea sunt rețele pentru transmiterea de informații guvernamentale deosebit de importante.cifre puternice. Astfel de cifre, cel puțin teoretic, pot fi sparte. Singura întrebare este dacă adversarul are suficientă putere, mijloace și timp pentru a dezvolta și implementa algoritmii corespunzători.De obicei, această idee este exprimată astfel: un adversar cu resurse nelimitate poate sparge orice cifru neabsolut puternic.Cum ar trebui să acționeze atunci un utilizator legitim în această situație , alegând un cifr pentru sine? Cel mai bine ar fi, desigur, să demonstreze că niciun adversar nu poate ani și să obțină astfel o estimare teoretică a rezistenței.Din păcate, teoria matematică nu oferă încă teoremele necesare - ele se referă la problema nerezolvată a limitelor inferioare pentru complexitatea de calcul a problemelor. \ Prin urmare, utilizatorului îi rămâne singura cale - să obțină evaluări practice ale rezistenței. Această cale constă din următoarele etape: „- înțelegeți și articulați clar de ce tip de adversar vom proteja informațiile; este necesar să înțelegem ce anume cunoaște sau poate învăța adversarul despre sistemul de cifrare, precum și ce forțe și înseamnă că îl va putea folosi pentru a-l deschide; - se pune mental în poziția inamicului și încearcă să atace cifrul din pozițiile sale, adică să dezvolte diverși algoritmi pentru spargerea cifrului; în timp ce este necesar să se ofere modele măsura maximă - modelarea forțelor, mijloacelor și capacităților inamicului; - cei mai buni algoritmi dezvoltați pot fi utilizați pentru evaluarea practică a securității unui cifr.Aici, pentru ilustrare, este util să menționăm două metode simple pentru spargerea unei cifru: ghicirea aleatorie a cheii (funcționează cu o probabilitate mică, dar are o complexitate mică) și enumerarea tuturor cheilor într-un rând până la găsirea adevăratului (funcționează întotdeauna, dar are o complexitate foarte mare). De asemenea, remarcăm că un atac asupra cheii nu este întotdeauna necesar: ​​pentru unele cifre, este posibil imediat, chiar și fără a cunoaște cheia, să se recupereze textul simplu din textul cifrat. 18 Capitolul 1 4. Noi direcții În 1983, în cartea „Coduri și matematică” de M. N. Arshinov și L. E. Sa-Sadovsky (biblioteca „Kvant”), s-a scris: „Există foarte multe metode de criptografie și, cele mai multe probabil, , acesta este un domeniu în care nu mai este nevoie să inventezi ceva esențial nou. Cu toate acestea, aceasta a fost o altă mare concepție greșită despre criptografie. În 1976, a fost publicată lucrarea tinerilor matematicieni americani W. Diffie și M. E. Hellman „New Trends in Cryptography”1”, care nu numai că a schimbat semnificativ criptografia, dar a dus și la apariția și dezvoltarea rapidă a noilor tendințe în matematică. Conceptul central „nouă criptografie” este conceptul de funcție unidirecțională (pentru mai multe despre aceasta, vezi capitolul 2). O funcție unidirecțională se numește funcție F: X -> Y, care are două proprietăți: a) există un algoritm polinom pentru calcularea valorilor lui F (x), b) nu există un algoritm polinom pentru inversarea funcției F (adică, rezolvarea ecuației F(x) = y față de x, vezi pagina 30 pentru definiția exactă).pentru restricții asupra complexității calculului și inversării acesteia.Întrebarea existenței funcțiilor unidirecționale este încă deschisă.Un alt concept nou este conceptul de funcție cu secret.Uneori este folosit și funcție de termen cu o capcană. O funcţie cu un secret K este o funcţie Fk: X -> Y care depinde de parametrul K şi are trei proprietăţi: a) există un algoritm polinom pentru calcularea valorii lui Fk(x) pentru orice K şi x; b) nu există un algoritm polinom pentru inversarea Fa pentru K necunoscut; c) există un algoritm polinom pentru inversarea Fk cu K cunoscut. Același lucru se poate spune despre existența funcțiilor cu secret ca și despre funcțiile unidirecționale. În scopuri practice ale criptografiei, au fost construite mai multe funcții care se pot dovedi a fi funcții cu un secret. Pentru ei, proprietatea b) nu a fost încă dovedită riguros, dar se crede că problema inversării este echivalentă cu o problemă matematică dificilă care a fost studiată de mult timp. Cea mai cunoscută și mai populară dintre acestea este funcția teoretică a numărului pe care este construit cifrul RSA (a se vedea capitolul 4 pentru mai multe despre aceasta). "" Diffie W., Hellman M. E. Securitate și rezistență la imitație. Introducere în criptografie // TIEER. V. 67, Nr. 3, 1979. Concepte de bază ale criptografiei 19 Utilizarea funcțiilor cu secret în criptografie permite: 1) organizarea schimbului de mesaje criptate folosind doar canale de comunicare deschise, adică refuzarea canalelor de comunicare secrete pentru prealabil. schimb de chei; 2) include o problemă matematică dificilă în problema ruperii cifrului și, prin urmare, crește valabilitatea securității cifrului; 3) rezolvarea de noi probleme criptografice, altele decât criptarea (semnătură digitală electronică etc.). Să descriem, de exemplu, cum poate fi implementat punctul 1). Utilizatorul A, care dorește să primească mesaje criptate, trebuie să aleagă o funcție Fk cu secret K. El informează toate părțile interesate (de exemplu, publică) descrierea funcției Fk ca algoritm de criptare. Dar, în același timp, nu spune nimănui sensul secretului lui K și îl păstrează secret. Acum, dacă utilizatorul B dorește să trimită informații protejate utilizatorului A? X, apoi calculează y = Fk(x) și trimite y pe un canal deschis utilizatorului A. Deoarece A știe cum să inverseze Fk pentru K secretul său, el calculează x din y primit. Nimeni altcineva nu știe K și, prin urmare, din cauza proprietății b) a unei funcții cu un secret, nu va putea calcula informația protejată x în timp polinomial dintr-un mesaj criptat cunoscut Fk(x). Sistemul descris se numește criptosistem cu cheie publică, deoarece algoritmul de criptare Fk este public sau deschis. Recent, astfel de criptosisteme sunt numite și asimetrice, deoarece au asimetrie în algoritmi: algoritmii de criptare și de decriptare sunt diferiți. Spre deosebire de astfel de sisteme, cifrurile tradiționale sunt numite simetrice: în ele, cheia pentru criptare și decriptare este aceeași. Pentru sistemele asimetrice, algoritmul de criptare este bine cunoscut, dar este imposibil să reconstruiți algoritmul de decriptare din acesta în timp polinomial. Diffie și Hellman au sugerat să folosească ideea descrisă mai sus și pentru electronice semnatura digitala mesaje care nu pot fi falsificate în timp polinomial. Permiteți utilizatorului A să nu fie nevoie să semneze mesajul x. Cunoscând secretul K, el găsește y astfel încât Pk(y) - x și împreună cu mesajul x trimite y utilizatorului B ca semnătură digitală. Utilizatorul B păstrează y ca dovadă că A semnat mesajul x. Un mesaj semnat cu o semnătură digitală poate fi gândit ca o pereche (x, y), unde x este un mesaj, y este o soluție a ecuației Pk(y) - x, Fk"¦ X -> Y este o funcție cu un secret cunoscut de toți care interacționează Din definiția funcției Fk, sunt evidente următoarele proprietăți utile ale unei semnături digitale: 2) orice abonat care cunoaște cheia publică, adică funcția Fk\ însăși poate verifica autenticitatea semnăturii 3 ) în caz de dispute este imposibil să refuzi semnătura din cauza caracterului infalsibil al acesteia 4) mesajele semnate (x, y) pot fi făcute fără teama de deteriorare, redirecționate prin orice canale de comunicare. Pe lângă principiul construirii unui criptosistem cu un cheie publică, Diffie și Hellman în aceeași lucrare au propus o altă idee nouă - distribuția cheii publice.Ei și-au pus întrebarea: este posibil să se organizeze o astfel de procedură pentru interacțiunea abonaților A și B prin canale de comunicare deschise pentru a rezolva următoarele sarcini: 1) la început, A și B nu au nicio informație secretă comună, dar la sfârșitul procedurii, o astfel de informație secretă partajată (cheie comună) apare pentru A. și B, adică este generat; 2) un adversar pasiv care interceptează toate transmisiile de informații și știe că A și B doresc să primească, cu toate acestea, nu poate recupera cheia comună generată A și B. Diffie și Hellman au propus să rezolve aceste probleme folosind funcția F(x) = ax (mod p), unde p este un număr prim mare, x este un număr natural arbitrar, q este un element primitiv al câmpului GF(p). Este în general acceptat că inversarea funcției ax (modp), adică. log-logaritmul discret este o problemă matematică dificilă. (Consultați Capitolul 4 pentru mai multe detalii.) Procedura în sine, sau, după cum se spune, protocolul pentru generarea unei chei partajate, este descrisă după cum urmează. Abonații A și B, independent unul de celălalt, aleg aleatoriu câte un număr natural - să spunem xa și xb. Ei păstrează aceste elemente secrete. Mai mult, fiecare dintre ele calculează un element nou: y A = otXA (mod p), y b = aXb (mod p). (Numerele p și a sunt considerate publice. ) Apoi schimbă aceste elemente printr-un canal de comunicare. Acum abonatul A, după ce a primit uv și cunoscând elementul său secret xa, calculează un nou element: uxvA (modp) = (aXB)XA (modp). Abonatul B acţionează în mod similar: uxAv (mod p) = (aXA)Xv (mod p). Concepte de bază ale criptografiei 21 Astfel, A și B au un element comun de câmp egal cu aXlXv. Acest element este declarat prin cheia comună a lui A și B. Din descrierea protocolului, reiese clar că adversarul cunoaște p, a, aXA, aXb, nu cunoaște xa și xts și vrea să cunoască aXXb. În prezent, nu există algoritmi adversari mai eficienți decât logaritmul discret și aceasta este o problemă matematică dificilă. Progresele în dezvoltarea schemelor de semnătură digitală și distribuția cheilor publice au făcut posibilă aplicarea acestor idei și la alte probleme de interacțiune între abonații de la distanță. Astfel, a apărut o mare nouă direcție a criptografiei teoretice - protocoalele cripto-criptografice (a se vedea capitolul 3 pentru mai multe detalii). Obiectul de studiu al teoriei protocoalelor criptografice îl reprezintă abonații la distanță care interacționează, de regulă, prin canale de comunicare deschise. Scopul interacțiunii abonaților este de a rezolva o problemă. Există și un adversar care își urmărește propriile scopuri. În acest caz, inamicul în diferite sarcini poate avea capacități diferite: de exemplu, el poate interacționa cu abonați-abonați în numele altor abonați sau să intervină în schimbul de informații între abonați etc. Inamicul poate fi chiar unul dintre abonați sau mai mulți abonați care s-au înțeles. Iată încă câteva exemple de sarcini rezolvate de abonații la distanță. (Recomandăm cititorului să mai vină cu câteva exemple după propriul gust.) 1. Doi abonați care nu au încredere unul în celălalt interacționează. Vor să semneze un contract. Aceasta trebuie făcută astfel încât să se prevină următoarea situație: unul dintre abonați a primit semnătura celuilalt, dar el însuși nu a semnat. Protocolul pentru rezolvarea acestei probleme se numește de obicei protocol de semnare a contractului. 2. Doi abonați care nu au încredere unul în celălalt interacționează. Vor să tragă la sorți cu o monedă. Acest lucru ar trebui făcut în așa fel încât utilizatorul care aruncă moneda să nu poată schimba rezultatul aruncării după ce a primit o ghicire de la utilizatorul care ghiceste acest rezultat. Protocolul pentru rezolvarea acestei probleme se numește protocol de aruncare a monedelor. Să descriem unul dintre cele mai simple protocoale de aruncare a unei monede prin telefon (așa-numita schemă Blume-Micali). Pentru a-l implementa, abonații A și B trebuie să aibă o funcție unidirecțională /: X -> Y care îndeplinește următoarele condiții: 1) X este o mulțime de numere întregi care conține același număr de numere pare și impare; 22 Capitolul 1 2) orice numere xi,X2 ? X având o imagine )(x\) - o paritate; 3) dat fiind modelul f(x), este „dificil” să se calculeze paritatea argumentului necunoscut x. Rolul aruncării unei monede este jucat de o alegere aleatorie și la fel de probabilă a elementului x 6 X, iar rolul capetelor și al cozilor este jucat de uniformitatea și, respectiv, ciudățenia lui x. Fie A să fie aruncătorul de monede și B să ghicească. Protocolul constă din următorii pași: 1) A alege x („aruncă o monedă”), criptează x, adică calculează y = f(x) și trimite y către abonatul B; 2) B primește y, încearcă să ghicească paritatea lui x și trimite estimarea lui abonatului A; 3) A primește o ghicire de la B și îi spune lui B dacă a ghicit corect trimițându-i numărul x ales; 4) B verifică dacă A trișează calculând valoarea lui f(x) și comparând-o cu valoarea lui y obținută în a doua etapă. 3. Doi abonați A și B interacționează (exemplu tipic: A este un client bancar, B este o bancă). Abonatul A vrea să-i demonstreze abonatului B că el este A și nu un adversar. Protocolul pentru rezolvarea acestei probleme se numește de obicei protocol de identificare a abonatului. 4. Mai mulți abonați la distanță care au primit comenzi de la un centru interacționează. Unii abonați, inclusiv centrul, pot fi adversari. Este necesar să se dezvolte o strategie de acțiune unificată care să fie benefică pentru abonați. Această problemă este de obicei numită problema generalilor bizantini, iar protocolul soluționării ei se numește protocolul acordului bizantin. Să descriem un exemplu căruia această problemă își datorează numele. Bizanț - Bizanț. În noaptea dinaintea marii bătălii. Armata bizantină este formată din n legiuni, fiecare fiind subordonată propriului general. În plus, armata are un comandant-șef care îi conduce pe generali. Totuși, imperiul este în declin și până la o treime dintre generali, inclusiv comandantul șef, pot fi trădători. În timpul nopții, fiecare dintre generali primește un ordin de la comandantul șef despre acțiunile de dimineață și două va-varianta ordine: „atac” sau „retragere”. Dacă toți generalii cinstiți atacă, ei câștigă. Dacă toți se retrag, atunci reușesc să salveze armata. Dar dacă unii dintre ei atacă și alții se retrag, atunci sunt învinși. Dacă comandantul șef se dovedește a fi un trădător, atunci poate da ordine diferite unor generali diferiți, așa că ordinele comandantului șef nu trebuie respectate implicit. Dacă fiecare general acționează independent de ceilalți, rezultatele pot fi dezastruoase. Evident, generalii trebuie să facă schimb de informații între ei (referitor la comenzile primite) pentru a ajunge la o înțelegere. Concepte de bază ale criptografiei 23 Înțelegerea diferitelor protocoale și metode de construcție a acestora a rezultat la apariția a două modele matematice fructuoase - un sistem de demonstrare interactiv și o demonstrație cu cunoștințe zero. Studiile matematice ale acestor noi obiecte au dovedit multe afirmații care sunt foarte utile în dezvoltarea protocoalelor criptografice (a se vedea capitolul 2 pentru mai multe despre aceasta). Un sistem de demonstrare interactiv (P, V, S) este înțeles ca un protocol pentru interacțiunea a doi abonați: P (demonstrarea) și V (pro- (verificarea). Abonatul P vrea să demonstreze lui V că afirmația 5 este adevărată. La în același timp, abonatul V independent, fără ajutorul lui P , nu poate verifica afirmația S (deci V se numește verificator. Abonatul P poate fi și un adversar care dorește să-i demonstreze lui V că afirmația S este adevărată, deși este este fals.Protocolul poate consta în multe runde de schimb de mesaje între P și V și trebuie să îndeplinească două condiții: 1) completitudine - dacă 5 este cu adevărat adevărat, atunci abonatul P îl va convinge pe abonatul V să o admită; 2) corectitudine - dacă 5 este fals, atunci abonatul P este puțin probabil să-l convingă pe abonatul V că 5 este adevărat. Aici, pentru simplitate, am înlocuit formularea matematică exactă cu cuvintele „improbabil”. Subliniem că în definiția sistemului (P, V, S) nu era permis ca V să fie adversar. Dar dacă V s-ar dovedi a fi un adversar care vrea să „afle” de la P niște informații utile noi despre afirmația 5? În acest caz, P, desigur, poate să nu dorească ca acest lucru să se întâmple ca urmare a funcționării protocolului (P, V, S). Protocolul (P, V, S) care rezolvă o astfel de problemă se numește dovadă de cunoștințe zero și trebuie să îndeplinească, pe lângă condițiile 1) și 2), următoarea condiție: 3) cunoștințe zero - ca urmare a operației al protocolului (P, V, S) abonatul V nu își va spori cunoștințele despre enunțul S sau, cu alte cuvinte, nu va putea extrage nicio informație despre motivul pentru care S este adevărat. 5. Concluzie În ultimii ani, criptografia și metodele criptografice au devenit din ce în ce mai mult parte din viața noastră și chiar din viața de zi cu zi. Aici sunt cateva exemple. Când trimitem e-mailuri, în unele cazuri răspundem la întrebarea din meniu: „Am nevoie de modul de criptare?” Posesorul unui card bancar-bancar inteligent, adresându-se băncii prin terminal, efectuează mai întâi un protocol de autentificare a cardului criptografic. Utilizatorii de internet sunt probabil familiarizați cu discuțiile despre posibila adoptare a unui standard de semnătură digitală pentru acele pagini care conțin informații „critice” (legale, liste de prețuri etc.). Recent, utilizatorii rețelei au început să indice după numele lor de familie, împreună cu deja familiar „E-mail...” și mai puțin familiar - „Amprenta cheie publică...”. În fiecare zi apar tot mai multe astfel de exemple. Noile aplicații practice ale criptografiei sunt una dintre sursele dezvoltării acesteia. Capitolul 2 Criptografia și teoria complexității Accentul acestui capitol este de a clarifica ideile importante implicate în aplicarea abordării teoretice a complexității în criptografie. Expunerea este în mod necesar insuficient de formală - definițiile cu mai multe pagini sunt tipice pentru criptografia matematică. Se presupune că cititorul este familiarizat cu elementele fundamentale ale teoriei complexității computaționale: conceptele unei mașini Turing, clasele P și NP (vezi ), precum și cu capitolul 1 al acestei cărți. 1. Introducere În criptografia teoretică, există două abordări principale pentru determinarea securității criptosistemelor și a protocoalelor criptografice (în cele ce urmează vom folosi și termenul general de scheme criptografice): teoretică informațională și teoretică a complexității. Abordarea teoretică informațională presupune că un adversar care atacă o schemă criptografică nu are nici măcar o oportunitate teoretică de a obține informații suficiente pentru a-și atinge obiectivele. Exemplul clasic aici este cifrul Vernam cu chei unice, absolut rezistente împotriva unui adversar pasiv. Marea majoritate a schemelor criptografice criptografice utilizate în practică nu au o securitate atât de ridicată. Mai mult, de obicei este ușor să indicați un algoritm care îndeplinește sarcina cu care se confruntă adversarul, dar nu practic, ci în principiu. Luați în considerare următorul exemplu. Exemplul 1 (Criptosistem cu cheie publică). Criptosistem - Un criptosistem cu cheie publică este complet definit de trei algoritmi - algoritmi: generarea cheilor, criptarea și decriptarea. Algoritmul de generare a cheilor G este disponibil publicului; oricine îi poate da un șir aleatoriu r de lungimea corespunzătoare ca intrare și poate obține o pereche de chei (A "1, Xr). Cheia publică K \ este publicată, iar secretul cheia K-iși un șir aleator z sunt ținute secrete. Algoritmii de criptare Ekx și decriptarea D^2 sunt astfel încât dacă (K\, K-i) este o pereche de chei generată de algoritmul G, atunci Dk2(Ek1 [m)) = m pentru orice text simplu m. Pentru simplitate, presupunem că textul simplu și criptograma au aceeași lungime n. În plus, presupunem că textul simplu, criptograma și ambele chei sunt șiruri în alfabet binar. Să presupunem acum că un adversar atacă acest criptosistem. El cunoaște cheia publică K\, dar nu cunoaște cheia corespunzătoare secret Tasta Ki. Adversarul a interceptat criptograma d și încearcă să găsească mesajul m, unde d = Ec^(m). Deoarece algoritmul de criptare este bine cunoscut, adversarul poate pur și simplu să itera toate mesajele posibile de lungime n, să calculeze pentru fiecare astfel de mesaj TP( criptograma di = Ekx (mn-r) și să compare di cu d. La un mesaj pentru care di = d, și va fi textul simplu dorit. Dacă aveți noroc, textul clar va fi găsit suficient de repede. În cel mai rău caz, enumerarea va fi finalizată într-un timp de ordinul 2"T(n), unde T( n) este timpul necesar pentru calcularea funcției Ek, din mesajele de lungime n. Dacă mesajele au o lungime de ordinul a 1000 de biți, atunci o astfel de enumerare nu este fezabilă în practică pe niciunul dintre cele mai puternice computere. Am luat în considerare doar una dintre metodele posibile de atacare a unui criptosistem și cel mai simplu algoritm de căutare a textului simplu, numit de obicei algoritmul textului complet. se mai folosește un alt nume: „metoda forței brute”. Un alt algoritm simplu pentru găsirea textului simplu este ghicitul. Acest algoritm evident necesită puțin calcul, dar funcționează cu o probabilitate neglijabilă (pentru lungimi mari de texte). De fapt, adversarul poate încerca să atace criptosistemul în diverse moduri și să folosească diverși, mai sofisticați algoritmi de căutare în text simplu. Este firesc să considerăm un criptosistem sigur dacă un astfel de algoritm necesită o cantitate practic impracticabilă de calcul sau funcționează cu o probabilitate neglijabilă. (În acest caz, adversarul poate folosi nu numai algoritmi determiniști, ci și probabilistici.) Aceasta este abordarea complexității-teoretică a definiției securității. Pentru a-l implementa în relație cu unul sau altul tip de scheme criptografice, este necesar să faceți următoarele: 1) dați o definiție formală a unei scheme de acest tip; 2) da o definiție formală a securității schemei; 3) pentru a demonstra stabilitatea unui proiect de circuit specific de un tip dat. Aici apar imediat o serie de probleme. În primul rând, în schemele criptografice, desigur, se folosesc întotdeauna valorile parametrilor fixe. De exemplu, sistemele de cripto-criptografie și teoria complexității 27 sunt proiectate pentru chei de lungime, să zicem, 256 sau 512 octeți. Pentru a aplica abordarea teoretică a complexității, este necesar ca problema, a cărei complexitate computațională se presupune a fi utilizată, să fie masivă. Prin urmare, în criptocriptografia teoretică, sunt luate în considerare modele matematice ale schemelor criptografice. Aceste modele depind de un parametru numit parametru de securitate, care poate lua valori arbitrar de mari (de obicei, pentru simplitate, se presupune că parametrul de securitate poate rula pe întreaga serie naturală). În al doilea rând, determinarea puterii unei scheme criptografice depinde de sarcina cu care se confruntă adversarul și de ce informații despre schemă îi sunt disponibile. Prin urmare, stabilitatea schemelor vine - este necesar să se determine și să investigheze separat pentru fiecare ipoteză despre inamic. În al treilea rând, este necesar să se clarifice ce cantitate de calcule poate fi considerată „practic impracticabilă”. Din cele de mai sus rezultă că această valoare nu poate fi doar o constantă, trebuie reprezentată printr-o funcție a parametrului de securitate în creștere. Conform tezei lui Edmonds, un algoritm este considerat eficient dacă timpul său de execuție este limitat de un polinom în lungimea cuvântului de intrare (în cazul nostru, pe parametrul de securitate). Altfel, se spune că calculele prin acest algoritm sunt practic imposibile. De asemenea, observăm că schemele criptografic-criptografice în sine trebuie să fie eficiente, adică toate calculele prescrise de una sau alta schemă trebuie efectuate în timp polinomial. În al patrulea rând, este necesar să se determine ce probabilitate poate fi considerată neglijabilă. În criptografie, se obișnuiește să se considere ca atare orice probabilitate ca pentru orice polinom p și pentru toate n suficient de mari să nu depășească 1/p(n), unde u este parametrul de securitate. Deci, în prezența tuturor definițiilor de mai sus, problema fundamentarii securității unei scheme criptografice s-a redus la dovedirea absenței unui algoritm polinom care să rezolve problema cu care se confruntă adversarul. Dar aici apare un alt obstacol foarte serios: de ultimă oră Teoria complexității computaționale nu permite să se demonstreze limite inferioare superpolinomiale pentru complexitate pentru probleme specifice clasei luate în considerare. De aici rezultă că în momentul de față puterea schemelor criptografice poate fi stabilită doar cu implicarea unor presupuneri nedovedite. Prin urmare, direcția principală de cercetare este căutarea celor mai slabe condiții suficiente (ideal, necesare și suficiente) pentru existența schemelor stabile de fiecare tip. 28 Capitolul 2 Practic, sunt luate în considerare două tipuri de ipoteze - generale (sau teoretice ale complexității) și teoretice ale numerelor, adică ipoteze despre complexitatea problemelor specifice teoretice ale numerelor. Toate aceste ipoteze din literatură sunt de obicei numite criptografice. Mai jos luăm în considerare pe scurt câteva obiecte matematice interesante care au apărut la intersecția dintre teoria complexității și criptografia. Mai mult prezentare detaliată despre aceste aspecte pot fi găsite în carte. 2. Criptografia și ipoteza De regulă, familiaritatea matematicienilor nespecialiști cu teoria complexității computaționale se limitează la clasele P și NP și la celebra presupunere Să reamintim pe scurt informațiile necesare din teoria complexității computaționale. Fie?* mulțimea tuturor șirurilor finite din alfabetul binar S = (0,1). Submulțimile L C S* în teoria complexității sunt de obicei numite limbaje. Se spune că o mașină Turing M rulează în timp polinomial (sau pur și simplu că este polinom) dacă există un polinom p astfel încât, pe orice cuvânt de intrare de lungime n, mașina M se oprește după ce a efectuat nu mai mult de p(n) operații . O mașină Turing M recunoaște (sau acceptă) limbajul L dacă, la fiecare cuvânt introdus x E L, mașina M se oprește în starea de acceptare, iar la fiecare cuvânt x $ L, în starea de respingere. Clasa P este clasa tuturor limbajelor recunoscute de mașinile Turing care rulează în timp polinomial. O funcție / : 2* -> 2* este calculabilă în timp polinomial dacă există o mașină de Turing polinomială astfel încât dacă cuvântul x E? Un limbaj L aparține clasei NP dacă predicatul P(x, y) : S* x S* -? (0,1) calculabil în timp polinomial și un polinom p astfel încât L = (x\3yP(x, y)&i\y\ ^ p(|z|)). Astfel, un limbaj L aparține lui NP dacă, pentru orice cuvânt din L de lungime n, este posibil să se ghicească un șir de polinom de lungime în n și apoi, folosind predicatul P, să se verifice dacă presupunerea este corectă. Este clar că P C NP. Dacă această includere este strictă este una dintre cele mai cunoscute probleme nerezolvate din matematică. Majoritatea experților consideră că este strictă (așa-numita ipoteză P^NP). În clasa NP, este evidențiată o subclasă de limbaje maxim complexe, numită NP-complet: orice limbaj NP-complet este recunoscut în timp polinomial dacă și numai dacă P=NP. Pentru cele ce urmează, vom avea nevoie și de noțiunea de mașină Turing probabilistică. În mașinile Turing obișnuite (se numesc determinist-deterministe pentru a le distinge de cele probabiliste), noua stare în care trece mașina la pasul următor este complet determinată de starea curentă și de simbolul că capul de pe bandă este vizionare. În mașinile probabilistice, noua stare poate depinde și de o variabilă aleatorie, care ia valorile 0 și 1 cu probabilitate de 1/2 fiecare. Alternativ, Criptografia și Teoria complexității 29 poate considera că o mașină Turing probabilistică are o bandă aleatorie suplimentară pe care este scris un șir aleator binar infinit. O bandă aleatorie poate fi citită doar într-o direcție, iar tranziția la o nouă stare poate depinde de caracterul care este vizualizat pe acea bandă. Luați în considerare acum următoarea întrebare firească: nu este ipoteza P^NP o condiție necesară și suficientă pentru existența unor scheme criptografice puternice? Necesitatea este, într-adevăr, în multe cazuri aproape evidentă. Să ne întoarcem la Exemplul 1. Definiți următorul limbaj L = ((Ki,d,i)\ există un mesaj m astfel încât Ek(m) = d și bitul său i este 1). Este clar că L? NP: în loc de căutarea exhaustivă descrisă în introducere, puteți pur și simplu să ghiciți textul simplu m și să verificați în timp polinom-polinom că Efdim) = d și al i-lea bit m este egal cu 1. Dacă da, atunci cuvântul de intrare (Ki,d,i) este acceptat, altfel este respins. Sub ipoteza P=NP, există un algoritm polinom-polinom determinist care recunoaște limbajul L. Cunoscând K\ și d, acest algoritm poate fi folosit pentru a calcula secvenţial, bit cu bit, textul simplu rn. Astfel, criptosistemul este instabil. Aceeași abordare: ghiciți cheia secretă și verificați (în timp polinom-polinom) corectitudinea ghicirii, este aplicabilă în principiu altor scheme criptografice. Cu toate acestea, în unele cazuri, apar dificultăți tehnice din cauza faptului că, conform informațiilor pe care le deține adversarul, valoarea dorită (text clar, cheie secretă etc.) nu este restaurată în mod unic. În ceea ce privește problema suficienței ipotezei P^NP, următoarea abordare se sugerează aici: alegeți o problemă NP-completă și construiți pe baza ei o schemă criptografică a cărei problemă de rupere (adică problema cu care se confruntă adversarul) ar fi NP. -deplin. Asemenea încercări au fost făcute la începutul anilor 1980, mai ales în legătură cu criptosistemele cu cheie publică, dar nu au dus la succes. Rezultatul tuturor acestor încercări a fost realizarea următorului fapt: chiar dacă P^NP, atunci orice problemă NP-completă se poate dovedi dificilă numai pe o secvență infinită de cuvinte de intrare. Cu alte cuvinte, definiția clasei NP include o măsură a complexității „cel mai rău caz”. Pentru stabilitatea unei scheme criptografic-criptografice este necesar ca problema adversarului să fie dificilă „aproape peste tot”. Astfel, a devenit clar că o presupunere mult mai puternică decât P^NP este necesară pentru securitatea criptografică. Și anume presupunerea existenței unor funcții unidirecționale. 30 Capitolul 2 3. Funcții unidirecționale În mod informal, o funcție unidirecțională este o funcție efectiv calculabilă pentru care nu există algoritmi eficienți de inversat. Prin inversare înțelegem problema masivă de a găsi, dintr-o valoare dată a unei funcții, una (lu- (orice) valoare din preimagine (rețineți că funcția inversă, în general, poate să nu existe). Funcția -way este centrală în criptografia matematică, mai jos dăm definiția sa formală. Fie E™ = (0,1)" mulțimea tuturor șirurilor binare de lungime n. Prin funcția / înțelegem familia (/n), unde /" : E" -> Em, m = m,( n) Pentru simplitate, presupunem că n trece prin întreaga serie naturală și că fiecare dintre funcțiile /n este definită peste tot. Se spune că o funcție / este sinceră dacă există un polinom q astfel încât n $ C q(m(n)) pentru toți n Definiția 1. Se spune că o funcție onesta / este unilaterală dacă 1. Există un algoritm polinom care calculează f(x) pentru orice x. 2. Pentru orice mașină de Turing probabilistică polinomială A, se respectă următoarele: Fie ales șirul x la întâmplare din mulțimea E" (notat x € q X "). Apoi, pentru orice al-lea polinom p și toate n suficient de mari 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, не мог вычислить ни одного бита открытого тек- текста. На acest moment S-a dovedit că existența funcțiilor unidirecționale este o condiție necesară și suficientă pentru existența unor criptosisteme puternice cu cheie secretă, precum și a unor protocoale criptografice puternice de mai multe tipuri, inclusiv protocoale de semnătură electronică. Pe de altă parte, există un rezultat al lui Impagliazzo și Rudich, care este un argument destul de puternic conform căruia anumite tipuri de scheme criptografic-criptografice (inclusiv protocoale de distribuție a cheilor de tip Diffie-Hellman) necesită ipoteze mai puternice decât cele presupuse. existenţa funcţiilor unidirecţionale. Din păcate, acest rezultat este prea complicat pentru a fi explicat în acest capitol. 4. Generatoare pseudo-aleatorie Un dezavantaj semnificativ al cifrului Vernam este că cheile sunt unice. Este posibil să scapi de acest dezavantaj reducând ușor durabilitatea? O modalitate de a rezolva această problemă de încercare este următoarea. Emițătorul și receptorul au o cheie secretă comună K de lungime n, iar cu ajutorul unui algoritm q suficient de eficient, generează din aceasta o secvență r - q(K) de lungime q(n), unde q este un polinom. Un astfel de cripto-criptosistem (notăm C r) vă permite să criptați un mesaj m (sau un set de mesaje) de până la q (n) biți lungime conform formulei d - r (B in, unde © este pe biți). adăugarea șirurilor de biți modulo 2. Deshi- Decriptarea se realizează după formula m = d φ r. Din rezultatele lui Shanno-Shannon rezultă că un astfel de criptosistem nu este absolut sigur, adică sigur împotriva oricărui adversar (care, totuși, este nu este greu de verificat direct).Ce se va întâmpla dacă se va cere să se apere doar împotriva unui adversar limitat polinomial care poate ataca criptosistemul doar cu ajutorul algoritmilor probabilistici polinom-polinomi?aceste întrebări au condus la conceptul de generator pseudo-aleatoriu , care a fost introdus de Blum și Micali. Fie q: (0,1) "-" (0,1)? n" o funcție calculabilă în polipolinom (din p) timp. O astfel de funcție se numește generator. Intuitiv, un generator q este pseudo-aleatoriu dacă secvențele generate de acesta nu pot fi distinse de orice algoritm ve-probabilistic polinomial de secvențe aleatoare de aceeași lungime q(n). În mod formal, acest obiect este definit după cum urmează. Fie A o mașină Turing probabilistică polinomială care primește șiruri binare de lungime q(n) ca intrare și scoate un bit ca rezultat al funcționării sale. Fie P(A, n) = Pr(A(r) = 1|r unitate (0, Criptografie și Teoria complexității 33) Probabilitatea aici este determinată de alegerea aleatorie a șirului r și a variabilelor aleatoare pe care A le folosește în lucru. Fie P2 (A,n) = Pr(A(g(s)) = l|e unități (0,1)"). Această probabilitate este determinată de alegerea aleatorie a rândului s și a variabilelor aleatoare care A folosește în lucrarea sa. Subliniem că funcția g este calculată printr-un algoritm determinist Definiția 2. Un generator g se numește generator pseudoaleator criptografic sigur dacă pentru orice mașină de Turing probabilistică polinom A, pentru orice polinom p, și toate n suficient de mari \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 - din mulțimea tuturor acestor divizori primi ai numărului p - 1, q - din mulțimea tuturor numerelor q astfel încât q9 = 1 mod p și x ∈ Zg. Atunci funcția f(x, p, q, g) = (gx mod p, p, q, q) este unidirecțională (vezi capitolul 2). Recomandat

Cărți. Descarcă gratuit cărți DJVU, PDF. Bibliotecă electronică gratuită
V.V. Iascenko, Introducere în criptografie

Puteți (programul îl va marca cu galben)
Puteți vedea lista de cărți de matematică superioară sortată alfabetic.
Puteți vedea lista de cărți de fizică superioară sortată alfabetic.

• Descărcare gratuită a cărții, volum 1,69 Mb, format .djvu
Ediția a doua, ed. Iașcenko V.V., septembrie 1999

Doamnelor si domnilor!! Pentru a descărca fișiere ale publicațiilor electronice fără „glitches”, faceți clic pe linkul subliniat cu fișierul butonul DREAPTA al mouse-ului, selectați o comandă "Salvează ținta ca ..." ("Salvează ținta ca...") și salvați fișierul e-pub pe computerul local. Publicațiile electronice sunt de obicei în formatele Adobe PDF și DJVU.

Capitolul 1. Concepte de bază ale criptografiei
1. Introducere
2. Subiect al criptografiei
3. Fundamente matematice
4. Direcții noi
5. Concluzie

Capitolul 2. Criptografia și teoria complexității
1. Introducere
2. Criptografie și ipoteză
3. Funcții unidirecționale
4. Generatoare de pseudorandom
5. Dovezi cu cunoștințe zero

Capitolul 3 Protocoale criptografice
1. Introducere
2. Integritate. Protocoale de autentificare și semnătură electronică
3. De negăsit. Bani electronici
4. Protocoale precum „aruncarea unei monede pe telefon”
5. Încă o dată despre împărtășirea unui secret
6. Hai să ne jucăm „cupe”. Protocoale de vot
7. Dincolo de ipotezele standard. Mesaje confidențiale
8. În loc de o concluzie

capitolul 4
1. Introducere
2. Sistem de criptare RSA
3. Complexitatea algoritmilor teoreticii numerelor
4. Cum să distingem un număr compus de un număr prim
5. Cum se construiesc numere prime mari
6. Cum să testați un număr mare pentru primalitate
7. Cum se factorizează numerele compuse
8. Logaritm discret
9. Concluzie

Capitolul 5. Matematica împărtășirii secrete
1. Introducere
2. Partajare secretă pentru structurile de acces arbitrar
3. Partajarea liniară a secretelor
4. Partajare secretă perfectă și matroizi

Capitolul 6
1. În loc de o introducere
2. Un pic de teorie
3. Cum se criptează un fișier?
4. Învață din greșelile altora
5. În loc de o concluzie

Capitolul 7
1. Introducere
2. Cifre de substituție
3. Cifre de permutare
4. Cifre de substituție polialfabetică cu cheie periodică
5. Condiţiile problemelor olimpiadelor la matematică şi criptografie
6. Direcții și decizii

Anexă: un extras din articolul lui K. Shannon „Teoria comunicării în sistemele secrete”

Scurt rezumat al cărții

Sub total ed. V.V.Iascenko. Autori: V. V. Yashchenko (editor, capitolul 1), N. P. Varnovsky (capitolele 2, 3), Yu. V. Nesterenko (capitolul 4), G. A. Kabatyansky (capitolul 5), P. N Devyanin, V. G. Proskurin, A. V. Cheremushkin (capitolul ), P. A. Gyrdymov, A. Yu. Zubov, A. V. Zyazin, V. N. Ovchinnikov (Capitolul 7).

Pentru prima dată în limba rusă, cartea oferă o prezentare sistematică a fundamentelor științifice ale criptografiei de la cele mai simple exemple și concepte de bază până la construcții criptografice moderne. Înțelegerea principiilor criptografiei a devenit o necesitate pentru mulți datorită utilizării pe scară largă a instrumentelor de securitate a informațiilor criptografice. Prin urmare, cartea poate fi utilă cititorului general. Cartea este destinată studenților de la matematică și specialiști în securitatea informațiilor.

Criptografia - știința cifrurilor - a fost clasificată mult timp, deoarece a fost folosită în principal pentru a proteja secretele de stat și militare. În prezent, metodele și mijloacele de criptare sunt folosite pentru a asigura securitatea informațiilor nu numai a statului, ci și a persoanelor și organizațiilor. Aceasta nu este neapărat o chestiune de secrete. Prea multe informații diferite „plimbă” în jurul lumii în formă digitală. Și deasupra acestor informații există amenințări de cunoaștere neprietenoasă, acumulare, înlocuire, falsificare etc. Criptografia este cea care oferă cele mai fiabile metode de protecție împotriva unor astfel de amenințări.

Până acum, algoritmii criptografici pentru consumatorul mediu sunt un secret cu șapte sigilii, deși mulți au fost deja nevoiți să folosească unele instrumente criptografice: criptarea e-mailului, carduri bancare inteligente etc. Desigur, principala întrebare pentru utilizator este dacă acest instrument criptografic oferă protecţie fiabilă. Dar nici să formulezi corect această întrebare elementară nu este ușor. De ce dușman ne apărăm? Care sunt opțiunile pentru acest inamic? Ce obiective poate urmări? Cum se măsoară fiabilitatea protecției? Lista cu astfel de întrebări poate fi continuată. Pentru a le răspunde, utilizatorul are nevoie de cunoștințe despre conceptele de bază ale criptografiei.

O expunere populară a fundamentelor științifice ale criptografiei (vorbim doar despre criptografia „non-statală”; secțiunile criptografiei legate de securitatea statului ar trebui să rămână secrete) este scopul acestei cărți. Poate fi folosit și ca ajutor didactic. Nu există încă cărți similare în rusă. Materialele unui număr de capitole au fost publicate de autori mai devreme în alte publicații (capitolul 1 - în cartea lui S. A. Dorichenko, V. V. Yashchenko, „25 de studii asupra cifrurilor”, M .: TEIS, 1994; capitolele 1,2,4; ,5 - în revista „Educația matematică”, seria a treia, numărul 2, M .: MTsNMO, 1998; capitolul 7 - în ziarul „Informatika” (supliment săptămânal la ziarul „Pervoe septembrie”), N 4, ianuarie 1998 ). În pregătirea acestei ediții, aceste materiale au fost revizuite și completate. Prezentarea materialului este concepută pentru un cititor cu mentalitate matematică.

În cea mai mare parte, capitolele sunt independente unele de altele (acest lucru se realizează printr-o anumită repetiție) și pot fi citite în orice ordine. Capitolul 1 - introductiv - este recomandat pentru toți să citească, deoarece explică toate conceptele de bază ale criptografiei moderne la un nivel popular: cifru, cheie, securitate, semnătură digitală electronică, protocol criptografic etc. În alte capitole, o parte a materialului se repetă, dar mai profund. Capitolele 2, 3, 4, 5 folosesc o parte din informațiile de la matematică superioară cunoscute elevilor claselor de matematică și studenților. Capitolul 6 se adresează experților în tehnologia computerelor. Capitolul 7 conține materiale pentru olimpiadele de criptografie pentru școlari și, prin urmare, nu sunt necesare cunoștințe dincolo de programa școlară pentru a-l citi.

Avertisment: Instrumentele criptografice și produsele software menționate în această carte sunt folosite doar pentru a ilustra idei criptografice generale; autorii nu și-au propus să evalueze sau să compare instrumentele criptografice disponibile pe piață.

Criptografia a fost pusă pe o bază științifică, în mare parte datorită muncii remarcabilului om de știință american Claude Shannon. Raportul său „Teoria matematică a criptografiei” a fost pregătit în secret în 1945, declasificat și publicat în 1948, tradus în rusă în 1963. Deoarece „Works on Information Theory and Cybernetics” (1963) de C. Shannon a devenit o raritate bibliografică, am inclus în anexă partea principală a articolului lui K. Shannon „Teoria comunicării în sistemele secrete”. Această lucrare fundamentală este lectură recomandată pentru oricine este interesat de criptografie.

Pentru o înțelegere profesională a algoritmilor criptografici și capacitatea de a le evalua punctele forte și punctele slabe, este necesară o pregătire matematică serioasă (la nivelul departamentelor de matematică ale universităților). Acest lucru se datorează faptului că criptografia modernă se bazează pe rezultatele profunde ale unor ramuri ale matematicii precum teoria complexității calculelor, teoria numerelor, algebra, teoria informației etc. Cei care doresc să studieze serios criptografia pot recomanda monografia de revizuire. „Cryptography in Banking” de Anokhin M. I., Varnovsky N. P., Sidelnikova V. M., Yashchenko V. V., M.: MEPhI, 1997.

Cum să transferați informațiile necesare către destinatarul necesar în secret de la alții? Fiecare dintre cititori, în momente diferite și cu scopuri diferite, probabil a încercat să rezolve singuri această problemă practică (pentru comoditatea referințelor ulterioare, o vom numi „problema TP”, adică problema transmisiei secrete). După ce a ales soluția potrivită, cel mai probabil a repetat invenția uneia dintre metodele de transmitere sub acoperire a informațiilor, care are deja mai mult de o mie de ani.

Reflectând la problema TP, nu este greu să ajungem la concluzia că există trei posibilități.
1. Creați un canal de comunicare absolut fiabil între abonați, inaccesibil celorlalți.
2. Folosiți un canal de comunicare public, dar ascundeți însuși faptul transferului de informații.
3. Folosiți un canal de comunicare public, dar transmiteți prin acesta informațiile necesare într-o formă atât de transformată încât doar destinatarul să le poată restaura.

Să comentăm aceste trei posibilități.
1. Cu nivelul actual de dezvoltare a științei și tehnologiei, este aproape imposibil să se realizeze un astfel de canal de comunicare între abonații la distanță pentru transmiterea repetată a unor cantități mari de informații.
2. Steganografia este angajată în dezvoltarea mijloacelor și metodelor de a ascunde faptul transmiterii unui mesaj.

Primele urme ale metodelor steganografice se pierd în vremuri străvechi. De exemplu, o astfel de metodă de a ascunde un mesaj scris este cunoscută: capul unui sclav a fost bărbierit, a fost scris un mesaj pe scalp, iar după ce părul a crescut din nou, sclavul a fost trimis destinatarului. Din lucrările polițiste sunt binecunoscute diverse metode de scriere secretă între rândurile textului obișnuit, neprotejat: de la lapte la reactivi chimici complecși cu prelucrare ulterioară.

Metoda „microdot” este cunoscută și de la detectivi: un mesaj este înregistrat folosind tehnologia modernă pe un mediu foarte mic (microdot), care este trimis cu o scrisoare obișnuită, de exemplu, sub o ștampilă sau în alt loc, în loc prestabilit.

În prezent, datorită utilizării pe scară largă a computerelor, sunt cunoscute multe metode subtile pentru „ascunderea” informațiilor protejate în cantități mari de informații stocate într-un computer. Un exemplu ilustrativ de ascundere a unui fișier text într-o grafică poate fi găsit pe Internet; este dat și în revista Computerra, N48 (225) din 1 decembrie 1997, la pagina 62. (De remarcat că autorii articolului din revistă trimit în mod eronat steganografia la criptografie. texte, dar, în general, steganografia și criptografia sunt domenii fundamental diferite în teoria și practica securității informațiilor.)

3. Criptografia este angajată în dezvoltarea metodelor de conversie (criptare) a informațiilor pentru a le proteja de utilizatorii ilegali. Astfel de metode și modalități de conversie a informațiilor se numesc cifruri.

Criptarea (criptarea) este procesul de aplicare a unui cifr la informațiile protejate, adică conversia informațiilor protejate (text simplu) într-un mesaj criptat (text cifrat, criptogramă) utilizând anumite reguli conținute în cifru.

Decriptarea este un proces care este inversul criptării, adică conversia unui mesaj criptat în informații protejate folosind anumite reguli conținute în cifr.

Criptografia este o știință aplicată, folosește cele mai recente realizări ale științelor fundamentale și, în primul rând, matematica. Pe de altă parte, toate sarcinile specifice criptografiei depind în esență de nivelul de dezvoltare a tehnologiei și tehnologiei, de mijloacele de comunicare utilizate și de metodele de transmitere a informațiilor.

Subiectul criptografiei. Care este subiectul criptografiei? Pentru a răspunde la această întrebare, să revenim la problema TP pentru a clarifica situația și conceptele folosite. În primul rând, observăm că această problemă apare doar pentru informațiile care necesită protecție. De obicei în astfel de cazuri se spune că informația conține un secret sau este protejată, privată, confidențială, secretă. Pentru situațiile cele mai tipice și frecvent întâlnite de acest tip, au fost introduse chiar și concepte speciale:
- secret de stat;
- un secret militar;
- secret comercial;
- secretul juridic;
- secretul medical etc.

În continuare vom vorbi despre informațiile protejate, ținând cont de următoarele caracteristici ale unor astfel de informații:
- există un anumit cerc de utilizatori legitimi care au dreptul de a deține aceste informații;
- exista utilizatori ilegali care cauta sa achizitioneze aceste informatii pentru a le valorifica in propriul beneficiu, si in detrimentul utilizatorilor legitimi.

Cărți, descărcați cărți, descărcați cărți, cărți online, citiți online, descărcați cărți gratis, citiți cărți, citiți cărți online, citiți, bibliotecă online, cărți citite, citiți online gratis, citiți cărți gratis, ebook, citiți cărți online, cele mai bune cărți de matematică și fizică, cărți interesante matematică și fizică, cărți electronice, cărți gratis, cărți pentru descărcare gratuită, descărcare gratuită cărți matematică și fizică, descărcare cărți gratuit complet, bibliotecă online, cărți descărcate gratuit, citiți cărți online gratuit fără înregistrare matematică și fizică, citește cărți online gratuit matematică și fizică, bibliotecă electronică matematică și fizică, cărți pentru a citi online matematică și fizică, lumea cărților matematică și fizică, citește gratuit matematică și fizică, bibliotecă online matematică și fizică, cărți de citit matematică și fizică, cărți online gratuit matematică și fizică , cărți populare matematică și fizică, bibliotecă de cărți gratuite matematică și fizică, descărcare electr carte gratuită de matematică și fizică, bibliotecă online gratuită de matematică și fizică, descărcare de cărți electronice, manuale de matematică și fizică online, bibliotecă de cărți electronice de matematică și fizică, descărcare gratuită de cărți electronice fără înregistrare matematică și fizică, cărți bune de matematică și fizică, descărcare cărți complete matematică și fizică, bibliotecă electronică citită gratuit matematică și fizică, bibliotecă electronică descărcare gratuită matematică și fizică, site-uri pentru descărcare cărți matematică și fizică, cărți inteligente matematică și fizică, căutare cărți matematică și fizică, descărcare cărți electronice matematică gratuită și fizică, descărcare cărți electronice matematică și fizică, cele mai bune cărți despre matematică și fizică, bibliotecă electronică pentru matematică și fizică gratuite, citiți cărți online gratuite despre matematică și fizică, site pentru cărți despre matematică și fizică, bibliotecă electronică, cărți online pentru citește, carte de matematică și fizică electronică, site pentru descărcarea cărților gratuit și fără înregistrare , o bibliotecă online gratuită de matematică și fizică, de unde puteți descărca gratuit cărți de matematică și fizică, citiți cărți gratuit și fără înregistrare matematică și fizică, descărcați manuale de matematică și fizică, descărcați cărți electronice gratuite de matematică și fizică, descărcați cărți gratuite complet, bibliotecă online gratuit, cele mai bune cărți electronice matematică și fizică, bibliotecă online de cărți matematică și fizică, descărcați cărți electronice gratuit fără înregistrare, descărcare bibliotecă online gratuit, de unde descărcați cărți gratuite, e- biblioteci gratuite, cărți electronice gratuite, biblioteci electronice gratuite, bibliotecă online gratuită, cărți gratuite pentru a citi, cărți online pentru a citi gratuit, citire gratuit online, cărți interesante pentru a citi online matematică și fizică, citire cărți online matematică și fizică, bibliotecă electronică online matematică și fizică, bibliotecă gratuită de cărți electronice matematică și fizică, bibliotecă online de citit, citit gratuit și fără înregistrare și matematică și fizică, găsiți o carte de matematică și fizică, catalog de cărți de matematică și fizică, descărcați cărți online gratuit de matematică și fizică, biblioteca online de matematică și fizică, descărcați cărți gratuite fără înregistrare matematică și fizică, de unde puteți descărca cărți gratuite de matematică și fizică, de unde poți descărca cărți, site-uri pentru descărcare gratuită de cărți, online pentru a citi, bibliotecă de citit, cărți de citit online gratuit fără înregistrare, bibliotecă de cărți, bibliotecă online gratuită, bibliotecă online de citit gratuit , cărți de citit gratuit și fără înregistrare, bibliotecă electronică pentru a descărca cărți gratuit, online pentru a citi este gratuit.

,
Din 2017, reluăm versiunea mobilă a site-ului web pentru telefoane mobile (design text abreviat, tehnologie WAP) - butonul de sus din colțul din stânga sus al paginii web. Dacă nu aveți acces la Internet printr-un computer personal sau un terminal de internet, puteți utiliza telefonul mobil pentru a vizita site-ul nostru web (design prescurtat) și, dacă este necesar, puteți salva datele de pe site în memoria telefonului mobil. Salvați cărți și articole pe telefonul mobil (internet mobil) și descărcați-le de pe telefon pe computer. Descărcarea comodă a cărților prin telefonul mobil (în memoria telefonului) și pe computer prin interfața mobilă. Internet rapid fără etichete inutile, gratuit (pentru prețul serviciilor de internet) și fără parole. Materialul este oferit spre revizuire. Link-urile directe către fișiere de cărți și articole de pe site și vânzarea acestora de către terți sunt interzise.

Notă. Un link text convenabil pentru forumuri, bloguri, citarea materialelor site-ului web, codul html poate fi copiat și pur și simplu lipit în paginile dvs. web atunci când citați materialele site-ului nostru. Materialul este oferit spre revizuire. De asemenea, salvați cărți pe telefonul mobil prin Internet (există o versiune mobilă a site-ului - linkul este în partea din stânga sus a paginii) și descărcați-le de pe telefon pe computer. Linkurile directe către fișierele cărților sunt interzise.

Pentru prima dată în limba rusă, cartea oferă o prezentare sistematică a fundamentelor științifice ale criptografiei de la cele mai simple exemple și concepte de bază până la construcții criptografice moderne. Înțelegerea principiilor criptografiei a devenit o necesitate pentru mulți datorită utilizării pe scară largă a instrumentelor de securitate a informațiilor criptografice. Prin urmare, cartea poate fi utilă cititorului general.
Cartea este destinată studenților de la matematică și specialiști în securitatea informațiilor.

Subiectul criptografiei.
Care este subiectul criptografiei? Pentru a răspunde la această întrebare, să revenim la problema TP pentru a clarifica situația și conceptele folosite.

În primul rând, observăm că această problemă apare doar pentru informațiile care necesită protecție. De obicei în astfel de cazuri se spune că informația conține un secret sau este protejată, privată, confidențială, secretă. Pentru situațiile cele mai tipice și frecvent întâlnite de acest tip, au fost introduse chiar și concepte speciale:
- secret de stat;
- un secret militar;
- secret comercial;
- secretul juridic;
- secretul medical etc.

În continuare vom vorbi despre informațiile protejate, ținând cont de următoarele caracteristici ale unor astfel de informații:
- există un anumit cerc de utilizatori legitimi care au dreptul de a deține aceste informații;
- există utilizatori ilegali care caută să obțină aceste informații pentru a. să-l transforme în propriul beneficiu și în detrimentul utilizatorilor legitimi.

Pentru simplitate, ne vom limita mai întâi să luăm în considerare o singură amenințare - amenințarea dezvăluirii de informații. Există și alte amenințări la adresa informațiilor protejate de la utilizatorii ilegali: înlocuirea, imitarea etc. Despre ele vom vorbi mai jos.

Cuprins
Prefaţă
Capitolul 1. Concepte de bază ale criptografiei
§unu. Introducere
§2. Subiectul criptografiei
§3. Fundamente matematice
§patru. Destinații noi
§5. Concluzie
Capitolul 2. Criptografia și teoria complexității
§unu. Introducere
§2. Criptografia și ipoteza P = NP
§3. Funcții unidirecționale
§patru. Generatoare pseudorandom
§5. Dovezi cu cunoștințe zero
Capitolul 3 Protocoale criptografice
§unu. Introducere
§2. Integritate. Protocoale de autentificare și semnătură electronică
§3. Imposibil de urmărit. Bani electronici
§patru. Protocoale de aruncare a monedelor
§5. Mai multe despre împărtășirea unui secret
§6. Hai să jucăm zaruri. Protocoale de vot
§7. Dincolo de ipotezele standard. Mesaje confidențiale
§opt. În loc de concluzie
capitolul 4
§unu. Introducere
§2. Sistem de criptare RSA
§3. Complexitatea algoritmilor teoreticii numerelor
§patru. Cum să deosebești un număr compus de un număr prim
§5. Cum se construiesc numere prime mari
§6. Cum se verifică dacă un număr mare este prim
§7. Cum se factorizează numerele compuse
§opt. Logaritm discret
§9. Concluzie
Capitolul 5. Matematica împărtășirii secrete
§unu. Introducere
§2. Partajare secretă pentru structurile de acces arbitrar
§3. Partajarea liniară a secretelor
§patru. Separarea perfectă dintre secret și matroid
Capitolul 6
§unu. În loc de o introducere
§2. Un pic de teorie
§3. Cum se criptează un fișier?
§patru. Să învățăm din greșelile altora
§5. În loc de concluzie
Capitolul 7
§unu. Introducere
§2. Cifre de substituție
§3. Cifre de permutare
§patru. Cifre de substituție polialfabetică cu o cheie periodică
§5. Condițiile problemelor olimpiadelor de matematică și criptografie
§6. Direcții și soluții
Anexa A. Un extras din articolul lui K. Shannon „Teoria comunicării în sistemele secrete”
Anexa B. Lista adnotată a lecturilor recomandate
Anexa B. Glosar de termeni criptografici
Index alfabetic al termenilor rusi
Index alfabetic al termenilor englezi.

Descărcați gratuit o carte electronică într-un format convenabil, vizionați și citiți:
Descarcă cartea Introducere în criptografie, Yaschenko V.V., 2012 - fileskachat.com, descărcare rapidă și gratuită.

Descărcați pdf
Mai jos puteți cumpăra această carte la cel mai bun preț redus cu livrare în toată Rusia.

În criptografie, un număr prim aleatoriu este înțeles ca un număr prim care conține un număr dat de biți în notație binară, pe algoritmul de generare al căruia sunt impuse anumite restricții. Obținerea numerelor prime aleatoare este ... ... Wikipedia

Martin Hellman Martin Hellman (Martin E. Hellman; născut la 2 octombrie 1945) este un criptograf american. A câștigat faimă datorită dezvoltării primului sistem criptografic asimetric în colaborare cu Whitfield Diffie și Ralph Merkle (1976). Una dintre ...... Wikipedia

Criptomașina germană Lorenz a fost folosită în timpul celui de-al Doilea Război Mondial pentru a cripta cele mai secrete mesaje Criptografia (din altă greacă ... Wikipedia

Criptomașina germană Lorenz a fost folosită în timpul celui de-al Doilea Război Mondial pentru a cripta cele mai secrete mesaje Criptografia (din greacă κρυπτός ascuns și γράφω scriu) știința metodelor matematice pentru asigurarea confidențialității ... ... Wikipedia

Descompunerea în factori a unui număr natural este descompunerea lui într-un produs de factori primi. Existența și unicitatea (până la ordinea factorilor) unei astfel de descompunere rezultă din teorema fundamentală a aritmeticii. Spre deosebire de ...... Wikipedia

Consta din proceduri care prevăd: includerea utilizatorilor în sistem; generarea, distribuția și introducerea cheilor în echipament; controlul utilizării cheilor; schimbarea și distrugerea cheilor; arhivarea, stocarea și restaurarea cheilor. ... ... Wikipedia

Acest articol trebuie rescris complet. Pot exista explicații pe pagina de discuții. Există două clase de sisteme de comunicații: digitale și analogice... Wikipedia

Un număr prim este un număr natural care are exact doi divizori naturali diferiți: unul și el însuși. Toate celelalte numere naturale, cu excepția unuia, se numesc compuse. Astfel, toate numerele naturale sunt mai mari decât unu ...... Wikipedia

Test de primalitate polinomială probabilistică. Testul Miller Rabin vă permite să determinați în mod eficient dacă un anumit număr este compus. Cu toate acestea, nu poate fi folosit pentru a demonstra riguros că un număr este prim. Cu toate acestea, testul Miller Rabin este adesea ... ... Wikipedia

Testul de primalitate este un algoritm care, dat un număr natural, determină dacă numărul dat este prim. Există teste deterministe și probabiliste. Determinarea simplității unui număr dat în cazul general nu este o sarcină atât de banală. Doar ...... Wikipedia

Mod de criptare O metodă de aplicare a unui cifru bloc pentru a converti o secvență de blocuri de date simple într-o secvență de blocuri de date criptate. În același timp, datele de la altul pot fi folosite pentru a cripta un bloc... Wikipedia