Función unidireccional

Problemas no resueltos en Ciencias de la Computación : '' ¿Existen funciones unidireccionales?''

Una función unidireccional es una función matemática que es fácil de evaluar para cualquier valor de entrada, pero difícil de encontrar el argumento dado el valor de la función. Aquí, "fácil" y "difícil" deben entenderse en términos de la teoría de la complejidad computacional . La brecha entre la complejidad de las transformaciones hacia adelante y hacia atrás determina la eficiencia criptográfica de una función unidireccional. La no inyectividad de una función no es condición suficiente para llamarla unidireccional. Las funciones unidireccionales también se pueden llamar difíciles de revertir o irreversibles.

La existencia de funciones unidireccionales aún no ha sido probada. Su existencia probará que las clases de complejidad P y NP no son iguales , resolviendo una serie de problemas en informática teórica en el camino . Moderno[ ¿cuándo? ] la criptografía asimétrica se basa en la suposición de que existen funciones unidireccionales.

Las funciones unidireccionales son herramientas fundamentales en criptografía , identificación personal, autenticación y otras áreas de seguridad de datos. Aunque la existencia de tales funciones es todavía una hipótesis no comprobada, existen varios contendientes que han resistido décadas de escrutinio. Muchos de ellos forman parte integral de la mayoría de los sistemas de telecomunicaciones , así como de los sistemas de comercio electrónico y banca por Internet de todo el mundo.

Definición

Sea el conjunto de todas las cadenas binarias de longitud n. Una función es una función unidireccional si se calcula eficientemente en tiempo polinomial en una máquina de Turing determinista , pero no existe una máquina de Turing probabilística polinomial que invierta esta función con una probabilidad más que exponencialmente pequeña. Es decir, para cualquier máquina de polinomios probabilísticos , para cualquier polinomio y suficientemente grande : $\{0,1\}^{n}$ $f:\{0,1\}^{*}\flecha derecha \{0,1\}^{*}$ $METRO$ $p(n)$ $n\en \mathbb {N}$

Pr[M(f(m))\en f^{{-1}}(m)]<1/p(n)

donde la fila se elige al azar en el conjunto de acuerdo con la ley de distribución uniforme. El tiempo de funcionamiento de la máquina está limitado por un polinomio en la longitud de la preimagen deseada [1] . $metro$ $\{0,1\}^{n}$ $METRO$

Existencia

No se ha probado la existencia de funciones unidireccionales. Si f es una función unidireccional, entonces encontrar la función inversa es difícil (por definición) pero fácilmente verificable (evaluando f en ella). Así, de la existencia de una función unidireccional se sigue que P ≠ NP. Sin embargo, no se sabe si P ≠ NP implica la existencia de funciones unidireccionales.

La existencia de funciones unidireccionales implicará la existencia de muchos otros objetos criptográficos útiles, entre ellos:

generadores de números pseudoaleatorios ;
si hay una función unidireccional con un bit duro , entonces hay un patrón de bits de compromiso ;
familias de funciones pseudoaleatorias ;
inserciones de imitación ;
firma digital electrónica .

Uso

Se dice que una función unidireccional conserva la longitud si la longitud en bits del valor de la función es igual a la longitud en bits del argumento. Estas funciones se utilizan, por ejemplo, en generadores pseudoaleatorios. Si la longitud en bits del valor de una función unidireccional es constante para cualquier longitud de argumento, se denomina función hash . Entonces, la función hash se usa para almacenar contraseñas o crear una firma electrónica [1] .

La dificultad del problema de construir esquemas criptográficos a partir de funciones unidireccionales puede ilustrarse con el siguiente ejemplo. Sea una función unidireccional y necesitamos construir un criptosistema con una clave secreta . En tal criptosistema, solo hay una clave, una secreta, que es conocida tanto por el remitente como por el destinatario del mensaje cifrado. Los algoritmos de cifrado y descifrado dependen de esta clave secreta y son tales que para cualquier texto sin formato . Está claro que si el criptograma del mensaje se calcula como , entonces el adversario que interceptó , puede calcular solo con una probabilidad insignificante. Pero, en primer lugar, no está claro cómo un destinatario legítimo puede recuperar un mensaje de un criptograma. En segundo lugar, del hecho de que la función es unidireccional, solo se deduce que el adversario no puede calcular el mensaje completo. Y este es un nivel muy bajo de resistencia. Es deseable que un adversario que conoce el criptograma no pueda calcular ni un solo bit del texto sin formato. $F$ $E_{K}$ $D_{K}$ $k$ $D_{K}(E_{K}(m))=m$ $metro$ $d$ $metro$ $d=f(m)$ $d$ $metro$ $metro$ $F$ $d$

Para resolver el primer problema, se inventaron las funciones unidireccionales con entrada secreta . Este es un tipo especial de función unidireccional para el cual es fácil de calcular dado , pero difícil de calcular a partir de conocido . Sin embargo, hay cierta información secreta adicional que, si se conoce, se puede calcular fácilmente . $f(m)$ $metro$ $f(m)$ $metro$ $y$ $f(m)$ $y$ $metro$

Otro ejemplo del uso de funciones unidireccionales en esquemas criptográficos es el siguiente esquema de autenticación:

El suscriptor genera la siguiente secuencia de mensajes: etc. , donde es una función unidireccional. Luego se transmite por un canal secreto (o en una reunión) al suscriptor . Cuando es necesario confirmar su identidad, transmite un mensaje por un canal abierto . cheques: . La próxima vez enviará y verificará: etc. La interceptación de mensajes en la i-ésima etapa en el canal abierto no le dará nada al atacante, ya que no podrá obtener el valor correspondiente para identificarse como el próximo suscriptor . tiempo _ Tales esquemas se utilizan para identificar "amigo/enemigo" [2] . $A$ $m_{0},m_{1}=f(m_{0}),m_{2}=f(m_{1})$ $m_{{100}}=f(m_{{99}})$ $f(m)$ $m_{{100}}$ $B$ $A$ $B$ $m_{{99}}$ $B$ $f(m_{{99}})=?m_{{100}}$ $A$ $m_{{98}}$ $B$ $f(m_{{98}})=?m_{{99}}$ $m_{{i-1}}$ $A$

Prueba de trabajo

Para proteger los sistemas informáticos del abuso de los servicios, se le pide a la parte solicitante que resuelva un problema que requiere mucho tiempo para encontrar una solución, y la parte que presta el servicio verifica fácil y rápidamente el resultado. Un ejemplo de este tipo de protección antispam es el sistema Hashcash [3] , que solicita un hash de inversión parcial al remitente del correo electrónico.

El sistema Bitcoin requiere que la suma hash resultante sea menor que un parámetro especial. Para buscar la suma hash deseada, se requiere volver a calcularla varias veces con la enumeración de valores arbitrarios del parámetro adicional. Todas las computadoras del sistema tardan unos 10 minutos en buscar una suma hash, que regula la velocidad a la que se emiten nuevos bitcoins. La verificación requiere solo un único cálculo hash.

Fuerza de los esquemas criptográficos

