Методы и средства криптографической защиты информации. Жданов О.Н - 161 стр.

UptoLike

ВУЗ: 

СибГАУ | Красноярск

Составители: 

Рубрика: 

161
Схема шифрования Pohlig-Hellman похожа на RSA. Это не
симметричный алгоритм, так как для шифрования и дешифрирования
используются различные ключи. Это не схема с открытым ключом, потому
что ключи легко получаются один из другого, и ключ шифрования, и ключ
дешифрирования должны храниться в секрете. Как и в RSA,
С = P
e
mod n
P=C
d
modn
где
ed
≡
1 (mod какое-нибудь составное число)
В отличие от RSA n не определяется с помощью двух простых чисел и
остается частью закрытого ключа. Если у кого-нибудь есть е и п, он может
вычислить d. He зная е или d, противник будет вынужден вычислить
е = log
p
C mod n, а это является трудной проблемой.
2.7.4. Алгоритм Rabin
Безопасность схемы Рабина (Rabin) опирается на сложность поиска
квадратных корней по модулю составного числа. Эта проблема аналогична
разложению на множители. Вот одна из реализаций этой схемы.
Сначала выбираются два простых числа р и q, конгруэнтных 3 mod 4.
Эти простые числа являются закрытым ключом, а их произведение п =pq -
открытым ключом.
Для шифрования сообщения М(М должно быть меньше n), просто
вычисляется С = М
2
mod n
Дешифрирование сообщения также несложно, но немного скучнее. Так
как получатель знает р и q, он может решить две конгруэнтности с помощью
китайской теоремы об остатках . Вычисляется
m
1
= C
(p+l)/4
mod p
т
2
= (р - C
(p+1)/4
) mod p
т
3
= C
(q+1)/4
mod q
m
4
= (q- C
(q+1)/4
) mod q
Затем выбирается целые числа а = 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
= (ат
2
+ bm
3
) mod n
M
4
= (am
2
+ bm
4
) mod n
Один из четырех результатов M
1
, M
2
, М
3
и М
4
, равно М. Если
сообщение написано по английски, выбрать правильное М, нетрудно. С
другой стороны, если сообщение является потоком случайных битов
(скажем, для генерации ключей или цифровой подписи), способа определить,
какое М
i
- правильное, нет. Одним из способов решить эту проблему служит
добавление к сообщению перед шифрованием известного заголовка.
Алгоритм Williams. Хью Вильяме (Hugh Williams) переопределил
схему Рабина, чтобы устранить эти недостатки. В его схеме р и q выбираются
так, чтобы
р = 3 mod 8

Страницы