¿Qué es un ejemplo simple de una función de trampilla?

5

El otro día intenté explicarle la criptografía de clave pública a un lego, que requiere una explicación de la función de la trampilla. Si bien sé en principio qué es una función de trampilla, debo admitir que las propiedades matemáticas específicas detrás del problema de la factorización principal y el problema de ECC están fuera de mi alcance.

¿Existe un ejemplo simple que pueda usarse para ejemplificar una función de trampilla? Estaba pensando en cuadrados y raíces cuadradas, ya que los cuadrados se calculan fácilmente pero las raíces cuadradas, en cierto modo, requieren fuerza bruta guiada.

    
pregunta John Wu 25.09.2015 - 19:49
fuente

1 respuesta

6

La respuesta más básica es simplemente factorización. Es fácil calcular el producto de dos números primos. Tomaría un minuto o dos, pero puede calcular en lápiz y papel que 1093 * 1039 = 1,135,627. Ir por el otro lado es mucho más difícil. Si le diera el número 1,135,627 y le preguntara cuáles son los dos números que multipliqué para obtener ese número, podría llevarle horas de factorización de prueba con lápiz y papel para factorizarlo. Para hacerlo rápidamente necesitarías una computadora.

Pero si te pidiera que factorizaras 15, contestarías rápidamente 5 y 3. Así que la dificultad de la factorización aumenta a medida que los números primos aumentan de valor. Si los dos números primos se eligen lo suficientemente grande, incluso una computadora, o incluso miles de computadoras no son suficientes para llegar a los dos factores.

    
respondido por el Steve Sether 25.09.2015 - 20:12
fuente

Lea otras preguntas en las etiquetas