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

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

Слухи об этом стали распространяться в научном сообществе и прессе . В течение двух дней секретное рас- поряжение было аннулировано. Шамир и его коллеги считают, что за отменой секретного распоряжения стояло
NSA, хотя никаких официальных комментариев не было . Дальнейшие подробности этой причудливой истории приведены в [936].
Упрощенная схема идентификации Feige-Fiat-Shamir
Перед выдачей любых закрытых ключей арбитр выбирает случайный модуль , n, который является произве- дением двух больших простых чисел. В реальной жизни длина n должна быть не меньше 512 битов и лучше как можно ближе к 1024 битам. n может общим для группы контролеров. (Использование чисел Блюма (Blum) об- легчит вычисления, но не является обязательным для безопасности .)
Для генерации открытого и закрытого ключей Пегги доверенный арбитр выбирает число v, являющееся квадратичным остатком mod n. Другими словами выбирается v так, чтобы уравнение x
2
? v (mod n) имело ре- шение, и существовало v
-1
mod n. Это v и будет открытым ключом Пегги. Затем вычисляется наименьшее s, для которого s ? sqrt (v
-1
) (mod n). Это будет закрытый ключ Пегги. Используется следующий протокол идентиф и- кации.
(1) Пегги выбирает случайное r, меньшее n. Затем она вычисляет x =-r
2
mod n и посылает x Виктору.
(2) Виктор посылает Пегги случайный бит b.
(3) Если b = 0, то Пегги посылает Виктору r. Если b = 1, то Пегги посылает Виктору y = r*s mod n.
(4) Если b = 0, Виктор проверяет, что x = -r
2
mod n, убеждаясь, что Пегги знает значение sqrt(x). Если b = 1,
Виктор проверяет, что x = y
2
*v mod n, убеждаясь, что Пегги знает значение sqrt(v
-1
).
Это один этап протокола, называемый аккредитацией. Пегги и Виктор повторяют этот протокол t раз, пока
Виктор не убедится, что Пегги знает s. Это протокол "разрезать и выбрать". Если Пегги не знает s, она может подобрать r так, что она сможет обмануть Виктора, если он пошлет ей 0, или она может подобрать r так, что она сможет обмануть Виктора, если он пошлет ей 1 . Она не может сделать одновременно и то, и другое. Вероят- ность, что ей удастся обмануть Виктора один раз, равна 50 процентам . Вероятность, что ей удастся обмануть его t раз, равна 1/2
t
Виктор может попробовать вскрыть протокол, выдавая себя за Пегги . Он может начать выполнение прото- кола с с другим контролером, Валерией. На шаге (1) вместо выбора случайного r ему останется просто исполь- зовать значение r, которое Пегги использовало в прошлый раз . Однако, вероятность того, что Валерия на шаге
(2) выберет то же значение b, которое Виктор использовал в протоколе с Пегги, равна 1/2 . Следовательно, веро- ятность, что он обманет Валерию, равна 50 процентам . Вероятность, что ему удастся обмануть ее t раз, равна
1/2
t

