Hogar › Servicios › Usando generadores de números pseudoaleatorios. Generadores de números pseudoaleatorios. Método del producto medio

Usando generadores de números pseudoaleatorios. Generadores de números pseudoaleatorios. Método del producto medio

Generadores de secuencias pseudoaleatorias

En la práctica, una de las más importantes es la siguiente tarea. Con base en lo anterior y otras propiedades del RRSP, es necesario determinar si una secuencia particular es una implementación del RRSP. En lo que sigue, en aras de la brevedad, simplemente llamaremos a la implementación del RRSP una secuencia aleatoria.

Blum, Goldwasser, Micalli y Yao propusieron un enfoque constructivo para definir una secuencia aleatoria. Su definición considera que una secuencia es aleatoria a menos que exista un algoritmo polinómico (probabilístico) que pueda distinguirla de la aleatoriedad pura. Esta secuencia se llama polinomialmente indistinguible de aleatorio o pseudoaleatorio.

Este enfoque le permite utilizar secuencias pseudoaleatorias (PSR) para generar determinista algoritmos implementados máquinas de estados finitos. Aunque desde un punto de vista matemático tales secuencias no son aleatorias, ya que están completamente determinadas por el llenado inicial, sin embargo, su uso práctico no proporciona ninguna ventaja al criptoanalista debido a su "indistinguibilidad" de los aleatorios. Dado que este enfoque parece más constructivo, nos detendremos en él con más detalle.

Secuencias aleatorias en el sentido última definición También llamado "aleatorio para todos los usos prácticos". Los generadores de tales secuencias se denominan criptográficamente seguros ( criptográficamente fuerte) o criptográficamente seguro ( criptográficamente seguro). Pseudoaleatoriedad en en este caso no es sólo una propiedad de la secuencia (o generador), sino también una propiedad del observador, o más bien de sus capacidades computacionales.

Se han demostrado dos afirmaciones importantes para PSP:

1. Una secuencia es pseudoaleatoria si y sólo si imprevisible, es decir. resiste las pruebas con la siguiente broca. Esto significa que incluso si se conoce parte de una secuencia de cualquier longitud, si se desconocen el llenado inicial del generador y los parámetros del algoritmo de generación, es imposible proponer un algoritmo que sea significativamente mejor que simplemente adivinar o lanzar un algoritmo. moneda para obtener el siguiente bit.

2. Los generadores criptográficamente fuertes existen si y sólo si hay funciones que son fácilmente computables, pero computacionalmente difíciles de invertir (funciones unidireccionales - funciones unidireccionales). En este caso, a cada generador de PSP se le puede asignar una correspondencia uno a uno con una determinada función unidireccional, que depende de ciertos parámetros.

El sensor más simple números pseudoaleatorios es generador lineal congruente(LKG), que se describe mediante una ecuación recurrente de la forma X norte =(aX n -1 +b) modo N, Dónde X0- valor inicial aleatorio, A– multiplicador, b– incremento, norte– módulo.

El período de la secuencia de salida de dicho generador no excede norte, el valor máximo se logra con la elección correcta de los parámetros a,b,norte, es decir, cuando

· números norte Y b coprimo: MCD(N,b)=1);

· a-1 múltiplo de cualquier primo pag, dividiendo norte;

· a-1 múltiple 4 , Si norte múltiple 4 .

A continuación se muestra una lista de constantes para LKG que proporcionan periodo máximo secuencias y, lo que es igualmente importante, las secuencias correspondientes pasan pruebas estadísticas.

Para implementar LKG en computadoras personales teniendo en cuenta su cuadrícula de bits, el módulo se utiliza a menudo N=2 31 -1»2.14×10 9. En este caso, las propiedades estadísticas de más alta calidad del PSP se logran para la constante a=397204094.

Comparado con otros tipos de generadores de PSP este tipo proporciona un alto rendimiento debido a la pequeña cantidad de operaciones para crear un bit pseudoaleatorio.

La desventaja de los LCG en términos de su uso para crear cifrados de flujo es la previsibilidad de las secuencias de salida. Se han propuesto ataques efectivos contra LKG. Joan Boyar, ella posee métodos de ataques a cuadráticos. X n =(aX n -1 2 +bX n -1 +c)modNy cúbico ‑ X n =(aX n -1 3 +bX n -1 2 +cX n -1 +d)modN generadores.

Otros investigadores han resumido los resultados del trabajo. Boyardo para el caso de un generador polinomial congruente general. Popa Y Boyardo mostró cómo descifrar el LKG, aunque no se conoce la secuencia completa.

Wishmann Y Colina, y más tarde Pierre L'Écuger combinaciones estudiadas de LCH. Los resultados no son criptográficamente más sólidos, pero tienen períodos más largos y se comportan mejor bajo algunos criterios de aleatoriedad.

Registros de desplazamiento de retroalimentación lineal (Registros de desplazamiento de retroalimentación lineal - LFSR) incluyen el propio registro de desplazamiento y el circuito de cálculo de funciones comentario (secuencia de toque) – ver fig. 12:

flujo de bits

norte

∙∙∙

Arroz. 2. Registro de desplazamiento con retroalimentación lineal ( LFSR)

En el diagrama, el contenido del registro, una secuencia de bits, se desplaza con la llegada de un pulso de reloj ( pulso de reloj) un lugar a la derecha. El bit menos significativo se considera la salida. LFSR en este ciclo de trabajo. El valor del dígito más significativo es el resultado de la suma de mod2(Función XOR) bits de retroalimentación.

Teóricamente, norte-poco LFSR puede generar una secuencia pseudoaleatoria con un punto 2n-1 poco, tal LFSR se denominan registros de período máximo. Para hacer esto, el registro de turnos debe visitar todos 2n-1 estados internos ( 2n-1, porque llenar el registro de desplazamiento con cero provocará una secuencia infinita de ceros).

Recordemos que un polinomio se dice irreducible si no puede expresarse como producto de otros polinomios de menor grado distintos de 1 y de sí mismo.

Polinomio primitivo grados norte es un polinomio irreducible que divide pero no divide xd +1 para cualquiera d: (2n-1│d)

Teorema(sin prueba): Para que el LFSR tenga un período máximo, es necesario y suficiente que el polinomio formado a partir de los elementos de retroalimentación ( secuencia de toque) más uno era un polinomio primitivo módulo 2. (De hecho, un polinomio primitivo es un generador en un campo determinado).

