Криптографическая стойкость это способность шифрсистемы противостоять попыткам ее математического анализа.
Ключевое поле – количество вариантов ключей
Криптология оперирует большими числами, однако громадье цифр не должно никого вводить в заблуждение.
Количество вариантов ключей шифра моноалфавитной замены, известного нам по рассказу Конан Дойля «Пляшущие человечки» равно количеству всевозможных перестановок 26 элементов (26 букв латинского алфавита) т.е. 26! или 403,291,461,126,605,635, 584,000,000. Понятно, что даже с использованием арифмометра, перебор задача не самая простая. Впрочем, не только арифмометра.
Значительно повышает стойкость шифра использование нескольких алфавитов. Такие шифры получили название – шифры многоалфавитной (полиалфавитной) замены. В практической реализации возможно применение 5-ти различных алфавитов, в этом случае количество возможных ключей возрастет до (26!)5 т.е. 2441. В этом случае ключ будет состоять из 130 букв и возможность его запоминания вызывает большие сомнения.
На этом принципе основан один из самых известных шифров- шифр Виженера, имеющий «двоякую природу». Его можно отнести и к блочным и к поточным шифрам. При рассмотрении его как блочного шифра, при использовать все тех же 5 замещающих алфавитов из 26 букв количество возможных ключей составит 265=223 . А сам ключ будет состоять из 5 чисел находящихся между 0 и 25
В потоковом варианте ключом является определенная последовательность букв (лозунг), на основании которой формируется поток ключей. Пример – шифр ОГПУ 1926 г. СК «Скандинавия», использовавшийся Р. Зорге с лозунгом «SABWAY». Однако это лишь первый шаг, в итоге ряда преобразований получался т.н. квадратный пропорциональный шифр. Эта самая пропорциональность позволяла уменьшить количество входящих в шифровку знаком на 25-50% , в зависимости от ее длины.
Теоретическое ключевое пространство самой знаменитой шифровальной машины – немецкой «Энигмы», в самом простом 3-х дисковом исполнении составляло
3,283,883,513,796,974,198,700,882,069,882,752,878,379,955,261,095,623,685,444,055,315,226,006,433,615,627,409,666,933,182,371,154,802,769,920,000,000,000 вариантов, то есть 3х10114
Для флотского 4-дискового варианта 23,276,989,683,567,292,244,023,724,793,447,227,628,130,289,261,173,376,992,586,381,072,041,865,764,882,821,864,156,921,211,571,619,366,980,734,115,647,633,344,328,661,729,280,000,000,000,000,000, то есть 2х10145
Учитывая, что количество атомов в наблюдаемой вселенной составляет 1080 уверенность немецких криптографов в своей машине представляется вполне обоснованной.
Однако англичанам стали известны некоторые константы машины, правила работы и другая информация.
Дешифровка (взлом) «Энигмы был сведен к определению суточного ключа, который:
для 3-х дисковой машины составлял 107,458,687,327,250,619,360,000 т.е. 1,07х1023 что соответствует 74 битному ключу
а для 4-х дискового исполнения 3,1х1026, а это эквивалентно уже 84-битному ключу
Для понимания, что собой представляет число 1,07х1023:
Если взять такое количество листов бумаги толщиной 0.1 мм, то получиться 70 000 000 стопок «высотой» от Земли до Солнца.
В случае же использования в качестве единицы измерения миллиметра то данное количество миллиметров эквивалентно расстоянию 11 350 световых лет.
Ну а возраст вселенной в секундах(!) составляет 4,354х1017 то есть многократно меньше ключевого поля простенькой «Энигмы»
Особенно подобные сравнения почему-то любят представители IT сообщества. Для взлома 64-битного ключа методом перебора компьютеру, выполняющему 1 млн. операций в секунду понадобиться 5000 лет.
А для взлома 128 битного ключа 1025 лет, при том, что вселенная существует 1,4х1010 лет.
Если создать суперкомпьютер, в котором 1 млн. микросхем, каждая из которых выполняет 1 млн. операций в секунду то для взлома DES (256) понадобилось бы 20 минут и т.п.
После таких утверждений приходят на ум строки из оценки криптографической стойкости Энигмы немецкими специалистами:
«С математической точки зрения мы не можем говорить о теоретически абсолютной неразрешимости криптограммы, но из-за специальных процедур, выполняемых машиной «Enigma», разрешимость настолько далека от практической возможности, что шифр система машины, при правильном использовании ключей, должна рассматриваться как практически неспособная к решению.”
К чему привела такая уверенность широко известно.
Американская шифровальная машина SIGABA, так же периода второй мировой войны, имела ключевое пространство 2Х1032 = 2107,3
Позднее машина была несколько упрошена и этот показатель составил 1.7х1030 =2100,4.
Более того до тех пор, пока противник не захватил или восстановил машину число вариантов достигало 2992.8 .
В США было изготовлено 10 060 таких машин и около 450 000 шифрдисков к ним.
О чем говорят эти числа?
Да в общем то ни о чем. Шерлок Холмс расшифровал сообщение, Чарльз Бэббидж разработал алгоритм атаки на шифр Виженера еще в 1854 году. Англичане читали «Энигму», а один из первых советских электронных шифраторов «Ангстрем-3», при контрольной проверке, был вскрыт без всяких проблем, не смотря на «астрономическое» ключевое поле.
Можно добавить, что с сообщением на русском языке Шерлоку пришлось бы повозиться ненамного дольше не смотря на большее количество букв. При знании статистики языка (наиболее употребляемые буквы СЕНОВАЛИТР в русском и ASINTOER в английском) такой шифр вскрывается уже при наличии 24 знаков.
Вышеприведенные числа характеризуют лишь затраты машинного времени на проведение тотального перебора всех возможных комбинаций. Сегодня, хакеры называют этот метод «тупой брут форс». Здесь ключевое слово — тупой. Сразу же возникает вопрос, что гарантирует нахождение правильной комбинации в конце перебора, а не в его начале?
Уровни (типы) криптографической стойкости
Сегодня приняты три уровня криптографической стойкости: вычислительная, информационно-теоретическая и доказуемая.
Вычислительная криптографическая стойкость – у противника, при современном уровне развития криптоанализа, не существует необходимых вычислительных и временных ресурсов для вскрытия шифрсистемы
Шифрсистема считается вычислительно стойкой, если при ее криптоанализе необходимо выполнить не менее 280 операций
Информационно-вычислительная стойкость (абсолютная стойкость) – невозможность вскрытия шифрсистемы ни теоретически, ни практически, даже если в распоряжении криптоаналитиков неограниченно большие вычислительные ресурсы.
Доказательства этого типа криптографической стойкости выводят из теории информации
Доказуемая стойкость – если доказательство стойкости криптографической системы предоставляется в виде решения конкретной, трудно решаемой математической проблемы.
Все эти «новации», в основном, возникли после прихода в криптографию «айтишников» и прочих «связистов».
Сразу же возникает вопрос – к какому уровню криптографической стойкости отнести шифр гаммирования? Если уже имеются «абсолютно стойкие» шифры, выведенные из теории информации (очень странная формулировка)
Однако если очень хочется то можно, например, назвать этот шифр «абсолютно стойким «по Шеннону» Почему именно «по Шеннону» а не «по Котельникову» вопрос отдельный.
Сегодня существует только один шифр гарантированной (абсолютной) стойкости, не вскрываемость которого доказана математически. Это шифр Вернама (шифр одноразовых блокнотов) известный в нашей стране как шифр гаммирования
Все остальные шифрсистемы могут быть взломаны, как минимум теоретически, ибо не доказано обратное.
Из вышесказанного совсем не следует, что все другие шифры, не подлежат применению. Все зависит от ценности шифруемой информации. Это единственный параметр, а все «бухгалтерские» соображения, в данном случае, значения не имеют.
Следовательно, необходимо ввести какую-то вероятностную оценку и т.д.
В общем случае, гарантированная оценка стойкости — это отношение Q/P. Где Q – трудоемкость метода, P – надежность метода, то есть вероятность правильного определения ключа. Криптоанализ системы проводится по всем известным методам ее вскрытия, а не только по методу тотального перебора. Минимальное отношение Q/P является гарантированной оценкой стойкости. При желании можно вводить различные коэффициенты учитывающие, например прогноз развития вычислительных мощностей или другие параметры.
В начале 60-х годов в СССР минимально допустимая гарантированная оценка стойкости составляла 1025
Однако способность шифра противостоять математическим методам анализа (криптографическая стойкость) это только один фактор обеспечения безопасности шифрованной связи. Да, значительный, но один из.
Из этого следует, что в реальной жизни законы Керкгоффса вряд ли потеряют свою актуальность в обозримом промежутке времени. В 1972 г. в США было 325 случаев утери ключевой документации но ни один из них, по заключениям АНБ, не нанес кого-либо ущерба.
