Sep 29 2004

Analisi delle frequenze


by tonycrypt

Nel caso dei cifrari monoalfabetici, ad ogni lettera se ne sostituisce un’altra secondo opportune regole. Se ad esempio sostituissimo la c con la x, la i con la y, poi a=r e o=b, potremmo scrivere la parola “ciao” come “xyrb”. Sembra trattarsi di un sistema di crittografia estremamente sicuro e, in primo luogo, piuttosto difficile da violare. In realtà è molto facile attaccarlo e violarlo: basta conoscere le proprietà statistiche del linguaggio con cui il testo è stato scritto. In questo modo non bisogna fare molta fatica per rivelare esattamente tutto il contenuto reale del crittogramma. Tonycrypt ha creato un programma che consente di effettuare automaticamente e rapidamente l’analisi delle frequenze di un testo. Si tratta di un programma gratuito disponibile nella sezione download o scaricabile cliccando qui. Per realizzare lo schema delle frequenze con cui si presentano le lettere della lingua italiana, abbiamo pensato di analizzare un testo sufficientemente lungo: la Convenzione di Ginevra relativa al trattamento dei prigionieri di guerra. Ecco dunque uno schema della ricorrenza delle lettere della lingua italiana:

Ecco i valori non approssimati (nel grafico dobbiamo tener conto anche dell’estetica, dunque riportiamo solo i valori interi) delle frequenze letterarie in lingua italiana: Lettera a: 9,651 %; Lettera b: 0,481 %; Lettera c: 3,469 %; Lettera d: 4,142 %; Lettera e: 12,791 %; Lettera f: 0,929 %; Lettera g: 1,9984 %; Lettera h: 0,517 %; Lettera i: 12,730 %; Lettera j: 1,584E-03 %; Lettera k: 7,921E-04 %; Lettera l: 5,809 %; Lettera m: 2,031 %; Lettera n: 7,690 %; Lettera o: 8,760 %; Lettera p: 3,018 %; Lettera q: 0,350 %; Lettera r: 8,140 %; Lettera s: 4,835 %; Lettera t: 7,290 %; Lettera u: 2,685 %; Lettera v: 1,283 %; Lettera w: 0 %; Lettera x: 0 %; Lettera y: 0 %; Lettera z: 1,387 %;

 

Supponiamo adesso di trovarci davanti ad un testo cifrato in cui si è deciso di sostituire la a con la x, la e con la y e così via. E supponiamo che il testo originale, in chiaro, fosse scritto in italiano. Sottoponiamo tale testo ad un’analisi delle frequenze. Troveremo che la x presenta una ricorrenza vicina al 9%, la y intorno al 12% e così via. Confrontando tali risultati con la soprastante tabella delle ricorrenze tipiche della lingua italiana, immediatamente ci si accorge della sostituzione effettuata.

Vediamo un esempio pratico di quanto appena esposto: supponiamo di trovarci davanti al seguente testo:

 

