Test di primalità per la crittografia a chiave pubblica

  2
1.2    SIGNIFICATO DELLA CRITTOGRAFIA 
 
La crittografia, un tempo era strumento dei soli agenti segreti, mentre oggi � un mezzo che 
coinvolge praticamente tutti, in quanto � necessaria a garantire la nostra privacy nell�era della 
comunicazione digitale. 
Infatti, la comunicazione � diventata oggi un perno fondamentale della nostra societ�, e di 
conseguenza � diventata necessaria anche la riservatezza di ogni informazione trasmessa. 
Ma non basta: la crittografia ha anche il ruolo della certificazione, ovvero che ogni messaggio 
provenga realmente da colui che se ne dichiara autore e che giunga a destinazione senza che 
abbia subito modifiche o intercettazioni (intenzionali e non) durante il suo transito. 
 
Esempi di queste modifiche, o meglio, intrusioni, possono andare dalla clonazione dei telefoni 
cellulari all�intercettazione di informazioni trasmesse via Internet. 
Ricorrendo alla firma digitale, � possibile autenticare e certificare i documenti in formato 
elettronico equiparandoli cos� allo stesso valore legale di quelli cartacei. 
Da questo si pu� dedurre che la crittografia ha invertito le sue funzioni: un tempo era 
strumento di segretezza usato da pochi, mentre oggi � diventata veicolo di certezza e di diritto 
per tutti i cittadini. 
Dopo questi brevi cenni si pu� cominciare a dire come funziona la crittografia. 
 
          
1.2.1    Crittologia e crittanalisi 
 
 
Nel linguaggio comune, si intende per crittografia la scienza che studia i vari metodi per 
dissimulare un messaggio. 
Questa terminologia � tuttavia incompleta in quanto devono essere esaminate le varie branche. 
Il vero termine che si attribuisce alla scienza delle scritture segrete � crittologia. 
La crittologia si suddivide in due rami contrapposti: la crittografia, che studia i sistemi di 
protezione dei messaggi, e la crittanalisi che studia invece le tecniche per violare il segreto 
dei messaggi cifrati. 
Il termine crittologia � caduto in disuso; si usa quindi, in senso generale, il termine  
crittografia.
  3
Gli addetti ai lavori in ambito crittografico saranno perci� i crittologi (escogitano nuove 
tecniche di cifratura) e i crittanalisti (ricercano invece le tecniche per rendere leggibili le 
informazioni cifrate). 
Crittologi e crittanalisti sono in eterna concorrenza: l�operato di questi ultimi pu� tuttavia 
essere a fin di bene qualora i primi operassero a fin di male! 
Ai crittanalisti di oggi, che operano per lo pi� su Internet, � talvolta dato l�appellativo di 
hacker. 
 
 
1.2.2    Cifratura e decifrazione 
 
 
Dopo avere identificato i personaggi principali che operano in ambito crittografico, � il 
momento di dare una terminologia ben precisa alle operazioni fondamentali. 
Il messaggio il cui contenuto deve essere protetto prende il nome di testo in chiaro; 
il messaggio, trasformato e reso illeggibile dalle tecniche crittografiche prende invece il nome 
di testo cifrato. 
 
 
L�applicazione che trasforma il testo da chiaro a cifrato prende il nome di cifratura, mentre la 
trasformazione crittografica � detta cifrario. 
I cifrari usati in ambito informatico sono invece noti come algoritmi di cifratura. 
L�operazione inversa della cifratura � detta decifrazione qualora essa venga svolta dal 
legittimo destinatario del messaggio tramite l�opportuna trasformazione che converte in chiaro 
il testo cifrato; se tale operazione � invece compiuta da utenti che non conoscono la 
trasformazione inversa, anzich� di decifrazione si parler� invece di decrittazione, la quale 
tenta di violare il segreto dei messaggi con tecniche crittanalitiche. 
 
 
In generale la decifrazione � un�operazione breve e lecita, mentre la decrittazione � pi� 
laboriosa e, di solito, illecita. 
  4
