¿Por qué son importantes los números primos en criptografía?

Una cosa que siempre me sorprende como no criptógrafo: ¿por qué es tan importante usar números primos? ¿Qué los hace tan especiales en criptografía?

¿Alguien tiene una breve explicación simple ? (Soy consciente de que hay muchos iniciadores y que la Criptografía Aplicada es la Biblia, pero como dije: no estoy buscando implementar mi propio algoritmo criptográfico, y las cosas que encontré solo hicieron explotar mi cerebro: no hay 10 páginas de fórmulas matemáticas Por favor :))

Gracias por todas las respuestas Acepté el que me dejó el concepto más claro.

La explicación más básica y general: la criptografía tiene que ver con la teoría de números , y todos los números enteros (excepto 0 y 1) están compuestos por números primos, por lo que se trata mucho de números primos en la teoría de números.

Más específicamente, algunos algoritmos criptográficos importantes como el RSA dependen de manera crítica del hecho de que la factorización prima de grandes números lleva mucho tiempo. Básicamente, tiene una "clave pública" que consiste en un producto de dos números primos grandes utilizados para cifrar un mensaje, y una "clave secreta" que consiste en esos dos números primos utilizados para descifrar el mensaje. Puede hacer pública la clave pública, y todos pueden usarla para cifrar mensajes, pero solo usted conoce los factores primos y puede descifrar los mensajes. Todos los demás tendrían que factorizar el número, lo que lleva demasiado tiempo para ser práctico, dado el estado actual del arte de la teoría de números.

¿Sencillo? Sip.

Si multiplica dos números primos grandes, obtendrá un número no primo enorme con solo dos factores primos (grandes).

Factorizar ese número es una operación no trivial, y ese hecho es la fuente de muchos algoritmos criptográficos. Ver funciones unidireccionales para más información.

Anexo: Solo un poco más de explicación. El producto de los dos números primos se puede utilizar como una clave pública, mientras que los primos mismos como una clave privada. Cualquier operación realizada a los datos que solo se pueden deshacer al conocer uno de los dos factores no será trivial para desencriptar.

Aquí hay un ejemplo muy simple y común.

El algoritmo de cifrado RSA, que se usa comúnmente en sitios web de comercio seguro, se basa en el hecho de que es fácil tomar dos números primos (muy grandes) y multiplicarlos, mientras que es extremadamente difícil hacer lo contrario, es decir: tomar un número muy grande, dado que tiene solo dos factores primos, y encontrarlos.

Lo importante no son los números primos, sino los algoritmos que funcionan con números primos. En particular, encontrar los factores de un número (cualquier número).

Como sabes, cualquier número tiene al menos dos factores. Los números primos tienen la propiedad única de que tienen exactamente dos factores: 1 y ellos mismos.

La razón por la que la factorización es tan importante es que los matemáticos y los informáticos no saben cómo factorizar un número sin simplemente probar todas las combinaciones posibles. Es decir, primero intente dividir por 2, luego por 3, luego por 4, y así sucesivamente. Si intentas factorizar un número primo, especialmente uno muy grande, tendrás que probar (esencialmente) cada número posible entre 2 y ese número primo grande. Incluso en las computadoras más rápidas, llevará años (incluso siglos) factorizar los tipos de números primos utilizados en la criptografía.

Es el hecho de que no sabemos cómo factorizar eficientemente un gran número lo que da fuerza a los algoritmos criptográficos. Si, algún día, alguien descubre cómo hacerlo, todos los algoritmos criptográficos que utilizamos actualmente quedarán obsoletos. Esto sigue siendo un área abierta de investigación.

Porque nadie conoce un algoritmo rápido para factorizar un número entero en sus factores primos. Sin embargo, es muy fácil verificar si un conjunto de factores primos se multiplica a un número entero determinado.

Hay algunos buenos recursos para aumentar la criptografía. Aquí hay uno:

• http://research.microsoft.com/en-us/groups/crypto/firstcrypto.aspx

Desde esa página:

En el sistema de criptografía de clave pública más comúnmente utilizado, inventado por Ron Rivest, Adi Shamir y Len Adleman en 1977, tanto las claves públicas como las privadas se derivan de un par de números primos grandes de acuerdo con una fórmula matemática relativamente simple. En teoría, podría ser posible derivar la clave privada de la clave pública trabajando la fórmula al revés. Pero solo el producto de los números primos grandes es público, y factorizar números de ese tamaño en números primos es tan difícil que incluso las supercomputadoras más poderosas del mundo no pueden romper una clave pública ordinaria.

El libro de Bruce Schneier, Criptografía Aplicada, es otro. Recomiendo mucho ese libro; Es divertido leer.

Para ser un poco más concreto acerca de cómo RSA usa las propiedades de los números primos, el algoritmo RSA depende críticamente del teorema de Euler , que establece que para números relativamente primos "a" y "N", a ^ e es congruente con 1 módulo N, donde e es la función totient de Euler de N.

