M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 763

I l problema di proteggere l’informazione dasguardi indiscreti – in particolare, anche se

non solamente, quando l’informazione deveessere comunicata fra due partecipanti – si èpresentato millenni fa; dopo la seconda guerramondiale, con l’avvento dei calcolatori elettro-nici, la scienza della protezione dell’informazio-ne mediante crittografia ha avuto grande svi-luppo, dato che i nuovi strumenti consentonola realizzazione di sistemi complessi di codificache non sarebbero stati praticamente applica-bili con tecniche manuali.In questo articolo, dopo un cenno ai diversiaspetti della sicurezza (security) dell’informa-zione, si presenteranno brevemente le metodo-logie principali per la confidenzialità ottenutamediante codifica (e relativa decodifica), dalmomento che proprio la confidenzialità è allabase di tutte le soluzioni di sicurezza. Si intro-durranno le cifre di merito che portano a valuta-zioni delle diverse metodologie, e si indiche-ranno i metodi oggi più significativi miranti a in-frangere la sicurezza.

1. INTRODUZIONE

Si può definire la crittologia (cryptology) comelo studio della messa in sicurezza dell’informa-zione, vale a dire come l’analisi e il progetto, daun lato, di metodi per proteggere l’informazio-ne contro utilizzi indesiderabili e, in senso op-posto, di metodi per infrangere (o “rompere”)una tale protezione [1]. La crittografia (crypto-graphy) [2, 3] raggruppa pertanto i metodi de-stinati alla protezione dell’informazione, men-tre il suo contrario è la crittanalisi (cryptanaly-sis) [2, 3]: queste due discipline costituisconocomplessivamente la crittologia. Qui l’attenzio-ne sarà posta principalmente su metodologie ealgoritmi (o “primitive crittografiche”) in usonella crittografia contemporanea, la quale è ba-sata in modo essenziale sull’uso del calcolato-re elettronico; prima di entrare in argomento sifarà però un breve cenno storico.La proprietà essenziale che si desidera conferi-re all’informazione è la sicurezza (security). Inrealtà tale termine naturale è un po’ vago e va

DENTRO LA SCADENTRO LA SCATOLATOLARubrica a cura diFabio A. Schreiber

Con questo numero si conclude il ciclo di articoli “Dentro la scatola”. Scopo dichiarato dellarubrica era di presentare, in modo semplice e succinto, ma rigoroso, i concetti basilaridell’Informatica a coloro che, a vario titolo, di Informatica si occupano o con l’Informaticalavorano, pur senza avere una formazione tecnica specifica.Il tema scelto per il 2004 è stato: “Perché gli anglofoni lo chiamano “computer”, ovvero:introduzione alle aritmetiche digitali”, e ha affrontato il modo di codificare l’informazione digitale.Per il 2005 il filo conduttore della serie è stato: “Ma ce la farà veramente? Ovvero: introduzionealla complessità computazionale e alla indecidibilità”, con l’intento di guidare il lettoreattraverso gli argomenti fondanti dell’Informatica e le loro implicazioni pratiche e filosofiche. Laterza serie, negli anni 2006 e 2007, ha esplorato “Come parlano i calcolatori”, ovvero ilinguaggi di programmazione delle procedure e di interazione con i dati e i protocolli dicomunicazione per i sistemi distribuiti. Non a caso la serie si conclude con un contributo sullacrittografia, argomento di grande attualità e di fondamentale importanza in un mondo semprepiù informatizzato, nel quale la sicurezza e la privatezza dell’informazione diventano una delleprincipali preoccupazioni a livello tecnico e sociale per lo sviluppo di nuove applicazioni.Colgo l’occasione per ringraziare sentitamente tutti i colleghi che hanno compiuto il non piccolosforzo di condensare in testi sintetici e divulgativi i loro contributi e il Consiglio Direttivo dell’AICAper aver intrapreso un’iniziativa, che ci auguriamo possa avere un seguito nel futuro.

Crittografia elettronicaLuca Breveglieri, Mariagiovanna Sami

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 7

1

0

0

0

1

64

precisato caso per caso specificando qualiaspetti di sicurezza si vogliono considerare.L’esempio forse più immediato e intuitivo è da-to dalla proprietà di confidenzialità (confiden-tiality), vale a dire la protezione dell’informazio-ne, sia essa un messaggio da trasmettere o undato memorizzato, contro l’interpretazione e diconseguenza lo sfruttamento da parte di un’en-tità, essere umano o macchina, non esplicita-mente autorizzata a svolgere tale funzione.L’operazione fondamentale per ottenere la con-fidenzialità è la cifratura (encryption), mediantela quale si altera e confonde la forma codificatadell’informazione al fine di renderla non inter-pretabile; l’operazione inversa, mediante laquale si ricostruisce la forma originale, si chia-ma decifrazione (decryption)1. L’informazionein forma non cifrata e cifrata si chiama, rispetti-vamente, testo in chiaro (cleartext o plaintext) etesto cifrato (ciphertext). Le operazioni di cifra-tura e decifrazione si effettuano mediante algo-ritmi (o primitive) crittografici, e spesso all’in-sieme dei due algoritmi – di cifratura e di deci-frazione – si dà nome di crittosistema (crypto-system o ciphersystem).La confidenzialità è tuttavia solo la prima e piùsemplice proprietà di sicurezza dell’informazio-ne; ce ne sono altre più raffinate e specifiche, chesi vedranno più avanti. È pur vero che la proprietàdi confidenzialità funziona in molti casi come ba-se per ottenere le altre proprietà più sofisticate.La crittografia contemporanea è interamentebasata sull’uso del calcolatore elettronico. Tra-lasciando dunque interpretazioni cinematogra-fiche fantasiose, non è neppure lontanamentepensabile che la cifratura di un blocco di infor-mazione, e meno che mai la decifrazione, svol-ta mediante un algoritmo crittografico contem-poraneo di uso commerciale (come DES o AES),sia effettuabile da parte di un essere umano amente o al massimo solo con l’ausilio di carta,matita e poco altro. Non è tuttavia sempre statocosì, e la crittografia per secoli fu applicata ma-nualmente o tramite qualche ausilio meccanicopiuttosto semplice.Ecco una brevissima sintesi storica [6], relativa asistemi crittografici miranti a garantire la funzio-ne di confidenzialità per messaggi da spedire. I

