ABC della crittografia (tratto da qui)
La crittografia come modifica volontaria del testo esisteva già al tempodegli egiziani nel 1900 a.C. (tomba del faraone Knumotete II). La parola crittografia ha origine greca e significa "nascosto". Un'altraparola correlata è steganografia che significa scrittura nascosta. Unesempio legato all'antichità è di scrivere messaggi segreti non sull'argilla che ricopriva le tavolette, ma sulle stesse tavolette che venivano poi ricoperte d'argilla e sembravano non usate. Gli Spartani per crittare un messaggio segreto di tipo militare usavano2500 anni fa una striscia di papiro avvolta a spirale attorno ad un bastone(che costituirà la chiave di decodifica). Una volta scritto il messaggio inverticale sul papiro questo veniva consegnato al destinatario che, con un bastone dello stesso diametro poteva leggere il messaggio in chiaro. Questo metodo è di trasposizione perchè il messagggio è in chiaro ma l'ordine delle lettere è da scoprire.

Un altro metodo, questa volta di sostituzione, è stato inventato da GiulioCesare: la chiave è un numero n stabilito e si sostituisce ogni lettera del messaggio con l'ennesima seguente.
Esempio: pippo con chiave 3 diventa snssr.

Questo metodo è facilmente attaccabile perchè basta confrontare la frequenza delle lettere nella lingua italiana con la frequenza dei simboliusati nel messaggio cifrato. Bisogna inoltre considerare che le chiavipossibili sono solo 26, quindi al limite con un brute force si potrebbescovare la chiave. Data la bassa complessità [tanto bassa non è, numero dicombinazioni possibili: 26!=4*(10^26)] del metodo usato da Cesare è chiaroche non fosse infallibile, ma dati i risultati militari è stato efficace!Il metodo di Cesare ha ispirato un sistema usato ancora oggi, il ROT-13dove la chiave è appunto 13, quindi A->N, B->O, etc.

Il metodo che usavano gli ebrei è detto ATBASH. La sostituzione avvieneutilizzando questa tabella dove le lettere della seconda riga sono scrittein ordine decrescente:
a b c d e f g h i j k l m n o p q r s t u v w x y z
z y x w v u t s r q p o n m l k j i h g f e d c b a
Messaggio: Il Libro di Geremia. Testo Cifrato: Ro Oryil wr Tvivnrz

Lo storico greco Polibio inventò una tecnica di codifica legando le letterea una coppia di numeri che ne indicava la posizione in una tabella. Lacoppia di numeri era comunicata nella notte attraverso delle torce. Ecco un esempio di tabella: 
1 2 3 4  5
1 a b c d  e
2 f g h ij k
3 l m n o  p
4 q r s t  u
5 v w x y  z
pippo diventa (3,5) (2,4) (3,5) (3,5) (3,4)
Se la disposizione delle lettere nella tabella non seguono l'ordinealfabetico si capisce la difficoltà di trovare la chiave che in questo casoè la tabella.

L'imperatore romano Augusto usava invece un altro interessante metodo disostituzione usando come chiave un'altra parola o frase. La chiave e iltesto avevano un corrispettivo numerico, il testo cifrato risultava unasfilza di numeri ottenuti come somma fra testo e chiave.

Esempio (testo:spippolatori, chiave: decifralo):
a b c d e f g h i l  m  n  o  p  q  r  s  t  u  v  z
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
testo in chiaro   s  p  i  p  p  o  l  a  t  o  r  i
chiave                d  e  c  i  f  r  a  l  o  d  e  c
valore testo        17 14 9  14 14 13 10 1  18 13 16 9
valore chiave      4  5  3  9  6  16 1  10 13 4  5  3
valore cifrato      21 19 12 23 20 29 11 11 31 17 21 12
testo cifrato        z  u  n  b  v  h  m  m  m  s  z  n 


Se la somma (valore cifrato) eccede 21 si ricomincia dalla a; ciò equivale a fare una somma modulo 21.La decifrazione è una semplice sottrazione.La criptoanalisi di questo metodo non beneficia della frequenza delle lettere della lingua usata. Questo metodo può essere attaccato con un bruteforce utilizzando un dizionario di parole. Ovviamente ci si può difenderenon usando come chiave parole di senso compiuto, ma un insieme di letteregenerate in maniera casuale.

