Complexitat algorísmica
“Curs d'Introducció a la criptografia”
by Jordi Íñigo Griera is licensed under a
Creative Commons Attribution 4.0 International License.
Project hosted at github.com/jig/crypto
Notació $O$; $b$ és la longitud en bits dels operands;
variants "llapis i paper" excepte indicació contrària
| Algorisme | Complexitat | Complexitat |
| $(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 (mult. repetida) |
| $a^k \mod n$ | $O(b^3)$ | polinòmica (sqr i multiplica) |
| $a^{1/2} \mod p$ | $O(b^3)$ | polinòmica |
| $a^{1/2} \mod n$ | factorització $\downarrow$ | subexponencial |
| Algorisme | Complexitat | Complexitat |
| trobar clau simètrica-$b$ | $O(2^b)$ | exponencial |
| col·lisió hash-$b$ | $O(\sqrt{2^b})$ | exponencial |
| factorització $n=p\cdots$ | $O(b_n·\sqrt{2^{b_p}})$ | exponencial (divisió consecutiva) |
| factorització $n=p\cdots$ | $O(2^{2,774·(b_n^{1/3})(ln(b_n)^{2/3})})$ | subexponencial (QSA) |
| DLP | $O(2^{2,774·(b^{1/3})(ln(b)^{2/3})})$ | subexponencial |
| ECDLP | $O(\sqrt{2^b})$ | exponencial |
bits de seguretat
els bits de seguretat (security strength) derivats de la complexitat algorísmica
| longitud $\rightarrow$ | $64$ | $128$ | $256$ | $512$ | $1024$ | $2048$ | $4096$ | $8192$ |
| trobar clau simètrica-$b$ | $2^{64}$ | $2^{128}$ | $2^{256}$ | $2^{512}$ | $2^{1024}$ | $2^{2048}$ | $2^{4096}$ | $2^{8192}$ |
| col·lisió hash-$b$ | $2^{32}$ | $2^{64}$ | $2^{128}$ | $2^{256}$ | $2^{512}$ | $2^{1024}$ | $2^{2048}$ | $2^{4096}$ |
| factorització | $2^{28,7}$ | $2^{40}$ | $2^{55}$ | $2^{75}$ | $2^{101}$ | $2^{136}$ | $2^{182}$ | $2^{242}$ |
| DLP | $2^{28,7}$ | $2^{40}$ | $2^{55}$ | $2^{75}$ | $2^{101}$ | $2^{136}$ | $2^{182}$ | $2^{242}$ |
| ECDLP | $2^{32}$ | $2^{64}$ | $2^{128}$ | $2^{256}$ | $2^{512}$ | $2^{1024}$ | $2^{2048}$ | $2^{4096}$ |
bits de seguretat
segons el NIST
| <2030 | >2030 | ||||
| bits de seguretat $\rightarrow$ | $80$ | $112$ | $128$ | $192$ | $256$ |
| trobar clau simètrica-$b$ | $80$ | $112$ | $128$ | $192$ | $256$ |
| col·lisió hash-$b$ | $160$ | $224$ | $256$ | $384$ | $512$ |
| factorització | $1024$ | $2048$ | $3072$ | $7680$ | $15360$ |
| DLP | $1024$ | $2048$ | $3072$ | $7680$ | $15360$ |
| ECDLP | $160$ | $224$ | $256$ | $384$ | $512$ |
Algorismes recomanats i mida
| $\dagger$ | $\ddagger$ | |
| Xifrat simètric | 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 recomenades fins a nivell Secret
$\ddagger$) NIST recomenades fins a nivell Top-Secret