Calcolare la complessità di un algoritmo
L'elemento principale per valutare la resistenza di un algoritmo di crittografia all'analisi crittografica è il tempo necessario per svolgere l'attacco. In generale non si può essere certi di aver trovat l'algoritmo di attacco più efficiente. Tutt'al più si può dire che, per un determinato algoritmo, il livello di impegno per un attacco è di un determinato ordine di grandezza. Quindi si può confrontare tale ordine di grandezza con la velocità dei microprocessori disponibili, per determinare il livello di sicurezza di un dato algoritmo.
Una misura comune dell'efficienza di un algoritmo è la sua complessità temporale. Si definisce complessità temporale di un algoritmo la funzione f(n) tale che, per tutti gli input di lunghezza n, l'esecuzione dell'algoritmo richiede al più f(n) passi. Pertanto, per determinate dimensioni di input e determinate velocità del microporcessore, la complessità temporale è un limite superiore del tempo di esecuzione.
La definizione contiene numerose ambiguità. Innanzitutto, la definizione di passo non è precisa. Un passo potrebbe essere un'unica operaazione di una macchina di Turning, un'istruzione del microprocessore, un'istruzione in un linguaggio di alto livello e così via. Tuttavia, queste differenti definizioni di "passo" dovrebbero essere tutte correlate con semplici costanti moltiplicative. Per valore molto estesi di n, queste costanti non sono importanti. Ciò che è importante è la velocità con cui il tempo di esecuzione relative cresce. Per esempio se ci si chjiede se il problema di utilizzare chiavi a 50 cifre (n=10 alla 50) o a 100 cifre (n= 10 alla 100) per RSA, non è necessario (né realmente possibile) conoscere esattamente quanto tempo sarebbe necessario per violare le chiavi di ciascuna dimensione. Piuttosto si è interssati ai valori generici del livello di impegno e a conoscere qual è l'impegno relativo necessario per chiavi di dimensioni sempre più grandi.
Il secondo problema è che, in generale, non si può stabilire una formula esatta per f(n) ma solo una forma approssimata. Anche in questo caso si è principalmente interessati alla velocità di variazione di f(n) all'aumentare di n.
