Когда наступит время подбирать ключи.

Когда наступит время подбирать ключи.

Когда наступит время подбирать ключи

Группа известных специалистовкриптографов, созданная под эгидой Альянса производителей программного обеспечения для бизнеса (промышленной организации, препятствующей незаконному использованию программного обеспечения), пришла к выводу, что необходимая длина ключа в настоящее время должна быть не менее 75 битов с дальнейшим увеличением в течение последующих 20 лет до 90 битов.

Американцы люди серьезные и шутить такими вещами не будут. Но попробуйте, уважаемый читатель, разобраться, на чем основано это утверждение, и проверить точность заключения заокеанских специалистов.

С чего начнем? Если есть замок, который нужно открыть, но нет ключа, используют отмычку или другой подходящий (или не очень подходящий) инструмент. Если нужно вскрыть шифрсообщение, а методом взлома будет полный перебор ключей, то для этого нужен инструмент — мощный компьютер. С анализа возможностей современных компьютеров и начнем.

Еще в 60-х годах некоторые производители электронно-вычислительной техники начали создавать суперкомпьютеры — мощные машины для решения задач с большим объемом вычислений, применявшихся до последнего времени главным образом в военных целях. Как и все самое-самое, это направление развития компьютерной техники всегда вызывало повышенный интерес со стороны как специалистов, так и людей далеких от этой тематики. Видимо, в целях удовлетворения этого интереса с недавнего времени в открытой печати публикуется так называемый ТОР 500 — обновляемый два раза в год список пятисот самых мощных в мире эксплуатируемых суперкомпьютеров и крупнейших суперкомпьютерных центров (CKЦ) мира (табл. 1). Для составления первого списка используется достигнутая максимальная производительность по тесту Linpack parallel.

Табл.1.10 самых мощных суперкомпьютеров по состоянию на июль 1997

Из списка, появившегося летом 1997 года, следует, что по быстродействию суперкомпьютеры распределились следующим образом:
с мощностью порядка 1012 FLOPS —1 экз.;
с мощностью порядка 1011 FLOPS—20 экз.;
с мощностью порядка 1010 FLOPS—328 экз.;
с мощностью порядка 109 FLOPS—151 экз.

В табл. 2 приведен список первых 15 стран в порядке убывания производительности их самых мощных суперкомпьютеров. Если у некоторой страны имеется несколько суперкомпьютеров, то указывалась производительность самого мощного из них. Понятно, что наличие суперкомпьютеров показывает научно-технический потенциал страны, отражает ее военные возможности.

Табл.2.Первые 15 стран из списка Top500

Первое место в мире по количеству суперкомпьютеров занимают США—254 (51%). За ними следуют Япония — 87 (17,5%), Германия — 45 (9%), Великобритания—24 (4,8%), Франция—18(3,6%),Корея— 8 (1,6%), Канада—7 (1,4%), Швеция, Швейцария и Норвегия — по 6 (1,2%).

Россия упомянута в этом списке лишь один раз: на 156-м месте находится компьютер НРС Ultra 10000 (пиковая производительность 16600 MFLOPS), произведенный фирмой SUN и установленный в Национальном резервном банке России. Хотелось бы верить, что это положение не совсем соответствует действительности. Интересная деталь: в США отсутствуют компьютеры иностранного производства — американцы работают только на отечественных машинах и к тому же снабжают ими весь остальной мир.

Таблица 3. Компьютеры из списка ТОР500, принадлежащие организациям, способным заниматься перехватом и дешифрованием информации

Количество установок суперкомпьютеров возрастает год от года в геометрической прогрессии, причем основной объем опять же приходится на США. Интересно отметить, что главным образом в перечне присутствуют машины, выпущенные в течение последних двух лет, на долю остальных приходится не более четверти списка. Можно констатировать, что за последние 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) или даже более.

Состав производителей суперкомпьютеров в мире представлен на рис. 1.

Рис.1.

В списке значатся 11 фирм, причем четыре лидирующие в нем американские компании обеспечивают более 80% мирового рынка (402 установки из 500). Всего же производители США перекрывают 86% мирового производства суперкомпьютеров (Intel, ТМС, DEC, Parsytec в общей сложности составляют 28 установок, или 5,6%). Японские фирмы (Fujitsu, NEC, Hitachi) обеспечивают остальные 70 установок в ТОР500 (14%).

Прослеживается четкая зависимость между местом, занимаемым теми или иными странами в рассматриваемом списке, и уровнем инвестиций в информационные технологии в этих странах (рис. 2).

Рис.2.

Мы рассмотрели список самых мощных в мире компьютеров столь подробно и разносторонне не случайно. Он послужит нам отправной точкой для исследования стойкости алгоритмов шифрования со случайным ключом в случае использования для их взлома современных ЭВМ.