primi algoritmi di cifratura di cui si abbia notizia,risalenti all’antichità, furono di tipo alfabetico aschema di sostituzione prefissato: i caratteri deltesto in chiaro venivano sostituiti secondo unoschema fisso e naturalmente invertibile. Assainoto è l’algoritmo di Cesare, dove la lettera “A”viene sostituita da “C”, “B” da “D”, …, “X” da“Z”, “Y” da “A” e infine “Z” da “B”. Naturalmen-te tale schema è invertibile, per potere decifrare.Lo schema di sostituzione prefissato costituisceun esempio elementare di chiave segreta o pri-vata di cifratura (secret o private key). Nell’algo-ritmo di Cesare la chiave è data da due elementi:la specifica del tipo di schema e il numero di pas-si. In generale la chiave sarà costituita da tutti glielementi e i parametri caratterizzanti lo schema.La proprietà di confidenzialità è garantita dalpossesso esclusivo della chiave, che deve esse-re nota solo a chi o che cosa sia autorizzato a in-terpretare il contenuto del messaggio. La chiavesegreta può restare in uso per sempre, oppure(per maggior sicurezza) la si può mantenere perun certo intervallo di tempo o per un dato nume-ro di operazioni di cifratura, cambiandola poicon frequenza proporzionata al livello di confi-denzialità che si desidera conseguire.Lo scopo della crittanalisi consiste nel trovarela chiave segreta in uso, ovvero lo schema disostituzione, avendo a disposizione come ma-teriale di lavoro qualche esempio di testo cifra-to e possibilmente anche qualche esempio ditesto in chiaro corrispondente. Ingenuamente,si può sempre tentare la crittanalisi medianteforza bruta (brute force) provando tutte le chia-vi segrete. Ne segue che per garantire un buonlivello di protezione alla cifratura occorre ga-rantire che l’insieme di chiavi ammissibili, ospazio delle chiavi (key space), sia adeguata-mente ampio, sì da rendere impossibile o alme-no non conveniente il ricorso a forza bruta.Gli algoritmi crittografici a schema di sostituzio-ne prefissato, alfabetici o più realisticamente ablocchi di caratteri, sono però vulnerabili all’a-nalisi delle frequenze dei caratteri (frequencyanalysis). Il principio secondo cui analizzandole frequenze relative dei caratteri (o dei blocchidi caratteri) nel testo cifrato e confrontandolecon quelle caratteristiche del testo in chiaro,possedendone un esemplare oppure facendoqualche ipotesi ragionevole su come esso siafatto, si possa ritrovare lo schema di sostituzio-ne (la chiave segreta), risale al tardo Medioevo

1 Qualcuno purtoppo dice e scrive crittare e decrittare,crittazione e decrittazione.

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 7

1

65

0

0

0

1

e al Rinascimento; tale scoperta è accreditata aLeon Battista Alberti [6]. Ovviamente per pote-re adottare la frequency analysis occorre cono-scere la lingua naturale in cui il testo è statoscritto ed è necessario che il testo cifrato siasufficientemente lungo da consentire l’applica-zione di sia pur semplici ragionamenti statistici.Un esempio letterario molto celebre è presen-tato in una delle avventure di Sherlock Holmes,“I pupazzi ballerini”, dove a ogni lettera è sosti-tuito un disegno schematico.A fronte dello sviluppo delle tecniche di analisidelle frequenze vennero sviluppati metodi com-binati di cifratura mediante sostituzione e per-mutazione di elementi di informazione (caratterio blocchi), secondo schemi guidati da una chia-ve segreta. Infatti, applicando sostituzioni diffe-renziate si riduce l’efficacia dell’analisi delle fre-quenze, e intercalando permutazioni (cioè cam-biamenti di ordine) diverse si tendono a cancel-lare le regolarità ripetitive eventualmente pre-senti nel testo in chiaro. I crittosistemi di tale ti-po in uso in età moderna furono numerosi, spes-so incentrati su un repertorio prefissato ma ab-bastanza ampio di tabelle di sostituzione e per-mutazione, di uso manuale, da scegliere casoper caso come specificato dalla chiave segreta[6]. In séguito l’operazione di cifratura manualevenne accelerata mediante l’uso di sistemi elet-tromeccanici, quando tale tecnologia fu inventa-ta, senza però cambiare il principio del metodo.Il culmine di tale tendenza fu raggiunto dalla no-tissima macchina elettromeccanica Enigma pro-gettata poco prima e posta in uso durante la se-conda guerra mondiale [6]. Essa sostituisce e per-muta i caratteri del testo secondo schemi com-plicati selezionati dalla chiave segreta. Di fatto l’a-nalisi delle frequenze di testi cifrati da Enigma ri-sultava molto complessa con i metodi dell’epoca,e fattibile solo in casi speciali e fortunati.Con la fine della guerra e la contemporanea in-venzione del calcolatore elettronico inizia la sto-ria della crittografia contemporanea, dove cifra-tura e decifrazione sono realizzate da strumentielettronici. Il primo crittosistema, ideato secon-do criteri che aspiravano a essere sistematici, do-cumentato (almeno parzialmente) e realizzatosia in software sia in hardware, che risultò di rile-vante successo commerciale, fu DES (Data En-cryption Standard), progettato da IBM nel 1973-74 [2] e reso standard da NIST nel 1976. Con essoinizia ufficialmente la storia della crittografia

