Николай Варновский: "Протоколы = распределенные алгоритмы + соглашения о форматах"

Тема сегодняшней беседы - криптографические протоколы, математический аппарат, на котором основано, в частности, использование электронных денег.

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

А обеспечить, допустим, целостность - это значит...

- "Целостность" - тоже сложное понятие. Невозможно формально определить, что такое целостность. Простейший вариант - один абонент посылает другому сообщение, и нужно, чтобы это сообщение никто не исказил и не подменил. Это можно обеспечить традиционными методами "старой" криптографии. У обоих абонентов есть один и тот же секретный ключ, и они вычисляют так называемый тег - "сворачивают" сообщение (как при вычислении контрольной суммы, но с использованием секретного ключа) и результат добавляют к тому, что пересылается. Получатель проверяет тег, а поскольку ключ, как они считают, есть только у них, то вычислить с его помощью тег мог только тот, кто послал сообщение.

Вся эта кухня называется "код аутентификации сообщения" (message authentication code, MAC). Не совсем ясно, можно ли MAC отнести к протоколам. Лучше рассмотреть более сложную ситуацию.

Представим себе, что сообщение - это платежное поручение. Тогда банку нужно: а) удостовериться, что сообщение пришло от данного клиента и б) получить доказательство этого. Тег обеспечивает только выполнение (а). Для выполнения (б) нужна электронная подпись.

Здесь появляется третий участник - арбитр. В случае недоразумений начинается арбитраж, и арбитр должен иметь возможность решить, подлинная подпись или нет. Так вот, если у абонентов общий секретный ключ, то такие споры неразрешимы в принципе - получатель никогда не докажет, что он получил поручение от клиента. С тем же успехом он мог создать это поручение сам! Отсюда необходимость в протоколах электронной подписи.

Существуют и более сложные схемы. Например, клиент не хочет, чтобы доказательство факта перевода им денег мог получить кто-нибудь без его желания. Для этого предназначен протокол конфиденциальной подписи. Допустим, клиент банка подписывает поручение о переводе крупной суммы денег с одного счета на другой. Банк, естественно, просит подтверждения. Они выполняют с клиентом специальный протокол, в котором клиент доказывает банку, что это действительно его подпись. После этого совершается перевод. Так вот, если подпись кто-то (противник) перехватил, то этот кто-то все равно не сможет доказать, что данное поручение подписано данным клиентом. Потому что протокол устроен так, что сам противник, не зная секретного ключа этого клиента, мог бы, в принципе, изготовить в точности ту же информацию, которую он перехватил. А вот подписавший всегда может доказать подлинность своей конфиденциальной подписи, равно как и разоблачить любую подделку.

Это хороший пример объяснения того, ради каких задач создаются криптопротоколы.

Есть какая-нибудь классификация протоколов?

- Можно выделить следующие основные классы прикладных криптографических протоколов.

• генерация ключей (или протоколы "типа Диффи-Хеллмана");
• аутентификация (то есть идентификация абонента);
• подпись (обычная, затемненная, конфиденциальная и т. д.);
• электронные деньги (это целая система протоколов);
• протоколы голосования;
• конфиденциальные вычисления.

Протоколы голосования тоже применяются в банковском деле?

- Они разрабатываются не для финансовой сферы (1). Основная область их применения - всевозможные выборы. В частности, гарантируется проверяемость правильности подсчета голосов. Потому они пока и не получили широкого распространения...

Ну уж...

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

Например, здесь каждый голосующий получает некоторые доказательства того, как он проголосовал. Тем самым создаются замечательные возможности для продажи голосов.

Интересно. А защиты от этого не существует?

- Вот сейчас специалисты этим и занимаются. Каждый год появляется несколько статей на эту тему. Конечная цель - довести технологию голосования до массового использования в русле общей тенденции перехода на электронную документацию во всех сферах жизни. В Италии, скажем, недавно принят "закон Бассанини", по которому со следующего года все госучреждения должны быть готовы к приему документов в электронной форме. Там определены организации, которые должны выработать соответствующие форматы и процедуры, в том числе и протоколы.

Давайте теперь подробнее остановимся на протоколах, связанных с электронными деньгами.