En se proporciona una lista de polinomios primitivos prácticamente aplicables.

Por ejemplo, un polinomio primitivo es x 32 x 7 x 5 x 3 x 2 x1. Registro ( 32,7,5,3,2,1,0 ) significa que al tomar un registro de desplazamiento de 32 bits y generar un bit de retroalimentación sumando mod2 7º, 5º, 3º, 2º y 1º bits, obtenemos LFSR longitud máxima (con 2 32 -1 estados).

Tenga en cuenta que si pag(x) es un polinomio primitivo, entonces xn×p(1/x)– también primitivo.

Por ejemplo, si el polinomio (a,b,0) primitivo, entonces (a,a-b,0)– primitivo. Si un polinomio (a,b,c,d,0) primitivo, entonces (a,a-d,a-c,a-b,0)– primitivo, etc.

Los trinomios primitivos son especialmente convenientes porque Sólo se añaden 2 bits del registro de desplazamiento, pero también son más vulnerables a los ataques.

LFSR– convenientes para la implementación técnica, pero tienen propiedades desagradables. Los bits consecutivos son linealmente dependientes, lo que los hace inútiles para el cifrado. Incluso si se desconoce el circuito de retroalimentación, es suficiente 2n bits de salida para determinarlo.

Grandes números aleatorios generados a partir de bits secuenciales LFSR, están altamente correlacionados y, a veces, ni siquiera son completamente aleatorios. Sin embargo, LFSR Se utilizan con bastante frecuencia como elementos de algoritmos más complejos para generar una secuencia de claves de cifrado.

También hay una serie de generadores de PSP (incluidos los generadores de números de Fibonacci) que, por diversas razones, no se han encontrado. amplia aplicación en sistemas criptográficos. Mayoría soluciones efectivas se obtuvieron sobre la base de generadores compuestos.

La idea de construir un generador compuesto se basa en que una combinación de dos o más generadores simples PSP, en caso de elección correcta de la función de combinación (incl. mod 2, modo 2 32 -1 etc.), proporciona un generador con propiedades de aleatoriedad mejoradas y, como resultado, con una mayor solidez criptográfica.

En el caso de crear un generador PSP criptográficamente fuerte, el problema de crear cifrados de flujo simplemente se resuelve. El resultado de dicho PSP es indistinguible (o más bien, debería ser indistinguible) del RRSP. Siempre se pueden iniciar dos generadores de forma sincrónica desde un único vector de estado inicial, que es mucho más corto. mensaje transmitido, que distingue este esquema del cifrado Vernam.

Hay 4 enfoques conocidos para diseñar generadores apropiados:

1) enfoque teórico de sistemas;

2) enfoque teórico de la complejidad;

3) enfoque teórico de la información;

4) enfoque aleatorio.

Estos enfoques difieren en sus suposiciones sobre las capacidades del criptoanalista, la definición de éxito criptográfico y el concepto de confiabilidad.

En caso enfoque teórico del sistema el criptógrafo crea un generador de flujo de claves que tiene propiedades verificables, incluida la duración del período de la secuencia de salida, la distribución estadística del flujo de bits, la complejidad lineal de la transformación, etc. Teniendo en cuenta las técnicas de criptoanálisis conocidas, el criptógrafo optimiza el generador contra estos ataques.

Basándose en este enfoque, Rüppel formuló el siguiente conjunto de criterios para cifrados de flujo:

1. Largo período de secuencia de salida, sin repeticiones;

2. Alta complejidad lineal, como característica de nuestro generador a través de un registro LFSR la longitud mínima que puede generar el mismo resultado;

3. Indistinguibilidad del RRSP según criterios estadísticos;

4. Mezclar: cualquier bit del flujo de claves debe ser una transformación compleja de todos o la mayoría de los bits del estado inicial (clave);

5. Disipación: se debe disipar la redundancia en todas las subestructuras del algoritmo generador;

6. Criterios para la no linealidad de las transformaciones: de acuerdo con una determinada métrica, la distancia a las funciones lineales debe ser suficientemente grande, el criterio para la propagación de cambios en forma de avalancha en el caso de un cambio de un bit, etc.

La práctica confirma la conveniencia de aplicar los criterios especificados no sólo para el análisis y evaluación de cifrados de flujo creados en el marco de un enfoque teórico de sistemas, sino también para cualquier cifrado de flujo y de bloque.

El principal problema de estos criptosistemas es que les resulta difícil demostrar algún hecho sobre su solidez criptográfica, ya que para todos estos criterios no se ha demostrado su necesidad o suficiencia. Un cifrado de flujo puede satisfacer todos estos principios y aún así ser débil porque La resistencia a un determinado conjunto de ataques criptoanalíticos no garantiza nada.

Un ejemplo de una construcción exitosa de un generador compuesto desde el punto de vista de una complejidad lineal creciente es la cascada de Goleman (Fig. 3).

La etapa de Goleman incluye varios registros LFSR y el momento de cada siguiente LSFR controlado por el anterior para que el estado cambie LFSR-(k+1) en el momento t ocurre si en el paso anterior t-1 salida LFSR-k es igual a 1, y LFSR-(k+1) no cambia su estado de lo contrario.

si todo LFSR– longitudes yo, entonces la complejidad lineal del sistema con norte registros iguales yo×(2 yo-1)n-1.

X(t)

LFSR-2

LFSR-3

Tacto

Arroz. 4. Generador alternante start-stop

Este generador tiene un período largo y una alta complejidad lineal.

Aplicando enfoque teórico de la complejidad, el criptógrafo está intentando demostrar la solidez del generador utilizando la teoría de la complejidad. La base de las soluciones en este enfoque son los generadores basados en el concepto función unidireccional.

Función unidireccional F(incógnita): D→R fácil de calcular para todos x О D, pero es muy difícil invertir para casi todos los valores de R. De lo contrario, si V es la complejidad computacional de obtener F(incógnita), y V * es la complejidad computacional de encontrar f-1(incógnita), entonces se cumple la desigualdad V * >>V. Es fácil ver que una función de potencia en algún campo finito puede ser candidata para una función unidireccional. F(incógnita)=una x, Dónde a,xОGF(q)– Campo de Galois desde q elementos.

