Tipos de funciones hash. Funciones hash: concepto y conceptos básicos. Hash de cadenas de longitud variable

12 de mayo de 2010 a las 01:28

Algoritmos hash

• Seguridad de información

Creo que mucha gente sabe que desde 2007 Instituto Nacional US Standards and Technologies (NIST) está organizando un concurso para desarrollar un algoritmo hash que reemplace a SHA-1 y la familia de algoritmos SHA-2. Sin embargo este tema, por alguna razón ha sido descuidado en el sitio. En realidad, esto es lo que me trajo hasta ti. Les llamo la atención sobre una serie de artículos dedicados a los algoritmos hash. En esta serie, estudiaremos juntos los conceptos básicos de las funciones hash, consideraremos los algoritmos hash más famosos, nos sumergiremos en la atmósfera de la competencia SHA-3 y consideraremos los algoritmos que pretenden ganarla, y definitivamente los probaremos. Si es posible, también consideraremos estándares rusos hash.

Acerca de mí

Estudiante del Departamento de Seguridad de la Información.

Acerca del hash

Hoy en día, casi ninguna aplicación de criptografía está completa sin el uso de hash.
Las funciones hash son funciones diseñadas para "comprimir" un mensaje arbitrario o un conjunto de datos, generalmente escritos en alfabeto binario, en algún patrón de bits de longitud fija llamado convolución. Las funciones hash tienen varias aplicaciones al realizar experimentos estadísticos, al realizar pruebas dispositivos lógicos, al construir algoritmos búsqueda rápida y comprobar la integridad de los registros en las bases de datos. El principal requisito de las funciones hash es la distribución uniforme de sus valores cuando los valores de los argumentos se seleccionan aleatoriamente.
Una función hash criptográfica es cualquier función hash que sea criptográficamente estable, es decir, que satisfaga una serie de requisitos específicos de las aplicaciones criptográficas. En criptografía, las funciones hash se utilizan para resolver los siguientes problemas:
- construir sistemas de seguimiento de la integridad de los datos durante su transmisión o almacenamiento,
- autenticación de fuente de datos.

Cualquier función se llama función hash. h:X->Y, fácilmente computable y tal que para cualquier mensaje METRO significado h(M) = H (convolución) tiene una longitud de bits fija. X- conjunto de todos los mensajes, Y- un conjunto de vectores binarios de longitud fija.

Como regla general, las funciones hash se construyen sobre la base de las llamadas funciones de compresión en un solo paso. y = f(x1, x2) dos variables, donde x1, x2 Y y- vectores binarios de longitud metro, norte Y norte en consecuencia, y norte es la longitud de la convolución, y metro- longitud del bloque de mensajes.
para obtener el valor h(M) el mensaje se divide primero en bloques de longitud metro(al mismo tiempo, si la longitud del mensaje no es múltiplo metro Eso último bloque se complementa de alguna manera especial hasta completar), y luego a los bloques resultantes M 1, M 2,.., M N Aplique el siguiente procedimiento secuencial para calcular la convolución:

H o = v,
H i = f(M i ,H i-1), i = 1,.., N,
h(M) = HN

Aquí v- alguna constante, a menudo llamada vector de inicialización. ella sale
por diversos motivos y puede ser una constante secreta o un conjunto de datos aleatorios (una muestra de fecha y hora, por ejemplo).
Con este enfoque, las propiedades de la función hash están completamente determinadas por las propiedades de la función de compresión de un solo paso.

Hay dos tipos importantes Funciones hash criptográficas: con y sin clave. Las funciones hash clave se denominan códigos de autenticación de mensajes. Proporcionan una oportunidad sin fondos adicionales Garantizar tanto la exactitud de la fuente de datos como la integridad de los datos en sistemas con usuarios que confían mutuamente.
Las funciones hash sin clave se denominan códigos de detección de errores. Permiten garantizar la integridad de los datos utilizando medios adicionales (cifrado, por ejemplo). Estas funciones hash se pueden utilizar en sistemas con usuarios tanto confiados como desconfiados.

