Codificadores.

Scramblers.

Último Con el tiempo, el ámbito de aplicación de los algoritmos de codificación ha disminuido significativamente.

Esto se debe principalmente a una disminución en el volumen de transmisión secuencial de información bit a bit, para cuya protección se desarrollaron estos algoritmos.

En los sistemas modernos, casi en todas partes existen redes con conmutación de paquetes, que utiliza cifrados en bloque para mantener la confidencialidad.

Y su potencia criptográfica supera, y a veces de manera bastante significativa, la potencia criptográfica de los codificadores.

La esencia de la codificación es un cambio bit a bit en el flujo de datos que pasa por el sistema. Casi la única operación utilizada en los codificadores es XOR — «OR exclusivo bit a bit».

Paralelamente al paso del flujo de información en el codificador, de acuerdo con una determinada regla, se genera un flujo de bits: el flujo de codificación.

Tanto el cifrado directo como el inverso se llevan a cabo aplicando XOR a la secuencia de codificación. sobre el original.

La generación de la secuencia de bits de codificación se produce cíclicamente a partir de una pequeña cantidad inicial de información: la clave según el siguiente algoritmo.

Los valores de ciertos los bits se seleccionan del conjunto actual de bits y se agregan mediante XOR entre sí.

Todos los bits se desplazan 1 bit y el valor recién recibido («0» o «1») se coloca en el bit menos significativo liberado. El valor que estaba en el bit más significativo antes del cambio se agrega a la secuencia de codificación, convirtiéndose en su siguiente bit (ver Fig. 1).

De la teoría de la transmisión de datos, la criptografía tomó prestado un sistema de registro binario para registrar dichos esquemas. Según él, el codificador que se muestra en la figura se escribe con la combinación «100112 » – las unidades corresponden a los bits de los cuales se eliminan bits para formar retroalimentación.

Considere un ejemplo de codificación de la secuencia de información 0101112 mediante un codificador 1012 con una clave inicial de 1102.

Como puede ver, el dispositivo codificador es extremadamente simple. Su implementación es posible tanto de forma electrónica como eléctrica, lo que aseguró su uso generalizado en condiciones de campo. Además, el hecho de que cada bit de la secuencia de salida dependa de un solo bit de entrada fortalece aún más la posición de los codificadores en la protección de la transmisión de datos. Esto se debe al ruido que inevitablemente surge en el canal de transmisión, que puede distorsionar en este caso sólo los bits sobre los que caen, y no el grupo de bytes asociados a ellos, como es el caso de los cifrados en bloque.

La decodificación de secuencias codificadas se produce según el mismo esquema que la codificación. Para ello se utiliza en los algoritmos la codificación «OR exclusiva» – un esquema que puede restaurarse de forma única durante la decodificación sin ningún coste computacional adicional. Decodifiquemos el fragmento resultante.

Como puedes adivinar, el principal problema con los cifrados basados ​​en codificadores — sincronización de dispositivos transmisores (codificadores) y receptores (decodificadores). Si se omite o se inserta incorrectamente incluso un bit, toda la información transmitida se pierde irreversiblemente.

Por lo tanto, en los sistemas de cifrado basados ​​en codificadores, se presta gran atención a los métodos de sincronización.

En la práctica, se suele utilizar una combinación de dos métodos para estos fines:

a) añadir sincronización bits al flujo de información conocido de antemano por el lado receptor, lo que le permite, si no se encuentra dicho bit, comenzar a buscar activamente la sincronización con el remitente, y

b) el uso de generadores de impulsos temporales de alta precisión, que permiten, en momentos de pérdida de sincronización, decodificar los bits de información recibidos «de la memoria» sin sincronización.

El número de bits cubiertos por la retroalimentación, es decir, la capacidad del dispositivo de memoria para los bits que generan la secuencia de codificación, se denomina capacidad del codificador. El codificador que se muestra arriba tiene un ancho de bit de .

En términos de parámetros de seguridad criptográfica, este valor es completamente idéntico a la longitud de la clave de los cifrados de bloque, que se analizará más a fondo. En esta etapa, es importante tener en cuenta que cuanto mayor sea la capacidad de bits del codificador, mayor será la solidez criptográfica del sistema en función de su uso.

