Generador de secuencias pseudoaleatorias.

Servicios

La primera tecnología ampliamente utilizada para generar un número aleatorio fue el algoritmo propuesto por Lechmer, conocido como método de congruencia lineal. Este algoritmo está parametrizado por cuatro números de la siguiente manera: Subsecuencia números aleatorios

(X n) se obtiene utilizando la siguiente igualdad iterativa:

X norte +1 = (a X norte + c) mod m< m.

Si m, a y c son números enteros, entonces se crea una secuencia de números enteros en el rango 0 X n.

La elección de los valores de a, c y m es fundamental para desarrollar un buen generador de números aleatorios. Obviamente, m debe ser muy grande para poder generar muchos números aleatorios. Se cree que m debería ser aproximadamente igual al entero positivo máximo para de esta computadora

. Por lo general, m es cercano o igual a 2 31.

Se utilizan tres criterios al elegir un generador de números aleatorios:

1. La función debe crear un período completo, es decir todos los números entre 0 y m antes de que los números generados comiencen a repetirse.

2. La secuencia generada debe aparecer de forma aleatoria. La secuencia no es aleatoria ya que se genera de manera determinista, pero las diversas pruebas estadísticas que se pueden aplicar deberían mostrar que la secuencia es aleatoria.

3. La función debe implementarse efectivamente en procesadores de 32 bits. Los valores de a, c y m deben elegirse de manera que se cumplan estos tres criterios. De acuerdo con el primer criterio, se puede demostrar que si m es simple y c = 0, entonces cuando un cierto valor y el periodo creado por una función

, será igual a m-1. Para la aritmética de 32 bits, el valor primo correspondiente es m = 2 · 31 - 1. Por tanto, la función para generar números pseudoaleatorios es:

X n +1 = (a X n) mod (2 31 - 1) Solo pequeño número

El poder del algoritmo lineal congruente es que si el factor y el módulo (base) se eligen apropiadamente, entonces la secuencia de números resultante será estadísticamente indistinguible de una secuencia aleatoria del conjunto 1, 2, ..., m- 1. Pero no puede haber aleatoriedad en la secuencia obtenida mediante el algoritmo, independientemente de la elección del valor inicial X 0 . Si se selecciona un valor, los números restantes de la secuencia estarán predeterminados. Esto siempre se tiene en cuenta en el criptoanálisis.

Si el adversario sabe que se está utilizando el algoritmo lineal congruente y si se conocen sus parámetros (a = 7 5, c = 0, m = 2 31 - 1), entonces, si se revela un número, toda la secuencia de números se convierte en conocido. Incluso si el adversario sólo sabe que se está utilizando un algoritmo lineal congruente, conocer una pequeña parte de la secuencia es suficiente para determinar los parámetros del algoritmo y todos los números posteriores. Supongamos que el enemigo puede determinar los valores de X 0, X 1, X 2, X 3. Entonces:

X 1 = (a X 0 + c) mod mX 2 = (a X 1 + c) mod mX 3 = (a X 2 + c) mod m

Estas igualdades nos permiten encontrar a, cy m.

Así, aunque el algoritmo es buen generador secuencia pseudoaleatoria de números, es deseable que la secuencia real utilizada sea impredecible, ya que en este caso el conocimiento de parte de la secuencia no permitirá determinar sus elementos futuros. Este objetivo se puede lograr de varias maneras. Por ejemplo, usando interna reloj del sistema para modificar el flujo de números aleatorios. Una forma de utilizar el reloj es reiniciar la secuencia después de N números, utilizando el valor actual del reloj módulo m como nuevo valor inicial. Otra forma es suma simple valores de tiempo actuales para cada módulo de número aleatorio m.

(Inglés) ruso: « La generación de números aleatorios es demasiado importante para dejarla al azar».

YouTube enciclopédico

1 / 5

✪ Generadores de números aleatorios y pseudoaleatorios

✪ Generador de números pseudoaleatorios | Criptografía | Programación (parte 8)

✪ Lecciones de C++ desde cero / Lección #5 - Generador de números + cadenas en C++

✪ rand. sardina rand establece el rango. tiempo de espera nulo. Generador de números aleatorios. aleatorizar. Lección #29.

✪ Números aleatorios, método congruencial lineal - LNG (Generador Congruencial Lineal)

Subtítulos

