[RoLUG] paper sulla crittografia
Roccatello Eduard
rolug@lists.linux.it
Sat, 8 Feb 2003 18:13:20 +0100
Ciao a tutti
questo =E8 un branetto che ho scritto tempo fa sulla storia della=20
crittografia. =E8 ancora in fase di beta e pensavo che Diego (mi avevi=20
accennato il tuo interesse verso l'argomento) potrebbe completarlo per RS=
G.
Scusate il post lungo ma =E8 di pubblico interesse :-)
ciao
--=20
Roccatello Eduard
RoLUG member @ http://rovigo.linux.it
Webmaster @ http://www.pcimprover.it
-- INIZIO PAPER --
Generalizziamo sulla Crittografia - La storia di un'arte
<LE PRIME FORME DI CIFRAZIONE>
Le pi=F9 antiche notizie sicure sono probabilmente quelle sulla "scitala=20
lacedemonica" , data da Plutarco come in uso dai tempi di Licurgo (IX sec=
=20
a.C.) ma pi=F9 sicuramente usata ai tempi di Lisandro(verso il 400 a.C.) =
=2E =20
Consisteva in un bastone su cui si avvolgeva ad elica un nastro di cuoio;=
=20
sul nastro si scriveva per colonne parallele all'asse del bastone, e=20
lettera per lettera, il testo segreto. Tolto il nastro dal bastone il tes=
to=20
vi risultava trasposto in modo regolare ma sufficiente per evitare la=20
lettura senza un secondo bastone uguale al primo.=20
Tra il 360 e il 390 venne compilato da Enea il tattico, generale della le=
ga=20
arcadica, il primo trattato di cifre il cui XXI capitolo tratta appunto d=
i=20
messaggi segreti. In questo viene descritto un disco sulla zona esterna=20
del quale erano contenuti 24 fori,ciascuno corrispondente ad una lettera=20
dell'alfabeto. Un filo, partendo da un foro centrale, si avvolgeva passan=
do=20
per i fori delle successive lettere del testo: all'arrivo, riportate le=20
lettere sul disco, si svolgeva il filo segnando le lettere da esso=20
indicate: il testo si doveva poi leggere a rovescio. Le vocali spesso era=
no=20
sostituite da gruppi di puntini.=20
In questo stesso periodo vennero ideati codici cifrati indiani ed ebraici=
=20
utilizzati in particolar modo per celare nomi propri, innominabili o=20
sacrileghi. Numerosi testi e documenti greci antichi contengono tratti=20
cifrati, specialmente=20
nomi propri, ma si trovano anche interi scritti cifrati con sostituzione=20
semplice e con alfabeti generalmente a numero.=20
<IL CIFRARIO ATBASH>
Il libro di Geremia nella Bibbia usa un semplicissimo codice monoalfabeti=
co=20
per cifrare la parola Babele; la prima lettera dell'alfabeto ebraico=20
(Aleph) viene=20
cifrata con l'ultima (Taw), la seconda (Beth) viene cifrata con la penult=
ima=20
(Shin) e cos=EC via; da queste quattro lettere =E8 derivato il nome di At=
bash=20
(A con T, B con SH) per questo codice. Usando il moderno alfabeto=20
internazionale, l'Atbash pu=F2 essere riassunto con la seguente tabella d=
i=20
cifratura:=20
CHIARO a b c d e f g h i j k l m
CIFRATO Z Y X W V U T S R Q P O N
CHIARO n o p q r s t u v w x y z
CIFRATO M L K J I H G F E D C B A
Esempio: master --> NZHGVI
<LA SCACCHIERA DI POLIBIO>
Lo storico greco Polibio , nelle sue Storie descrive il pi=F9 antico esem=
pio=20
di codice poligrafico, che attribuisce ai suoi contemporanei Cleoxeno e=20
Democleito; l'idea =E8 quella di cifrare una lettera con una coppia di nu=
meri=20
compresi tra 1 e 5, in base ad una scacchiera 5x5. In tal modo il messagg=
io=20
pu=F2 essere trasmesso con due gruppi di cinque torce (p.es. 1,5 =3D una =
torcia=20
accesa a destra, cinque a sinistra). In effetti pi=F9 che di un codice=20
segreto, si tratta di un sistema di telecomunicazione, di fatto un=20
telegrafo ottico. Telegrafi a torce esistevano da molti secoli ed erano=20
stati destritti da Enea il tattico intorno al 350AC, ma erano basati su u=
n=20
limitato elenco di messaggi possibili; quello di Polibio si basa invece=20
sulla scomposizione del messaggio nelle singole lettere ed =E8 quindi in=20
grado di trasmettere qualsiasi messaggio.=20
# 1 2 3 4 5
1 a b c d e
2 f g h i j
3 kq l m n o
4 p r s t u
5 v w x y z
Nell'alfabeto greco ci sono 24 lettere ed avanza quindi un carattere che=20
Polibio proponeva di usare come segnale di sincronizzazione (inizio e fin=
e=20
trasmissione). Nell'esempio seguente si utilizzer=E0, al posto di quello=20
greco, l'alfabeto internazionale il quale ha viceversa il difetto di esse=
re=20
formato da 26 caratteri; cos=EC per poter costruire il quadrato necessari=
o=20
per la cifratura bisogner=E0 "fondere" due lettere rare ma non foneticame=
nte=20
differenti nella stessa casella, in questo caso la k e la q. In questo mo=
do=20
si otterr=E0 la tabella a lato.=20
Ogni lettera pu=F2 viene quindi rappresentata da due numeri, guardando la=
riga=20
e la colonna in cui la lettera si trova. Per esempio, a=3D11, r=3D42 e ci=
ao =3D=20
13241135
La scacchiera di Polibio ha alcune importanti caratteristiche, e cio=E9 l=
a=20
riduzione nel numero di caratteri utilizzati, la conversione in numeri e =
la=20
riduzione di un simbolo in due parti che sono utilizzabili separatamente.
<IL CIFRARIO DI CESARE>
Giulio Cesare usava per le sue corrispondenze riservate un codice di=20
sostituzione molto semplice, nel quale la lettera chiara veniva sostituit=
a=20
dalla lettera che la segue di tre posti=20
nell'alfabeto: la lettera A =E8 sostituita dalla D, la B dalla E e cos=EC=
via=20
fino alle ultime lettere che sono cifrate con le prime come nella tabella=
=20
che segue (che fa riferimento all'odierno alfabeto internazionale).=20
Chiaro 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
Cifrato D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
Prendendo come esempio la frase Auguri di buon compleanno si otterr=E0 il=
=20
seguente messaggio cifrato:=20
Chiaro=09=09auguridibuoncompleanno
Cifrato=09=09dxjxulglexrqfrpsohdqqr
Pi=F9 in generale si dice codice di Cesare un codice nel quale la lettera=
del=20
messaggio chiaro viene spostata di un numero fisso di posti, non=20
necessariamente tre; un esempio =E8 il codice che sempre secondo Svetonio=
era=20
usato da Augusto, dove la A era sostituita dalla B, la B dalla C e cos=EC=
=20
via. Poich=E9 l'alfabeto internazionale =E8 composto da 26 caratteri sono=
=20
possibili 26 codici di Cesare diversi dei quali uno (quello che comporta=20
uno spostamento di zero posizioni) dar=E0 un cifrato uguale al messaggio=20
chiaro iniziale.=20
<LA CRITTOGRAFIA NEL MEDIOEVO>
In questo periodo la crittografia viene usata solo per celare i nomi prop=
ri,=20
con la sostituzione di una lettera con quella successiva dell'alfabeto=20
regolare (A con B, B con C ecc.), ma limitando tale sistema alle vocali,=20
cifrate a volte con gruppi di punti,secondo il sistema di Enea il tattico=
=2E=20
Verso l'anno mille compaiono i primi alfabeti cifranti o monografici. Ess=
i=20
sono usati successivamente soprattutto nelle missioni diplomatiche tra i=20
vari staterelli europei, particolarmente da parte delle repubbliche=20
marinare e dalla corte papale di Roma e a partire dal XIV=B0 secolo. Si u=
sano=20
le cosiddette nomenclature, ossia liste di parole chiave del gergo=20
diplomatico abbreviate con un solo segno; ne troviamo molti esempi tra i=20
secoli XIV=B0 e XVIII=B0.
Un altro sistema =E8 quello usato dall'Arcivescovo di Napoli, Pietro di=20
Grazia, tra il 1363 e il 1365 in cui le vocali sono sostituite da semplic=
i=20
segni e le vocali scritte in chiaro funzionano da nulle; nelle ultime=20
lettere il procedimento =E8 applicato anche alle consonanti pi=F9 frequen=
ti=20
(l,r,s,m,n), che a volte erano cifrate anche con altre lettere alfabetich=
e.=20
Nel 1378, dopo lo scisma di Avignone, l'antipapa Clemente VII=B0 decise d=
i=20
unificare i sistemi di cifrature dell'Italia Settentrionale ed affid=F2 t=
ale=20
compito a Gabriele Lavinde; in Vaticano =E8 conservato un suo manuale del=
=20
1379. In esso ogni lettera =E8 cifrata con un segno di fantasia, in alcun=
i=20
casi vi sono delle nulle, in altri vi sono delle nomenclature; le vocali=20
sono trattate come le altre lettere, come in una cifra del 1395 di Mantov=
a.=20
Dagli inizi del XIV=B0 secolo, per depistare i tentativi di analisi stati=
stica=20
delle frequenze, si iniziano ad usare pi=F9 segni per cifrare una stessa=20
vocale come possiamo leggere in una cifra con pi=F9 di tre segni diversi =
per=20
ogni vocale, ma senza nulle e senza omofoni conservata sempre a Mantova d=
el=20
1401.
Tuttavia la prima cifra completa cio=E8 dotata di segni arbitrari per cia=
scuna=20
lettera, omofoni per le vocali , molte nulle e un nomenclatore, fu la =20
lettera di Michele Steno tra Roma e Venezia scritta nel 1411, di cui=20
abbiamo la chiave ed una decrittazione non fedele, che riportiamo qui a=20
fianco. Abbiamo altri esempi di cifre da Roma e da Firenze.
In seguito viene ampliato il nomenclatore e, a parte la diversit=E0 dei s=
egni=20
cifranti, tutte le cifre italiane dei tre secoli successivi seguirono=20
questo modello. Ne abbiamo esempi anche alla corte Francese del XVII=B0=20
secolo e perfino da parte dei nobili francesi in esilio nel 1793. Tale=20
sistema fu in uso anche nella telegrafia segreta attorno alla seconda met=
=E0=20
dell' '800. Eccezioni a questo canone si debbono al Cardinale Richelieu=20
attorno al 1640 per consiglio di Antonio Rossignol; si tratta di repertor=
i=20
invertiti con gruppi cifranti variabili, con due documenti per cifrare e=20
decifrare con omofoni per le singole lettere. Possiamo trovarne altri=20
esempi nelle corrispondenze tra Luigi XIV=B0 e il suo maresciallo alla fi=
ne=20
del '600 . La loro corrispondenza, con 11.125 gruppi cifranti diversi,=20
veniva considerata "sicura", ed infatti fu sempre cifrata con lo stesso=20
repertorio, mentre era gi=E0 stata violata nel 1689 da Wallis.
Dopo Luigi XIV=B0 la crittografia francese declin=F2 , tanto che sotto Na=
poleone=20
si usava un repertorio di soli 200 gruppi quasi privo di omofoni ed=20
applicato solo a parti dei dispacci.
Sembra che anche questa inferiorit=E0 nella cifratura contribu=EC al disa=
stro=20
russo del 1812-13 .
Altre cifre papali del XVI=B0 secolo utilizzano un sistema assai diverso,=
=20
ossia la cifratura con polifoni. La prima di queste cifre appare attorno =
al=20
1540; l'ultima nel 1585. Il nomenclatore di tali cifre =E8 costituito da=20
circa 300 voci, tutte cifrate con gruppi di tre cifre.
Un altro esempio di polifonia si trova nel sistema usato dal langravio=20
d'Assia nei primissimi anni del '600, nella quale spesso un gruppo di due=
=20
numeri indica o una lettera ed una parola vuota oppure una sillaba.=20
Tuttavia =E8 probabile che a distinguere le funzioni del gruppo venissero=
=20
collocati segni ausiliari, che poi il tempo ha cancellato. Secondo il=20
Meister, uno studioso di crittografia, il sistema polifonico era usato=20
spesso per ridurre la lunghezza del testo cifrato. Egli riporta anche=20
istruzioni per la composizione di simili cifre che sono all'avanguardia p=
er=20
i suoi tempi.
<IL CIFRARIO BIFIDO>
Il cifrario bifido di Delastelle =E8 un cifrario poligrafico basato sulla=
=20
matrice 5x5 usata per la prima volta nella scacchiera di Polibio e=20
utilizzata anche dal Playfair Cipher e dalla cifra campale germanica. Il=20
metodo =E8 dovuto a F=E9lix-Marie Delastelle uno tra i massimi crittologi=
=20
francesi del XIX secolo.=20
Il metodo si articola in tre passi: Il messaggio chiaro viene spezzato in=
=20
blocchi di cinque caratteri ciascuno; se l'ultimo blocco non =E8 esattame=
nte=20
di cinque, gli ultimi posti sono riempiti di X. Ogni lettera del blocco=20
viene cifrata con due cifre e cio=E8 con l'indice di riga e l'indice di=20
colonna, che vengono scritte in verticale sotto la lettera chiara. Le cif=
re=20
vengono ora riscritte in orizzontale riga dopo riga ottenendo un messaggi=
o=20
con un numero di cifre doppio dell'originale. A questo punto ogni coppia =
di=20
numeri viene ritrasformata in lettera sempre secondo la matrice. Ne risul=
ta=20
il messaggio cifrato da trasmettere. La matrice pu=F2 essere quella sempl=
ice=20
con le lettere dell'alfabeto ordinate (senza la W che pu=F2 cifrarsi con =
una=20
doppia V), oppure pu=F2 essere ottenuta con una parola chiave come nel=20
cifrario di Playfair. Il Delastelle propose anche un cifrario trifido, ch=
e=20
fa uso di una matrice tridimensionale 3x3x3, con 27 celle (ne avanza dunq=
ue=20
una che pu=F2 servire per lo spazio o per un carattere di controllo).=20
Esempio
1 2 3 4 5=20
1 C O M P U=20
2 T E R A B=20
3 D F G H I=20
4 J K L N Q=20
5 S V X Y Z=20
Come esempio si prenda la matrice ottenuta con la parola chiave COMPUTER,=
e=20
si=20
voglia cifrare il messaggio=20
URGE INVIO RINFORZI
che viene cos=EC scomposto e cifrato=20
URGEI-NVIOR-INFOR-ZIXXX
12323 45312 34312 53555
53325 42523 54223 55333
Il messaggio in cifre viene ora raggruppato a due a due e riconvertito in=
=20
lettere, ottenendo cos=EC il messaggio cifrato:=20
12 32 35 33 25 45 31 24 25 23 34 31 25 42 23 53 55 55 53 33
O F I G B Q D A B R H D B K R X Z Z X G
<CIFRATURA DES>
Il D.E.S. (Data Enncryption Standard) =E8 uno dei sistemi di cifratura pi=
=F9=20
famosi, largamente usati e sicuri del XX secolo.
Certificato per la sua affidabilit=E0 da NIST ogni 5 anni, fino al 1993, =
il=20
D.E.S. =E8 divenuto il sistema ufficiale di cifratura del Governo degli S=
tati=20
Uniti gi=E0 dal 1977.=20
Due anni prima, nel 1975, L'IBM, che per molti anni ha dominato=20
incontrastata il mondo dei computer, lo aveva introdotto per la prima vol=
ta=20
nel mondo informatico.=20
Il D.E.S. =E8 un cifrario misto che prevede 16 trasformazioni successive=20
(trasposizioni e sostituzioni).In pratica il testo chiaro viene suddiviso=
=20
in blocchi da 64 bit (equivalenti a 8 caratteri); ogni blocco =E8 sottopo=
sto=20
a una trasposizione data in base ad una chiave di 64 bit; si applica quin=
di=20
per 16 volte una funzione cifrante e alla fine la trasposizione inversa d=
i=20
quella iniziale. Viene definito un sistema simmetrico perch=E8 sia=20
l'emittente del messaggio, sia=20
il ricevente devono conoscere la stessa chiave segreta. In un ambiente di=
=20
poliutenza, si era parlato di una diffusione della chiave, fino a renderl=
a=20
di pubblico dominio; ma poi ci si =E8 chiesti se ne valesse davvero la pe=
na.=20
Se usato singolarmente, il D.E.S. pu=F2 essere un ottimo sistema per inse=
rire=20
files in un disco fisso, nella forma cifrata.=20
Il DES =E8 stato presentato come un cifrario assolutamente sicuro, ma su=20
questa presunta inattaccabilit=E0 si sono accese molte polemiche e certo=20
anche molte leggende. La critica pi=F9 fondata =E8 quella di Hellman dell=
a=20
Stanford University, che sostiene che la chiave =E8 troppo corta e che il=
=20
codice potrebbe essere forzato con una crittoanalisi di tipo esaustivo.
In effetti le chiavi possibili sono 256 (8 dei 64 bit sono usati come bit=
di=20
controllo e ne restano quindi solo 56 per la chiave), un numero molto=20
elevato ma non pi=F9 fuori della portata dei moderni supercomputer. E' st=
ata=20
avanzata perfino l'ipotesi che un nemico sufficientemente ricco e potente=
=20
potrebbe far costruire un computer capace di forzare il D.E.S. con una=20
brutale ricerca esaustiva dello spazio chiave (che richiederebbe 3,5 ore)=
=2E=20
Tale computer =E8 stato estimato per 1 milione di dollari; sono stati fat=
ti=20
tanti progetti ed altrettante polemiche, ma=20
il computer non =E8 ancora stato realizzato.=20
Gli studiosi Biham e Shamir idearono una nuova tecnica di forzatura detta=
=20
crittanalisi differenziale Tale tecnica richiederebbe la cifratura di 247=
=20
testi in chiaro scelti in base a specifici criteri, ed il confronto dei=20
risultati. Pi=F9 recentemente Matsui ha sviluppato un'altro tipo di attac=
co,=20
conosciuto come crittanalisi lineare. Secondo Matsui la chiave del D.E.S.=
=20
pu=F2 essere riconosciuta tramite l'analisi di 243 testi in chiaro noti. =
Il=20
suo primo esperimento ebbe successo, ma fu archiviato perch=E8 richiese 9=
735=20
stazioni di lavoro operanti per 50 giorni e 12 ore, un tempo troppo lungo=
,=20
considerando che la chiave del D.E.S. pu=F2 essere frequentemente cambiat=
a=20
proprio per impedire forzature.
Il DES, quindi =E8 da ritenersi ancora sicuro, ed ha il vantaggio della=20
velocit=E0 di cifratura che =E8 molto superiore a quella del suo principa=
le=20
rivale il codice RSA.
Inoltre, in risposta ai numerosi tentativi di forzatura =E8 stato elabora=
to il=20
D.E.S. Triplo, uno speciale tipo di D.E.S. a tre livelli di cifratura.
<IL CIFRARIO RSA>
RSA =E8 un cifrario a chiave pubblica che permette di cifrare un messaggi=
o=20
attraverso un procedimento che sfrutta le propriet=E0 dei numeri primi.
Si determini la prima chiave n, prodotto di p e q, due numeri primi molto=
=20
elevati, tali che la fattorizzazione di n sia difficile o perlomeno n=20
risulti una funzione unidirezionale rispetto al tempo d'uso del codice. N=
=20
viene infatti resa pubblica.=20
Esempio: n=3Dpq=3D5*7=3D35=20
Si calcoli dunque il valore della funzione di Eulero di n:=20
b=3Df(n)=3D(p-1)*(q-1) il cui valore rimane segreto; si scelga ancora un =
intero=20
d tale che d e f(n) siano primi tra loro, infine il suo inverso h=20
(nell'aritmetica finita di ordine f(n)), che =E8 il pi=F9 piccolo x per c=
ui=20
(dx-1)/f(n) =E9 un intero, il numero h =E9 la seconda chiave, e viene res=
o=20
pubblico, mentre d resta segreto e sar=E0 la chiave per decifrare.=20
Esempio:
b =3D f(35)=3D35(1-1/5)*(1-1/7)=3D24=20
d =3D 7 (primo con 24)=20
k =3D (7x - 1)/24=20
7x - 1 =3D k*24=20
7x =3D k*24 + 1=20
x =3D (k*24 + 1)/7=20
sostituisco a k 2 per far risultare x un numero intero ed ottengo x=3D7,=20
dunque h=3Dx=3D7 o anche calcolando l'inverso con una seconda funzione di=
=20
Eulero: (metodo impraticabile per numeri elevati)
b =3D f(35)=3D24=20
d =3D 7=20
k =3D f(24) =3D 24(1-1/2)(1-1/3) =3D 8=20
h =3D 7k-1 MOD 24 =3D 77 MOD 24 =3D 7=20
Per trasmettere il messaggio lo si traduce inizialmente in un vettore di=20
numeri (in precedenza ci si =E8 accordati riguardo alla modalit=E0 di=20
"traduzione"). Stabilita dunque la sequenza numerica m1, m2....mr si=20
trasmettono gli m uno alla volta. Il crittogramma corrispondente a m =E8=20
allora: c=3Dmh mod n.=20
Esempio: prendiamo m=3D3=20
c=3Dmh mod n=3D37 mod 35=3D2187 mod 35=3D17=20
La chiave di decifrazione =E8 costituita dall'intero d, segreto, che perm=
ette=20
di recuperare m grazie alla formula m =3D cd mod n; infatti, in modulo f(=
n),=20
d e h sono inversi, e quindi, in modulo n, c =3D mh, cd =3D m hd =3D m kf=
(n)+1 =3D=20
(m f(n))km e, per il teorema di Fermat-Eulero, =3D 1km =3D m.=20
Esempio:=20
m =3D cd mod n=3D177mod 35=3D3 (provare per credere!)=20
In sintesi: per cifrare un messaggio il trasmettitore deve prendere le=20
diverse cifre pubbliche del ricevente e costruire un messaggio cifrato,=20
quest'ultimo a sua volta utilizza la parte segreta del suo codice per=20
decifrarlo.=20
Il codice RSA viene considerato sicuro perch=E8, essendo la formula di=20
decifrazione basata su f(n) calcolabile solo se a conoscenza di p e q, no=
n=20
esiste un algoritmo efficiente per scomporre n nei suoi fattori primi p e=
=20
q, perlomeno in tempi accettabili.=20
Potrebbe sorgere il dubbio che esista un modo di calcolare f(n) senza=20
passare per p e q: questa ipotesi in effetti =E8 verificabile ma ha lo st=
esso=20
grado di complessit=E0 di fattorizzare n.