Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С

• Название: Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
• Дата: 29.04.2022
• Размер: 3.25 Mb.
• Имя файла: Shnayer_Prikladnaya-kriptografiya.352928.pdf
• Тип: Протокол; #504484
• страница: 53 из 78

Кэрол шифрует B
c
(напомним, она хочет купить секрет S
c
) открытым ключом, полученным от Алисы . Она вычисляет FBI для B
c и только что зашифрованного результата. Она посылает этот FBI Бобу.
(4) Боб берет каждое из n-битовых чисел B
1
, B
2
, . . . B
k и заменяет каждый бит, номера которого нет в FBI,
полученном от Кэрол, его дополнением. Он посылает этот новый список n-битовых чисел B'
1
, B'
2
, . . . B'
k

Алисе.
Кэрол берет каждое из n-битовых чисел C
1
, C
2
, . . . C
k и заменяет каждый бит, номера которого нет в FBI,
полученном от Боба, его дополнением. Она посылает этот новый список n-битовых чисел C'
1
, C'
2
, . . . C'
k
Алисе.
(5) Алиса расшифровывает все C'
i закрытым ключом Боба, получая k n-битовых чисел C"
1
, C"
2
, . . . C"
k
. Она вычисляет S
i
? C"
i для i = 1, . . . k, и посылает результаты Бобу.
Алиса расшифровывает все B'
i закрытым ключом Кэрол, получая k n-битовых чисел B"
1
, B"
2
, . . . B"
k
. Она вычисляет S
i
? B"
i для i = 1, . . . k, и посылает результаты Кэрол.
(6) Боб вычисляет S
b
, выполняя XOR C
b и b-го числа, полученного от Алисы.
Кэрол вычисляет S
c
, выполняя XOR B
c и c-го числа, полученного от Алисы..
Все так сложно. Поясним эти долгие действия на примере .
У Алисы есть для продажи восемь 12-битовых секретов : S
1
= 1990, S
2
= 471, S
3
= 3860, S
4
= 1487, S
5
= 2235,
S
6
= 3751, S
7
= 2546 и S
8
= 4043. Боб хочет купить S
7
, а Кэрол - S
2
(1) Алиса использует алгоритм RSA. В диалоге с Бобом она использует следующую пару ключей : n = 7387, e
= 5145 и d = 777, а в диалоге с Кэрол - n = 2747, e = 1421 и d = 2261. Она сообщает Бобу и Кэрол их от- крытые ключи.
(2) Боб генерирует восемь 12-битовых чисел, B
1
= 743, B
2
= 1988, B
3
= 4001, B
4
= 2942, B
5
= 3421, B
6
= 2210,
B
7
=2306 и B
8
= 222, и сообщает их Кэрол. Кэрол генерирует восемь 12-битовых чисел, C
1
= 1708, C
2
= 711,
C
3
= 1969, C
4
= 3112, C
5
= 4014, C
6
= 2308, C
7
= 2212 и C
8
= 222, и сообщает их Бобу.
(3) Боб хочет купить S
7
, поэтому он открытым ключом, выданным Алисой, шифрует C
7 2212 5145
mod 7387 = 5928
Теперь:
2212 = 0100010100100 5928 = 1011100101000
Следовательно, FBI этих двух чисел равен {0, 1, 4, 5, 6}. Он посылает его Кэрол.
Кэрол хочет купить S
2
, поэтому она открытым ключом, выданным Алисой, шифрует B
2 и вычисляет FBI
B
2 и результата шифрования. Она посылает Бобу {0, 1, 2, 6, 9, 10}.
(4) Боб берет B
1
, B
2
, . . . B
8
и заменяет каждый бит, индекс которого отсутствует в наборе {0, 1, 2, 6, 9, 10} его дополнением. Например:
B
2
= 111111000100 = 1988
B
2
= 011001111100 = 1660
Он посылает B'
1
, B'
2
, . . . B'
8
Алисе.
Кэрол берет C
1
, C
2
, . . . C
8
и заменяет каждый бит, индекс которого отсутствует в наборе {0, 1, 4, 5, 6}его дополнением. Например:
C
7
= 0100010100100 = 2212
C'
7
= 1011100101000 = 5928
Она посылает C'
1
, C'
2
, . . . C'
8
Алисе.
(5) Алиса расшифровывает все C'
i закрытым ключом Боба и выполняет XOR результатов с S
i
. Например, для i = 7:
5928 777
mod 7387 = 2212; 2546 ? 2212 = 342
Она посылает результат Бобу.
Алиса расшифровывает все B'
i закрытым ключом Кэрол и выполняет XOR результатов с S
i
. Например,
для i = 2:
1660 2261
(mod 2747) = 1988; 471 ? 1988 = 1555
Она посылает результат Кэрол.
(6) Боб вычисляет S
7
, выполняя XOR C
7
и седьмого числа, полученного им от Алисы :