- На всякий случай надо уточнить, что электронными деньгами многие называют то, что ныне используется в пластиковых карточках. Это совершенно неправильно. Сейчас пластиковая карточка - это что-то вроде сберкнижки, не более. Она идентифицирует клиента банка и позволяет ему оперировать своим счетом. В карточных системах основная задача - опять-таки обеспечение целостности. А настоящие электронные деньги - это полная замена бумажных денег. Вместо выпуска бумажных купюр банк-эмитент выпускает купюры электронные.

Что собой представляет "электронная купюра"?

- Если очень кратко - это некий кусок информации с "аутентификатором", по которому можно проверять, что купюра не подделана. Для использования таких денег они должны обладать двумя свойствами - целостностью и неотслеживаемостью. Причем снова главное - целостность. Потому что если кто-то научится подделывать эти деньги, то вопрос о неотслеживаемости уже не возникнет....

Ну а чем обеспечивается стойкость реально используемых уже сейчас протоколов в системах электронной наличности банков? Может быть, среди их клиентов есть ловкие люди, которые научились аккуратно подделывать электронные купюры...

- Это... маловероятно. Те протоколы, о которых мы сейчас говорим, изобретены Давидом Шаумом (David Chaum) - есть такой известный специалист в Голландии, он и задачу неотслеживаемости поставил, и электронные деньги придумал, и еще масса других вещей связана с его именем. Так вот, стойкость протоколов, которые он ввел, основана на том, что фактически клиенты этих систем получают подпись по схеме RSA. И если кто-то научился подделывать подписи в такой схеме, то он тем самым взломал систему RSA.

Вот в это как-то не верится. В принципе это вероятно, конечно... но это очень серьезная, глобальная задача. Она, видимо, не намного проще задачи факторизации (разложения составного числа на простые множители).

Я бы отметил здесь еще один момент. Стойкость криптосистем с открытым ключом держится на предположении о существовании функций с секретом или на сложности конкретных задач - факторизации, дискретного логарифма. Значит, если именно эти задачи вдруг кто-нибудь решит, то криптосистемы с открытым ключом... не то чтобы совсем потеряют актуальность, но с ними возникнут проблемы, и серьезные. А вот для схем электронной подписи - теоретически! - подходит любая односторонняя функция (ОФ). Например, есть известная задача о рюкзаке. Гипотеза о ее сложности сегодня обоснована лучше, чем гипотеза о сложности любой другой функции, которую используют или пытаются использовать в криптографии. Есть и ряд других гипотетических ОФ. Но, несмотря на все усилия, пока никому не удалось придумать эффективный способ использовать эти функции на практике... Для таких целей, кроме сложности, нужны некоторые свойства функций, которые "в природе", по-видимому, крайне редки.

А что с неотслеживаемостью?

- Неотслеживаемость обеспечивается следующим образом. Клиент обращается в банк, идентифицирует себя. Банк проверяет, что у клиента действительно есть счет и ему можно выдать запрошенные купюры. После этого клиент передает банку заготовки купюр с номерами и получает так называемую затемненную (слепую) подпись. Из подписанного материала клиент "извлекает" купюру, которой он может в дальнейшем расплатиться. Но! Когда банк - впоследствии - увидит эту купюру, он не узнает, в каком именно сеансе он ее подписал. Вот что гарантирует протокол снятия со счета. Другими словами: банк всегда узнает купюру, которую он подписал; но он не сможет (с вероятностью выше простого угадывания) указать, кому и в каком сеансе он эту купюру выдал. Тут, кстати, надо отметить, что все расчеты с помощью купюр, подписанных данным банком-эмитентом, используются только в расчетах клиентов этого банка между собой (и, конечно, с самим банком).

Я хотел бы уточнить, в каком смысле тут обеспечена неотслеживаемость. Действительно, впоследствии банк не сможет отследить, какому клиенту он когда-то выдавал именно эту купюру. Но в момент выдачи происходит проверка счета, клиент идентифицируется и банк ведь может где-то записать, сколько денег он выдал данному клиенту?

- Может.