Il segreto di un�operazione di cifratura consiste quasi sempre nella conoscenza di una certa 
quantit� di informazione che viene detta chiave. 
Di solito si utilizza la stessa chiave per cifrare e decifrare; ci sono per� sistemi dove la chiave 
di cifratura � diversa da quella di decifrazione: sono detti asimmetrici. 
 
Il crittologo Kerckhoffs enunci� un principio secondo il quale l�affidabilit� di un sistema 
crittografico non � basata sulla segretezza del metodo di cifratura, ma sulla segretezza della 
chiave: l�algoritmo di cifratura deve essere considerato pubblico o quantomeno noto ai 
possibili avversari. 
Un�ultima osservazione: scopo della crittografia non � nascondere i messaggi, ma renderli 
illeggibili agli utenti non autorizzati. 
La scienza che invece tratta della trasmissione nascosta dei messaggi � detta steganografia. 
  5
1.3    ORIGINI DELLA CRITTOGRAFIA 
 
La crittografia pu� considerarsi antica quanto l�uomo; infatti l�esigenza di restringere la 
comunicazione a determinati individui era diffusa anche nelle civilt� preistoriche. 
Sono stati per� l�avvento della politica e del commercio a rendere sempre pi� esigenti le 
comunicazioni segrete: in pace e in guerra era necessario che i messaggi inviati e non ricevuti 
fossero illeggibili ai nemici. 
 
Nasce cos� la Criptografia, dal greco scrittura nascosta. 
I Romani e i Greci gi� adottavano sistemi di cifratura; nel caso dei Greci � da ricordare il 
sistema di Plutarco, che usa un bastoncino (scytala) con una striscia di pergamena avvolta a 
spirale con scritto il messaggio: poteva leggere quest�ultimo solo chi possedeva una scytala di 
ugual diametro. 
 
Nel caso dei Romani � invece da ricordare il Cifrario di Cesare, capostipite di una serie di 
cifrari a sostituzione. 
Durante il Medioevo la crittografia fiorisce in Oriente, mentre col Rinascimento si afferma 
anche in Occidente, grazie al rifiorire del commercio internazionale e delle vicende politiche e 
diplomatiche tra i vari stati. 
 
Cos� come si cercava di proteggere i propri messaggi, si tentava anche la decrittazione di 
quelli provenienti da potenze concorrenti: nel XV secolo, Cicco Simonetta, addetto alla 
Cancelleria degli Sforza, scrive il primo trattato di decrittazione; anche Venezia disponeva di 
un servizio cifra che proteggeva le proprie comunicazioni e tentava di decrittare quelle 
provenienti da altre potenze. 
 
Da Roma, grazie a Leon Battista Alberti, si ha il primo vero trattato di crittografia scritto in 
Occidente, il De Cifris, di sole 25 pagine, che tratta la soluzione dei cifrari a sostituzione 
monoalfabetica e descrive quelli a sostituzione polialfabetica, che resteranno indecrittati per 
altri tre secoli. 
  6
Durante il XVII e il XVIII secolo quasi tutti i governi europei possedevano un ufficio cifra 
con lo scopo di decrittare i messaggi intercettati alle altre potenze (alleate e non). 
Nascono cos� le camere nere, centrali di spionaggio che intercettavano e leggevano 
segretamente la posta in partenza e in arrivo presso le ambasciate estere di ogni nazione; tra 
queste centrali spiccava quella di Vienna. 
 
 
Chiudono poi nel secolo successivo, dove, l�invenzione del telegrafo rivoluziona l�uso dei            
sistemi crittografici; anche la natura dei messaggi era mutata con una prevalenza di messaggi 
militari brevi rispetto invece a quelli diplomatici, pi� lunghi; per i primi erano richiesti tempi 
pi� rapidi per la cifratura e la decifrazione: questo ha spinto a creare metodi di cifra meno 
sicuri ma pi� facili da usare. 
 
 
Sempre nel XIX secolo si ha la risoluzione dei cifrari polialfabetici (Kasiski) e ci sono stati i 
contributi di Kerckhoffs che d� pi� importanza alla chiave che al metodo di cifratura. 
In Francia ci sono stati molti studi teorici sulla crittografia, mentre l�Italia � rimasta un po� in 
disparte. 
  7