E, se ogni volta si cambia la chiave generandola casualmente, stiamo usandoun metodo chiamato One-Time Pad, che è difficile da superare senzaconoscere la chiave e generando in maniera "davvero" casuale la chiave (enon è facile perchè si può ottenere solo osservando fenomeni casualinaturali). Occorre notare che non bisogna usare questo metodo per duediversi messaggi con la stessa chiave perchè la differenza tra testocifrato e testo in chiaro è uguale e, in unione a un bruteforce, aiuta diparecchio la criptoanalisi di questo metodo. Infatti, trascurando ildiscorso della somma modulo 21 per semplificare il discorso risulta che:

1) Cifrato1 = Testo1 + Chiave
2) Cifrato2 = Testo2 + Chiave
Sottraendo si ha:Cifrato1 - Cifrato2 = Testo1 + Chiave - (Testo2 + Chiave) = Testo1 - Testo2

Altri metodi usatissimi per centinaia di anni prevedevano la sostituzione delle singole parole con altre che costituivano la chiave. Spesso siusavano più metodi insieme. Siamo nel quindicesimo secolo quando nasce la crittografia moderna con LeonBattista Alberti, artista rinascimentale poliedrico, amico di unfunzionario pontificio che gli chiese di inventare un metodo dicrittografia. L'idea partì dall'osservazione che un criptoanalista può essere aiutatodalle caratteristiche di una lingua come le frequenza delle lettere, lesillabe impossibili o più frequenti, le sequenze di lettere caratteristichecome le desinenze. Per rendere più difficile il lavoro del criptoanalista altro non c'era da fare se non cambiare durante il procedimento l'alfabetoda cui pescare la lettera cifrata: questo è il sistema polialfabetico.

 

Altro esempio di cifratura con il sistema del polialfabeto è quelloinventato da un tedesco contemporaneo dell'Alberti: Johannes Trithemius. Ilsistema fa uso di una tabella che si chiama tabula recta, formata da 26 righe (tante quante le lettere dell'alfabeto inglese) riportanti ognuna unalfabeto scalato di una posizione rispetto a quello precedente. La tabella si usa così: la prima lettera da cifrare rimane la stessa, la seconda sicifra con il secondo alfabeto, la terza lettera userà il terzo alfabeto ecosì via fino a ricominciare dal primo alfabeto dopo la ventiseiesimalettera. Per rendere difficile il lavoro dei criptoanalisti si può usare unalfabeto disordinato o, meglio ancora (è più facile da ricordare ecomunicare al destinatario del messaggio) una frase chiave.