Acerca de las propiedades y requisitos estadísticos

Como ya dije, el principal requisito para las funciones hash es la distribución uniforme de sus valores cuando los valores de los argumentos se seleccionan aleatoriamente. Para funciones hash criptográficas También es importante que con el más mínimo cambio en el argumento, el valor de la función cambie mucho. A esto se le llama efecto avalancha.

A funciones clave El hashing tiene los siguientes requisitos:
- imposibilidad de fabricación,
- imposibilidad de modificación.

El primer requisito significa la alta complejidad de seleccionar un mensaje con valor correcto convoluciones. En segundo lugar, la alta complejidad de la selección de mensaje dado con un valor de plegado conocido de otro mensaje con el valor de plegado correcto.

Los requisitos para las funciones sin llave son:
- unidireccionalidad,
- resistencia a la colisión,
- resistencia a encontrar una segunda preimagen.

La unidireccionalidad se refiere a la gran dificultad de encontrar un mensaje basado en un valor de convolución determinado. Cabe señalar que en este momento No se utilizan funciones hash unidireccionales comprobadas.
La resistencia a la colisión se refiere a la dificultad de encontrar un par de mensajes con los mismos valores de convolución. Normalmente, el descubrimiento por parte de los criptoanalistas de una manera de construir colisiones es la primera señal de que el algoritmo se está volviendo obsoleto y necesita ser reemplazado rápidamente.
La resistencia a encontrar una segunda preimagen se refiere a la dificultad de encontrar un segundo mensaje con el mismo valor de convolución para un mensaje determinado con un valor de convolución conocido.

Esta fue la parte teórica, que nos será útil en el futuro...

Acerca de los algoritmos hash populares

Algoritmos CRC16/32- suma de comprobación (no conversión criptográfica).

Algoritmos MD2/4/5/6. Son creación de Ron Rivest, uno de los autores del algoritmo RSA.
El algoritmo MD5 alguna vez tuvo gran popularidad, pero los primeros requisitos previos para la piratería aparecieron a finales de los noventa y ahora su popularidad está cayendo rápidamente.
El algoritmo MD6 es un algoritmo muy interesante desde el punto de vista del diseño. Fue nominado para el concurso SHA-3, pero, lamentablemente, los autores no tuvieron tiempo de adaptarlo al estándar y este algoritmo no está en la lista de candidatos que pasaron a la segunda ronda.

Algoritmos de regla sha Algoritmos que se utilizan ampliamente en la actualidad. Hay una transición activa de los estándares de versión SHA-1 a SHA-2. SHA-2 es el nombre colectivo de los algoritmos SHA224, SHA256, SHA384 y SHA512. SHA224 y SHA384 son esencialmente análogos de SHA256 y SHA512, respectivamente, solo que después de calcular la convolución, parte de la información que contiene se descarta. Deben utilizarse únicamente para garantizar la compatibilidad con equipos de modelos más antiguos.

Estándar ruso - GOST 34.11-94.

En el próximo artículo

Revisión de algoritmos MD (MD4, MD5, MD6).

Literatura

A. P. Alferov, Fundamentos de criptografía.

Bruce Schneier, criptografía aplicada.

hash al resolver problemas en C++.

El proceso de búsqueda de datos en grandes volúmenes La información está asociada a costos de tiempo, los cuales se deben a la necesidad de visualizar y comparar un número importante de elementos con la clave de búsqueda. Se puede reducir la búsqueda localizando el área de visualización. Por ejemplo, clasifique los datos por clave de búsqueda, divídalos en bloques que no se superpongan según alguna característica del grupo o haga coincidir los datos reales con un código determinado que simplificará el procedimiento de búsqueda.

Actualmente, un método ampliamente utilizado para proporcionar acceso rapido a la información almacenada en memoria externa– hash.

