Astăzi despre alte cifre, deși sunt legate de criptosisteme cu cheie secretă. Ele sunt uneori numite stream, uneori streaming.
Ce este un cifru de flux? Dacă cifrul de bloc funcționează cu o cantitate mare de informații și criptează întregul bloc, cipul de flux funcționează cu biți. Foarte rar funcționează cu octeți.
Cifrul fluxului este dezvoltarea cifrului Vernon, care a fost inventat în 1917, chiar înainte de apariția criptografiei ca știință. Particularitatea acestui cifr este că se poate dovedi, că în anumite condiții este absolut stabilă.
Funcționează astfel - aveți un flux de text deschis și un flux cheie, firele sunt adăugate bit-by-bit modulo două și obțin fluxul de text cipher.
A fost dovedită de un om ca Claude Shannon, care a început să studieze cifrele și a matematizat întreaga teorie. Și el a demonstrat că dacă cheia folosită în cifrul lui Vernon este egală cu lungimea textului deschis și cheia este aleasă în mod aleatoriu și cheia este utilizată exact o dată, atunci este absolut stabilă.
Dar acesta este doar un model, ca și Mașina Turing.
Dar în sistemele reale nu există nimic absolut aleatoriu. Dacă alegeți o cheie egală cu lungimea plaintextului, puteți alege în continuare absolut aleatoriu greu.
Și aș vrea să am un algoritm determinist care generează o gamă cheie.
Se pune întrebarea, ce facem? Cum s-ar modifica cifrul este adevărat, pentru a obține un sistem criptostic practic.
Orice cifru de flux clasic este un flux cheie. Mai mult, acest flux cheie este adăugat modulo doi cu textul plaintext și textul criptat este obținut.
Cel mai important element este o funcție care exprimă o gamă cheie. În sine depinde de o cheie care este hrănită la intrare.
Există o cutie, puneți cheia acolo, apăsați butonul, dă un pic. Acești biți pe care îi folosiți ca o gamă.
Cipurile de flux generează doar o gamă, fără operațiuni complicate cu plaintext, la fel ca în șifile de blocuri acolo.
Cipurile de flux au un mic dezavantaj - în sine nu protejează împotriva distorsiunilor intenționate. Cipurile de flux furnizează numai confidențialitate. În modurile de blocare, există moduri în care se menține protecția împotriva distorsiunii.
Foarfece cu feedback. Generarea unui nou bit ca o funcție a celor anterioare. Foarte des se utilizează funcția obișnuită liniară. Teoretic poți folosi neliniar. Dar aproape întotdeauna folosiți liniare.
Regiștrii de deplasare pentru care funcția de feedback este liniară se numesc registre de deplasare liniară.
Dacă vorbim despre registrele de deplasare deloc. Orice registru de deplasare liniară cu feedback liniar poate fi specificat nu doar ca coeficienți ai unei funcții liniare, ci ca un polinom.
Cel mai înalt grad al polinomului este egal cu lungimea registrului de deplasare.
Odată ce registrul de deplasare exprimă gama cheie, se poate întâmpla ca, datorită finitei registrului nostru, secvența să fie periodică.
Dar ce se întâmplă dacă secvența se repetă după câteva bare? Apoi, cheia noastră va fi foarte rea, vom obține o secvență non-aleatoare.
Am dori să avem un astfel de registru de deplasare, astfel încât perioada acestei secvențe să fie maximă. Și apoi apare întrebarea - cum să facem ca perioada să fie maximă? Cum determinați perioada registrului de deplasare?
Pentru a răspunde la întrebarea privind maximul, să ne întoarcem la statele de înregistrare. De când începe să se repete gamma? Când ajungi la stat, care deja a căzut. Perioada maximă a secvenței poate fi ce? 2 ^ (lungimea registrului) este 1.
Să examinăm exemplul s0 * s1 + s2. Polinomul caracteristic 1 + x 2 + x 3 000 -> 000
În cazul unui raster neliniar, perioada este puțin previzibilă.
Dar în cazul unei liniare există o ipoteză - pentru ca aceasta să aibă o perioadă maximă, polinomul său caracteristic trebuie să fie ireductibil față de rf2.
De fapt, aproprierea polinomilor nu este suficientă.
Este necesar ca polinomul să fie primitiv.
Dovada că 1 + x + x ^ 4 nu va avea o perioadă maximă.
Ce este un polinom inerent?
Mai întâi trebuie să dăm o astfel de definiție - să specificăm ordinea polinomului. Ordinea polinomului este un număr minim de n astfel încât polinomul x ^ n - 1 este divizibil prin F (x).
Nu intrăm în junglă de câmpuri finite, dar acest ordin este o caracteristică importantă.
Se spune că un polinom este primitiv, dacă ordinul lui este 2 ^ n-1.
Se poate demonstra că orice polinom ireductibil împarte un polinom.
a + b mod p p * b mod p
Și să nu aibă rădăcini în acest câmp.
Se spune că un polinom este primitiv, dacă prin această alfa este posibil să exprime toate elementele slăbite ale câmpului.
Dacă luați un polinom care nu este primitiv, atunci totul nu se va alinia în lanț.
Am luat registrul de deplasare, zeros zabbahali și odinichki, am luat un polinom opțional, a cerut regulile de funcționare.
Se poate demonstra că secvența formată pe un registru de deplasare este aproape aleatorie.
Dacă luați n = 256, atunci perioada va fi de 2 ^ 256. Adică, cu o lungime mică a registrului, se poate obține o secvență aleatorie de lungime ireală. Dar există o captură.
Polinomul, de fapt, este cheia.
Totul ar fi bine dacă doi oameni nu ne-ar fi supărat și nu am venit cu un adlgoritm care să-și recapete registrul într-o mică succesiune. Au fost numiți Berlekamp și Messi.
Este un clasic, a folosit foarte mult unde.
Demonstrarea algoritmului Berlekamp messi.
În cele din urmă am ajuns la cele mai interesante.
Ideea utilizării registrelor cu feedback a eșuat. Ce ar trebui să fac? Cum de a trăi mai departe?
Care este problema în registrul nostru? Este aproape pretutindeni liniară. Trebuie să introducem neliniaritatea.
Să facem un filtru. Nu vom da o gamă în sine, ci un fel de funcție neliniară din gamma. O altă idee este utilizarea altor tipuri de neliniaritate
Avem un registru preferat de deplasare liniară, dar gama nu este aruncată din celula stângă, ci este o funcție nelineară a statului. Adică, de la stat la stat, schimbăm liniar, dar gama este considerată a fi o funcție neliniară a statului. Există dezvoltarea acestei idei.
Există o funcție neliniară a en variabilelor. Și fiecare variabilă este produsă de un registru de deplasare separat.
Se poate demonstra că prima variantă se reduce la cea de-a doua.
Deci, când a fost doar un registru, secvența era aproape aleatorie. Am lăsat-o prin filtru. Cine a spus că secvența va fi aleatoare?
Care este distanța maximă?
max = ρ (f, A) Considerăm transformarea Hammer-Hadamard - extinderea în baza funcțiilor ortogonale.
Distanța maximă este 2 n - 2 (n / 2) dacă este egală. Funcțiile pe care se obține maximul sunt numite funcții îndoite.
Deci, am aflat că funcția ar trebui să fie o funcție îndoită, trebuie să fie echilibrată, mai mult, trebuie să fie perfect echilibrată.
Să înlocuim o constantă pentru variabile. Dacă noua funcție este dezechilibrată, atunci puteți efectua un atac prin înlocuirea cu zero a variabilelor necesare și încercarea de a scoate corelațiile.
De exemplu, dacă este sub forma unei funcții de filtrare, cum ar fi x * y \ xor x * z \ xor z. z = 1 => xy
f (x, y, z) = z cu probabilitate 3/4. Și cu aceeași credință este egal cu X.
Și asta înseamnă că poți sorta doar prin valorile lui X. Și ai un detector de ghicit - o șansă de coincidență de 3/4. De asemenea, puteți restabili registrul z. Combinând apoi puteți restaura jocul.
Astfel de atacuri se numesc atacuri corelaționale. Complexitatea este mult redusă. Dacă puterea registrelor a fost n1 n2 n3, atunci o căutare completă ar fi 2 (n 1 + n 2 + n 3). atunci căutarea va fi 2 n 1 + 2 n 2 + 2 n 3
Cipurile greșite pot fi văzute prin accesarea https: \\ mail.ru
Dacă utilizați crom, acesta arată o blocare și acolo se spune în descriere că conexiunea este protejată de rc4 128. Cifrul rc4 este streaming, a fost rupt în mod repetat și nu este sigur pentru seyas.
Trimiteți-le prietenilor: