Compromiso de tiempo y memoria

Compromiso de tiempo y ___ _memoria informática , que utiliza la relación inversa de la cantidad de memoria requerida y la velocidad de ejecución del programa: el tiempo de cálculo se puede aumentar al reducir la memoria utilizada o, por el contrario, reducido al aumentar la cantidad de memoria utilizada.

Debido a la disminución de los costos relativos de la cantidad de RAM (RAM) y la memoria del disco duro (durante un período de tiempo, el costo del espacio en el disco duro se abarató mucho más rápido que el costo de otros componentes de la computadora ), técnicas que utilizan disponibles memoria para reducir el tiempo de cálculo se han extendido gradualmente. Al mismo tiempo, técnicas como la compresión de datos demuestran un enfoque alternativo: el uso económico de la memoria debido a las conversiones de datos adicionales de un formato a otro.

Ejemplos de aplicación

Tablas de consulta

Muchos problemas de búsqueda, como el problema de la mochila continua , el problema del logaritmo discreto , o el problema de invertir una función unidireccional , siendo resueltos, de hecho, por enumeración, al mismo tiempo permiten el uso de los llamados. tablas de búsqueda (tablas de búsqueda en inglés ) [1] . La idea es esta: en lugar de iterar sobre todas las soluciones factibles sin usar memoria adicional, o calcularlas todas una vez por adelantado y almacenarlas en la memoria (a menudo no existe ni la primera ni la segunda posibilidad), puede precalcular una parte de la solución factible . valores y, habiéndolos organizado en una estructura de datos especial, una tabla de búsqueda, para usarla para llevar a cabo una enumeración adicional directamente al resolver el problema.

Una sección separada de este artículo está dedicada a la aplicación de este enfoque en criptografía.

Compresión de datos

La elección de la relación óptima "lugar - tiempo" se puede aplicar al problema del almacenamiento de datos. El almacenamiento de datos en forma no comprimida requerirá más memoria, pero llevará menos tiempo recuperarlos que recuperar datos almacenados en forma comprimida. Dependiendo de la tarea concreta, puede ser preferible una u otra opción.

Un ejemplo clásico de una representación de datos compacta es, por ejemplo, el formato de representación de fórmula Τ Ε Χ utilizado para escribir artículos científicos. El resultado del trabajo del usuario es un archivo de un formato especial que, si es necesario, se puede convertir fácilmente en un archivo pdf mucho más "pesado" que, a su vez, ya se puede usar para ver el documento en visores más populares. que los específicos de Τ Ε Χ .

Ciclo de promoción

El desenrollado de bucles es una técnica de optimización de código muy popular utilizada en muchos compiladores. La idea es aumentar el número de instrucciones ejecutadas durante una iteración del bucle. Como resultado, el número de iteraciones disminuye (hasta una en el límite: todas las instrucciones se ejecutan una tras otra), lo que, a su vez, aumenta la eficiencia de la caché de datos .

Criptografía

Esta sección analiza un ejemplo clásico del uso del enfoque de intercambio espacio-tiempo en criptografía : el uso de tablas de búsqueda para resolver el problema criptográfico de invertir una función hash criptográfica .

La enumeración criptoanalítica requiere costos computacionales significativos. En el caso de que se requiera crackear repetidamente el criptosistema, lo lógico sería realizar previamente una enumeración exhaustiva y almacenar en memoria los valores calculados. Habiendo hecho esto una vez, puede seguir enumerando casi instantáneamente [2] . Sin embargo, en realidad, este método no es aplicable debido a los enormes costos de memoria.

Método de Hellman

En 1980, Martin Hellman propuso un enfoque de compromiso para el problema del criptoanálisis, que hace posible analizar un criptosistema que tiene claves en operaciones, con costos de memoria también [1] . Esto es posible después de que se haya realizado una vez la preobtención O(n) de posibles claves. $norte$ $N^{{2/3}}$ $N^{{2/3}}$

La idea es la siguiente.

Deje que el algoritmo de cifrado use una función unidireccional . Por las propiedades de una función unidireccional, derivar una clave usada de un par conocido es una tarea difícil, mientras que calcular una función a partir de un texto sin formato dado es una tarea simple. $S_{k_{i}}(P)$ $k_i$ $P_{0},C_{0}$

El criptoanalista utiliza un ataque de texto sin formato elegido y obtiene un texto cifrado único que coincide con el texto sin formato : $C_{0}$ $P_0$

C_{0}=S_{k}(P_{0})

La tarea es encontrar la clave que se utilizó para cifrar. Para hacer esto, necesita encontrar una manera de calcular las posibles claves. Vamos a presentar los llamados. función de reducción , que asigna una determinada clave al texto cifrado (la longitud de la clave suele ser menor que la longitud del texto cifrado, de ahí el término): $k$ ${\ estilo de visualización R (C)}$ $C_{yo}$ $k_{{yo+1}}$

R(C_{i})=k_{i+1}

Calcular la función de reducción es una operación simple.

Función $f=R[S_{k_{i}}(P_{0})]$

asigna una clave a otra clave . Ahora podemos obtener un llavero arbitrariamente largo: $k_i$ $k_{{yo+1}}$

