Función de trampilla

Herramienta criptográfica unidireccional

La idea de la función trampa. Una función trampa f con su trampa t se puede generar mediante un algoritmo Gen. f se puede calcular de manera eficiente, es decir, en tiempo polinomial probabilístico . Sin embargo, el cálculo de la inversa de f es generalmente difícil, a menos que se proporcione la trampa t . ^[1]

En informática teórica y criptografía , una función trampa es una función que es fácil de calcular en una dirección, pero difícil de calcular en la dirección opuesta (encontrar su inversa ) sin información especial, llamada "trampilla". Las funciones trampa son un caso especial de funciones unidireccionales y se utilizan ampliamente en criptografía de clave pública . ^[2]

En términos matemáticos, si f es una función de trampilla, entonces existe cierta información secreta t , tal que dada f ( x ) y t , es fácil calcular x . Consideremos 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 la cerradura. Sin embargo, para abrir el candado fácilmente se requiere el uso de la llave. Aquí la llave t es la trampilla y el candado es la función de la 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 tratar de dividir 6895601 por muchos números primos hasta encontrar la respuesta. Sin embargo, si a uno le dicen que 1931 es uno de los números, puede encontrar la respuesta ingresando "6895601 ÷ 1931" en cualquier calculadora. Este ejemplo no es una función trampa robusta - 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 primos mucho más grandes .

Las funciones de trampilla adquirieron importancia en criptografía a mediados de la década de 1970 con la publicación de técnicas de cifrado asimétrico (o de clave pública) por parte de 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 temprana fue utilizar esquemas basados ​​en el problema de suma de subconjuntos . Esto resultó ser bastante inadecuado.

A partir de 2004 ^[actualizar], las familias de funciones de trampilla más conocidas son las familias de funciones RSA y Rabin . Ambas se escriben como exponenciación módulo un número compuesto y ambas están relacionadas con el problema de la factorización prima .

No se sabe que las funciones relacionadas con la dureza del problema del logaritmo discreto (ya sea módulo un primo o en un grupo definido sobre una curva elíptica ) sean funciones trampa, porque no se conoce información de "trampa" sobre el grupo que permita el cálculo eficiente de logaritmos discretos.

Una puerta trampa en criptografía tiene el significado específico mencionado anteriormente y no debe confundirse con una puerta trasera (con frecuencia se usan indistintamente, lo cual es incorrecto). Una puerta trasera es un mecanismo deliberado que se agrega a un algoritmo criptográfico (por ejemplo, un algoritmo de generación de pares de claves, un algoritmo de firma digital, etc.) o a un sistema operativo, que permite que una o más partes no autorizadas eludan o subviertan la seguridad del sistema de alguna manera.

Definición

Una función trampa es una colección de funciones unidireccionales { f _k  : D _k → R _k } ( k ∈ K ), en la que todos K ​​, D _k , R _k son subconjuntos de cadenas binarias {0, 1} ^* , que satisfacen las siguientes condiciones:

• Existe un algoritmo de muestreo de tiempo polinomial probabilístico (PPT) Gen st Gen(1 ⁿ ) = ( k , t _k ) con k ∈ K ∩ {0, 1} ⁿ y t _k ∈ {0, 1} ^* satisface | t _k | < p ( n ), en el que p es algún polinomio. Cada t _k se denomina trampilla correspondiente a k . Cada trampilla se puede muestrear de manera eficiente.
• Dado un valor de entrada k , también existe un algoritmo PPT que genera x ∈ D _k . Es decir, cada D _k se puede muestrear de manera eficiente.
• Para cualquier k ∈ K , existe un algoritmo PPT que calcula correctamente f _k .
• Para cualquier k ∈ K , existe un algoritmo PPT A st para cualquier x ∈ D _k , sea y = A ( k , f _k ( x ), t _k ), y entonces tenemos f _k ( y ) = f _k ( x ). Es decir, dada la trampilla, es fácil invertir.
• Para cualquier k ∈ K , sin trampilla t _k , para cualquier algoritmo PPT, la probabilidad de invertir correctamente f _k (es decir, dado f _k ( x ), encontrar una preimagen x' tal que f _k ( x' ) = f _k ( x )) es insignificante. ^{[3] [4] [5]}

