Puncte:2

Shift crypt, perfect sigur?

drapel in

Știu că, dacă doar un caracter este criptat folosind un cifr de schimbare, atunci cifrul de schimbare este perfect sigur. Dar dacă spațiul tastelor este mai mare decât spațiul mesajelor? Ar fi încă perfect sigur? Cred că ar fi totuși un da, dar nu știu cum să mă descurc cu cheile nefolosite.

Teorema 2.10 (Introducere în criptografia modernă, ediția a doua) precizează că o schemă de criptare perfect secretă trebuie să aibă dimensiunea cheilor cel puțin la fel de mare ca și mesajele. Autorul o demonstrează prin contradicție, așa că de fapt este greu de văzut ce se întâmplă dacă spațiul cheie conține mai multe elemente.

forest avatar
drapel vn
Este perfect sigur în același mod în care un cifr XOR pe un singur bit este perfect sigur atunci când criptează un singur bit.
drapel in
@forest De ce totuși? Răspunsul lui Daniel S arată un contraexemplu.
Puncte:1
drapel ru

Nu neaparat. Luați în considerare un cifr de schimbare Caesar pe alfabetul roman de 26 de caractere. Mapăm litera la unul dintre numerele 0-25, să zicem $x$ și adăugați o valoare cheie $k\în [0,25]$ calcula $y=x+k\mod {26}$ și apoi mapa înapoi la alfabet. Dacă $k$ este ales uniform la întâmplare, atunci acesta este perfect sigur. Cu toate acestea, dacă mărim gama de $k$ a zice $[0,30]$ acest lucru nu mai este perfect sigur ca valori $x+0\mod {26}$, $x+1\mod{26}$, $x+2\mod{26}$, $x+3\mod{26}$ și $x+4\mod{26}$ sunt de două ori mai probabile decât celelalte texte cifrate. Acest lucru oferă informații semnificative despre $x$ și de aici textul simplu. De exemplu, dacă vedem textul cifrat „b” corespunzător $y=1$ avem mai multe dovezi că $x=23, 24, 25, 0, 1$ decât celelalte valori. Prin urmare, statistica bayesiană mărește credința noastră că litera text simplu se află în mulțimea {'x','y','z','a','b'} și scade credința noastră că se află în afara acestui set. Nu am fi capabili să facem această inferență cu un cifr perfect sigur.

În mod obișnuit, pentru a obține uniformitatea necesară pentru o securitate perfectă, spațiul cheilor trebuie să fie un multiplu al unei dimensiuni a spațiului de text cifrat și cheile selectate uniform la întâmplare. Cu toate acestea, se poate obține o securitate perfectă prin alte mijloace (de exemplu, în schema de mai sus, dacă selectăm cheile $\{0,1,2,3,4,26,27,28,29,30\}$ cu probabilitatea 1/52 și alte chei cu probabilitatea 1/26, atunci cifrul de schimbare este încă perfect sigur.

drapel in
Cred că am înțeles de ce sunt de două ori mai probabile decât celelalte texte cifrate, deoarece dacă $x=0$, atunci $0+1\mod\ 26 = 1 = 0 + 27\mod\ 26$. Dar de ce oferă mai multe informații despre $x$ și, prin urmare, textul simplu? Ai putea te rog să detaliezi mai multe?
Daniel S avatar
drapel ru
Am mai adăugat câteva cuvinte; anunțați-mă dacă sunt necesare clarificări suplimentare.
drapel in
Cred că îl văd acum: pentru un mesaj arbitrar care nu este în „setul nostru de credințe” $m$, $P(M=m\mid C = y = 1) = 0$, între timp $P(M=m) = 1/26 USD. Astfel, prin definiție nu este perfect sigur, nu?
Daniel S avatar
drapel ru
Aproape. Pentru un mesaj uniform $M$ și pentru $m$ în afara setului nostru de convingeri $P(M=m|C=y=1)=1/30$ și pentru $m$ în interiorul setului nostru de convingeri $P(M=m| C=y=1)=1/15$. Ambele sunt distincte de uniforma anterioară 1/26 și astfel nu este atinsă securitatea perfectă.
drapel in
Cum ați obținut 1/30 USD și 1/15 USD? Dacă $y=1$ nu am ști că numai valorile posibile sunt $x=23,24,25,0,1$ și, prin urmare, dacă un mesaj este în afara setului nostru de convingeri, $P(M=m\mid C =y=1) = 0$?
Daniel S avatar
drapel ru
Deoarece pentru fiecare $m$ din afara setului nostru de credințe există exact 1 valoare de $k$ din 30 care ar duce la $y=1$ și pentru fiecare $m$ din setul nostru de credințe există 2 valori de $k$ din 30 care ar duce la $y=1$.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.