Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
(6) Микросхема обычным образом подписывает сообщение, используя выбранное на этапе (5) значение k. (7) Алиса посылает цифровую подпись Бобу, или опубликовывает ее в сети, или еще что-нибудь делает. (8) Мэллори раскрывает r и, так как он знает 14 простых чисел, расшифровывает подсознательное сообщение. Страшнее всего, что, даже если Алиса знает, что происходит, она ничего не сможет доказать . Пока 14 про- стых чисел хранятся в секрете, Мэллори в безопасности. Уничтожение подсознательного канала в DSA Подсознательный канал опирается на то, что Алиса может выбирать k для передачи подсознательной ин- формации. Чтобы сделать подсознательный канал невозможным, Алисе не должно быть позволено выбирать k. Однако, выбор k должен быть запрещен и для всех других. Если кому-то другому будет позволено выбирать k, то этот человек получит возможность подделать подпись Алисы . Единственным решением для Алисы является проведение генерации k вместе с другой стороной, Бобом, так, чтобы Алиса не могла контролировать ни один бит k, а Боб не мог определить ни один бит k. На другой стороне протокола у Боба должна быть возможность проверить, что Алиса использовала именно совместно созданное k. Вот этот протокол [1470, 1472, 1473] (1) Алиса выбирает k' и посылает Бобу u = g k' mod p (2) Боб выбирает k" и посылает его Алисе. (3) Алиса вычисляет k = k'k" mod (p - 1). Она использует k, чтобы подписать свое сообщение M, используя DSA, и посылает Бобу свою подпись: r и s. (4) Боб проверяет, что ((u = g k' mod p) mod q) = r Если это так, то он знает, что для подписи M использовалось k. После этапа (4) Боб знает, что в r не было включено никакой подсознательной информации . Если он является доверенной стороной, он может проверить, что в подписи Алисы нет подсознательной информации . Другим придется поверить его заявлению, Боб не см о- жет доказать этот факт третьей стороне, воспроизведя протокол . Удивительно то, что Боб, если захочет, может использовать этот протокол для создания собственного по д- сознательного канала. Боб может включить подсознательную информацию в одну из подписей Алисы, выбрав k" с определенными характеристиками. Когда Симмонс открыл такую возможность , он назвал ее "Каналом ку- кушки". Подробности работы Канала кукушки, и мешающий этому трехпроходный протокол генерации k, рас- сматриваются в [1471, 1473]. Другие схемы Подсознательный канал можно организовать для любой схемы подписи [1458, 1460, 1406]. Описание прото- кола встраивания подсознательного канала в схемы Fiat-Shamir и Feige-Fiat-Shamir вместе с возможными зло- употреблениями можно найти в [485]. 23.4 Неотрицаемые цифровые подписи Автором этого алгоритма неотрицаемой подписи (см. раздел 4.3) является Дэвид Чаум (David Chaum) [343,327]. Сначала опубликовываются большое простое число p и примитивный элемент g, которые будут со- вместно использоваться группой подписывающих . У Алисы есть закрытый ключ x и открытый ключ g x mod p. Чтобы подписать сообщение, Алиса вычисляет z = m x mod p. Это все, что ей нужно сделать. Проверка под- писи немного сложнее. (1) Боб выбирает два случайных числа, a и b, меньшие p, и отправляет Алисе: c = z a (g x ) b mod p (2) Алиса вычисляет t=x -1 mod (p-1), и отправляет Бобу: d = c t mod p (3) Боб проверяет, что d ? m a g b (mod p) Если это так, он считает подпись истинной. Представим, что Алиса и Боб выполнили этот протокол, и Боб теперь считает, что Алиса подписала сообще- ние. Боб хочет убедить в этом Кэрол, поэтому он показывает ей запись протокола . Дэйв, однако, хочет убедить Кэрол, что документ подписан кем-то другим . Он создает поддельную запись протокола . Сначала он генерирует сообщение на этапе (1). Затем на этапе (3) он генерирует d и ложную передачу от другого человека на этапе (2). Наконец, он создает сообщение этапа (2). Для Кэрол записи Боба и Дэйва одинаковы. Ее невозможно убедить в правильности подписи, пока она не выполнит протокол самостоятельно . Конечно, если бы она следила из-за плеча Боба за тем, как он выполняет протокол, она была бы убеждена . Кэрол нужно увидеть выполнение этапов по порядку, так, как это делал Боб . Используя эту схему подписи, можно столкнуться с проблемой, но я не знаю подробностей . Прежде, чем воспользоваться этой схемой, просмотрите литературу . Другой протокол включает не только протокол подтверждения - Алиса может убедить Боба в правильности своей подписи - но и протокол отрицания. Алиса может с помощью интерактивного протокола с нулевым зн а- нием убедить Боба, что ее подпись неправильна, если это так [329]. Как и предыдущий протокол группа подписывающих использует общедоступное большое простое число p и примитивный элемент g. У Алисы есть закрытый ключ x и открытый ключ g x mod p. Чтобы подписать сообще- ние, Алиса вычисляет z = m x mod p. Чтобы проверить подпись: (1) Боб выбирает два случайных числа, a и b, меньшие p, и отправляет Алисе: c = m a g b mod p (2) Алиса выбирает случайное число q, меньшее p, а затем вычисляет и отправляет Бобу: s 1 = cg q mod p, s 2 = (cg q ) x mod p (3) Боб посылает Алисе a и b, чтобы Алиса могла убедиться, что Боб не мошенничал на этапе (1). (4) Алиса посылает Бобу q, чтобы он мо воспользоваться m x и восстановить s 1 и s 2 . Если s 1 ? cg q mod p s 2 ? (g x ) b+q z a (mod p) то подпись правильна. Алиса может также отказаться от подписи z под сообщением m. Подробности приведены в [329]. Дополни- тельные протоколы для неотрицаемых подписей можно найти в [584, 344]. Лейн Харн (Lein Harn) и Шубао Янг (Shoubao Yang) предложили схему групповых неотрицаемых подписей [700]. Преобразуемые неотрицаемые подписи Алгоритм для преобразуемых неотрицаемых подписей, которые можно проверять, отменять и преобраз о- вывать в обычные неотрицаемые подписи, приведен в [213]. Он основан на алгоритме цифровых подписей El- Gamal. Как и в ElGamal, сначала выбираются два простых числа, p и q, так, чтобы q было делителем p-1. Теперь нужно создать число g, меньшее q. В диапазоне от 2 до p-1 выбирается случайное число h и вычисляется g=h( p-1)/q mod p Если g равно 1, выбирается другое случайное h. Если нет, используется полученное значение g. Закрытыми ключами служат два различных случайных числа , x и z, меньшие q. Открытыми ключами явля- ются p, q, g, y и u, где y = g x mod p u=g я mod p Для вычисления преобразуемой неотрицаемой подписи сообщения m (которое в действительности является хэш-значением сообщения), сначала диапазоне от 1 до q-1 выбирается случайное число t. Затем вычисляется T = g r mod p и m' = Ttzm mod q. Теперь вычисляется обычная подпись ElGamal для m'. Выбирается случайное число R, меньшее p-1 и взаимно простое с ним. Затем вычисляется r = g R mod p и, с помощью расширенного алгоритма Эвклида, в ы- числяется s, для которого m' ? rx + Rs (mod q) Подписью служат подпись ElGamal (r, s) и T. Вот как Алиса подтверждает свою подпись Бобу: (1) Боб генерирует два случайных числа, a и b, и вычисляет c = T Tma g b mod p и посылает результат Алисе. (2) Алиса генерирует случайное число k и вычисляет h 1 = cg k mod p и h 2 = h 1 z mod p, а затем посылает оба числа Бобу. (3) Боб посылает Алисе a и b. (4) Алиса проверяет, что c = T Tma g b mod p. Она посылает k Бобу. (5) Боб проверяет, что h 1 = T Tma g b+k mod p, и что h 2 = y ra r sa u b+k mod p. Алиса может преобразовать все свои неотрицаемые подписи в обычные, опубликовав z. Теперь любой мо- жет проверить ее подпись без ее помощи. Схемы неотрицаемых подписей можно объединить со схемами разделения секрета, создав распределенные преобразуемые неотрицаемые подписи [1235]. Кто-нибудь может подписать сообщение, а затем распределить возможность подтверждения правильности подписи . Он может, например, потребовать, чтобы в протоколе убе- ждения Боба в правильности подписи участвовали трое из пяти обладателей возможность подтверждения пр а- вильности. В [700, 1369] предложены улучшения, позволяющие отказаться от необходимости доверенного лица - распределителя. 23.5 Подписи, подтверждаемые доверенным лицом Вот как Алиса может подписать сообщение, а Боб проверить его так , чтобы и Кэрол немного позже могла доказать Дэйву правильность подписи Алисы (см. раздел 4.4) [333]. Сначала опубликовываются большое простое число p и примитивный элемент g, которые будут совместно использоваться группой пользователей. Также опубликовывается n, произведение двух простых чисел. У Кэрол есть закрытый ключ z и открытый ключ h = g x mod p. В этом протоколе Алиса может подписать m так, чтобы Боб мог проверить правильность ее подписи, но не мог убедить в этом третью сторону. (1) Алиса выбирает случайное x и вычисляет a = g x mod p b = h x mod p Она вычисляет хэш-значение m, H(m), и хэш-значение объединения a и b, H(a,b), а затем j = (H(m) ? H(a,b)) 1/3 mod n и посылает a, b и j Бобу. (2) Боб выбирает два случайных числа, s и t, меньших p, и посылает Алисе c = g s h t mod p (3) Алиса выбирает случайное q, меньшее p, и посылает Бобу d = g q mod p e = (cd) x mod p (4) Боб посылает Алисе s и t. (5) Алиса проверяет, что g s h t ? c (mod p) затем она посылает Бобу q. (6) Боб проверяет d ? g q mod p e/a q ? a s b t (mod p) (H(m) ? H(a,b)) = j 1/3 mod n Если все тождества выполняются, то Боб считает подпись истинной . Боб не может использовать запись этого доказательства для убеждения Дэйва в истинности подписи , но Дэйв может выполнить протокол с доверенным лицом Алисы, Кэрол. Вот как Кэрол убеждает Дэйва в том, что a и b образуют правильную подпись. (1) Дэйв выбирает случайные u и v, меньшие p, и посылает Кэрол k = g u a v mod p (2) Кэрол выбирает случайное w, , меньшее p, и посылает Дэйву l = g w mod p y = (kl) z mod p (3) Дэйв посылает Кэрол u и v. (4) Кэрол проверяет, что g K = v ? k (mod p) Затем она посылает Дэйву w. (5) Дэйв проверяет, что g w ? l (mod p) y/h w ? h K > v (mod p) Если все тождества выполняются, то Дэйв считает подпись истинной. В другом протоколе Кэрол может преобразовать протокол доверенного лица в обычную цифровую подпись . Подробности в [333]. 23.6 Вычисления с зашифрованными данными Проблема дискретного логарифма Существует большое простое число p и генератор g. Алиса хочет для конкретного x найти такое e, для кото- рого g e ? x (mod p) Это трудная проблема, и Алисе не хватает вычислительных мощностей для вычисления результата . У Боба есть такие возможности - он представляет правительство, или мощный вычислительный центр, или еще какую- нибудь влиятельную организацию. Вот как Алиса может получить помощь Боба, не раскрыв ему x [547, 4]: (1) Алиса выбирает случайное число r, меньшее p. (2) Алиса вычисляет x' = xg r mod p (3) Алиса просит Боба решить g e' ? x' (mod p) (4) Боб вычисляет e' и посылает его Алисе. (5) Алиса восстанавливает e, вычисляя e = (e' - r) mod (p - 1) Аналогичные протоколы для проблем квадратичных остатков и примитивных корней приведены в [3, 4]. (См. также раздел 4.8.) 23.7 Бросание "честной" монеты Следующие протоколы позволяют Алисе и Бобу бросать честную монету в сети передачи данных (см. раздел 4.9) [194]. Это пример бросания монеты в колодец (см. раздел 4.10). Сначала только Боб узнает результат бро- ска и сообщает его Алисе. Затем Алиса может проверить, что Боб сообщил правильный результат броска . Бросание "честной" монеты с помощью квадратных корней Подпротокол бросания честной монеты: (1) Алиса выбирает два больших простых числа, p и q, и посылает их произведение n Бобу. (2) Боб выбирает случайное положительное целое число r, меньшее n/2. Боб вычисляет z = r 2 mod n и посылает z Алисе. (3) Алиса вычисляет четыре квадратных корня z (mod n). Она может сделать это, так как она знает разлож е- ние n на множители. Назовем их +x, -x, +y и -y. Обозначим как x' меньшее из следующих двух чисел: x mod n -x mod n Аналогично, обозначим как y' меньшее из следующих двух чисел: y mod n -y mod n Обратите внимание, что r равно либо x', либо y'. (4) Алиса делает пытается угадать, какое из значений равно r - x' или y', и посылает свою догадку Бобу. (5) Если догадка Алисы правильна, результатом броска монеты является "орел", а если неправильна - "решка". Боб объявляет результат броска монеты. Подпротокол проверки: (6) Алиса посылает p и q Бобу. (7) Боб вычисляет x' и y' и посылает их Алисе. (8) Алиса вычисляет r. У Алисы нет возможности узнать r, поэтому она действительно угадывает. Она на этапе (4) сообщает Бобу только один бит своей догадки, не давая Бобу получить и x', и y'. Если Боб получит оба этих числа, он сможет изменить r после этапа (4). Бросание "честной" монеты с помощью возведения в степень по модулю F В этом протоколе в качестве однонаправленной функции используется возведение в степень по модулю пр о- стого числа p [1306]: Подпротокол бросания честной монеты: (1) Алиса выбирает простое число p так, чтобы множители p-1 были известны, и среди них было по крайней мере одно большое простое число. (2) Боб выбирает два примитивных элемента, h и t, в GF(p). Он посылает их Алисе. (3) Алиса убеждается, что h и t являются примитивными элементами, и затем выбирает случайное число x, взаимно простое с p-1. Затем она вычисляет одно из двух значений : y = h x mod p, или y = t x mod p Она посылает y Бобу. (4) Боб пытается угадать, вычислила Алиса y как функцию h или как функцию t, и посылает свое предполо- жение Алисе. (5) Если догадка Боба правильна, результатом бросания монеты является "орел", в противном случае - "решка". Алиса объявляет результат броска монеты. Подпротокол проверки: (6) Алиса раскрывает Бобу значение x. Боб вычисляет h x mod p и t x mod p, убеждаясь, что Алиса играла чест- но и проверяя результат броска. Он также проверяет, что x и p-1 - взаимно простые числа. Чтобы Алиса могла смошенничать, она должна знать два целых числа, x и x', для которых выполняется h x ?t x' mod p. Для того, чтобы узнать эти значения, ей нужно вычислить : log t h =xx -1 mod p-1 и log t h =xx' -1 mod p-1. Это трудные проблемы. Алиса смогла бы сделать это, если бы она знала log t h, но Боб выбирает h и t на этапе (2). У Алисы нет дру- гого способа кроме, как попытаться вычислить дискретный логарифм . Алиса может также попытаться смошен- ничать, выбрав x, которое не является взаимно простым с p-1, но Боб обнаружит это на этапе (6). Боб может смошенничать, если h и t не являются примитивными элементами в поле in GF(p), но Алиса смо- жет легко проверить это после этапа (2), так как ей известно разложение p-1 на простые множители. Удачным в этом протоколе является то, что если Алиса и Боб захотят бросить несколько монет, он7и смогут использовать одни и те же значения p, h и t. Алиса просто генерирует новое x, и протокол продолжается с этапа (3). Бросание "честной" монеты с помощью целых чисел Блюма В протоколе бросания монеты можно использовать челые числа Блюма . (1) Алиса генерирует целое число Блюма n, случайное x, взаимно простое с n, x 0 = x 2 mod n и x 1 = x 0 2 mod n. Она посылает Бобу n и x 1 (2) Боб угадывает, четным или нечетным является x 0 (3) Алиса посылает x Бобу. (4) Боб проверяет, что n является целым числом Блюма (Алиса нужно передать Бобу множители n и доказа- тельства того, что они являются простыми , или выполнить некоторый протокол с нулевым знанием, убе ж- дающий Боба, что n - это целое число Блюма), и что x 0 = x 2 mod n и x 1 = x 0 2 mod n. Если все проверки вы- полняются, и Боб угадал правильно, он выигрывает бросок . Это важно, чтобы n было числом Блюма. Иначе Алиса сможет найти такое x' 0 , что x' 0 2 mod n = x 0 2 mod n=x 1 , где x' 0 также является квадратичным остатком. Если бы x 0 был четным, а x' 0 - нечетным (или наоборот), Алиса могла бы мошенничать. 23.8 Однонаправленные сумматоры Существует простая функция однонаправленного сумматоры [116] (см. раздел 4.12.): A(x i , y) = x i-1 y mod n Числа n (являющееся произведением двух простых чисел ) и x 0 должны быть заранее согласованы. Тогда суммированием y 1 , y 2 и y 3 будет (( mod ) mod ) mod x n n n y y y q 0 2 3 Это вычисление не зависит от порядка y 1 , y 2 и y 3 23.9 Раскрытие секретов "все или ничего" Этот протокол позволяет нескольким сторонам (для работы протокола нужно не меньше двух участников ) покупать различные секреты у одного продавца (см. раздел 4.13) [1374, 1175]. Начнем с определения. Возьмем две строки битов, x и y. Фиксированным битовым индексом (fixed bit index, FBI) x и y называется последова- тельность номеров совпадающих битов этих строк. Например: x = 110101001011 y = 101010000110 FBI(x, y) = {1, 4, 5, 11} (Мы читаем биты справа налево, считая нулевым крайний правый бит .) Теперь вот как выглядит протокол. Алиса будет продавцом. Боб и Кэрол - покупателями. У Алисы есть k n- битовых секретов: S 1 , S 2 , . . . S k . Боб хочет купить секрет S b , Кэрол - секрет S c (1) Алиса генерирует пару "открытый ключ/закрытый ключ"и сообщает Бобу (но не Кэрол) открытый ключ. Она генерирует другую пару "открытый ключ/закрытый ключ"и сообщает Кэрол (но не Бобу) открытый ключ. (2) Боб генерирует k n-битовых случайных чисел, B 1 , B 2 , . . . B k , и сообщает их Кэрол. Кэрол генерирует k n- битовых случайных чисел, C 1 , C 2 , . . . C k , и сообщает их Бобу. (3) Боб шифрует C b (напомним, он хочет купить секрет S b ) открытым ключом, полученным от Алисы . Он вы- числяет FBI для C b и только что зашифрованного результата. Он посылает этот FBI Кэрол. |