Función de trampilla
Una función de trampilla es una función que es fácil de calcular en una dirección, pero difícil de calcular en la dirección opuesta (encontrando su inversa ) sin información especial, llamada "trampilla". Las funciones de trampilla se utilizan ampliamente en criptografía . [2]
En términos matemáticos, si f es una función de trampilla, entonces existe alguna información secreta t , tal que dados f ( x ) yt , es fácil calcular x . Considere un candado y su llave. Es trivial cambiar el candado de abierto a cerrado sin usar la llave, empujando el grillete en el mecanismo de bloqueo. Sin embargo, para abrir el candado con facilidad, es necesario utilizar la llave. Aquí la llave es la trampilla y el candado es la función de trampilla.
Un ejemplo de una trampa matemática simple es "6895601 es el producto de dos números primos. ¿Cuáles son esos números?" Una solución típica de " fuerza bruta " sería intentar dividir 6895601 entre varios números primos hasta encontrar la respuesta. Sin embargo, si se le dice a uno que 1931 es uno de los números, se puede encontrar la respuesta ingresando "6895601 ÷ 1931" en cualquier calculadora. Este ejemplo no es una función robusta de trampilla: las computadoras modernas pueden adivinar todas las respuestas posibles en un segundo, pero este problema de muestra podría mejorarse utilizando el producto de dos números primos mucho más grandes .
Las funciones de trampilla cobraron importancia en la criptografía a mediados de la década de 1970 con la publicación de técnicas de cifrado asimétricas (o de clave pública) por Diffie , Hellman y Merkle . De hecho, Diffie y Hellman (1976) acuñaron el término. Se habían propuesto varias clases de funciones y pronto se hizo evidente que las funciones de trampilla son más difíciles de encontrar de lo que se pensaba inicialmente. Por ejemplo, una sugerencia inicial fue utilizar esquemas basados en el problema de la suma de subconjuntos . Esto resultó, bastante rápido, no ser adecuado.
A partir de 2004 [actualizar], los candidatos de función (familia) trampilla más conocidos son las familias de funciones RSA y Rabin . Ambos se escriben como exponenciación módulo un número compuesto, y ambos están relacionados con el problema de la factorización prima .
Las funciones relacionadas con la dureza del problema del logaritmo discreto (ya sea módulo a primo o en un grupo definido sobre una curva elíptica ) no se conocen como funciones de trampilla, porque no hay información conocida de "trampilla" sobre el grupo que permita el cálculo eficiente. de logaritmos discretos.
