Cuando llega el momento de recoger las llaves.

Cuando llegue el momento de recoger las llaves.

Cuando llega el momento hora de recoger las claves

Un grupo de renombrados expertos en criptografía, creado bajo los auspicios de Business Software Alliance (una organización industrial que desalienta el uso ilegal de software), ha llegado a la conclusión de que la longitud de clave requerida actualmente debería ser de al menos 75 bits, con mayores aumentos en los próximos años. 20 años a 90 bits.

Los estadounidenses son personas serias y no bromean sobre esas cosas. Pero intente, querido lector, descubrir en qué se basa esta afirmación y comprobar la exactitud de las conclusiones de los expertos extranjeros.

¿Por dónde empezamos? Si hay una cerradura que debe abrirse, pero no hay llave, utilice una llave maestra u otra herramienta adecuada (o no tan adecuada). Si necesita descifrar un mensaje cifrado y el método de descifrado es una enumeración completa de las claves, entonces necesita una herramienta para ello: una computadora potente. Comencemos analizando las capacidades de las computadoras modernas.

En los años 60, algunos fabricantes de equipos informáticos electrónicos comenzaron a crear supercomputadoras, máquinas potentes para resolver problemas con un gran volumen de cálculos, que hasta hace poco se utilizaban principalmente con fines militares. Como todo lo mejor, esta dirección en el desarrollo de la tecnología informática siempre ha despertado un mayor interés tanto por parte de especialistas como de personas alejadas de este tema. Al parecer, para satisfacer este interés, recientemente se ha publicado en la prensa abierta el llamado TOP 500, una lista actualizada dos veces al año de los quinientos superordenadores más potentes utilizados en el mundo y los mayores centros de supercomputadores (SCC) en el mundo (Tabla 1). Para compilar la primera lista, se utiliza el rendimiento máximo alcanzado en la prueba paralela de Linpack.

Tabla 1.10 de las supercomputadoras más potentes a julio de 1997

De la lista que apareció en el verano de 1997, se deduce que la velocidad de las supercomputadoras se distribuyó de la siguiente manera:
con una potencia de aproximadamente 1012 FLOPS — 1 copia;
con una potencia de aproximadamente 1011 FLOPS — 20 copias;
con una potencia de aproximadamente 1010 FLOPS—328 copias;
con una potencia de aproximadamente 109 FLOPS—151 copias.

en la mesa La Figura 2 muestra una lista de los 15 países principales en orden descendente según el rendimiento de sus supercomputadoras más poderosas. Si un país tiene varios superordenadores, se indicaba el rendimiento del más potente de ellos. Está claro que la presencia de supercomputadoras muestra el potencial científico y técnico de un país y refleja sus capacidades militares.

Tabla 2. Primeros 15 países de la lista Top500

El primer lugar en el mundo en número de supercomputadoras lo ocupa Estados Unidos: 254 (51%). Le siguen Japón: 87 (17,5%), Alemania: 45 (9%), Gran Bretaña: 24 (4,8%), Francia: 18 (3,6%), Corea: 8 (1,6%), Canadá: 7 (1,4%). %), Suecia, Suiza y Noruega: 6 cada uno (1,2%).

Rusia se menciona en esta lista solo una vez: en el puesto 156 se encuentra la computadora NPC Ultra 10000 (rendimiento máximo 16600 MFLOPS), fabricada por SUN e instalada en el Banco Nacional de Reserva de Rusia. Me gustaría creer que esta situación no es del todo cierta. Un detalle interesante: en Estados Unidos no hay ordenadores fabricados en el extranjero: los estadounidenses trabajan únicamente con máquinas nacionales y, además, las suministran al resto del mundo.

Tabla 3. Computadoras de Lista TOP500, perteneciente a organizaciones capaces de interceptar y descifrar información

El número de instalaciones de supercomputadoras crece exponencialmente año tras año, y la mayor parte se produce nuevamente en los Estados Unidos. Es interesante observar que la lista contiene principalmente automóviles producidos en los últimos dos años; el resto no representa más de una cuarta parte de la lista. Se puede afirmar que en los últimos 3 o 4 años la lista se ha actualizado casi por completo. Las estadísticas por año son las siguientes: 1997 — 207 instalaciones (a julio de 1997), 1996 — 168 instalaciones, 1995 — 52 instalaciones, 1994 — 45 instalaciones, 1993 — 16 instalaciones, 1992 — 10 instalaciones, 1991 — sólo 2 instalaciones, cuyas calificaciones son 128 y 195. Intentemos predecir el aumento en el número de supercomputadoras durante los próximos dos años basándonos en las estadísticas de los últimos seis años:

45/10 = 4,5
52/16 = 3,25
168/45 = 3,7
207/52 = 3,9.