hash(o hash, Inglés hash) es una transformación de la matriz de datos de entrada cierto tipo y longitud arbitraria en una cadena de bits de salida de longitud fija. Estas transformaciones también se denominan funciones hash o funciones de convolución, y sus resultados se llaman hash, código hash, tabla hash o digerir mensajes (inglés) resumen del mensaje).

Tabla de picadillo- Este estructura de datos, implementando la interfaz matriz asociativa, es decir, le permite almacenar pares clave-valor y realizar tres operaciones: la operación de agregar nueva pareja, operación de búsqueda y operación de eliminación de un par por clave. Una tabla hash es una matriz formada en en un cierto orden función hash.

• la función debe ser sencilla desde el punto de vista computacional;
• la función debe distribuir las claves en la tabla hash de la manera más uniforme posible;
• la función no debe asignar ninguna relación entre valores clave a una relación entre valores de dirección;
• la función debe minimizar el número de colisiones, es decir, situaciones en las que diferentes claves corresponde a un valor de la función hash (las claves en este caso se llaman sinónimos).

En este caso, la primera propiedad de una buena función hash depende de las características de la computadora y la segunda, de los valores de los datos.

Si todos los datos fueran aleatorios, entonces las funciones hash serían muy simples (por ejemplo, unos pocos bits clave). Sin embargo, en la práctica, los datos aleatorios son tan raros que es necesario crear una función que dependa de la clave completa. Si una función hash distribuye una población posibles claves de manera uniforme en múltiples índices, el hash divide efectivamente múltiples claves. El peor de los casos es cuando todas las claves se agrupan en un índice.

Cuando ocurren colisiones, es necesario encontrar una nueva ubicación para almacenar las claves que reclaman la misma celda de la tabla hash. Además, si se permiten las colisiones, se debe minimizar su número. En algunos casos especiales es posible evitar colisiones por completo. Por ejemplo, si todas las claves de los elementos se conocen de antemano (o cambian muy raramente), entonces se puede encontrar alguna función hash inyectiva para ellas que las distribuya entre las celdas de la tabla hash sin colisiones. Las tablas hash que utilizan funciones hash similares no necesitan un mecanismo de resolución de colisiones y se denominan tablas hash con direccionamiento directo.

Las tablas hash deben coincidir con lo siguiente propiedades.

• La realización de una operación en una tabla hash comienza calculando la función hash de la clave. El valor hash resultante es un índice de la matriz original.
• Número de elementos de la matriz almacenados divididos por el número valores posibles la función hash se llama factor de relleno de la tabla hash (factor de carga) y es parámetro importante, del cual depende el tiempo promedio para completar las operaciones.
• Las operaciones de búsqueda, inserción y eliminación deben completarse en un tiempo promedio de O(1). Sin embargo, esta estimación no tiene en cuenta los posibles costos de hardware de reconstruir el índice de la tabla hash asociados con el aumento del valor del tamaño de la matriz y la adición de un nuevo par a la tabla hash.
• El mecanismo de resolución de colisiones es un componente importante de cualquier tabla hash.

El hash es útil cuando amplia gama Los valores posibles deben almacenarse en una pequeña cantidad de memoria y se necesita una forma de acceso rápido, casi aleatorio. Las tablas hash se utilizan a menudo en bases de datos, y especialmente en procesadores de lenguaje como compiladores y ensambladores, donde aumentan la velocidad de procesamiento de la tabla de identificadores. Como uso del hash en La vida cotidiana Se pueden dar ejemplos de distribución de libros en la biblioteca en catálogos temáticos, ordenamiento en diccionarios por las primeras letras de las palabras, cifrado de especialidades en universidades, etc.

Métodos de resolución de colisiones

Las colisiones complican el uso de tablas hash porque rompen la correspondencia única entre los códigos hash y los datos. Sin embargo, existen formas de superar las dificultades que surgen:

• método de encadenamiento (hash externo o abierto);
• método de direccionamiento abierto (hash cerrado).