Si el codificador funciona durante un tiempo suficientemente largo, inevitablemente se repetirá. Después de completar un cierto número de ciclos de reloj, se creará una combinación de bits en las celdas del codificador, que ya apareció en ella una vez, y a partir de ese momento la secuencia de codificación comenzará a repetirse cíclicamente con un período fijo.

Este problema es insuperable por su naturaleza, ya que los N bits del codificador no pueden contener más de 2N combinaciones de bits y, por lo tanto, después de un máximo de 2N-1 ciclos, definitivamente se producirá una repetición de la combinación.

Combinación « todos ceros» se excluye inmediatamente de la cadena del gráfico de estado del codificador: lleva al codificador a la misma posición «todo ceros». Esto también indica que la clave «todos ceros» no aplicable para scrambler.

Cada bit generado durante el cambio depende sólo de unos pocos bits de la combinación actualmente almacenada por el codificador. Por lo tanto, después de repetir una determinada situación que ya se ha encontrado una vez en el codificador, todos los que la sigan repetirán exactamente la cadena que ya pasó previamente en el codificador.

Son posibles varios tipos de gráficos de estado del codificador .

En la Figura 2 se muestran opciones de ejemplo para un codificador de 3 bits.

En el caso de «A» excepto por el bucle siempre presente «000»>>»000″ Vemos dos ciclos más, con 3 estados y 4. En caso «B» vemos una cadena que converge a un ciclo de 3 estados y nunca sale de allí.

Y finalmente, en el caso de «B» todos los estados posibles excepto cero se combinan en un ciclo cerrado.

Es obvio que en este caso, cuando todos los 2N-1 estados del sistema forman un ciclo, el período de repetición de las combinaciones de salida es máximo, y En la correlación entre la duración del ciclo y el inicial no existe ningún estado del codificador (clave), lo que daría lugar a la aparición de claves más débiles.

Fig. 2.

Y aquí está el las matemáticas presentaron otro regalo a la ciencia aplicada, que es la criptografía.

Un corolario de uno de los teoremas demuestra (en términos de codificación) que para un codificador de cualquier tamaño de bits N siempre existe la posibilidad de elegir bits cubiertos por retroalimentación de que la secuencia generada por ellos tendrá un período igual a 2N-1 bits.

Entonces, por ejemplo, en un codificador de 8 bits, cuando se cubren los bits 0, 1, 6 y 7, durante el tiempo de generación de 255 bits, todos los números del 1 al 255 se pasan secuencialmente sin repetirse ni una sola vez.

Los circuitos con realimentación seleccionados según esta ley se denominan generadores de secuencias de mayor longitud (GLP) y se utilizan en equipos de codificación.

De una variedad de generadores PND de un tamaño de bit determinado, en el momento en que se implementaron de forma eléctrica o electrónica mínima, se seleccionaron aquellos cuyo número de bits involucrados en la creación del siguiente bit era mínimo. Normalmente, era posible llegar al generador PND en 3 o 4 comunicaciones.

La capacidad de bits del codificador excedía los 30 bits, lo que hacía posible transmitir hasta 240 bits = 100 MB de información sin temor a comenzando a repetir la secuencia de codificación.

Los PND están indisolublemente ligados a la teoría matemática de los polinomios irreducibles. Resulta que es suficiente que un polinomio de grado N no sea representable módulo 2 como producto de cualquier otro polinomio para que un codificador construido sobre su base cree un PND.

Por ejemplo, el único irreducible polinomio de grado 3 es x3 +x+1, en binario se escribe 10112 (los unos corresponden a los bits presentes).

Los codificadores basados ​​en polinomios irreducibles se forman descartando el bit más significativo (que siempre está presente y, por lo tanto, contiene información solo sobre el grado del polinomio), por lo que, basándose en el polinomio especificado, podemos crear un codificador 0112 con un período de ciclo de 7 (= 23-1).

Naturalmente, en la práctica se utilizan polinomios de órdenes mucho más elevados. Y siempre se pueden encontrar tablas de polinomios irreducibles de cualquier orden en libros de referencia matemáticos especializados.

Una desventaja importante de los algoritmos de codificación es su inestabilidad ante la falsificación. Este problema se analiza con más detalle en la próxima conferencia, en relación con la creación de criptosistemas completos.