contemporanea. Oggi DES è superato da altresoluzioni più moderne, come AES (Advanced En-cryption Standard - 2002) [2] [5], ma con esso sipuò concludere la nostra breve rassegna storica.Nel resto dell’articolo si illustreranno sintetica-mente i concetti e i metodi fondamentali dellacrittografia contemporanea basata su calcolato-re elettronico: prima se ne presenteranno con-cetti e modelli di base (sezione 2), poi si descri-veranno gli algoritmi commerciali attualmentein uso, a chiave segreta (sezione 3) e pubblica(sezione 4). Le conclusioni tratteggeranno alcu-ne tendenze di ricerca attuali (sezione 5).

2. CONCETTI E MODELLI DI BASE

La crittografia può garantire diverse proprietà disicurezza dell’informazione. Come già detto, laproprietà fondamentale (e più semplice) è laconfidenzialità, in pratica la restrizione della fa-coltà di interpretazione e sfruttamento dell’infor-mazione solo a entità specifiche, proprietà che siottiene tramite la funzione di cifratura. La pro-prietà di autenticazione (authentication) consi-ste nella garanzia che l’informazione sia prodot-ta o riconosciuta da un’entità identificabile, e siottiene mediante la funzione di firma digitale (di-gital signature), che si vedrà più avanti. La firmadigitale può anche garantire la proprietà di inte-grità (integrity) dell’informazione, che consistenella garanzia che l’informazione non sia altera-ta, accidentalmente o intenzionalmente, e anchela proprietà di non-ripudio (non-repudiation),che consiste nella garanzia che l’informazioneprodotta o riconosciuta da un’entità non possaessere da questa misconosciuta in séguito. Infi-ne la proprietà di autorizzazione (authorization)consiste nella garanzia che l’informazione (o ilservizio) sia accessibile solo da parte di un’en-tità o di un gruppo esplicitamente autorizzato atale funzione, e si ottiene tramite combinazionidelle funzioni citate in precedenza.Ogni crittosistema è dotato di uno o più elemen-ti di informazione che costituiscono la chiave(key), da cui dipende il livello di sicurezza del si-stema. In definitiva la chiave è sempre rappre-sentabile come stringa di bit. I crittosistemiodierni sono progettati in conformità al cosid-detto princìpio di Kerchoff (formulato già nel1883): tutti gli aspetti del crittosistema sonopubblici (struttura, algoritmi e parametri), tran-ne la chiave. L’idea è che un crittosistema con

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 7

1

0

0

0

1

66

troppi aspetti segreti finisca per essere meno si-curo di uno con pochi. Infatti, poiché la crittogra-fia oggi è diffusissima e primitive crittografichesi trovano realizzate in numerosi dispositivi elet-tronici, fissi e mobili, prodotti e distribuiti in mi-lioni di esemplari, sarebbe del tutto vano illuder-si di riuscire a celare, anche solo per breve tem-po, gli aspetti strutturali e algoritmici o la confi-gurazione di un crittosistema di successo com-merciale. Senza contare che rendendo pubblicoil crittosistema numerosi ricercatori possonostudiarlo ed eventualmente scoprire per tempodifetti sfuggiti a una prima analisi. Il massimoche si riesca a fare, e d’altra parte il minimo indi-spensabile, è tenere segreta la chiave o parte diessa. Pertanto il principio di Kerchoff rappresen-ta un requisito formale del tutto coerente conl’uso concreto che oggi si fa della crittografia.La figura 1 mostra il modello generale di crittosi-stema, nel caso l’informazione da rendere confi-denziale sia un messaggio. Le entità A e B sono ipartecipanti (partner) del sistema. Ecco (1) il mo-dello espresso in simboli:

c = ek (m) e m = dk (c)(1)

dove m, c, k ∈ M, C, K

Gli elementi m, c e k sono il testo in chiaro (mes-saggio originale), il testo cifrato (messaggio ci-frato) e la chiave, rispettivamente, e apparten-gono agli insiemi o spazi M, C e K del testo inchiaro, cifrato e della chiave, rispettivamente.Di norma il testo in chiaro e quello cifrato (m e c)

