Алгоритм Чаума. Сначала опубликовывается большое простое число р и примитивный элемент g, которые будут совместно использоваться группой подписывающих.
У Отправителя есть закрытый ключ х и открытый ключ gх mod p. Чтобы подписать сообщение, Отправитель вычисляет z тх mod p. Это все, что ему нужно сделать. Проверка подписи немного сложнее. 1 Получатель выбирает два случайных числа, a и b, меньшие p, и отправляет Отправителю c zagхb mod p 2 Отправитель вычисляет t x-1mod p-1, и отправляет Получателю d ct mod p. 3 Получатель проверяет, что d тagb mod p Если это так, он считает подпись истинной. 1 П р и м е р Для простоты вычисления используем небольшие числа.
Пусть р23, g5. Заметим, что g5 действительно примитивный корень, т.к. по теореме 2 с цp22 q12, q211 52 mod 2321 511 mod 23221 Закрытый ключ выбираем х7. Пусть т3. Открытый ключ 57mod 2317 Чтобы подписать сообщение, Отправитель вычисляет z тх mod p 37 mod 232. Проверка подписи Получателем 1 Получатель выбирает два случайных числа, a4 и b2, и отправляет Отправителю c zagхb mod p 24572 mod 231 2 Отправитель вычисляет t 7-1mod 223, и отправляет Получателю d ct mod p13 mod 231. 3 Получатель проверяет, что d3452 mod 231. Поскольку d совпадает с тagb, то подпись Получатель считает истинной.
Представим, что Отправитель и Получатель выполнили этот протокол, и Получатель теперь считает, что Отправитель подписал сообщение. Получатель хочет убедить в этом Участника 3, поэтому он показывает ему запись протокола. Сначала он генерирует сообщение на этапе 1. Затем на этапе 3 он генерирует d и ложную передачу от другого человека на этапе 2. Наконец, он создает сообщение этапа 2. Для Участника 3 записи Получателя и Участника 4 одинаковы.
Его невозможно убедить в правильности подписи, пока он не выполнит протокол самостоятельно. Конечно, если бы Отправитель следил из-за плеча Получателя за тем, как он выполняет протокол, он был бы убежден. Участнику 3 нужно увидеть выполнение этапов по порядку, так, как это делал Получатель.
Другой протокол включает не только протокол подтверждение Отправитель может убедить Получателя в правильности своей подписи но и протокол отрицания. Отправитель может с помощью интерактивного протокола с нулевым значением убедить Получателя, что его подпись неправильна, если это так. Как и предыдущий протокол група подписывающих использует общедоступное большое простое число p и примитивный элемент g.2 У Отправителя есть закрытый х и открытый ключ gх mod p. Чтобы подписать, сообщение Отправитель вычисляет z тх mod p. Чтобы проверить подпись 1 Получатель выбирает два случайных числа, a и b, меньшие p, и отправляет Отправителю c тagb mod p 2 Отправитель выбирает случайное число q, меньшее p, а затем вычисляет и отправляет Получателю s1 cgq mod p, s2 cgqx mod p 3 Получатель посылает Отправителю a и b, чтобы Отправитель мог убедиться, что Получатель не мошенничал на этапе 1. 4 Отправитель посылает Получателю q, чтобы он мог воспользоваться тх и восстановить s1 и s2. Если s1 cgq mod p, s2 cgхbq mod p, то подпись правильна. Отправитель может также отказаться от подписи z под сообщением m. П р и м е р Для простоты вычисления используем небольшие числа.
Пусть р29, g3. Заметим, что g3 действительно примитивный корень, т.к. по теореме 2 с цp28 q12, q27 314 mod 29281 3 4mod 29231 Закрытый ключ выбираем х3. Пусть т4. Открытый ключ 33mod 296 Чтобы подписать сообщение, Отправитель вычисляет z тх mod p 43 mod 296. Чтобы проверить подпись 1 Получатель выбирает два случайных числа, a10 и b16, и отправляет Отправителю c тagb mod p 410316 mod 2925. 2 Отправитель выбирает случайное число q2, а затем вычисляет и отправляет Получателю s1 cgq mod p2532mod 2922, s2 cgqx mod p 25323 mod 295. 3 Получатель посылает Отправителю a и b, чтобы Отправитель мог убедиться, что Получатель не мошенничал на этапе 1. 4 Отправитель вычисляет cgq, получает s1. gхbqza331626105mod 29. Действительно, s25mod 29. Подпись правильна. 4.2 Преобразуемые неоспоримые подписи.
Сначала выбираются два простых числа, p и q так чтобы q было делителем p-1. Теперь нужно создать число g, меньшее q. В диапазоне от 2 до p-1 выбирается случайное число h и вычисляется ghp-1q mod p. Если g1, выбирается другое случайное число h. Если нет, используется полученное значение g. Закрытыми ключами служат два различных случайных числа, x и z, меньшие q. Открытыми ключами являются p, q, g, y и u, где y g х mod p, u g z mod p. Для вычисления преобразуемой неотрицательной подписи сообщения т которое в действительности является хэш-значением сообщения, сначала в диапазоне от 1 до q-1 выбирается случайное число t. Затем вычисляется Т g r mod p и тTtzm mod q. Теперь вычисляется обычная подпись ElGamal для т. Выбирается случайное число R, меньшее р-1 и взаимно простое с ним. Затем вычисляется r g R mod p и, с помошью расширенного алгоритма Эвклида, вычисляется s, для которого тrxRsmod q. Подписью служат подпись ElGamal r, s и Т. Вот как Отправитель подтверждает свою подпись Получателю 1 Получатель генерирует два случайных числа, а и b, и вычисляет c T Tma g b mod p и посылает результат Отправителю. 2 Отправитель генерирует случайное число к и вычисляет h1 cgk mod p и h2 h1z mod p, а затем посылает оба числа Получателю . 3 Получатель посылает Отправителю a и b. 4 Отправитель проверяет, что c T Tma g b mod p. Он посылает к Получателю. 5 Получатель проверяет, что c T Tma g bк mod p, и что h2 y ra rsa u bk mod p. 1 Отправитель может преобразовать все свои неоспоримые подписи в обычные, опубликовав z. Теперь любой может проверить его подпись без его помощи.
Схемы неоспоримых подписей можно объединить со схемами разделения секрета, создав распределенные преобразуемые неоспоримые подписи.
Кто нибудь может подписать сообщение, а затем распределить возможность подтверждения правильности подписи.
Он может, например, потребовать, чтобы в протоколе убеждения Получателя в правильности подписи участвовали трое из пяти обладателей возможность подтверждения правильности. 4.3 Подписи, подтверждаемые доверенным лицом. Сначала опубликовываются большое простое число р и примитивный элемент g, которые будут совместно использоваться группой пользователей.
Также опубликовывается п, произведение двух простых чисел.
У Участника 3 есть закрытый ключ z и открытый ключ hgхmod p. В этом протоколе Отправитель может подписать т так, чтобы Получатель мог проверить правильность его подписи, но не мог убедить в этом третью сторону. 1 Отправитель выбирает случайное число х и вычисляет аgх mod p, bhх mod p. Он вычисляет хэш- значение т, Нт, и хэш-значение объединения a и b, На, b jНт Нa, b13 mod n и посылает a, b и j Получателю. 2 Получатель выбирает два случайных числа, s и t, меньших р, и посылает Отправителю с gs ht mod p. 3 Отправитель выбирает случайное q, меньшее p, и посылает Получателю dgq mod p, e cdх mod p 4 Получатель посылает Отправителю s и t. 5 Отправитель проверяет, что gs ht стod p затем он посылает Получателю q. 6 Получатель проверяет dgq mod p, е аqas btтod p, Нт Нa, b j 13 mod n Если все тождества выполняются, то Получатель считает подпись истиной. 10 Получатель не может использовать запись этого доказательства для убеждения Участника 4 в истиности подписи, но Участник 4 может выполнить протокол с доверенным лицом Отправителя, Участник 3. Вот как Участник 3 убеждает Участника 4 в том, что a и b образуют правильную подпись. 1 Участник 4 выбирает случайные u v k gu av mod p 2 Участник 3 выбирает случайное w, меньшее р, и посылает Участнику 4 l gw mod p, y kl z mod p 3 Участник 4 посылает Участнику 3 u и v. 4 Участник 3 проверяет, что gu av kтod p. Затем она посылает Участнику 4 w. 5 Участник 4 проверяет, что gw lmod p, yhwhu bvтod p. Если все тождества выполняются, то Участник 4 считает подпись истинной. 11 4.4