2212 ? 342=2546
Кэрол вычисляет S
2
, выполняя XOR B
2
и второго числа, полученного ей от Алисы
1988
?
1555 = 471
Протокол работает для любого количества покупателей . Если Боб, Кэрол и Дэйв хотят купить секреты, Али- са выдает каждому покупателю два открытых ключа, по одному на каждого другого покупателя . Каждый поку- патель получает набор чисел от каждого другого покупателя . Затем они выполняют протокол с Алисой для каж- дого из своих наборов номеров и выполняют XOR всех полученных от Алисы результатов, получая свои секр е- ты. Более подробно это описано в [1374, 1175].
К сожалению, пара нечестных участников могут смошенничать . Алиса и Кэрол, действуя на пару, могут лег- ко понять, какой секрет получил Боб: если они знают FBI C
b и алгоритм шифрования Боба, они могут подыскать такое b, что у C
b будет правильный FBI. А Боб и Кэрол, действуя вместе, могут легко заполучить все секреты
Алисы.
Если вы считаете, что участники честны, можно использовать протокол попроще [389].
(1) Алиса шифрует все секреты RSA и посылает их Бобу:
C
i
= S
i
A
mod n
(2) Боб выбирает свой секрет C
b
, генерирует случайное число r и посылает Алисе.
C' = C
b r
e mod n
(3) Алиса посылает Бобу^
P' = C'
@
mod n
(4) Боб вычисляет P'
S
b
= P'r
-1 mod n
Если участники могут жульничать, Боб может доказать с нулевым знанием, что он знает некоторое r, такое что C' = C
b r
e mod n, и хранить в b секрете, пока Алиса не передаст ему на этапе (3) P' [246).
23.10 Честные и отказоустойчивые криптосистемы
Честная схема Diffie-Hellman
Честные криптосистемы представляют собой программный способ условного вручения документов (см. раз- дел 4.14). Этот пример взят из работ Сильвии Микали ( Silvia Micali) [1084, 1085]. Он запатентован [1086,
1087].
В базовой схеме Diffie-Hellman группа пользователей использует общее простое число p и генератор g. За- крытым ключом Алисы является s, а ее открытым ключом t = g s
mod p. Вот как сделать схему Diffie-Hellman честной (в этом примере используется пять доверенных лиц ).
(1) Алиса выбирает пять целых чисел, s
1
, s
2
, s
3
, s
4
, s
5
, меньших p-1. Закрытым ключом Алисы является s = (s
1
+ s
2
+ s
3
+ s
4
+ s
5
) mod p-1
а ее открытым ключом t = g s
mod p
Алиса также вычисляет t
i
= g s
i mod p, для i = 1, . . . 5.
Открытыми частями Алисы являются t i
, а закрытыми - s i
(2) Алиса посылает закрытую и соответствующую открытую части каждому доверенному лицу . Например,
она посылает s
1
и t
2
доверенному лицу 1. Она посылает t в KDC.
(3) Каждое доверенное лицо проверяет, что t
i
= g s
i mod p
Если это так, доверенное лицо подписывает t i
и посылает его в KDC. Доверенное лицо сохраняет s i
в безо- пасном месте.
(4) Получив все пять открытых частей, KDC проверяет, что

