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

(1) Алиса выбирает случайное число rA и посылает Тренту rA3 mod n

(2) Трент сообщает Бобу, что кто-то хочет обменяться с ним ключом .

(3) Боб выбирает случайное число rB и посылает Тренту Гд3 mod n

(4) Трент, используя свой закрытый ключ, расшифровывает rA и гд. Он посылает Алисе Га ® Гд

(5) Алиса вычисляет

(Га ® Гд) ® Га = Гд

Она использует гд для безопасного сеанса связи с Бобом.

Протокол выглядит хорошо, но содержит заметный изъян. Кэрол может подслушать этап(3) и использовать эту информацию, воспользовавшись помощью доверчивого Трента и своего сообщника Дэйва, чтобы раскрыть [1472].

(1) Кэрол выбирает случайное число Гс и посылает Тренту гд3 гс3 mod n

(2) Трент сообщает Дэйву, что кто-то хочет обменяться с ним ключом .

(3) Дэйв выбирает случайное число rD и посылает Тренту rD mod n

(4) Трент, используя свой закрытый ключ, расшифровывает rc и rD. Он посылает Кэрол (гд Гс mod n) ® rD

(5) Дэйв посылает rD Кэрол.

(6) Кэрол использует rC и rD для получения гд. Она использует гд для расшифровывания переговоров Алисы и Боба.

Это плохо.

Глава 23

Специальные алгоритмы для протоколов

23.1 Криптография с несколькими открытыми ключами

Это обобщение RSA (см. раздел 19.3) [217, 212]. Модуль n является произведением двух простых чисел p и q. Однако вместо e и d, для которых ed = 1 mod ((p-1)(q-1)), выбирается t ключей K,, для которых выполняется

K1* K2*. . . *Kt = 1 mod ((p-1)(q-1))

Так как

MK1*K2*...*Kt = M

то эта схема оказывается схемой с несколькими ключами, описанная в разделе 3.5.

Если, например, используется пять ключей, то сообщение, зашифрованное ключами K3 и K5, может быть расшифровано с помощью K1, K2 и K4.

C = MK3*K5 mod n

M = cK1*K2*K4 mod n

Одним из применений этой схемы является подписание документа несколькими людьми . Представим ситуацию, когда для того, чтобы документ был действителен, он должен быть подписан и Алисой, и Бобом . Используются три ключа: K1, K2 и K3. Алиса и Боб получают по одному ключу из первых двух, а третий опубликовывается.

(1) Сначала Алиса подписывает M и посылает его Бобу. M = MK1 mod n

(2) Боб может восстановить M по M. M = M K3*K5 mod n

(3) Он может также добавить свою подпись. M = MK2 mod n

(4) Проверить подписи можно при помощи открытого ключа K3. M = M "K3 mod n

Обратите внимание, что для работоспособности этой системы нужна заслуживающая доверия сторона, кот о-рая установила бы систему и выдала ключи Алисе и Бобу . Та же проблема существует и в схеме [484]. Более тонкая схема описана в [695, 830, 700], Но усилия, предпринимаемые для проверки, пропорциональны колич е-ству подписывающих. Новые схемы [220, 1200], основанные на схемах идентификации с нулевым знанием, преодолевают эти недостатки предшествующих си стем.

23.2 Алгоритмы разделения секрета

В разделе 3.7 я рассматривал идею, используемую в схемах разделения секрета. Четыре приведенных ниже различных алгоритма представляют собой частные случаи общего теоретического подхода [883].

Схема интерполяционных многочленов Лагранжа

Для создания пороговой схема Ади Шамир воспользовался уравнениями для многочленов в конечном поле [1414]. Выберем простое число p, которое больше количества возможных теней и больше самого большого из возможных секретов. Чтобы сделать секрет общим, сгенерируем произвольный многочлен степени Например, если нужно создать пороговую схему (3,n) (для восстановления M потребуется три тени), генерируется квадратичный многочлен

(ax2 + bx + M) mod p

где p - это случайное простое число, большее любого из коэффициентов. Коэффициенты a и b выбираются случайным образом, они хранятся в тайне и отбрасываются после того, как распределяются тени . M - это сообщение. Простое число должно быть опубликовано. Тени получаются с помощью вычисления многочлена в n различных точках:

k, =F(x,)

Другими словами, первой тенью может быть значение многочлена при x = 1, второй тенью - значение многочлена при x = 2, и т.д.

Так как в квадратичных многочленах три неизвестных коэффициента, a, b и M, для создания трех уравнений можно использовать любые три цели . Одной или двух теней не хватит, а четырех или пяти теней будет много .

Например, пусть M равно 11. Чтобы создать пороговую схему (3, 5), в которой любые трое из пяти человек могут восстановить M, сначала получим квадратичное уравнение (7 и 8 - случайно выбранные числа chosen randomly):

F(x) = (7x 2 + 5x + 11) mod 13 Пятью тенями являются: k1 = = 7 + 8 + 11= 0 (mod 13) k2 = F(2) = 28 + 16 + 11= 3 (mod 13) k3 = F(3) = 63 + 24 + 11= 7 (mod 13) k4 = F(4) = 112 + 32 + 11= 12 (mod 13) k5 = F(5) = 175 + 40 + 11= 5 (mod 13)

Чтобы восстановить M по трем теням, например, k2, k3 и k5, решается система линейных уравнений: a*22 + b*2 + M = 3 (mod 13) a*32 + b*3 + M = 7 (mod 13) a*52 + b*5 + M = 5 (mod 13)

Решением будут a = 7, b = 8 и M = 11. Итак, M получено.

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

F(x) = ax5 + bx4 + cx3 + dx2 + ex + M (mod ,p)

Шесть человек могут шесть неизвестных (включая M), но пятерым не удастся узнать ничего об M.

Наиболее впечатляющим моментом совместного использования секрета является то, что, если коэффицие н-ты выбраны случайным образом, пять человек даже при помощи бесконечных вычислительных мощностей не смогут узнать ничего, кроме длины сообщения (которая и так им известна) . Это также безопасно, как одноразовый блокнот, попытка выполнить исчерпывающий поиск (то есть, перебор всех возможных шестых теней) покажет, что любое возможное сообщение останется секретным . Это справедливо для всех представленных в этой книге схем разделения секр ета.

Векторная схема

Джордж Блэкли (George Blakley) изобрел схему, использующую понятие точек в пространстве [182]. Сообщение определяется как точка в т-мерном пространстве. Каждая тень - это уравнение (от-1)-мерной гиперплоскости, содержащей эту точку.

Например, если для восстановления сообщения нужны три тени, то оно является точкой в трехмерном пр о-странстве. Каждая тень представляет собой иную плоскость. Зная одну тень, можно утверждать, что точка находится где-то на плоскости. Зная две тени - что она находится где-то на линии пересечения двух плоскостей . Зная три тени, можно точно определить, что точка находится на пересечении трех плоскостей .

Asmuth-Bloom

В этой схеме используются простые числа [65]. Для (т, п)-пороговой схемы выбирается большое простое число p, большее M. Затем выбираются числа, меньшие p - d1, d2, . . . dn, для которых:

1. Значения d,- упорядочены по возрастанию, d,- < d,+1

2. Каждое d, взаимно просто с любым другим d,

3. d1*d2* . . .*d„ > ,p*dn-„+2*dn-„+3*. . .*dn

Чтобы распределить тени, сначала выбирается случайное число r и вычисляется