método de cadena. La tecnología de adhesión de elementos es que elementos del conjunto, que corresponden al mismo valor hash, están vinculados en una lista en cadena. El número de posición i almacena un puntero al encabezado de la lista de aquellos elementos cuyo valor hash clave es igual a i; si no existen tales elementos en el conjunto, NULL se escribe en la posición i. En la Fig.

La Figura 38.1 demuestra la implementación del método de encadenamiento para resolver colisiones. La clave 002 está reclamada por dos valores, que están organizados en una lista lineal.

Arroz. 38.1.

Cada celda de la matriz es un puntero a una lista vinculada (cadena) de pares clave-valor correspondientes al mismo valor hash de la clave. Las colisiones simplemente resultan en cadenas de más de un elemento.

Bajo el supuesto de que cada elemento puede caer en cualquier posición de la tabla con igual probabilidad e independientemente de dónde caiga cualquier otro elemento,

Anotación: En esta conferencia, se formula el concepto de función hash, y también breve reseña Algoritmos para generar funciones hash. Además, la posibilidad de utilizar algoritmos de bloque cifrado para formar una función hash.

Objetivo de la conferencia: familiarizarse con el concepto de función hash, así como con los principios de funcionamiento de dichas funciones.

El concepto de función hash.

Función hash es una función matemática o de otro tipo que, para una cadena de longitud arbitraria, calcula algún valor entero o alguna otra cadena de longitud fija. Matemáticamente se puede escribir así:

donde M es el mensaje original, a veces llamado prototipo, y h es el resultado, llamado valor hash (y también código hash o resumen del mensaje(De inglés resumen del mensaje)).

El propósito de una función hash es determinar característica distintiva preimagen: valor de la función hash. Este significado suele tener cierta tamaño fijo por ejemplo, 64 o 128 bits. El código hash se puede analizar más a fondo para resolver cualquier problema. Por ejemplo, el hash se puede utilizar para comparar datos: si dos matrices de datos tienen códigos hash diferentes, se garantiza que las matrices serán diferentes; si son iguales, lo más probable es que las matrices sean iguales. EN caso general No existe una correspondencia uno a uno entre los datos de origen y el código hash debido al hecho de que el número de valores de la función hash es siempre menor que el número de opciones de datos de entrada. En consecuencia, hay muchos mensajes de entrada que dan los mismos códigos hash (estas situaciones se denominan colisiones). La probabilidad de colisiones juega un papel importante en la evaluación de la calidad de las funciones hash.

Las funciones hash se utilizan ampliamente en la criptografía moderna.

La función hash más simple se puede construir usando la operación "suma módulo 2" de la siguiente manera: obtenemos la cadena de entrada, sumamos todos los bytes módulo 2 y devolvemos el byte resultante como valor hash. La longitud del valor de la función hash en este caso será de 8 bits, independientemente del tamaño del mensaje de entrada.

Por ejemplo, deje que el mensaje original se traduzca al vista digital, era el siguiente (en hexadecimal):

Traduzcamos el mensaje a vista binaria, escribe los bytes uno debajo del otro y suma los bits en cada columna módulo 2:

0011 1110 0101 0100 1010 0000 0001 1111 1101 0100 ---------- 0110 0101

El resultado (0110 0101 (2) o 65 (16)) será el valor hash.

Sin embargo, dicha función hash no se puede utilizar con fines criptográficos, como generar firma electronica, ya que es bastante fácil cambiar el contenido de un mensaje firmado sin cambiar el valor suma de control.

Por lo tanto, la función hash considerada no es adecuada para aplicaciones criptográficas. En criptografía, una función hash se considera buena si es difícil crear dos preimágenes con el mismo valor función hash, y también si la salida de la función no tiene una dependencia explícita de la entrada.

Formulemos los requisitos básicos para las funciones hash criptográficas:

• la función hash debe ser aplicable a un mensaje de cualquier tamaño;
• el cálculo del valor de la función debe realizarse con la suficiente rapidez;
• en significado conocido Debería ser difícil (prácticamente imposible) que una función hash encuentre una preimagen adecuada de M;
• Dado un mensaje M, debería ser difícil encontrar otro mensaje M' con el mismo valor hash que Mensaje original;
• Debería ser difícil encontrar un par de mensajes distintos al azar con el mismo valor hash.