t=(t
1
* t
2
* t
3
* t
4
* t
5
) mod p
Если это так, KDC признает открытый ключ.
В этот момент KDC знает, что у каждого доверенного лица есть правильная часть, и что они при необход и- мости смогут восстановить закрытый ключ . Однако ни KDC, ни любые четыре доверенных лица не могут вос- становить закрытый ключ Алисы.
Работы Микали [1084, 1085] также содержат последовательность действия для создания честного RSA и для объединения пороговой схемы с честной криптосистемой , позволяющей m доверенным лицам из n восстановить закрытый ключ.
Отказоустойчивая схема Diffie-Hellman
Как и в предыдущем протоколе у группы пользователей есть общие простое число p и генератор g. Закры- тым ключом Алисы является s, а ее открытым ключом t = g s
mod p.
(1) KDC выбирает случайное число B из диапазона от 0 до p-2 и вручает B с помощью протокола вручения битов (см. раздел 4.9).
Алиса выбирает случайное число A из диапазона от 0 до p-2. Она посылает KDC g
A
mod p.
(2) Пользователь "разделяет" A с каждым доверенным лицом, используя схему подтверждаемого совместного использования секрета (см. раздел 3.7).
(3) KDC раскрывает B Алисе.
(4) Алиса проверяет вручение этапа (1). Затем она устанавливает свой открытый ключ равным t = g
A
g
B
mod p а закрытый ключ равным s = (A + B) mod (p-1)
Доверенные лица могут восстановить A. Так как KDC знает B, этого достаточно для восстановления s. И
Алиса не сможет использовать никаких подсознательных каналов для передачи несанкционированной инфор- мации. Этот протокол, рассмотренный в [946, 833] в настоящее время патентуется.
23.11 ZERO-KNOWLEDGE PROOFS OF KNOWLEDGE
Доказательство с нулевым знанием для дискретного логарифма
Пегги хочет доказать Виктору, что ей известно x, являющееся решением
A
x
? B (mod p)
где p - простое число, а x - произвольное число, взаимно простое с p-1. Числа A, B и p общедоступны, а x хранится в секрете. Вот как Пегги, не раскрывая значения x, может доказать, что оно ей известно (см. раздел
5.1) [338, 337].
(1) Пегги генерирует t случайных чисел, r l
, r
2
, . . . r t
, причем все r i
меньше p-1.
(2) Пегги вычисляет h i
= A
r i
mod p для всех значений i и посылает их Виктору.
(3) Пегги и Виктор, воспользовавшись протоколом бросания монеты генерируют t битов: b
1
, b
2
, . . . b t.
(4) Для всех t битов Пегги выполняет одну из следующих операций:
a) Если b i
= 0, она посылает Виктору r i
b) Если b i
= 1, она посылает Виктору s i
= (r i
- r j
) mod (p-1), где j - наименьшее значение индекса, при кото- ром b j
= 1
(5) Для всех t битов Виктор проверяет одно из следующих условий :
a) При b i
= 0 что A
r i
? h i
(mod p)
b) При b i
= 1 что A
s i
? h i
h j
-1
(mod p)
(6) Пегги посылает Виктору Z, где
Z = (x - r j
) mod (p-1)
(7) Виктор проверяет, что A
Z
? Bh j
-1
(mod p)

