¿Cómo se pueden factorizar grandes números para determinar la seguridad de los populares algoritmos de cifrado?

Question

¿De qué manera la seguridad del algoritmo de cifrado depende del factorizar números grandes?

Por ejemplo, he leído en algunos foros de programación matemática que al usar el tamiz cuadrático o el Tamiz de campo de número general, se puede factorizar un número de 256 bits con relativa facilidad en hardware disponible comercialmente.

¿Cómo se traduce esto en poder romper la seguridad de algoritmos como RSA, AES, etc.? ¿Ser capaz de factorizar los números de la longitud de la clave es suficiente?

¿Hay alguien entendido en criptografía y algoritmos de cifrado que pueda arrojar algo de luz sobre él?

Answer 1

RSA, cryptoalgorithm, se basa en la teoría de números, específicamente la multiplicación de dos números primos grandes y el hecho de que es difícil de factorizar, para diferenciar entre claves públicas y privadas.

aquí hay una pregunta en Yahoo respuestas en la que alguien ha dado algún detalle: http://answers.yahoo.com/question/index?qid=20070125183948AALJ40l

Se basa en algunos hechos:

• n=p.q es fácil de calcular pero difícil de revertir el pequeño teorema
• de Fermat : http://en.wikipedia.org/wiki/Fermat%27s_little_theorem
• Varios resultados de la teoría de números.

No es factorizar números grandes lo que es difícil, es factorizar dos números grandes cuyos únicos factores son en sí mismos primos grandes, porque encontrar esos números primos es difícil.

Una búsqueda rápida a través de mis marcadores me da esto: the mathematical guts of rsa encryption si le interesa cómo funciona. También, algunas explicaciones aquí también, solo vuelve a leer mis notas de teoría numérica para ser claro.

• n = p * q le da un número grande dado p, q prime.
• phi (n) = (p-1) (q-1). Esta es una extensión del pequeño teorema de Fermat Más sobre por qué necesitamos esto y por qué funciona en mi blog aquí: http://vennard.org.uk/weblog/2010/02/a-full-explanation-of-the-rsa-algorithm/
• Lo que significa, si elegimos un número E coprime (sin factores primos comunes) a (p-1) (q-1) podemos encontrar Es mod inversa phi (n).

• Lo que hacemos, encontramos DE = 1 (p-1) (q-1) o más bien lo resolvemos usando el mayor algoritmo de divisor común de euclides, versión extendida.

• Ahora, dado todo lo anterior, si tomamos T^E (pq) obtenemos C. Sin embargo, si tomamos (T^E)^D (pq) volvemos a T.

AES no es lo mismo, no es una criptografía de clave pública. AES toma una clave y la usa en ambas direcciones, cifrado y descifrado. El proceso es básicamente muy difícil de deshacer, más bien como un hash pero diseñado para ser reversible. Sin embargo, no depende de factorizar grandes números en primos para su seguridad; se basa completamente en la fuerza de la clave y la incapacidad de deducir la clave del algoritmo o la clave dada texto llano conocido y el algoritmo.

Wikipedia tiene a good article on AES de alto nivel con un buen enlace que le muestra cómo funciona - vea here y here. Me gusta particularmente el último enlace.

Answer 2

AES es muy diferente, AES crea un SPN, Red de permutación de sustitución. Genera s-boxes (cajas de sustitución) basadas en funciones polinomiales generadas en tiempo de encriptación. Lo ejecuta a través de 10-14 rondas de sustitución de nivel de byte y permuta de nivel de bit, la longitud de bit de la clave determina el número de rondas y las teclas de ronda.

RSA se basa en factores de números primos grandes que son extremadamente difíciles de computar, pero bastante fáciles de cifrar inicialmente.

Answer 3

¿De qué manera la seguridad de un algoritmo de encriptación depende de factorizar números grandes?

La frase que falta es "clave pública", como en "¿Cómo es la seguridad del algoritmo de cifrado de clave pública ..."

En la criptografía moderna hay dos categorías principales de sistemas de cifrado, simétrico (clave secreta) y clave pública (que usa un par de claves públicas/privadas).

Dentro de cada categoría, encontrará los tamaños de clave relativamente cerca. Para los sistemas de clave pública como RSA y DH/DSA, ambos utilizados en el cifrado de correo electrónico OpenPGP, los tamaños de clave comunes son 1024 bits y más grandes en estos días (principios de 2010). Esto tiene que ver con los requisitos matemáticos de las claves adecuadas utilizadas para cifrar y descifrar mensajes. Para RSA, en pocas palabras, es mucho más fácil generar un factor de dos números primos grandes aleatorios y hacer multiplicaciones con ellos, en comparación con factorizar un número muy grande que no tiene factores pequeños. Como ha descubierto el factoring de números muy grandes es el "problema" o enfoque necesario para romper RSA a través de la fuerza bruta.

Diffie-Hellman/Algoritmo de firma digital (DH/DSA) se basan en un problema matemático diferente, el cálculo de logaritmos discretos.