k_{i}{\stackrel {f}{\longrightarrow }}k_{i+1}{\stackrel {f}{\longrightarrow }}k_{i+2}{\stackrel {f}{\longrightarrow }}...

Para construir una tabla de búsqueda, el criptoanalista recibe elementos aleatorios del espacio de claves. De cada llave, utilizando el método descrito anteriormente, obtenemos un llavero de longitud . Escribimos en la memoria solo las claves inicial y final de cada cadena (clasificamos los pares de claves por la clave final ). Por lo tanto, la tabla terminada ocupa celdas de memoria. La generación de tablas requiere operaciones. $metro$ $t$ $O(m)$ $monte$

Teniendo la tabla construida, el criptoanalista puede enumerar de la siguiente manera. Partimos del hecho de que la clave utilizada en el cifrado se encontró durante la generación de la tabla. En este caso, una de las claves finales almacenadas en memoria se puede obtener de ella en no más de t operaciones de aplicación de la función . $k$ $F$ $metro$

Después de cada aplicación de la operación de reducción, el criptoanalista busca la siguiente clave recibida en la tabla (puede encontrarla o asegurarse de que no existe para operaciones con búsqueda binaria , ya que la tabla se ordena por la clave final). Habiendo encontrado una de las claves finales, es posible restaurar toda la cadena correspondiente a partir de la clave inicial que le corresponde; la clave deseada es su penúltima clave. $registro(m)$

Encontrar la clave requiere [3] ; despreciando el factor logarítmico, tenemos . En este caso, los costos de memoria para almacenar la tabla son . $O(t\cdot log(m))$ $Antiguo Testamento)$ $O(m)$

El análisis del algoritmo, sin embargo, debe tener en cuenta que la probabilidad de éxito en el descifrado es en realidad menor que uno, y el tiempo de descifrado puede resultar mayor que el declarado, por las razones que se indican a continuación. $P_{éxito}$

Es posible fusionar cadenas cuando la enésima clave de una y la enésima clave de otra cadena coinciden para algún par de índices. $yo, j$ $i$ $j$
Posible llamado. "falsas alarmas" (ing. falsas alarmas), cuando el criptoanalista encuentra más de una clave final en la tabla. En este caso, tiene que comprobar todas las cadenas pertinentes.

Se puede derivar un límite inferior [1] para la probabilidad de descifrado exitoso:

P_{éxito}\geq {\frac {1}{N}}\sum \limits _{i=1}^{m}\sum \limits _{j=0}^{t-1}\ izquierda(1-{\frac {it}{N}}\derecha)^{j+1}

La expresión anterior corresponde a la aproximación de que la función es una variable aleatoria con una distribución uniforme en el conjunto de claves. Sin embargo, un criptosistema estable debería ser un buen generador pseudoaleatorio [1] . $F$

La evaluación de esta expresión conduce al siguiente resultado: no tiene sentido tomar el producto mayor que $mt^{2}$ $norte$ : de lo contrario, el límite inferior de la probabilidad de éxito cae rápidamente.

cuando lleguemos $mt^{2}=N$

P_{{éxito}}\geq 0.8{\frac {mt}{N}}={\frac {1}{t}}

El criptoanalista ahora puede generar no solo una, sino tablas, en cada tabla utilizando su propia función de reducción (que evitará fusionar cadenas de diferentes tablas). En este caso, el límite inferior de la probabilidad de descifrado exitoso será: $yo$

P_{éxito,l}\geq 1-\left[{\frac {1}{N}}\sum \limits _{i=1}^{m}\sum \limits _{j=0} ^{t-1}\left(1-{\frac {it}{N}}\right)^{j+1}\right]^{l}

Al elegir , el criptoanalista recibe costos de memoria y tiempo (cada tabla usa su propia función de reducción, por lo que al descifrar necesita obtener su propia cadena para cada tabla) con una probabilidad de éxito cercana a uno [nota al pie que explica por qué la cantidad de falsas alarmas sea pequeño y enlace en Hellman]. Tomando , obtenemos el tiempo requerido y los costos de memoria. $l = t$ $monte$ $t^{2}$ $t=m=N^{{1/3}}$ $N^{{2/3}}$

Otros ejemplos

Otros algoritmos que también utilizan la "selección óptima de lugar y tiempo":

Algoritmo de Shanks , utilizado para calcular logaritmos discretos .
Programación dinámica , en la que la complejidad del tiempo de una tarea que se divide efectivamente en subtareas puede reducirse significativamente mediante la memorización , guardando las soluciones ya calculadas para las subtareas.
Las tablas Rainbow en criptografía son una versión mejorada de las tablas de búsqueda para invertir funciones hash criptográficas .

Véase también

Eficiencia del algoritmo
computacional
de aceleración de Blum
teorema de Savitch
bucle desenrollado

Notas

↑ 1 2 3 4 Martín E. Hellman. Una compensación de tiempo-memoria criptoanalítica. // Transacciones en Teoría de la Información. - Julio 1980. - Nº 4.
↑ Philippe Oechslin. Hacer un intercambio de tiempo-memoria criptoanalítico más rápido. // ISBN 3-540-40674-3 .
↑ Kormen T., Leyzerson Ch., Rivest R. Algoritmos: construcción y análisis. - 2do. — M.: Williams, 2005. — 1296 p. — ISBN 5-8459-0857-4 .