Utilizando la tasa de crecimiento promedio de dos años (3,8), calculamos los valores aproximados de instalaciones para 1998-99:

168 x 3,8 = 638 instalaciones en 1998. ,
207 x 3,8 = 786 instalaciones en 1999

Por lo tanto, en el próximo año o dos podemos esperar que la lista TOP 500 crezca hasta llegar al TOP 1500 (638 + 786 = 1424) o incluso más.

La composición de los fabricantes de supercomputadoras en el mundo se presenta en la Fig. 1.

Fig.1 .

En la lista figuran 11 empresas, y las cuatro principales empresas estadounidenses representan más del 80% del mercado mundial (402 instalaciones de 500). En total, los fabricantes estadounidenses cubren el 86% de la producción mundial de supercomputadoras (Intel, TMC, DEC, Parsytec representan un total de 28 instalaciones, o el 5,6%). Las empresas japonesas (Fujitsu, NEC, Hitachi) aportan las 70 instalaciones restantes del TOP500 (14%).

Existe una relación clara entre el lugar que ocupan ciertos países en la lista considerada y el nivel de inversión en tecnología de la información en estos países (Fig. 2).

Fig.

No es casualidad que repasemos la lista de los ordenadores más potentes del mundo con tanto detalle y versatilidad. Nos servirá como punto de partida para estudiar la solidez de los algoritmos de cifrado con una clave aleatoria si se utilizan computadoras modernas para descifrarlos.

Supongamos que los algoritmos de cifrado que estamos considerando son ideales, es decir, el método óptimo para descifrarlos será una búsqueda directa de todas las claves posibles de un algoritmo determinado. Obviamente, en este caso, la solidez de los criptosistemas estará determinada por la longitud de la clave. Al realizar este estudio, se asumió que el criptoanalista de la parte contraria tiene toda la información sobre el algoritmo de cifrado, con excepción de los datos sobre la clave secreta, y el texto cifrado del mensaje está disponible para su análisis. Por definición, se supone que un algoritmo ideal carece de deficiencias que reduzcan su solidez criptográfica.

Supongamos también que la computadora genera una clave en un ciclo de reloj y la operación de descifrado se produce instantáneamente. Al determinar la relación entre el número de claves y la velocidad de la computadora más potente, obtenemos un límite inferior para la complejidad de descifrar un mensaje para un algoritmo ideal. Los resultados de estos cálculos se dan en la tabla. 4. Según la teoría de la probabilidad, el tiempo promedio para descifrar un mensaje (tiempo esperado de descifrado) debe considerarse la mitad del tiempo indicado en la tabla (indicado entre paréntesis). En los casos en que el período requerido para una enumeración completa de claves superó los 10.000 años, no se indicó el tiempo promedio de descifrado.

Tabla 4. Tiempo ( en años), que actualmente requieren los superordenadores más potentes para una enumeración completa de claves

Según algunas estimaciones, el rendimiento del ordenador dividido por su coste aumenta 10 veces cada 5 años. Según esta tesis, durante los próximos cincuenta años el rendimiento de las computadoras aumentará de la siguiente manera:

2005—10 veces
2010—100 veces
2015—1000 veces
2020—10,000 veces
2025—100,000 veces
/> 2030 — 1,000,000 de veces
2035 — 10.000.000 de veces
2040 — 100.000.000 de veces
2045 — 1.000.000.000 de veces
2050 — 10.000.000.000 de veces
etc.

Intentemos comprobar la autenticidad de esta afirmación.

Según la Gran Enciclopedia Soviética (artículo “Computadora digital”), la primera computadora digital electrónica, ENIAC, se construyó en 1945 y entró en funcionamiento en 1946 en los EE. UU. A partir de ese momento, en muchos países comenzaron las investigaciones activas encaminadas a crearla. elementos digitales electrónicos confiables y desarrollo de estructuras informáticas digitales racionales.

La velocidad de funcionamiento de las máquinas de primera generación (hasta mediados de los años 50) no superaba varios cientos de operaciones por segundo. Supongamos que la velocidad de las primeras máquinas era de 100 operaciones por segundo y tomemos este valor como punto de partida.

Dado que han pasado 51 años desde entonces (10,2 períodos de cinco años), en 1997 la potencia de las computadoras debería haber aumentado a aproximadamente 100-1010,2 = 1012,2 operaciones por segundo, lo que confirma la lista TOP 500 anterior en el año 1951, la Comisión Estatal. adoptó la primera máquina de conteo electrónico MESM en el continente europeo y en la URSS con una velocidad de 50 operaciones por segundo, creada por un pequeño grupo bajo la dirección del académico S. A. Lebedev. A estas alturas (97 -51 = 46, 46/5 = 9,2) la productividad estimada de este tipo de máquina debería ser 50 • 109,2 = 5 • 1010,2 operaciones por segundo. La computadora más potente del continente europeo, ubicada en Gran Bretaña, funciona a una velocidad de 2,6 • 1011

