4. Новые направления

В 1983 году в книге «Коды и математика» М. Н. Аршинова и Л. Е. Садовского (библиотечка «Квант») было написано: «Приемов тайнописи — великое множество, и, скорее всего, это та область, где уже нет нужды придумывать что-нибудь существенно новое.» Однако это было очередное большое заблуждение относительно криптографии. Еще в 1976 году была опубликована работа молодых американских математиков У. Диффи и М. Э. Хеллмана «Новые направления в криптографии», которая не только существенно изменила криптографию, но и привела к появлению и бурному развитию новых направлений в математике. Центральным понятием «новой криптографии» является понятие односторонней функции (подробнее об этом см. главу 2).

Односторонней называется функция обладающая двумя свойствами:

а) существует полиномиальный алгоритм вычисления значений

б) не существует полиномиального алгоритма инвертирования функции (т. е. решения уравнения относительно х, точное определение см. на стр. 30).

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

Еще одним новым понятием является понятие функции с секретом. Иногда еще употребляется термин функция с ловушкой. Функцией с секретом К называется функция зависящая от параметра К и обладающая тремя свойствами:

а) существует полиномиальный алгоритм вычисления значения для любых

б) не существует полиномиального алгоритма инвертирования при неизвестном

в) существует полиномиальный алгоритм инвертирования при известном К.

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

Применение функций с секретом в криптографии позволяет:

1) организовать обмен шифрованными сообщениями с использованием только открытых каналов связи, т. е. отказаться от секретных каналов связи для предварительного обмена ключами;

2) включить в задачу вскрытия шифра трудную математическую задачу и тем самым повысить обоснованность стойкости шифра;

3) решать новые криптографические задачи, отличные от шифрования (электронная цифровая подпись и др.).

Опишем, например, как можно реализовать п. 1). Пользователь А, который хочет получать шифрованные сообщения, должен выбрать какую-нибудь функцию с секретом К. Он сообщает всем заинтересованным (например, публикует) описание функции в качестве своего алгоритма шифрования. Но при этом значение секрета К он никому не сообщает и держит в секрете. Если теперь пользователь В хочет послать пользователю А защищаемую информацию а; 6 X, то он вычисляет и посылает у по открытому каналу пользователю А. Поскольку А для своего секрета К умеет инвертировать то он вычисляет х по полученному у. Никто другой не знает К и поэтому в силу свойства б) функции с секретом не сможет за полиномиальное время по известному шифрованному сообщению вычислить защищаемую информацию х.

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

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

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

1) подписать сообщение решить уравнение может только абонент — обладатель данного секрета другими словами, подделать подпись невозможно;

2) проверить подлинность подписи может любой абонент, знающий открытый ключ, т.е. саму функцию

3) при возникновении споров отказаться от подписи невозможно в силу ее неподделываемости;

4) подписанные сообщения можно, не опасаясь ущерба, пересылать по любым каналам связи.

Кроме принципа построения криптосистемы с открытым ключом, Диффи и Хеллман в той же работе предложили еще одну новую идею — открытое распределение ключей. Они задались вопросом: можно ли организовать такую процедуру взаимодействия абонентов по открытым каналам связи, чтобы решить следующие задачи:

1) вначале нет никакой общей секретной информации, но в конце процедуры такая общая секретная информация (общий ключ) появляется, т. е. вырабатывается;

2) пассивный противник, который перехватывает все передачи информации и знает, что хотят получить тем не менее не может восстановить выработанный общий ключ

Диффи и Хеллман предложили решать эти задачи с помощью функции

где большое простое число, произвольное натуральное число, а — некоторый примитивный элемент, поля Общепризнанно, что инвертирование функции т.е. дискретное логарифмирование, является трудной математической задачей. (Подробнее см. главу 4.)

Сама процедура или, как принято говорить, протокол выработки общего ключа описывается следующим образом.

Абоненты независимо друг от друга случайно выбирают по одному натуральному числу — скажем Эти элементы они держат в секрете. Далее каждый из них вычисляет новый элемент:

(Числа и а считаются общедоступными.) Потом они обмениваются этими элементами по каналу связи. Теперь абонент А, получив у в и зная свой секретный элемент вычисляет новый элемент:

Аналогично поступает абонент В:

Тем самым появился общий элемент поля, равный Этот элемент и объявляется общим ключом

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

Успехи, достигнутые в разработке схем цифровой подписи и открытого распределения ключей, позволили применить эти идеи также и к другим задачам взаимодействия удаленных абонентов. Так возникло большое новое направление теоретической криптографии — криптографические протоколы (подробнее см. главу 3).

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

Приведем еще несколько примеров задач, решаемых удаленными абонентами. (Читателю рекомендуем по своему вкусу самостоятельно придумать еще какие-нибудь примеры.)

1. Взаимодействуют два не доверяющих друг другу абонента. Они хотят подписать контракт. Это надо сделать так, чтобы не допустить следующую ситуацию: один из абонентов получил подпись другого, а сам не подписался.

Протокол решения этой задачи принято называть протоколом подписания контракта.

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

Протокол решения этой задачи принято называть протоколом подбрасывания монеты.

Опишем один из простейших протоколов подбрасывания монеты по телефону (так называемая схема Блюма-Микали). Для его реализации у абонентов должна быть односторонняя функция удовлетворяющая следующим условиям:

1) X — множество целых чисел, которое содержит одинаковое количество четных и нечетных чисел;

2) любые числа , имеющие один образ имеют одну четность;

3) по заданному образу «трудно» вычислить четность неизвестного аргумента х.

Роль подбрасывания монеты играет случайный и равновероятный выбор элемента роль орла и решки — четность и нечетность х соответственно. Пусть А — абонент, подбрасывающий монету, абонент, угадывающий результат. Протокол состоит из следующих шагов:

1) А выбирает х («подбрасывает монету»), зашифровывает х, т. е. вычисляет и посылает у абоненту

2) В получает у, пытается угадать четность х и посылает свою догадку абоненту

3) А получает догадку от В и сообщает В, угадал ли он, посылая ему выбранное число

4) В проверяет, не обманывает ли А, вычисляя значение и сравнивая его с полученным на втором шаге значением у.

3. Взаимодействуют два абонента (типичный пример: А — клиент банка, В — банк). Абонент А хочет доказать абоненту В, что он именно А, а не противник.

Протокол решения этой задачи принято называть протоколом идентификации абонента.

4. Взаимодействуют несколько удаленных абонентов, получивших приказы из одного центра. Часть абонентов, включая центр, могут быть противниками. Необходимо выработать единую стратегию действий, выигрышную для абонентов.

Эту задачу принято называть задачей о византийских генералах, а протокол ее решения — протоколом византийского соглашения.

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

Осмысление различных протоколов и методов их построения привело в 1985-1986 г.г. к появлению двух плодотворных математических моделей — интерактивной системы доказательства и доказательства с нулевым разглашением. Математические исследования этих новых объектов позволили доказать много утверждений, весьма полезных при разработке криптографических протоколов (подробнее об этом см. главу 2).

Под интерактивной системой доказательства понимают протокол взаимодействия двух абонентов: (доказывающий) и V (проверяющий). Абонент хочет доказать V, что утверждение S истинно. При этом абонент V самостоятельно, без помощи не может проверить утверждение S (поэтому V и называется проверяющим). Абонент может быть и противником, который хочет доказать V, что утверждение S истинно, хотя оно ложно. Протокол может состоять из многих раундов обмена сообщениями между и должен удовлетворять двум условиям:

1) полнота — если S действительно истинно, то абонент убедит абонента V признать это;

2) корректность — если S ложно, то абонент вряд ли убедит абонента V, что S истинно.

Здесь словами «вряд ли» мы для простоты заменили точную математическую формулировку.

Подчеркнем, что в определении системы не допускалось, что V может быть противником. А если V оказался противником, который хочет «выведать» у какую-нибудь новую полезную для себя информацию об утверждении 5? В этом случае естественно, может не хотеть, чтобы это случилось в результате работы протокола Протокол решающий такую задачу, называется доказательством с нулевым разглашением и должен удовлетворять, кроме условий 1) и 2), еще и следующему условию:

3) нулевое разглашение — в результате работы протокола абонент V не увеличит свои знания об утверждении S или, другими словами, не сможет извлечь никакой информации о том, почему S истинно.