hanno dimensione (in bit) prefissata. I simboliek e dk sono gli algoritmi di cifratura e decifra-zione, rispettivamente. Li si suole formulare co-me funzioni a un solo argomento parametrizza-te dalla chiave k, e naturalmente si ha l’identità∀ m, k dk [ek (m)] = m.L’entità O rappresenta l’avversario (adversary),che si procura materiale vario, generalmenteesemplari di testo cifrato ed eventualmente an-che in chiaro, su cui lavorare per effettuare lacrittanalisi e trovare la chiave k o almeno partedel testo in chiaro m.La chiave k può essere la medesima per entram-bi i partecipanti o differenziarsi tra i due. Nel pri-mo caso si parla di crittosistema a chiave segreta(o privata) o simmetrico, nel secondo a chiavepubblica o asimmetrico. Nelle sezioni 3 e 4 se nevedranno due esempi caratteristici. Per ora siprosegue supponendo unica la chiave, ma quan-to si dirà vale anche per chiavi differenziate.È necessario garantire che la chiave k sia notasolo ai partecipanti A e B, e che sia valida, cioèeffettivamente legata alla coppia AB e non adaltri partecipanti. Insomma, si deve stabilire unlegame sicuro tra chiave e identità del parteci-pante. È questo il problema di distribuzionedella chiave (key distribution). La soluzione ge-nerale è data dal certificato (certificate): c’è unaterza parte fidata (trusted third party), intrinse-camente sicura, chiamata autorità di certifica-zione o CA (Certification Authority), che rilasciala chiave dietro richiesta del partecipante. LaCA mantiene una base di dati dove registra ipartecipanti afferenti e le rispettive chiavi. Ipartecipanti possono iscriversi alla CA, essereregistrati e associati a una chiave, oppure riti-rarsi (o essere espulsi) rilasciando la chiave.Per esempio, il partecipante A richiede alla CA lachiave di A per la coppia AB, e la CA risponde in-viando ad A un certificato (messaggio) contenen-te la chiave in questione; il partecipante B proce-de in modo simile. Naturalmente la CA deve es-sere un’entità la cui sicurezza è presupposta e in-discussa; spesso è un’autorità pubblica o legal-mente riconosciuta. Il certificato deve essere au-tentico e integro, e pertanto molto spesso vieneprotetto con firma digitale, come spiegato prima.Si è riconosciuto che per ottenere la proprietàdi confidenzialità (e di riflesso anche le altre) lafunzione di cifratura deve possedere le due ca-ratteristiche seguenti: confusione e diffusione.Confondere significa modificare le frequenze

FIGURA 1Modello generale di crittosistema (canale di comunicazione cifrato)

C.A

Autoritàdi certificazione

Richiestadi chiave

Richiestadi chiave

Certificatocontenente k

Partecipante Partecipante

Avversario

c = ek (m)m = dk (c)A

O

B

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 7

1

67

0

0

0

1

relative dei simboli (caratteri, numeri, bit oblocchi) nel testo in chiaro in dipendenza dallachiave, sì vanificare la crittanalisi mediante fre-quency analysis. Diffondere significa permuta-re i simboli (come prima) secondo la chiave, sìda cancellare le regolarità ripetitive eventual-mente presenti nel testo in chiaro.Numerosissimi algoritmi di cifratura, in partico-lare di tipo simmetrico, sono costruiti secondouna “ricetta” comune: suddividono il testo inblocchi di simboli, hanno struttura iterativa e ilcorpo del ciclo applica al blocco una successio-ne, fissa o dipendente dall’iterazione, di trasfor-mazioni costituite da sostituzioni e permutazio-ni di simboli pilotate dalla chiave, rispettivamen-te per confondere e diffondere il testo; in ingres-so c’è il testo in chiaro e in uscita quello cifrato. Ilcrittosistema AES esposto nella sezione 3 ne èun’esemplificazione per così dire “da manuale”.Nella crittografia odierna le trasformazioni ap-plicate al testo sono quasi sempre di tipo mate-matico ben definito e sono generalmente for-mulate nell’ambito della teoria dei campi (o de-gli anelli) finiti, una branca dell’algebra. Il ri-quadro dà una sintesi di tale teoria.

Ci sono motivazioni precise che hanno contri-buito a orientare la crittografia verso la mate-matica dei campi finiti. Ecco le due principali:❑ L’insieme di elementi è finito ed essi sonopertanto rappresentabili in modo esatto.❑ Le operazioni di addizione e moltiplicazionedel campo modellano a grandi linee le trasfor-mazioni di sostituzione e permutazione, e han-no dunque effetto confusivo e diffusivo.Un esempio di campo è dato dagli interi con ad-

dizione e moltiplicazione modulo un numero pri-mo p > 1. Per esempio, 2 + 4 mod 5 = resto di 6 ri-spetto a 5 = 1, e 2 × 4 mod 5 = resto di 8 rispettoa 5 = 3. Esistono anche campi finiti i cui elementisono polinomi. Insomma, il campo finito offre unambiente matematico sistematico e ricco di pro-prietà utili dove costruire primitive crittografiche.Si può quantificare il livello di sicurezza (di confi-denzialità ecc.) del crittosistema in tre categoriegenerali. Il parametro caratterizzante la dimen-sione del crittosistema è il numero di bit n ≥ 1 ne-cessari per codificare in binario la chiave (lun-ghezza di chiave). Ecco le tre categorie di livello:❑ assoluto: non esiste in linea di principio nes-sun metodo di crittanalisi;❑ computazionale: si dimostra matematica-mente che l’algoritmo di crittanalisi computa-zionalmente più efficiente è NP-completo;❑ pratico: l’algoritmo di crittanalisi computazio-nalmente più efficiente noto al momento ha co-sto economicamente non conveniente rispettoal valore dell’informazione in chiaro ottenibile.Il livello di sicurezza assoluto è conseguibileunicamente usando la chiave una volta sola percifrare e sostituendola continuamente. Datoche non c’è riuso della chiave, la crittanalisi èimpossibile in via teorica. I crittosistemi di que-sto tipo sono detti usa-e-getta (one-pad).È molto arduo costruire un crittosistema colloca-to a livello di sicurezza computazionale, a causadella difficoltà matematica di dare una dimostra-zione rigorosa di NP-completezza. Gli esempi no-ti di crittosistemi la cui analisi è stata dimostrataessere NP-completa sono pochi [1] e nessuno èdi interesse commerciale rilevante. Di fatto quasitutti i crittosistemi in uso commerciale si colloca-no a livello di sicurezza soltanto pratico.Si conclude con un breve accenno alla crittanali-si. In generale essa ha lo scopo di trovare il testoin chiaro, partendo dal testo cifrato, senza cono-scere la chiave. In pratica comunque mira quasisempre a trovare proprio la chiave, perché unavolta questa è nota qualunque esemplare di te-sto cifrato è decifrabile. Il metodo ingenuo e uni-versale di crittanalisi è la forza bruta; la fre-quency analysis è un metodo meno generico mapure universale2, più o meno efficace. I metodidi crittanalisi lineare e differenziale sono moltogenerali e consistono nell’approssimare il critto-sistema con funzioni lineari; sono tuttavia meto-