Por tanto, podemos decir que la previsión «10 veces en 5 años» es bastante razonable y describe de forma fiable el crecimiento de la potencia informática durante largos períodos de tiempo.

Definamos que x(t) es una función continua que muestra la velocidad de las computadoras en el tiempo t. Basándose en la hipótesis de trabajo aceptada “10 veces en 5 años” y el punto de referencia inicial (tg = O en 1946), la función se ve así: x(t) = С0 • 10t/5, donde el punto de referencia inicial С0 = 100— potencia de la primera computadora ENIAC.

Introducimos la siguiente notación:

S es la potencia del alfabeto del que se extraen los símbolos de la clave;
L es la longitud de la clave;
||{K}|| = SL — la potencia del conjunto de claves;
Tm({K}, x(t)) — el tiempo máximo para buscar las claves;
D ({K}, x(t)) — expectativa matemática de descifrado;
topt , — momento óptimo para iniciar el descifrado;
Tb({K}, x(t)) — tiempo de seguridad del sistema ( depende de dos parámetros: la hora de inicio del descifrado t y su duración D).

Según los supuestos realizados, el tiempo para enumerar todas las claves en un espacio de claves determinado en el tiempo t (el tiempo máximo para descifrar un mensaje) será Tm = = ||{K}||/x(t), y el tiempo medio para descifrar un mensaje es la mitad del tiempo máximo: D = 1/2 Tm = 1/2 (||{K}||/x(t)). Con base en el pronóstico sobre el aumento en el poder de las herramientas informáticas, se podría simplemente tomar como base que la duración de la búsqueda en 100 años debería ser un tiempo predeterminado, por ejemplo un año, y crear la siguiente ecuación como ||{ K}||/Cl • x(t+100) > 1, de lo que se deduce que la longitud de clave requerida debe ser de 136 a 137 bits. Sin embargo, se pueden hacer estimaciones más precisas y útiles para evitar desperdiciar energía en tareas cuyo momento aún no ha llegado.

Por supuesto, si se esperan 100 años, entonces un ataque contundente a un algoritmo criptográfico, cuya implementación hoy requiere muchos años, en ese momento solo tomará unos segundos, pero debido a la pérdida total de relevancia de la información obtenida, el significado de su implementación desaparecerá. Dado el continuo crecimiento de la potencia informática, se puede suponer que el descifrado no debería comenzar inmediatamente después de recibir el texto cifrado, sino en el momento en que requiera menos tiempo. ¡La ganancia en muchos casos puede ser muy significativa! Por ejemplo, si hoy el proceso de criptoanálisis tarda 100 años, en 5 años la potencia de la computadora aumentará 10 veces y el descifrado, que demora 10 años, finalizará en 2015. En 10 años, el rendimiento de la computadora aumentará 100 veces y una búsqueda completa de opciones, finalizadas en un año, darán resultados ya en 2011. Así, la ganancia de tiempo en comparación con la primera opción es de 89 años. La pregunta es si es posible reducir aún más el tiempo de criptoanálisis eligiendo el momento óptimo de su inicio y cuánto tiempo (a partir de este momento) durará el descifrado óptimo.

El modelo de trabajo para calcular el tiempo de seguridad de un sistema de cifrado (1) consta de la suma de dos factores operativos: el momento en que comienza el descifrado más la complejidad del descifrado. Al mínimo de esta función lo llamaremos tiempo máximo de seguridad Tb de un sistema de cifrado ideal. El adjetivo «máximo» se introdujo sólo para enfatizar la idealidad de los algoritmos en estudio: en la vida real, los criptosistemas tienen ciertas desventajas que reducen su fortaleza criptográfica. El coeficiente Cl=31.536.000 surge al pasar de operaciones por segundo a operaciones por año y se utiliza principalmente por conveniencia.

Para determinar el mínimo de esta función, encontraremos su derivada y resolveremos la ecuación Tb’ = 0. Como resultado de la solución y simplificación obtenemos el siguiente valor del momento de tiempo top en el que se alcanza el mínimo de la función Tb, es decir, el momento óptimo para iniciar el criptoanálisis:

Sustituyendo ||{K}|| En esta fórmula, puede obtener el valor del momento superior. El tiempo de seguridad de un sistema de cifrado ideal está determinado por el valor de la función Tb en este punto. Sustituyendo en (1) la potencia del conjunto de claves ||{K}|| en el sistema en estudio y se puede encontrar el valor de topt, su tiempo de seguridad Tb.