Более того, банк всегда может посмотреть, сколько денег находится на счете любого клиента. Он может наблюдать всю динамику его "финансовой жизни". Единственное, чего банк не может, - узнать, на что именно потратил свои деньги клиент и кто прислал деньги ему. Можно ли это назвать полной неотслеживаемостью?

- Ну, знаете ли... если банк не будет знать, у кого сколько денег на счете, то как он вообще будет работать? Я этого не могу себе представить. Но это уже не имеет отношения к криптографии, это - банковское дело. Шаум ставил вопрос о неотслеживаемости так: пусть есть какое-то количество граждан и какое-то количество (коммерческих или государственных) организаций. Граждане обращаются в эти организации таким образом, что требуется некоторая идентификация. Пример: на Западе библиотеки давно переведены на электронную систему заказа книг. Любой абонент сети может обратиться за любой книгой, статьей и т. д. В принципе, возникает возможность вести полное досье на каждого: кто чем интересуется. А это - грубейшее нарушение ваших прав и свобод. Для обеспечения неотслеживаемости Шаум предложил схему с псевдонимами.

Как она работает?

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

Знакомая схема - право на доступ в спецхран...

- Но этот сертификат никак не привязан к паспортным данным!

Все отлично, если не считать того, что эту привязку знает орган, который выдает сертификаты.

- Не обязательно. В теории схема, когда "орган знает", называется "схемой Большого Брата". Ее достоинства и недостатки очевидны. Но можно обойтись и без Большого Брата. Вы приходите в этот самый "орган" с паспортом. Он проверяет паспорт и подписывает ваш псевдоним затемненной подписью. Но он-то, "орган", вашего псевдонима не знает! Ситуация точно такая же, как с выдачей электронной купюры. Поэтому дальше ваши контакты с банком, библиотекой, прачечной и т. д. "орган" отследить не может. В свою очередь, прачечная и библиотека знают только ваш псевдоним. Но, честно говоря, даже сейчас можно без всяких протоколов во многих банках зарегистрироваться под любым именем, открыть счет, положить туда деньги - электронные или обычные, неважно. Регистрация "по паспорту" далеко не всегда требуется. Все зависит от того, каких правил в этом вопросе придерживается банк (библиотека, гостиница...). Этот момент никак не связан с "электронностью" денег. С другой стороны, большинство клиентов любого банка полностью идентифицированы и против этого не протестуют...

Но возникает один очень принципиальный вопрос: зачем вообще банки, если электронными купюрами мы все сможем свободно обмениваться напрямую?

- Совершенно верно. Поэтому электронным деньгам будут особенно сопротивляться банкиры. Сопротивляться-то они будут, но я считаю, что все равно переход на электронные деньги неизбежен.

Как это может выглядеть на практике?

- В первом приближении так: есть один банк-эмитент, где находятся счета клиентов, в том числе других банков, и он выдает клиентам электронные купюры.

А клиенты потом расплачиваются ими между собой?

- Да, но, к сожалению, это организовать не так просто - получатель должен иметь возможность проверить подлинность купюры (в такой системе ее обычно называют электронной монетой). Сразу возникает проблема - монета легко копируется, и один и тот же клиент мог бы дважды расплатиться одной и той же монетой. Но эта проблема решена, причем довольно остроумно с математической точки зрения. В результате, когда монета в конце концов попадает в банк, он проверяет, не была ли она туда положена раньше. И когда он видит, что монета потрачена дважды, схема позволяет идентифицировать нарушителя.

А предотвратить нарушение нельзя?

- Можно, но только с помощью дополнительных средств.

Опять "Большой Брат"?

- Нет, всего лишь электронный бумажник. Бумажник - это компьютер со встроенным в него модулем, выданным банком. Этот модуль и контролирует, чтобы монеты дважды не тратились.

Прекрасное решение, по-моему.

- В общем, да. Единственная техническая проблема - модуль должен быть хорошо защищен. Как часто пишут на Западе, модуль достаточно надежен, если его взлом требует усилий национальной лаборатории. Просто надо, чтобы дилетанты не могли взломать. А профессионалов очень мало, и они вряд ли станут этим заниматься.

А какие еще здесь проблемы?