L'uso della criptografia continua intensificandosi sempre di più emigliorandosi con il tempo fino ad avere importanza tale da cambiare ilcorso della storia durante le due guerre mondiali quando appaiono le primemacchine elettriche per cifrare i messaggi ma, soprattutto, per lacriptoanalisi.I tedeschi usarono per tutta la seconda guerra mondiale una macchiachiamata Enigma che avrebbe dovuto cifrare i messaggi in maniera sicura.Così non successe, perchè inglesi e polacchi unendo le loro forze furono ingrado di decifrare quasi tutti i messaggi intercettati.L'Enigma era una macchina elettromeccanica con contatti, lampadine, rotorie una tastiera. Ogni lettera veniva cifrata con un alfabeto diverso dandoluogo ad un numero sproposito di combinazioni che rendevano la decodificateoricamente impossibile per l'epoca. Ma ciò non fermò gli inglesi chetrassero grande beneficio dai messaggi decodificati. Per anni la regola generale è stata di creare algoritmi semplici e diimpiegare chiave molto lunghe per rendere difficile la vita alcriptoanalista. Oggi l'orientamento è opposto data la potenza di calcolo dicui si può disporre per fare un bruteforce, quindi si creano algoritmicomplicatissimi da decifrare in modo che anche se il nostro avversarioavesse parecchio materiale su cui condurre un'analisi, gli sarebbbepressocchè inutile.Oggi la crittografia serve per il commercio elettronico, l'autenticazione,la riservatezza delle informazioni, etc. Uno dei presupposti fondamentali èche si suppone che il criptoanalista di turno conosca in generale il nostrometodo di crittografia, questo perchè è davvero un disastro cambiare ognivolta metodo di crittografia ogni qual volta si ha il sospetto che qualcunosia riuscito a infrangerlo. Da questo presupposto segue che i metodi sibasano sulle chiavi di codifica e decodifica.Se la chiave è la stessa sia per la codifica che per la decodificaricadiamo nel caso delle crittografia classica: questi sono i metodi achiave simmetrica o segreta. Gli algoritmi a chiave asimmetrica o pubblica(che risalgono agli anni '70) utilizzano coppie di chiavi complementari.Una delle due chiavi è pubblica e conosciuta da tutti e serve per cifrare imessaggi, mentre l'altra è segreta e riservata al destinatario dei messaggiche la utilizzerà per decifrarli. Le chiavi vanno a coppie e quindi solouna chiave può decifrare il messaggio generato utilizzando la chiave a leicomplementare. In questo modo possiamo trasmettere tranquillamente lanostra chiave pubblica senza paura che venga intercettata. Spesso ci si orienta per metodi ibridi simmetrici-asimmetrici (come succedenel famoso PGP) perchè il solo metodo asimmetrico non è efficiente (èlento!) per grandi moli di dati e, se dovessimo inviare lo stesso messaggioa più persone, dovremmo cifrarlo ogni volta con la giusta chiave.PGP (Pretty Good Privacy) è un pacchetto freeware (http://www.pgpi.com) che realizza la crittografia a chiave pubblica; permette l'interscambio didocumenti elettronici realizzando segretezza, autenticità, integrità deidati su un canale insicuro. PGP è principalmente pensato per lo scambio didocumenti via Internet, ma può essere usato su un qualsiasi canaleinsicuro; è indubbiamente un prodotto di qualità, e non c'è da dubitaredell'integrità morale del suo autore (che potrebbe come sempre averlasciato delle trap-door), Philip Zimmerman. Egli infatti lo ha sviluppatocon il chiaro intento di permettere la privacy nell'interscambio di posta elettronica su Internet, con un approccio fortemente critico verso lapolitica di NSA e del Congresso Americano di progettare un monopolio deisistemi di crittografia; P. Zimmerman è stato sotto inchiesta per due annie mezzo, accusato di esportazione non autorizzata di materialecrittografico, ed è recente la notizia che le autorità federalistatunitensi hanno deciso di non perseguirlo penalmente.

Standard federale ancora oggi ufficiale (nella versione triplo-des) per gliUSA, è nato nel 1977 per implementazioni per lo più hardware comederivazione di Lucifer, un algoritmo di IBM nato nel '70, su insistenza delNational Bureau of Standard per difendere dati riservati ma non segretimilitari.

Il DES brevettato nel 1976 da IBM è royalty-free dal 1993.Il DES è un codice cifrato a blocchi (si dice che un codice è cifrato ablocchi quando si applica un codice cifrato a un bit, byte, parola o gruppidi parole alla volta). Il blocco che si usa per crittografare è di 64 bits(8 sottoblocchi da 8 bits). Dato che l'ultimo bit di ogni sottoblocco è dicontrollo, i bit utili sono 56.Per cifrare il testo si divide in blocchi da 64 bits che sono cifrati insuccessione. Se un messaggio non riempie i 64 bits si può completare indiversi modi: si possono aggiungere zeri, si possono aggiungere bit randomspecificando nell'ultimo quanti se ne aggiungono, etc.Il DES è molto usato in ambito commerciale perchè nonostante consti dinumerosi passaggi, questi sono tutti relativamenti semplici come XOR,sostituzioni e permutazioni.Occorre ricordare che il DES cambia solo la chiave; questo porta vantaggieconomici immediati, ma appena verrà scoperto il modo per forzarlo (senzabruteforce) occorrerà cambiare radicalmente tutto. Un altro difettofondamentale è lo spazio limitato delle chiavi pari a 2^56. Per ovviare alproblema si tenta di allungare le chiavi o di applicare più volte il DES(triplo-DES o TDES).Il progetto originale dell' IMB per il DES prevedeva una chiave più lungadei 56 bits usati di default. Probabilmente il progetto originario fuinfluenzato dall'NSA che impose all'IBM una chiave sicura, ma comunque allaportata dei loro potenti mezzi.

Nel gennaio 1998 la RSA Laboratories lanciò il "DES challenge II"coordinato e risolto da distributed.net in 39 days.Record presto battuto, nel 17 luglio 1998.L'EFF, Electronic Frontier Foundation's, costruì una macchina (DES Crackermachine) per distruggere il DES e ha scritto un libro (maggio 1998) dove èspiegato nei minimi dettagli come si è proceduto(http://www.eff.org/descracker).La macchina del costo di 210.000 $ (80.000 per lo sviluppo e il rimanenteper i materiali impiegati, il software è stato scritto da volontari in 2settimane) forza un DES-56 bits in meno di 3 giorni. Il progetto è statocompletato in 18 mesi.Hanno così dimostrato ai loro "stolti" (così li definiscono nel libro)governanti che il DES può essere forzato con una macchina dedicata. Qualchegiorno prima un funzionario del dipartimento di giustizia, Robert Litt, siaffannava a dire che non era possibile che l'FBI possesse macchine percraccare il DES.6 mesi dopo, 19/01/1999, Distributed.Net lavorando con un network mondialein Internet di 100.000 pc e con il DES Cracker della EFF, vinse l'RSA DataSecurity's DES Challenge III con il tempo record di 22 ore e 15 minuti! Dal novembre 1998 il DES non è più l'algoritmo standard federale; èsostituito dal triplo-DES finchè il nuovo AES non sarà pronto.IDEA, International Data Encryption Algorithm Creato nel 1991 da Xuejja Lai e James L. Massey, è, come il DES, codicecifrato a blocchi di 64 bits con chiave, però, di 128 bits. Anche IDEA usacalcoli semplici basati su operazioni (addizioni e moltiplicazioni)modulari, scambi e concatenamenti. Le sottochiavi usate nel procedimentosono tutte diversi e a 16 bits.Con questo tipo di crittogafia è stato risolto il problema della gestionedelle chiavi che non occorre più trasmettere al destinatario del messaggioper la decodifica. Il concetto di crittografia simmetrica è statointrodotto nel 1976 da Whitfield Diffie e Martin Hellman e si basa sulconcetto fondamentale che un messaggio codificato con una precisa chiavepubblica può essere decodificato SOLO dalla corrispondente chiave privatache è unica ed associata strettamente a quella pubblica; ciò si basa anchesu un dato matematico per cui, impiegando 1024 bits, per ottenere la(unica) chiave segreta da quella pubblica occorrerebbe una potenza dicalcolo pari a una rete di milioni di computer al lavoro per 1000 anni! Gli algoritmi a chiave pubblica, per la loro lentezza, sono usati spessoper cifrare la chiave di sessione con cui verrà codificato il messaggiousando la crittografia simmetrica.

Nel 1976 due crittologi americani, Diffie ed Hellmann, pubblicarono unfondamentale lavoro teorico nel quale, ipotizzando di poter disporre di uncifrario "asimmetrico", dimostravano la fattibilità di sistemicrittografici di nuovo tipo, adatti alla crittografia di massa mediante ilconcetto delle "chiavi pubbliche".Questo algoritmo è stato sotto brevetto fino al 29/4/97. Basa la suadifficoltà di decodifica sui problemi logaritmici. E' considerato sicuro con chiavi lunghe e generatori adatti.

Nato a due anni dal Diffie-Hellman (e brevettato il 29/9/1983 , scadenzanel 2000 in USA, libero nel resto del mondo), questo algoritmo è ancoraoggi molto usato (dato in licensa a 350 compagnie, conta un numero dimotori di codifica installati pari a circa 300 milioni). L'acronimoindividua le iniziali degli inventori, i tre ricercatori del MIT RonRivest, Adi Shamir e Leonard Adleman. La sua potenza si basa sull'estremadifficoltà di ricreare la chiave segreta da quella pubblica basandosi sufunzioni unidirezioni e quindi invertibili ma tali che la funzione direttasia banale, ma quella inversa sia estremamente difficoltosa. Ecco un esempio che dovrebbe chiarire e che è appunto l'idea su cui si basa l'RSA:è facilissimo trovare il prodotto di due numeri molto grandi, ma dato ilprodotto sarà estremamente difficoltoso trovarne i 2 fattori primi.Illustriamo i passaggi e l'esempio (che sarà fatto con numeri piccoli pernon complicare): 

1) Prendiamo due numeri primi p(=3) e q(=11) molto grandi ed n(=33) sia il loro prodotto. 

2) Prendiamo e(=3) che deve essere: minore di n, dispari e primo con(p-1)(q-1). [ (p-1)(q-1)=(3-1)(11-1)=2*10=20 ] 

3) Calcolare d(=7) in modo che: d*e=1 MODULO (p-1)(q-1). Significa che d*ediviso (divisione intera) (p-1)(q-1) dà come risultato 1. Infattid*e=3*7=21/20=1. 