Cuando observamos el mundo físico, encontramos variaciones aleatorias en todas partes. Podemos generar reales., midiendo variaciones aleatorias llamadas ruido. Midiendo este ruido (muestreo), se pueden obtener números. Por ejemplo, si mides corriente eléctrica estática del televisor durante algún tiempo, obtienes una secuencia aleatoria perfecta. Puedes visualizar esta secuencia aleatoria dibujando un camino cuya dirección cambia dependiendo de cada número. A esto se le llama paseo aleatorio. Cabe señalar que no existe un patrón de ninguna escala en cada punto de la secuencia; el siguiente paso es siempre impredecible. Dicen que procesos aleatorios no determinista, ya que es imposible predecir su desarrollo de antemano. Las máquinas, por otra parte, son deterministas. en milisegundos. Sus operaciones son predecibles y repetibles. En 1946, John von Neumann fue invitado a realizar cálculos para el ejército. Participó especialmente activamente en el diseño de la bomba de hidrógeno. para encontrar uno que se ajuste y abra la cerradura.

Pero serán necesarios varios días.

Por tanto, suponemos que durante 8 horas está prácticamente protegido. Cuando se utilizan generadores de números pseudoaleatorios, la seguridad aumenta al aumentar la longitud del grano. La computadora más poderosa probará todos los granos posibles durante muchos años, por lo que podemos asumir con seguridad una seguridad práctica en lugar de una seguridad perfecta. A medida que aumenta la velocidad de cálculo, la longitud del grano debería aumentar proporcionalmente. La pseudoaleatoriedad libera a Alice y Bob de tener que intercambiar por adelantado una secuencia aleatoria completa de compensaciones.

En cambio, intercambian granos aleatorios relativamente pequeños y los estiran en las mismas secuencias aleatorias que se requieren. Pero, ¿qué pasa si nunca se reúnen para intercambiar este grano al azar? Fuentes de números aleatorios

Las fuentes de números aleatorios reales son extremadamente difíciles de encontrar. El ruido físico, como los detectores de eventos de radiación ionizante, el ruido de disparo en una resistencia o los rayos cósmicos, pueden ser tales fuentes. Sin embargo, estos dispositivos se utilizan en aplicaciones.

seguridad de red casi nunca. También surgen dificultades ataques brutales para dispositivos similares.

Las aplicaciones criptográficas utilizan algoritmos especiales para generar números aleatorios. Estos algoritmos están predeterminados y por tanto generan una secuencia de números que teóricamente no pueden ser estadísticamente aleatorias. Al mismo tiempo, si eliges un buen algoritmo, la secuencia numérica resultante es

Entre los PRNG modernos, también se ha generalizado el “vórtice Mersenne”, propuesto en 1997 por Matsumoto y Nishimura. Sus ventajas son un período colosal (2 19937 −1), una distribución uniforme en 623 dimensiones (el método lineal congruente da una distribución más o menos uniforme en un máximo de 5 dimensiones), generación rápida de números aleatorios (2-3 veces más rápido que PRNG estándar utilizando el método de congruencia lineal). Sin embargo, existen algoritmos que reconocen la secuencia generada por el vórtice de Mersenne como no aleatoria.

PRNG con fuente de entropía o RNG

Así como existe la necesidad de generar secuencias de números aleatorios fácilmente repetibles, también existe la necesidad de generar números completamente impredecibles o simplemente completamente aleatorios. Estos generadores se llaman generadores de números aleatorios(RNG - Generador de números aleatorios en inglés, RNG). Dado que estos generadores se utilizan con mayor frecuencia para generar claves simétricas y asimétricas únicas para el cifrado, la mayoría de las veces se construyen a partir de una combinación de un PRNG criptográfico y fuente externa entropía (y es precisamente esta combinación la que ahora se entiende comúnmente como RNG).

Casi todo grandes fabricantes Los microchips se suministran mediante RNG de hardware con diferentes fuentes de entropía, utilizando diferentes métodos para eliminar su inevitable previsibilidad. Sin embargo, en en este momento la velocidad a la que todos los microchips existentes recopilan números aleatorios (varios miles de bits por segundo) no se corresponde con la velocidad procesadores modernos.

EN investigación moderna Se está intentando utilizar mediciones de las propiedades físicas de los objetos (por ejemplo, la temperatura) o incluso fluctuaciones cuánticas del vacío como fuente de entropía para el RNG.

