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

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

Пусть m - открытый текст сообщения. Два ключа шифрования - e
1
и e
2
. Общий модуль - n. Шифротекстами сообщения являются:
c m
n e
1 1
=
mod c
m n
e
2 2
=
mod
Криптоаналитик знает n, e
1
, e
2
, c
1
и c
2
. Вот как он узнает m.
Так как e
1
и e
2
- взаимно простые числа, то с помощью расширенного алгоритма Эвклида r и s, для которых re
1
+ se
2
= 1
Считая r отрицательным (или r, или s должно быть отрицательным, пусть отрицательным будет r), то снова можно воспользоваться расширенным алгоритмом для вычисления c
1
-1
. Затем
(c
1
-1
)
-r
* c
2
s
= m mod n
Существует два других, более тонких вскрытия систем такого типа . Одно использует вероятностный метод для разложения n на множители. Другой - детерминированный алгоритм вычисления какого-нибудь секретного ключа без разложения модуля на множители . Оба вскрытия подробно описаны в [449].
Мораль: Не делайте n общим для группы пользователей.
Вскрытие малого показателя шифрования RSA
Шифрование и проверка подписи RSA выполняется быстрее, если для e используется небольшое значение,
но это также может быть небезопасным [704]. Если e(e + 1)/2 линейно зависящих сообщений с различными о т- крытыми ключами шифруются одним и тем же значением e, существует способ вскрыть такую систему . Если сообщений не так много, или если сообщения не связаны, то проблем нет. Если сообщения одинаковы, то доста- точно e сообщений. Проще всего дополнять сообщения независимыми случайными числами .
Это также гарантирует, что m e
mod n ? m e
. Так делается в большинстве практических реализаций RSA, на- пример, в PEM и PGP (см. разделы 24.10 и 24.12).
Мораль: Дополняйте сообщения перед шифрованием случайными значениями, убедитесь, что размер m примерно равен n.
Вскрытие малого показателя дешифрирования RSA
Другим вскрытием, предложенным Майкл Винер (Michael Wiener), раскрывает d, где d не превышает чет- верти размера n, а e меньше n [1596]. При случайном выборе e и d это встречается редко, и никогда не произой- дет, если значение e мало.
Мораль: Выбирайте большое значение d.
Полученные уроки
Джудит Мур (Judith Moore) на основании перечисленных вскрытий приводит следующие ограничения RSA
[1114, 1115]:
— Знание одной пары показателей шифрования/дешифрирования для данного модуля позволяет взломщику разложить модуль на множители.
— Знание одной пары показателей шифрования/дешифрирования для данного модуля позволяет взломщику вычислить другие пары показателей, не раскладывая модуль на множители.
— В протоколах сетей связи, применяющих RSA, не должен использоваться общий модуль . (Это является быть очевидным следствием предыдущих двух пунктов .)
— Для предотвращения вскрытия малого показателя шифрования сообщения должны быть дополнены сл у- чайными значениями.
— Показатель дешифрирования должен быть большим .
Не забывайте, недостаточно использовать безопасный криптографический алгоритм, должны быть безопа с- ными вся криптосистема и криптографический протокол . Слабое место любого из трех этих компонентов сдел а- ет небезопасной всю систему.

