Crittografia

Cenni di teoria della complessità e teoria dei numeri

Cenni di teoria della complessità e teoria dei numeri. Appendice della tesi di laurea in "Applicazione delle tecniche di crittografia nella trasmissione ed elaborazione dati" redatta dall'ingegnere Federico Gennari nell'anno accademico 2000/2001.

APPENDICE 1: cenni di teoria della complessità e teoria dei numeri

La finalità principale della teoria della complessità è di fornire strumenti per classificare problemi di calcolo secondo le risorse necessarie per risolverlo (essenzialmente il tempo, talvolta anche la memoria), basandosi essenzialmente sulla difficoltà intrinseca del problema piuttosto che sul particolare modello di calcolo.

Suddetti problemi saranno risolti medianti algoritmi, il cui tempo di lavoro è il numero di operazioni elementari che esso deve compiere per arrivare alla soluzione (operazioni binarie, comparazioni, istruzioni macchina ecc.). In genere si usa il tempo nel caso peggiore, essendo un limite superiore, in funzione della grandezza dell’ingresso, ma ci si può riferire anche al tempo medio (sempre in funzione dell’ingresso) e al tempo asintotico, ovvero quando l’ingresso cresce all’infinito.

Un algoritmo a tempo polinomiale è un algoritmo il cui tempo nel caso peggiore che è una funzione dell’ordine O(n^k), dove n è la dimensione dei dati di ingresso e k una costante. Un algoritmo il cui tempo di lavoro non è polinomiale è chiamato a tempo esponenziale, ed è considerato inefficiente.

Un algoritmo a tempo sub-esponenziale ha un tempo di lavoro nel caso peggiore è una funzione del tipo e^o(n). Esso è asintoticamente più veloce di uno a tempo esponenziale pieno ma asintoticamente più lento di uno a tempo polinomiale.

La classe di complessità P è l’insieme di tutti i problemi di decisione (problemi la cui risposta è si/no,  a cui ci limitiamo per facilità ma i cui algoritmi possono essere estesi ai problemi computazionali) che sono risolvibili in tempo polinomiale.

La classe di complessità NP è l’insieme di tutti i problemi decisionali per cui la risposta SI può essere verificata in un tempo polinomiale avendo una informazione extra detta certificato (non è detto che però sia semplice ottenerlo).

La classe di complessità co-NP è l’analogo del precedente, ma riguardante la risposta NO.

Esempio  Proposizione: n è un numero intero.

                Domanda: n è composto? Cioè, esistono a,b>1 tali che n=ab?

I composti appartengono a NP perché se un intero n è composto può essere verificato in tempo polinomiale se viene dato il certificato divisore a (1<a<n). Analogamente appartengono a co-NP.

Elenchiamo adesso una serie di risultati della teoria dei numeri con applicazioni alla crittografia:

•  Teorema fondamentale dell’aritmetica;
• Complessità computazionale delle quattro operazioni base;
•  Algoritmo di Euclide per il calcolo del Massimo Comune Divisore (MCD) di due interi;
•  Se a e b sono interi, allora a è detto essere congruente a b modulo n, scritto (mod n), se n divide (a - b). L’intero n è chiamato modulo della congruenza.  
1. Generalizzazione d’Eulero del Teorema di Fermat: se N=pq, con sia p che q numeri primi, definendo ø(N)=(p-1)(q-1), allora Xø(N) = 1 mod N è vera per tutti gli X non divisibili per p e q (cioè sono primi tra loro, MCD (X, ø(N) )=1).            
2.  Teorema del resto Cinese (CRT)
•  Algoritmo di Gauss: produce la soluzione x del Teorema del resto Cinese, calcolato come(dove N_i=n/n_i e M = N_i^-1) in O( (lg n)²) operazioni su bit.
•  Sia n2 un intero:
•  (teorema di Eulero) se aZ_n*, allora
• se n è un prodotto di primi distinti, e se , allora  per tutti gli interi a. In altre parole, quando si lavora modulo n, gli esponenti possono essere ridotti modulo .
• Tabella della complessità delle operazioni base su bit in Z_n

              L’insieme di Z_n è rappresentato dagli interi {0, 1, 2, …, n - 1}, con le seguenti operazioni

• Somma modulare            (a + b)=  a+b               (se a+b<n)

                                                                     a+b-n                      (se )

•  Esponenziale modulare può essere eseguito efficientemente con l’algoritmo quadra-e-moltiplica  (square-and-root) ripetuto, che è cruciale in molti protocolli crittografici. Una versione dell’algoritmo è basato sulla rappresentazione dei numeri in base 2, ad esempio del numero k

                                        (dove k_i {0,1})

•  Algoritmo di quadra-e-moltiplica ripetuto per esponenziali in Z_n ;
•  Simbolo di Legendre e Simbolo di Jacobi;
• Strutture algebriche;

La sicurezza di molti codici a chiave pubblica si basa sulla presunta intrattabilità dei problemi computazionali elencati sommariamente nella tabella seguente. Parlando non rigorosamente un problema è facile o trattabile se può essere risolto in tempo polinomiale, almeno per una frazione non trascurabile degli ingressi possibili. In altre parole, se c’è un algoritmo che può risolvere una frazione non trascurabile  di tutte le istanze di un problema in tempo polinomiale, allora un qualsiasi crittosistema la cui sicurezza è basata su quel problema deve essere considerato insicuro. I problemi di calcolo qui elencati hanno una complessità reale non conosciuta, cioè sono ampiamente considerati intrattabili (se si scelgono bene i parametri del problema) sebbene non ci sia ancora una prova univoca. Generalmente, il solo limite inferiore conosciuto sulle risorse richieste per la soluzione sono banali limiti lineari, che non forniscono una prova della loro intrattabilità. Per questa ragione sono state escogitate varie tecniche di riduzione di un problema computazionale in un altro: queste riduzioni forniscono un mezzo per convertire un algoritmo che risolve il secondo problema in un algoritmo per la soluzione del primo e sono studiate in letteratura (si veda la bibliografia maggiori notizie).

• » Invia tramite EMAIL
• » Versione per la STAMPA
• » Le vostre opinioni

I link correlati all'argomento

• La tesi di laurea in Tecniche crittografiche
• Appendice 2 della tesi
• Appendice 3 della tesi
• Appendice 4 della tesi