¿Por qué son importantes los números primos para la seguridad informática?

Creo que una de las respuestas más relevantes (y ciertamente accesibles) a esta pregunta es que los números primos juegan un papel esencial en el algoritmo RSA (http://en.wikipedia.org/wiki/Rsa), que es uno de los más importantes. algoritmos ampliamente implementados para la transmisión segura de datos a través de Internet.

Básicamente, la seguridad de RSA se reduce a los siguientes hechos: es fácil probar números para primalidad, pero difícil, basado en el conocimiento actual, factorizar números enteros, especialmente si son productos de números primos grandes. Entonces, por ejemplo, un número entero del producto de dos números primos, cada uno de aproximadamente 1000 dígitos de largo (aproximadamente 2000 dígitos de largo) es extremadamente difícil de factorizar dado el conocimiento actual y el poder de cómputo, pero en realidad es fácil encontrar números primos de aproximadamente 1000 dígitos de largo.

Dicho todo esto, no existe un consenso claro sobre si la factorización entera es realmente un problema realmente difícil. Ciertamente, algunos matemáticos creen que la factorización de enteros en realidad podría tener una solución de tiempo polinomial, y probablemente no sea un problema de NP completo.

AlgoritmosCriptografíaNúmeros primos

Cómo explicar el uso e implementación de una variable estática en C a un principiante

¿Qué algoritmo se pregunta en la entrevista de Google?

¿Por qué muchos elementos utilizados en la función objetivo de un algoritmo de aprendizaje asumen todas las características centradas en cero y tienen una varianza en el mismo orden?

Cómo hacer un bot de chat usando Python implementando algoritmos de aprendizaje automático (como SVM, Naive Bayes, Random Forest, etc.)

¿Qué son los algoritmos de calibración para aplicaciones biomédicas en teléfonos inteligentes?

¿Qué solución se vuelve más barata en sitios web grandes, Google App Engine o Amazon EC2?

Para el cifrado-descifrado, es ideal tener una operación que sea muy fácil / eficiente de hacer de una manera, pero muy difícil / ineficiente de otra manera. ¡Los números primos proporcionan una de esas operaciones!

Es muy fácil (es decir, rápido) multiplicar dos o más primos dados para obtener el producto, un número (compuesto). Sin embargo, es laboriosamente difícil (es decir, consume mucho tiempo) factorizar un número dado en sus factores primos.

Tenga en cuenta que aquí nos estamos refiriendo a números realmente grandes, no a números pequeños que encontramos. Por ejemplo, es muy fácil (para una computadora) multiplicar dos primos de 100 dígitos para obtener un producto de 199 o 200 dígitos, en solo unos segundos. Pero dado solo ese producto, tomaría incluso la computadora más eficiente muchos años (tal vez, décadas o incluso siglos) para recuperar los dos factores principales.

Esto está en el corazón de muchos métodos de seguridad que involucran cifrado y descifrado. La operación fácil permite una fácil encriptación-desencriptación, mientras que la operación difícil asegura que los interceptores no puedan decodificar el mensaje encriptado, incluso si de alguna manera lo obtienen.

Nota: En esta respuesta, por “fácil”, queremos decir “rápido” para la computadora. Del mismo modo, ‘difícil’ solo significa ‘lento’.

Michael Hamburg

La respuesta a su pregunta está en su propia pregunta.

Los múltiplos de números primos son difíciles de factorizar. Esp, cuando los números primos son realmente grandes.

Lee mas:
http://en.wikipedia.org/wiki/RSA …
http://en.wikipedia.org/wiki/Int …

Por cierto, además del uso de la factorización de enteros , se han empleado muchas otras técnicas en el espacio de seguridad informática como las funciones de cifrado hash (MD5, SHA1, etc.) que no hacen uso del problema de factorización de enteros en absoluto. En cambio, los algoritmos mencionados anteriormente (y otros algoritmos basados en la red Feistel como DES / AES / IDEA) se basan en dos de las técnicas más populares en la criptografía: confusión (o sustitución) y difusión (o permutación y transposición).

Ver también:
http://en.wikipedia.org/wiki/Fei …
http://en.wikipedia.org/wiki/Mes …

Dicho esto, ya se ha demostrado que si la Computación Cuántica alguna vez se hiciera realidad, la mayoría de los algoritmos de criptología actuales podrían analizarse (dividirse / piratearse) en tiempo polinomial, en lugar del tiempo exponencial que lleva el Turing basados en diseños.

Lee mas:
http://en.wikipedia.org/wiki/Qua …

Editar:
Otro problema matemático computacionalmente difícil utilizado en criptografía es: Criptografía de curva elíptica. Para los protocolos basados en curvas elípticas, se supone que no es factible encontrar el logaritmo discreto de un elemento de curva elíptica aleatorio con respecto a un punto base conocido públicamente.

Referencia: http://en.wikipedia.org/wiki/Ell …

Michael Hamburg

More Interesting

Cómo demostrar que el problema del vendedor de viajes es NP-hard

Cómo implementar un hashing sensible a la localidad

¿Por qué es importante almacenar y organizar datos de manera eficiente dentro de estructuras específicas al programar?

¿Cuáles son las principales diferencias, con ejemplos, entre un algoritmo de aprendizaje profundo y un algoritmo de aprendizaje de refuerzo?

¿Hay algún problema para el cual se pruebe que no existe un algoritmo óptimo?

En Facebook, ¿qué determina los ocho amigos que se muestran en esa cuadrícula de imágenes de perfil 4 × 2?

¿Cuál es el algoritmo de clasificación más rápido con la menor complejidad?

¿Cuál es el futuro de la música generada por computadora?

Cómo mejorar las estructuras de datos y algoritmos