Вероятность удачного мошенничества Пегги равна 1/2
t
Доказательство с нулевым знанием для возможности вскрыть RSA
Алиса знает закрытый ключ Кэрол. Может быть она взломала RSA, а может она взломала дверь квартиры
Кэрол и выкрала ключ. Алиса хочет убедить Боба, что ей известен ключ Кэрол. Однако она не хочет ни сооб- щать Бобу ключ, ни даже расшифровать для Боба одно из сообщений Кэрол . Далее приведен протокол с нуле- вым знанием, с помощью которого Алиса убеждает Боба, что она знает закрытый ключ Кэрол [888]. Пусть от- крытый ключ Кэрол - e, ее закрытый ключ - d, а модуль RSA - n.
(1) Алиса и Боб выбирают случайное k и m, для которых km ? e (mod n)
Числа они должны выбирать случайным образом, используя для генерации k протокол бросания монеты, а затем вычисляя m. Если и k, и m больше 3, протокол продолжается. В противном случае числа выбирают- ся заново.
(2) Алиса и Боб генерируют случайный шифротекст C. И снова они должны воспользоваться протоколом бр о- сания монеты.
(3) Алиса, используя закрытый ключ Кэрол, вычисляет
M = C
d mod n
Затем она вычисляет
X = M
k mod n и посылает X Бобу.
(4) Боб проверяет, что X
m mod n = C. Если это так, то он убеждается в правильности заявления Алисы .
Аналогичный протокол можно использовать для демонстрации возможности вскрытия проблемы дискретн о- го логарифма [888].
Доказательство с нулевым знанием того, что n является числом Блюма
Пока неизвестно никаких действительно практичных доказательств того, что n =pq, где p и q - простые чис- ла, конгруэнтные 3 по модулю 4. Однако если n имеет форму p r
q s
, где r и s нечетны, то у числа n сохраняются свойства, которые делают числа Блюма полезными для криптографии . И тогда существует доказательство с нулевым знанием того, что n имеет такую форму.
Предположим, что Алисе известно разложение на множители числа Блюма n, где n обладает рассмотренной выше формой. Вот как она может доказать Бобу, что n имеет такую форму [660].
(1) Алиса посылает Бобу число u, чей символ Якоби равен -1 по модулю n.
(2) Алиса и Боб совместно выбирают случайные биты: b
1
, b
2
, . . . b k
(3) Алиса и Боб совместно выбирают случайные числа: x
1
, x
2
, . . . x k
(4) Для каждого i = 1, 2, . . . k Алиса посылает Бобу квадратный корень по модулю n для одного из четырех чисел: x i
, -x i
, ux i
, - ux i
. Символ Якоби квадратного корня должен быть равен b i
Вероятность удачного мошенничества
Алисы равна 1/2
k
23.12 Слепые подписи
Понятие слепых подписей (см. раздел 5.3) было придумано Дэвидом Чаумом (David Chaum) [317, 323], ко- торый также предложил и первую реализацию этого понятия [318]. Она использует алгоритм RSA.
У Боба есть открытый ключ e, закрытый ключ d и открытый модуль n. Алиса хочет, чтобы Боб вслепую, не читая, подписал сообщение m.
(1) Алиса выбирает случайное число k из диапазона от 1 до n. Затем она маскирует m, вычисляя t = mk e
mod n
(2) Боб подписывает t t
d
= (mk e
)
d mod n
(3) Алиса снимает маскировку с t d
, вычисляя

s = t d
/k mod n
(4) Результатом является s = m d
mod n
Это можно легко показать t
d
? (mk e
)
d
? m d
k (mod n), поэтому t d
/k = m d
k/k ? m d
(mod n).
Чаум придумал целое семейство более сложных алгоритмов слепой подписи [320, 324], называемых неожи- данными слепыми подписями. Схемы этих подписей сложнее, но они дают больше возможностей .
23.13 Передача с забыванием
В этом протоколе, предложенном Майклом Рабином ( Michael Rabin) [1286], Алиса с вероятностью 50 про- центов удается передать Бобу два простых числа, p и q. Алиса не знает, успешно ли прошла передача (См. раз- дел 5.5.) (Этот протокол можно использовать для передачи Бобу любого сообщения с 50-процентной вероятно- стью успешной передачи, если p и q раскрывают закрытый ключ RSA.)
(1) Алиса посылает Бобу произведение двух простых чисел: n = pq.
(2) Боб выбирает случайное число x, меньшее n и взаимно простое с n. Он посылает Алисе:
a = x
2
mod n
(3) Алиса, зная p и q, вычисляет четыре квадратных корня a: x, n-x, y и n-y. Она случайным образом выбирает любой из этих корней и посылает его Бобу .
(4) Если Боб получает y или n-y, он может вычислит наибольший общий делитель x+y и n, которым будет ли- бо p, либо q. Затем, конечно же, n/p = q. Если Боб получает x или n-x, он не может ничего вычислить.
У этого протокола может быть слабое место : возможна ситуация, когда Боб может вычислить такое число a,
что при известном квадратном корне a он сможет все время раскладывать n на множители.
23.14 Безопасные вычисления с несколькими участниками
Этот протокол взят из [1373]. Алиса знает целое число i, а Боб - целое число j. Алиса и Боб вместе хотят уз- нать, что правильно - i?j или i>j, но ни Алиса, ни Боб не хочет раскрыть свое число партнеру. Этот особый слу- чай безопасных вычислений с несколькими участниками (см. раздел 6.2) иногда называют проблемой мил- лионера Яо [162, 7].
В приводимом примере предполагается, что i и j выбираются из диапазона от 1 до 100. У Боба есть откры- тый и закрытый ключи.
(1) Алиса выбирает большое случайное число x и шифрует его открытым ключом Боба.
c = E
B
(x)
(2) Алиса вычисляет c-j и посылает результат Бобу.
(3) Боб вычисляет следующие 100 чисел:
y u
= D
B
(c-i+u), для 1?u?100
D
B
обозначает дешифрирование закрытым ключом Боба.
Он выбирает большое случайное число p. (Размер p должен быть немного меньше x. Боб не знает x, но
Алиса может легко сообщить ему размер x.) он вычисляет следующие 100 чисел:
z u
= (y u
mod p), для 1?u?100
Далее он проверяет, что для всех u?v
|z u
- z м
| ? 2
и что для всех u
0 < z u
< p-1
Если это не так, то Боб выбирает другое простое число и пробует снова.
(4) Боб посылает Алисе эту последовательность чисел, соблюдая их точный порядок:
z l
, z
2
, . . . z j
, z j+1
+1, z j+2
+1, . . . z
100
+1, p