Es fácil ver que la multiplicación, debido a la propiedad de asociatividad, se puede realizar en menos que el número x-1 pasos. Por ejemplo, a 9 =a×((a 2) 2) 2, que le permite calcular el grado requerido en lugar de ocho en cuatro pasos (primero un 2 = un × un, entonces un 4 = un 2 un 2, un 8 = un 4 un 4 y finalmente un 9 = un 8 un).

La operación inversa es encontrar el exponente a partir del valor. función de potencia(logaritmo): en un campo finito aún no se puede resolver mejor que utilizando métodos de fuerza bruta optimizados opciones posibles. En caso gran tamaño campos (de orden 2 1024 )esta tarea es desarrollo moderno equipo de computacion computacionalmente intratable.

Un ejemplo de un generador correspondiente es el algoritmo. RSA. Deja que el parámetro N=p×q, Dónde p,q– números primos, valor inicial del generador x0 norte, mi: MCD( mi,(p-1)×(q-1))=1.

x i+1 =x e i mod N

El resultado del generador es el más pequeño. poco significativo xyo+1. La durabilidad de este generador es equivalente a la durabilidad RSA. Si norte Lo suficientemente grande, el generador proporciona una durabilidad práctica.

Se propone otro ejemplo de un generador basado en un enfoque de complejidad. Floración, Floración Y Shub (BBS). En en este momento Este es uno de los más simples y algoritmos eficientes. La teoría matemática de este generador es de residuos de módulo cuadrático. norte.

Elijamos dos números primos grandes. pag Y q, dando el resto 3 al dividirlo por 4. Producto norte pagq Llamémoslo el número de Bloom. elijamos incógnita: MCD( n,x)=1. Encontremos el valor inicial del generador: x 0 = x 2 modo sustantivo.

Ahora i El enésimo número pseudoaleatorio es el bit menos significativo xyo, Dónde x i = x 2 i -2 mod n.

Tenga en cuenta que para obtener i-º bit, no se requiere cálculo ( yo-1) estados. si sabemos p, q, entonces podemos calcularlo inmediatamente: b yo es el valor de bit más pequeño:

Esta propiedad le permite utilizar BBS- generador para trabajar con archivos de acceso aleatorio ( acceso aleatorio).

Número norte se puede distribuir libremente para que cada suscriptor de la red pueda generar de forma independiente los bits necesarios. Además, si el criptoanalista no puede factorizar el número norte, no podrá predecir el siguiente bit, ni siquiera en un sentido probabilístico, como "hay un 51% de posibilidades de que el siguiente bit sea 1".

Nota; que los generadores construidos con funciones unidireccionales son muy lentos para su implementación práctica Se requieren procesadores especiales.

Los dos próximos enfoques información teórica y aleatoria no han encontrado una aplicación práctica generalizada.

Desde el punto de vista teórico de la información lo mas el mejor remedio en la lucha contra un criptoanalista que tiene tiempo y recursos informáticos infinitos, es una cinta de un solo uso o una libreta de un solo uso.

En caso aleatorio En este enfoque, el objetivo es aumentar el número de bits con los que el criptoanalista necesita trabajar (sin aumentar la clave). Esto se puede lograr mediante el uso de grandes cadenas públicas aleatorias. La clave indicará qué partes de estas cadenas deben usarse para el cifrado y descifrado. Entonces el criptoanalista deberá utilizar el método de enumeración total de opciones ( fuerza bruta) en líneas aleatorias.

La fortaleza de este método se puede expresar en términos del número promedio de bits que un criptoanalista tendría que examinar antes de que las posibilidades de determinar la clave sean mejores que las simples conjeturas.

Ueli Maurer describió tal esquema. La probabilidad de romper dicho criptosistema depende de la cantidad de memoria disponible para el criptoanalista (pero no depende de sus recursos informáticos).

Para que este esquema adopte una forma práctica, se requieren aproximadamente 100 secuencias de bits. 10 20 mordisco cada uno. Digitalizar la superficie lunar es una forma de obtener tal cantidad de bits.

En conclusión, observamos que para construir un generador de PSP es necesario obtener algunos bits aleatorios. La forma más sencilla es utilizar el bit menos significativo del temporizador de la computadora.

Usando este método, no puedes recibir muchos bits, porque Cada llamada al procedimiento de generación de bits puede tardar número par pasos del temporizador, lo que sin duda afectará las propiedades de la secuencia.

Mayoría mejor manera conseguir numero aleatorio- esto es para apelar al azar natural mundo real– ruido como resultado procesos transitorios V diodos semiconductores, ruido térmico de resistencias altas, desintegración radiactiva, etc. En principio, existe un elemento de aleatoriedad en las computadoras:

Hora del día;

carga de CPU;

Hora de llegada de paquetes de red, etc.

El problema no es encontrar las fuentes de la aleatoriedad, sino mantener la aleatoriedad en las mediciones.

Por ejemplo, esto se puede hacer así: busquemos un evento que ocurra regularmente, pero de forma aleatoria (el ruido excede un cierto umbral). Midamos el tiempo entre el primer evento y el segundo, luego entre el segundo y el tercero. Si t 1.2  t 2.3, luego igualamos la salida del generador a 1; Si t 1,2 < t 2.3, entonces la salida es 0. Continuaremos el proceso.

El Instituto Nacional Estadounidense de Estándares (ANSI) ha desarrollado un método para generar claves de 64 bits utilizando el algoritmo DES (ANSI X9.17). Su objetivo principal es obtener gran cantidad claves para múltiples sesiones de comunicación. En lugar del algoritmo DES, puede utilizar cualquier otro algoritmo de cifrado potente.

Deje que la función E K (P) cifre P usando el algoritmo DES en una clave K preparada previamente, que se usa solo para generar claves secretas. A continuación, sea V 0 el valor inicial de 64 bits que se mantiene en secreto para el enemigo, y Ti representa la marca de fecha y hora cuando el enemigo i-ésima clave. Luego el siguiente clave aleatoria R i se calcula mediante la transformación:

R yo = E K (E K (T yo) Å V yo)

Para obtener el siguiente valor de V i, es necesario calcular

V i = E K (E K (T i) Å R i)