1.4    LA CRITTOGRAFIA DAL XX SECOLO A OGGI 
 
Col ventesimo secolo, la crittografia diviene sempre pi� meccanizzata e perde cos� i connotati 
di arte esoterica acquistati nei secoli passati. 
Vernam getta luce teorica sui fondamenti matematici della crittografia ed elabora le propriet� 
delle chiavi molto lunghe. 
Tra le due guerre compaiono le prime cifranti automatiche. Durante la Seconda Guerra 
Mondiale ricordiamo l�Enigma, macchina tedesca per la cui soluzione si adoprano matematici 
come Turing. I giapponesi usano invece macchine i cui nomi in codice sono Arancione e 
Rossa, che vengono risolte durante la guerra; il cifrario della macchina Porpora resister� 
molto pi� a lungo. 
 
 
1.4.1    La crittografia contemporanea 
 
 
Il 1949 � per� l�anno della svolta: Claude Shannon pubblica sul Bell Systems Technical 
Journal l�articolo Communication Theory of Secrecy Systems col quale la crittografia entra 
definitivamente nel panorama della Teoria dell�Informazione. 
Inizia cos� la crittografia contemporanea, che si basa pi� su propriet� matematiche 
teoricamente dimostrabili che sull�ingegno empirico del singolo crittografo. 
Negli anni Settanta, in seguito alla diffusione delle prime reti informatiche, si ha la messa a 
punto del primo sistema crittografico certificato e standardizzato a livello internazionale: � il 
DES (Data Encryption Standard), che resister� fino al 1998 trattando tutte le transazioni 
commerciali del pianeta. 
Oltre al DES si diffondono anche i sistemi a chiave asimmetrica (crittografia a chiave 
pubblica e firma digitale).
  8
Negli anni Novanta, la crittografia rifiorisce in seguito al diffondersi universale della Rete per 
antonomasia, Internet, per affrontare le problematiche di sicurezza e autenticazione relative 
alle varie applicazioni online quali il commercio elettronico, l�e-business, il telelavoro e cos� 
via. 
 
In questo capitolo � stata svolta una breve introduzione sulla storia della crittografia e sui 
concetti fondamentali che stanno alla base. Al lettore desideroso di approfondire queste 
nozioni si suggerisce il testo 16. In ogni caso � reperibile, sia sul mercato che su Internet, 
un�enorme quantit� di materiale informativo.  
  9
 
CAPITOLO 2 
 
 
CENNI SUI CRITTOSISTEMI A 
CHIAVE PUBBLICA 
 
   
2.1    DEFINIZIONE 
 
Un crittosistema si pu� identificare con la quintupla (P, C, K, E, D). 
I cinque enti citati sono: 
 
1) P un insieme dei possibili testi in chiaro. 
2) C un insieme dei possibili testi cifrati. 
3) K un insieme delle possibili chiavi, meglio identificato come 
          spazio delle chiavi. 
4)            Per ogni k ∈  K � definita una funzione di codifica e
k
 ∈  E ed una  
               corrispondente funzione di decodifica d
k
 ∈  D, con e
k
 : P →  C e d
k
 : C →  P 
               tali che d
k
 [e
k 
(x)] = x,  ∀ x ∈  P. 
  10
La funzione di codifica � iniettiva: questo per evitare ambiguitа nella decifrazione. 
L'algoritmo e la chiave sono apparentemente la stessa cosa in quanto rappresentati da una 
sequenza di numeri.  Logicamente c'� per� una differenza: l'algoritmo indica il procedimento 
di calcolo, mentre la chiave � un caso particolare dell'operato dell'algoritmo. 
Ci sono due tipologie principali di crittosistemi: 
 