La existencia de funciones unidireccionales es una condición necesaria para la solidez de muchos tipos de esquemas criptográficos. En algunos casos, este hecho se establece de manera bastante simple. Considere una función tal que . Es computable por el algoritmo en tiempo polinomial. Demostremos que si no es una función unidireccional, entonces el criptosistema es inestable. Supongamos que hay un algoritmo probabilístico polinomial que invierte con probabilidad para al menos algún polinomio . Aquí está la longitud de la clave . Un atacante puede ingresar una clave para el algoritmo y obtener algún valor de la preimagen con la probabilidad especificada . A continuación, el atacante alimenta el algoritmo como entrada y recibe un par de claves . Si bien no es necesariamente lo mismo que , es, sin embargo, por definición, un sistema criptográfico para cualquier texto sin formato . Dado que se encuentra con una probabilidad de al menos , que no se considera despreciable en criptografía, el criptosistema es inestable. $F$ $f(r)=K_{1}$ $GRAMO$ $F$ $A$ $F$ $1/p(n)$ $pags$ $norte$ $K_1$ $A$ $K_1$ $r'$ $r'$ $GRAMO$ $(K_{1},K'_{2})$ $K'_{2}$ $K_{2}$ $D_{{K_{2}'}}(E_{{K_{1}}}(m))=m$ $metro$ $K'_{2}$ $1/p(n)$

De lo dicho se desprende que la suposición de la existencia de funciones unidireccionales es la suposición criptográfica más débil, que puede ser suficiente para probar la existencia de esquemas criptográficos fuertes de varios tipos. Para averiguar si esta condición es realmente suficiente, se dirigen esfuerzos considerables de especialistas.

Hoy en día[ ¿cuándo? ] se demuestra que la existencia de funciones unidireccionales es condición necesaria y suficiente para la existencia de criptosistemas fuertes con clave secreta, así como de protocolos criptográficos fuertes de varios tipos, incluidos los protocolos de firma electrónica. Por otro lado, está el resultado de Impagliazzo y Rudich, que es un argumento suficientemente fuerte de que ciertos tipos de esquemas criptográficos (incluidos los protocolos de distribución de claves tipo Diffie-Hellman) requieren suposiciones más fuertes que la suposición de función unidireccional [4] .

Candidatos a funciones unidireccionales

A continuación se describen varios contendientes para las funciones unidireccionales. Por el momento no se sabe si realmente son unidireccionales, pero una extensa investigación aún no ha podido encontrar un algoritmo inverso eficiente para cada uno de ellos.

Multiplicación y factorización

La función toma como entrada dos números primos y en representación binaria y devuelve su producto . Esta función se puede calcular en tiempo de orden , donde es la longitud total (número de números binarios) de la entrada. Construir una función inversa requiere encontrar los factores de un número entero dado . La determinación de los factores es una operación computacional que consume mucho tiempo. Para estimar la complejidad de un algoritmo que descompone un número entero en factores primos, se suele utilizar la función: $F$ $pags$ $q$ ${\ Displaystyle N = f (p, q)}$ $O$ $(n^{2})$ $norte$ $norte$ $norte$

L_{N}(\alpha ,\beta )=\exp((\beta +o(1)(\ln N)^{\alpha }(\ln \ln N)^{1-\alpha } ))

Si el algoritmo tiene complejidad , entonces necesita un tiempo polinomial para ejecutarse (el tamaño del problema en la entrada, la cantidad de bits del número, ). Con la complejidad, requerirá un tiempo exponencial. Por lo tanto, la tasa de crecimiento de la función está entre polinomial y exponencial. Por lo tanto, se dice que los algoritmos con tal complejidad requieren un tiempo subexponencial [5] . $O(L_{N}(0,\beta))$ $\ln N$ $O(L_{N}(1,\beta))$ $L_{N}(\alfa,\beta)$ $0 < \ alfa < 1$

Hay varios métodos para factorizar un número con primos y . Algunos: $N=p*q$ $pags$ $q$

División de prueba : en este algoritmo, para todos los números primos que no superen , se verifica la condición . Tal algoritmo está cerca de la búsqueda exhaustiva y tiene una complejidad exponencial . $pags$ ${\ sqrt {N}}$ $N/p\en {\mathbb Z}$ $O(L_{N}(1,1))$
El método de la curva elíptica funciona bien si uno de los factores primos no excede . Su complejidad se estima en . $pags$ $2^{50}$ $L_{p}(1/2,c)$
La criba cuadrática es probablemente la forma más rápida de factorizar números entre y . Su complejidad es . $10^{{80}}$ $10^{{100}}$ $L_{p}(1/2,1)$
Tamiz cuadrático en un campo numérico . Este es actualmente el método más exitoso para números con 100 o más lugares decimales. Se puede usar para factorizar números hasta , y su complejidad se estima como [5] . $10^{{155}}$ $L_N(1/3,\;(64/9)^{\frac{1}{3)))$

La función se puede generalizar a un rango de semiprimos . Tenga en cuenta que no puede ser unilateral para arbitraria , ya que su producto tiene un factor de 2 con probabilidad de ¾. $F$ $pq>1$

Tenga en cuenta que la factorización con complejidad polinomial es posible en una computadora cuántica usando el algoritmo de Shor ( clase BQP ).

Elevando al cuadrado y sacando la raíz cuadrada módulo

La función toma dos números enteros: y , donde es el producto de dos números primos y . El resultado es el resto después de dividir por . Encontrar la función inversa requiere calcular el módulo de la raíz cuadrada , es decir, encontrar si también se sabe que . Se puede demostrar que el último problema es computacionalmente tan difícil como la factorización. $F$ $X$ $norte$ $norte$ $pags$ $q$ $x^{2}$ $norte$ $norte$ $X$ $y$ $x^{2}{\bmod N}=y$ $norte$

El criptosistema Rabin se basa en la suposición de que la función Rabin es unidireccional.

Exponencial discreta y logaritmo

La función de exponente discreto toma como argumentos un número primo y un número entero en el rango de hasta y devuelve el resto después de dividir algunos por . Esta función se puede calcular fácilmente en el tiempo , donde es el número de bits en . La inversión de esta función requiere calcular el módulo del logaritmo discreto . Sea un grupo abeliano finito, por ejemplo, un grupo multiplicativo de un campo finito o una curva elíptica sobre un campo finito. La tarea de calcular logaritmos discretos es determinar un número entero que, dados los datos, satisfaga la relación: $F$ $pags$ $X$ ${\ estilo de visualización 0}$ $p-1$ $A^{x}$ $pags$ $O$ $(n^{3})$ $norte$ $pags$ $pags$ $(GRAMO*)$ $X$ $A,B$

A^{x}=B

Para algunos grupos , esta tarea es bastante sencilla. Por ejemplo, si es un grupo de números enteros módulo de suma. Para otros grupos, sin embargo, esta tarea es más difícil. Por ejemplo, en un grupo multiplicativo de campos finitos, el algoritmo más conocido para resolver el problema del logaritmo discreto es el método de la criba cuadrática en un campo numérico . La complejidad de calcular logaritmos discretos en este caso se estima como . El esquema de ElGamal se basa en este problema [6] . $GRAMO$ $GRAMO$ $norte$ $L_{N}(1/3,c)$

Para grupos como la curva elíptica, el problema del logaritmo discreto es aún más difícil. El mejor método actualmente disponible para calcular logaritmos discretos sobre una curva elíptica general sobre un campo se llama método ρ de Pollard . Su complejidad . Este es un algoritmo exponencial, por lo que los criptosistemas de curva elíptica tienden a trabajar con una clave pequeña, alrededor de 160 bits. Mientras que los sistemas basados en factorización o cálculo de logaritmos discretos en campos finitos utilizan claves de 1024 bits [6] . $\mathbb {F} _{q}$ $O(L_{N}(1,1/2))$

Varios problemas estrechamente relacionados también están relacionados con el problema del logaritmo discreto. Sea un grupo abeliano finito : $(GRAMO*)$

El problema de Diffie-Hellman , que es el siguiente: elementos dados de . Se requiere calcular . $A\en G,B=A^{x},C=A^{y}$ $D=A^{{xy}}$
El problema de selección de Diffie-Hellman . Dado: . Se requiere para determinar si y es un producto . $A\en G,B=A^{x},C=A^{y},D=A^{z}$ $z$ $X$ $y$

Se puede demostrar que el problema de selección de Diffie-Hellman no es más difícil que el problema de Diffie-Hellman, y que el problema de Diffie-Hellman no es más difícil que el problema del logaritmo discreto [6] .

Funciones hash criptográficas

Hay muchas funciones hash criptográficas (por ejemplo , SHA-256 ) que son rápidas de calcular. Algunas de las versiones más simples no pasaron por un análisis complejo, pero las versiones más sólidas continúan ofreciendo soluciones prácticas y rápidas para cálculos unidireccionales. Gran parte del apoyo teórico para estas características tiene como objetivo frustrar algunos de los ataques exitosos anteriores.

Otros contendientes

Otros contendientes para funciones unidireccionales se basan en la dificultad de decodificar códigos lineales aleatorios y otros problemas.

Véase también

Notas

↑ 1 2 Ptitsyn, 2002 , pág. 38-39.
↑ Esquema de autenticación .
↑ Hashcash - Una contramedida de denegación de servicio (2002)
↑ Russel Impagliazzo, Steven Rudich. La recuperación de información privada no implica permutaciones unidireccionales .
↑ 1 2 Smart, 2005 , pág. 185-186.
↑ 1 2 3 Smart, 2005 , pág. 187-188.

Enlaces

Oded Goldreich. Volumen 1, Herramientas básicas // Fundamentos de criptografía . - Prensa de la Universidad de Cambridge , 2001. - ISBN 0-521-79172-3 .
Jonathan Katz, Yehuda Lindell. Introducción a la Criptografía Moderna. - CRC Press , 2007. - ISBN 1-58488-551-3 .
Michael Sipser Sección 10.6.3: Funciones unidireccionales // Introducción a la Teoría de la Computación . - PWS Publishing, 1997. - P. 374 -376. — ISBN 0-534-94728-X .
Christos Papadimitriou . Sección 12.1: Funciones unidireccionales // Complejidad computacional. — 1ª edición. - Addison Wesley , 1993. - S. 279-298. — ISBN 0-201-53082-1 .
Capítulo 2.3. Funciones unidireccionales // Introducción a la criptografía / Ed. V. V. Yashchenko.
Capítulo 2.5.2 Función unidireccional // Aplicación de la teoría del caos determinista en criptografía / Ptitsyn N. - 2002. (enlace inaccesible)
Capítulo 7.2 Funciones unidireccionales // Criptografía / Smart N. - 2005. - ISBN 5-94836-043-1 .
Capítulo 4.1 Funciones unidireccionales (ruso) ? . Consultado el 9 de octubre de 2014. Archivado desde el original el 3 de diciembre de 2016. (indefinido)