Un problema importante con los sistemas de generación de datos aleatorios es la presencia de desviaciones y correlaciones en la secuencia generada. Los procesos en sí pueden ser aleatorios, pero pueden surgir problemas durante el proceso de medición. ¿Cómo lidiar con esto?

1) Adición por mod 2 dos secuencias independientes: si un bit aleatorio se desplaza a 0 la cantidad ε , entonces la probabilidad de que ocurra 0 se puede escribir como P(0)=0,5+ε.

Adición por mod 2: dos bits independientes igualmente distribuidos darán: P(0)=(0.5 +e) 2+(0,5-ε) 2=0.5 +2×ε 2 , sumando cuatro bits obtenemos: PAG(0)=0.5+8 ε 4, etc El proceso converge a una distribución equiprobable de 0 y 1.

2) Sea la distribución de unos y ceros en la secuencia las cantidades pag Y q respectivamente. Usemos el método de codificación: considere dos bits:

Si estos son los mismos bits, deséchelos y considere próxima pareja;

Si los bits son diferentes, tomamos el primer bit como valor de salida.

este método le permite resolver el problema del sesgo preservando al mismo tiempo las propiedades de aleatoriedad de la fuente (con cierta pérdida en el volumen de datos).

Problema potencial El problema con ambos métodos es que si existe una correlación entre bits adyacentes, estos métodos aumentan el desplazamiento. Una forma de evitar esto es utilizar diferentes fuentes de números aleatorios.

El hecho de que un generador de números aleatorios tenga un sesgo, en términos generales, no significa que sea inadecuado. Por ejemplo, para generar una clave de 112 bits para el algoritmo "triple" DES(DES triple) se utiliza un generador con tendencia a cero: P(xt=0)=0,55, P(xt=1)=0,45(entropía norte= 0,99277 por bit de clave en comparación con 1 para un generador ideal).

En este caso, el atacante puede optimizar el procedimiento de búsqueda total de claves buscando la clave comenzando por el valor más probable ( 00…0 ) y terminando con el menos probable ( 11…1 ). Debido a la presencia de sesgo, se puede esperar encontrar la clave en un promedio de 2 109 intentos. Si no hubiera desplazamiento, entonces sería necesario 2 111 intentos. Hay una ganancia, pero es insignificante.

algoritmo de generación de números pseudoaleatorios llamado algoritmo BBS(de los apellidos de los autores: L. Blum, M. Blum, M. Shub) o generador con resto cuadrático. Para fines criptográficos, este método se propuso en 1986.

Es el siguiente. Primero, se seleccionan dos números primos grandes 1. Un número entero positivo mayor que uno se llama simple, si no es divisible por ningún otro número excepto por sí mismo y por uno. Para obtener más información sobre los números primos, consulte Fundamentos de la teoría de números utilizados en la criptografía de clave pública. números p y q. Los números p y q deben ser ambos comparable de 3 módulo 4, es decir, cuando pyq se dividen entre 4, se debe obtener el mismo resto 3. A continuación se calcula el número M = p* q, llamado entero de Bloom. Luego se elige otro entero aleatorio x que sea coprimo (es decir, que no tenga más divisores comunes que uno) con M. Calculamos x0= x 2 mod M. x 0 se llama número inicial del generador.

En cada enésimo paso de la operación del generador, se calcula x n+1 = x n 2 mod M. El resultado del enésimo paso es un bit (normalmente el menos significativo) del número x n+1. A veces se toma como resultado el bit de paridad, es decir, el número de unos en representación binaria elemento. Si el número de unos en el registro numérico es par, el bit de paridad se toma igual a 0, si el número de unos es impar, el bit de paridad se toma igual a 1.

Por ejemplo, sea p = 11, q = 19 (nos aseguramos de que 11 mod 4 = 3, 19 mod 4 = 3). Entonces M = p* q = 11*19=209. Elijamos x que sea coprimo con M: sea x = 3. Calculemos el número inicial del generador x 0:

x 0 = x 2 mod M = 3 2 mod 209 = 9 mod 209 = 9.

Calculemos los primeros diez números x i usando el algoritmo BBS. Como bits aleatorios tomaremos el bit menos significativo en notación binaria números x i:

x 1 =9 2 mod 209 = 81 mod 209 = 81	bit menos significativo:	1
x 2 =81 2 mod 209 = 6561 mod 209 = 82	bit menos significativo:	0
x 3 =82 2 mod 209 = 6724 mod 209 = 36	bit menos significativo:	0
x 4 =36 2 mod 209 = 1296 mod 209 = 42	bit menos significativo:	0
x 5 =42 2 mod 209 = 1764 mod 209 = 92	bit menos significativo:	0
x 6 =92 2 mod 209 = 8464 mod 209 = 104	bit menos significativo:	0
x 7 =104 2 mod 209 = 10816 mod 209 = 157	bit menos significativo:	1
x 8 =157 2 mod 209 = 24649 mod 209 = 196	bit menos significativo:	0
x9 =196 2 mod 209 = 38416 mod 209 = 169	bit menos significativo:	1
x 10 =169 2 mod 209 = 28561 mod 209 = 137	bit menos significativo:	1

La propiedad más interesante de este método a efectos prácticos es que para obtener el enésimo número de la secuencia, no es necesario calcular todos los n números anteriores x i. Resulta que x n se puede obtener inmediatamente usando la fórmula

Por ejemplo, calculemos x 10 directamente a partir de x 0:

Como resultado, obtuvimos el mismo valor que en el cálculo secuencial: 137. Los cálculos parecen bastante complejos, pero en realidad son fáciles de formular en un pequeño procedimiento o programa y utilizarlos cuando sea necesario.

La capacidad de obtener xn "directamente" le permite utilizar el algoritmo BBS para cifrar transmisiones, por ejemplo, para archivos de acceso aleatorio o fragmentos de archivos con registros de bases de datos.

La seguridad del algoritmo BBS se basa en la dificultad de factorizar un número grande M. Se argumenta que si M es lo suficientemente grande, ni siquiera es necesario mantenerlo en secreto; Hasta que se factorice M, nadie puede predecir la salida del generador PNG. Esto se debe al hecho de que la tarea de factorizar números de la forma n = pq (p y q son números primos) es computacionalmente muy difícil si sólo conocemos n, y p y q son números grandes que constan de varias decenas o centenas de bits ( este es el llamado problema de factorización).