Чтобы этот протокол работал, Пегги никогда не должна использовать r повторно. В противном случае, если
Виктор на шаге (2) пошлет Пегги другой случайный бит, то он получит оба ответа Пегги . Тогда даже по одному из них он сможет вычислить s, и для Пегги все закончится.
Схема идентификации Feige-Fiat-Shamir
В своих работах [544, 545], Фейге, Фиат и Шамир показали, как параллельная схема может повысить число аккредитаций на этап и уменьшить взаимодействия Пегги и Виктора .
Сначала, как и в предыдущем примере, генерируется n, произведение двух больших простых чисел . Для ге- нерации открытого и закрытого ключей Пегги сначала выбирается k различных чисел: v
1
, v
2
, . . . v k
, где каждое v
i является квадратичным остатком mod n. Иными словами, v i
выбираются так, чтобы x
2
? v i
(mod n) имело ре- шение, и существовало v i
-1
mod n. Строка, v
1
, v
2
, . . . v k
, служит открытым ключом. Затем вычисляются наи- меньшие s i
, для которых s i
? sqrt (v i
-1
) (mod n). Строка s
1
, s
2
, . . . s k
, служит закрытым ключом.
Выполняется следующий протокол:
(1) Пегги выбирает случайное r, меньшее n. Затем она вычисляет x =-r
2
mod n и посылает x Виктору.
(2) Виктор посылает Пегги строку из k случайных битов: b
1
, b
2
, . . . b k
(3) Пегги вычисляет y = r *( s s
s b
b k
b k
1 2
1 2
*
* *
K
)mod n. (Она перемножает вместе значения s i
, соответствующие b
i
=1. Если первым битом Виктора будет 1, то s
1
войдет в произведение, а если первым битом будет 0, то нет, и т.д.) Она посылает y Виктору.
(4) Виктор проверяет, что x = y
2
*( v v
v b
b k
b k
1 2
1 2
*
* *
K
) mod n. (Он перемножает вместе значения v i
, основываясь га случайной двоичной строке. Если его первым битом является 1, то v
1
войдет в произведение, а если первым битом будет 0, то нет, и т.д.)
Пегги и Виктор повторяют этот протокол t раз, пока Виктор не убедится, что Пегги знает s
1
, s
2
, . . . s k
Вероятность, что Пегги удастся обмануть Виктор t раз, равна 1/2
kt
. Авторы рекомендуют использовать веро- ятность мошенничества 1/2 20
и предлагают значения k = 5 и t = 4. Если у вас склонность к мании преследов а- ния, увеличьте эти значения.
Пример
Взглянем на работу этого протокола небольших числах . Если n = 35 (два простых числа - 5 и 7), то возмож- ными квадратичными остатками являются :
1: x
2
? 1 (mod 35) имеет решения: x = 1, 6, 29, 34.
4: x
2
? 4 (mod 35) имеет решения: x = 2, 12, 23, 33.
9: x
2
? 9 (mod 35) имеет решения: x = 3, 17, 18, 32.
11: x
2
? 11 (mod 35) имеет решения: x = 9, 16, 19, 26.
14: x
2
? 14 (mod 35) имеет решения: x = 7, 28.
15: x
2
? 15 (mod 35) имеет решения: x = 15, 20.
16: x
2
? 16 (mod 35) имеет решения: x = 4, 11, 24, 31.
21: x
2
? 21 (mod 35) имеет решения: x = 14, 21.
25: x
2
? 25 (mod 35) имеет решения: x = 5, 30.
29: x
2
? 29 (mod 35) имеет решения: x = 8, 13, 22, 27.
30: x
2
? 30 (mod 35) имеет решения: x = 10, 25.
Обратными значениями (mod 35) и их квадратными корнями являются:
v v
-1
s=sqrt(v
-1
)
1 1
1 4
9 3
9 4
2 11 16 4

