Оценка надежности криптоалгоритмов в зависимости от длины ключа

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

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

С физической точки зрения транзистор, который является основой современной интегральной схемы, может быть уменьшен еще примерно в 10 раз, до размера 0,03 микрон. За этой гранью процесс включения выключения микроскопических переключателей станет практически невозможным. Таким образом максимальное быстродействие составит - 1016 операций секунду, а предел роста наступит приблизительно в 2030 г. Попробуем проанализировать предельные значения двух указанных тенденций.

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

Предположим, что размер процессора равен размеру атома. Тогда в наших обозначениях быстродействие гипотетического процессора выразится формулой F Vc Ra 3 1018 операций в секунду, где Vc 3 10 8 м с скорость света в вакууме, а Ra 10-10 м - размеры атомов. Столько раз за 1 секунду свет пройдет размеры атома. Поскольку период обращения Земли вокруг Солнца составляет 365,2564 суток или 31 558 153 секунд, то за один год такой процессор выполнит 94674459 10181026 операций. Более быстрый процессор в нашей вселенной невозможен в принципе. Один такой процессор по быстродействию превосходит более двух миллионов самых современных суперкомпьютеров Intel ASCI Red стоимостью 55млн долл работающих одновременно, и состоящих из 9152 процессоров Pentium каждый, точное значение - 2 242 152,466. Производительность одного процессора в системе Intel ASCI Red - 1,456 108 операций в секунду.

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

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

Попробуем, поэтому, проанализировать предельные значения двух указанных тенденций. Таблица 2.1 Десять самых мощных суперкомпьютеров в мире. Наименование машины Страна-обладатель Фирма-производитель Процессоры Мощность GFLOPS 1 Intel ASCI Red США Intel 9125 1333 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.2Время, необходимое для полного перебора ключейНаименование машины Мощность FLOPS 56 бит 7.2 Е16 64 бита 1.8 E19 80 бит 1.2 Е24 100 бит 1.26 Е30 128 бит 3.4 E38 Intel ASCI Red 1.333 Е12 14 часов 5 мес. 28460 лет 3.01 Е10 8.09 Е18 Hitachi Tsukuba CP-PACS 3.68 Е11 52 часа 18 мес. 102676 года 1.09 Е11 2.93 Е19 SGI Cray T3E 2.65 Е11 69 часов 51 мес. 143256 года 1.51 Е11 4.07 Е19 Fujitsu Numerical Wind Tunnel 2.3 Е11 171 час 60 мес. 164592 года 1.74 Е11 4.69 Е19 Hitachi SR2201 2.2 Е11 178 часов 61 мес. 172720 лет 1.82 Е11 4.9 Е19 Таким образом с помощью указанной рабочей модели можно оценивать надежность проектируемых и эксплуатируемых систем шифрования.

Алгоритм ГОСТ 28147-89 использует таблицу подстановок размером 512 бит. Общее число возможных таблиц составляет 1.33 Е36 и полное время перебора составляет 3.162 Е16 лет. Для алгоритма IDEA длина ключа составляет 128 бит и полное время перебора составляет 8.09 Е18 лет. Даже если будет использован суперкомпьютер состоящий из ста тысяч процессоров с максимально возможной скоростью в 1016 операций секунду для расшифровывания ГОСТа понадобится 4.21 Е7 лет, а для IDEA - 1.08 Е10 лет. Очевидно, что даже применение нескольких сотен суперкомпьютеров Intel ASCI Red, стоимостью по 55 миллионов долларов каждый, не в стоянии кардинально улучшить ситуацию.

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

Для нашей планеты естественным пределом является площадь земной поверхности. Если выразить поверхность земного шара считая океаны, пустыни, Арктику с Антарктикой в квадратных миллиметрах, и на каждый миллиметр поместить по миллиону таких процессоров, то в год мощность такого вычислительного устройства составит 5.1 1052 операций, что эквивалентно длине в 175-176 бит. Если исходить из предположения, что стойкость шифра должна составлять 100 лет, то за указанный период такая система сможет перебрать 5 1054 ключей, что составит 181-182 бита. И это притом, что никакие вычислительные ресурсы процессоров не тратятся на согласование их взаимной работы в системе, на решение задачи дешифрования и т.д. Таблица 2.3 Варианты перебора ключа раскладок клавиатуры Раскладка Символы Варианты Минимальная длина пароля 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZАБВГ ДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ 68 2.11 Е18 10 ABCDEFGHIJKLMNOPQRSTUVWXYZ АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ 58 2.49 Е19 11 0123456789АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭ ЮЯ 42 3.01 Е19 12 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ 36 4.74 Е18 12 АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ 32 3.67 Е19 13 ABCDEFGHIJKLMNOPQRSTUVWXYZ 26 6.45 Е19 14 0123456789 10 1 Е19 19 Из проведенного нами исследования можно сделать вывод, что для обеспечения надежности достаточно использовать алгоритмы с длиной ключа не менее 64 битов, а применять и разрабатывать алгоритмы с длиной ключа более 128 бит экономически не выгодно.

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

В таком случае для обеспечения необходимой защиты требуется использовать пароль не короче 12 символов, что соответствует 56-битному ключу. 16-символьный гарант пароль соответствует 75-битному ключу и гарантирует достаточную защиту от прямой атаки. 3.2