Примеры криптографических протоколов

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

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

2. Протокол иден­тификации абонента. Взаимодействуют два абонента А и В. Абонент А хочет доказать абоненту В, что он именно А, а не против­ник. Типичный пример: А — владелец интеллектуальной смарт-карты (кре­дитной карты, карты доступа в закрытое помещение, компьютерный ключ), В — банк, компьютер охраны, администратор сети.

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

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

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

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

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

2) любые числа x ₁ ,x ₂ Î X, имеющие один образ f(x₁) = f(x₂), имеют одну четность;

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

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

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

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

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

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

Интерактивная система доказательства

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

Определение. Под интерактивной системой доказательства (Р, V, S) понимают протокол взаимодействия двух абонентов:

Р (prover) — доказывающего и

V (verifier) — проверяющего.

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

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

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

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

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

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