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

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’.

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 …