(5) Алиса проверяет, конгруэнтен ли i-ый член последовательности x mod p. Если это так, она делает вывод,
что i?j. В противном случае она решает, что i> j.
(6) Алиса сообщает Бобу свои выводы.
Проверка, которую Боб выполняет на этапе (3), должна гарантировать, что ни одно число не появится два ж- ды в последовательности, генерированной на этапе (4). В противном случае, если z a
= z b
, Алиса узнает, что a ? j
< b.
Недостатком этого протокола является то, что Алиса узнает результаты вычислений раньше Боба . Ничто не помешает ей завершить протокол на этапе (5), отказавшись сообщать Бобу результаты. Она даже может солгать
Бобу на этапе (6).
Пример протокола
Пусть они используют RSA. Открытым ключом Боба является 7, а закрытым - 23. n = 55. Секретное число
Алисы, i, равно 4, секретное число Боба, j - 2. (Предположим, что числа i и j могут принимать только значения
1, 2, 3 и 4.)
(1) Алиса выбирает x = 39 и c = E
B
(39) = 19.
(2) Алиса вычисляет c-i=19-4=15. Она посылает 15 Бобу.
(3) Боб вычисляет следующие четыре числа:
y
1
= D
B
{15+l) =26
y
2
= D
B
{15+2) = 18
y
3
= D
B
{15+3) =2
y
4
= D
B
{15+4) = 39
Он выбирает p = 31 и вычисляет:
z
1
= (26 mod 31) = 26
z
2
= (18 mod 31) =18
z
3
= (2 mod 31) = 2
z
4
= (39 mod 31) = 8
Он выполняет все проверки и убеждается, что последовательность правильна .
(4) Боб посылает Алисе эту последовательность чисел, соблюдая их порядок :
26, 18, 2+1, 8+1, 31, т.е., 26, 18, 3, 9, 31
(5) Алиса проверяет, конгруэнтно ли четвертое число X mod p. Так как 9 ? 39 (mod 31 ), то i > j.
(6) Алиса сообщает об этом Бобу.
Этот протокол можно использовать для создания намного более сложных протоколов . Группа людей может проводить секретный аукцион по сети. Они логически упорядочивают себя по кругу и, с помощью попарных сравнений, определяют, кто предложил большую цену . Чтобы помешать людям уже изменять сделанные пред- ложения в середине аукциона должен использоваться какой-то протокол вручения битов. Если аукцион прово- дится по голландской системе, то предложивший наивысшую цену получает предмет за предложенную цену .
Если аукцион проводится по английской системе, то он получает предмет за вторую высшую цену. (Это может быть выяснено во время второго круга попарных сравнений .) Аналогичные идеи применимы при заключении сделок, переговорах и арбитраже.