16 11 9
29 29 8
Обратите внимание, что у чисел 14, 15, 21, 25 и 30 нет обратных значений mod 35, так как они не взаимно просты с 35. Это имеет смысл, так как должно быть (5 - 1) * (7 - 1)/4 квадратичных остатков mod 35, взаимно простых с 35: НОД(x, 35) = 1 (см. раздел 11.3).
Итак, Пегги получает открытый ключ, состоящий из k = 4 значений: {4,11,16,29}. Соответствующим закры- тым ключом является {3,4,9,8}. Вот один этап протокола.
(1) Пегги выбирает случайное r=16, вычисляет 16 2
mod 35 = 11 и посылает его Виктору.
(2) Виктор посылает Пегги строку случайных битов: {1, 1, 0, 1}
(3) Пегги вычисляет 16*(3 1
*4 1
*9 0
*8 1
) mod 35 = 31 и посылает его Виктору.
(4) Виктор проверяет, что 31 2
*(4 1
*11 1
*16 0
*29 1
) mod 35 =11.
Пегги и Виктор повторяют этот протокол t раз, каждый раз с новым случайным r, пока Виктор будет убеж- ден.
Небольшие числа, подобные использованным в примере, не обеспечивают реальной безопасности . Но когда длина n равна 512 и более битам, Виктор не сможет узнать о закрытом ключе Пегги ничего кроме того факта,
что Пегги действительно знает его.
Улучшения
В протокол можно встроить идентификационные данные . Пусть I - это двоичная строка, представляющая идентификатор Пегги: имя, адрес, номер социального страхования, размер головного убора, любимый сорт про- хладительного напитка и другая личная информация . Используем однонаправленную хэш-функцию H(x) для вычисления H(I,j), где j - небольшое число, добавленное к I. Найдем набор j, для которых H(I,j) - это квадратич- ный остаток по модулю n. Эти значения H(I,j) становятся v
1
, v
2
, . . . v k
(j не обязаны быть квадратичными остат- ками). Теперь открытым ключом Пегги служит I и перечень j. Пегги посылает I и перечень j Виктору перед ша- гом (1) протокола (или Виктор загружает эти значения с какой-то открытой доски объявлений ), И Виктор гене- рирует v
1
, v
2
, . . . v k
из H(I,j).
Теперь, после того, как Виктор успешно завершит протокол с Пегги, он будет убежден, что Трент, которому известно разложение модуля на множители, сертифицировал связь между I и Пегги, выдав ей квадратные корни из v i
, полученные из I. (См. раздел 5.2.) Фейге, Фиат и Шамир добавили следующие замечания [544, 545]:
Для неидеальных хэш-функций можно посоветовать рандомизировать I, добавляя к нему длинную случайную строку R.
Эта строка выбирается арбитром и открывается Виктору вместе с I.
В типичных реализациях k должно быть от 1 до 18. Большие значения k могут уменьшить время и трудности связи,
уменьшая количество этапов.
Длина n должна быть не меньше 512 битов. (Конечно, с тех пор разложение на множители заметно продвинулось .)
Если каждый пользователь выберет свое собственное n и опубликует его в файле открытых ключей, то можно обойтись и без арбитра. Однако такой RSA-подобный вариант делает схему заметно менее удобной .
Схема подписи Fiat-Shamir
Превращение этой схемы идентификации в схему подписи - это, по сути, вопрос превращения Виктора в хэш-функциию. Главным преимуществом схемы цифровой подписи Fiat-Shamir по сравнению с RSA является ее скорость: для Fiat-Shamir нужно всего лишь от 1 до 4 процентов модульных умножений, используемых в
RSA. В этом протоколе снова вернемся к Алисе и Бобу .
Смысл переменных - такой же, как и в схеме идентификации . Выбирается n - произведение двух больших простых чисел. Генерируется открытый ключ, v
1
, v
2
, . . . v k
, и закрытый ключ, s
1
, s
2
, . . . s k
, где s i
? sqrt (v i
-1
) (mod n).
(1) Алиса выбирает t случайных целых чисел в диапазоне от 1 до n - r
1
, r
2
, . . ., r t
- и вычисляет x
1
, x
2
, . . . x t
,
такие что x i
= r i
2
mod n.
(2) Алиса хэширует объединение сообщения и строки x i
, создавая битовый поток: H(m, x
1
, x
2
, . . . x t
). Она ис- пользует первые k*t битов этой строки в качестве значений b ij
, где i пробегает от1 до t, а j от 1 до k.
(3) Алиса вычисляет y
1
, y
2
, . . . y t
,, где y i
= r i
*( s s
s b
b k
b i
i ik
1 2
1 2
*
* *
K
) mod n
(Для каждого i она перемножает вместе значения s i
, в зависимости от случайных значений b ij
. Если b ij
=1,
то s i
участвует в вычислениях, если b ij
=0, то нет.)
(4) Алиса посылает Бобу m, все биты b ij
, и все значения y i
. У Боба уже есть открытый ключ Алисы: v
1
, v
2
, . . .
v k

