Математика криптологии

В. Масол, д.ф-м.н, Издательский Дом "Комиздат"

Классическая криптология состоит из двух частей: криптографии - науки о засекречивании информации, и криптоанализа - науки о проникновении в засекреченные материалы. Если необходимость первой (криптографии) никогда не вызывала сомнений, то относительно второй составляющей время от времени возникали диспуты об этичности целей науки криптоанализа. Однако конкретные исторические события поставили точку в этих диспутах. Напомним об одном из них.

– Джентельмены не читают чужих писем,- заявил госсекретарь США Стимсон в 1929 г., узнав о том, что “черный кабинет” госдепартамента США занимался раскрытием шифрованных дипломатических телеграмм многих стран. Он немедленно упразднил упомянутый кабинет. Однако, являясь в 1940 г. военным министром, Стимсон заметно смягчился и простил раскрытие японских шифров (подробнее об этом и других исторических фактах см. В работе [1]).

Период до 1949 г. называют эпохой донаучной криптологии, поскольку достижения тех времен основаны в большей мере на интуиции и “вере”, не подкрепленных доказательствами. Последние впервые появились в публикации 1949 г. К. Шеннона [2]. Он доказал в ней, в частности, невозможность раскрытия случайного шифра Г. Вернама, введенного в работе [3], без знания секретного ключа.

В свою очередь, идеология криптографии с открытыми (несекретными) ключами впервые была изложена в 1976 г. У. Диффи и М. Хеллманом в работе [4]. В ней авторы показали, что секретная связь возможна без передачи секретного ключа между отправителем и получателем.

Благодаря ставшими уже классическими статьям [2 и 4], криптология состоялась как математическая наука.

К. Шеннон выделил в своей работе два общих принципа, используемых в практических шифрах: рассеивание и перемешивание. Достижение рассеивания и перемешивания осуществляется посредством реализации перестановок символов открытого текста, а также подстановок, заменяющих символы открытого текста на другие символы, из того же алфавита. Конкретный вид как перестановок, так и подстановок определяют секретные ключи. Один из примеров криптоалгоритма, разработанного в соответствии с указанными принципами К.Шеннона, является стандарт шифрования данных (DES), принятый в США в июле 1977 г. в качестве Федерального стандарта. В этом стандарте открытый текст Х, криптограмма Y и ключ Z -- двоичные последовательности длиной М = 64, N = 64 и K = 56 соответственно. Так как M = N, то DES является подстановкой в алфавите, содержащем 264 символов. Полное описание криптоалгоритма DES можно найти практически в любом учебнике по криптографии (например [5]), опубликованном после 1977 г.

С момента принятия Федерального стандарта DES и по сей день, он остается в центре внимания криптоаналитиков. Используемые при этом математические методы частично изложены в упоминавшейся ранее книге [5]. К ним А. Конхайм (автор книги [5]) относит методы теории вероятностей и математической статистики, линейной алгебры, теории групп и теории сложности. Более десяти лет стандарт DES оправдывал надежды его защитников. По состоянию на январь 1988 г. наиболее быстрый из известных вариантов криптоанализа этого стандарта предполагал выполнение 2K-1 процедур шифрования, т. е. практически предполагалось осуществление перебора всех вариантов. Первые сообщения о том, что теоретически возможно вскрыть стандарт DES за число операций, меньшее, чем 2K-1, появились в 1990 г., а соответствующие публикации в 1993 г. Так в работе [6] показано, что методом разностного криптоанализа перебор вариантов можно снизить до 247. Данный подход, как выяснилось со временем, был известен разработчикам стандарта DES. Однако противодействия этому методу, заложенные ими в криптосистему DES, при некоторых обстоятельствах, указанных авторами работы [6], удается обойти. Линейный криптографический анализ, предложенный в работе [7], основан на вероятностной оценке числа линейных соотношений между открытым текстом, шифртекстом и битами ключа, которые содержат информацию о ключе. Для успешной атаки на стандарт DES метод линейного криптоанализа требует 243 зашифрованных текстов (см. [7]).

Теоретические работы [6 и 7] послужили толчком к совершенствованию известных и созданию новых криптографических схем. Этот период в развитии криптографии нашел свое отображение в монографии [8], перевод которой на русский язык в настоящее время готовится в Издательском доме “Вильямс” (www.williamspublishing.com). В частности, в этой работе помещено детальное описание криптоалгоритма RC5, являющегося, по мнению специалистов, весьма удачным и таким, который после незначительных модификаций мог бы сменить стандарт DES.

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

В связи со сказанным более острым становится вопрос о том, что понимать под надежностью криптографического алгоритма. От чего в точности он защищает? Ответ на поставленный вопрос ищется, в частности, в рамках различных математических теорий. Принимая во внимание тот факт, что в большинстве случаев криптосистемы являются булевыми функциями, т. е. функциями, отображающими наборы из n битов в наборы из m битов, создатели указанных систем стремятся к тому, чтобы эти функции имели равномерно распределенный выход и тем самым “уничтожали” статистические закономерности открытого текста, обеспечивая, таким образом, криптосистеме надежность в теоретико-информационном смысле. В свою очередь, стандарт DES и возможные его приемники, к которым специалисты относят криптоалгоритмы RC6 (незначительная модификация упоминавшегося ранее RC5), MARS, Twofish, Serpent и Rijndael, считаются надежными в вычислительном смысле.

