Вот на таких фокусах и построена вся так называемая «новая криптография» — шифры с открытым ключом, электронная подпись и так далее. Может ли серьезный человек доверить свои серьезные секреты подобным средствам? Как показывает жизнь, очень даже может, и это приобретает, по-видимому, массовый характер. А что, если какой-нибудь вундеркинд от нечего делать выдумает способ быстрого разложения чисел на множители? А что, если он (или она) уже?.. Остается допустить, что у серьезных людей есть серьезные основания пренебречь подобными опасениями. Поэтому не мешает ознакомиться с принципами и достижениями современной криптологии — науки о тайнописи и способах ее прочтения. Ибо уже в ближайшее время, судя по всему, компьютеры будут общаться друг с другом исключительно при помощи непостижимых цифровых заклинаний….
Интервью
Длинное число, вынесенное в эпиграф, представляет собой фразу The magic words are squeamish ossifrage («Волшебные слова: брезгливая скопа»), зашифрованную Роналдом Л. Ривестом (Ronald L. Rivest), Ади Шамиром (Adi Shamir) и Леонардом Адлеманом (Leonard Adleman) по изобретенной ими системе RSA.
В статье этих авторов, вышедшей в 1978 году, премия в сто долларов была назначена тому, кто первым расшифрует это сообщение. Метод шифрования был известен, единственное, что требовалось — разложить на два сомножителя 129-значное число, приведенное в той же статье. Это было сделано только в 1994 году, через 17 лет после публикации статьи Ривеста, Шамира и Адлемана. Задача была решена с помощью весьма изощренного алгоритма и потребовала 220 дней работы 600 человек и 1600 компьютеров, связанных через Internet.
Вот на таких фокусах и построена вся так называемая «новая криптография» — шифры с открытым ключом, электронная подпись и так далее. Может ли серьезный человек доверить свои серьезные секреты подобным средствам? Как показывает жизнь, очень даже может, и это приобретает, по-видимому, массовый характер. А что, если какой-нибудь вундеркинд от нечего делать выдумает способ быстрого разложения чисел на множители? А что, если он (или она) уже?.. Остается допустить, что у серьезных людей есть серьезные основания пренебречь подобными опасениями. Поэтому не мешает ознакомиться с принципами и достижениями современной криптологии — науки о тайнописи и способах ее прочтения. Ибо уже в ближайшее время, судя по всему, компьютеры будут общаться друг с другом исключительно при помощи непостижимых цифровых заклинаний. Отсюда и первый вопрос, который я задал заместителю заведующего лабораторией МГУ по математическим проблемам криптографии, к.ф.-м.н. Валерию Ященко:
— Актуальна ли массовая популяризация теоретических основ криптографии?
Да, вне всякого сомнения. Криптография, которая раньше была засекречена, сейчас касается самых разных сторон жизни, в том числе и бытовых. Любой пользователь, даже школьник, не раз сталкивается со словами «шифр», «ключ», «криптограмма»… Например, он входит в Internet; в меню многих средств навигации Сети задается вопрос, нужен ли режим шифрования, и если ответить «нужен», начинается процедура выработки ключа. Чтобы правильно действовать, пользователь должен иметь представление об основах криптографии.
Второй пример, не менее яркий — это банковские карточки. Раньше карточки были только магнитными и держались на магнитной неподделываемости. Потом появились интеллектуальные карточки, в них вшит процессор, который выполняет криптографические функции.
Третий пример — цифровая подпись. Это у всех на слуху, все об этом говорят, но не все понимают, что это такое, и тем более не понимают математическую основу. Цифровая подпись — это некоторая криптографическая конструкция, но отличная от шифров, и от нее требуются другие качества: не просто защита открытого текста, но и неподделываемость, и защита от отказа от подписи. Именно это имеет исключительное значение во всех делах, связанных с использованием в бизнесе электронных документов.
— Давайте кратко коснемся терминологии, потому что часто встречаются некорректности, приводящие к неправильному пониманию сути дела…
Здесь ситуация сложная. Во-первых, терминология до конца не устоялась, во-вторых, есть отличия в терминологии зарубежной и русской, поскольку в России не произошло еще то, что произошло на Западе — выделения открытой криптографии в широкую область, где работает много ученых, проводятся конференции… Общепринято, что криптология — это наука, состоящая из двух частей — криптографии и криптоанализа. Криптография — это разработка шифров, криптоанализ — это вскрытие шифров. Они неразделимы, нельзя быть хорошим криптографом, не зная криптоанализа. Шифры нужно разрабатывать только стойкие, но стойкость нельзя гарантировать теоретически. Она доказывается лишь путем всевозможных атак на шифры. Поэтому криптология — наука единая.
— Есть разные варианты шифрования: с открытым ключом, с секретным ключом…
Раньше криптография практически сводилась к защите только от одной угрозы — угрозы вскрытия информации. За последние тридцать лет, в связи с изобретением новых средств, в том числе математических, появилась возможность методами криптографии защищаться от многих других угроз. И из-за появления этих новых средств возникло следующее разделение: асимметричная криптография и симметричная криптография (по другой версии, двухключевая и одноключевая). При использовании двухключевой криптографии вы посылаете абоненту сообщение, зашифрованное с помощью его открытого ключа, который общедоступен. Но расшифровать это сообщение можно лишь с помощью закрытого ключа, который известен только этому абоненту. Традиционная, одноключевая криптография, симметрична в том смысле, что ключ для шифрования идентичен ключу для дешифрования. Теперь ее часто называют криптографией с секретным ключом. При ее использовании возникает сложнейшая задача — внематематическая, внекриптографическая! — обеспечение сверхнадежного закрытого канала для обмена ключами.
— Именно это требование препятствует массовому применению систем такого типа?
Да. Точнее, страшно его затрудняет. С другой стороны, относительно криптографии с секретным ключом имеется теорема Шеннона (1948 год) о существовании абсолютно стойкого шифра — шифра, который невозможно вскрыть. Чтобы его использовать, длина ключа должна равняться длине самого сообщения. Это одноразовый шифр, в разных вариантах он называется шифром с одноразовым ключом или шифром наложения. Правда, здесь есть одна тонкость — когда мы говорим о стойкости шифра, то всегда надо явно указывать модель, в которой мы говорим о стойкости. В данном контексте обычно различают законных пользователей и противника. Понятие стойкости жестко привязано к модели нападения противника. Должно существовать описание двух моментов: чего противник хочет (прочитать, подделать, имитировать…) и что он может. Одно дело — хулиган с улицы, другое дело — спецслужбы. Например, абсолютная стойкость шифра Шеннона относится только к невозможности вскрытия. А по отношению к имитации и искажению он, наоборот, нестойкий. То есть противник может врезаться в наш с вами канал связи, перехватывать сообщения и вместо них посылать свои. Наиболее болезненно это не в деловой сфере (хотя и в деловой тоже), — а в военной (имитация запусков ракет, изменение их траектории…). Тем самым абсолютно стойкий одноразовый шифр не защищен от искажения информации. И вообще, идеально устойчивый ко всем атакам шифр невозможно себе представить. Лучше даже говорить не «шифр» — когда мы говорим «шифр», речь идет только о защите от вскрытия. Лучше использовать более общее понятие «криптографическая система«.
— В связи с этим, каково место криптографии в системе защиты информации? Может быть, существует статистика: какой процент случаев несанкционированного доступа связан со слабостью криптографической защиты?
Такой статистики нет, и быть не может. Истинная причина взлома систем защиты информации, например, в крупных банках, обычно скрывается. Есть различные экспертные оценки, но я не думаю, что им можно верить. Разброс большой. Можно сказать одно — когда мы защищаем информацию, мы обязаны добиться выполнения «принципа равнопрочности». Противник не будет нападать только на криптографию. Он будет нападать всеми способами — физически, подкупом, прослушиванием… С другой стороны, хотя криптография и очень сложная наука, стоимость криптографической защиты все-таки намного меньше, чем стоимость других элементов защиты. И если есть хороший шифр и проверено, что в данном окружении он надежен, то — использовать его, и голова не болит. А если не шифровать, то потребуются огромные затраты на обеспечение надежности.
— Но между надежностью криптографического протокола и реальной надежностью секретного обмена информацией есть большая разница. Если даже отвлечься от того, что хакер может перехватить ваше сообщение еще до шифрования — очень многое зависит от программной реализации криптосистемы, от других факторов…
В сфере компьютерной безопасности тоже применяются средства криптографии — шифрование паролей, и т.п. Но четкое выполнение всех правил безопасности при работе на компьютере требует сил, времени, аккуратности. Обычно пользователи этим пренебрегают; в лучшем случае ставят простейший пароль. А шифрование сообщений не требует от пользователя дополнительных усилий. Кстати, одно из требований при разработке криптографических средств: у пользователя не должно возникать желания их отключить. Наиболее ярко сложность реализации этого требования проявилась в последние годы при разработке хороших цифровых подписей для банковских приложений. Использование качественных систем подписи может заметно замедлять обработку документов. Это отдельная головная боль для криптографии.
Что касается реализации криптосистемы — здесь тоже должен соблюдаться принцип равнопрочности. Пусть есть теоретическая модель криптографической системы — стойкой в каких-то предположениях. Когда мы начинаем ее реализовывать, то первое, что нужно обеспечить — абсолютное соответствие алгоритма теоретической модели. Это обычно большая проблема — установить, что алгоритм делает именно то, что нужно и не делает ничего лишнего. Надо помнить, что, как правило, у разработчика есть богатые возможности сделать так, чтобы алгоритм делал что-то лишнее, а вы об этом не будете знать… При этом надо, чтобы и на чисто программистском уровне ничего никуда не втекало и не вытекало (через какие-нибудь файлы подкачки, скажем). Следующий этап — обеспечение правильности и надежности функционирования ключевой системы. Речь идет об обмене ключами и распределении ключей. Используется ли один секретный ключ, или два ключа — закрытый и открытый — в любом случае возникает проблема распределения ключей. То есть, кроме алгоритма самой криптографической системы, должен еще существовать алгоритм обмена ключами.
— Я специально перед разговором с Вами перечитывал статью Филипа Зиммерманна («Компьютерра» # 225, 1 декабря 1997 г.), и он там говорит об очень серьезной проблеме — если открытый ключ принадлежит не тому, кому вы думаете, то абонент, приславший вам этот ключ, спокойно будет читать ваши послания.
Да. Несомненно.
— Спрашивается, как же тогда проверить, настоящий ключ или поддельный? Оказывается, что все это сводится опять к какой-то «ненаучной» ситуации: «центры доверия», сертификация и т.д.
И это несомненно. Но здесь я могу высказать некое общее суждение (и сам Зиммерманн об этом же говорит, и говорит абсолютно правильно). А именно, за последние двадцать лет отношения между традиционной и асимметричной криптографией развивались очень драматично. Когда появилась асимметричная криптография, возникла эйфория — теперь мы можем решить массу новых задач.
Это продолжалось лет пять, пока строили теоретические модели. Все было прекрасно. Правда, несколько лет ушло на чисто бюрократическую борьбу с правительством — за то, чтобы криптографию развивать в открытую. Когда этого добились, начались конференции, появилась Криптографическая Ассоциация (Международная ассоциация криптологических исследований, www.iacr.org). Но когда стали реализовывать эти идеи уже в конкретных системах, сразу уткнулись в не менее сложную проблему, чем в симметричной криптографии. Там существовала внекриптографическая проблема — нахождение сверхнадежного канала для обмена ключами. А здесь исходная идея прекрасная — нам не нужен скрытый обмен ключами, мы используем одностороннюю функцию (ОФ)…
— Что это такое?
Грубо говоря, это очень вычислительно трудная математическая задача. Например, вычислить произведение двух длинных чисел — легко. Но чтобы найти сами эти числа по их произведению, нужны колоссальные вычисления. Объем этих вычислений экспоненциально растет с длиной самих чисел. В асимметричных системах гарантией надежности шифра служит именно вычислительная сложность таких задач.
Так вот, вроде бы, все складывалось отлично. Но когда стали на практике это делать, сразу обнаружились дыры при реализации обмена открытыми ключами. Стали эти дыры латать, находить новые, и так далее. Теперь выясняется, что в очень больших системах стоимость всей этой работы начинает приближаться к стоимости традиционных решений. И на сегодняшний день, спустя двадцать лет после начала развития асимметричной криптографии, перспективы развития этих двух направлений оцениваются как фифти-фифти. Ведь такие проблемы, как цифровая подпись, например, можно решить и с помощью симметричной криптографии. Зато над этими решениями не висит дамоклов меч: проклятие всей асимметричной криптографии в том, что она может рухнуть из-за какого-то неожиданного прорыва в математике.
— А почему, собственно, он не висит над симметричной криптографией? Там ведь тоже некая математика, которую, в принципе, можно победить…
А там другие средства, другое гарантирование стойкости, не связанное с ОФ.
— Если речь идет об алгоритмах на основе теоремы Шеннона, это понятно. Но ведь наверно имеется в виду использование и других шифров?
Да, есть много различных шифров. Некоторые такие шифры доведены даже до стандарта — американская система DES, например. Есть и соответствующий российский стандарт СКЗД. Это опубликовано. Там совершенно другие принципы. Конечно, эти принципы тоже математические. Но стойкость этих шифров подтверждается тем обстоятельством, что их пытались вскрыть всеми известными способами — и не вскрыли. А шифры с открытым ключом держатся на вере в такие вещи, как трудность разложения числа на множители.
ЧТО ТАКОЕ «ДОКАЗАТЕЛЬСТВА С НУЛЕВЫМ РАЗГЛАШЕНИЕМ»
Иногда в процессе установления или осуществления коммуникации (предоставления доступа к информации, заключения и совершения сделки и т.п.) желательно идентифицировать одного, двух или более участников коммуникации остальными участниками.
Способы идентификации, применяемые в обыденной и профессиональной практике, можно разделить на три большие группы:
- идентификация человека по предположительно уникальным физическим (биологическим) признаком: узнавание в лицо, узнавание голоса, проверка почерка или автографической подписи и т.п., а также более сложные биометрические технологии (анализ отпечатков пальцев, рисунка радужной оболочки глаза или ДНК);
- идентификация человека по факту предъявления определенной вещи (билета, удостоверения личности, магнитной карточки и т.п.);
- идентификация человека (или негуманоидного субъекта коммуникации — компьютера, узла сети либо другого аппаратно-программного агента) по факту известности ему определенной информации.
Именно способы, относящиеся к последней группе, имеют отношение к криптографии, и именно они являются наиболее широко используемыми и перспективными в распределенных компьютерных коммуникативных и коммерческих средах.
Простейшие примеры идентификации по известности информации — ввод пользователем пароля для регистрации на компьютере, ввод владельцем карточки своего PIN для доступа к функциям банкомата, и вообще системы типа «пароль» или «пароль-отзыв».
При всей своей простоте, решения типа «пароль» или «пароль-отзыв» не являются надежными в криптографическом смысле. Во-первых, они предполагают, что необходимая для идентификации информация (персональный «секрет») известна по крайней мере двум участникам системы — идентифицирующему себя субъекту и проверяющей подсистеме. А «знают двое — знает свинья», как говаривал папа Мюллер. Именно поэтому ни с юридической точки зрения, ни с позиций здравого смысла ввод пароля не может рассматриваться как эквивалент собственноручной подписи.
Во-вторых, такие системы подвержены очень простой атаке (она несомненно известна читателю по фильмам военной тематики): атакующий встает на пути к «защищенному» объекту чуть раньше часового и спрашивает у подходящего «легитимного пользователя» пароль, а вместо отзыва убивает его. Затем он идет к часовому и сообщает ему (в ответ на запрос) только что узнанный пароль; в ответ он получает отзыв. Теперь он обладает всей необходимой информацией, чтобы изображать любого участника системы.— Но их тоже пытались вскрыть…
Да, пытались, но — меньше пытались, скажем так. По времени меньше. Точнее, не по времени, а по наработанному количеству атак. За асимметричными шифрами нет истории их вскрытия. В известном смысле, даже наоборот — есть масса алгоритмов такого типа, опубликованных за последние 10-15 лет, которые взламывались через два месяца после публикации. С симметричными такого не происходит — еще и по той причине, между прочим, что из них опубликованы только стандарты. Есть большая асимметрия между этими двумя классами шифров…
— А сама по себе открытость асимметричной криптографии дает какие-нибудь преимущества в смысле стойкости криптосистем? Например, тот факт, что исходный текст программы шифрования общедоступен в Internet, является дополнительным аргументом в пользу надежности этой программы?
Здесь есть одно тонкое место. Но сначала я скажу свое мнение об одной вещи, связанной с Internet. В Internet масса сайтов, где встречается слово «crypto». Я на некоторые из них заглядывал, и у меня осталось впечатление, что это огромная мусорная свалка. И чтобы отсеять весь этот мусор от чего-то добротного, нужно иметь соответствующую квалификацию. Там масса неправильного, вредного, масса обманов… Так что, если говорить о публикации текстов, то нужно уметь четко отделить рекламный момент от содержательного. Это очень трудно. Ведь нет же никаких стандартов, нет способов проверки качества! Вот тебе дают продукт. Как ты можешь пытаться его взломать? Либо надо самому иметь высочайшую квалификацию, либо приходится довериться некоему коллективу специалистов. Потому что единственной гарантией стойкости шифра является то, что много квалифицированных криптоаналитиков пытались его вскрыть, но не смогли.
— Но если программа коммерческая, значит, есть конкуренты, а они заинтересованы в том, чтобы найти и обнародовать слабые места. И если таких публикаций нет…
…это ничего не значит! Это не значит, что шифр никто не вскрыл. Вполне возможно, что вскрыли и молчат. Впрочем, анализ стратегии конкурентов в такой ситуации не имеет отношения ни к криптографии, ни к математике, и я на эту тему высказываться не хочу.
— В книге «Криптография в банковском деле», одним из авторов которой Вы являетесь, выделены три основные задачи криптографии: обеспечение конфиденциальности информации, целостности информации…
…и неотслеживаемость.
— Да. И о последних двух задачах обычно говорят меньше, чем о конфиденциальности. В какой степени эти две задачи сегодня решены?
Начнем с последней задачи. На русском языке о ней написано мало, особенно в теоретическом плане. Кроме этой книги имеется ряд статей, но преимущественно прикладного характера. Более того, в России даже сама концепция неотслеживаемости осознана — на фундаментальном уровне — очень немногими. И вообще в мире это направление развито совершенно недостаточно.
— В книге «Криптография в банковском деле» об этой задаче сказано:
«…Она была поставлена в работах Шаума (Chaum) в начале 80-х годов. В то время эта концепция осталась практически незамеченной. Хотя, быть может, ситуация на самом деле обратная: идея была замечена и понята слишком хорошо, и определенные силы, по причинам, которые станут понятны ниже, сделали все, чтобы не дать ей дальнейшего развития». Что именно имеется в виду?
Если мы используем электронные платежи, то разработчик системы электронных платежей, будь это государство или банк, не должен иметь возможности отследить, кто кому какие деньги пересылает. То есть электронные платежи не должны быть дополнительным способом контроля за движением денег данного клиента.
— В частности, при такой системе государству будет довольно сложно собирать налоги…
Это другой вопрос. Я не хочу смешивать две вещи. Налоги — сами по себе, а задача неотслеживаемости — сама по себе. Задача неотслеживаемости ставится заказчиком системы. Разработчики системы не вправе думать и о клиенте, и о налогах… Если встать на такую позицию, то мы скатимся к шедшей много лет дискуссии на Западе, когда правительство США хотело заставить криптографическое сообщество признать систему «Клиппер» — это, грубо говоря, криптосистема с встроенным в нее ключом, который лежит у прокурора. Вообще, криптосистема — это такой инструмент, что часто возникает желание использовать его не только для решения задач клиента, заказчика, но и для попутного решения каких-нибудь фискальных задач, еще для чего-нибудь… Я считаю, что чистая наука не должна этим заниматься.
— По-моему, вряд ли какое-нибудь государство пойдет на создание такой системы, где нет физической возможности отслеживать, кто кому что заплатил…
Это дело государства. Может быть, правовая система будет ставить клиента в такие условия, что он сам, добровольно, будет отдавать государству то, что положено, сохраняя при этом полную конфиденциальность своих финансовых дел… В любом случае, к криптологии это не имеет отношения!
— Итак, вы рассматриваете задачу неотслеживаемости как абстрактно-теоретическую. В такой постановке она решена?
Пока нет! Это все в стадии обсуждения и обдумывания теоретиками. Но я бы не хотел дальше в это углубляться — это большой отдельный разговор. Надо только отметить, что эта задача имеет самое прямое отношение к созданию электронных денег.
Бескровный вариант этой схемы известен всем администраторам компьютерных систем, он обычно называется «ловушкой для паролей»: на рабочем месте атакующим запускается программа, имитирующая работу подсистемы контроля операционной системы или сети. Не подозревающий об этом легитимный пользователь вводит свое имя и пароль, в результате чего они становятся известны атакующему…
Следовательно, задача состоит в том, чтобы один из участников мог убедить другого в том, что обладает некоторым идентифицирующим его «персональным секретом», не раскрывая его. Возможно ли такое?
В 1989 году на конференции Crypto ’89 французские криптографы Жан-Жак Кискатер (Jean-Jacques Quisquater) и Луи Гийу (Louis Guillou) выступили с докладом «Как объяснять доказательства с нулевым разглашением детям» (в качестве содокладчиков, разумеется, фигурировали многочисленные их дети). В нем они предложили яркую и запоминающуюся метафору, известную как «пещера Алладина».
Предположим, Алиса утверждает, что знает волшебное слово, открывающее дверь C-D в пещере Алладина (см. рисунок), и хочет доказать это Бобу, который не склонен ей верить. В то же время, Алиса не хочет, чтобы Боб завладел секретом пещеры, узнав это слово.
Как Алиса может убедить Боба, что она знает секрет, не разглашая его? Для этого Алиса и Боб должны выполнить шаги в соответствии со следующим протоколом:
- Боб остается в точке А.
- Алиса проходит в пещеру и сворачивает в точке B направо или налево (поскольку Боб ее не видит, он не знает, в какую именно сторону она свернула.
- Боб проходит в точку B.
- Боб кричит в пещеру, прося Алису вернуться со стороны A или со стороны B, выбрав вариант случайным образом.
- Алиса выполняет его просьбу (используя волшебное слово, если ей случилось оказаться по другую сторону от двери).
Шаги 1-5 могут быть выполнены n раз, при этом, если Боб выбирает вариант своей просьбы действительно случайным образом (т.е. Алиса не может его предугадать), он может быть уверен в том, что Алиса и вправду знает волшебное слово (с вероятностью случайного совпадения 2-n).
Разумеется, это лишь простейший пример «доказательства с нулевым разглашением», но он позволяет понять общую логику рассуждения.
— М.О.— В таком случае, прежде чем перейти к следующему вопросу, я хочу привести еще одну цитату из уже упоминавшейся книги.
«Необходимость обезопасить автоматизированные банковские системы от посягательств уголовных элементов хорошо осознана разработчиками. Однако они пытаются обеспечить безопасность путем шифрования данных, не отдавая себе отчета в том, что здесь речь идет о неотслеживаемости, а вовсе не о конфиденциальности.
… Становится очевидной несостоятельность следующего тезиса противников неотслеживаемости: она (неотслеживаемость) не нужна, поскольку если клиент не доверяет банку, то он никогда не положит в этот банк свои деньги. На самом деле клиент не доверяет персоналу, работающему в банке и третьим лицам, которые могут перехватить информацию в каналах связи. С другой стороны, всякий банк, который заботится о неотслеживаемости платежей, повышает доверие клиентов к себе».
— Итак, вторая задача — обеспечение целостности. В теоретическом плане она решена?
Эта задача состоит в том, чтобы гарантировать поступление информации из достоверного источника и в неискаженном виде. В банковских расчетах, например, это даже важнее, чем обеспечение конфиденциальности. Для решения этой задачи сперва использовались шифраторы, но вскоре (не позднее, чем в начале 80-х годов) стало понятно, что нужны совсем другие средства. И тогда возникла новая ветвь криптографии — криптографические протоколы. Протокол — это распределенный алгоритм решения несколькими участниками некоторой криптографической задачи. Причем среди этих участников могут быть и противники. Протоколы предназначены прежде всего для защиты от нечестных действий партнеров.
Многие протоколы теоретически обоснованы. Но ни в коем случае нельзя думать, что этот вопрос закрыт, так как жизнь постоянно ставит все новые задачи, которые надо решать. Сейчас, пожалуй, это основная область исследований в теоретической криптологии. Число протоколов растет с каждым годом. Лучше говорить о криптографических примитивах, это такие элементарные кирпичики, из которых строится протокол. Так вот, даже таких примитивов сейчас насчитывается около двадцати пяти. Например, «подбрасывание монеты по телефону», «блоб» (передача бита «на хранение», bit commitment) — корректность этих примитивов теоретически обоснована.
— Правильно я понимаю, что это обоснование заключается в сведении такой задачи к предположению об односторонности какой-нибудь функции? Например, к гипотезе, что длинные числа невозможно быстро разложить на множители?
Не только и даже не столько односторонние функции здесь играют роль. Теория таких задач зиждется на фундаменте, который за последние 10-15 лет выделился из теории сложности вычислений. Это так называемые интерактивные системы доказательств (interactive proof systems) или системы доказательства с нулевым разглашением (zero-knowledge). Вот на этой чисто математической теории основаны протоколы. Практически все новые приложения криптографии — подписи, карточки и т.д., обосновываются с помощью доказательств с нулевым разглашением.
— Но в схеме PGP, например, подпись связана с односторонней функцией…
Дело в том, что цифровая подпись возникла одновременно с открытым ключом, где-то в семидесятые годы. Это была первая модель протокола, и она действительно использует ОФ. Но надо четко понимать: ОФ — объект гипотетический. Стойкая цифровая подпись тоже объект гипотетический. Есть ряд теорем, которые доказывают существование одного из этих объектов при условии существования другого. Но самым главным математическим содержанием всей новой криптографии, особенно в последние годы, стало все то, что связано с теорией сложности вычислений. И именно от прорывов в этой области математики зависит дальнейшее развитие криптографии.
— Не могли бы Вы здесь еще один момент прокомментировать: в связи с криптографией иногда говорят, что есть некие секретные математические теоремы, с помощью которых все существующие шифры на самом деле вскрываются…
Ясно, что та часть криптографии, которая связана с защитой государственных секретов, военных секретов, должна быть закрытой. И вся математика, и все остальное, что с этим связано, тоже остается закрытым. Но, с другой стороны, конечно же, наука едина. И фундаментальные достижения невозможно скрывать долго.
— А сейчас каковы наиболее актуальные научные направления в криптологии? Какие задачи считаются важнейшими? Вот, например, если известный вам Сергей Степанов (математик, недавно анонсировавший открытие «быстрого» алгоритма разложения на множители — Л.Л-М.) напечатает статью с описанием своего алгоритма — что будет? Вся открытая криптография рухнет?
Произойдет крупный обвал. Правда, не сразу, ибо здесь все не так однозначно. У теоретиков-числовиков сейчас действительно идет борьба за построение так называемого полиномиального алгоритма факторизации (а также полиномиального алгоритма дискретного логарифмирования). Но если и будет построен такой алгоритм (на что претендует Степанов), он может оказаться быстрым лишь в некотором абстрактном математическом смысле, и для реальных систем это ничего на практике не изменит.
— Ну, а если алгоритм окажется реалистичным, то открытую криптографию все-таки придется закрывать?
Тоже не обязательно. Математика неисчерпаема, число «математических молекул» велико… Даже в последние три-четыре года были всякие сюрпризы — я имею в виду, в частности, квантовую криптографию. Вообще, криптография развивается очень интересно, поскольку она живет на стыке фундаментальной математики, физики и прикладной технологии. И как математик, я вам скажу о математическом аппарате — это нечто вторичное, он определяется тем, что в данный момент удобно и легко реализовывать. За много веков использовали разное — сначала бумажки, потом всякие там колеса, потом возникла элементная база компьютеров — и каждый раз создавался адекватный математический аппарат. Это приводило к развитию различных направлений в математике. Если раньше, до войны, основными в этой области были комбинаторика, вероятность, то после появления микроэлектроники стала актуальной теория автоматов, а теперь самое важное направление — теория сложности вычислений. А также теория чисел, поскольку кандидаты в ОФ, которые пока не рухнули, это ровно две теоретико-числовые задачи — разложение на множители и дискретный логарифм. Точнее, есть два понятия, которые часто путают — ОФ и ОФ с секретом. То, что реально применяется, это односторонние функции с секретом. То есть их нельзя обратить, если не знаешь встроенный секрет, «ловушку». За последние лет 15-20 было перебрано много кандидатов на эти функции, а выжили только эти две. И из всех математических задач, которые были просмотрены на этот предмет (их несколько тысяч!) только в одной — в задаче разложения на множители — органически заложена возможность для встраивания секрета. Было много попыток искусственно встраивать секрет в другие задачи — но это искусственное встраивание привело к тому, что все быстро разваливалось.
— Какие же разделы математики или физики в более отдаленной перспективе могут быть использованы в криптографии?
В течение последних 3-4 лет очень много стали говорить о двух таких разделах — это квантовая криптография и динамический хаос. Вообще, надо сказать, что в науке уже давно, много веков назад так сложилось, что если появляется какое-то новое направление, то сразу ищут возможные применения его в криптографии. Криптография очень удобный объект для приложений.
— Теперь расскажите, пожалуйста, подробнее о деятельности вашей лаборатории.
Наша лаборатория существует уже семь лет. Среди нас есть и профессиональные криптографы, и математики, пришедшие к этой тематике из теории чисел, алгебры, математической логики. Мы занимаемся фундаментальными исследованиями в области математических проблем криптографии. Это не только алгоритмы, а вообще изучение различных математических объектов, связанных с криптографией. Занимаемся теорией сложности вычислений, алгеброй, дискретной математикой, теорией кодирования. Нас интересует, как некоторые объекты из этих областей математики можно применить в криптографии. Например, заведующий лабораторией, Владимир Сидельников — известный в мире теоретик-кодовик, он занимается теорией кодирования, читает по ней спецкурс на мех-мате МГУ. Его интересуют задачи на стыке теории кодирования и криптографии. Один яркий пример : его работа 1992 года — V.M.Sidelnikov, S.O.Shestakov, On insecurity of cryptosystems based on generalized Reed-Solomon codes // Discrete Mathematics and Applications, 1992 — (она имела большой резонанс) о нестойкости системы шифрования Нидеррайтера, основанной на теоретико-кодовой конструкции.
Помимо научной работы, мы готовим обзоры по криптографии и связанным с ней областям. Для Центробанка мы сделали обзор и выпустили вот эту книгу (Анохин М.И., Варновский Н.П., Сидельников В.М., Ященко В.В., «Криптография в банковском деле» — М.: МИФИ, 1997). В МИФИ, на курсах для банковских работников и на нескольких факультетах, она используется как учебник. Надо сказать, что это единственная книга на русском языке, где подробно и строго изложены основные концепции современной криптографии, включая математический аппарат, с особым упором на проблемы защиты финансовой информации. В МИФИ ведется подготовка специалистов по защите информации, в основном для Центробанка…
— …так что можно считать, что заказчиком этой книги был Центробанк?
Да.
— А если к вам кто-нибудь обратится с просьбой дать оценку установленной у него криптографической системе?
Принципиальная позиция лаборатории состоит в том, чтобы консультировать только по теоретическим вопросам. Иногда, впрочем, мы занимаемся экспертной оценкой надежности системы защиты информации «в целом» — но не конкретного шифра. Например, разрабатывается какая-нибудь корпоративная сеть. Нас спрашивают: мы хотим делать то-то и то-то, какие возможны дыры, где и что следует защищать? Такую экспертизу мы можем провести, но сюда не входит создание или оценка конкретной системы. Я, кстати, хочу еще раз подчеркнуть, что «отдельно взятая» криптография бессильна, и лучше говорить о более широких понятиях, таких как защита информации и даже информационная безопасность.
— Где же готовят специалистов по таким вопросам?
В области образования ситуация следующая. Имеется две официально утвержденные специальности: 013200 (криптография) и 220600 (организация и технология защиты информации). Для того, чтобы вести обучение по каждой из них, нужна лицензия Минвуза, которая выдается после аттестации учебно-методическим объединением (УМО) по информационной безопасности. Лицензию на подготовку специалистов по криптографии имеет только ИКСИ (Институт криптографии, связи и информатики Академии ФСБ, http://www.fssr.ru). По защите информации наиболее продвинутые учебные заведения, которые уже несколько лет готовят студентов, это МИФИ (факультет информационной безопасности), РГГУ (факультет защиты информации). За последние два года к ним подключились МИЭМ и МИРЭА, но там пока стадия становления. Еще несколько вузов России получили лицензии, однако полной картины я не знаю. Знаю, что таких вузов мало. На www-странице ИКСИ есть много информации на эту тему: информация об УМО, о ряде вузов и даже об олимпиадах для школьников по криптографии, которые проводятся с 1991 года.
— А в МГУ что-нибудь делается в этом направлении?
Да, в Московском университете сейчас организуется новое подразделение под названием «Учебно-научный центр по проблемам информационной безопасности». В его составе будут Высшие курсы переподготовки и повышения квалификации по информационной безопасности. Но они предназначены не для студентов. Предполагается, что после юридического оформления и получения лицензии Высшие курсы будут заниматься переподготовкой дипломированных специалистов, т.е. давать второе высшее образование — в области информационной безопасности. На Западе такие учебные заведения называют «магистерскими школами». В первую очередь они предназначены для людей, работавших в близких областях, в частности, для военнослужащих, сокращаемых из армии — офицеров войск связи, например.
— А как же студенты МГУ?
Факультет защиты информации в МГУ открывать не предполагается. Но по вопросам, связанным с этой тематикой, читаются спецкурсы на мехмате по четырем кафедрам: дискретной математики, теории чисел, математической логики, математической теории интеллектуальных систем. Студенты пишут курсовые, дипломы, в том числе и под руководством сотрудников нашей лаборатории. Есть на мехмате «Научно-исследовательский семинар по дискретной математике и математическим проблемам криптографии», которым руководят акад. Олег Лупанов, проф. Владимир Сидельников и проф. Юрий Нестеренко.
— Каковы перспективы карьеры для студентов, которые выберут такую специальность?
Руководство многих факультетов и вузов активно добивается получения лицензии на преподавание информационной безопасности. По двум причинам: это повышает приток абитуриентов, и на такие специальности есть спрос со стороны большого количества фирм. Мы об этом уже говорили в начале — появилось много новых применений криптографии, и специалисты остро необходимы.
Насколько я знаю, и у студентов интерес очень большой. К нам в лабораторию за последний год приезжало несколько руководителей разного уровня из различных вузов России. Вчера, например, заходил завкафедрой из Томского университета, был у нас и ректор Красноярского университета. Все говорят в один голос: молодежь требует, чтобы читались такие дисциплины!
Другая сторона этой медали — очень много на эти темы пишут, но пишут, как правило, совершенно неквалифицированные люди. Специалисты же пишут об этом мало, да и вообще специалистов очень мало.
— И напоследок, если можно, пару слов об Академии криптографии.
Академия существует уже шесть лет, она является головной научной организацией России по криптографии. В составе ее учредителей было пять академиков РАН, в том числе Сергей Яблонский, Владимир Козлов и другие широко известные ученые. Академия криптографии издает свои «Труды по дискретной математике». Более подробно о деятельности Академии криптографии было рассказано недавно в интервью ее президента Николая Андреева газете «Известия».
Беседовал Леонид Левкович-Маслюк
levkovl@spp.Keldysh.ru
Библиография
- Для знакомства с основными понятиями криптографии вполне подходит книга С.А.Дориченко, В.В.Ященко «25 этюдов о шифрах». При достаточной строгости изложения математический аппарат там довольно простой, и книга доступна даже хорошо подготовленному школьнику.
- Современное состояние математического аппарата криптографии освещено в серии статей под рубрикой «Математика и криптография» в сборнике «Математическое просвещение», Третья серия, вып. 2, 1998.
- В книге Анохин М.И., Варновский Н.П., Сидельников В.М., Ященко В.В., «Криптография в банковском деле» — М.: МИФИ, 1997, подробно разобраны многие вопросы криптографии, как прикладные, так и чисто математические, с общей ориентацией на финансовые приложения. Там же имеется обширная библиография.
Всевозможные легенды и удивительные истории, связанные с шифрами можно прочитать в книгах:
Т.А.Соболева, «Тайнопись в истории России» — М., 1994. David Kahn, Codebreakers. The Story of Secret Writing. N.Y.,Macmillan, 1967.
Вот несколько статей по математическим вопросам криптографии, написанных в последние годы сотрудниками лаборатории.
- О.А.Логачев, Г.В.Проскурин, В.В.Ященко, «Локальное обращение конечного автомата с помощью автоматов» // «Дискретная математика», том 7, выпуск 2, 1995.
- Ю.В.Кузнецов, С.А.Шкарин, «Коды Рида-Маллера (обзор публикаций)», 1996.
- В.В.Ященко, «О критерии распространения для булевых функций и о бент-функциях» // «Проблемы передачи информации», том 33, вып.1, 1997.
- В.М.Сидельников, «Системы распределения ключей на основе «экспоненциального представления» линейной группы GLn(Fp)» // «Проблемы передачи информации», том 30, вып.4, 1994.
- В.М.Сидельников, «Открытое шифрование на основе двоичных кодов Рида-Маллера» // «Дискретная математика», том 6, выпуск 2, 1994.
- В.А.Артамонов, В.В.Ященко, «Многоосновные алгебры в системах открытого шифрования» // «Успехи математических наук», 1994.
- V.M.Sidel’nikov, M.A.Cherepnev, V.V.Yashchenko, Systems of open distribution of keys on the basis of noncommutative semigroups // Russian Acad. Sci. Dokl. Math., vol. 48 (1994), No. 2.
- М.А.Черепнев, «О связи сложностей задач дискретного логарифмирования и Диффи-Хеллмана» // «Дискретная математика», том 8, выпуск 3, 1996.
- О.А.Логачев, А.А.Сальников, В.В.Ященко, «Бент-функции на конечной группе» // «Дискретная математика», том 9, выпуск 4, 1997.
Автор: ВАЛЕРИЙ ЯЩЕНКО
Опубликовано в журнале «Компьютерра» №20 от 25 мая 1998 года