и r. Секретным ключом Боба является только r. Он знает n = /2qr, но, чтобы раскрыть p и q, ему понадобится разложить на множители это число . Если простые числа достаточно велики, Бобу будет так же трудно выдать себя за Алису, как и Уолтеру или кому-нибудь еще .

Подсознательный канал существует и в DSA (см. раздел 20.1) [1468, 1469, 1473]. На самом деле их даже может быть несколько. Простейший подсознательный канал включает выбор k. Предполагается, что это будет 160-битовое число. Однако, если Алиса выбирает конкретное k, то Боб, зная закрытый ключ Алисы, сможет раскрыть это k. Алиса пос1лать Бобу 160-битовое подсознательное сообщение в каждой подписи DSA, а все остальные будут только проверять подпись Алисы . Дополнительное усложнение: Так как k должно быть случайным, Алиса и Боб должны использовать общий одноразовый блокнот и шифровать подсознательное соо б-щение с помощью этого блокнота, генерируя k.

В DSA есть подсознательные каналы, не требующие передавать Бобу закрытый ключ Алисы . Они также подразумевают выбор конкретных значений k, но не могут передавать по 160 битов информации. Следующая схема, представленная в [1468, 1469], позволяет Алисе и Бобу обмениваться в каждой подписи одним битом подсознательной информации.

(1) Алиса и Боб выбирают случайное простое число P (отличающееся от параметра p в схеме подписи). Это секретный ключ для подсознательного канала.

(2) Алиса подписывает безобидное сообщение M. Если она хочет отправить Бобу подсознательный бит 1, она убеждается, что параметр r подписи является квадратичным остатком по модулю P. Если она хочет отправить ему 0, она проверяет, что параметр r подписи не является квадратичным остатком по модулю P. Она добивается этого, подписывая сообщение с помощью случайных значений k, пока она не получит подпись с нужным ей свойством для r. Так как числа, являющиеся квадратичными остатками и не являющиеся ими, равновероятны, то это не должно быть слишком сложно.

(3) Алиса пос1лает Бобу подписанное сообщение.

(4) Боб проверяет подпись, убеждаясь в подлинности сообщения . Затем он проверяет, является ли r квадратичным остатком по модулю P и восстанавливает подсознательный бит.

Передача таким образом нескольких битов подразумевает подбор такого r, которое является или не является квадратичным остатком по нескольким модулям. Подробности приведены в [1468, 1469].

Эта схема может быть легко расширена для передачи нескольких подсознательных битов на подпись . Если Алиса и Боб выбирают два случайных числа P и Q, то Алиса может посылать два бита, выбирая случайное k так, чтобы г являлось или не являлось квадратичным остатком mod P, а также являлось или не являлось квадр а-тичным остатком mod Q. Случайное значение k с вероятностью 25 процентов позволит получить r с нужными свойствами.

Вот как Мэллори, нечестный реализатор DSA, может создать алгоритм, извлекающий по 10 битов закрытого ключа Алисы из каждой ее подписи.

(1) Мэллори строит свою реализацию DSA базе устойчивой к взлому СБИС, чтобы никто не смог проверить, как она работает. Он создает 14 подсознательных каналов в своей реализации DSA. То есть, он выбирает 14 случайных простых чисел и использует микросхему, которая выбирает значение k так, чтобы r являлось или не являлось квадратичным остатком по модулю каждого из этих 14 простых чисел , в зависимости от подсознательного сообщения.

(2) Мэллори выдает микросхемы Алисе, Бобу и остальным желающим.

(3) Алиса обычным образом подписывает сообщение, используя свой закрытый 160-битовый ключ x.

(4) Микросхема случайным образом выбирает 10-битовый блок x: первые 10 битов, вторые 10 битов, и т.д. Так как существует 16 возможных 10-битовых блоков, то номер блока выражается 4-битовым числом. Этот 4-битовый идентификатор и 10 битов ключа и будут 14-битовым подсознательным сообщением .

(5) Микросхема перебирает случайные значения k, пока не удастся найти то, которое обладает правильными квадратичными остатками, нужными для передачи подсознательного . Вероятность случайного k обладать правильной формой равна 1/16384. Если микросхема может проверить 10000 значений k в секунду, нужное значение будет найдено меньше, чем за пару секунд. Эти вычисления не зависят от сообщения и могут быть вычислены заранее, до того, как Алиса захочет подписать сообщение.

(6) Микросхема обычным образом подписывает сообщение, используя выбранное на этапе (5) значение k.

(7) Алиса посылает цифровую подпись Бобу, или опубликовывает ее в сети, или еще что-нибудь делает.

(8) Мэллори раскрывает r и, так как он знает 14 простых чисел, расшифровывает подсознательное

сообщение.

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

Уничтожение подсознательного канала в DSA

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

Вот этот протокол [1470, 1472, 1473]

(1) Алиса выбирает k и посылает Бобу u = gk mod p

(2) Боб выбирает k" и посылает его Алисе.

(3) Алиса вычисляет k = kk" mod (p - 1). Она использует k, чтобы подписать свое сообщение M, используя DSA, и пос1лает Бобу свою подпись: r и s.

(4) Боб проверяет, что ((u = gk mod p) mod q) = r

Если это так, то он знает, что для подписи M использовалось k. После этапа (4) Боб знает, что в r не было включено никакой подсознательной информации. Если он является доверенной стороной, он может проверить, что в подписи Алисы нет подсознательной информации . Другим придется поверить его заявлению, Боб не см о-жет доказать этот факт третьей стороне, воспроизведя протокол .

