citesc Introducere în criptografia modernă ediția a treia (Previzualizarea Google Books a secțiunii relevante, paginile 10-11) și mă străduiesc să înțeleg descrierea unei metode de atac pe un cifr de substituție monoalfabetic.
Pare a fi o versiune îmbunătățită a unei abordări de analiză a frecvenței literelor, eliminând nevoia de a „verifica ce are sens” manual. Câteva informații date:
- Tuturor literelor din limba engleză li se atribuie o valoare 0-25
- O cheie necunoscută, folosită pentru a codifica textul simplu în text cifrat, este formată dintr-o mapare aleatorie, 1:1, a literelor din (1). de exemplu. (a -> x, b -> r, c -> o, ...)
Autorii descriu această abordare după cum urmează:
Descriem acum un atac care nu suferă de aceste dezavantaje [ale abordării analizei manuale a frecvenței]. Ca și înainte, asociați literele alfabetului englez cu $0, ..., 25$. Lăsa $p_i$, cu $0 <= p <= 1$, notează frecvența $ith$ literă în textul englez normal (adică 0,082 ca exemplu). ... [folosind aceste cifre] dă:
$(1)$ $\displaystyle \sum_{i=0}^{25} p_i^2 \aproximativ 0,065$
Notă: Unde $0.065$ este contextuală într-un corpus al unui anumit text englezesc (adică poate varia în funcție de sursă; de exemplu, cuvintele din dicționarul lui Webster.)
Acum, să spunem că ni se dă un text cifrat și lăsați $q_i$ denotă frecvența ia-a literă a alfabetului din textul cifrat împărțit la lungimea textului cifrat. Dacă cheia este k, atunci $p_i$ ar trebui să fie aproximativ egală cu $q_{i+k}$ pentru toți i pentru că ia-a litera este mapată la $\stânga(i+k\dreapta)th$ scrisoare. (folosim $i+k$ în loc de cele mai greoaie $\left[I+k \mod 26\right]$.) Astfel, dacă calculăm
$(2)$ $I_j := \displaystyle \sum_{i=0}^{25} p_i \cdot q_{i+j}$
pentru fiecare valoare a $j \în \left \{0, ..., 25\right\}$, atunci ne așteptăm să găsim asta $I_k \aproximativ 0,065$ (Unde k este cheia reală), în timp ce $I_j$ pentru $j \neq k$ va fi diferit de 0,065. Acest lucru duce la un atac de recuperare a cheilor care este ușor de automatizat: calculează $I_j$ pentru toți $j$, iar la ieșire valoarea $k$ pentru care $I_k$ este cel mai apropiat de 0,065.
Întrebarea mea se referă la abordarea generală a celei de-a doua însumări $(2)$ -- Nu înțeleg care este valoarea $j$ este pentru fiecare termen al însumării. Este $j$ menită să fie ial treilea termen al unei chei $k$? Astfel încât fiecare termen în $2$ ar fi calculat pentru fiecare valoarea posibilă a $j$?
Înțeleg generarea de frecvență, înțeleg ce se întâmplă conceptul de $(1)$ și că găsirea cea mai apropiată $q_i$ la $p_i$ s-ar apropia $p_i^2$ prin care actualul $k_i$ ar minimiza acest lucru -- găsind astfel cea mai potrivită cartografiere.
Cu toate acestea, se pare că aceasta este doar o abordare cu forță brută, având în vedere modul în care calculul final este comparat cu cel inițial $0.065$ valoare, de parcă s-ar fi luat în considerare maparea adecvată pentru fiecare literă.
Am pierdut ceva? În caz contrar, am impresia că doar sortam fiecare distribuție de frecvență după valoare, presupunând prezența unui număr egal de litere în textul cifrat cu cel al spațiului mesajului sursă (adică, nu există lacune posibile în distribuție).