4) Cifriamo il testo con c=(t^e) MODULO p*q.t, intero positivo, è il testo in chiaro. il risultato c è il testocifrato.  La chiave pubblica conterrà n ed e(esponente pubblico), quella privata n ed(esponente privato).  Se t sono i numeri da 0 ad 8, li cifreremo elevandoli alla terza e facendoil risultato modulo 33. 

La chiave per l'RSA è il modulo n. Più è grande la chiave, più sarà sicura(ma lenta) la cifratura. Con 1024 bits si è abbastanza (molto?) sicuri.Per craccare un RSA a 256 bits basta un potente home computer; andando a384 bits servirebbe un'organizzazione universitaria o una grande azienda;la crittografia a 512 bits può essere superata da agenzie statali. Solochiavi a 2048 bits possono ritenersi sicure per qualche anno a ogni livello(e chissà...).

Se volessimo usare un sistema ibrido si potrebbero usare RSA e DES. Con ilDES produciamo una chiave casuale (che cifreremo con l'RSA) che servirà percrittare il messaggio in maniera simmetrica. Spedisco poi il messaggio e lachiave DES cifrata con la chiave pubblica RSA al suo proprietario che conla sua chiave segreta decritterà prima la chiave che impiegherà perdecodificare il messaggio.Questo si fa perchè DES è da due (a livello software) a 4/5 ordini (alivello hardware) di grandezza più veloce dell'RSA.Nel marzo 1994, usando 1600 computer connessi a Internet, Atkins e altrifattorizzarono un numero di 129 cifre (426 bits) in 8 mesi di lavoro.Una studio del 1997 stimava in un milione di dollari il costo per forzareun RSA con chiave a 512 bits.Curiosità: il numero di numeri primi minori o uguali a n è asintotico an/ln n. Quindi il numero di numeri primi di lunghezza minore o uguale a 512bits è di circa 10^150, cioè più grande del numero degli atomidell'universo conosciuto. Questo la dice lunga sull'enorme disponibilità dichiavi diverse.

Notizia del marzo 1999 apparsa sul mensile Crypto-Gram: è statofattorizzato un RSA-140. Un nuovo record è stato stabilito da Herman Rielee il suo gruppo ad Amsterdam avendo fattorizzato un numero di 140 cifre(456 bit). Questo numero è stato una delle sfide dell'RSA, era il prodottodi due numeri primi molto grandi, proprio il tipo di numeri usati nelcriptosistema RSA.La mole di lavoro è stata stimata in 2000 anni-mips (mips=milioni diistruzioni al secondo, un anno-mips corrisponde alla potenza di calcolo diuna macchina che macina per un anno un milione di istruzioni al secondo. UnDEC 11/780 è una macchina mips. Un Pentium II di fascia alta è una macchinada 200 mips. Il supercomputer per simulare esplosioni nucleari installatoal Sandia National Laboratory è una macchina da 1.8 milioni di mips).Per l'impresa è stato usato un algoritmo detto "a setaccio di numeri", lostesso usato per fattorizzare un RSA-130 impiegherebbe 1000 mips-anni, perun RSA-150 1500 mips-anni. L'algoritmo non scala come ci si aspetterebbe,ma le tecniche di fattorizzazione diventano sempre più efficienti e velociperchè i computer diventano sempre più veloci, le macchine possono lavorarein rete, gli algoritmi migliorano continuamente di pari passo alle ricerchedi matematica.E' stato già avviato un progetto per fattorizzare un RSA-155 (512 bit) chesarà pronto per fine 1999.

Sono stati un pò più veloci della fine d'anno promessa e così è il 22agosto quando il solito Herman Riele annuncia l'impresa compiuta adAmsterdam su un numero da 155 cifre (512 bit) del tipo degli stessi usatiper l'RSA in quanto prodotto di due fattori primi da 78 cifre. 300 macchinetra workstation SGI e PC Pentium hanno lavorato alacremente per sette mesidurante la notte e i weekend. Usando il solito algoritmo a setaccio si sonoimpiegati 8000 anni-mips in 3.7 mesi per la fase cosiddetta "di setaccio" e224 ore-CPU e 3.2 Gigabytes di memoria per la seconda fase di riduzionematriciale su un Cray C916.Lo sforzo è stato 50 volte più facile che craccare il DES. Fattorizzare lechiavi usate per il commercio elettronico è sempre più facile e lo saràancor di più in futuro. Questa impresa deve mettere in allarme perchè lamaggior parte dei protocolli sicuri usati in Internet usano RSA a 512 bits.Grosse e medie società come Compaq e Microsoft usano ancora per i loromagazzini on-line l'RSA a 512 bit. Occorre inoltre riflettere sul fatto cheè probabile che qualche organizzazione in segreto già forzi abitualmente comunicazioni private e/o segrete. All'Eurocrypt '99, Adi Shamir (la S dell'acronimo RSA) presenta l'idea peruna macchina che potrebbe incrementare la velocità di fattorizzazioneattuale di 100-1000 volte. Chiamata TWINKLE (The Weizmann INstitute KeyLocating Engine), fattorizza chiavi di 512 bits.La macchina opera essenziamente in due passi: il primo fa da setaccio eattua una massiccia ricerca parallela di equazioni con una certa relazione.Appena un certo numero di relazioni è trovato, c'è una massiccia operazionematriciale per risolvere un'equazione lineare e produrre i fattori primi.Shamir ha teorizzato l'uso di tecniche elettro-ottiche per la prima fase disetaccio, idea peraltro non nuova perchè si rifà a quella di D.H. Lehmerche pensò nel 1930 di usare tecniche meccanico-ottiche. La macchina sembranon sia ancora stata costruita.  E' da notare che questa nuova macchina non risolve il problema di prestazione del secondo passaggio che riguardaoperazioni sulla matrici. La complessità del secondo passaggio esplodenella fattorizzazione di numeri enormi: con un numero a 1024 bit, peresempio, il secondo passaggio richiederebbe 10 terabytes di memoria (non dimemoria di immagazzinamento ma di vera memoria per il computer).Questa macchina non introduce nessun concetto matematico innovativo, masemplicemente esegue operazioni già conosciute più velocemente. L'idea è semplice: così come si entra in Hotmail e si spediscono e ricevonomessaggi, allo stesso modo lo si può fare, utilizzando però email criptatesenza dover scaricare nessun software.HushMail http://www.hushmail.com, basato su PGP e S/MIME-like, sfruttajava. Il mittente entra in HushMail e, attraverso un'applet java, puòmandare un'email criptata. Anche il destinatario deve avere un account suHushMail. Gli account possono essere anonimi. Gli algoritmi sono ElGamal a1024 bit e Blowfish. La chiave privata personale è immagazzinata sul serverdi HushMail e l'unica cosa che la protegge da accessi più o meno illegalial server è una passphrase. L'altra debolezza è costituita dall'applet javache non si può mai sapere se è quella corretta o un cavallo di Troia. Anchecertificando l'applet ci sarebbero dei problemi. L'ultimo problema è legatoalla collocazione fisica del server, che nonstante la compagnia che logestisce sia di Antigua, è collocato in Canada, che notoriamente è moltopiù suscettibile ad azioni legali.Nonostante tutto HushMail sembra una ragionevole implementazione dell'idea.Esistono altri servizi come http://www.ziplip.com, http://www.ynnmail.com, http://www.zixmail.com che sono molto meno sicuri fornendo una protezionedavvero blanda e facilmente attaccabile.Insomma, le email web-based criptate sono più sicure di una email noncriptata, ma meno sicure di una email criptata con PGP per molti motivi: iserver sono obiettivi di attacchi, le connessioni anche se SSL non sono immuni da spoofing.

 

ome Page