Además, se puede demostrar que un atacante, conociendo una determinada secuencia generada por el generador BBS, no podrá determinar ni los bits anteriores ni los siguientes. Generador BBS impredecible en la dirección izquierda Y en la dirección correcta. Esta propiedad es muy útil para propósitos de criptografía y también está asociada con las características de factorizar el número M.

lo mas inconveniente significativo algoritmo es que no es lo suficientemente rápido, lo que no permite su uso en muchas áreas, por ejemplo, en cálculos en tiempo real y también, desafortunadamente, en cifrado de flujo.

Pero este algoritmo produce una secuencia realmente buena de números pseudoaleatorios con un período grande (con la elección adecuada parámetros iniciales), lo que permite su uso con fines criptográficos al generar claves de cifrado.

Términos clave

cifrado de flujo– cifrado de flujo.

algoritmo BBS– uno de los métodos para generar números pseudoaleatorios. El nombre del algoritmo proviene de los nombres de los autores: L. Blum, M. Blum, M. Shub. El algoritmo se puede utilizar en criptografía. Para calcular el siguiente número x n+1 usando el algoritmo BBS, use la fórmula x n+1 = x n 2 mod M, donde M = pq es el producto de dos números primos grandes py q.

Generador de números pseudoaleatorios (PRNG)- algún algoritmo o dispositivo que crea una secuencia de bits que parece aleatoria.

Generador lineal congruente números pseudoaleatorios: uno de los PRNG más simples, que para calcular el siguiente número k i usa la fórmula k i =(a*k i-1 +b)mod c, donde a, b, c son algunas constantes, a k i-1 es el el anterior número pseudoaleatorio.

Método de Fibonacci con rezagos– uno de los métodos para generar números pseudoaleatorios. Se puede utilizar en criptografía.

cifrado de flujo– un cifrado que cifra el mensaje de entrada un bit (o byte) por operación. Un algoritmo de cifrado de flujo elimina la necesidad de dividir un mensaje en un número entero de bloques. Los cifrados de flujo se utilizan para cifrar datos en tiempo real.

Breve resumen

Un cifrado de flujo es un cifrado que cifra un mensaje de entrada un bit (o byte) por operación. Un algoritmo de cifrado de flujo elimina la necesidad de dividir un mensaje en un número entero de bloques. Por lo tanto, si se transmite una secuencia de caracteres, cada carácter se puede cifrar y transmitir a la vez. Los cifrados de flujo se utilizan para cifrar datos en tiempo real.

Los programas informáticos a menudo requieren una emulación de la aleatoriedad. Por ejemplo, al desarrollar juegos. Si el programa tiene un determinado generador, es decir, un productor de un número aleatorio, entonces, utilizando el número obtenido de esta manera, puede seleccionar una u otra rama de ejecución del programa, o un objeto arbitrario de la colección. En otras palabras, lo principal es generar un número. En ello se basa la emulación de otro tipo de aleatoriedad.

Ciertamente no sabemos si existe aleatoriedad en la naturaleza o si sólo nos parece que se debe a las limitaciones de nuestro conocimiento. Sólo sabemos que no existe una verdadera aleatoriedad en la programación. No hay ningún lugar del que pueda surgir un número arbitrario; es imposible programar su aparición desde ningún lugar. Sólo puedes crear un programa que, como resultado de aplicar fórmula compleja al "grano" producirá un número, y nos parecerá que este número es aleatorio.

"Grano" son los datos de entrada para la fórmula. Podrían ser, por ejemplo, hora del sistema en milisegundos, que cambia constantemente. En consecuencia, el “grano” será constantemente diferente. O el programador puede configurarlo él mismo.

Un programa de este tipo (en realidad un módulo o función) se denomina generador de números pseudoaleatorios. Incluido en la biblioteca estándar. lenguaje pitón Incluye el módulo aleatorio. Contiene muchas funciones relacionadas con la emulación de la aleatoriedad (por ejemplo, "mezclar" elementos de una secuencia), y no solo funciones para generar números pseudoaleatorios.

Este tutorial cubrirá las funciones random(), randrange() y randint() del módulo aleatorio. Tenga en cuenta que el módulo aleatorio contiene la función aleatoria() del mismo nombre. Sucede.

Para acceder a las funciones, es necesario importar el módulo aleatorio:

>>> importar aleatoriamente

O importar funciones individuales de ello:

>>> desde importación aleatoria aleatoria, randrange, randint

Funciones para obtener números enteros "aleatorios": randint() y randrange()

Las funciones randint() y randrange() generan números enteros pseudoaleatorios. El primero de ellos es el más simple y siempre toma solo dos argumentos: los límites del rango entero del cual se selecciona cualquier número:

>>> aleatorio .randint (0, 10) 6

o (si se importaron funciones individuales):

>>> randint(100, 200) 110

En el caso de randint(), ambos límites están incluidos en el rango, es decir, en el lenguaje matemático, el segmento se describe como .

Los números pueden ser negativos:

>>> aleatorio .randint (-100, 10) -83 >>> aleatorio .randint (-100, -10) -38

Pero el primer número siempre debe ser menor o al menos igual al segundo. Es decir, un<= b.

La función randrange() es más compleja. Puede ser necesario un argumento, dos o incluso tres. Si solo se especifica uno, devuelve un número aleatorio entre 0 y el argumento especificado. Además, el argumento en sí no está incluido en el rango. En el lenguaje de las matemáticas, esto es Vi ] 2 Vi+1 = EDEK1,K2 [ EDEK1,K2 [ DTi] Ri]

El esquema implica el uso de una clave de 112 bits y tres cifrados EDE. Se proporcionan dos valores pseudoaleatorios como entrada: el valor de fecha y hora y el valor inicial de la iteración actual; la salida es el valor inicial para la siguiente iteración y el siguiente valor pseudoaleatorio; Incluso si el número pseudoaleatorio Ri está comprometido, no es posible calcular Vi+1 a partir de Ri en un tiempo razonable y, por tanto, el siguiente valor pseudoaleatorio Ri+1, ya que se realizan tres operaciones EDE adicionales para obtener Vi+. 1.

Hardware PRNG

