Función de trampilla

En informática teórica y criptografía , una función de puerta trasera es una función fácil de calcular en una dirección, pero difícil de calcular en la dirección opuesta (calcular su inversa ) sin información especial, denominada "puerta trasera". Las funciones de puerta trasera 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 puerta trasera, entonces existe alguna información secreta t tal que, dados 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, simplemente empujando el grillete hacia el mecanismo de cierre. Sin embargo, para abrir el candado fácilmente, se requiere usar la llave. Aquí, la llave t es la puerta trasera y el candado es la función de puerta trasera.

Un ejemplo de una sencilla trampa matemática 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 muchos números primos hasta encontrar la respuesta. Sin embargo, si se nos dice que 1931 es uno de esos números, podemos encontrar la respuesta introduciendo "6895601 ÷ 1931" en cualquier calculadora. Este ejemplo no es una función de trampa robusta (las computadoras modernas pueden adivinar todas las posibles respuestas en un segundo), pero este problema de ejemplo podría mejorarse utilizando el producto de dos números primos mucho mayores .

Las funciones de puerta trasera cobraron protagonismo 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 Diffie , Hellman y Merkle . De hecho, Diffie y Hellman (1976) acuñaron el término. Se propusieron varias clases de funciones, y pronto se hizo evidente que las funciones de puerta trasera 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 la suma de subconjuntos . Esto demostró ser rápidamente inadecuado.

A partir de 2004Las funciones candidatas (familias) de puerta trasera 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 dificultad del problema del logaritmo discreto (ya sea módulo un número primo o en un grupo definido sobre una curva elíptica ) sean funciones trampa, porque no se conoce ninguna información de "puerta trasera" sobre el grupo que permita el cálculo eficiente de logaritmos discretos.

En criptografía, una trampilla tiene el significado específico mencionado anteriormente y no debe confundirse con una puerta trasera (términos que se usan frecuentemente indistintamente, lo cual es incorrecto). Una puerta trasera es un mecanismo intencional 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, por ejemplo, que permite a una o más partes no autorizadas eludir o vulnerar la seguridad del sistema de alguna manera.

Definición

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

Existe un algoritmo de muestreo probabilístico de tiempo polinomial (PPT) Gen st Gen(1 ⁿ ) = ( k , t _k ) con k ∈ K ∩ {0, 1} ⁿ y t _k ∈ {0, 1} ^* satisface | t _k | < p ( n ), donde p es algún polinomio. Cada t _k se llama la puerta trasera correspondiente a k . Cada puerta trasera puede ser muestreada eficientemente.
Dado un input k , también existe un algoritmo PPT que produce x ∈ D _k . Es decir, cada D _k puede ser muestreado 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 puerta trasera 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 despreciable. ^{[ 3 ]}^{[ 4 ]}^{[ 5 ]}

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

Ejemplos

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

Suposición RSA

En este ejemplo, la inversa $d$ de $e$ módulo $\phi (n)$ ( Función totiente de Euler de $n$ ) es la trampilla:

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

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

Suposición de residuo cuadrático de Rabin

Dejar $n$ sea un número compuesto grande tal que $n=pq$ , dónde $p$ y $q$ son primos grandes tales que $p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}$ y se mantuvo confidencial para el adversario. El problema es calcular $z$ dado $a$ de tal manera que $a\equiv z^{2}{\pmod {n}}$ . La trampilla es la factorización de $n$ . Con la trampilla, las soluciones de z se pueden dar como $cx+dy,cx-dy,-cx+dy,-cx-dy$ , dónde $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}}$ Consulte el teorema chino del resto para obtener más detalles. Tenga en cuenta que dados los números primos $p$ y $q$ , podemos encontrar $x\equiv a^{\frac {p+1}{4}}{\pmod {p}}$ y $y\equiv a^{\frac {q+1}{4}}{\pmod {q}}$ Aquí están las condiciones $p\equiv 3{\pmod {4}}$ y $q\equiv 3{\pmod {4}}$ garantizar que las soluciones $x$ y $y$ puede estar bien definido. ^{[ 8 ]}

Véase también

Función unidireccional

Notas

↑ Ostrovsky, págs. 6–9
↑ Bellare, M (junio de 1998). «Funciones de puerta trasera de muchos a uno y su relación con los criptosistemas de clave pública». Avances en criptología — CRYPTO '98 . Notas de clase en ciencias de la computación. Vol. 1462. págs. 283–298 . doi : 10.1007/bfb0055735 . ISBN 978-3-540-64892-5. S2CID 215825522 .
↑ Notas de Pass, def. 56.1
↑ Apuntes de clase de Goldwasser, definición 2.16
↑ Ostrovsky, págs. 6–10, def. 11
↑ Notas de Pass, def. 56.1; def. 7 de Dodis, lección 1.
↑ Apuntes de clase de Goldwasser, 2.3.2; Apuntes de Lindell, pág. 17, Ej. 1.
↑ Apuntes de clase 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, Apuntes de clase sobre criptografía (PDF) , consultado el 25 de noviembre de 2015.
Ostrovsky, Rafail, Fundamentos de la criptografía (PDF) , consultado el 27 de noviembre de 2015.
Dodis, Yevgeniy, Apuntes de clase de Introducción a la Criptografía (Otoño de 2008) , consultado el 17 de diciembre de 2015.
Lindell, Yehuda, Fundamentos de la criptografía (PDF) , consultado el 17 de diciembre de 2015.

[1] Ostrovsky, págs. 6–9

[2] Bellare, M (junio de 1998). «Funciones de puerta trasera de muchos a uno y su relación con los criptosistemas de clave pública». Avances en criptología — CRYPTO '98 . Notas de clase en ciencias de la computación. Vol. 1462. págs. 283–298 . doi : 10.1007/bfb0055735 . ISBN 978-3-540-64892-5. S2CID 215825522 .

[3] Notas de Pass, def. 56.1

[4] Apuntes de clase de Goldwasser, definición 2.16

[5] Ostrovsky, págs. 6–10, def. 11

[6] Notas de Pass, def. 56.1; def. 7 de Dodis, lección 1.

[7] Apuntes de clase de Goldwasser, 2.3.2; Apuntes de Lindell, pág. 17, Ej. 1.

[8] Apuntes de clase de Goldwasser, 2.3.4.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]