Допустим, что рассматриваемые нами алгоритмы шифрования идеальны, то есть оптимальным методом их взлома будет прямой перебор всех возможных ключей данного алгоритма. Очевидно, что в этом случае стойкость криптосистем будет определяться длиной ключа. При проведении данного исследования предполагалось, что криптоаналитик противной стороны обладает всей информацией относительно алгоритма шифрования, за исключением данных о секретном ключе, и ему доступен для анализа шифртекст сообщения. По определению предполагается, что идеальный алгоритм лишен каких-либо недостатков, снижающих его криптостойкость.

Предположим также, что генерация ключа компьютером происходит за один такт его работы, а операция дешифрования — мгновенно. Определив отношение количества ключей к быстродействию самого мощного компьютера, мы получим нижнюю оценку сложности дешифрования сообщения для идеального алгоритма. Результаты этих расчетов приведены в табл. 4. По теории вероятностей средним временем расшифровки сообщения (матожиданием времени дешифрования) следует считать половину приведенного в таблице времени (указано в скобках). В случаях, когда необходимый для полного перебора ключей период превышал 10 000 лет, среднее время дешифрования не указывалось.

Таблица 4. Время (в годах), необходимое в настоящий момент самым мощным суперкомпьютерам для полного перебора ключей

По некоторым оценкам производительность компьютера, деленная на его стоимость, увеличивается в 10 раз за каждые 5 лет. Исходя из этого тезиса, в течение следующих пятидесяти лет быстродействие компьютеров будет возрастать следующим образом:

2005 год—в 10 раз
2010 год—в 100 раз
2015 год—в 1000 раз
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 лет» и начальной точки отсчета (tg = О в 1946 г.), функция выглядит следующим образом: x(t) = С0 • 10t/5, где начальная точка отсчета С0 = 100— мощность первого компьютера ЭНИАК.

Введем следующие обозначения:

S — мощность алфавита, из которого извлекаются символы для ключа;
L — длина ключа;
||{К}|| = SL — мощность множества ключей;
Тm({К}, x(t)) — максимальное время перебора ключей;
D ({К}, x(t)) — матожидание дешифрования;
topt , — оптимальный момент начала дешифрования;
Tб({K}, x(t)) — время безопасности системы (зависит от двух параметров — времени начала дешифрования t и его длительности D).

При сделанных предположениях время перебора всех ключей в заданном ключевом пространстве в момент t (максимальное время дешифрования сообщения) составит Тm = = ||{K}|| / x(t), а среднее время дешифрования сообщения — половину максимального времени: D = 1/2 Тm = = 1/2 (||{K}|| / x(t)). Исходя из прогноза об увеличении мощности компьютерных средств, можно было бы просто принять за основу, что длительность перебора через 100 лет должна составить некоторое заранее заданное время, например один год, и составить следующее уравнение типа ||{К}|| / Cl • x(t+100) > 1, из которого следует, что необходимая длина ключа должна быть 136-137 бит. Однако можно дать более точные и полезные оценки для того, чтобы не расходовать впустую силы на те задачи, время которых еще не пришло.

Конечно, если подождать 100 лет, то силовая атака на криптографический алгоритм, реализация которой сегодня требует многих лет, в тот момент займет лишь несколько секунд, но из-за полной потери актуальности добытой информации исчезнет смысл ее проведения. Учитывая непрерывный рост мощности компьютерных средств, можно предположить, что дешифрование следует начинать не сразу по получении шифртекста, а в тот момент, когда оно потребует наименьшего времени. Выигрыш во многих случаях может быть очень значительным! Например, если на сегодняшний день процесс криптоанализа потребует 100 лет, то через 5 лет компьютерные мощности возрастут в 10 раз, и дешифрование, заняв 10 лет, закончится в 2015 г. Через 10 лет производительность компьютеров возрастет в 100 раз, и полный перебор вариантов, завершившись в течение одного года, даст результат уже в 2011 г. Таким образом, выигрыш во времени по сравнению с первым вариантом составляет 89 лет. Вопрос в том, можно ли еще сократить время криптоанализа за счет оптимального выбора момента его начала и сколько времени (начиная с этого момента) продлится оптимальное дешифрование.

Рабочая модель для расчета времени безопасности системы шифрования (1) состоит из суммы двух действующих факторов — момент начала дешифрования плюс сложность дешифрования. Минимум этой функции назовем максимальным временем безопасности Tб идеальной системы шифрования. Прилагательное «максимальный» введено только для того, чтобы подчеркнуть идеальность исследуемых алгоритмов — в реальной жизни криптосистемы обладают определенными недостатками, снижающими их криптостойкость. Коэффициент Сl=31 536 000 возникает при переходе от операций в секунду к операциям в год и используется в основном для удобства.