Aparte del legado, los conocidos generadores LFSR que se utilizaron ampliamente como PRNG de hardware en el siglo XX, desafortunadamente, se sabe muy poco sobre los PRNG (cifrados de flujo) de hardware modernos, ya que la mayoría de ellos se desarrollaron con fines militares y se mantienen en secreto. . Casi todos los PRNG de hardware comercial existentes están patentados o se mantienen en secreto. Los PRNG de hardware están limitados por requisitos estrictos de memoria consumible (la mayoría de las veces el uso de memoria está prohibido), rendimiento (1-2 ciclos de reloj) y área (varios cientos de celdas FPGA o ASIC). Debido a requisitos tan estrictos para los PRNG de hardware, es muy difícil crear un generador a prueba de criptografía, razón por la cual todos los PRNG de hardware conocidos se han roto hasta ahora. Ejemplos de tales generadores son Toyocrypt y LILI-128, ambos generadores LFSR y ambos han sido descifrados mediante ataques algebraicos.

Debido a la falta de buenos PRNG de hardware, los fabricantes se ven obligados a utilizar los mucho más lentos pero conocidos cifrados de bloques (DES, AES) y funciones hash (SHA-1) disponibles en los modos de transmisión.

Tenga en cuenta que para crear RRSP, se utilizan tres tipos de generadores: tabulares, generadores físicos y generadores de PSP.

Un ejemplo de generador de tablas es una tabla de 106 dígitos aleatorios publicada en 1955 por Rand Corporation.

Los generadores físicos se han generalizado tras la creación de los microprocesadores, que son económicos y proporcionan un rendimiento suficiente. En la figura. La Figura 4.1 presenta un ORB generador físico de datos aleatorios, implementado por APA Consulting en un microcontrolador de la familia PIC12C67X (paquete SOIC de 8 pines, tamaño 5,3 x 8,1 mm).

Arroz. 4.1. Generador de números aleatorios ORB

El funcionamiento de este generador se basa en el principio de medir el voltaje en un condensador, que se carga y descarga de acuerdo con un determinado flujo de bits.

Los dos primeros tipos de generadores, además de buenas propiedades estadísticas, tienen una serie de desventajas, las principales de las cuales incluyen la complejidad de la implementación técnica, el bajo rendimiento y el alto costo.

Por estas razones, los generadores de PSP se han generalizado en el desarrollo de software y hardware para la protección de información criptográfica.

El sensor de números pseudoaleatorios de software más simple es generador lineal congruente(LKG), que se describe mediante una ecuación recurrente de la forma , donde
– valor inicial aleatorio, – multiplicador, – incremento,
– módulo.

El período de la secuencia de salida de dicho generador no excede
, el valor máximo se logra con la elección correcta de los parámetros
, es decir, cuando:

– números
Y son primos relativos: mcd
;

–
múltiplo de cualquier primo , dividiendo
;

–
divisible por 4 si
múltiplo de 4.

A continuación se muestra una lista de constantes para LCG que aseguran el período máximo de la secuencia y, igualmente importante, las secuencias correspondientes pasan pruebas estadísticas.

Para implementar LCG en computadoras personales, teniendo en cuenta su cuadrícula de bits, a menudo se usa el módulo

. En este caso, las propiedades estadísticas de más alta calidad del PSP se logran para la constante
.

En comparación con otros tipos de generadores de PSP, este tipo proporciona un alto rendimiento debido a la pequeña cantidad de operaciones para crear un bit pseudoaleatorio.

La desventaja de los LCG en términos de su uso para crear cifrados de flujo es la previsibilidad de las secuencias de salida.

Joan Boyar propuso ataques eficaces contra LKG.

Posee métodos de ataque a generadores cuadráticos y cúbicos: y.

Otros investigadores han generalizado el trabajo de Boyar al caso de un generador polinomial congruente general. Stern y Boyar mostraron cómo descifrar el LKG, aunque se desconoce la secuencia completa.

Wishmann y Hill, y más tarde Pierre L'Ecuger, estudiaron combinaciones de LCH. Las complicaciones no son criptográficamente más fuertes, pero tienen períodos más largos y se comportan mejor bajo algunos criterios de aleatoriedad.

Registros de desplazamiento de retroalimentación lineal(Registros de desplazamiento de retroalimentación lineal - LFSR) incluyen el registro de desplazamiento en sí y el circuito para calcular la función de retroalimentación (secuencia de tomas); consulte la Fig. 4.2.

Arroz. 4.2 Registro de desplazamiento de retroalimentación lineal (LFSR)

En el diagrama, el contenido del registro (una secuencia de bits) se desplaza un bit hacia la derecha con la llegada del pulso de reloj. El bit menos significativo se considera la salida del LFSR en un ciclo operativo determinado. El valor del dígito más significativo es el resultado de sumar módulo 2 (función XOR) los dígitos (puntos de referencia) de la realimentación. La secuencia generada se llama secuencia recurrente lineal.

Teóricamente, -bit LFSR puede generar una secuencia pseudoaleatoria con un punto
poco. Estos LFSR se denominan registros de período máximo.

Para hacer esto, el registro de turnos debe visitar todos
estados internos distintos de cero.

La misma recurrencia puede ser generada por registros. diferentes longitudes. Supongamos que entre registros similares el nuestro -bit LFSR tiene una longitud mínima.

Las funciones de retroalimentación de registros se pueden asignar a un polinomio
grado no superior con coeficientes del campo de residuos módulo dos, que consta de monomios de la forma
, Dónde
- conjunto de números de puntos de captación de retroalimentación.

Polinomio
llamado polinomio mínimo secuencia recurrente correspondiente.

Para cada secuencia finita (o periódica) se puede especificar un LFSR que, dado algún relleno inicial, genere esta secuencia.

Entre todos estos registros, existe un registro de longitud mínima. .

Magnitud llamado complejidad lineal secuencias .

Recordemos que un polinomio se llama irreducible si no puede expresarse como producto de dos polinomios de menor grado que sean constantes diferentes.

Polinomio primitivo grados sobre el campo de residuos módulo dos es un polinomio irreducible que divide
, pero no divide
para cualquier :
.

Teorema. Para que la secuencia generada por LFSR tenga un período máximo, es necesario y suficiente que su polinomio mínimo sea un polinomio primitivo módulo 2.

En se proporciona una lista de polinomios primitivos prácticamente aplicables. Por ejemplo, un polinomio primitivo es.