YHUVRODPHWDGHJOLDQQLXQILVLFRLQJOHVHGDYLGGHXWVFKGXUDQWHXQDFRQIHUHQCD VXOODILVLFDTXDQWLVWLFDHEEHOLGHDGLFUHDUHXQFDOFRODWRUHTXDQWLVWLFRTXHV WDHXQDLGHDULYROXCLRQDULDLQTXDQWRLFDOFRODWRULWUDGLCLRQDOLVLFRPSRUWDQ RVHFRQGROHOHJJLGHOODILVLFDFODVVLFDHTXLQGLFRQOHOLPLWDCLRQLFKHQRLWXWW LFRQRVFLDPRPDXQFDOFRODWRUHTXDQWLVWLFRDYUHEEHXQDSRWHQCDGLFDOFRORWHRU LFDPHQWHLQILQLWDWDOHGDSRWHULQYHUWLUHXQDOJRULWPRDIDWWRULCCDCLRQHFRPH OUVDSUHVVRFKHLVWDQWDQHDPHQWHUHQGHQGRTXLQGLDVVROXWDPHQWHLQXWLOLLVLVW HPLGLFULWWRJUDILDDOJRULWPLFDODVSLHJDCLRQHGHOIXQCLRQDPHQWRGLXQFDOFRO DWRUHTXDQWLVWLFRHFRVDDVVDLFRPSOHVVDHQRQHGHWWRFKHVLSRVVDUHDOLCCDUHLQ SUDWLFDDOPHQRLQWHPSLEUHYLDQFKHVHVLVRVSHWWDFKHJOLXVDQHDEELDQRJLUHDOL CCDWRHVHPSODULPDDQFKHVROROLSRWHVLGLXQDVXDIXWXUDUHDOLCCDCLRQHSRQHGHL VHULLQWHUURJDWLYLVXOOXWLOLCCRGHOODFULWWRJUDILDDOJRULWPLFDVSHFLDOPHQ WHSHUTXHLGRFXPHQWLFKHGHYRQRULPDQHUHULVHUYDWLSHUXQSHULRGRGLWHPSRDEED VWDQCDOXQJRTXLQGLDOODOXFHGLTXHVWRIDWWRVLLPSRQHXQUDGLFDOHFDPELDPHQWR GLVWUDWHJLDQHOODFULWWRJUDILDDWWXDOHQRQEDVWDSLXDXPHQWDUHODOXQJKHCCDG HOOHFKLDYLSHUUHQGHUHVLFXURXQGRFXPHQWRSHULSURVVLPLDQQLVHPSUHQHOOLSRW HVLGLDYYHQWRGHOFDOFRODWRUHTXDQWLVWLFRPDELVRJQDULFRUUHUHDTXDOFRVDGLF RPSOHWDPHQWHQXRYR

 

Effettuiamo un’analisi di frequenze di tale testo mediante il programma Frequency che ho sviluppato per Tonycrypt:

A questo punto non è necessaria grande intelligenza per capire cosa sta succedendo. Tutto l’andamento delle frequenze risulta traslato di 3 lettere. Chi ha cifrato il testo si è limitato ad effettuare un offset di 3 posti, utilizzando il codice di Cesare. La lettera d presenta una frequenza di 11 %, confrontabile, nella tabella della lingua italiana, a quella della a=9 %. Nel testo cifrato h=10 % mentre in lingua italiana e=12 %. Nel testo cifrato l=11 % mentre in lingua italiana i=12 %. E così via: tutto il testo originale è stato sottoposto ad un offset di 3 posti. A questo punto non ci resta che procedere inversamente. Decifriamo applicando il codice di Cesare al contrario, cioè con un offset di 26-3=23 posti (potete provare voi stessi dalla pagina dedicata al codice di Cesare). Risultato:

VERSOLAMETADEGLIANNIUNFISICOINGLESEDAVIDDEUTSCHDURANTEUNACONFERENZASULLAFIS ICAQUANTISTICAEBBELIDEADICREAREUNCALCOLATOREQUANTISTICOQUESTAEUNAIDEARIVOLU ZIONARIAINQUANTOICALCOLATORITRADIZIONALISICOMPORTANOSECONDOLELEGGIDELLAFISI CACLASSICAEQUINDICONLELIMITAZIONICHENOITUTTICONOSCIAMOMAUNCALCOLATOREQUANTI STICOAVREBBEUNAPOTENZADICALCOLOTEORICAMENTEINFINITATALEDAPOTERINVERTIREUNAL GORITMOAFATTORIZZAZIONECOMELRSAPRESSOCHEISTANTANEAMENTERENDENDOQUINDIASSOLU TAMENTEINUTILIISISTEMIDICRITTOGRAFIAALGORITMICALASPIEGAZIONEDELFUNZIONAMENT ODIUNCALCOLATOREQUANTISTICOECOSAASSAICOMPLESSAENONEDETTOCHESIPOSSAREALIZZAR EINPRATICAALMENOINTEMPIBREVIANCHESESISOSPETTACHEGLIUSANEABBIANOGIREALIZZATO ESEMPLARIMAANCHESOLOLIPOTESIDIUNASUAFUTURAREALIZZAZIONEPONEDEISERIINTERROGA TIVISULLUTILIZZODELLACRITTOGRAFIAALGORITMICASPECIALMENTEPERQUEIDOCUMENTICHE DEVONORIMANERERISERVATIPERUNPERIODODITEMPOABBASTANZALUNGOQUINDIALLALUCEDIQU ESTOFATTOSIIMPONEUNRADICALECAMBIAMENTODISTRATEGIANELLACRITTOGRAFIAATTUALENO NBASTAPIUAUMENTARELALUNGHEZZADELLECHIAVIPERRENDERESICUROUNDOCUMENTOPERIPROS SIMIANNISEMPRENELLIPOTESIDIAVVENTODELCALCOLATOREQUANTISTICOMABISOGNARICORRE REAQUALCOSADICOMPLETAMENTENUOVO

