Quiero poder saber cuántas claves por segundo, utilizando claves RSA de 1024 bits, se pueden verificar en un sistema Pentium 4 estándar. ¿Cómo puedo usar esto para determinar el rendimiento del descifrado y, posiblemente, el tiempo restante?
El rendimiento realmente depende de la implementación, el tipo de procesador, el reloj del procesador y muchos otros factores. La utilidad de línea de comandos OpenSSL incluye una herramienta de referencia. Por ejemplo:
$ openssl speed rsa1024
Doing 1024 bit private rsa's for 10s: 2430 1024 bit private RSA's in 9.28s
Doing 1024 bit public rsa's for 10s: 48984 1024 bit public RSA's in 9.92s
OpenSSL 1.0.1 14 Mar 2012
built on: Tue Jul 3 20:15:19 UTC 2012
options:bn(64,32) rc4(8x,mmx) des(ptr,risc1,16,long) aes(partial) blowfish(idx)
compiler: cc -fPIC -DOPENSSL_PIC -DZLIB -DOPENSSL_THREADS -D_REENTRANT -DDSO_DLFCN
-DHAVE_DLFCN_H -DL_ENDIAN -DTERMIO -g -O2 -fstack-protector --param=ssp-buffer-size=4
-Wformat -Wformat-security -Werror=format-security -D_FORTIFY_SOURCE=2
-Wl,-Bsymbolic-functions -Wl,-z,relro -Wa,--noexecstack -Wall -DOPENSSL_NO_TLS1_2_CLIENT
-DOPENSSL_MAX_TLS1_2_CIPHER_LENGTH=50 -DOPENSSL_BN_ASM_PART_WORDS -DOPENSSL_IA32_SSE2
-DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_GF2m -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DMD5_ASM
-DRMD160_ASM -DAES_ASM -DVPAES_ASM -DWHIRLPOOL_ASM -DGHASH_ASM
sign verify sign/s verify/s
rsa 1024 bits 0.003819s 0.000203s 261.9 4937.9
Se sabe que la máquina en la que ejecuté esto es bastante lenta (es un clon VIA C7 x86 de baja potencia). Un Pentium 4 (que también es un sistema de 32 bits) debería ejecutarse al menos tan rápido como eso, pero probablemente no mucho más rápido (Me sorprendería si OpenSSL alcanzara las 1000 firmas por segundo con RSA 1024 en un Pentium 4). p>
Convertir una figura de este tipo en el rendimiento de aplicación es un ejercicio difícil.
Esta pregunta está etiquetada como "fuerza bruta". Obviamente, no es factible intentar una RSA de 1024 bits de fuerza bruta ingenua al intentar cada clave RSA de 1024 bits posible. Incluso si pudieras validar una clave en Tiempo de Planck (Wikipedia) y pudieras ejecutar este algoritmo en cada átomo en el universo y lo habría hecho desde el Big Bang , todavía no habrías encontrado la clave.
La buena noticia es que hay atajos. Una opción es la factorización de enteros. Si conoce la clave pública y está tratando de forzar la clave privada, puede probar un algoritmo de factorización de enteros . Si tiene éxito, puede ir a RSA Laboratories y reclamar su premio de $ 100,000 . Buena suerte con eso :-).
Un enfoque más probable se basa en el hecho de que los pares de claves RSA generalmente se eligen utilizando algoritmos determinísticos que comienzan a partir de una semilla pseudo-aleatoria relativamente corta. Si conoce (o puede adivinar) el algoritmo utilizado para elegir la clave bajo ataque y el número de semillas posibles también es limitado (ya sea porque el tamaño de la semilla es pequeño o porque el generador de números pseudoaleatorios es semana), esto podría limitar el número de semillas. Posibles claves para un número aceptable. Tales ataques se han realizado en el pasado en claves generadas por sistemas específicos, pero estos son bastante raros y están muy lejos.
Incluso si tiene suerte y el algoritmo de par de claves RSA utilizado se basa en una semilla aleatoria de 16 bytes (nunca he visto nada más corto que eso), e incluso si tuviera una computadora que pudiera hacer un millón de RSA operaciones de clave privada por segundo (y usted no lo hace) todavía le tomaría un promedio de 6 billones de billones de años para que la fuerza bruta de la clave bruta.
Por lo tanto, la única situación en la que es posible hoy aplicar fuerza bruta a una clave privada RSA de 1024 bits es si la semilla pseudoaleatoria utilizada para generar la clave es algo predecible y limita el número de posible semilla a un número inferior a 2 por el poder de 50 o menos. Si conoces un algoritmo tan defectuoso que está en uso, definitivamente valdría la pena un trabajo de investigación. De lo contrario, el algoritmo de acceso rápido a la fuerza bruta sería esperar hasta que pueda obtener una computadora cuántica .
Lea otras preguntas en las etiquetas brute-force