1) Crittosistemi ad uso ristretto. 
2) Crittosistemi ad uso generale. 
 
Nei crittosistemi ad uso ristretto la sicurezza si basa sulla segretezza degli algoritmi di 
codifica e decodifica, mentre in quelli ad uso generale si basa non pi� su questi ultimi ma su 
un valore segreto detto chiave. 
Affinch� un crittosistema ad uso generale sia sicuro � necessaria un'elevata quantit� di chiavi, 
onde scoraggiare eventuali tentativi di ricerca esaustiva, ovvero di utilizzare tutte le chiavi 
possibili per convertire un testo da cifrato a chiaro. 
I crittosistemi ad uso generale possono essere di due tipi: a chiave privata o a chiave 
pubblica. 
 
Nei crittosistemi a chiave privata, due utenti (ad esempio Paolo e Luca) devono mettersi 
d'accordo sulla chiave. 
In passato una cosa del genere non dava problemi perch� l'uso della crittografia era assai 
ridotto, mentre con l'utilizzo in massa che avviene oggi � del tutto impensabile l'idea di 
corrispondere un paio di chiavi ad ogni coppia di utenti (il numero delle chiavi crescerebbe 
secondo una legge quadratica!). 
 
Questo inconveniente � stato superato a partire dal 1976 con l'introduzione dei crittosistemi a 
chiave pubblica.  
In essi la chiave di cifratura � resa nota al pubblico senza conseguenze riguardo la sicurezza 
del testo cifrato. 
 
Gli utenti generano, ciascuno indipendentemente dall'altro, due chiavi E e D, la prima per la 
codifica e la seconda per la decodifica. 
Paolo, per inviare il messaggio M a Luca, usa la chiave (pubblica) E di Luca. 
  11
Applicando la trasformazione corrispondente otterr� il testo cifrato che invier� a Luca. 
Quest'ultimo, unico a conoscere la chiave D, otterr� il messaggio M applicando la 
trasformazione inversa al crittogramma ricevuto. 
 
I crittosistemi a chiave pubblica sono progettati apposta per l'utilizzo tra molti utenti; non 
sono totalmente inattaccabili, ma basano la loro sicurezza sui lunghissimi tempi necessari ad 
ottenere la chiave di decodifica D da quella di codifica E. 
 
La funzione di cifratura deve essere di tipo particolare: pi� precisamente deve essere una 
funzione pseudodirezionale. 
 
 
Definizione 1 
 
Una funzione si dice one-way function (a senso unico) se � facile il calcolo della diretta ma � 
molto difficile (senza informazioni aggiuntive) quello dell'inversa.    
 
Come difficolt� ci si riferisce a quella computazionale, ovvero ai lunghi tempi di calcolo che 
si creerebbero anche con l'utilizzo dei calcolatori pi� potenti. 
Nel continuo le complessit� di calcolo dell'inversa e della diretta sono quasi uguali, mentre nel 
discreto il calcolo dell'inversa � assai laborioso, anche nei casi in cui � facile il calcolo della 
diretta. 
 
Definizione 2 
 
Una funzione si dice trapdoor one-way function (pseudodirezionale) se � a senso unico ed � 
facilmente invertibile se si � a conoscenza delle informazioni particolari riguardanti la sua 
costruzione. 
  12
2.2    IL PROBLEMA DEL LOGARITMO DISCRETO 
 
Il funzionamento di molti crittosistemi a chiave pubblica � basato sul calcolo di logaritmi 
discreti su certi gruppi ciclici, impresa assai ardua dal punto di vista  computazionale (il pi� 
noto crittosistema basato sul logaritmo discreto � l�El Gamal).   
Gli studi su questo problema non hanno trovato algoritmi a tempo polinomiale  
(vedi sez. 2.3.1) per la soluzione ed inoltre non � neppure stata trovata una dimostrazione che  
esistano algoritmi pi� rapidi.  
In crittografia, l'utilit� del problema del logaritmo discreto consiste nel fatto che la ricerca di 
logaritmi discreti � un'operazione laboriosa, al contrario dell'operazione inversa (elevamento a 
potenza) che invece � pi� rapida ed efficiente. 
 
 
          