Conjunto de indicadores
significa que al tomar un registro de desplazamiento de longitud 32 y generar un bit de retroalimentación sumando los bits 7, 5, 3, 2 y 1 módulo 2, obtenemos un LFSR de longitud máxima (con
estados).

Aquí hay un programa en C para la secuencia generada por este LFSR:

Estático sin firmar largo ShiftRegister=1; //cualquier relleno inicial distinto de cero

Registro de cambios = ((((Registro de cambios >>31)

^(Registro de cambios>>6)

^(Registro de cambios >>4)

^(Registro de cambios >>2)

^(Registro de cambios >>1)

^(Registro de cambios))

| Registro de cambios >>1);

devolver ShiftRegister y 0x00000001;

Tenga en cuenta que si
es un polinomio primitivo, entonces
– también primitivo. Además, si el polinomio
primitivo, entonces
– primitivo. Si un polinomio
primitivo, luego primitivo, etc.

Los trinomios primitivos son especialmente convenientes porque Sólo se añaden 2 bits del registro de desplazamiento, pero también son más vulnerables a los ataques.

En términos generales, los LFSR son convenientes para la implementación técnica, pero desde el punto de vista de la solidez criptográfica, tienen debilidades.

Los bits recurrentes lineales consecutivos son linealmente dependientes, lo que los hace inútiles para el cifrado.

Suficiente
bits recurrentes sucesivos para determinar el conjunto de números de puntos de captación de retroalimentación.

Los grandes números aleatorios generados a partir de bits LFSR sucesivos están altamente correlacionados. Sin embargo, los LFSR se utilizan con bastante frecuencia como elementos de algoritmos más complejos para generar una secuencia de claves de cifrado.

También existen varios generadores PSP (incluidos los generadores Galois) que, por diversas razones, no han encontrado una amplia aplicación en los sistemas criptográficos. Las soluciones más efectivas se obtuvieron a base de generadores compuestos.

La idea de construir un generador compuesto se basa en el hecho de que la combinación de dos o más generadores PSP simples, en el caso de la elección correcta de la función de combinación (incluida la suma de módulo,
etc.), proporciona un generador con propiedades de aleatoriedad mejoradas y, como resultado, con una mayor solidez criptográfica.

En el caso de crear un generador PSP criptográficamente fuerte, el problema de crear cifrados de flujo se resuelve fácilmente. El resultado de dicho PSP es indistinguible (o más bien, debería ser indistinguible) del RRSP. Siempre se pueden iniciar dos generadores sincrónicamente desde un único vector de estado inicial, que es mucho más corto que el mensaje transmitido, lo que distingue este esquema del cifrado Vernam.

Hay 4 enfoques conocidos para diseñar generadores apropiados:

1) enfoque teórico de sistemas;

2) enfoque teórico de la complejidad;

3) enfoque teórico de la información;

4) enfoque aleatorio.

Estos enfoques difieren en sus suposiciones sobre las capacidades del criptoanalista, la definición de éxito criptográfico y el concepto de confiabilidad.

En el enfoque teórico de sistemas, el criptógrafo crea un generador de flujo de claves que tiene propiedades verificables, incluida la duración del período de la secuencia de salida, la distribución estadística del flujo de bits, la complejidad lineal de la transformación, etc.

Teniendo en cuenta las técnicas de criptoanálisis conocidas, el criptógrafo optimiza el generador contra estos ataques.

Basándose en este enfoque, Rüppel formuló el siguiente conjunto de criterios para cifrados de flujo.

1.Largo período de secuencia de salida, sin repeticiones.

2. Alta complejidad lineal como característica de nuestro generador a través de un registro LFSR de longitud mínima que puede generar la misma salida.

3. Indistinguibilidad de RRSP según criterios estadísticos.

4. Mezclar: cualquier bit del flujo de claves debe ser una transformación compleja de todos o la mayoría de los bits del estado inicial (clave).

5. Disipación: Se debe disipar la redundancia en todas las subestructuras del algoritmo generador.

6. Criterios de no linealidad de las transformaciones: de acuerdo con una determinada métrica, la distancia a las funciones lineales debe ser suficientemente grande; se requiere una propagación de errores similar a una avalancha en caso de un cambio en un bit del argumento, etc.

Un cifrado de flujo puede satisfacer todos estos principios y aún así ser débil porque La resistencia a un determinado conjunto de ataques criptoanalíticos no garantiza nada.

Un ejemplo de una construcción exitosa de un generador compuesto desde el punto de vista de una complejidad lineal creciente es la cascada de Goleman (Fig. 4.3). La etapa Goleman incluye varios registros de desplazamiento LFSR. El primer registro se mueve uniformemente en incrementos de 1. El desplazamiento de cada registro posterior es controlado por el anterior, de modo que el estado del registro posterior cambia en un ciclo de reloj. sucede si está en ritmo
1 se elimina del registro anterior. De lo contrario, el estado del registro posterior no cambia.

Si todos los LFSR son longitudes , entonces la complejidad lineal del sistema con registros iguales
.

Arroz. 4.3. cascada de gollman

Un ejemplo típico de combinación de registros de desplazamiento es el circuito del generador alternante Stop-and-Go.

Este generador tiene un período largo y una alta complejidad lineal.

El generador start-stop (Figura 4.4) utiliza tres registros de desplazamiento lineales de diferentes longitudes. LFSR-2 cambia de estado si la salida de LFSR-1 es 1; LFSR-3 cambia de estado de otra manera. El resultado del generador es la suma en módulo de 2 salidas de los registros LFSR-2, LFSR-3.

Arroz. 4.4. Generador alternante start-stop

Aplicando teoría de la complejidad En este enfoque, el criptógrafo intenta demostrar la solidez del generador utilizando la teoría de la complejidad.

La base de las soluciones en este enfoque son los generadores basados en el concepto ohdireccional inferioroh funciones.

Valor de función unidireccional

fácil de calcular, pero para casi todos los valores es casi imposible determinar el valor apropiado . De lo contrario, si – complejidad computacional de la obtención
, A
– complejidad computacional del hallazgo
, Eso
.

Existe un acuerdo general en que una candidata para una función unidireccional podría ser una función exponencial en algún campo finito.
, Dónde
.

