- Современную криптографию уже невозможно представить без математики. Можно об этом рассказать чуть подробнее?
- Активное использование математических методов – это, на мой взгляд, одна из самых сильных сторон отечественной криптографической школы. Дело в том, что с помощью математических методов можно не только сконструировать сложные современные шифры, но и строго обосновать их криптографическую стойкость – способность противостоять практическому или теоретическому взлому – криптоанализу. И это наиболее важное применение математики в криптографии.
Если говорить просто, то задача криптоанализа – это восстановление информации о секретном ключе. Зная ключ, злоумышленник получает возможность проводить дешифрование перехватываемых им сообщений, изменять и подменять их, подписывать чужим именем и т.д. Так вот, современный криптоанализ – он ведь абсолютно математичен. Например, статистические методы анализа шифров, возникшие издавна из простого частотного анализа и заключающиеся в поиске закономерностей в шифртексте, не мыслимы сейчас без результатов математической статистики и разработанных в ней эффективных критериев различения статистических гипотез. Современные аналитические методы криптоанализа, такие как алгебраический криптоанализ, заключаются в описании работы шифра с помощью большой переопределенной системы булевых уравнений, от эффективности решения которой зависит успех криптоаналитика. Значит, нужно учиться решать такие системы уравнений, разрабатывать новые математические методы для этого. Или – криптоанализ систем «нового поколения», так называемых систем с открытым ключом. В таких системах (например, RSA, ElGamal, Shamir и др., активно применяющихся в криптографических протоколах сети Интернет) используются последние достижения теории чисел и алгебры. Взломать их – значит решить сложные математические задачи. Например, изобрести эффективный алгоритм разложения числа на множители, вычисления дискретного логарифма и т.д. То есть, опять – математика. Никак без нее. Правда, не совсем так. Без математики, в общем-то, можно пробовать – но это будут исследования наугад, эксперименты с входными данными и большими вычислительными мощностями (кстати, этот стиль криптографических исследований довольно популярен на Западе). Можно и на этом пути достичь некоторого – временного – успеха, но все значительные теоретические результаты в криптографии и криптоанализе имеют под собой серьезную математическую основу.
Соответственно математичными должны быть и средства, позволяющие противостоять криптоанализу. В этой области возникают такие задачи, как конструирование элементов шифра (например, дискретных функций), обладающих специальными свойствами.
- Криптографию и криптоанализ назвали наиболее важными формами разведки в современном мире. А они сводятся к холодным математическим вычислениям. Кто лучше вычисляет, тот и побеждает. Или есть еще что-то?
- Научные методы криптографии – это методы дискретной математики, алгебры, теории вероятностей, математической статистики. И в то же время криптография – это искусство. Объекты, которые она исследует, могут не подчиняться математическим законам, а научные методы иногда не дают результата. И тогда остается только воображение.
- А можно рассказать о том, какие научные работы в сфере криптографии и криптоанализа ведутся в Институте математики СО РАН?
- Можно было бы сказать, что мы исследуем так называемый шифр Цезаря… и некоторые его модификации. Однако, к счастью, о наших исследованиях можно рассказать и подробнее. В институте математики им. С.Л. Соболева мы, в основном, занимаемся исследованием криптографических свойств булевых функций, использующихся при конструировании шифров. Булева функция отображает n двоичных битов в множество из нуля и единицы. В каком-то смысле это наиболее простые функции. С помощью булевых функций – как составных элементов – строится практически каждый симметричный шифр.
Изучая математические свойства булевых функций, можно оценивать криптографическую стойкость шифров, в которых они используются. Известно много примеров того, как неудачный выбор булевых функций приводил к успешным атакам на шифр, например, на бывший государственный стандарт США блочный шифр DES (1993) и поточный шифр Grain, вошедший в число финалистов международного проекта eCRYPT (2011).
Если интересно, расскажу про DES подробнее. В 1993 году исследователями из Японии была обнаружена существенная слабость к линейному криптоанализу блочного шифра DES. Этот шифр был стандартом симметричного шифрования США на протяжении почти двадцати лет (с 1980 года по 1998 год). Слабость шифра, которая привела к успешной атаке на него, заключалась в отсутствии необходимых криптографических свойств его нелинейных компонент, заданных векторными булевыми функциями. По той же причине шифр оказался нестойким и к дифференциальному криптоанализу. В 1999 году шифр DES потерял статус государственного стандарта. Стойкость шифра к упомянутым методам криптоанализа может быть достигнута за счет использования максимально нелинейных булевых функций и их обобщений при построении S-блоков, что и было сделано в более современных шифрах, таких как шифры AES (современный стандарт США) и CAST (стандарт Канады).
К числу свойств, которые мы изучаем, относятся высокая нелинейность (упрощенно, – способность противостоять линейному криптоанализу), уравновешенность (частотный криптоанализ), большая алгебраическая степень функции, ее алгебраическая и корреляционная иммунность (алгебраический криптоанализ) и другие. Часто криптографические свойства противоречат друг другу, и при выборе булевой функции требуется находить компромисс между различными свойствами. Решение этих задач тесно связано со многими открытыми математическими вопросами дискретной математики, алгебры, теории графов и комбинаторики.
Одно из наших новых направлений – исследование методов защиты шифров от атак по сторонним каналам, от так называемого «нечестного» криптоанализа, который проводится не на основе математической модели шифра (как правило, модель шифра сама по себе не секретна), а на основе «прослушивания» реализации шифра.
Например, если шифр «зашит» в некотором устройстве, то «нечестным» методом его анализа считается тот, который использует данные о возникающем электромагнитном излучении при его работе, о времени вычислений, шуме и другие данные, полученные с установленных снаружи «жучков». Чтобы защитить шифр от подобных атак, необходимо маскировать его структуру. В том числе и булевы функции, описывающие его компоненты. При этом задача маскирования булевых функций хорошо формулируется математически – требуется строить разложения исходной булевой функции в сумму нескольких функций с определенными свойствами, выяснять, когда такие разложения существуют и т.п.
В работе принимают активное участие аспиранты ИМ СО РАН и студенты НГУ. В настоящее время мы проводим совместные научные исследования с лабораторией компьютерной безопасности и криптографии COSIC (Бельгия), широко известной по разработке нескольких мировых криптографических стандартов. Эта лаборатория является одной из наиболее успешных криптографических лабораторий мира. Ее сотрудниками были разработаны современный стандарт блочного шифрования США – шифр AES (2002), а также новая хэш-функция Keccak, ставшая победителем международного конкурса SHA-3 (2012). Стараемся перенимать их опыт.
Кроме научных задач мы занимаемся преподаванием на мехмате НГУ и в физико-математической школе (СУНЦ). Проводим такие курсы, как «Криптография и криптоанализ», «Криптография в задачах» и другие, издаем учебные пособия. В институте математики уже несколько лет проводим научный семинар по криптографии. Наши студенты и аспиранты занимаются подготовкой школьников СУНЦ к Всероссийской олимпиаде по математике и криптографии. Например, в прошлом 2012 году подготовленные ими ученики 11 класса СУНЦ заняли на этой олимпиаде 6 призовых мест по России (к слову, на Новосибирск пришлось всего восемь призовых мест)
- И в заключение, немного о перспективах дальнейшего развития математической криптографии?
- Криптография, конечно, будет активно развиваться. Одна из ее новых задач – разработка скоростных методов шифрования с высоким уровнем секретности. Эта задача обусловлена появлением новых каналов связи (беспроводные сети, сотовая связь, Интернет), по которым передаются всё большие объемы информации. И как бы ни росли со временем вычислительные возможности у криптографов, достигать оптимальной стойкости криптографических систем при ограниченной скорости шифрования можно будет, лишь применяя при их разработке серьезные математические результаты. Как-никак задача нахождения оптимума – это математическая задача. Так было и тысячу лет назад, так будет и в далеком будущем.
В заключение хотелось бы пожелать успешного развития отечественной криптографии. И научной, и практической. Хочется верить, что со временем во многих используемых нами устройствах (компьютерах, сотовых телефонах, охранных системах) наконец-то появятся криптографические протоколы и шифры, разработанные в России. Мы в данном случае говорим о гражданской криптографии, в ее закрытой части Россия, судя по всему, как всегда на мировом уровне. Осталось догнать в том, что можно определить и как гражданскую, и как коммерческую криптографию. Но для этого нужно много работать. Очень много.
Юрий Курьянов
- Войдите или зарегистрируйтесь, чтобы отправлять комментарии