Для определения минимума этой функции найдем ее производную и решим уравнение Tб’ = 0. В результате решения и упрощения получаем следующее значение момента времени topt в котором достигается минимум функции Tб, то есть оптимальное время начала криптоанализа:

Подставив ||{К}|| в эту формулу, можно получить значение момента времени topt. Время безопасности идеальной системы шифрования определяется значением функции Tб в этой точке. Подставив в (1) мощность множества ключей ||{К}|| в исследуемой системе и значение topt можно найти ее время безопасности Tб.

Среднее время дешифрования определяется по следующей формуле:

Самый неожиданный и интересный факт, на мой взгляд, заключается в том, что если подставить значение topt в формулу (3) и произвести необходимые упрощения, то длительность начатого в оптимальный момент дешифрования независимо от длины ключа всегда одна и та же: 5 / ln 10 == 2,171472409516 года (739,13 дней или 19 035,12 часов).

Тб = topt +2,17

Таким образом, с помощью указанной рабочей модели можно оценивать надежность проектируемых и эксплуатируемых систем шифрования. Например, стойкость (в годах) алгоритмов с различной длиной ключа в наших оценках приводится в табл. 5. Расчеты производились по формуле (2) для третьего столбца и формуле (1) для пятого столбца, а все данные отсчитывались от начального момента времени —1946 г. В качестве примера проведенных вычислений рассмотрим алгоритм шифрования с 70-разрядным ключом. В соответствии с формулой (2) оптимальный момент начала его взлома— 64,7 года, или 1946 + 64,7 = = 2010,7 год, то есть 12 августа 2010 г. Процесс, запущенный в этот день, продлится 2 года 2 месяца 1 день 17 часов 31 минуту и завершится 13 октября 2012 года в 4 часа 48 минут.

Таблица 5. Оптимальный момент начала дешифрования, его продолжительность и момент окончания в зависимости от длины ключа

Конечно, все приведенные результаты справедливы лишь в среднем. Длительность дешифрования каждого отдельного сообщения может варьироваться от 0 до Тm, но поставленное на поток (в промышленных масштабах) оно будет стремиться к указанным выше величинам.

Какую еще пользу можно извлечь из построенной теории? Практически полезной может оказаться формула зависимости длины ключа от заранее заданного nl — года начала дешифрования.

Например, требуется закрыть некоторую информацию таким образом, чтобы в течение 20 лет гарантированно сохранить ее конфиденциальность. Какой в этом случае должна быть длина ключа?

Сегодня 1998 г., информация не должна быть расшифрована до 2018 г., следовательно, nl= 2018-1946 = 72 г. Произведя необходимые вычисления, получаем, что мощность множества ключей ||{К}|| должна составлять не менее 3,444 • 10^22, а длина ключа — приблизительно 74,87 бита.

Да, правы оказались американские критптографы! На основании этих же вычислений можно сделать вывод, что этот срок рассматривается ими как вполне достаточный для устаревания дешифруемой информации. Проверим их утверждение относительно того, что через 20 лет необходимая длина ключа должна составить 90 бит.

Через 20 лет наступит 2018 год, следовательно, чтобы обеспечить требуемую стойкость информации, оптимальное время дешифрования должно наступить не ранее 2038 г. (2038-1946 = 92 г.).

Вычисленная по формуле (4) мощность множества ключей должна составить 3,444 • 1022, а длина ключа—88,16 бита.

Незначительное различие между полученными результатами и результатами, предлагаемыми американскими специалистами с мировой известностью, подтверждает математическую корректность и обоснованность предложенной нами теории и ее главной исходной посылки — быстродействие компьютеров десятикратно увеличивается каждые 5 лет. Имеющиеся расхождения могут зависеть, например, от точности вычислений различных калькуляторов или от значения константы Сl, (количества секунд в году), если учитывать, что в году не 365 дней, а 365 дней 6 часов 40 минут.

Также подтверждают предложенную теорию и сведения о взломе в 1997 г. сообщений с ключами длиной в 40, 48 и 56 битов, время безопасности которых закончилось уже давно, составив соответственно 19,5 (1965 г.), 31,56 (1977 г.), 43,6 (1989 г.) года. Более того, пользуясь приведенными выше формулами, в 1998 г. можно обоснованно предполагать взлом ключей длиной до 62 битов включительно. А вот ключи с большим числом разрядов в 1998 году взломаны не будут! Автор готов заключить пари по этому поводу с любым желающим.

Еще один вывод состоит в том, что запрет американских законодателей на экспорт криптографических продуктов с длиной ключа более 56 битов рассчитан на быстродействие компьютеров десятилетней давности и не обеспечивает на сегодняшний день безопасности передаваемой информации.

На этом фоне гораздо привлекательнее выглядит криптография России, которая уже в течение 10 лет в качестве стандарта предлагает 256битовый ключ, безопасность которого гарантирована на 300 лет вперед — до 2290 года.