Es fácil ver que la exponenciación puede acelerarse debido a las propiedades de la asociatividad. Por ejemplo,
, que le permite calcular el grado en cuatro pasos en lugar de ocho.

La operación inversa: el problema de encontrar el exponente a partir del valor de la función de potencia (logaritmo discreto), en el caso general, aún no se puede resolver mejor que utilizando métodos de enumeración optimizados.

Con una característica correspondientemente seleccionada
y grado de expansión del campo
Con el desarrollo moderno de la tecnología informática, este problema es computacionalmente insoluble.

Un ejemplo de un generador basado en una función unidireccional es un generador basado en el algoritmo RSA con parámetros
amable. Aquí
, Dónde
– números primos secretos, grandes y desiguales, – exponente de la función de potencia, mcd
,
.

El resultado de un ciclo de reloj del generador: el bit menos significativo
. La durabilidad de este generador no es inferior a la del RSA. Si
Lo suficientemente grande, el generador proporciona una durabilidad práctica.

BBS es otro ejemplo de generador basado en complejidad (propuesto por Blum, Blum y Shub).

Este es uno de los algoritmos simples y efectivos. La teoría matemática de este generador es módulo de residuos cuadráticos compuesto. .

Parámetros del generador: números primos secretos grandes y desiguales,
, tal que,
; número
;– deducción aleatoria del módulo secreto
.

El primer paso es calcular el estado inicial.
.

En el ciclo principal, el elemento PSP con el número
igual, es decir El enésimo número pseudoaleatorio es el bit menos significativo del número
.

Tenga en cuenta que el algoritmo se puede utilizar para cifrar archivos de acceso aleatorio si, excepto , ingrese el parámetro secreto
, porque entonces se puede calcular mediante , porque, donde
.

Esta propiedad le permite utilizar el generador BBS para trabajar con archivos de acceso aleatorio.

Número se puede distribuir libremente para que cada suscriptor de la red pueda generar de forma independiente los bits necesarios. Además, si el criptoanalista no puede factorizar el número , no podrá predecir el siguiente bit, ni siquiera en un sentido probabilístico, como "hay un 51% de posibilidades de que el siguiente bit sea 1".

Tenga en cuenta que estos generadores son muy lentos; su implementación práctica requiere procesadores especiales.

Los dos siguientes enfoques teórico de la información Y aleatorio, no han encontrado una amplia aplicación práctica.

Desde el punto de vista teórico de la información En general, la mejor herramienta en la lucha contra un criptoanalista que tiene tiempo y recursos informáticos infinitos es una cinta de un solo uso o una libreta de un solo uso.

La clave indicará qué partes (o bits) de estas cadenas deben usarse para el cifrado y descifrado. Entonces el criptoanalista tendrá que utilizar el método de búsqueda total de opciones (fuerza bruta) en cadenas aleatorias.

La fortaleza de este método se puede expresar en términos del número promedio de bits que un criptoanalista tendría que examinar antes de que las probabilidades de determinar la clave sean mejores que las simples conjeturas.

Ueli Maurer describió tal plan. La probabilidad de romper dicho criptosistema depende de la cantidad de memoria disponible para el criptoanalista (pero no depende de sus recursos informáticos).

Para que este esquema adopte una forma práctica, se requieren aproximadamente 100 secuencias de bits.
bits cada uno. Digitalizar la superficie lunar es una forma de obtener tal cantidad de bits.

En conclusión, observamos que para construir un generador de PSP es necesario obtener algunos bits aleatorios. La forma más sencilla es utilizar la parte menos significativa del temporizador de la computadora.

Usando este método, no puedes recibir muchos bits, porque Cada llamada al procedimiento de generación de bits puede tomar un número par de pasos del temporizador, lo que ciertamente afectará las propiedades de la secuencia.

La mejor manera de obtener un número aleatorio es apelar a la aleatoriedad natural del mundo real: ruido de transitorios en diodos semiconductores, ruido térmico de resistencias de alto voltaje, desintegración radiactiva, etc.

En principio, existe un elemento de aleatoriedad en las computadoras:

– hora del día;

– carga del procesador;

– hora de llegada de los paquetes de red, etc.

El problema no es encontrar las fuentes de la aleatoriedad, sino mantener la aleatoriedad en las mediciones.

Por ejemplo, esto se puede hacer así: busquemos un evento que ocurra regularmente, pero de forma aleatoria (el ruido excede un cierto umbral).

midamos el tiempo entre el primer evento y el segundo, luego el tiempo entre el segundo evento y el tercero.

Si
, luego igualamos la salida del generador a 1; Si
, entonces la salida es 0. Si es necesario, continuaremos el proceso.

Supongamos que la probabilidad de que ocurra cero se desplace por , es decir. se puede escribir como
.

Adición por
dos bits independientes igualmente distribuidos darán:. Al sumar cuatro bits obtenemos:
. El proceso converge a una distribución de bits igualmente probable.

Otro enfoque. Sean la distribución de unos y ceros en la secuencia las cantidades Y respectivamente.

Transformemos pares de bits sucesivos:

– si se trata de bits idénticos, deséchelos y considere el siguiente par;

– si los bits son diferentes, tomamos el primer bit como valor de salida.

Este método nos permite resolver el problema del sesgo preservando al mismo tiempo las propiedades de aleatoriedad de la fuente (con cierta pérdida en el volumen de datos).

Un problema potencial con ambos métodos es que cuando hay correlación entre bits adyacentes, estos métodos aumentan el desplazamiento. Una forma de evitar esto es utilizar diferentes fuentes de números aleatorios y agregar los bits de secuencias firmados uno debajo del otro verticalmente.

El hecho de que un generador de números aleatorios tenga un sesgo, en términos generales, no siempre significa que sea inadecuado.

Por ejemplo, supongamos que se utiliza un generador con polarización cero para generar una clave de 112 bits para el algoritmo Triple DES (ver más abajo):
,
(entropía
0,99277 por bit de clave en comparación con 1 para un generador ideal).

En este caso, el atacante puede optimizar el procedimiento de búsqueda total de claves buscando la clave a partir del valor más probable.
y terminando con el menos probable
. Debido a la presencia de sesgo, podemos esperar encontrar la clave en un promedio de
intentos. Si no hubiera desplazamiento, entonces sería necesario
intentos.