Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[117]

Сначала выбираются два простых числа p и q, конгруэнтных 3 mod 4. Эти простые числа являются закр ы-тым ключом, а их произведение n =pq - открытым ключом.

Для шифрования сообщения M (M должно быть меньше n), просто вычисляется

C = M2 mod n

Дешифрирование сообщения также несложно, но немного скучнее . Так как получатель знает p и q, он может решить две конгруэнтности с помощью китайской теоремы об остатках . Вычисляется

m1 = С+1)/4 mod p

m2 = (p - C(p+1)/4) mod p

m3 = C<q+1)/4 mod q

m4 = (q - C(q+1)/4) mod q

Затем выбирается целые числа a = q(q-1 mod p и b = p(p-1 mod q). Четырьмя возможными решениями являются:

M1 = (am1 + bm3) mod n M2 = (am1 + bm4) mod n M3 = (am2 + bm3) mod n M4 = (am2 + bm4) mod n

Один из четырех результатов, M1, M2, M3 и M4, равно M. Если сообщение написано по английски, выбрать правильное Mi нетрудно. С другой стороны, если сообщение является потоком случайных битов (скажем, для генерации ключей или цифровой подписи ), способа определить, какое Mi - правильное, нет. Одним из способов решить эту проблему служит добавление к сообщению перед шифрованием известного заголовка .

Williams

Хью Вильямс (Hugh Williams) переопределил схему Рабина, чтобы устранить эти недостатки [1601]. В его схеме p и q выбираются так, чтобы

p = 3 mod 8

q = 7 mod 8

Кроме того, используется небольшое целое число, S, для которого J(S,N) = -1. (J - это символ Якоби - см. раздел I I .3). N и S опубликовываются. Секретным ключом является k, для которого

k = 1/2 (1/4 (p - 1) (q - 1) + 1)

Для шифрования сообщения M вычисляется c1, такое что J(M,N) =(-1)c1 . Затем вычисляется M = (Sc1 *M) mod N. Как и в схеме Рабина, C = M2 mod N. И c2 = M mod 2. Окончательным шифротекстом сообщения является тройка:

(C, ci, c2)

Для дешифрирования C, получатель вычисляет M" с помощью Ck =± M" (mod N)

Правильный знак M" определяет c2. Наконец M= (Sc1 * (-1) c1 *M") mod N

Впоследствии Вильямс улучшил эту схему в [1603, 1604, 1605]. Вместо возведения в квадрат открытого текста сообщения, возведите его в третью степени . Большие простые числа должны быть конгруэнтны 1 по модулю 3, иначе открытый и закрытый ключи окажутся одинаковыми . Даже лучше, существует только одна уникальная расшифровка каждого шифрования.

Преимущество схем Рабина и Вильямса перед RSA в том, что доказано, что они также безопасны, как и ра з-ложение на множители. Однако перед вскрытием с выбранным шифротекстом они совершенно беззащитны . Если вы собираетесь использовать эти схемы для случаев, когда взломщик может выполнить такое вскрытие (например, алгоритм цифровой подписи, когда взломщик может выбирать подписываемые сообщения ), не за-


бывайте использовать перед подписанием однонаправленную хэш-функцию . Рабин предложил другой способ защититься от такого вскрытия: к каждому сообщению перед хэшированием и подписанием добавляется ун и-кальная случайная строка. К несчастью, после добавления однонаправленной хэш-функцией тот факт, что си с-тема столь же безопасна, как и разложение на множители, больше не является доказанным [628]. Хотя с практической точки зрения добавление хэшир ования не может ослабить систему.

Другими вариантами схемы Рабина являются [972, 909, 696, 697, 1439, 989]. Двумерный вариант описан в [866, 889].

19.6 ElGamal

Схему EIGamal [518,519] можно использовать как для цифровых подписей, так и для шифрования, его без опасность основана на трудности вычисления дискретных логарифмов в конечном поле .

