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

¿Simple? Sip.

Si multiplica dos números primos grandes, obtiene 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. Vea funciones unidireccionales para más información.

Adición: Sólo 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 en sí mismos como una clave privada. Cualquier operación realizada a datos que solo se pueden deshacer sabiendo que 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, lo que significa: tomar un número muy grande, dado que solo tiene dos factores primos, y encontrarlos.

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

Hay algunos buenos recursos para aumentar el cripto. Aquí hay uno:

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

De esa página:

En la clave pública más utilizada sistema de criptografía, inventado por Ron Rivest, Adi Shamir y Len Adleman en 1977, tanto el público como el privado las claves se derivan de un par de números primos según a matemática relativamente simple fórmula. En teoría, podría ser posible derivar la clave privada desde la clave pública trabajando el fórmula al revés. Pero solo el el producto de los números primos grandes es público, y teniendo en cuenta los números de que tamaño en primos es tan difícil que incluso los superordenadores más potentes de el mundo no puede romper un ordinario clave pública.

El libro de Bruce Schneier Criptografía aplicada es otro. Recomiendo encarecidamente ese libro; es divertido leer.

No son tanto los números primos mismos los que son importantes, sino los algoritmos que funcionan con números primos. En particular, encontrar los factores de un número (cualquier número).

Como usted sabe, cualquier número tiene al menos dos factores. Los números primos tienen la propiedad única en 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 científicos de la computación no saben cómo factorizar un número sin simplemente intentar todo lo posible combinado. Es decir, primero intenta 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) todos los números posibles entre 2 y ese número primo grande. Incluso en las computadoras más rápidas, tomará años (incluso siglos) para factorizar los tipos de números primos utilizados en criptografía.

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

Para ser un poco más concreto acerca de cómo RSA utiliza las propiedades de los números primos, el algoritmo RSA depende críticamente de el Teorema de Euler , que establece que para números primos relativos " 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? Para calcular la función totient de Euler de N de manera eficiente se requiere conocer la factorización primera 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 saber p y q, el cálculo de e es muy difícil.

De manera más abstracta, muchos protocolos criptográficos usan varias funciones trapdoor, 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 de trampilla (como la multiplicación de números primos grandes), y los números primos son absolutamente centrales para la teoría de números.

Yo sugeriría el libro Un Viaje Matemático En Código. El libro tiene una agradable sensación con los pies en la tierra, lo cual es sorprendente, ya que se trata de criptografía. El libro resume el viaje de Sarah Flannery de aprender rompecabezas cuando era niña a crear el algoritmo Cayley-Purser (CP) a la edad de 16 años. Da una explicación increíblemente detallada de las funciones de una vía, la teoría de números y los números primos y cómo se relacionan con la criptografía.

¿Qué hace que este libro sea aún más específico para tu pregunta es que Sarah intentó implementar un nuevo algoritmo de clave pública usando matrix. Fue mucho más rápido que usando números primos pero se encontró un agujero de bucle que podría explotarlo. Resulta que su algoritmo era mejor usado como un mecanismo de encriptación 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 individuos muy inteligentes.

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

No soy un matemático o críptico, así que aquí hay una observación externa en términos sencillos (no hay ecuaciones de fantasía, lo siento).

Todo este hilo está lleno de explicaciones sobre CÓMO los primos se usan en criptografía, es difícil encontrar a alguien en este hilo explicando de una manera fácil POR QUÉ los primos se usan ... lo más probable es que todo el mundo da ese conocimiento por sentado.

Solo mirando el problema desde el exterior puede generar una reacción como; pero si utilice las sumas de dos primos, ¿por qué no crear una lista de todas las sumas posibles que cualquiera de dos primos puede generar?

En este sitio hay una lista de 455,042,511 primos, donde los primos más altos 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 primos conocidos y mucho menos todos sus posibles sumas. Es más fácil tomar un número y comprobar si es primo.

Calcular grandes números primos en sí mismo es una tarea monumental, por lo que calcular a la inversados números primos que se han multiplicado entre sí, ambos criptógrafos y matemáticos dirían que es suficientemente difícil... hoy.

Los algoritmos criptográficos generalmente se basan para su seguridad en tener un "problema difícil". La mayoría de los algoritmos modernos parecen utilizar 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, es la correcta, no alguna otra respuesta que da el mismo resultado.

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

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

Por cierto, hay un documento publicado {[10] } sobre el algoritmo que puede "resolver" este problema de factorización primaria en un tiempo aceptable utilizando cuántica ordenador. Así que los algoritmos más nuevos en criptografía pueden no confiar en esta "dificultad" de factorización primaria más cuando la computadora cuántica viene a la ciudad:)

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

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