Campo Finito [4]. Il campo finito o di Galois1 (fini-te o Galois field) costituisce la struttura algebri-ca dove sono ambientati tutti o quasi i crittosi-stemi attuali. Un campo finito F è un insieme fini-to di elementi a, b, c, …, dotato di due operazionibinarie tra elementi: addizione a + b e moltiplica-zione a × b, associative, commutative, dotate dielemento neutro e opposto o reciproco. Il campofinito può ridursi a un anello finito, cui manca so-lo la possibilità di definire il reciproco di ciascunelemento. Alcuni crittosistemi (come per esem-pio RSA) sono ambientati in anelli finiti.

1 Dal nome dello scopritore, il matematico franceseEvariste Galois.

2 Tranne che nel caso usa-e-getta.

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 7

1

0

0

0

1

68

di complessi, che richiedono parecchi aggiusta-menti ad hoc dipendenti dal crittosistema inesame [7, 8]. Oltre a questi metodi in un certosenso universali, la crittanalisi si divide in fami-glie particolari di cosiddetti attacchi (attack) mi-rati sul crittosistema specifico, i quali ne sfrutta-no le debolezze matematiche o i difetti di imple-mentazione (in SW o in HW); gli attacchi sarannoripresi brevemente nelle conclusioni (sezione 5).

3. CRITTOSISTEMI SIMMETRICI

Un crittosistema mirato a garantire la confiden-zialità dell’informazione è detto simmetrico o achiave segreta se i due partecipanti A e B usanola stessa chiave ks, detta appunto segreta (oprivata); si rivedano la figura 2 e il modello (1).

La chiave segreta ksAB è dunque univoca per lacoppia di partecipanti AB. Essa va calcolata ini-zialmente e deve essere conosciuta solo daparte di A e B; in generale può essere distribui-ta mediante certificazione.Il primo crittosistema simmetrico standard dilarga diffusione fu DES: ha testo in chiaro, ci-frato e chiave segreta tutti di lunghezza 64bit. Una variante, Triple-DES o 3DES, consistenell’applicare in cascata tre cifrature DES condue chiavi differenti ed è talvolta ancora oggiutilizzata.Il crittosistema standard oggi di maggiore dif-fusione è Rijndael (Rijemen-Daemen 2000) oAES (Advanced Encryption Standard) [5]. Lostandard AES è stato definito nel 2002 a sé-guito di un processo di selezione internazio-nale gestito dal NIST e durato due anni. Alla fi-ne è stato scelto tra sei crittosistemi concor-renti e ha rapidamente rimpiazzato DES in nu-merose applicazioni. Ha la caratteristica im-portante di essere calcolabile in modo effi-ciente sia in software sia in hardware. Infattilavora essenzialmente su byte, ed è efficienteanche se programmato su processori da 8 bit,di potenza limitata. È del tutto pubblico, mol-to studiato e ben documentato, e pertantosoddisfa al principio di Kerchoff. Per una bre-ve presentazione del crittosistema [2, 5] si ve-da il riquadro.Il crittosistema AES fornisce gli algoritmi di ci-fratura e decifrazione, e garantisce la proprietà

FIGURA 2Modello di crittosistema asimmetrico (canale cifrato con chiave pubblica)

Crittosistema AES (o Rijndael) [2, 5]Ambiente matematico: campo finito F2

8 dei polinomi di grado max 8 (byte), a coeff. binari (0 e 1).

Testo in chiaro, cifrato e chiave segreta: stringhe m, c e k, ciascuna da 128 bit

Algoritmo di schedulazione della chiave (va effettuato una-tantum): pre-elabora la chiave segreta k (usando varie trasformazio-ni molto simili a quelle dell’algoritmo di crifatura), derivando da essa 10 chiavi di round kr (1 ≤ r ≤ 10 ), ciascuna delle quali è unastringa di 128 bit.

Algoritmo di cifratura: suddividi il testo in chiaro m in 16 byte mu,v, organizzati a matrice quadrata di tipo 4 × 4 (1 ≤ u, v ≤ 4), ed eseguiil ciclo seguente (ciascuna iterazione si chiama “round”)

for r from 1 to 10 do

applica a ciascun byte mu,v la trasformazione (non-lineare) SubByte

applica a ciascuna riga mu della matrice la trasformazione (lineare) ShiftRow

applica a ciascuna colonna mv della matrice la trasformazione (lineare) MixColumn

applica all’intero testo m la trasformazione (lineare) AddRoundKey(kr)

