Когда наступит предел?. Статья обновлена в 2023 году.

Когда наступит предел?

Когда наступит предел?

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

Возраст Вселенной оценивается в 20 млрд лет. Земли — в 4,5, обезьяна превратилась в человека 10 000 лет тому назад, и около 3 000 лет людям знакомо искусство криптографии. Наконец, лишь 55 лет отделяют нас от момента появления первого компьютера. Еще 20 лет назад алгоритмы шифрования с длиной ключа 56 бит удовлетворяли самым взыскательным требованиям, сегодня же уровень их надежности определяется как минимум 75 разрядами и согласно авторитетным оценкам через 20 лет эта планка поднимется до 90. Тем не менее уже сейчас существуют алгоритмы с длиной ключа 128, 168 и 256 бит.

Зададимся вопросом: если Солнце будет светить еще в течение 100 млн лет, каким числом будет измеряться длина ключа к тому времени, когда оно погаснет? Ведь, образно говоря, на сегодняшний день человеческая цивилизация в своем развитии сделала только первый шаг из 10-километрового пути!

Логично предположить, что длина ключа не может возрастать бесконечно. Хотя бы потому, что не бесконечна скорость света как максимальная скорость передачи информации, не бесконечна и масса Вселенной, а следовательно, количество атомов в ней, используя которые можно записывать информацию. То есть конечны именно те факторы, которые, по всей видимости, положат конец дальнейшему увеличению длины ключа для алгоритмов шифрования. Насколько известно автору, подобный подход к рассматриваемому вопросу ранее не обсуждался в открытых исследованиях и может представлять самостоятельный интерес. Попробуем поэтому построить несколько верхних оценок для максимальной длины ключа, основываясь на простейших сведениях из Большой Совесткой энциклопедии и ряда других энциклопедических изданий.

Одна из оценок максимальной длины ключа для идеальных алгоритмов шифрования связана с определением максимального быстродействия процессора, основанным на парадоксальном, на первый взгляд, утверждении, что быстродействие процессора тем выше, чем меньше его размер. Введем следующие обозначения: V — скорость света в вакууме — 3*10^8 м; R — размеры aтомов — 10^(-10) м.

Предположим, что размеры процессора и атома одинаковы. Тогда в наших обозначениях быстродействие гипотетического процессора выразится формулой V/R=3*10^18 - столько раз за 1 секунду свет пройдет расстояние, равное размеру атома. Учитывая, что в году приблизительно 31 536 000 секунд, за этот временной отрезок наш гипотетический процессор совершит 9,46*10^25 операций, то есть сможет осуществить полный перебор ключевой последовательности длиной до 86,4 битов. Более быстрый процессор невозможен в принципе, следовательно более быстрое дешифрование методом тотального перебора ключей также принципиально невозможно!

Один подобный процессор приблизительно равен по быстродействию одновременной работе трех миллионов суперкомпьютеров Intel ASCI Red (точное значение — 2 999 746,3).

Если исходить из предположения, что шифр должен быть гарантирован от взлома на протяжении 100 лет, то за указанный период гипотетический процессор совершит 10^28 операций или сможет перебрать 10^28 ключей при условии, что за один такт своей работы он будет обрабатывать один ключ. Переведенная на язык битов длина раскрытого ключа составит около 93 бит.

Вывод: все ключи длиной более 93 бит гарантируют стойкость шифра в течении 100 лет, а введение избыточной длины только тормозит процессы шифрования и дешифрования.

Очевидно, что ускорить процесс обработки ключевых последовательностей возможно только:- уменьшив размеры атома-увеличив скорость света-увеличив количество процессоров в системе

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

Однако отметим, что увеличение количества процессоров в системе тоже не может быть бесконечным. Для нашей планеты естественным пределом является площадь земной поверхности. Если выразить поверхность земного шара (считая океаны, пустыни, Арктику и Антарктику) в квадратных миллиметрах и на каждый миллиметр поместить по миллиону суперпроцессоров, мощность такого вычислительного устройства составит 5,1*10^52 операций в год, что эквивалентно длине ключа в 175-176 бит. За 100 лет непрерывной работы, определенных нами за достаточный срок стойкости алгоритма, система сможет перебрать 5*10^54 ключей или произвести успешную силовую атаку на 181-182-разрядный ключ. И это при том условии, что вычислительные ресурсы процессоров полностью направлены на решение поставленной задачи и никакая их часть не тратится на согласование работы в системе (в многопроцессорных комплексах на это обычно расходуется около 20% мощности каждого процессора.

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

Вторая оценка, которая из-за своей очевидной недостижимости может представлять только теоретический интерес, вытекает из следующих соображений: масса Вселенной - приблизительно 10^50 грамм, и почти вся она состоит из водорода. В 1 грамме водорода приблизительно 6*10^23 атомов. Если предположить когда-либо в будущем достижение плотности записи ключ/атом, то становиться очевидно, что Вселенная может содержать 6*10^73 ключей. Длина ключа в этом случае составит 245,08 бит.

При более реальной плотность записи информации бит/атом количество возможных ключей несколько уменьшиться и составит 2,53*10^71, а длина ключа - 273,2 бит.

Для того чтобы перебрать все эти ключи со скоростью гипотетического процессора, понадобится в случае «ключ/атом» — 6*10^47 лет, а в случае «бит/атом» —6*10^45 лет. Описанной выше системе «Планета Земля» для реализации перебора понадобится 1,2*10^21 лет и 5*10^18 лет соответственно.

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

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

Страна Золотые резервы (тонн) Валютные резервы (млрд. долларов) Сумма (млрд. долларов) Intel ASCI Red Ключей в год Длина ключа (бит)
США 8142,6 75,71 157,14 2857 9*10^22 76,3
Япония 753,6 143,55 151,1 2747 8,66*10^22 76,3
Германия 2865,3 82.05 110,7 2012,7 6,35*10^22 75,7
Китай 395,0 59,35 63,3 1151 3,63*10^22 74,9
Великобритания 1198,4 41 53 963,63 3*10^22 74,7
Франция 2545,8 26,62 52,1 947,3 3*10^22 74,7
Италия 2073,7 28.24 49 891 2,8*10^22 74,4
Нидерланды 1081,5 37,49 48,3 878,2 2,8*10^22 74,4
Швейцария 2590,3 32 57,9 507,3 1,6*10^22 73,7
Россия 241,3 10,09 12,5 227,3 0,72*10^22 72,6


Золотовалютные резервы отдельных стран по данным международной финансовой статистики (по состоянию на 1995 г., газета «Труд» от 19 октября 1995 г.)

Приведенная таблица показывает величину золотовалютных резервов десяти наиболее богатых государств мира. Стоимость одного грамма золота при расчетах была принята равной 10 долларам. Исходя из того, что стоимость одного суперкомпьютера Intel ASCI Red составляет 55 млн долл., в графе 5 приведено их количество, приобретение которого может себе позволить та или иная страна. Вытекающие отсюда возможности решения криптографических задач отражены в графах 6 и 7.

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

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

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

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