¿Dónde entran los números primos en eso? Calcular la función totient de Euler de N de manera eficiente requiere conocer la factorización prima de N. En el caso del algoritmo RSA, donde N = pq para algunos primos "p" y "q", entonces e = (p - 1) (q - 1) = N - p - q + 1. Pero sin conocer pyq, el cálculo de e es muy difícil.

De manera más abstracta, muchos protocolos criptográficos utilizan diversas funciones de trampillas , funciones que son fáciles de calcular pero difíciles de invertir. La teoría de números es una rica fuente de tales funciones trampa (como la multiplicación de números primos grandes), y los números primos son absolutamente centrales para la teoría de números.

Sugeriría el libro A Mathematical Journey In Code . El libro tiene una sensación agradable, lo cual es sorprendente, ya que se trata de criptografía. El libro resume el viaje de Sarah Flannery desde el aprendizaje de los acertijos cuando era niño hasta la creación del algoritmo Cayley-Purser (CP) a la edad de 16 años. Ofrece una explicación increíblemente detallada de funciones unidireccionales, teoría de números y números primos y cómo se relacionan con criptografía.

Lo que hace que este libro sea aún más específico para su pregunta es que Sarah intentó implementar un nuevo algoritmo de clave pública utilizando matrices. Fue mucho más rápido que usar números primos, pero se encontró un agujero de bucle que podría explotarlo. Resulta que su algoritmo se usó mejor como mecanismo de cifrado privado. El libro es un gran testimonio del uso de números primos para el cifrado, ya que ha resistido la prueba del tiempo y los desafíos de las personas muy inteligentes.

Un recurso más para ti. Seguridad ahora! El episodio 30 (~ 30 minutos de podcast, enlace a la transcripción) habla sobre problemas de criptografía y explica por qué los números primos son importantes.

No soy matemático ni críptico, así que aquí hay una observación externa en términos simples (sin ecuaciones elegantes, lo siento).

Todo este hilo está lleno de explicaciones sobre CÓMO se usan los primos en la criptografía, es difícil encontrar a alguien en este hilo que explique de una manera fácil POR QUÉ se usan los primos ... probablemente porque todos dan ese conocimiento por sentado.

Solo mirar el problema desde afuera puede generar una reacción como; pero si usan las sumas de dos primos, ¿por qué no crear una lista de todas las sumas posibles que pueden generar dos primos?

En este sitio hay una lista de 455,042,511 primos, donde el primo más alto es 9,987,500,000 ( 10 dígitos).

El primo más grande conocido (a partir de febrero de 2015) es 2 a la potencia de 257,885,161 - 1, que es 17,425,170 dígitos.

Esto significa que no tiene sentido mantener una lista de todos los números primos conocidos y mucho menos todas sus sumas posibles. Es más fácil tomar un número y verificar si es primo.

Calcular grandes números primos en sí mismo es una tarea monumental, por lo que el cálculo inverso de dos números primos que se han multiplicado entre sí, tanto los criptógrafos como los matemáticos dirían que es bastante difícil ... hoy en día.

Los algoritmos criptográficos generalmente dependen de su seguridad para tener un "problema difícil". La mayoría de los algoritmos modernos parecen usar la factorización de números muy grandes como su problema difícil: si multiplica dos números grandes juntos, calcular sus factores es "difícil" (es decir, consume mucho tiempo). Si esos dos números son números primos, entonces solo hay una respuesta, lo que lo hace aún más difícil, y también garantiza que cuando encuentre la respuesta, sea la correcta, no alguna otra respuesta que simplemente dé el mismo resultado.

Creo que lo importante en la criptografía no son los primos en sí, sino la dificultad del problema de factorización primo

Supongamos que tiene un número entero muy grande que se sabe que es producto de dos primos myn, no es fácil encontrar lo que son myn. Algoritmo como RSA depende de este hecho.

Por cierto, hay un artículo publicado sobre algoritmos que puede "resolver" este problema de factorización principal en un tiempo aceptable usando una computadora cuántica. Por lo tanto, es posible que los algoritmos más nuevos en criptografía ya no dependan de esta "dificultad" de factorización principal cuando la computadora cuántica llega a la ciudad :)

Porque los algoritmos de factorización se aceleran considerablemente con cada factor encontrado. Hacer que ambas claves privadas sean primarias garantiza que el primer factor encontrado también será el último. Idealmente, ambas claves privadas también tendrán un valor casi igual, ya que solo importa la fuerza de la clave más débil.

Los números primos se utilizan principalmente en criptografía, ya que consume un tiempo considerable para determinar si un número dado es primo o no. Para el hacker, si algún algoritmo toma mucho tiempo para descifrar el código, se vuelve inútil para ellos.