Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Конференция «Технологии управления данными 2018»
СУБД, платформы, инструменты, реальные проекты.
29 ноября 2018 г.
2004 г.

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

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

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

– Джентельмены не читают чужих писем,- заявил госсекретарь США Стимсон в 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)

Новости мира IT:

Архив новостей

Последние комментарии:

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 985 1945361
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2015 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...