¿Cómo se pueden usar los números primos en el cifrado?

El cifrado es uno de los principales usos de los números primos. El algoritmo RSA completo se puede encontrar aquí: RSA (algoritmo).

Simplemente le explicaría la idea de por qué usamos números primos para el cifrado.
Como sabrás, los números primos carecen de patrón, es decir, considera los números pares, impares y primos.

• Si digo que e = 1000000008 es el número par k, entonces puede decir k = e / 2.
• Si digo que o = 1000000009 es el número impar número k, entonces puede decir k = (o + 1) / 2.
• Ahora, si digo que p = 1000000007 es el kth número primo, ¿puede decirme el valor de k sin pasar realmente por encima de todos los números primos? – NO.

Este es aún un número muy pequeño donde el valor de k se puede determinar con la ayuda de la computadora (Tamiz de Eratóstenes), pero piense en un número de 100 a 1000 dígitos o mucho más grande donde es computacionalmente imposible (en la actualidad) sin invertir años. .

Debido a esta propiedad de los números primos, todavía no se ha encontrado ningún método de tiempo polinómico para factorizar números enteros grandes en números primos en una computadora clásica (pero no se ha demostrado que no exista) y la seguridad del cifrado RSA se basa en este hecho. Romper el cifrado RSA es tan difícil como factorizar, que es una pregunta abierta conocida como el problema RSA.
Si alguna vez se desarrolla un método eficiente, amenazaría la seguridad actual o eventual de los criptosistemas basados ​​en RSA.

Como dice PositiveCat, el intercambio de claves Diffie-Hellman y el cifrado de clave pública RSA y los esquemas de firma DSA se basan en el problema de logaritmo discreto.

Es bastante rápido y fácil realizar el módulo de exponenciación de un número primo, pero no existe un algoritmo fácil para realizar la transformación inversa, el logaritmo discreto.

ok – mentí. RSA se basa en la dificultad de factorizar el producto de grandes números primos, no en logaritmos discretos.

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

Discreto problema logarith.

Básicamente, puede multiplicar a primos juntos y puede estar seguro de que el resultado solo será divisible por uno de esos dos primos. Multiplicarlos es fácil, pero factorizarlos es difícil y requiere mucho tiempo, eso es lo que llamamos una función unidireccional.