The design of the UNIX Operating System 130 страница
Часто используется шифрование с помощью односторонней функции, называемой также хеш- или дай-джест-функцией. Применение этой функции к шифруемым данным позволяет сформировать небольшой дайджест из нескольких байтов, по которому невозможно восстановить исходный текст. Получатель со - общения может проверить целостность данных, сравнивая полученный вместе с сообщением дайджест с вычисленным вновь при помощи той же односторонней функции. Эта техника активно используется для контроля входа в систему. Например , пароли пользователей хранятся на диске в зашифрованном одно-сторонней функцией виде. Наиболее популярные хеш-функции: MD4, MD5 и др.
|
|
|
В системах шифрования с открытым или асимметричным ключом (public/ assymmetric key) использу - ется два ключа (см. рис. 15.1). Один из ключей, называемый открытым, несекретным, используется для шифрования сообщений, которые могут быть расшифрованы только с помощью секретного ключа, имеющегося у получателя, для которого предназначено сообщение. Иногда поступают по-другому. Для шифрования сообщения используется секретный ключ, и если сообщение можно расшифровать с помо-щью открытого ключа, подлинность отправителя будет гарантирована (система электронной подписи). Этот принцип изобретен Уитфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом (Martin Hellman) в 1976 г.
|
|
|
|
|
|
Рис. 15.1. Шифрование открытым ключом
Использование открытых ключей снимает проблему обмена и хранения ключей, свойственную системам с симметричными ключами. Открытые ключи могут храниться публично, и каждый может послать за-шифрованное открытым ключом сообщение владельцу ключа. Однако расшифровать это сообщение мо - жет только владелец открытого ключа при помощи своего секретного ключа, и никто другой. Несмотря на очевидные удобства, связанные с хранением и распространением ключей, асимметричные алгоритмы гораздо менее эффективны, чем симметричные, поэтому во многих криптографических системах исполь-зуются оба метода.
|
|
|
Среди несимметричных алгоритмов наиболее известен RSA, предложенный Роном Ривестом (Ron Rivest), Ади Шамиром (Adi Shamir) и Леонардом Эдлманом (Leonard Adleman). Рассмотрим его более подробно.
| Основы операционных систем | 165 |
Шифрование с использованием алгоритма RSA
Идея, положенная в основу метода, состоит в том, чтобы найти такую функцию y=Φ(x), для которой по-лучение обратной функции x=f-1(y) было бы в общем случае очень сложной задачей (NP-полной задачей). Например, получить произведение двух чисел n=pЧq просто, а разложить n на множители, если p и q дос-таточно большие простые числа, – NP-полная задача с вычислительной сложностью ~ n10. Однако если знать некую секретную информацию, то найти обратную функцию x=f-1(y) существенно проще. Такие функции также называют односторонними функциями с лазейкой или потайным ходом.
Применяемые в RSA прямая и обратная функции просты. Они базируются на применении теоремы Эй-лера из теории чисел.
Прежде чем сформулировать теорему Эйлера, необходимо определить важную функцию Φ(n) из теории чисел, называемую функцией Эйлера. Это число взаимно простых (взаимно простыми называются целые числа, не имеющие общих делителей) с n целых чисел, меньших n. Например, Φ(7)=6. Очевидно, что, ес-
ли p и q – простые числа и p 
q, то Φ(p)=p-1, и Φ(pq)=(p-1)Ч(q-1).
Теорема Эйлера
Теорема Эйлера утверждает, что для любых взаимно простых чисел x и n (x < n)
xΦ(n)mod n = 1
или в более общем виде
xkΦ(n)+1mod n = 1
Сформулируем еще один важный результат. Для любого m>0 и 0<e<m, где e и m взаимно просты, най-дется единственное 0<d<m, такое, что
Дата добавления: 2021-01-21; просмотров: 105; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!