EN computadoras personales Los autores de software RNG utilizan fuentes de entropía mucho más rápidas, como el ruido. tarjeta de sonido o contador de ciclos del procesador. La acumulación de entropía fue el punto más vulnerable del RNG. Este problema aún no está completamente resuelto en muchos dispositivos (por ejemplo, las tarjetas inteligentes), que por tanto siguen siendo vulnerables. Muchos RNG utilizan métodos tradicionales, aunque lentos, para recopilar entropía, como medir la respuesta del usuario (movimiento del mouse, etc.), como en PGP y Yarrow, o la interacción entre subprocesos, como en Java SecureRandom.

Un ejemplo de un RNG simple con una fuente de entropía

Si utilizamos la hora actual como fuente de entropía, entonces para obtener un número entero de 0 a norte basta con calcular el resto de dividir la hora actual en milisegundos por el número norte+1. La desventaja de este RNG es que produce el mismo número en un milisegundo.

Ejemplos de RNG y fuentes de entropía

		PRNG	Ventajas	Defectos
/dev/aleatorio en UNIX/Linux	Contador de reloj de CPU, aunque solo se recopila durante interrupciones de hardware	LFSR, con salida hash mediante SHA-1	Disponible en todos los Unixes, una fuente confiable de entropía	Se "calienta" durante mucho tiempo, puede "atascarse" durante mucho tiempo o funciona como un PRNG ( /dev/urandom)
Milenrama de Bruce Schneier	Métodos tradicionales	AES -256 y SHA-1 estado interno pequeño	Diseño flexible criptorresistente	Lento
Microsoft CriptoAPI	Hora actual, tamaño del disco duro, tamaño memoria libre, número de proceso y nombre de la computadora NETBIOS	Hash MD5 de estado interno de 128 bits de tamaño	Integrado en Windows, no se atasca	Depende en gran medida del proveedor de cifrado (CSP) utilizado.
Java seguroaleatorio	Comunicación entre hilos	Hash SHA-1 de estado interno (1024 bits)	Gran estado interno	Colección lenta de entropía
Caos por Ruptor	Contador de reloj del procesador, recopilado continuamente	Hashing de estado interno de 4096 bits basado en una variante no lineal del generador Marsaglia	Hasta que el más rápido de todos, el gran Estado interno, se “atasque”	Desarrollo original, las propiedades se dan únicamente según declaración del autor.
RRAND de Ruptor	contador de ciclos de CPU	Cifrado del estado interno con cifrado de flujo EnRUPT en modo de cifrado autenticado (aeRUPT)	Muy rápido, estado interno de tamaño arbitrario para elegir, sin "atascados"	Desarrollo original, las propiedades se dan únicamente según declaración del autor. El cifrado EnRUPT no es criptoseguro.
RdRand de Intel	Ruido actual	Construcción de un generador de frecuencia basado en lectura de bits "aleatoria" de valores de corrientes	Muy rápido, no se atasca.	Desarrollo original, las propiedades se dan únicamente de acuerdo con la declaración del artículo de habrahabr; por favor, aclare.
Stratosphera PRNG de ORION	Contador de reloj del procesador, recopilado continuamente (la sal también se utiliza en forma de un número entero seleccionado al azar)	Construcción de un PNG basado en un algoritmo de Intel con inicialización y desplazamiento reutilizables	Lo suficientemente rápido, no se atasca, pasa todas las pruebas DIEHARD	Desarrollo original, las propiedades se dan únicamente en base a información del sitio web oriondevteam.com - (aclaración del 23/10/2013).

PRNG en criptografía

Un tipo de PRNG son los PRBG, generadores de bits pseudoaleatorios, así como varios cifrados de flujo. Los PRNG, al igual que los cifrados de flujo, constan de un estado interno (que generalmente varía en tamaño desde 16 bits hasta varios megabytes), una función para inicializar el estado interno con una clave o grano(Semilla inglesa), funciones de actualización del estado interno y funciones de salida. Los PRNG se dividen en aritméticos simples, criptográficos rotos y criptográficos fuertes. Su propósito general es generar secuencias de números que no puedan distinguirse de los aleatorios mediante métodos computacionales.

Aunque muchos PRNG o cifrados de flujo potentes ofrecen números mucho más "aleatorios", dichos generadores son mucho más lentos que los generadores aritméticos convencionales y pueden no ser adecuados para ningún tipo de investigación que requiera que el procesador esté libre para realizar cálculos más útiles.

