ElGamal

Как и в базовой схеме ElGamal, подписью является пара чисел: XhY. Уолтер может проверить подпись El­Gamal. Он убеждается, что

Боб может восстановить подсознательное сообщение. Сначала он убеждается, что

(gyX^r = g^M' (mod p)

Если это так, он считает сообщение подлинным (не подделанным Уолтером). Затем для восстановления М он вычисляет

М = (Г¹ (M' - rX)) mod (р- 1)

Например, пусть/; = И, a g = 2. Закрытый ключ г выбирается равным 8. Это означает, что открытым клю­чом, который Уолтер может использовать для проверки подписи, будет g^r mod p = 2⁸ mod 11 = 3.

Чтобы отправить подсознательное сообщение М = 9, используя безобидное сообщение М' = 5, Алиса прове­ряет, что 9 и 11, а также 5 и 11 попарно взаимно просты. Она также убеждается, что взаимно просты 9 и 11-1=10. Это так, поэтому она вычисляет

X = g^M' (mod/;) = 2⁹ modll= 6

Затем она решает следующее уравнение для Y:

5 = 8 6 + 9 Fmod 10

Y= 3, поэтому подписью служит пара чисел 6 и 3 (Хи Y). Боб убеждается, что

(gyX^r = g^M' (mod p)

(2⁸)⁶6³=2⁵ (modll)

Это так (выполните арифметические действия самостоятельно, если вы мне не верите), поэтому он может раскрыть подсознательное сообщение, вычисляя

М= (Г¹ (М' - rX)) mod (р - 1)= 3"^!(5 - 8*6) mod 10 = 7(7) mod 10 = 49 mod 10 = 9

ESIGN

Подсознательный канал можно добавить и к ESIGN [1460] (см. раздел 20.6). В ESIGN секретный ключ явля­ется парой больших простых чисел р и д, а открытым ключом служит п = p²q. Использовании подсознательного канала закрытым ключом являются три простых числа p, qur,a открытым ключом - я, такое что

п = p²qr

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

Чтобы подписать обычное сообщение, Алиса сначала выбирает случайное число х, меньшее pqr, и вычисляет:

w, наименьшее целое, которое больше или равно (Н(т) - х^к mod n)lpq

s-x + dw/kx"-¹ mod p) pq

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

Для проверки подписи Боб вычисляет / mod п. Кроме этого, он вычисляет а, наименьшее целое, которое больше или равно удвоенному числу битов п, деленному на 3. Если Я(от) меньше или равна / mod n, и если / mod n меньше Щт)+2^а, то подпись считается правильной.

Для отправки подсознательного сообщения М с помощью безобидного сообщения М' Алиса вычисляет s, ис­пользуя М вместо of Дот). Это означает, что сообщение должно быть меньше, чем p²qr. Затем она выбирает случайное число и и вычисляет

х' = М' +иг

Затем это значение х' используется в качестве "случайного числа" х при подписи М'. Соответствующее зна­чение s посылается в качестве подписи.

Уолтер может проверить, что s (второе s) является правильной подписью М' Точно также проверить подлин­ность сообщения может и Боб. Но, так как ему известно и г, он может вычислить

s = x' + ypqr = M + ur + ypqr = M (mod r)

Эта реализация подсознательного канала намного лучше двух предыдущих. В вариантах Ong-Schnorr-Shamir и ElGamal у Боба должен быть закрытый ключ Алисы. Боб сможет не только читать подсознательные сообщения Алисы, но и выдавать себя за Алису, подписывая обычные документы. Алиса ничего с этим не смо­жет поделать, устанавливая такой подсознательный канал, ей придется довериться Бобу.

Схема ESICN страдает от этой проблемы. Закрытым ключом Алисы служит набор трех простых чисел: р, q

и г. Секретным ключом Боба является только г. Он знает п = р²дг, но, чтобы раскрыть р и д, ему понадобится разложить на множители это число. Если простые числа достаточно велики, Бобу будет так же трудно выдать себя за Алису, как и Уолтеру или кому-нибудь еще.

DSA

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

сообщение.

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