Computational security

Potenzialmente si può conoscere un algoritmo che riesce a rompere la chiave (anche brute force), ma la potenza di calcolo necessaria non è accessibile. La sicurezza sta nella difficoltà computazionale che serve per romperli.

• la chiave deve essere corta, ma abbastanza grande da resistere un attacco brute force
• conosciuta la chiave, la codifica e la decodifica devono essere efficienti

Funzione efficiente: polinomiale

I costi sono polinomiali. $p(n):=a\times n^x$

$a$ e $x$ sono parametri che caratterizzano lo schema. $n$ è il parametro di sicurezza, quindi per uno schema con chiave a 128 bit, servono $a\times 128^x$ operazioni.

Funzione trascurabile

Più piccola delle funzioni polinomiali. $\exists N:f(n)<\frac{1}{p(n)},\forall n>N$

Quindi chi ha la chiave deve operare con algoritmi veloci ed efficienti (polinomiali). Chi non la ha ma vuole comunque decodificare i dati, deve lavorare con algoritmi inefficienti. Pù diverge il costo, più l’algoritmo è sicuro.

Sicurezza di un algoritmo computazionale

La sicurezza è calcolata in base alla media delle operazioni necessarie per rompere lo schema:

• sicurezza a 80bit: ~$2^{80}$ operazioni
• sicurezza a 112bit: ~$2^{112}$ operazioni
• sicurezza a 128bit: ~$2^{128}$ operazioni

Nella cifratura moderna simmetrica, la lunghezza della chiave definisce il livello di sicurezza, perchè è tutto basato sulla scoperta della chiave, quindi uno schema che utilizza una chiave a 128bit garantisce un livello di sicurezza di 128 bit.

Stream cipher Block ciphers