(5) Боб вычисляет z
1
, z
2
, . . . z t
, где z i
= y
2
*( v v
v b
b k
b i
i ik
1 2
1 2
*
* *
K
) mod n
(И снова Боб выполняет умножение в зависимости от значений b ij
.) Также обратите внимание, что z i
должно быть равно x i
(6) Боб проверяет, что первые k*t битов H(m, z
1
, z
2
, . . . z t
) - это значения b ij
, которые прислала ему Алиса.
Как и в схеме идентификации безопасность схемы подписи пропорциональна l/2
kt
. Она также зависит от сложности разложения n на множители. Фиат и Шамир показали, что подделка подписи облегчается, если сложность разложения n на множители заметно меньше 2
kt
. Кроме того, из-за вскрытия методом дня рождения
(см. раздел 18.1), они рекомендуют повысить k*t от 20 по крайней мере до 72, предлагая k = 9 и t = 8.
Улучшенная схема подписи Fiat-Shamir
Сильвия Микали (Silvia Micali) и Ади Шамир улучшили протокол Fiat-Shamir [1088]. Они выбирали v
1
, v
2
,
. . . v k
так, чтобы они были первыми k простыми числами. То есть v
1
= 1, v
2
= 3, v
3
= 5, и т.д.
Это открытый ключ. Закрытым ключом, s
1
, s
2
, . . . s k
, служат случайные квадратные корни, определяемые как s
i
= sqrt (v i
-1
) (mod n)
В этой версии у каждого участника должен быть свой n. Такая модификация облегчает проверку подписей ,
не влияя на время генерации подписей и их безопасность.
Другие улучшения
На основе алгоритма Fiat-Shamir существует и N-сторонняя схема идентификации [264]. Два других улуч- шения схемы Fiat-Shamir в [1218]. Еще один вариант - в [1368].
Схема идентификации Ohta-Okamoto
Этот протокол является вариантом схемы идентификации Feige-Fiat-Shamir, его безопасность основана на трудности разложения на множители [1198, 1199]. Эти же авторы разработали схему с несколькими подписями
(см. раздел 23.1), с помощью которой различные люди могут последовательно подписывать [1200]. Эта схема была предложена для реализации на интеллектуальных карточках [850].
Патенты
Fiat-Shamir запатентован [1427]. При желании получить лицензию на алгоритм свяжитесь с Yeda Research and Development, The Weizmann Institute of Science, Rehovot 76100, Israel.
21.2 GUILLOU-QUISQUATER
Feige-Fiat-Shamir был первым практическим протоколом идентификации . Он минимизировал вычисления,
увеличивая число итераций и аккредитаций на итерацию . Для ряда реализаций, например, для интеллектуал ь- ных карточек, это не слишком подходит. Обмены с внешним миром требуют времени, а хранение данных для каждой аккредитации может быстро исчерпать ограниченные возможности карточки .
Луи Гиллу (Louis Guillou) и Жан-Жак Кискатр (Jean-Jacques Quisquater) разработали алгоритм идентифика- ции с нулевым знанием, который больше подходит для подобных приложений [670, 1280]. Обмены между Пег- ги и Виктором, а также параллельные аккредитации в каждом обмене сведены к абсолютному минимуму : для каждого доказательства существует только один обмен, в котором - только одна аккредитация . Для достижения того же уровня безопасности при использовании схемы Guillou-Quisquater потребуется выполнить в три раза больше вычислений, чем при Feige-Fiat-Shamir. И, как и Feige-Fiat-Shamir, этот алгоритм идентификации мож- но превратить в алгоритм цифровой подписи.
Схема идентификации Guillou-Quisquater
Пегги - это интеллектуальная карточка, которая собирается доказать свою подлинность Виктору . Идентифи- кация Пегги проводится по ряду атрибутов, представляющих собой строку данных содержащих название ка р- точки, период действия, номер банковского счета и другие, подтверждаемые ее применимость, данные . Эта би- товая строка называется J. (В реальности строка атрибутов может быть очень длинной, и в качестве J использу- ется ее хэш-значение. Это усложнение никак не влияет на протокол .) Эта строка аналогична открытому ключу .
Другой открытой информацией, общей для всех "Пегги", которые могут использовать это приложение, является показатель степени v и модуль n, где n - это произведение двух хранящихся в секрете простых чисел . Закрытым