Para fines militares y condiciones de campo Sólo se utilizan PRNG (cifrados de flujo) criptográficos síncronos secretos; Ejemplos de PRNG criptorresistentes conocidos son RC4, ISAAC, SEAL, Snow, el algoritmo teórico muy lento Blum - Blum - Shuba, así como contadores con funciones hash criptográficas o cifrados de bloque seguros en lugar de la función de salida.

Ejemplos de PRNG criptorresistentes

Cifrado por turnos

EN en este caso Se utiliza un método para generar una clave de sesión a partir de una clave maestra. Se utiliza un contador con período N como entrada al dispositivo de cifrado. Por ejemplo, si se utiliza una clave DES de 56 bits, se puede utilizar un contador con un período de 256. Después de cada clave creada, el valor del contador se incrementa en 1. Por tanto, la secuencia pseudoaleatoria obtenida utilizando este esquema tiene una. período completo: cada valor de salida X0, X1,…XN-1 basado en diferentes significados contador, entonces X0 ≠ X1 ≠ XN-1. Dado que la clave maestra es secreta, es fácil demostrar que cualquier clave secreta no depende del conocimiento de una o más claves anteriores. claves secretas.

ANSIX9.17

El PRNG del estándar ANSI X9.17 se utiliza en muchas aplicaciones PGP y de seguridad financiera. Este PRNG se basa en triple DES. El generador ANSI X9.17 consta de las siguientes partes:

1. Entrada: El generador está controlado por dos entradas pseudoaleatorias. Una es una representación de 64 bits. fechas actuales y hora, que cambian cada vez que se crea un número. El otro es el valor bruto de 64 bits. Se inicializa con algún valor arbitrario y cambia durante la generación de una secuencia de números pseudoaleatorios.
2. Claves: El generador utiliza tres módulos DES triples. Los tres utilizan el mismo par de claves de 56 bits, que se mantiene en secreto y sólo se utiliza cuando se genera un número pseudoaleatorio.
3. Salida: La salida consta de un número pseudoaleatorio de 64 bits y un valor de 64 bits que se utilizará como semilla al crear el siguiente número.

• DTi: valor de fecha y hora al comienzo de la i-ésima etapa de generación.
• Vi es el valor inicial para la etapa de i-ésima generación.
• Ri es un número pseudoaleatorio creado en la i-ésima etapa de generación.
• K1, K2: claves utilizadas en cada etapa.

1 Ri = EDEK1,K2 [ EDEK1,K2 [ DTi] 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 de los generadores LFSR heredados y conocidos 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 existentes, mucho más lentos pero bien conocidos. cifrados en bloque(DES, AES) y funciones hash (SHA-1) en modos de transmisión.

Generadores 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 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 de esta última definición también se denomina “aleatorio para todos” aplicaciones practicas" Los generadores de tales secuencias se denominan criptográficamente seguros ( criptográficamente fuerte) o criptográficamente seguro ( criptográficamente seguro). La pseudoaleatoriedad 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 informáticas.

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 de números pseudoaleatorios más simple es generador lineal congruente(LKG), que se describe mediante una ecuación recurrente de la forma X norte =(aX n -1 +b) mod 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, valor máximo logrado 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 LCG en computadoras personales, teniendo en cuenta su cuadrícula de bits, a menudo se usa el módulo 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 rendimiento alto 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áticas. 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 estudiaron combinaciones de LCG. 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

∙∙∙

2

1

Arroz. 2. Registro de desplazamiento de 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– conveniente para 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 muy a menudo utilizados como elementos de más algoritmos complejos formación de 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 V 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 la elección correcta función unificadora (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 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 transformaciones: de acuerdo con alguna métrica, la distancia a 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 en términos de 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. En caso contrario, si V – complejidad computacional recepción 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 candidata para una función unidireccional puede ser una función potencia en algún campo finito. 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 optimizados para enumerar posibles opciones. 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 pqq– 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). Por el 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 yo = x 2 yo -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 Hay valor más pequeño poco:

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

Número norte se puede distribuir libremente, de modo que cada suscriptor de la red pueda generar de forma independiente bits requeridos. 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 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 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 obtener un número aleatorio es recurrir 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 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 una gran cantidad de 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, entonces 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.