Для генерации пары ключей сначала выбирается простое число р и два случайных числа, g и x, оба эти числа должны быть меньше р. Затем вычисляется

y = gx mod р

Открытым ключом являются y, g и р. И g, и р можно сделать общими для группы пользователей. Закрытым ключом является x.

Подписи ElGamal

Чтобы подписать сообщение M, сначала выбирается случайное число k, взаимно простое с р-1. Затем вычисляется

a = gk mod р

и с помощью расширенного алгоритма Эвклида находится b в следующем уравнении: M = (xa + kb) mod (р - 1)

Подписью является пара чисел: a и b. Случайное значение к должно храниться в секрете. Для проверки подписи нужно убедиться, что

yaab mod р = gM mod р

Каждая подпись или шифрование EIGamal требует нового значения к, и это значение должно быть выбрано случайным образом. Если когда-нибудь Ева раскроет к, используемое Алисой, она сможет раскрыть закрытый ключ Алисы x. Если Ева когда-нибудь сможет получить два сообщения, подписанные или зашифрованные с помощью одного и того же к, то она сможет раскрыть x, даже не зная значение к. Описание ElGamal сведено в

Табл. 19-5. Подписи ElGamal

Открытый ключ:

рпростое число (может быть общим для группы пользователей)

g<р (может быть общим для группы пользователей)

y=gx mod р

Закрытый ключ: x<р

Подпись:

квыбирается случайным образом, взаимно простое с р-1

a(подпись) =gk mod р

b(подпись), такое что M = (xa + kb) mod (р - 1)

Проверка:

Подпись считается правильной, если yaab mod р = gM mod р

Например, выберем р = 11 и g = 2, а закрытый ключ x = 8. Вычислим


y = gx mod p = 28 mod 11 = 3

Открытым ключом являются y = 3, g = 2 иp = 11. Чтобы подписать M = 5, сначала выберем случайное число k=9. Убеждаемся, что gcd(9, 10)= 1. Вычисляем

a = gk mod p = 29 mod 11 = 6

и с помощью расширенного алгоритма Эвклида находим b: M = (xa + kb) mod (p - 1) 5 = (8*6 + 9*b) mod 10

Решение: b = 3, а подпись представляет собой пару: a = 6 и b = 3. Для проверки подписи убедимся, что yaab mod p = gM mod p 3663 mod 11 = 25 mod 11

Вариант EIGamal, используемый для подписей, описан в [1377]. Томас Бет (Thomas Beth) изобрел вариант схемы EIGamal, подходящий для доказательства идентичности [146]. Существуют варианты для проверки подлинности пароля [312] и для обмена ключами [773]. И еще тысячи и тысячи других (см. раздел 20.4).

Шифрование EIGamal

Модификация EIGamal позволяет шифровать сообщения. Для шифрования сообщения M сначала выбирается случайное число к, взаимно простое с p - 1. Затем вычисляются

a = g mod p

b = yk M mod p

Пара (a,b) является шифротекстом. Обратите внимание, что шифротекст в два раза длиннее открытого те к-ста. Для дешифрирования (a,b) вычисляется

M = b/ax mod p

Так как ax = gkx (mod p) и b/ax = yk M/ax = gxk M/ gkx = M (mod p), то все работает (см. 13-й). По сути это то же самое, что и обмен ключами Диффи-Хеллмана (см. раздел 22.1) за исключением того, что y - это часть ключа, а при шифровании сообщение умножается на yk.

Табл. 19-6. Шифрование EIGamal

Открытый ключ:

pпростое число (может быть общим для группы пользователей)

g<p (может быть общим для группы пользователей)

y=gx mod/?

Закрытый ключ: x<p

Шифрование:

kвыбирается случайным образом, взаимно простое с p-1

a(шифротекст) =gk mod p

b(шифротекст)= yk M mod p

Дешифрирование: M (открытый текст) = b/ax mod p

Скорость

Некоторые примеры скорости работы программных реализаций EIGamal приведены в 12-й [918].

Табл. 19-7.



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203]