Debido a las propiedades de los pares de claves públicas y privadas, el espacio de búsqueda se limita a los factores de grandes números primos, que se vuelve muy escasa, así que tiene sentido tratar de ser ahora más inteligente entonces simplemente tratando de factor de cada número muy grande.

Mientras que con sistemas de cifrado simétrico como AES, RC6, RC4, Twofish, DES y Triple-DES, estos algoritmos utilizan una clave aleatoria de una longitud de bits dado. Cualquier clave aleatoria no trivial (es decir, 0x000 ... 000 puede ser una elección de clave incorrecta) es adecuada. Entonces, estos sistemas, si no hay ataque contra el algoritmo en sí, simplemente puede buscar fuerza bruta a través del espacio clave (es decir, pruebe todas las 2^256 claves posibles) para descifrar un mensaje sin la clave secreta. Como cualquier tecla es adecuada, la densidad de las teclas es 2^256.

Estoy haciendo caso omiso de Quantum Computing (teórico y práctico), principalmente porque a) No puedo dar una respuesta sólida, yb) representa un gran cambio de paradigma que convierte muchas matemáticas aplicadas y ciencias de la computación de la complejidad computacional en su cabeza, esa comprensión básica sigue siendo un objetivo en movimiento. Ah, y la mayoría de mis enemigos aún no tienen una computadora cuántica. :)

Espero que esto explique la diferencia general entre los dos tipos de sistemas de cifrado, como RSA y AES.

Recuadro: La criptografía es un tema rico y complejo, donde los conceptos básicos pueden ser bastante simple de entender, e incluso escribir una aplicación ingenua ("libro de texto"), las complejas sutilezas de una aplicación segura hace que sea mejor para los programadores que no son expertos en criptografía para usar cripto-sistemas de alto nivel, incluido el uso de protocolos estándar bien conocidos para mejorar sus posibilidades de que la criptografía de un sistema no sea la falla explotable en un sistema.

Answer 4

RSA está roto por factorización. En realidad, RSA es dos algoritmos, uno para encriptación (asimétrica) y uno para firmas digitales; ambos usan el mismo primitivo. En RSA, hay un valor público (el módulo , a menudo mencionado n) que es un producto de dos (o más) factores primos distintos. El factorizar n revela la clave privada. El factoring se vuelve más difícil cuando aumenta el tamaño de n. El registro actual (publicado a principios de este año) es para un entero de 768 bits; tomó cuatro años de gran computación y trabajo duro por personas muy inteligentes. Las mismas personas admiten abiertamente que tienen poca idea de cómo podrían intentar el mismo truco en un entero de 1024 bits (hay una parte del algoritmo de factorización mejor conocido que requiere una gran cantidad de RAM rápida, y para un 1024-bit entero que requeriría una máquina ridículamente grande). Las recomendaciones actuales de longitud de clave para RSA son 1024 bits para corto plazo, 2048 bits para seguridad a largo plazo. Tenga en cuenta que el costo computacional de RSA aumenta con el tamaño de la clave también, por lo que no queremos utilizar realmente grandes teclas sin una buena razón. Una PC básica producirá alrededor de 1000 firmas RSA por segundo (y por núcleo) con una clave de 1024 bits, y ocho veces menos con una clave de 2048 bits. Esto sigue siendo bastante bueno.

Existen otros algoritmos de encriptación asimétrica y algoritmos de firma digital. Algo relacionado con RSA es el algoritmo de encriptación Rabin-Williams; el factoring también lo rompe. Luego están los algoritmos basados ​​en el logaritmo discreto (en el grupo multiplicativo de números módulo a gran prima): Diffie-Hellman (intercambio de claves), DSA (firma), El Gamal (encriptación) ... para estos algoritmos, la factorización no es directa amenaza; pero se basan en las mismas partes de la teoría de números, y el algoritmo mejor conocido para el logaritmo discreto es muy similar al algoritmo mejor conocido para la factorización (y tiene el mismo nombre: GNFS - como General Number Field Sieve). Por lo tanto, se sospecha que un avance en la factorización sería el resultado de un avance en la teoría de los números, que también arrojaría alguna luz sobre el logaritmo discreto.

Los algoritmos del logaritmo discreto se pueden aplicar a otros grupos, siendo las más populares las curvas elípticas. Las curvas elípticas no se ven afectadas por la factorización. Si la factorización se hiciera fácil, por lo tanto, al eliminar RSA y poner en peligro indirectamente a DSA y Diffie-Hellman, entonces cambiaríamos a ECDH y ECDSA; los estándares y las implementaciones existen y se implementan.

"Criptografía simétrica", es decir, funciones hash (MD5, SHA-256 ...), código de autenticación (HMAC, CBC-MAC ...), cifrado simétrico (AES, 3DES ...), generación de números aleatorios (RC4 ...) y actividades relacionadas, no se ven afectadas por la factorización. Para estos algoritmos, las claves son meros conjuntos de bits, sin ninguna estructura especial; no hay nada que factorizar.