Различные толкования понятия надежности можно объяснить, обратившись к правилу для криптографов, сформулированному еще в XIX веке Керкхоффом (Kerckhoffs) в его книге “La Cryptographic militare”: криптоаналитику противника известен весь механизм шифрования, кроме значения секретного ключа. Для криптографа, придерживающегося этого правила, понятие надежности алгоритма становится, таким образом, динамически изменяющимся, зависящим от криптоаналитических возможностей противника в различные моменты времени.

Формирование понятия надежности, изобретение линейного криптоанализа в ответ на принятие стандарта DES -- все это может служить примерами проявления взаимосвязи двух составных частей криптологии. В свою очередь криптография с открытым ключом послужила толчком к раскрытию многих криптосистем. Чтобы объяснить это явление, обратимся снова к работе К. Шеннона [2]. В ней автор рекомендует конструировать такие шифры, чтобы раскрытие любого из них было эквивалентно решению задачи, о которой известно, что для ее решения требуется большой объем работы. Эта рекомендация помогла авторам работы [4] предложить криптографию, не использующую передачи секретного ключа. Их метод построен на применении односторонней функции и односторонней функции с потайным ходом. Определения и примеры этих функций, а также собственно алгоритм шифрования можно найти практически в каждом учебнике по криптографии, вышедшем после 1977 г., в частности [5, 8, 10, 11 и др. ]. Доказательство стойкости криптосистемы с открытым ключом могло бы состоять в обосновании того факта, что любой алгоритм раскрытия этой системы требует неприемлемо большого объема вычислений. Ни одна из систем с открытым ключом не удовлетворяет этому критерию стойкости. Хотя существуют такие криптосистемы, в отношении которых доказано, что их стойкость эквивалентна сложности решения задачи разложения целого числа n на простые множители. По мнению многих специалистов, указанная задача является крайне сложной для больших значений числа n. Вполне естественно, что поиски труднорешаемых математических задач могут привести к доказательству того, что задача, считавшаяся трудной и на этом основании использовавшаяся в криптоалгоритме, в действительности не является таковой и, следовательно, криптосистема, построенная на ней, вполне раскрываемая.

Ранее мы коснулись содержания учебников по криптографии, опубликованных после 1977 г. Для читателя, заинтересовавшегося данной тематикой, добавим к сказанному, что как учебники, так и справочные пособия по криптографии последних лет содержат, как правило, сведения о классическом шифровании с секретными ключами, о шифровании с открытыми ключами и о применениях криптографии. Различие между монографиями обусловлено различными научно-педагогическими интересами их авторов. Так, в работе [5] значительное место уделено математическим методам криптоанализа, в [11] - криптографии с открытыми ключами, в [8] - применениям криптографии (в частности, к безопасному общению в сети интернет), в [12] - программной реализации на языке Java алгоритмов криптографии с открытыми ключами и иллюстрациям их применения в задачах аутентификации информации, цифровой подписи и т. д.

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

Литература

1. D.Kahn. The Codebreakers, The Story of Secret Writing.-- New York: Screbner, 1996.

2. K.Э. Шеннон. Теория связи в секретных системах (В кн.: Шеннон К.Э. Работы по теории информации и кибернетике).- М.: ИЛ, 1963.- С. 333–402.

3. G.S.Vernam. Cipher printing telegraph systems for secret wire and radio telegraphic communications //J.Amer. Inst. Elec. Eng.-1926.- v. 55.- Р.109–115.

4. W.Diffie and M.E.Hellman. New directions in cryptography //IEEE Trans. Informat. Theory.- 1976.- Nov., v. IT-22.- P. 644–654.

5. A.G. Konheim. Cryptography: A Primer //John Willy & Sons.- New York, 1981.

6. E. Biham and A. Shamir. Differential Cryptanalysis of the Data Encryption Standart.- New York: Springer-Verlag, 1993.

7. M. Matsui. Linear Criptanalysis Method for DES Cipher. Proseedings, EUROCRYPT’93; published by Springer-Verlag.

8.** W. Stallings. Cryptography and Network security. Principles and Practice. Second Edition. Upper Saddle River, NJ: Prentice Hall, 1999.

9. P. Kocher. Timing attacks on implementations of Diffie-Hellman, RSA, DSS and other systems. - Lect. Notes Comput. Sci.- v. 1109.- Р. 104–113.

10. О.В. Вербіцький. Вступ до криптології.-Львів: Видавництво науково-технічної літератури, 1998.

11. A. Salomaa. Public - Key Cryptography.- New York: Springer-Verlag, 1996.

12.** J. Jaworski and P. Perrone. Java Security Handbook.- SAMS Publishing, 2000.

13. K. Nyberg. Differentially uniform mappings for cryptography. - Lect. Notes Comput. Sci.- v. 765.- Р. 55–64.

** Готовится перевод на русский язык в Издательском доме “Вильямс”. (www.williamspublishing.com)