Naturalmente il sistema di analisi delle frequenze è applicabile al caso più generale in cui ad ogni lettera se ne sostituisce arbitrariamente un’altra, senza nessun tipo di regola. Il caso appena citato, dell’algoritmo di Cesare, è solo un esempio particolare di sostituzione monoalfabetica. Il programma Frequency è gratuitamente disponibile nell’area Download di Tonycrypt.


Sep 5 2004

Il codice “Navajo”


by tonycrypt

Tra la prima e la seconda guerra mondiale, gli USA pensarono di cifrare le loro comunicazioni semplicemente traducendole nel linguaggio degli indiani Choctaws. Pensarono insomma di sfruttare la complessità di tale linguaggio a difesa delle loro comunicazioni. Dopo l’inizio della guerra per gli USA, nel 1941, lo studio di questo genere di crittografia venne esteso e si sperimentarono i linguaggi di Commanches, Choctaws, Kiowas, Winnebagos, Seminoles, Navajos, Hopis e Cherokees. Successivamente però si optò per utilizzare esclusivamente il linguaggio Navajos.
Tra le varie tribù indiane vennero scelti proprio i Navajo perché la loro lingua appartiene a una famiglia linguistica priva di legami con qualsiasi idioma asiatico o europeo, inoltre si trattava dell’unica tribù che non fosse stata visitata da studiosi tedeschi. I “NAC”,Native American Codetalkers (parla-codice), ebbero un ruolo importantissimo nella guerra del Pacifico, contro i Giapponesi. Con il progredire della guerra nel Pacifico crebbe l’importanza dei “parla-codice” e la richiesta del loro aiuto aumentò rapidamente. Non tutti i marines però erano al corrente della presenza dei navajo e i “parla-codice” venivano a volte scambiati per soldati nemici, catturati dagli americani e rilasciati soltanto dopo l’intervento di soldati del loro stesso reparto. Per evitare questo genere di incidenti ad ogni navajo venne affiancato un marine che aveva il compito di proteggere non solo lui ma, soprattutto, il codice. Il “parla-codice” non doveva essere catturato dai giapponesi, perché avrebbe potuto rivelare la chiave del codice, e il marine aveva ricevuto l’ordine di ucciderlo prima che cadesse prigioniero.
Inizialmente si presentarono alcuni problemi dovuti al fatto che i navajo non avevano nel loro idioma i moderni termini tecnici e militari. Uno scoglio che venne facilmente superato inventando nomi di fantasia. Ad esempio si decise di usare nomi di uccelli per gli aerei e di pesci per le navi da guerra. In tal modo il cacciabombardiere era lo sparviero (Gini, in codice navajo), l’aereo spia era il gufo (Ne-as-jah).
Il loro codice è uno dei più sicuri e dei più semplici, uno dei pochi rimasto inviolato, ma il ruolo dei navajo nella seconda Guerra mondiale rimase un segreto militare fino al 1968, quando vennero finalmente autorizzati a rendere pubblico il loro contributo alla guerra. L’attività dei codetalkers viene ricordata nel film Windtalker, diretto dal regista cinese Yusen Wu.