Ключевое поле простенькой «Энигмы» 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 вариантов
Криптографическая стойкость — это способность шифрсистемы противостоять попыткам ее математического анализа.
Ключевое поле – количество вариантов ключей
Криптология оперирует большими числами, однако громадье цифр не должно никого вводить в заблуждение.
Количество вариантов ключей шифра моноалфавитной замены, известного нам по рассказу Конан Дойля «Пляшущие человечки» равно количеству всевозможных перестановок 26 элементов (26 букв латинского алфавита) т.е. 26! или 403,291,461,126,605,635, 584,000,000. Понятно, что даже с использованием арифмометра, перебор задача не самая простая. Впрочем, не только арифмометра.
Значительно повышает стойкость шифра использование нескольких алфавитов. Такие шифры получили название – шифры многоалфавитной (полиалфавитной) замены. В практической реализации возможно применение 5-ти различных алфавитов, в этом случае количество возможных ключей возрастет до (26!)^5 т.е. 2^441. В этом случае ключ будет состоять из 130 букв и возможность его запоминания вызывает большие сомнения.
На этом принципе основан один из самых известных шифров- шифр Виженера, имеющий «двоякую природу». Его можно отнести и к блочным, и к поточным шифрам. При рассмотрении его как блочного шифра, при использовать все тех же 5 замещающих алфавитов из 26 букв количество возможных ключей составит 26^5=2^23, а сам ключ будет состоять из 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х10^114
Для флотского 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х10^145
Учитывая, что количество атомов в наблюдаемой вселенной составляет 10^80 уверенность немецких криптографов в своей машине представляется вполне обоснованной.
Однако англичанам стали известны некоторые константы машины, правила работы и другая информация.
Дешифровка (взлом) «Энигмы» была сведена к определению суточного ключа, который:
для 3-х дисковой машины составлял 107,458,687,327,250,619,360,000 т.е. 1,07х10^23 что соответствует 74 битному ключу
а для 4-х дискового исполнения 3,1х10^26, а это эквивалентно уже 84-битному ключу
Для понимания, что собой представляет число 1,07х10^23:
Если взять такое количество листов бумаги толщиной 0.1 мм, то получиться 70 000 000 стопок «высотой» от Земли до Солнца.
В случае же использования в качестве единицы измерения миллиметра то данное количество миллиметров эквивалентно расстоянию 11 350 световых лет.
Ну а возраст вселенной в секундах(!) составляет 4,354х10^17, то есть многократно меньше ключевого поля простенькой «Энигмы»
Особенно подобные сравнения почему-то любят представители ITсообщества.
Для взлома 64-битного ключа методом перебора компьютеру, выполняющему 1 млн. операций в секунду понадобиться 5000 лет.
А для взлома 128 битного ключа 10^25 лет, при том, что вселенная существует 1,4х10^10 лет.
Если создать суперкомпьютер, в котором 1 млн. микросхем, каждая из которых выполняет 1 млн. операций в секунду то для взлома DES (256) понадобилось бы 20 минут и т.п.
После таких утверждений приходят на ум строки из оценки криптографической стойкости «Энигмы» немецкими специалистами:
«С математической точки зрения мы не можем говорить о теоретически абсолютной неразрешимости криптограммы, но из-за специальных процедур, выполняемых машиной «Enigma», разрешимость настолько далека от практической возможности, что шифр система машины, при правильном использовании ключей, должна рассматриваться как практически неспособная к решению»
К чему привела такая уверенность широко известно.
Американская шифровальная машина SIGABA, так же периода второй мировой войны, имела ключевое пространство 2Х10^32 = 2^107,3
Позднее машина была несколько упрошена и этот показатель составил 1.7х10^30 =2^100,4.
Более того до тех пор, пока противник не захватил или восстановил машину число вариантов достигало 2^992.8.
В США было изготовлено 10 060 таких машин и около 450 000 шифрдисков к ним.
О чем говорят эти числа?
Да в общем то ни о чем. Шерлок Холмс расшифровал сообщение, Чарльз Бэббидж разработал алгоритм атаки на шифр Виженера еще в 1854 году. Англичане читали «Энигму», а один из первых советских электронных шифраторов «Ангстрем-3», при контрольной проверке, был вскрыт без всяких проблем, не смотря на «астрономическое» ключевое поле.
Можно добавить, что с сообщением на русском языке Шерлоку пришлось бы повозиться ненамного дольше не смотря на большее количество букв. При знании статистики языка (наиболее употребляемые буквы СЕНОВАЛИТР в русском и ASINTOER в английском) такой шифр вскрывается уже при наличии 24 знаков.
Вышеприведенные числа характеризуют лишь затраты машинного времени на проведение тотального перебора всех возможных комбинаций. Сегодня, хакеры называют этот метод «тупой брут форс». Здесь ключевое слово — тупой. Сразу же возникает вопрос, что гарантирует нахождение правильной комбинации в конце перебора, а не в его начале?
Сегодня существует только один шифр гарантированной (абсолютной) стойкости, не вскрываемость которого доказана математически. Это шифр Вернама (шифр одноразовых блокнотов) известный в нашей стране как шифр гаммирования
Все остальные шифрсистемы могут быть взломаны, как минимум теоретически, ибо не доказано обратное.
Из вышесказанного совсем не следует, что все другие шифры, не подлежат применению. Все зависит от ценности шифруемой информации. Это единственный параметр, а все «бухгалтерские» соображения, в данном случае, значения не имеют.
Следовательно, необходимо ввести какую-то вероятностную оценку и т.д.
В общем случае, гарантированная оценка стойкости — это отношение Q/P. Где Q – трудоемкость метода, P – надежность метода, то есть вероятность правильного определения ключа. Криптоанализ системы проводится по всем известным методам ее вскрытия, а не только по методу тотального перебора. Минимальное отношение Q/P является гарантированной оценкой стойкости. При желании можно вводить различные коэффициенты учитывающие, например прогноз развития вычислительных мощностей или другие параметры.
В начале 60-х годов в СССР минимально допустимая гарантированная оценка стойкости составляла 10^25
Однако способность шифра противостоять математическим методам анализа (криптографическая стойкость) это только один фактор обеспечения безопасности шифрованной связи. Да, значительный, но один из.
Из этого следует, что в реальной жизни законы Керкгоффса вряд ли потеряют свою актуальность в обозримом промежутке времени.
В 1972 г. в США было 325 случаев утери ключевой документации, но ни один из них, по заключениям АНБ, не нанес кого-либо ущерба.
