Complejidad algorítmica
“Curso de Introducción a la Criptografía”
by Jordi Íñigo Griera is licensed under a
Creative Commons Attribution 4.0 International License.
Project hosted at github.com/jig/crypto
Notación $O$; $b$ es la longitud en bits de los operandos
| Algoritmo | Complejidad | Complejidad |
| $(a+b) \mod n$ | $O(b)$ | polinómica |
| $(a·b) \mod n$ | $O(b^2)$ | polinómica |
| $a^{-1} \mod n$ | $O(b^2)$ | polinómica |
| $a^k \mod n$ | $O(b^{b_k+1})$ | exponencial (alg. mult. repetida) |
| $a^k \mod n$ | $O(b^3)$ | polinómica (alg. sqr y multiplica) |
| $\sqrt[e]{a} \mod p$ | $O(b^3)$ | polinómica ($p$ primo) |
| $\sqrt[e]{a} \mod n$ | factoritzación $\downarrow$ | — |
| Algoritmo | Complejidad | Complejidad |
| encontrar clave simétrica-$b$ | $O(2^b)$ | exponencial |
| colisión hash-$b$ | $O(\sqrt{2^b}) = O(2^{b/2})$ | exponencial |
| factorización $n=p\cdots$ | $O(b_n·\sqrt{2^{b_p}})$ | exponencial (divisió consecutiva) |
| factorización $n=p\cdots$ | $O(2^{2,774·(b_n^{1/3})(ln(b_n)^{2/3})})$ | subexponencial(alg. GNFS) |
| DLP | $O(2^{2,774·(b^{1/3})(ln(b)^{2/3})})$ | subexponencial(alg. GNFS) |
| ECDLP | $O(2^{b/2})$ | exponencial(alg. Pollard's ρ) |
bits de seguridad
según el NIST
| <2030 | >2030 | ||||
| bits de seguridad $\rightarrow$ | $80$ | $112$ | $128$ | $192$ | $256$ |
| encontrar una clave simétrica-$b$ | $80$ | $112$ | $128$ | $192$ | $256$ |
| colisión hash-$b$ | $160$ | $224$ | $256$ | $384$ | $512$ |
| factorización | $1024$ | $2048$ | $3072$ | $7680$ | $15360$ |
| DLP | $1024$ | $2048$ | $3072$ | $7680$ | $15360$ |
| ECDLP | $160$ | $224$ | $256$ | $384$ | $512$ |
Algoritmos recomendados y tamaños
| $\dagger$ | $\ddagger$ | |
| Cifrado simétrico | AES-128 |
AES-256 |
| Hash | SHA-256
| SHA-384 |
| H/MAC | SHA-256 |
SHA-256 |
| RSAP $\rightarrow$ RSA | RSA-2048 |
RSA-3072 |
| DLP $\rightarrow$ DH | DH-2048 |
DH-3072 |
| ECDLP $\rightarrow$ ECDSA|ECDH | NIST P-256, Curve25519 |
NIST P-384 |
$\dagger$) NIST recomendadas a nivel Secret
$\ddagger$) NIST recomendadas a nivel Top-Secret