end for

il testo finale elaborato dai 10 round del ciclo costituisce il testo cifrato c; ciascuna delle quattro trasformazioni (o funzioni) interne alround SubByte, ShiftRow, MixColumn e AddRoundKey è biunivoca; per i particolari si veda per esempio, [5].

Algoritmo di decifrazione: il ciclo di cifratura, eseguito in ordine retroverso e con le trasformazioni SubByte, ShifRow, MixColumn eAddRoundKey sostituite dalle rispettive inverse InvSubByte, InvShiftRow, InvMixColumn, InvAddRoundKey(k10 – r) (chiavi di roundusate in ordine inverso).

m = dksB (c)c = ekpB (c)

Partecipante

C.A.

BA

Certificatocontenente kpB

Autoritàdi certificazione

Richiestadella chiave pubblicadel parteciapante B Fornitura iniziale della chiave

segreta ksB del partecipante B

Partecipante

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 7

1

69

0

0

0

1

di confidenzialià dell’informazione. Si colloca alivello di sicurezza pratico (non computaziona-le), poiché non è formalmente dimostrato chela crittanalisi di AES sia infattibile in tempo me-no che esponenziale rispetto al numero di bitdella chiave, benché di fatto oggi per infrange-re AES non si sappia fare di meglio che esplo-rare l’intero spazio delle chiavi mediante forzabruta, ciò che implica circa 2128 ≈ 1043 tentativi.Allo stato attuale la crittanalisi di AES è del tut-to infattibile con i supercalcolatori più potentidisponibili.Ci sono altri crittosistemi simmetrici concorrentidi AES, più o meno diffusi. Tra quelli più noti sitrovano RC4 e RC5, molto semplici e talvolta usa-ti per esempio in reti di sensori con potenza dicalcolo limitatissima e alcuni altri, ma non molti.

4. CRITTOSISTEMI ASIMMETRICI

Una comunità di membri che usano a coppie uncrittosistema simmetrico deve gestire in gene-rale tante chiavi segrete quante sono le coppiepossibili, e la distribuzione delle chiavi risultapertanto onerosa e rischiosa. Un crittosistemamirante a garantire la confidenzialità dell’infor-mazione è detto asimmetrico o a chiave pubbli-ca se i due partecipanti A e B usano chiavi diffe-renti; si veda la figura 1. Ecco (2) il modelloespresso in simboli (questo particolarizza ilmodello (1)):

c = eks (m) e m = dkp (c)(2)

dove m, c, ks, kp ∈ M, C, Ks, Kp

Ciascun partecipante (qui A e B) è dotato di duechiavi: segreta ks e pubblica kp. Per cifrare ilmessaggio per B, A si serve della chiave pubbli-ca di B, kpB; per decifrare B si serve della pro-pria chiave segreta, ksB; lo stesso accade se Bdeve cifrare per A. La chiave pubblica di ciascunpartecipante può essere resa nota a tutti gli al-tri partecipanti, mentre quella segreta è cono-sciuta solo dal partecipante cui si riferisce. Nesegue che la comunità di partecipanti usa mol-te meno chiavi che nel caso simmetrico.Tuttavia, dato che deve valere l’identità ∀m ∈M : dkp [eks (m)] = m, le due chiavi di una cop-pia segreta-pubblica di un partecipante sonolegate funzionalmente. Affinché il crittosiste-ma sia sicuro deve essere computazionalmen-te infattibile trovare la chiave segreta cono-

scendo quella pubblica (poiché allora tutti po-trebbero farlo e le chiavi segrete cesserebberodi essere tali!). Il proprietario della chiave se-greta conosce dall’inizio la sua chiave e nonha mai bisogno di calcolarla.Non esiste, o quanto meno oggi non si cono-sce, nessuna “ricetta” per definire crittosiste-mi asimmetrici. Di conseguenza ci sono atutt’oggi ben pochi esempi di crittosistemiasimmetrici ed essi differiscono profonda-mente uno dall’altro.Il crittosistema asimmetrico principale e piùdiffuso è RSA (Rivest-Shamir-Adelman), idea-to nel 1977. Per una breve presentazione delcrittosistema [2, 3] si veda il riquadro. Essen-zialmente, RSA fornisce gli algoritmi di cifratu-ra e decifrazione, e garantisce la proprietà diconfidenzialià dell’informazione. Fornisceperò anche l’algoritmo di firma digitale e ga-rantisce le proprietà di autenticazione, inte-grità e non-ripudio. Si basa su un teorema diteoria dei numeri (si veda il riquadro); qui ci si

Crittosistema RSA [2]Ambiente matematico: anello Zn degli interi modulo n > 1, dove l’interon = pq (composto) è il prodotto di due fattori primi differenti p, q > 1rappresentabili con circa il medesimo numero di bit.

Testo in chiaro e cifrato: numeri interi m e c (0 ≤ m, c < n).

Fase di preparazione (va effettuata una-tantum per impostare il sistema):

• calcola la funzione di Eulero ϕ(n) = (p – 1) (q – 1), dove 1 < ϕ(n) < n

• scegli (a caso) un intero a > 1 [e < ϕ (n)] coprimo con ϕ (n), cioè taleche il massimo comun divisore di a e ϕ (n) sia 1, ovvero tale chem.c.d.[a, ϕ (n)] = 1

• calcola l’intero b > 1 reciproco di a modulo ϕ (n), cioè tale che ab = 1mod ϕ (n) (b esiste ed è unico se e solo se m.c.d.[a, ϕ (n)] = 1, e si cal-cola facilmente)