2.2.1    Problema del logaritmo discreto in (G, •) 
 
Si consideri un generico gruppo (finito) e si denoti con • la sua legge di  composizione. 
Il problema del logaritmo discreto si presenta nella seguente forma: 
         
 
dato un gruppo finito (G, �), a ∈  G, b ∈  H, con H = {a
i
: i ≥  0} sottogruppo generato da a,    
determinare l'unico intero c tale che 0 ≤  c ≤  H -1 e a
c
 = b. 
L'intero c si indica con log
a
 b. 
         
Consideriamo ad esempio il campo finito Z
p
, con p primo (problema del logaritmo discreto  
in Z
p
).  In questo caso posso descrivere il problema nel seguente modo: 
dato p primo, a ∈  Z
p
  elemento primitivo (cio� a ha ordine uguale a p - 1), b ∈  Z
p
 *,            
determinare l'unico intero c, con 0 ≤  c ≤  p - 2, tale che a
c
 ≡  b mod p. L'intero c si denota  
con log
a
 b. 
� da notare che H, per ogni scelta di a ∈  G, � un gruppo ciclico di ordine H . 
Quindi la questione si riconduce al caso di problema in un gruppo ciclico. 
         
  13
Questo mostra come la difficolt� del problema del logaritmo discreto dipenda  
principalmente dalla rappresentazione del gruppo considerato. 
Ci sono anche dei casi in cui la risoluzione del problema del logaritmo discreto �  banale. 
Consideriamo, per esempio, il gruppo additivo ciclico Z
n
 e supponiamo MCD (a, n) = 1  
(quindi a � un generatore di Z
n
 ). L'operazione a
c
  corrisponde alla moltiplicazione di a per c 
modulo n. In questo caso il problema del logaritmo discreto consiste nel trovare un intero c 
tale che a c ≡  b mod n. 
Dal fatto che  MCD (a, n) = 1 segue che a possiede a
-1 
, inverso moltiplicativo modulo n che si 
pu� facilmente calcolare con l'algoritmo euclideo. 
A questo punto si ricava facilmente c = log
a
 b = b a
-1
  mod  n. 
Si consideri il gruppo moltiplicativo Z
p
*, con p primo. Esso � un gruppo ciclico di ordine p - 
1 e quindi � isomorfo al gruppo additivo Z
p - 1
. 
� stato mostrato in precedenza quanto il calcolo del logaritmo discreto sia efficiente in tali  
gruppi additivi. Questo suggerisce di trasportare il problema dato in quello facilmente    
risolvibile in Z
p - 1
.  
Questo metodo pu� essere applicato al problema del logaritmo discreto in ogni gruppo G. 
Se esiste un metodo efficiente per calcolare l'isomorfismo tra H e Z
 H  
, il  
problema del logaritmo discreto in G  pu� essere risolto in maniera efficiente. 
Al contrario, si pu� mostrare facilmente che un efficiente metodo di calcolo del   
logaritmo discreto produce un efficiente algoritmo per il calcolo dell'isomorfismo tra i due  
gruppi. 
         
Quanto detto finora mostra che la difficolt� del problema del logaritmo discreto dipende dalla 
rappresentazione del gruppo ciclico considerato. 
Un problema molto interessante � la ricerca di gruppi per cui il problema del logaritmo  
discreto sia intrattabile: tra questi vi sono i gruppi moltiplicativi di un campo di Galois 
GF(p
n
) e i gruppi su curve ellittiche in un campo finito. Quest�ultima tipologia di gruppi 
verr� trattata in questa tesi con un tema diverso: verranno usati per la fattorizzazione e la 
primalità di grandi interi, come si potr� vedere nei prossimi capitoli.   
  14
2.3    IL CRITTOSISTEMA  RSA  
                                                                   