Crea una función hash que satisfaga a todos requisitos enumerados– la tarea no es fácil. También es necesario recordar que la entrada de la función recibe datos de tamaño arbitrario y el resultado hash no debe ser el mismo para datos de diferentes tamaños.

Actualmente, en la práctica, se utilizan como funciones hash funciones que procesan el mensaje de entrada bloque por bloque y calculan el valor hash h i para cada bloque M i del mensaje de entrada según las dependencias del formulario.

h yo = H (M yo, h yo-1),

donde h i-1 es el resultado obtenido al calcular la función hash para el bloque anterior de datos de entrada.

Como resultado, la salida de la función hash h n es una función de los n bloques del mensaje de entrada.

Uso de algoritmos de cifrado de bloques para generar una función hash

Puede utilizar una función hash de bloque como función hash. Si el algoritmo de bloque utilizado es criptográficamente fuerte, entonces la función hash basada en él será segura.

La forma más sencilla de utilizar un algoritmo de bloque para obtener un código hash es cifrar el mensaje en modo CBC. En este caso, el mensaje se representa como una secuencia de bloques cuya longitud es igual a la longitud del bloque del algoritmo de cifrado. Si es necesario, el último bloque de la derecha se rellena con ceros para crear un bloque de la longitud requerida. El valor hash será el último bloque de texto cifrado. Siempre que se utilice un algoritmo de cifrado de bloques sólido, el valor hash resultante tendrá las siguientes propiedades:

• Es casi imposible calcular un valor hash para un conjunto abierto de información determinado sin conocer la clave de cifrado;
• Sin conocer la clave de cifrado, es casi imposible seleccionar datos abiertos para un valor de función hash determinado.

El valor hash así generado generalmente se llama inserción de imitación o autenticador y se utiliza para comprobar la integridad del mensaje. Por tanto, el inserto imitativo es una combinación de control que depende de datos abiertos e información de clave secreta. El propósito de utilizar la inserción imitativa es detectar todos los cambios accidentales o intencionales en la matriz de información. El valor obtenido por la función hash al procesar el mensaje de entrada se agrega al mensaje en el momento en que se sabe que el mensaje es correcto. El destinatario verifica la integridad del mensaje calculando el mensaje imitado del mensaje recibido y comparándolo con el código hash recibido, que debe transmitirse de forma segura. Uno de estos maneras seguras puede haber cifrado de inserción imitativa llave privada remitente, es decir creando una firma. También es posible cifrar el código hash resultante con un algoritmo. cifrado simétrico, si el remitente y el destinatario tienen una clave de cifrado simétrica común.

El proceso especificado para obtener y utilizar inserciones de imitación se describe en la norma nacional GOST 28147-89. El estándar propone utilizar los 32 bits inferiores del bloque obtenidos en la salida de la operación de cifrado de todo el mensaje en el modo de encadenamiento de bloques de cifrado para controlar la integridad. mensaje transmitido. De la misma manera, puede utilizar cualquier bloque para formar una inserción simulada. algoritmo de cifrado simétrico.

A otros Una salida posible aplicaciones cifrado de bloque para generar el código hash es el siguiente. El mensaje original se procesa secuencialmente en bloques. El último bloque se rellena con ceros si es necesario; a veces, la longitud del mensaje se agrega al último bloque del formulario; número binario. En cada etapa, ciframos el valor hash obtenido en la etapa anterior, utilizando el bloque de mensaje actual como clave. El último valor cifrado recibido será el resultado del hash final.

De hecho, existen otros esquemas posibles para utilizar un cifrado de bloque para generar una función hash. Sea M i el bloque del mensaje original, h i el valor de la función hash en la i-ésima etapa, f el algoritmo de cifrado de bloques utilizado en el modo de reemplazo simple y sea la operación de suma módulo 2. Entonces , por ejemplo, son posibles los siguientes esquemas para generar una función hash:

En todos estos esquemas, la longitud del valor hash generado es igual a la longitud del bloque de cifrado. Todos estos, así como algunos otros esquemas para utilizar un algoritmo de cifrado de bloques para calcular valores hash, se pueden utilizar en la práctica.

La principal desventaja de las funciones hash diseñadas en base a algoritmos de bloques es la relativa baja velocidad trabajar. La solidez criptográfica requerida se puede lograr con menos operaciones en los datos de entrada. Hay mas algoritmos rápidos hashes diseñados de forma independiente, desde cero, según los requisitos de solidez criptográfica (los más comunes son MD5, SHA-1, SHA-2 y GOST R 34.11-94).

Hashing es un método especial para direccionar datos (un determinado algoritmo de disposición) por sus claves únicas ( llave ) para encontrar rápidamente la información que necesita..

Conceptos básicos

Tabla de picadillo

Una tabla hash es una matriz normal con un direccionamiento especial especificado por alguna función (función Hash).

Función hash

Una función que asigna la clave de un elemento de datos a algún índice en una tabla ( tabla de picadillo), llamado función hash o función hash :

i = h (llave );

Dónde llave- llave convertible, i- el índice de la tabla resultante, es decir la clave se muestra en un conjunto, por ejemplo, de números enteros ( direcciones hash ), que se utilizan posteriormente para acceder a los datos.

El hash de esta forma es una técnica que implica utilizar el valor de una clave para determinar su posición en una tabla especial.

Sin embargo, la función de disposición puede varios los valores clave únicos dan el mismo valor de posición i en la tabla hash. Una situación en la que dos o más claves comparten el mismo índice (dirección hash) se llama colisión (conflicto) al realizar hash. Por lo tanto, el esquema de hash debe incluirlo. algoritmo de resolución de conflictos , que determina el orden de las acciones si la posición i=h(llave) resulta que ya está ocupado por un registro con una clave diferente.

Existen muchos esquemas de hash, según la función hash utilizada. h(llave) y algoritmos de resolución de conflictos.

El método más común para especificar una función hash es: Método de división.

Los datos iniciales son: - alguna clave entera llave y tamaño de la mesa metro. El resultado de esta función es el resto cuando esta clave se divide por el tamaño de la tabla. forma general tal función en el lenguaje de programación C/C++:

En t h (En t llave , En t metro ) {

Para metro= 10 función hash devuelve el dígito menos significativo de la clave.

Para m= 100, la función hash devuelve los dos dígitos menos significativos de la clave.

En los ejemplos considerados, la función hash i=h(llave) solo define la posición desde la cual necesita buscar (o colocar inicialmente en la tabla) un registro con una clave llave. A continuación, debe utilizar algún esquema de hash (algoritmo).

Esquemas de hash

En la mayoría de los problemas, dos o más claves tienen el mismo hash, pero no pueden ocupar la misma celda en la tabla hash. Hay dos opciones posibles: busque una posición diferente para la nueva clave o cree una lista separada para cada índice de la tabla hash que contenga todas las claves que se asignan a ese índice.

Estas opciones representan dos esquemas de hash clásicos:

hash utilizando el método de direccionamiento abierto con muestreo lineal - lineal Investigacion abierto direccionamiento.

hash utilizando el método de cadena (con listas), o el llamado hash multidimensional - encadenamiento con separado liza;

Método de direccionamiento abierto con muestreo lineal. . Inicialmente, todas las celdas de la tabla hash, que es una matriz unidimensional normal, se marcan como desocupadas. Por lo tanto, al agregar una nueva clave, se verifica si la celda dada está ocupada. Si la celda está ocupada, el algoritmo busca en círculo hasta encontrar un espacio libre (“dirección abierta”).

Aquellos. Los elementos con claves homogéneas se colocan cerca del índice resultante.

En el futuro, cuando busque, primero busque la posición por clave i en la tabla, y si la clave no coincide, la búsqueda posterior se realiza de acuerdo con el algoritmo de resolución de conflictos, comenzando desde la posición i. .

método de cadena es la estrategia dominante . En este caso i obtenido de la función hash seleccionada h(llave)=i, se trata como un índice en una tabla hash de listas, es decir. clave primero llave la siguiente entrada está asignada a la posición i = h(llave) mesas. Si la posición está libre, entonces se coloca en ella un elemento con una clave. llave, si está ocupado, se elabora un algoritmo de resolución de conflictos, como resultado del cual dichas claves se colocan en una lista que comienza en i-esa celda de la tabla hash. Por ejemplo

Como resultado, tenemos una tabla de una serie de listas o árboles vinculados.

El proceso de completar (leer) una tabla hash es simple, pero acceder a los elementos requiere las siguientes operaciones:

Cálculo del índice i;

Busca en el hilo correspondiente.

Para mejorar la búsqueda al agregar un nuevo elemento, puede utilizar el algoritmo de inserción no al final de la lista, sino con orden, es decir. agregar elemento a Lugar correcto.

Un ejemplo de implementación del método de direccionamiento directo con muestreo lineal. . Los datos de origen son 7 registros (para simplificar, la parte de información consta solo de datos enteros), tipo de estructura declarada:

clave interna; // Llave

información interna; // Información

(59,1), (70,3), (96,5), (81,7), (13,8), (41,2), (79,9); tamaño de la tabla hash m = 10.

Función hash i=h(datos) =datos.llave%10; aquellos. resto de la división entre 10 - i.

Con base en los datos iniciales, completamos secuencialmente la tabla hash.

El hash de las primeras cinco claves proporciona diferentes índices (direcciones hash):

La primera colisión se produce entre las teclas 81 y 41: el lugar con el índice 1 está ocupado. Por lo tanto, buscamos en la tabla hash el espacio libre más cercano, en en este caso- Este i = 2.

La siguiente tecla 79 también genera una colisión: la posición 9 ya está ocupada. La eficiencia del algoritmo cae drásticamente, porque se necesitaron 6 muestras (comparaciones) para encontrar un espacio libre, el índice resultó ser libre i= 4.

El número total de muestras de este método es de 1 a n-1 muestras por elemento, donde n es el tamaño de la tabla hash.

Implementación del método de la cadena. para el ejemplo anterior. Declaramos un tipo estructurado para un elemento de lista (unidireccional):

clave interna; // Llave

información interna; // Información

zap*Siguiente; // Puntero al siguiente elemento de la lista

Según los datos iniciales, completamos secuencialmente la tabla hash agregando nuevo elemento al final de la lista si la plaza ya está ocupada.

Al aplicar hash a las cinco primeras claves, como en el caso anterior, se obtienen diferentes índices (direcciones hash): 9, 0, 6, 1 y 3.

Cuando ocurre una colisión, se agrega un nuevo elemento al final de la lista. Por lo tanto, el elemento con clave 41 se coloca después del elemento con clave 81, y el elemento con clave 79 se coloca después del elemento con clave 59.

Tareas individuales

1. Árboles binarios. Usando el programa de sensor de números aleatorios, obtenga 10 valores del 1 al 99 y construya un árbol binario.

Haz un desvío:

1.a Recorrido de izquierda a derecha: Izquierda-Raíz-Derecha: primero visitamos el subárbol izquierdo, luego la raíz y finalmente el subárbol derecho.

(O viceversa, de derecha a izquierda: Derecha -Raíz- Izquierda)

1.b Recorrido de arriba a abajo: Raíz-Izquierda-Derecha: visitamos la raíz de los subárboles.

1.c Recorrido de abajo hacia arriba: Raíz izquierda-derecha: visita la raíz después de los subárboles

Métodos para comprimir datos convertidos basados ​​en funciones Hash unidireccionales

Una función hash (hash, función hash) es una transformación que obtiene un cierto valor (convolución) de una longitud fija a partir de datos de longitud arbitraria. Los ejemplos más simples son las sumas de verificación (por ejemplo, crc32). Hay:

· hashes criptográficos;

· hashes del programador.

Un hash criptográfico se diferencia de un hash de programador en las dos propiedades siguientes: irreversibilidad y ausencia de colisiones. Denotemos:

metro- datos iniciales,

h(m) es una función hash de ellos.

Irreversibilidad significa que si se conoce el número h0, entonces es difícil elegir m tal que h(m) = h0.

Libre de colisiones significa que es difícil encontrar m1 y m2 de modo que m1 no sea igual a m2, sino h(m1) = h(m2).

Las funciones hash criptográficas se dividen en dos clases:

Funciones hash sin clave (códigos MDC (código de detección de modificación (manipulación)),

Funciones hash con una clave (códigos MAC (Código de autenticación de mensajes)).

Las funciones hash sin clave se dividen en dos subclases: funciones hash débiles y funciones hash fuertes.

Una función hash débil es una función unidireccional H(x) que satisface las siguientes condiciones:

1. el argumento x puede ser una cadena de bits de longitud arbitraria;

En segundo lugar, el valor de h (x) debe ser una cadena de bits de longitud fija;

3. el valor de h(x) es fácil de calcular;

4. para cualquier x fijo es computacionalmente imposible encontrar otro x" ≠ x tal que h(x")=h(x).

El par x" ≠ x cuando h(x")=h(x) se denomina colisión de función hash.