ключом служит B, рассчитываемое так, чтобы JB
v
? 1 (mod n).
Пегги посылает Виктору свои атрибуты J. Теперь она хочет доказать Виктору, что это именно ее атрибуты.
Для этого она должна убедить Виктора, что ей известно B. Вот этот протокол:
(1) Пегги выбирает случайное целое r, находящееся в диапазоне от 1 до n-1. Она вычисляет T = r v
mod n и от- правляет его Виктору.
(2) Виктор выбирает случайное целое d, находящееся в диапазоне от 0 до v-1. Он посылает d Пегги.
(3) Пегги вычисляет D = rB
d mod n и посылает его Виктору.
(4) Виктор вычисляет T = D
v
J
d mod n. Если T ? T' (mod n), то подлинность Пегги доказана.
Математика не слишком сложна:
T = D
v
J
d
= (
rB
d
)
v
J
d
= r
v
B
dv
J
d
= r
v
(
B
v
J
)
d
= r
v
= r'
?T
(mod n
), так как
JB
v
? 1 (mod n)
Схема подписи Guillou-Quisquater
Эту схему идентификации можно превратить в схему подписи, также пригодную для реализации в интелле к- туальных карточках [671, 672]. Открытый и закрытый ключи не меняются . Вот как выглядит протокол:
(1) Алиса выбирает случайное целое r, находящееся в диапазоне от 1 до n-1. Она вычисляет T = r v
mod n.
(2) Алиса вычисляет d = H(M,T), где M - подписываемое сообщение, а H(x) - однонаправленная хэш-функция.
Значение d, полученное с помощью хэш-функции, должно быть в диапазоне от 0 до v-1 [1280]. Если выход хэш-функции выходит за этот диапазон, он должен быть приведен по модулю v.
(3) Алиса вычисляет D = rB
d mod n. Подпись состоит из сообщения M, двух вычисленных значений, d and D,
и ее атрибутов J. Она посылает подпись Бобу.
(4) Боб вычисляет T = D
v
J
d mod n. Затем он вычисляет d' = H(M,T'). Если d ? d', то Алиса знает B, и ее под- пись действительна.
Несколько подписей
Что если несколько человек захотят подписать один и тот же документ ? Проще всего, чтобы они подписали его порознь, но рассматриваемая схема подписи делает это лучше . Пусть Алиса и Боб подписывают документ, а
Кэрол проверяет подписи, но в процесс подписания может быть вовлечено произвольное количество людей . Как и раньше, Алиса и Боб обладают уникальными значениями J и B: (J
A
,B
A
) и (J
B
,B
B
). Значения n и v являются об- щими для всей системы.
(1) Алиса выбирает случайное целое r
А
, находящееся в диапазоне от 1 до n-1. Она вычисляет T
А
= r
А
v mod n и посылает T
А
Бобу.
(2) Боб выбирает случайное целое r
*
, находящееся в диапазоне от 1 до n-1. Он вычисляет T
*
= r
*
v mod n и по- сылает T
*
Алисе.
(3) Алиса и Боб, каждый вычисляет T = (T
А
*T
*
) mod n.
(4) Алиса и Боб, каждый вычисляет d = H(M,T), где M - подписываемое сообщение, а H(x) - однонаправлен- ная хэш-функция. Значение d, полученное с помощью хэш-функции, должно быть в диапазоне от 0 до v-1
[1280]. Если выход хэш-функции выходит за этот диапазон, он должен быть приведен по модулю v.
(5) Алиса вычисляет D
A
= r
A
B
A
d mod n и посылает D
A
Бобу.
(6) Боб вычисляет D
B
= r
B
B
B
d mod n и посылает D
B
Алисе.
(7) Алиса и Боб, каждый вычисляет D = D
A
D
B
mod n. Подпись состоит из сообщения M, двух вычисленных значений, d and D, и атрибутов обоих подписывающих: J
A
и J
B
(8) Кэрол вычисляет J = J
A
J
B
mod n.