Вскрытие шифрования и подписи с использованием RSA
Имеет смысл подписывать сообщение перед шифрованием (см. раздел 2.7), но на практике никто не выпол- няет этого. Для RSA можно вскрыть протоколы, шифрующие сообщение до его подписания [48].
Алиса хочет послать сообщение Бобу. Сначала она шифрует его открытым ключом Боба, а затем подписы- вает своим закрытым ключом. Ее зашифрованное и подписанное сообщение выглядит так :
m n
n e
B
d
A
B
A
mod ) mod
Вот как Боб может доказать, что Алиса послала ему m', а не m. Так как Бобу известно разложение на множи- тели n
B
(это его собственный модуль), он может вычислить дискретные логарифмы по основанию n
B
. Следова- тельно, ему нужно только найти x, для которого m'
x
= m mod n
B
Тогда, если он может опубликовать xe
B
в качестве своего нового открытого показателя степени и сохранить свой прежний модуль n
B
, он сможет утверждать, что Алиса послала ему сообщение m', зашифрованное этим новым показателем.
В некоторых случаях это особенно неприятное вскрытие . Заметим, что хэш-функции не решают проблему.
Однако она решается при использовании для каждого пользователя фиксированного показ ателя шифрования.
Стандарты
RSA de facto является стандартом почти по всему миру . ISO почти, but not quite, created an RSA digital- signature standard; RSA служит информационным дополнением ISO 9796 [762.]. Французское банковское сооб- щество приняло RSA в качестве стандарта [525], так же поступили и австралийцы [1498]. В Соединенных Шта- тах из-за давления NSA и патентных вопросов в настоящее время нет стандарта для шифрования с открытым ключом. Многие американские компании используют PKCS (см. раздел 24.14), написанный RSA Data Security,
Inc. RSA определен и в качестве чернового банковского стандарта ANSI [61].
Патенты
Алгоритм RSA запатентован в Соединенных Штатах [1330], но ни водной другой стране. PKP получила ли- цензию вместе с другими патентами в области криптографии с открытыми ключами (раздел 25.5). Срок дейст- вия патента США истекает 20 сентября 2000 года.
19.4 Pohlig-Hellman
Схема шифрования Pohlig-Hellman [1253] похожа на RSA. Это не симметричный алгоритм, так как для шифрования и дешифрирования используются различные ключи . Это не схема с открытым ключом, потому что ключи легко получаются один из другого, и ключ шифрования, и ключ дешифрирования должны храниться в секрете. Как и в RSA,
C = P
e mod n
P = C
d mod n где ed є 1 (mod какое-нибудь составное число)
В отличие от RSA n не определяется с помощью двух простых чисел и остается частью закрытого ключа .
Если у кого-нибудь есть e и n, он может вычислить d. Не зная e или d, противник будет вынужден вычислить e = log p
C mod n
Мы уже видели, что это является трудной проблемой .
Патенты
Алгоритм Pohlig-Hellman запатентован в США [722] и в Канаде. PKP получила лицензию вместе с другими патентами в области криптографии с открытыми ключами (см. раздел 25.5).
19.5 Rabin
Безопасность схемы Рабина (Rabin) [1283, 1601] опирается на сложность поиска квадратных корней по мо- дулю составного числа. Эта проблема аналогична разложению на множители . Вот одна из реализаций этой схе- мы.