El tiempo promedio de descifrado está determinado por la siguiente fórmula:

El hecho más inesperado e interesante, en mi opinión, es que si sustituimos el valor de topt en la fórmula (3) y hacemos las simplificaciones necesarias, entonces la duración del descifrado iniciado en el momento óptimo, independientemente de la longitud de la clave, siempre es lo mismo: 5/ln 10 == 2,171472409516 años (739,13 días o 19.035,12 horas).

Tb = superior +2,17

Por lo tanto, utilizando el modelo de trabajo especificado, es posible evaluar la confiabilidad de los sistemas de cifrado diseñados y operados. Por ejemplo, la solidez (en años) de los algoritmos con diferentes longitudes de clave en nuestras estimaciones se muestra en la Tabla. 5. Los cálculos se realizaron de acuerdo con la fórmula (2) para la tercera columna y la fórmula (1) para la quinta columna, y todos los datos se contaron desde el momento inicial: 1946. Como ejemplo de los cálculos realizados, considere un cifrado algoritmo con una clave de 70 bits. De acuerdo con la fórmula (2), el momento óptimo para empezar a hackearlo es 64,7 años, o 1946 + 64,7 = 2010,7, es decir, el 12 de agosto de 2010. El proceso iniciado ese día tendrá una duración de 2 años 2 meses 1 día 17 horas 31 minutos y finaliza el 13 de octubre de 2012 a las 4 horas 48 minutos.

Tabla 5. El momento óptimo para iniciar el descifrado, su duración y el momento de finalización dependiendo de la longitud de la clave

Por supuesto, todos los resultados proporcionados son válidos solo en promedio. La duración del descifrado de cada mensaje individual puede variar de 0 a Tm, pero puesto en funcionamiento (a escala industrial) tenderá a los valores anteriores.

¿Qué otros beneficios se pueden derivar de la teoría construida? En la práctica, una fórmula para la dependencia de la longitud de la clave de un nl predeterminado (el año en que comenzó el descifrado) puede resultar útil.

Por ejemplo, se requiere cerrar cierta información de tal manera que se garantice mantener su confidencialidad durante 20 años. ¿Cuál debería ser la longitud de la clave en este caso?

Hoy es 1998, la información no debería descifrarse hasta 2018, por lo tanto, nl = 2018-1946 = 72 años, encontramos que la cardinalidad del conjunto de claves es ||{K}|| debe ser al menos 3,444 • 10^22 y la longitud de la clave es de aproximadamente 74,87 bits.

¡Sí, los criptógrafos americanos tenían razón! Basándonos en estos mismos cálculos, podemos concluir que consideran que este período es suficiente para que la información descifrada quede obsoleta. Comprobemos su afirmación de que después de 20 años la longitud de clave requerida debería ser de 90 bits.

Dentro de 20 años llegará 2018, por lo tanto, para garantizar la solidez de la información requerida, el momento óptimo para descifrar no debería ocurrir antes de 2038 (2038-1946 = 92).

La potencia del conjunto de claves calculada mediante la fórmula (4) debe ser 3,444 • 1022 y la longitud de la clave debe ser 88,16 bits.

La ligera diferencia entre los resultados obtenidos y los propuestos por especialistas estadounidenses de fama mundial confirma la corrección matemática y la validez de nuestra teoría propuesta y su premisa principal: la velocidad de las computadoras se multiplica por diez cada 5 años. Las discrepancias existentes pueden depender, por ejemplo, de la precisión de los cálculos de varias calculadoras o del valor de la constante Cl, (el número de segundos en un año), dado que un año no tiene 365 días, sino 365. días 6 horas 40 minutos.

La teoría propuesta también se ve confirmada por la información sobre el pirateo en 1997 de mensajes con claves de 40, 48 y 56 bits de longitud, cuyo tiempo de seguridad finalizó hace mucho tiempo, ascendiendo respectivamente a 19,5 (1965) y 31,56 (1977). , 43,6 (1989) años. Además, utilizando las fórmulas anteriores, en 1998 podemos suponer razonablemente que se descifrarán claves de hasta 62 bits de longitud. ¡Pero las claves con una gran cantidad de dígitos no serán pirateadas en 1998! El autor está dispuesto a apostar sobre este asunto con cualquiera.

Otra conclusión es que la prohibición impuesta por los legisladores estadounidenses sobre la exportación de productos criptográficos con una longitud de clave superior a 56 bits está diseñada para la velocidad de computadoras de hace diez años y actualmente no garantiza la seguridad. de la información transmitida.

En este contexto, parece mucho más atractiva la criptografía rusa, que desde hace 10 años ofrece como estándar una clave de 256 bits, cuya seguridad está garantizada durante 300 años en el futuro, hasta 2290.