• chiave pubblica e segreta: la coppia e la terna di interi kp = (a, n) e ks =(b, p, q)

Algoritmo di cifratura: calcola l’esponenziale c = ma mod n

Algoritmo di decifrazione: calcola l’esponenziale m = cb mod n

Dimostrazione di correttezza del sistema: dato l’intero a e la condizionem.c.d.[a, ϕ(n)] = 1, vale il teorema fondamentale seguente:

∀m si ha [(ma)b] = [(mb)a] = m mod n

pertanto l’algoritmo di decifrazione è effettivamente l’inverso di quello dicifratura (e viceversa).

Valutazione del livello di sicurezza del sistema: per trovare l’intero b(segreto), indispensabile per decifrare, partendo dall’intero a (pubblico),bisogna conoscere ϕ(n) = (p – 1) (q – 1), e dunque i fattori primi p e q di n;però scomporre l’intero n in fattori primi ha complessità temporale espo-nenziale con l’algoritmo migliore noto (Crivello di Eratostene, con svaria-te ottimizzazioni); se ne conclude che il crittosistema RSA si colloca a li-vello di sicurezza pratico (non computazionale).

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 7

1

0

0

0

1

70

limita a enunciarlo, si vedano [2] o [3] per la di-mostrazione.RSA non si colloca a livello di sicurezza com-putazionale perché non esiste una dimostra-zione formale che il problema della scomposi-zione in fattori primi sia NP-completo. In prati-ca oggi è possibile scomporre in fattori priminumeri rappresentabili con 600-700 bit, trami-te mezzi di supercalcolo molto potenti. La lun-ghezza di chiave standard per RSA (il numerodi bit per codificare n in binario) è fissata a1024 bit, più che adeguata per applicazioni ci-vili, e quella per applicazioni militari a 2048bit, ben oltre ogni immaginabile possibilità didecifrazione.Il crittosistema RSA è assai versatile e realizzafacilmente la funzione di firma digitale (digitalsignature) per autenticazione, integrità e non-ri-pudio. Ecco come procedere a questo scopo.❑ Il partecipante A firma il testo m cifrandolomediante la funzione eksA e la chiave segretaksA (non quella pubblica), cioè con l’esponenteb (non a): la coppia (m, c) costituisce il testo fir-mato (m è il testo e c la firma).❑ Il partecipante B verifica la firma prendendo iltesto firmato (m, c), decifrando la firma c me-diante la funzione dkpA e la chiave pubblica kpA(non quella privata), cioè con l’esponente a(non b), e confrontando il risultato della deci-frazione con m (cioè con il testo in chiaro):

• se coincidono la firma c è valida e il testo mè autentico e integro;• altrimenti non è valida e il testo m è da rifiu-tare in quanto falso o alterato.

Dato che la chiave segreta è in possesso solodel partecipante che firma il testo, questo nonpuò misconoscere la firma in un secondo tem-po. Pertanto anche la proprietà di non-ripudiodel testo firmato è garantita. La funzione di fir-ma digitale è ampiamente utilizzata per auten-ticare il certificato e garantirne l’integrità. L’in-sieme di regole standard che definiscono strut-tura, metodo di firma e modo di gestione delcertificato è noto come infrastruttura di chiavepubblica o PKI (Public Key Infrastructure), ed èun componente molto importante dei sistemicrittografici applicativi.

5. CONCLUSIONI

Vale la pena di concludere illustrando le ten-denze di ricerca attuali, di stampo scientifico

cioè mirate a scoperte nuove, e ingegneristicocioè mirate alla realizzazione. L’ideazione emessa punto di crittosistemi originali, simme-trici e asimmetrici, è un campo di ricercascientifica sempre aperto, dove si mira a indi-viduare nuovi crittosistemi con costo compu-tazionale decrescente e livello di sicurezzacrescente, senza però ampliare troppo lo spa-zio delle chiavi, anzi se possibile restringen-dolo. In questa direzione i crittosistemi asim-metrici basati su curve ellittiche [10, 11] sonodi grande interesse perché ammettono nume-rose varianti algoritmiche, non tutte ancoraidentificate e ben studiate. La crittografiaquantistica (quantum cryptography) è un ap-proccio promettente [12] ma richiede a tutt’og-gi sforzi di ricerca notevoli sia metodologicisia tecnologici. C’è infine una mole consisten-te di ricerca ingegneristica mirante a ottimiz-zare l’implementazione di crittosistemi già no-ti e in uso corrente, per evidenti ragioni di tipoapplicativo e industriale.In senso opposto, anche la crittanalisi è og-getto di ricerca, realizzativa e metodologica. Ilprimo approccio fa leva sull’aumento costantedella potenza dei mezzi di supercalcolo. Inve-ce i metodi universali di crittanalisi sonoestremamente difficili da ottimizzare e i pro-gressi in tale campo sono graduali e avvengo-no con una certa lentezza. Ben più fiorente,anzi oggi dominante, è lo studio dei metodi diattacco, cioè dei metodi di crittanalisi miratisul crittosistema specifico. Qui l’interessemaggiore è diretto verso il campo vastissimodei cosiddetti attacchi collaterali (side-chan-nel attack), che sfruttano le debolezze dell’im-plementazione del crittosistema. In ambito in-dustriale gli attacchi collaterali sono ben piùtemuti di ogni altra minaccia alla sicurezza didispositivi elettronici.Lo scopo dell’attacco collaterale è di racco-gliere informazione rilasciata in modo inav-vertito o imprevisto, sotto forma di grandezzamisurabile o quantità valutabile, da parte deldispositivo crittografico, e di elaborarla suc-cessivamente per effettuare la crittanalisi e indefinitiva trovare il testo in chiaro o meglioancora la chiave. In ordine di tempo sono sta-te scoperte tre famiglie principali di attacco ditipo collaterale, con numerose ramificazionipiù o meno fini:1. l’attacco in tempo (timing attack);

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 7