Сначала выбираются два простых числа p и q, конгруэнтных 3 mod 4. Эти простые числа являются закры- тым ключом, а их произведение n =pq - открытым ключом.
Для шифрования сообщения M (M должно быть меньше n), просто вычисляется
C = M
2
mod n
Дешифрирование сообщения также несложно, но немного скучнее . Так как получатель знает p и q, он может решить две конгруэнтности с помощью китайской теоремы об остатках . Вычисляется m
1
= C
(p+1)/4
mod p m
2
= (p - C
(p+1)/4
) mod p m
3
= C
(q+1)/4
mod q m
4
= (G - C
(q+1)/4
) mod q
Затем выбирается целые числа a = q(q
-1
mod p) и b = p(p
-1
mod q). Четырьмя возможными решениями явля- ются:
M
1
= (am
1
+ bm
3
) mod n
M
2
= (am
1
+ bm
4
) mod n
M
3
= (am
2
+ bm
3
) mod n
M
4
= (am
2
+ bm
4
) mod n
Один из четырех результатов, M
1
, M
2
, M
3
и M
4
, равно M. Если сообщение написано по английски, выбрать правильное M
i нетрудно. С другой стороны, если сообщение является потоком случайных битов (скажем, для генерации ключей или цифровой подписи ), способа определить, какое M
i
- правильное, нет. Одним из способов решить эту проблему служит добавление к сообщению перед шифрованием известного заголовка .
Williams
Хью Вильямс (Hugh Williams) переопределил схему Рабина, чтобы устранить эти недостатки [1601]. В его схеме p и q выбираются так, чтобы p ? 3 mod 8
q ? 7 mod 8
и
N = pq
Кроме того, используется небольшое целое число, S, для которого J(S,N) = -1. (J - это символ Якоби - см.
раздел I I .3). N и S опубликовываются. Секретным ключом является k, для которого k = 1/2 (1/4 (p - 1) (q - 1) + 1)
Для шифрования сообщения M вычисляется c
1
, такое что J(M,N) =
( )
?1 1
c
. Затем вычисляется M' = (
S
c
1
*M)
mod N. Как и в схеме Рабина, C = M'
2
mod N. И c
2
= M' mod 2. Окончательным шифротекстом сообщения явл я- ется тройка:
(C, c l
, c
2
)
Для дешифрирования C, получатель вычисляет M" с помощью
C
k
?± M" (mod N)
Правильный знак M" определяет c
2
. Наконец
M= (
S
c
1
*
( )
?1 1
c
*M") mod N
Впоследствии Вильямс улучшил эту схему в [1603, 1604, 1605]. Вместо возведения в квадрат открытого те к- ста сообщения, возведите его в третью степени . Большие простые числа должны быть конгруэнтны 1 по модулю
3, иначе открытый и закрытый ключи окажутся одинаковыми . Даже лучше, существует только одна уникальная расшифровка каждого шифрования.
Преимущество схем Рабина и Вильямса перед RSA в том, что доказано, что они также безопасны, как и ра з- ложение на множители. Однако перед вскрытием с выбранным шифротекстом они совершенно беззащитны .
Если вы собираетесь использовать эти схемы для случаев, когда взломщик может выполнить такое вскрытие
(например, алгоритм цифровой подписи, когда взломщик может выбирать подписываемые сообщения ), не за-

бывайте использовать перед подписанием однонаправленную хэш-функцию . Рабин предложил другой способ защититься от такого вскрытия: к каждому сообщению перед хэшированием и подписанием добавляется ун и- кальная случайная строка. К несчастью, после добавления однонаправленной хэш-функцией тот факт, что си с- тема столь же безопасна, как и разложение на множители, больше не является доказанным [628]. Хотя с прак- тической точки зрения добавление хэшир ования не может ослабить систему.
Другими вариантами схемы Рабина являются [972, 909, 696, 697, 1439, 989]. Двумерный вариант описан в
[866, 889].
19.6 ElGamal
Схему EIGamal [518,519] можно использовать как для цифровых подписей, так и для шифрования, его без о- пасность основана на трудности вычисления дискретных логарифмов в конечном поле .
Для генерации пары ключей сначала выбирается простое число p и два случайных числа, g и x, оба эти чис- ла должны быть меньше p. Затем вычисляется y = g x
mod p
Открытым ключом являются y, g и p. И g, и p можно сделать общими для группы пользователей . Закрытым ключом является x.
Подписи ElGamal
Чтобы подписать сообщение M, сначала выбирается случайное число k, взаимно простое с p-1. Затем вычис- ляется a = g k
mod p и с помощью расширенного алгоритма Эвклида находится b в следующем уравнении:
M = (xa + kb) mod (p - 1)
Подписью является пара чисел: a и b. Случайное значение k должно храниться в секрете. Для проверки под- писи нужно убедиться, что y
a a
b mod p = g
M
mod p
Каждая подпись или шифрование EIGamal требует нового значения k, и это значение должно быть выбрано случайным образом. Если когда-нибудь Ева раскроет k, используемое Алисой, она сможет раскрыть закрытый ключ Алисы x. Если Ева когда-нибудь сможет получить два сообщения, подписанные или зашифрованные с помощью одного и того же k, то она сможет раскрыть x, даже не зная значение k. Описание ElGamal сведено в
14-й.
Табл. 19-5.
Подписи ElGamal
Открытый ключ:
p простое число (может быть общим для группы пользователей)
g y
=g x
mod p
Закрытый ключ:
x
Подпись:
k выбирается случайным образом, взаимно простое с p-1
a
(подпись) =g k
mod p b
(подпись), такое что M = (xa + kb) mod (p - 1)
Проверка:
Подпись считается правильной, если y a
a b
mod p = g
M
mod p
Например, выберем p = 11 и g = 2, а закрытый ключ x = 8. Вычислим

y = g x
mod p = 2 8
mod 11 = 3
Открытым ключом являются y = 3, g = 2 и p = 11. Чтобы подписать M = 5, сначала выберем случайное число k=9. Убеждаемся, что gcd(9, 10)= 1. Вычисляем a = g k
mod p = 2 9
mod 11 = 6
и с помощью расширенного алгоритма Эвклида находим b:
M = (xa + kb) mod (p - 1)
5 = (8*6 + 9*b) mod 10
Решение: b = 3, а подпись представляет собой пару: a = 6 и b = 3.
Для проверки подписи убедимся, что y
a a
b mod p = g
M
mod p
3 6
6 3
mod 11 = 2 5
mod 11
Вариант EIGamal, используемый для подписей, описан в [1377]. Томас Бет (Thomas Beth) изобрел вариант схемы EIGamal, подходящий для доказательства идентичности [146]. Существуют варианты для проверки под- линности пароля [312] и для обмена ключами [773]. И еще тысячи и тысячи других (см. раздел 20.4).
Шифрование ElGamal
Модификация EIGamal позволяет шифровать сообщения. Для шифрования сообщения M сначала выбирает- ся случайное число k, взаимно простое с p - 1. Затем вычисляются a = g k
mod p b = y k
M mod p
Пара (a,b) является шифротекстом. Обратите внимание, что шифротекст в два раза длиннее открытого те к- ста. Для дешифрирования (a,b) вычисляется
M = b/a x
mod p
Так как a x
? g kx
(mod p) и b/a x
? y k
M/a x
? g xk
M/ g kx
= M (mod p), то все работает (см. 13-й). По сути это то же самое, что и обмен ключами Диффи-Хеллмана (см. раздел 22.1) за исключением того, что y - это часть ключа, а при шифровании сообщение умножается на y k
Табл. 19-6.
Шифрование ElGamal
Открытый ключ:
p простое число (может быть общим для группы пользователей)
g y
=g x
mod p
Закрытый ключ:
x
Шифрование:
k выбирается случайным образом, взаимно простое с p-1
a
(шифротекст) =g k
mod p b
(шифротекст)= y k
M mod p
Дешифрирование:
M (открытый текст) = b/a x
mod p
Скорость
Некоторые примеры скорости работы программных реализаций EIGamal приведены в 12-й [918].
Табл. 19-7.

Скорости EIGamal для различных длин модулей при 160-битовом пока- зателе степени (на SPARC II)
512 битов
768 битов
1024 битов
Шифрование
0.33 с
0.80 с
1.09 с
Дешифрирование
0.24 с
0.58 с
0.77 с
Подпись
0.25 с
0.47 с
0.63 с
Проверка l.37 с
5.12 с
9.30 c
Патенты
ElGamal незапатентован. Но, прежде чем двигаться вперед и реализовывать алгоритм, нужно знать, что PKP
считает, что этот алгоритм попадает под действие патента Диффи-Хеллмана [718]. Однако срок действия патен- та Диффи-Хеллмана заканчивается 29 апреля 1997 года , что делает ElGamal первым криптографическим плго- ритмом с открытыми ключами, пригодным для шифрования и цифровых подписей и несвязанным в Соедине н- ных Штатах патентами. Я не могу дождаться этого момента.
19.7 McEliece
В 1978 году Роберт МакЭлис (Robert McEliece) разработал криптосистему с открытыми ключами на основе теории алгебраического кодирования [1041]. Этот алгоритм использует существование определенного класса исправляющих ошибки кодов, называемых кодами Гоппа (Goppa). Он предлагал создать код Гоппа и замаск и- ровать его как обычный линейный код. Существует быстрый алгоритм декодирования кодов Гоппа , но общая проблема найти слово кода по данному весу в линейном двоичном коде является NP-полной. Хорошее описание этого алгоритма можно найти в [1233], см. также [1562]. Ниже приведен только краткий обзор.
Пусть d
H
(x,y) обозначает расстояние Хэмминга между x и y. Числа n, k и t служат параметрами системы.
Закрытый ключ состоит из трех частей: G' - это матрица генерации года Гоппа, исправляющего t ошибок. P - это матрица перестановок размером n*n. S - это nonsingular матрица размером k*k.
Открытым ключом служит матрица G размером k*n: G = SG'P.
Открытый текст сообщений представляет собой строку k битов в виде k-элементного вектора над полем
GF(2).
Для шифрования сообщения случайным образом выбирается n-элементный вектор z над полем GF(2), для которого расстояние Хэмминга меньше или равно t.
c = mG + z
Для дешифрирования сообщения сначала вычисляется c' = cP
-1
. Затем с помощью декодирующего алгоритма для кодов Гоппа находится m' , для которого d
H
(m'G,c) меньше или равно t. Наконец вычисляется m = m'S
-1
В своей оригинальной работе МакЭлис предложил значения n = 1024, t = 50 и k = 524. Это минимальные значения, требуемые для безопасности.
Хотя этот алгоритм был одним из первых алгоритмов с открытыми ключами, и вне появлялось публикаций о его успешном криптоаналитическом вскрытии, он не получил широкого признания в криптографическом с о- обществе. Схема на два-три порядка быстрее, чем RSA, но у нее есть ряд недостатков. Открытый ключ огромен:
2 19
битов. Сильно увеличивается объем данных - шифротекст в два раза длиннее открытого текста .
Ряд попыток криптоанализа этой системы можно найти в [8, 943, 1559, 306]. Ни одна из них не достигла ус- пеха для общего случая, хотя сходство между алгоритмом МакЭлиса и алгоритмом рюкзака немного волнует.
В 1991 два русских криптографа заявили, что взломали систему МакЭлиса с некоторыми параметрами [882].
В их статье это утверждение не было обосновано , и большинство криптографов не приняли во внимание этот результат. Еще одно выполненное русскими вскрытие, которое нельзя непосредственно использовать против системы МакЭлиса, описано в [1447, 1448]. Расширения McEliece можно найти в [424, 1227, 976].
Другие алгоритмы, основанные на линейных кодах, исправляющих ошибки
Алгоритм Нидеррейтера (Niederreiter) [1167] очень близок к алгоритму МакЭлиса и считает, что открытый ключ - это случайная матрица проверки четности кода, исправляющего ошибки . Закрытым ключом служит эф- фективный алгоритм декодирования этой матрицы .
Другой алгоритм, используемый для идентификации и цифровых подписей, основан на декодировании

синдрома [1501], пояснения см. в [306]. Алгоритм [1621], использующий коды, исправляющие ошибки, небез о- пасен [698, 33, 31, 1560, 32].
19.8 Криптосистемы с эллиптическими кривыми
Эллиптические кривые изучались многие годы, и по этому вопросу существует огромное количество литер а- туры. В 1985 году Нил Коблиц (Neal Koblitz) и В.С. Миллер (V. S. Miller) независимо предложили использовать их для криптосистем с открытыми ключами [867, 1095]. Они не изобрели нового криптографического алгори т- ма, использующего эллиптические кривые над конечными полями, но реализовали существующие алгоритмы,