Когда наступит время подбирать ключи
Всегда ли необходимо начинать криптоанализ сразу же после получения шифртекста? Быть может, если немного подождать, итоговый результат будет получен быстрее?
Группа известных специалистов-криптографов, созданная под эгидой Альянса производителей программного обеспечения для бизнеса (промышленной организации, препятствующей незаконному использованию программного обеспечения), пришла к выводу, что необходимая длина ключа в настоящее время должна быть не менее 75 битов с дальнейшим увеличением в течение последующих 20 лет до 90 битов [2]. Американцы люди серьезные, и шутить такими вещами не будут. Но попробуйте, уважаемый читатель, разобраться, на чем основано это утверждение, и проверить точность заключения заокеанских специалистов.
С чего начнем? Если есть замок, который нужно открыть, но нет ключа, используют отмычку или другой подходящий (или не очень подходящий) инструмент. Если нужно вскрыть шифрсообщение, а методом взлома будет полный перебор ключей, то для этого нужен инструмент мощный компьютер. С анализа возможностей современных компьютеров и начнем.
Еще в 60-х годах некоторые производители электронно-вычислительной техники начали создавать суперкомпьютеры мощные машины для решения задач с большим объемом вычислений, применявшихся до последнего времени главным образом в военных целях. Как и все самое-самое, это направление развития компьютерной техники всегда вызывало повышенный интерес со стороны как специалистов, так и людей далеких от этой тематики. Видимо, в целях удовлетворения этого интереса с недавнего времени в открытой печати публикуется так называемый TOP 500 обновляемый два раза в год список пятисот самых мощных в мире эксплуатируемых суперкомпьютеров и крупнейших суперкомпьютерных центров (СКЦ) мира. Для составления первого списка используется достигнутая максимальная производительность по тесту Linpack parallel.
Из списка, появившегося летом 1997 года [1], следует, что по быстродействию суперкомпьютеры распределились следующим образом:
с мощностью порядка 1012 FLOPS 1 экз.;
с мощностью порядка 1011 FLOPS 20 экз.;
с мощностью порядка 1010 FLOPS 328 экз.;
с мощностью порядка 109 FLOPS 151 экз.
Таблица 1. Десять самых мощных суперкомпьютеров в мире по состоянию на июль 1997 г.
| Рейтинг ТОР500 | Наименование машины | Страна-обладатель | Фирма-производитель | Количество процессоров | Мощность (GFLOPS) |
| 1 | Intel ASCI Red | США | Intel (США) | 7264 | 1068 |
| 2 | Hitachi/Tsukuba CP-PACS | Япония | Hitachi/Tsukuba (Япония) | 2048 | 368 |
| 3 | SGI/Cray T3E | Великобритания | Cray (США) | 696 | 265 |
| 4 | Fujitsu Numerical Wind Tunnel | Япония | Fujitsu (Япония) | 167 | 230 |
| 5 | Hitachi SR2201 | Япония | Hitachi (Япония) | 1024 | 220 |
| 6 | SGI/Cray T3E | Германия | Cray (США) | 512 | 176 |
| 7 | SGI/Cray T3E | США | Cray (США) | 512 | 176 |
| 8 | SGI/Cray T3E | Германия | Cray (США) | 512 | 176 |
| 9 | SGI/Cray T3E | США | Cray (США) | 512 | 176 |
| 10 | SGI/Cray T3E | США | Cray (США) | 512 | 176 |
Таблица 2. Первые пятнадцать стран из списка ТОР 500
| Рейтинг в Тор500 | Страна | Мощность (MFLOPS) | Год установки | Количество процессоров | Наименование компьютера |
| 1 | США | 1 068 000 | 1997 | 7264 | Intel ASCI Red |
| 2 | Япония | 368 200 | 1996 | 2048 | Hitachi/Tsukuba CP-PACS/2048 |
| 3 | Великобритания | 264 800 | 1997 | 696 | SGI/Cray T3E900 LC696-128 |
| 6 | Германия | 176 000 | 1996 | 512 | SGI/Cray T3E LC512-128 |
| 17 | Франция | 115 500 | 1997 | 256 | SGI/Cray T3E750 LC256-128 |
| 28 | Финляндия | 86 600 | 1996 | 192 | SGI/Cray T3E750 LC192-128 |
| 34 | Южная Корея | 69 300 | 1997 | 128 | SGI/Cray T3E900 LC128-128 |
| 50 | Швеция | 55 770 | 1996 | 184 | SGI/Cray T3E LC184-128 |
| 57 | Италия | 50 430 | 1996 | 128 | SGI/Cray T3E LC128-128 |
| 70 | Норвегия | 34 650 | 1997 | 88 | SGI/Cray T3E AC88-128 |
| 79 | Канада | 30 710 | 1995 | 16 | NEC SX-4/16 |
| 80 | Дания | 30 710 | 1997 | 16 | NEC SX-4/16 |
| 81 | Нидерланды | 30 710 | 1996 | 16 | NEC SX-4/16 |
| 83 | Швейцария | 30 710 | 1996 | 16 | NEC SX-4/16 |
| 93 | Австралия | 27 720 | 1996 | 13 | VPP300/13 |
Первое место в мире по количеству суперкомпьютеров занимают США 254 (51%). За ними следуют Япония 87 (17,5%), Германия 45 (9%), Великобритания 24 (4,8%), Франция 18 (3,6%), Корея 8 (1,6%), Канада 7 (1,4%), Швеция, Швейцария и Норвегия по 6 (1,2%). Россия упомянута в этом списке лишь один раз: на 156-ом месте находится компьютер HPC Ultra 10000 (пиковая производительность 16600 MFLOPS), произведенный фирмой SUN и установленный в Национальном Резервном Банке России. Хотелось бы верить, что это положение не совсем соответствует действительности. Интересная деталь: в США отсутствуют компьютеры иностранного производства американцы работают только на отечественных машинах и к тому же снабжают ими весь остальной мир.
Количество установок суперкомпьютеров возрастает год от года в геометрической прогрессии, причем основной объем опять же приходится на США. Интересно отметить, что главным образом в перечне присутствуют машины, выпущенные в течение последних двух лет, на долю остальных приходится не более четверти списка. Можно констатировать, что за последние 3 4 года список обновился практически полностью. Статистика по годам сложилась следующая: 1997 207 установок (по состоянию на июль 1997 г.), 1996 168 установок, 1995 52 установки, 1994 45 установок, 1993 16 установок, 1992 10 установок, 1991 всего 2 установки, рейтинги которых 128 и 195. Попробуем сделать прогноз увеличения числа суперкомпьютеров на ближайшие два года на основании статистики за последние шесть лет:
45 / 10 = 4,5
52 / 16 = 3,25
168 / 45 = 3,7
207 / 52 = 3,9.
Воспользовавшись средним коэффициентом роста за два года (3,8), вычислим ориентировочные значения установок на 1998 99 гг.:
168 х 3,8 = 638 установок в 1998 г.,
207 х 3,8 = 786 установок в 1999 г.
Таким образом, в ближайшие год-два можно ожидать перерастания списка ТОР 500 в ТОР 1500 (638 + 786 = 1424) или даже более.
Состав производителей суперкомпьютеров в мире представлен следующей иллюстрацией:
В списке значатся 11 фирм, причем четыре лидирующие в нем американские компании обеспечивают более 80% мирового рынка (402 установки из 500). Всего же производители США перекрывают 86% мирового производства суперкомпьютеров (Intel, TMC, DEC, Parsytec в общей сложности составляют 28 установок или 5,6%). Японские фирмы (Fujitsu, NEC, Hitachi) обеспечивают остальные 70 установок в ТОР500 (14%).
Прослеживается четкая зависимость между местом, занимаемым теми или иными странами в рассматриваемом списке, и уровнем инвестиций в информационные технологии в этих странах.
Таблица 3. Компьютеры из списка ТОР500, принадлежащие организациям, способным заниматься перехватом и дешифрованием информации
| Рейтинг | Производитель | Название | Мощность | Кем используются | Год установки | Кол-во процессоров |
| 7 | SGI/Cray | T3E LC512-128 | 176 000 | Правительство США | 1997 | 512 |
| 21 | SGI/Cray | T3D MC1024-8 | 100 500 | Правительство США | 1994 | 1024 |
| 85 | SGI/Cray | Y-MP T932/321024 | 29 360 | Правительство США | 1996 | 32 |
| 86 | SGI/Cray | Y-MP T932/321024 | 29 360 | Правительство США | 1997 | 32 |
| 205 | SGI/Cray | Y-MP C916/161024 | 13 700 | Правительство США | 1992 | 16 |
| 206 | SGI/Cray | Y-MP C916/161024 | 13 700 | Правительство США | 1992 | 16 |
| 207 | SGI/Cray | Y-MP C916/161024 | 13 700 | Правительство США | 1992 | 16 |
| 208 | SGI/Cray | Y-MP C916/161024 | 13 700 | Правительство США | 1992 | 16 |
| 209 | SGI/Cray | Y-MP C916/16512 | 13 700 | Правительство США | 1994 | 16 |
| 374 | SGI/Cray | POWER CHALLENGEarray | 9 398 | Правительство США | 1995 | 40 |
| 375 | SGI/Cray | POWER CHALLENGEarray | 9 398 | Правительство США | 1995 | 40 |
| 436 | SGI/Cray | POWER CHALLENGEarray | 7 831 | Правительство США | 1995 | 40 |
| 437 | SGI/Cray | POWER CHALLENGEarray | 7 831 | Правительство США | 1995 | 40 |
| 438 | SGI/Cray | POWER CHALLENGEarray | 7 831 | Правительство США | 1995 | 40 |
| 84 | TMC | CM-5/512 | 30 400 | АНБ (NSA) | 1993 | 512 |
| 217 | SGI/Cray | Y-MP C916/16512 | 13 700 | АНБ (NSA) | 1994 | 16 |
| 9 | SGI/Cray | T3E LC512-128 | 176 000 | НАСА (NASA) | 1996 | 512 |
| 315 | SGI/Cray | ORIGIN 2000 | 10 420 | NASA/Langley Research Center, Hampton | 1997 | 32 |
| 367 | IBM | SP2/48 | 9 530 | NASA/Langley Research Center, Hampton | 1994 | 32 |
| 98 | SGI/Cray | T3D MC256-8 | 25 300 | Defence Research Agency (Англия) | 1994 | 256 |
| 210 | SGI/Cray | Y-MP C916/16256 | 13 700 | Штаб-квартира Правительственной связи (UK) | 1994 | 16 |
| 15 | SGI/Cray | T3E LC256-256 | 13 870 | Океанографический офис ВМС США | 1997 | 256 |
| 23 | SGI/Cray | T3E LC256-128 | 93 200 | СNRS/IDRIS Оrsay, Франция | 1996 | 256 |
| 32 | SGI/Cray | T3E LC200-128 | 74 480 | ARPA, США | 1997 | 200 |
| 230 | SGI/Cray | T3D MC128-8 | 12 800 | Air Force Base Eglin USA | 1994 | 128 |
| 30 | IBM | SP2 P2 | 83 370 | Air Force Base Wright-Patterson USA | 1997 | 256 |
| 154 | SUN | Ultra HPC 10000 | 16 600 | МВД Ю.Кореи | 1997 | 48 |
| 155 | SUN | Ultra HPC 10000 | 16 600 | МВД Ю.Кореи | 1997 | 48 |
| 81 | NEC | SX-4/16 | 30 710 | National Aerospace Laboratory, Нидерланды | 1996 | 16 |
Мы рассмотрели список самых мощных в мире компьютеров столь подробно и разносторонне не случайно. Он послужит нам отправной точкой для исследования стойкости алгоритмов шифрования со случайным ключом в случае использования для их взлома современных ЭВМ.
Допустим, что рассматриваемые нами алгоритмы шифрования идеальны, то есть оптимальным методом их взлома будет прямой перебор всех возможных ключей данного алгоритма. Очевидно, что в этом случае стойкость криптосистем будет определяться длиной ключа. При проведении данного исследования предполагалось, что криптоаналитик противной стороны обладает всей информацией относительно алгоритма шифрования, за исключением данных о секретном ключе, и ему доступен для анализа шифртекст сообщения. По определению предполагается, что идеальный алгоритм лишен каких-либо недостатков, снижающих его криптостойкость.
Предположим также, что генерация ключа компьютером происходит за один такт его работы, а операция дешифрования мгновенно. Определив отношение количества ключей к быстродействию самого мощного компьютера, мы получим нижнюю оценку сложности дешифрования сообщения для идеального алгоритма. Результаты этих расчетов приведены в таблице 4. По теории вероятностей средним временем расшифровки сообщения (матожиданием времени дешифрования) следует считать половину приведенного в таблице времени (указано в скобках). В случаях, когда необходимый для полного перебора ключей период превышал 10 000 лет, среднее время дешифрования не указывалось.
Таблица 4. Время (в годах), необходимое в настоящий момент самым мощным суперкомпьютерам для полного перебора ключей
| Наименование машины |
Мощн. (FLOPS) |
56 бит = 7.2*Е16 ключей |
64 бита = 1.8*E19 ключей |
70 бит = 1.18*Е21 ключей | 75 бит = 3.78*Е22 ключей |
90 бит = 1.24*E27 ключей | 256 бит = 1,15*Е77 ключей |
| Intel ASCI Red | 1.068*Е12 | 0.002 г. (8,6 часа) |
0.534 г. (3,2 мес.) |
35 лет (17 лет) |
1122 г. (561 г.) |
36.8*Е6 | 3,4*Е57 |
| Hitachi/Tsukuba CP-PACS | 3.68*Е11 | 0,006 г. (25,8 часа) | 1,55 г. (9,3 мес.) | 101,7 г. (51 г.) |
3257 лет (1628 лет) |
106*Е6 | 9,9*Е57 |
| SGI/Cray T3E | 2.65*Е11 | 0.008 г. (34,6 часа) |
2.15 г. (25,8 мес.) |
141 г. (70 лет) |
4523 г. (2261 г.) |
148*Е6 | 1,37*Е58 |
| Fujitsu Numerical Wind Tunnel | 2.3*Е11 | 0.0099 г. (3,56 суток) |
2.48 г. (29,7 мес.) |
162 г. (81 г.) |
5211 г. (2605 лет) |
170*Е6 | 1,58*Е58 |
| Hitachi SR2201 | 2.2*Е11 | 0.0103 г. (3,7 суток) | 2.56 г. (30,7 мес.) |
170 лет (85 лет) |
5448 лет (2724 г.) |
179*Е6 | 1,66*Е58 |
По некоторым оценкам производительность компьютера, деленная на его стоимость, увеличивается в 10 раз за каждые 5 лет. Исходя из этого тезиса в течении следующих 50-ти лет быстродействие компьютеров будет возрастать следующим образом:
2005 год в 10 раз
2010 год в 100 раз
2015 год в 1 000 раз
2020 год в 10 000 раз
2025 год в 100 000 раз
2030 год в 1 000 000 раз
2035 год в 10 000 000 раз
2040 год в 100 000 000 раз
2045 год в 1 000 000 000 раз
2050 год в 10 000 000 000 раз
и т. д.
Попробуем проверить достоверность этого утверждения. По данным Большой Советской Энциклопедии (статья Цифровая вычислительная машина ), первая электронная ЦВМ ЭНИАК была построена в 1945 г. и вступила в строй в 1946 г. в США. С этого момента во многих странах начались активные исследования, направленные на создание надежных электронных цифровых элементов и разработку рациональных структур ЦВМ.
Скорость работы машин первого поколения (до середины 50-х годов) не превышала нескольких сотен операций в секунду. Предположим, что быстродействие самых первых машин равнялось 100 операциям в секунду и возьмем эту величину за точку отсчета. Поскольку с тех пор прошел 51 год (10,2 пятилетних периодов), то к 1997 году мощность компьютера должна была возрасти приблизительно до 100 * 1010,2 = 1012,2
операций в секунду, что и подтверждается приведенным выше списком ТОР 500.
В 1951 году Государственная комиссия приняла первую на европейском континенте и в СССР электронно-счетную машину МЭСМ с быстродействием 50 операций в секунду, созданной небольшой группой под руководством академика С. А. Лебедева. К настоящему моменту (97 51 = 46, 46/5 = 9,2) расчетная производительность такого рода машины должна быть 50 * 109,2 = 5 * 1010,2 операций в секунду. Самая мощная на европейском континенте ЭВМ, находящаяся в Великобритании, работает со скоростью 2,6 * 1011.
Таким образом, можно говорить, что прогноз 10 раз за 5 лет является достаточно обоснованным и достоверно описывает рост вычислительных мощностей на больших промежутках времени.
Определим, что x(t) непрерывная функция, показывающая быстродействие компьютеров в момент времени t. Исходя из принятой рабочей гипотезы 10 раз за 5 лет и начальной точки отсчета (t0 = 0 в 1946 г.), функция выглядит следующим образом: x(t) = С0 * 10t/5, где начальная точка отсчета C0 = 100 мощность первого компьютера ЭНИАК.
Введем следующие обозначения:
S
мощность алфавита, из которого извлекаются символы для ключа;
l
длина ключа;
||{K}|| = sl
мощность множества ключей;
Тм({K}, x(t))
максимальное время перебора ключей;
D ({K}, x(t))
матожидание дешифрования;
topt
оптимальный момент начала дешифрования;
Тб({K}, x(t))
время безопасности системы (зависит от двух параметров времени начала дешифрования t и его длительности D).
При сделанных предположениях время перебора всех ключей в заданном ключевом пространстве в момент t (максимальное время дешифрования сообщения) составит Тм = ||{K}||/x(t), а среднее время дешифрования сообщения половину максимального времени: D = 1/2 Тм
= 1/2 (||{K}||/x(t)). Исходя из прогноза об увеличении мощности компьютерных средств, можно было бы просто принять за основу, что длительность перебора через 100 лет должна составить некоторое заранее заданное время, например один год, и составить следующее уравнение типа ||{K}||/C1 * x(t+100) > 1, из которого следует, что необходимая длина ключа должна быть 136 137 бит. Однако можно дать более точные и полезные оценки для того, чтобы не расходовать впустую силы на те задачи, время которых еще не пришло.
Конечно, если подождать 100 лет, то силовая атака на криптографический алгоритм, реализация которой сегодня требует многих лет, в тот момент займет лишь несколько секунд, но из-за полной потери актуальности добытой информации исчезнет смысл ее проведения. Учитывая непрерывный рост мощности компьютерных средств, можно предположить, что дешифрование следует начинать не сразу по получении шифртекста, а в тот момент, когда оно потребует наименьшего времени. Выигрыш во многих случаях может быть очень значительным! Например, если на сегодняшний день процесс криптоанализа потребует 100 лет, то через 5 лет компьютерные мощности возрастут в 10 раз, и дешифрование, заняв 10 лет, закончится, в 2015 году. Через 10 лет производительность компьютеров возрастет в 100 раз и полный перебор вариантов, завершившись в течение одного года, даст результат уже в 2011 году. Таким образом, выигрыш во времени по сравнению с первым вариантом составляет 89 лет. Вопрос в том, можно ли еще сократить время криптоанализа за счет оптимального выбора момента его начала и сколько времени (начиная с этого момента) продлится оптимальное дешифрование.
Рабочая модель для расчета времени безопасности системы шифрования (1) состоит из суммы двух действующих факторов момент начала дешифрования плюс сложность дешифрования. Минимум этой функции назовем максимальным временем безопасности Тб
идеальной системы шифрования. Прилагательное максимальный введено только для того, чтобы подчеркнуть идеальность исследуемых алгоритмов в реальной жизни криптосистемы обладают определенными недостатками, снижающими их криптостойкость. Коэффициент C1 = 31 536 000 возникает при переходе от операций в секунду к операциям в год, и используется в основном для удобства.
(1)
Для определения минимума этой функции найдем ее производную и решим уравнение Тб? = 0. В результате решения и упрощения получаем следующее значение момента времени topt,
в котором достигается минимум функции Тб, то есть оптимальное время начала криптоанализа:
(2)
Подставив ||{K}|| в эту формулу, можно получить значение момента времени topt. Время безопасности идеальной системы шифрования определяется значением функции Тб в этой точке. Подставив в (1) мощность множества ключей ||{K}|| в исследуемой системе и значение topt
можно найти ее время безопасности Тб.
Среднее время дешифрования определяется по следующей формуле:
(3)
Самое неожиданный и интересный факт, на мой взгляд, заключается в том, что, если подставить значение topt в формулу (3) и произвести необходимые упрощения, то длительность начатого в оптимальный момент дешифрования независимо от длины ключа всегда одна и та же:
5 / ln10 = 2,171472409516 года
(739,13 дней или 19 035,12 часов).
Таким образом с помощью указанной рабочей модели можно оценивать надежность проектируемых и эксплуатируемых систем шифрования. Например, стойкость (в годах) алгоритмов с различной длиной ключа в наших оценках следующая:
| Длина ключа (бит) | Кол-во ключей | Оптимальное время начала дешифрования | Длительность дешифрования | Окончание дешифрования |
| 56 | 7,2 * Е 16 | 43,6 (1989,6 г.) | 2,17 | 45,77 (1991,77 г.) |
| 60 | 1,15 * E 18 | 49,6 (1995,6 г.) | 2,17 | 51,77 (1997,78 г.) |
| 62 | 4,6 * Е 18 | 52,6 (1998,6) | 2,17 | 54,77 (2000,8 г.) |
| 64 | 1,8 * Е 19 | 55,6 (2001,6 г.) | 2,17 | 57,77 (2003,77 г.) |
| 70 | 1,18 * Е 21 | 64,7 (2010,7 г.) | 2,17 | 66,87 (2012,87 г.) |
| 75 | 3,78 * Е 22 | 72,2 (2018,2 г.) | 2,17 | 74,37 (2020,37 г.) |
| 90 | 1,24 * Е 27 | 94,8 (2040,8 г.) | 2,17 | 36,96 (2042,87 г.) |
| 128 | 3,4 * Е 38 | 152 (2098 г.) | 2,17 | 94,15 (2100,17 г.) |
| 137 | 1,74 * Е 41 | 165,5 (2111,5 г.) | 2,17 | 167,69 (2113,69 г.) |
| 256 | 1,15 * Е 77 | 344,6 (2290,6 г.) | 2,17 | 286,79 (2292,77 г.) |