Si cada función en la colección anterior es una permutación unidireccional, entonces la colección también se denomina permutación de trampa . ^[6]

Ejemplos

En los dos ejemplos siguientes, siempre asumimos que es difícil factorizar un número compuesto grande (ver Factorización de enteros ).

Supuesto RSA

En este ejemplo, la inversa del módulo ( función totiente de Euler de ) es la trampa: ${\displaystyle d}$ ${\displaystyle e}$ ${\displaystyle \phi (n)}$ ${\displaystyle n}$

${\displaystyle f(x)=x^{e}\mod n.}$

Si se conoce la factorización de , entonces se puede calcular . Con esto se puede calcular la inversa de , y luego, dado , podemos encontrar . Su dureza se desprende del supuesto RSA. ^[7] ${\displaystyle n=pq}$ ${\displaystyle \phi (n)=(p-1)(q-1)}$ ${\displaystyle d}$ ${\displaystyle e}$ ${\displaystyle d=e^{-1}\mod {\phi (n)}}$ ${\displaystyle y=f(x)}$ ${\displaystyle x=y^{d}\mod n=x^{ed}\mod n=x\mod n}$

Supuesto de residuo cuadrático de Rabin

Sea un número compuesto grande tal que , donde y son primos grandes tales que , y se mantienen confidenciales para el adversario. El problema es calcular dados tales que . La trampa es la factorización de . Con la trampa, las soluciones de z se pueden dar como , donde . Consulte el teorema del resto chino para obtener más detalles. Tenga en cuenta que dados los primos y , podemos encontrar y . Aquí las condiciones y garantizan que las soluciones y pueden definirse bien. ^[8] ${\displaystyle n}$ ${\displaystyle n=pq}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}}$ ${\displaystyle z}$ ${\displaystyle a}$ ${\displaystyle a\equiv z^{2}{\pmod {n}}}$ ${\displaystyle n}$ ${\displaystyle cx+dy,cx-dy,-cx+dy,-cx-dy}$ ${\displaystyle a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle x\equiv a^{\frac {p+1}{4}}{\pmod {p}}}$ ${\displaystyle y\equiv a^{\frac {q+1}{4}}{\pmod {q}}}$ ${\displaystyle p\equiv 3{\pmod {4}}}$ ${\displaystyle q\equiv 3{\pmod {4}}}$ ${\displaystyle x}$ ${\displaystyle y}$

Véase también

• Función unidireccional

Notas

1. Ostrovsky, págs. 6-9
2. Bellare, M (junio de 1998). "Funciones de trampa de muchos a uno y su relación con los criptosistemas de clave pública". Avances en criptología — CRYPTO '98 . Apuntes de clase en informática. Vol. 1462. págs. 283–298. doi :10.1007/bfb0055735. ISBN 978-3-540-64892-5.S2CID215825522  .​
3. Notas del Pasista, definición 56.1
4. Notas de la conferencia de Goldwasser, definición 2.16
5. Ostrovsky, págs. 6-10, definición 11
6. Notas de Pass, def 56.1; def 7 de Dodis, conferencia 1.
7. Notas de la conferencia de Goldwasser, 2.3.2; notas de Lindell, pág. 17, Ej. 1.
8. Notas de la conferencia de Goldwasser, 2.3.4.

Referencias

• Diffie, W. ; Hellman, M. (1976), "Nuevas direcciones en criptografía" (PDF) , IEEE Transactions on Information Theory , 22 (6): 644–654, CiteSeerX  10.1.1.37.9720 , doi :10.1109/TIT.1976.1055638
• Pass, Rafael, Un curso de criptografía (PDF) , consultado el 27 de noviembre de 2015
• Goldwasser, Shafi, Notas de clase sobre criptografía (PDF) , consultado el 25 de noviembre de 2015
• Ostrovsky, Rafail, Fundamentos de criptografía (PDF) , consultado el 27 de noviembre de 2015
• Dodis, Yevgeniy, Introducción a la criptografía: notas de clase (otoño de 2008) , consultado el 17 de diciembre de 2015
• Lindell, Yehuda, Fundamentos de criptografía (PDF) , consultado el 17 de diciembre de 2015