cryptography - números - no entiendo los numeros primos
¿Por qué los primos son importantes en la criptografía? (14)
Una cosa que siempre me sorprende como un criptógrafo: ¿Por qué es tan importante usar números primos? ¿Qué los hace tan especiales en criptografía?
¿Alguien tiene una explicación corta simple ? (Soy consciente de que hay muchos iniciadores y que Applied Cryptography es la Biblia, pero como dije: no estoy buscando implementar mi propio algoritmo criptográfico, y las cosas que encontré hicieron que mi cerebro explotara: no hay 10 páginas de fórmulas matemáticas Por favor :))
Gracias por todas las respuestas. He aceptado la que me hizo el concepto más claro.
¿Sencillo? Sip.
Si multiplicas dos números primos grandes, obtienes un gran número no primo con solo dos (grandes) factores primos.
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.
Adición: Solo un poco más de explicación. El producto de los dos números primos se puede usar como una clave pública, mientras que los primos se pueden usar como una clave privada. Cualquier operación realizada a datos que solo pueden deshacerse conociendo uno de los dos factores será no trivial para descifrar.
Aquí hay un ejemplo muy simple y común.
El algoritmo de cifrado RSA que se utiliza comúnmente en los 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 una número muy grande, dado que solo tiene dos factores primos, y encuéntrelos.
Creo que lo importante en la criptografía no son primos, pero es la dificultad del problema de la factorización prima
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 algoritmo que puede "resolver" este problema de factorización prima en tiempo aceptable usando una computadora cuántica. Así que los algoritmos más nuevos en criptografía pueden no depender más de esta "dificultad" de factorización prima cuando la computadora cuántica llega a la ciudad :)
Debido a que los algoritmos de factorización se aceleran considerablemente con cada factor encontrado. Al hacer que ambas claves privadas prime, 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.
Hay algunos buenos recursos para aumentar la criptografía. Aquí hay uno:
Desde esa página:
En el sistema de criptografía de clave pública más utilizado, inventado por Ron Rivest, Adi Shamir y Len Adleman en 1977, las claves pública y privada se derivan de un par de grandes números primos 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 haciendo retroceder la fórmula. Pero solo el producto de los números primos grandes es público, y el factorizar números de ese tamaño en números primos es tan difícil que incluso los supercomputadores más poderosos del mundo no pueden romper una clave pública ordinaria.
El libro de Bruce Schneier Applied Cryptography es otro. Recomiendo mucho ese libro; es lectura divertida
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 formados por números primos, por lo que se ocupan mucho de los números primos en teoría de números.
Más específicamente, algunos algoritmos criptográficos importantes como RSA dependen críticamente 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 encriptar un mensaje, y una "clave secreta" que consiste en esos dos números primos utilizados para descifrar el mensaje. Puede hacer que la clave pública sea pública y todos pueden usarla para encriptar los mensajes, pero solo usted conoce los factores principales 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 de la técnica de la teoría de números.
Los algoritmos criptográficos generalmente confían en su seguridad al 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 se multiplican dos números grandes, calcular sus factores es "difícil" (es decir, requiere mucho tiempo). Si esos dos números son números primos, entonces hay una sola respuesta, lo que lo hace aún más difícil, y también garantiza que cuando encuentre la respuesta, es la correcta, no otra respuesta que da el mismo resultado.
Los números primos se utilizan principalmente en la criptografía, ya que consume un tiempo considerable para determinar si un número dado es o no el número primo. Para el pirata informático, si un algoritmo tarda mucho tiempo en descifrar el código, se vuelve inútil para ellos
No son tanto los números primos en sí los que son importantes, sino los algoritmos que funcionan con los 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 el sentido de que tienen exactamente dos factores: 1 y ellos mismos.
La razón por la que el factoring es tan importante es que los matemáticos y los informáticos no saben cómo factorizar un número sin simplemente intentar 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 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 quedarán obsoletos. Esto sigue siendo un área abierta de investigación.
No soy matemático ni criptólogo, así que aquí hay una observación externa en términos sencillos (sin ecuaciones extravagantes, 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 ... muy probablemente porque todos dan por hecho ese conocimiento.
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 dos primos puedan generar?
En este site hay una lista de 455,042,511 números primos, donde los números primos más altos son 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 el mejor.
Cálculo de grandes números primos en sí mismo es una tarea monumental, por lo que revertir el cálculo 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.
Para ser un poco más concreto sobre 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 los números primos relativamente "a" y "N", a ^ e es congruente con 1 modulo N, donde e es la función totient de Euler de N.
¿Dónde entran los números primos? Para calcular la función totient de Euler de N de manera eficiente, se 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 forma más abstracta, muchos protocolos criptográficos utilizan varias funciones de puerta de trampa , funciones que son fáciles de calcular pero difíciles de invertir. La teoría de números es una fuente rica de tales funciones de puerta de trampas (como la multiplicación de grandes números primos), y los números primos son absolutamente centrales para la teoría de números.
Porque nadie conoce un algoritmo rápido para factorizar un entero en sus factores primos. Sin embargo, es muy fácil verificar si un conjunto de factores primarios se multiplica a un determinado entero.
Sugeriría el libro Un viaje matemático en el código . El libro tiene un agradable sentido de la tierra, lo cual es sorprendente, ya que se trata de la criptografía. El libro resume el recorrido de Sarah Flannery desde el aprendizaje de rompecabezas 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 de una vía, 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 la matriz. Fue mucho más rápido que utilizar números primos, pero se encontró un agujero en el 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 individuos 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 primos son importantes.