1

71

0

0

0

1

2. l’attacco in potenza (power attack);3. l’attacco basato su induzione di guasto (fault-injection-based attack).Nei primi due casi si misura una grandezza fi-sica: tempo di calcolo e potenza elettrica con-sumata o elettromagnetica irradiata, rispetti-vamente; nel terzo si valuta una quantità, os-sia il risultato errato emesso in caso di guastoindotto intenzionalmente. Capita spesso chequeste grandezze e quantità siano correlate inmodo determinabile al testo in chiaro o allachiave, e che pertanto rilevandole e poi ana-lizzandole con metodi di carattere essenzial-mente statistico, si possano inferire l’uno ol’altra. Per misurare con precisione il tempo dicalcolo basta rilevare il segnale di clock delcircuito, per la potenza consumata o irradiatabasta ricorrere a oscilloscopio o altro stru-mento similare, e per indurre intenzionalmen-te un guasto (temporaneo) ben localizzato esincronizzato si può ricorrere per esempio allatecnologia laser (light-based fault attack).Infine, giova ricordare che naturalmente sisviluppano in continuazione applicazioni do-tate di funzionalità di sicurezza basata anchesu crittografia, sia nel campo delle comunica-zioni sia in quello delle basi di dati, e non dirado un’applicazione sicura tiene conto di en-trambi gli aspetti.

Bibliografia

[1] Simmons G.: Contemporary Cryptology. IEEEPress, 1992.

[2] Menezes A., van Oorschot P.C., Vanstone S.: Hand-book of Applied Cryptography. CRC Press, 1997.

[3] Stinson D.: Cryptography: Theory and Practice.CRC Press, 1995.

[4] Lidl R., Niederreiter H.: Finite Fields. 2a edizio-ne, Cambridge, University Press, 1997.

[5] FIPS 197: Announcing the Avdanced EncryptionStandard (AES). http://csrc.nist.gov/publica-tions/fips/fips197/fips-197.pdf, 2001.

[6] Singh S.: Codici e Segreti. Rizzoli, Milano, 1999.

[7] Matsui M., Linear Cryptanalysis Method for the DESCipher. Advances in Cryptology - EUROCRYPT ’93,LCNS n. 765, Springer-Verlag, 1994, p. 386-397.

[8] Biham E., Shamir A.: Differential Cryptanalysisof DES-like Cryptosystems. Journal of Crypto-logy, Vol. 4, n. 1, 1991, p. 3-72.

[9] Thomas S.: SSL and TLS Essentials securing theWeb. New York, John Wiley & Son, 2000.

[10] Menezes A.: Elliptic Curve Public Key Cryptosy-stems. Kluwer Academic Publishers, 1993.

[11] Boneh D., Franklin M.: Identity Based Encryp-tion from the Weil Pairing (IBE). SIAM Journal ofComputing, Vol. 32, n. 3, 2003, p. 586-615.

[12] Bennett C., Bessette F., Brassard G., Salvail L.,Smolin J.: Experimental Quantum Cryptography.Journal of Cryptology, Vol. 5, n.1, 1992, p. 3-28.

MARIAGIOVANNA SAMI è professore ordinario di prima fascia presso il Politecnico di Milano, nell’area dei Sistemidi Elaborazione. Dal 1987 al 1990 è stata Direttore del Dipartimento di Elettronica del Politecnico di Milano. ÈDirettore Scientifico del Master of Science in Embedded Systems Design presso l’Università della Svizzera Ita-liana a Lugano.La sua attività di ricerca riguarda le architetture hardware dei sistemi digitali, con particolare riguardo alle meto-dologie di progetto di sistemi dedicati caratterizzati da elevate prestazioni, robustezza e basso consumo di po-tenza. È autrice o co-autrice di oltre duecento lavori scientifici in sede internazionale ed ha ricevuto alcuni premiper la sua attività di ricerca. È membro dell’Accademia Italiana delle Scienze (detta dei Quaranta).E-mail: sami@elet.polimi.it

LUCA BREVEGLIERI, Nato nel 1962. Laureato in ingegneria elettronica nel 1986 e dottore di ricerca in ingegneria elet-tronica dell’informazione e dei sistemi nel 1991. Dal 1991 al 1998 è stato collaboratore tecnico (per la rete tele-matica) presso il Politecnico di Milano. Dal 1998 è professore associato di ingegneria informatica presso il Poli-tecnico di Milano. Ha svolto attività di ricerca nel campo della progettazione digitale e delle architetture di ela-borazione, in particolare per aritmetica del calcolatore ed elaborazione di segnale e immagine. I suoi intessi diricerca attuali comprendono algoritmi e dispositivi per crittografia, e aspetti della teoria dei linguaggi formali.E-mail: luca.breveglieri@polimi.it

Come detto nel riquadro iniziale, questa è l’ultima puntata di “Dentro la scatola”.Mondo Digitale coglie l’occasione per porgere un caldo “Grazie!”al prof. Fabio Schreiber che haproposto la rubrica, ideato la sequenza degli articoli e seguito passo passo l’implementazione.