encryption - online - descifrar mensaje rsa

¿De qué manera la capacidad de factorizar grandes números determina la seguridad de los populares algoritmos de cifrado? (4)

¿De qué manera la seguridad del algoritmo de encriptación depende de factorizar grandes cantidades?

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?

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

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 existen dos categorías principales de cifras, simétricas (clave secreta) y clave pública (que usa un par de claves pública / privada).

Dentro de cada categoría, encontrará tamaños de clave relativamente cercanos. 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, calculando logaritmos discretos.

Debido a las propiedades de los pares de claves públicas y privadas, el espacio de búsqueda se limita a factores de números primos grandes, que se vuelven increíblemente escasos, por lo que tiene sentido intentar ser mucho más inteligente que simplemente tratar de factorizar cada número muy grande.

Mientras que con cifrados simétricos como AES, RC6, RC4, Twofish, DES y Triple-DES, estos algoritmos utilizan una clave aleatoria de una longitud de bit dada. 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, intente con 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 ignorando la Computación Cuántica (teórica y práctica), principalmente porque a) No puedo dar una respuesta sólida, yb) representa un gran cambio de paradigma que hace que muchas matemáticas aplicadas y la informática de la complejidad computacional se vuelvan potencialmente irrelevantes, esa comprensión básica sigue siendo un objetivo móvil. Ah, y la mayoría de mis enemigos aún no tienen una computadora cuántica. :)

Espero que eso explique la diferencia general entre los dos tipos de sistemas criptográficos, como RSA y AES.

Barra lateral: la criptografía es un tema rico y complejo, donde los conceptos básicos pueden ser lo suficientemente simples para comprender e incluso escribir una implementación ingenua ("libro de texto"), las complejas sutilezas de una implementación segura lo hacen mejor para los programadores que no son expertos en criptografía. utilice 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.

AES es muy diferente, AES crea un SPN, la 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.

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 anotado n ) que es un producto de dos (o más) factores primarios distintos. Factoring n revela la clave privada. Factorizar 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 pocas pistas 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.

Hay 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 numérica, 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 de logaritmo discretos se pueden aplicar a otros grupos, siendo las curvas elípticas más populares. 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 las 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.

RSA, el criptoalgoritmo, 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 sobre las respuestas de Yahoo donde alguien ha dado algunos detalles: http://answers.yahoo.com/question/index?qid=20070125183948AALJ40l

Se basa en algunos hechos:

n=pq 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 difícil factorizar números grandes, sino factorizar dos números grandes cuyos únicos factores son en sí mismos grandes números primos, porque encontrar esos números primos es difícil.

Una búsqueda rápida a través de mis marcadores me da esto: las agallas matemáticas del cifrado rsa 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 gran número 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 que 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 algoritmo de divisor común más grande de euclides, la 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 un buen artículo sobre AES para alto nivel con un buen enlace que le muestra cómo funciona: vea here y here . Me gusta particularmente el último enlace.