- Еще одна задача - как сделать электронные монеты переводимыми, т. е. применимыми для многих платежей. Теоретически это сделано, но длина монеты при этом растет, и это неизбежно. С другой стороны, когда монета возвращается в банк, она через некоторое время "уничтожается". Поэтому возможно такое решение: сделать монеты переводимыми, а клиенты пусть сами решают, хранить им эти длинные записи у себя или обменять в банке на новые, короткие. Между прочим, длина монет растет именно потому, что они обеспечивают неотслеживаемость платежей при сохранении возможности идентификации первого нарушителя. Причем неотслеживаемость тут абсолютная! Она строго доказана и не зависит ни от каких предположений об односторонних функциях. А целостность (т. е. неподделываемость) основывается на уверенности в стойкости, например, схемы RSA.

Есть такое понятие "атака на протокол"?

- Конечно.

Мне очень понравилась фраза в интервью Валерия Ященко (2), где он говорит о том, что за шифрами с открытым ключом "нет истории их вскрытия", и это их недостаток. За протоколами, видимо, тем более нет такой истории?

- Конечно, протоколы объект сравнительно новый. Но... есть, например, такая модификация схемы RSA - схема Рабина. Майкл Рабин (Michael Rabin) доказал, что при некоторых предположениях (о противнике) взламывание этой схемы эквивалентно решению задачи факторизации. А ведь этой задачей занимались еще до нашей эры! Более того, это очень красивая задача: она просто формулируется и для математиков очень привлекательна. А в шифраторах бывает так все закручено, что просто очень не хочется в это вникать. В теоретической криптографии есть стойкость двух типов - информационная и сложностная. А на практике есть еще стойкость психологическая - когда не хватает желания этим заниматься. Но оно может появиться: если соберут хорошую бригаду, хорошо им заплатят...

Что такое конфиденциальные вычисления (шестой раздел из вашего списка)?

- Это самый туманный раздел всей науки о криптографических протоколах... Пусть есть N процессоров и N аргументов. Каждый процессор "знает" свой аргумент. Задача состоит в том, что они должны совместно вычислить заданную функцию от этих аргументов - но так, чтобы ни один процессор в результате не "узнал" ничего о чужих аргументах (не считая того, что следует из его собственного аргумента и найденного значения функции). Более того, некоторые участники этого вычисления могут быть противниками, то есть они будут стремиться помешать правильному вычислению. Оказывается, что любую функцию можно вычислить конфиденциально, если только доля противников не превышает некоторого порога.

Где же возникают такие задачи?

- Предположим, нам нужна некая программа для сравнительно простых, но очень секретных вычислений. Разные куски этой программы заказали (из соображений секретности) разным программистам. Среди них могут быть "разведчики", которые вставят свои закладки, а также "халтурщики", которые наделают ошибок. Частный случай, кстати, - протокол голосования; аргументы - голоса "за" или "против", функция - сумма аргументов... Другое направление - самопроверяющиеся (self-checking) и самокорректирующиеся (self-correcting) вычисления: как написать маленькую программку, которая проверит, что большая программа работает правильно, или даже скорректирует имеющиеся в ней ошибки? Это очень интересная область, но пока результаты получены только для совсем узкого класса функций.

Ну, а с "квантовыми" протоколами какая ситуация?

- С квантовыми протоколами был большой бум некоторое время назад. Они основаны на том, что при попытке перехвата "квантового сообщения" оно - благодаря законам квантовой механики - разрушается. Но вот два года назад на конференции в Праге один из ведущих специалистов по этому вопросу Жиль Брассар (Gilles Brassard) докладывал, что эти протоколы, по крайней мере, теоретически, рухнули. Все, кроме одного. Кстати говоря, после передачи сообщения по квантовому каналу получатель и отправитель должны еще выполнить довольно сложный протокол по обычному каналу, чтобы согласовать свои наблюдения. И почему-то вот этот "классический" протокол обычно упускают из виду... В общем, такое впечатление, что на квантовую криптографию возлагают слишком большие надежды. Реальных квантовых каналов связи пока нет - 4 километра в лабораторных условиях считается огромным достижением. Даже если это и реализуют, то не слишком скоро и очень дорого.

2 См. приложение "Компьюномика" в "Компьютерре" #20 (248) от 25 мая 1998 г.