¿Por qué son importantes los números primos en criptografía?
https://stackoverflow.com/questions/439870
-
22-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
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 hizo el concepto más claro.
Solución
La explicación más básica y general: la criptografía se trata de 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 trata mucho de 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 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 de la teoría de números.
Otros consejos
¿Simple? Sí.
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. Consulte funciones unidireccionales para obtener 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, es basado 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 solo tiene dos factores primos, y encontrar ellos.
No son tanto los números primos en sí 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 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 el cifrado. Aquí hay uno:
Desde 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 lo público como lo privado las claves se derivan de un par de grandes números primos según un matemática relativamente simple fórmula. En teoría, podría ser posible derivar la clave privada de la clave pública trabajando el fórmula al revés. Pero solo el producto de los grandes números primos es público, y factorizando números de eso el tamaño en primos es tan difícil que incluso los supercomputadores 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 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 de 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 el < a href = "http://en.wikipedia.org/wiki/Euler%27s_totient_function" rel = "noreferrer"> 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.
Más abstractamente, muchos protocolos criptográficos utilizan varias funciones de trampillas , funciones que son fáciles de calcular pero Difícil 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 Un viaje matemático en código . 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. Era 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 un 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 (~ podcast de 30 minutos, 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 criptista, 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 los primos se usan en criptografía, es difícil encontrar a alguien en este hilo que explique de manera fácil POR QUÉ se usan 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 puedan generar dos primos?
En este sitio hay una lista de 455,042,511 primos, donde el los 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 & # 8722; 1 que tiene 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 calcular en reversa dos números primos que se han multiplicado entre sí, tanto los criptógrafos como los matemáticos dirían que es lo suficientemente difícil ... . hoy.
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í, pero es la dificultad del problema de factorización principal
Suponga 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 principal en un tiempo aceptable usando una computadora cuántica. Por lo tanto, los algoritmos más nuevos en criptografía pueden no depender 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 usan principalmente en criptografía, ya que consume un tiempo considerable para determinar si un número dado es primo o no. Para el pirata informático, si algún algoritmo tarda mucho tiempo en descifrar el código, resulta inútil para ellos