Una función hash fuerte es una función unidireccional h(x) que satisface las condiciones 1 a 4 para una función hash débil y la propiedad 5:

5. Es computacionalmente imposible encontrar cualquier par x" ≠ x tal que h(x")=h(x).
Dado que de las propiedades 1-2 se deduce que el conjunto de definiciones de una función hash es mucho más amplio que el conjunto de valores, deben existir colisiones. La propiedad 4 requiere que los encuentres para valor ajustado x era casi imposible. El requisito 5 dice que es computacionalmente imposible que una función hash fuerte encuentre cualquier colisión.

Existen varios algoritmos para calcular funciones hash.

MD2 (Message Digest) es un algoritmo de reducción criptográfica. Produce un bloque de 128 bits a partir de un mensaje de longitud arbitraria. Esquema general MD2 funciona:

a. rellenar el texto del mensaje hasta una longitud que sea múltiplo de 128 bits;

b. cálculo de una suma de comprobación de 16 bits, se descartan los bits más significativos;

C. agregar una suma de verificación al texto;

d. recalcular la suma de control.

El algoritmo MD2 es muy lento, por lo que se utilizan con mayor frecuencia MD4, MD5, SHA (Secure Hash Algorithm). El hash resultante tiene una longitud de 160 bits.

GOST R34.11-94. Algoritmo ruso. La longitud de la convolución es de 256 bits (muy conveniente para generar una clave para GOST 28147-89 mediante una contraseña).

El Instituto Nacional de Estándares y Tecnología de EE. UU. (NIST) en su sitio web http://www.nist.gov/sha/ publicó especificaciones para los nuevos algoritmos hash SHA-256, SHA-384 y SHA-512, cuyo propósito es para proporcionar un nivel de solidez criptográfica hash, correspondiente a las longitudes de clave del nuevo estándar de cifrado DES.

Recuerde que un hash de n bits es una asignación de un mensaje de longitud arbitraria a un hash de n bits. secuencia pseudoaleatoria(valor hash). Hash criptográfico como variedad especial dicha función es un hash de n bits que tiene las propiedades de "unidireccionalidad" y "resistencia a colisiones".

Hasta ahora, las funciones hash más populares han sido MD4 y MD5, creadas por Raivist, que generan códigos hash de longitud n=128, y el algoritmo SHA-1, desarrollado por la NSA estadounidense, que genera códigos hash de longitud n=160. .

GOST R34.10-94 “Procedimientos para el desarrollo y verificación de dispositivos electrónicos firma digital basado en un algoritmo criptográfico asimétrico."