Per lo studio dell'algoritmo RSA � necessaria una trattazione preliminare di alcuni teoremi e 
algoritmi usati in Teoria dei Numeri. 
Tra questi, devono essere esaminati: il Teorema di Eulero, avente come caso particolare il 
Teorema di Fermat, e l'Algoritmo di Euclide, con le sue varianti. 
Molto utile sar� anche il Teorema del Resto Cinese, per la risoluzione di vari sistemi di 
congruenze. Prima di discutere l'algoritmo verr� fatta una breve panoramica degli strumenti 
matematici appena accennati, in modo da avere i giusti requisiti. 
 
2.3.1    Algoritmi deterministici e algoritmi probabilistici 
 
Un algoritmo pu� essere visto come una procedura, che, ricevuti dei dati in ingresso (input) 
restituisce una o pi� risposte (output) dopo un tempo finito. 
I requisiti fondamentali per la bont� di un algoritmo sono la correttezza (gli output siano 
esattamente quelli richiesti) e la stima del tempo computazionale, che deve essere adeguato 
all'uso pratico; l'ideale sarebbe una stima del peggior tempo e del tempo medio. 
I tempi vengono calcolati tramite operazioni binarie (prevedono l'uso delle cifre 0 e 1);  
la dimensione dei dati in ingresso sar� invece data dal numero di bit che richiedono: 
un intero positivo  n  avr� quindi dimensione: 1+  log
2  
n   (il simbolo associato al logaritmo  
indica qui, e nel seguito, la parte intera). 
Una suddisione degli algoritmi in base al tempo di esecuzione pu� essere la seguente: 
 
        
                 Tipo Algoritmo                                   Tempo di esecuzione 
               
              A tempo lineare                                 O [ln(n)] 
              A tempo quadratico                           O [ln
2
(n)] 
              A tempo polinomiale                          O [P(ln(n)], P polinomio generico, deg P >  2  
              A tempo esponenziale                       O [n
α
] , α  ∈  R
+
 
 
          
  15
Ci sono anche algoritmi con tempi di esecuzione intermedi, tra i quali spiccano quelli di  
fattorizzazione, molti dei quali prevedono tempi dell'ordine: 
 
                                 e
cn nln ln ln
 ,     c ∈  R
+
. 
 
La trattazione appena svolta riguarda gli algoritmi deterministici: 
questi ultimi producono risultati corretti (a parte eventuali errori umani o computazionali). 
Ci sono anche algoritmi dipendenti dall'uso dei numeri casuali, detti  
algoritmi probabilistici. 
 
         
Alcuni cenni sugli algoritmi probabilistici 
 
La nozione di algoritmo probabilistico � imprecisa poich� tra gli eventi possibili v'� anche  
quello che la procedura non vada a termine. 
In molti casi gli algoritmi probabilistici sono pi� efficienti di quelli deterministici: 
diversi problemi possono infatti essere risolti solo per via probabilistica.  
A caratterizzare gli algoritmi  probabilistici non � tanto il tempo assoluto di esecuzione ma il   
tempo atteso di esecuzione. 
Gli algoritmi probabilistici danno una risposta corretta con una probabilit� non uguale a 1 ma    
abbastanza vicina, col vantaggio per� di impiegare un tempo molto inferiore. 
Un esempio di algoritmo probabilistico pu� essere il seguente: 
dato un intero n molto grande, stabilire se � primo (test di primalità). 
Se la divisione per una prefissata quantit� di interi piccoli non ha successo, pu� nascere il 
sospetto che n sia primo: si ricorre quindi al calcolo di  2
n - 1 
  mod  n.  Se il risultato  
non  � 1 mod  n, n non � primo per il Teorema di Fermat (vedi sez. 2.3.2). In caso contrario             
c�� una  buona probabilit� che n sia primo. 
A partire dal capitolo successivo verranno esaminate varie applicazioni di algoritmi      
probabilistici, i quali sono di notevole importanza proprio nei test di primalità, principale  
oggetto di studio di questa tesi.