Удивительно то, что Боб, если захочет, может использовать этот протокол для создания собственного по д-сознательного канала. Боб может включить подсознательную информацию в одну из подписей Алисы, выбрав k" с определенными характеристиками. Когда Симмонс откр1л такую возможность, он назвал ее "Каналом кукушки". Подробности работы Канала кукушки, и мешающий этому трехпроходный протокол генерации k, рассматриваются в [1471, 1473].

Другие схемы

Подсознательный канал можно организовать для любой схемы подписи [1458, 1460, 1406]. Описание протокола встраивания подсознательного канала в схемы Fiat-Shamir и Feige-Fiat-Shamir вместе с возможными злоупотреблениями можно найти в [485].

23.4 Неотрицаемые цифровые подписи

Автором этого алгоритма неотрицаемой подписи (см. раздел 4.3) является Дэвид Чаум (David Chaum) [343,327]. Сначала опубликовываются большое простое число p и примитивный элемент g, которые будут совместно использоваться группой подписывающих. У Алисы есть закрытый ключ x и открытый ключ gx mod p.

Чтобы подписать сообщение, Алиса вычисляет z = mx mod p. Это все, что ей нужно сделать. Проверка подписи немного сложнее.

(1) Боб выбирает два случайных числа, a и b, меньшие p, и отправляет Алисе: c = za(gx)b mod p

(2) Алиса вычисляет t=x-1 mod (p-1), и отправляет Бобу: d = ct mod p

(3) Боб проверяет, что d - magb (mod p)

Если это так, он считает подпись истинной.

Представим, что Алиса и Боб выполнили этот протокол, и Боб теперь считает, что Алиса подписала сообщение. Боб хочет убедить в этом Кэрол, поэтому он показывает ей запись протокола. Дэйв, однако, хочет убедить Кэрол, что документ подписан кем-то другим . Он создает поддельную запись протокола. Сначала он генерирует сообщение на этапе (1). Затем на этапе (3) он генерирует d и ложную передачу от другого человека на этапе (2).

Наконец, он создает сообщение этапа (2). Для Кэрол записи Боба и Дэйва одинаковы. Ее невозможно убедить в правильности подписи, пока она не выполнит протокол самостоятельно .

Конечно, если бы она следила из-за плеча Боба за тем, как он выполняет протокол, она была бы убеждена . Кэрол нужно увидеть выполнение этапов по порядку, так, как это делал Боб .

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

Другой протокол включает не только протокол подтверждения - Алиса может убедить Боба в правильности своей подписи - но и протокол отрицания. Алиса может с помощью интерактивного протокола с нулевым зн а-нием убедить Боба, что ее подпись неправильна, если это так [329].

Как и предыдущий протокол группа подписывающих использует общедоступное большое простое число p и примитивный элемент g. У Алисы есть закрытый ключ x и открытый ключ gx mod p. Чтобы подписать сообщение, Алиса вычисляет z = otx mod p. Чтобы проверить подпись:

(1) Боб выбирает два случайных числа, a и b, меньшие p, и отправляет Алисе:

c = OTagb mod p

(2) Алиса выбирает случайное число q, меньшее p, а затем вычисляет и отправляет Бобу: s1 = cgq mod p, s2 = (cgq)x mod p

(3) Боб посылает Алисе a и b, чтобы Алиса могла убедиться, что Боб не мошенничал на этапе (1).

(4) Алиса посылает Бобу q, чтобы он мо воспользоваться otx и восстановить s1 и s2. Если s1 = cgq mod p

S2 = (gx)b+qza (mod

то подпись правильна.

Алиса может также отказаться от подписи z под сообщением т. Подробности приведены в [329]. Дополнительные протоколы для неотрицаемых подписей можно найти в [584, 344]. Лейн Харн (Lein Harn) и Шубао Янг (Shoubao Yang) предложили схему групповых неотрицаемых подписей [700].

Преобразуемые неотрицаемые подписи

Алгоритм для преобразуемых неотрицаемых подписей, которые можно проверять, отменять и преобраз о-вывать в обычные неотрицаемые подписи, приведен в [213]. Он основан на алгоритме цифровых подписей El-Gamal.

Как и в ElGamal, сначала выбираются два простых числа, p и q, так, чтобы q б1ло делителем /7-1. Теперь нужно создать число g, меньшее q. В диапазоне от 2 до /7-1 выбирается случайное число h и вычисляется

g=h(-1)/q mod p

Если g равно 1, выбирается другое случайное h. Если нет, используется полученное значение g.

Закрытыми ключами служат два различных случайных числа , x и z, меньшие q. Открытыми ключами являются /7, q, g, y и м, где

y = gx mod p

M=g mod p

Для вычисления преобразуемой неотрицаемой подписи сообщения т (которое в действительности является хэш-значением сообщения), сначала диапазоне от 1 до q-1 выбирается случайное число t. Затем вычисляется

T = gr mod p

m = Ttzm mod q.

Теперь вычисляется обычная подпись ElGamal для m. Выбирается случайное число R, меньшее /7-1 и взаимно простое с ним. Затем вычисляется r = gR mod p и, с помощью расширенного алгоритма Эвклида, в ы-числяется s, для которого

т = rx + Rs (mod q)

Подписью служат подпись ElGamal (r, s) и T. Вот как Алиса подтверждает свою подпись Бобу: