Здесь mod – операция «сравнение по модулю», ее результат – целый остаток от деления первого выражения на N. Как отправитель, так и получатель должны знать значение N. Отправитель знает значение е, а получатель – значение d (или наоборот).
Первый этап этого алгоритма – создание пары ключей (открытого и закрытого). Он состоит из следующих операций:
1. Выбираются два простых числа p и q
2. Вычисляется их произведение n = p*q
3. Выбирается число е (e<n), взаимно простое с p и q. То есть: НОД(e,(p-1)(q-1)) = 1,
Здесь НОД – наибольший общий делитель.
4. Решается в целых числах уравнение: e*d+(p-1)(q-1)*y = 1
Здесь d и y – неизвестные, искомые переменные. Уравнение решается методом Евклида, который и находит множество пар (d, y), каждая из которых является решением уравнения.
5. Два числа (e, n) публикуются как открытый ключ.
6. Число d является закрытым (секретным) ключом. P, q – секретные.
Шифрование с помощью алгоритма RSA
1. Отправитель разбивает свое сообщение на блоки, меньшие n.
2. Если исходный текст М, то шифрованный текст С = Мe (modn). Это значит: возводим М в степень е, делим на n и берем целый остаток от деления – это и есть зашифрованный результат.
Например: Пусть на вход блока шифрования подали число = 19. Тогда результат шифрования вычисляется так: 195 = 2476099 / 119 = 20807 c остатком 66. Результат шифрования – число 66
Дешифрование с помощью алгоритма RSA
Открытый текст вычисляется по формуле: M = Cdmodn
Например: На вход подали зашифрованное ранее число 66. Тогда открытый текст вычисляется так: 6677 = 1,27*10140 /119 = 1.06*10138 c остатком 19. Открытый текст – 19.
Распределение открытых ключей. Можно распределять следующими способами.
1. Публичное объявление открытых ключей. Этот подход очень удобен, но опасен возможностью подлога: некто посылает другим абонентам открытый ключ от лица пользователя А. Пока пользователь А обнаружит подлог, фальсификатор может прочитать все шифрованные сообщения, адресованные А.
2. Публично доступный каталог, публикация ключа в котором возможна либо при личной явке владельца, либо по защищенным каналам связи. Эта схема более защищена, но если противнику удается получить личный ключ объекта, ведущего каталог, то он получает возможность фальсифицировать ключ любого участника.
3. Авторитетный центр открытых ключей. В этом случае за каждым открытым ключом другого участника нужно обращаться в центр по защищенным каналам связи.
4. Сертификаты открытых ключей. В этом случае участники обмена могут обмениваться открытыми ключами без участия центра. Участник обмена генерирует пару ключей и обращается в центр сертификации за сертификатом, а затем может передавать этот сертификат другим участникам.
Цель алгоритма – дать возможность пользователям сообщить друг другу секретный ключ (сгенерировать его), чтобы шифровать последующие сообщения. Для зашифровывания и расшифровывания сообщений этот алгоритм использовать нельзя.
Эффективность алгоритма Диффи-Хеллмана опирается на трудность вычисления дискретных логарифмов. Дискретный логарифм определяется следующим образом. Есть понятие первообразного корня простого числа p(иногда его называют примитивным корнем по модулю p): число g является первообразным корнем p, если для каждого числа b от 1 до p-1 существует такое а, что gа = b (mod p). Например, 2 – первообразный корень числа 11. Это значит, что для каждого числа b от 1 до 10 существует целое число a, такое, что 2a = b (mod 11). Это число а называют дискретным логарифмом.
Обмен ключами по схеме Диффи-Хеллмана происходит следующим образом. В этой схеме имеется два открытых для всех числа: простое число q и целое число g, являющееся первообразным корнем q. Пусть пользователи А и В намерены обменяться ключами. Пользователь А выбирает случайное число Х1<q и вычисляет Ya = gx1 mod q. Пользователь В выбирает случайное число Х2<q и вычисляет Yb = gх2 mod q. Каждая сторона сохраняет значения X1 и Х2 в тайне, и делает значение Y свободно доступным другой стороне. Оба пользователя могут по значению Y (открытому ключу) и своему значению X1 или Х2 вычислить новый секретный ключ К. По правилам арифметики в классах вычетов следующие две формулы дают один и тот же результат: K = (Yb)x1 mod q, K = (Ya)x2 mod q
Таким образом, обе стороны владеют общим секретным ключом. А поскольку значения Х1 и Х2 хранились в тайне, противнику нужно по известным q, g, Ya, Yb вычислять ключи Х1 или Х2. Это задача вычисления дискретного логарифма, которая для больших простых чисел считается практически неразрешимой.
Для достижения приемлемой криптографической стойкости секретные ключи должны выбираться длиной не менее 256 бит. Кроме того, на безопасность системы влияет выбор чисел а и q. Число q должно быть большим: безопасность системы основана на сложности разложения на множители чисел той же величины, что и q.
Протокол обмена ключами по схеме Диффи-Хеллмана:
1. Всем участникам сообщаются открытые элементы: q – простое число и a (a<q) – первообразный корень q
2. Пользователь А вычисляет пару ключей (открытый и секретный):
X1 – случайное целое число (X1<q) (секретный ключ)
Ya = ax1 mod q (открытый ключ)
3. Пользователь В вычисляет пару ключей (открытый и секретный):
X2 – случайное целое число (X2<q) (секретный ключ)
Yb = ax2 mod q (открытый ключ)
4. Пользователь А вычисляет общий секретный ключ K = (Yb)x1 mod q
5. Пользователь В вычисляет общий секретный ключ K = (Ya)x2 mod q
Потоковые шифры преобразуют открытый текст в шифртекст побитно или побайтно. При этом один и тот же бит (или байт) открытого текста превращается в различные биты (или байты) шифртекста. Чаще всего потоковые шифры применяются при шифровании бесконечных потоков сообщений, например сетевого трафика между двумя компьютерами. Наибольшее применение потоковые шифрсистемы получили в радиосвязи и в беспроводных сетях.
Шифрование происходит следующим образом. Шифртекст получается в результате операции XOR над открытым текстом и гаммой (потока битов, создаваемого генератором гаммы).
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.