Алгоритм обмена ключа Диффи-Хеллмана

⇐ ПредыдущаяСтр 5 из 7Следующая ⇒

Первая публикация данного алгоритма открытого распространения ключа появилась в статье Диффи и Хеллмана в 1976 году, в которой вводились основные понятия криптографии с открытым ключом и в общих чертах упоминался алгоритм обмена ключа Диффи-Хеллмана. Открытое распределение ключей" (ОРК) подразумевает независимое генерирование каждым из пары связывающихся пользователей своего случайного числа, преобразование его посредством некоторой процедуры, обмен преобразованными числами по каналу связи и вычисление общего секретного ключа на основе информации, полученной по каналу связи от партнера и своего случайного числа. Каждый такой ключ существует только в течение одного сеанса связи (или даже части сеанса).

Таким образом, ОРК позволяет паре пользователей системы выработать общий секретный ключ, не имея заранее распределенных секретных элементов.
При этом две функции общего секретного ключа, традиционно доставляемого из Центра, - защита информации в канале связи от третьей стороны и подтверждение подлинности каждого из абонентов его партнеру, - разделяются.

Цель алгоритма состоит в том, чтобы два участника могли безопасно обменяться ключом, который в дальнейшем может использоваться в каком-либо алгоритме симметричного шифрования. Сам алгоритм Диффи-Хеллмана может применяться только для обмена ключами.

Алгоритм основан на трудности вычислений дискретных логарифмов. Дискретный логарифм определяется следующим образом. Вводится понятие примитивного корня простого числа Q как числа, чьи степени создают все целые от 1 до Q – 1. Это означает, что если А является примитивным корнем простого числа Q, тогда числа A mod Q, A² mod Q, ..., A^Q^{– 1} mod Q

являются различными и состоят из целых от 1 до Q – 1 с некоторыми перестановками. В этом случае для любого целого B < Q и примитивного корня A простого числа Q можно найти единственную экспоненту Х, такую, что

Y = A^Х mod Q, где 0 ≤ X ≤ (Q – 1)

Экспонента X называется дискретным логарифмом.

Протокол генерации ключей алгоритма Диффи-Хеллмана

Абоненты А и В:

1. знают числа A и P, которые являются открытыми константами протокола и известны всем участникам Р – простое число и А является примитивным корнем Р;

2. генерируют независимо друг от друга случайные числа – закрытые ключи: Ka, Kb, удовлетворяющих условию: 1 < K < P

3. вычисляют значения Y_A = A^Ka mоd(P) и Y_B = A^Kb mоd(P) и обмениваются ими по открытому каналу связи.

4. вычисляют общий секретный ключ K, которым шифруют сообщения по симметричному алгоритму.

абонент А:

K = (Y_B)^Ка mod (Р) = (A^К^b mod (Р))^Ка mod (Р) = (A^К^b )^Ка mod (Р)

абонент В:

K = (Y_А)^К^b mod (Р) = (A^Ка mod (Р))^К^b mod (Р) = (A^Ка )^К^b mod (Р)

Таким образом, две стороны обменялись секретным ключом. Так как значения К_а и К_b являются закрытыми, противник может получить только следующие значения: Р, A, Y_А и Y_В. Для вычисления ключа атакующий должен взломать дискретный логарифм, т.е. вычислить К_а и К_b, что является вычислительно трудной задачей

Безопасность обмена ключа в алгоритме Диффи-Хеллмана вытекает из того факта, что, хотя относительно легко вычислить экспоненты по модулю простого числа, очень трудно вычислить дискретные логарифмы. Для больших простых чисел задача считается практически неразрешимой.

Электронная подпись на базе алгоритма RSA

Система электронной подписи RSA получается при " смене мест" ключей e и d, т.е. шифрование сообщения для получения подписи производится с помощью ключа KR = {d, n}.
Цифровой подписью сообщения является число s: S = M ^d mоd (n), которое передается вместе с сообщением.

Проверка подлинности подписанного сообщения [M, S]: M =S^e mod (n)

Равенство чисел принятого сообщения и расшифрованной подписи доказывает, что сообщение M было подписано обладателем секретного ключа d, соответствующего ключу проверки подписи e, т.е. авторизует сообщение.

Протокол работы пары абонентов сети общей связи с алгоритмом RSA выглядит так.

1. Абоненты A (отправитель) и B (получатель) генерируют независимо друг от друга пары простых чисел: p_a, q_a и p_b, q_b

2. Вычисляют произведение больших простых чисел: N_a = p_a * q_a и N_b = p_b * q_b

3. Вычисляют ключи: E_a и D_a и E_b и D_b

4. Числа N_a, N_b и E_a, E_b помещаются в общедоступный справочник и получают статус открытых ключей; числа D_a, D_b сохраняются в качестве секретных ключей;

5. Обмен зашифрованными сообщениями:

А посылает В C _a = M_a^Eb mоd(N_b), зашифрованное открытым ключом пользователя B.

В посылает А C_b = M_в^Ea mоd(N_a), зашифрованное открытым ключом пользователя A.

6. Расшифрование: пользователь А → M_в = C_b^Da mоd(N_a)

пользователь В → M_a = C_a^Db mоd(N_b)

Формирование цифровой подписи:

1. Абоненты подписывают и шифруют сообщения:

А → S_a = M_a ^Da m оd(N_a)C_a = M_a^Eb mоd(N_b);

В → S_b = M_b ^Db mоd(N_b)C_b = M_b^Ea mоd(N_a).

2. ПередаютА → В: S_a, C _a В → А: S_b, C_b_.

3.РасшифровываютА: M_b = С_b^Da mоd(N_a), В: M_a = С_a^Db mоd(N_b)

4. Проверяют подлинность подписи

В: M_a = S_a ^Ea mоd(N_a), А: M_b = S_b ^Eb mоd(N_b)

В случае равенства значений принятых и расшифрованных M_a и M_b сообщения считаются переданными без искажения, а пользователи А и В аутентифицированы.

Алгоритм RSA

Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest), Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах. С тех пор алгоритм Rivest-Shamir-Adleman (RSA) широко применяется практически во всех приложениях, использующих криптографию соткрытым ключом.

Алгоритм RSA представляет собой блочный алгоритм шифрования, где зашифрованные и незашифрованные данные являются целыми между 0 и n -1 для некоторого n.

Первым этапом любого асимметричного алгоритма является создание пары ключей: открытого и закрытого и распространение открытого ключа. Для алгоритма RSA этап создания ключей состоит из следующих операций:

1. Выбираются два простых числа p и q

2. Вычисляется их произведение n=(p*q)

3. Выбирается произвольное число e (e< n), такое, что НОД(e, (p-1)(q-1))=1, то есть e должно быть взаимно простым с числом (p-1)(q-1).

4. Методом Евклида решается в целых числах уравнение e*d+(p-1)(q-1)*y=1.

Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар ( d, y ), каждая из которых является решением уравнения в целых числах.

5. Два числа { e, n } – являются открытым ключом KU.

6. Число d хранится в секрете – это и есть закрытый ключ – KR = {d, n}, который позволит расшифровывать сообщения, зашифрованные с помощью пары чисел ( e, n ).

Как же производится собственно шифрование с помощью этих чисел:

1. Отправитель разбивает свое сообщение на блоки, равные k=[log₂(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.

2. Подобный блок может быть интерпретирован как число из диапазона ( 0; 2^k-1 ). Для каждого такого числа m_i вычисляется выражение c_i=(m_i)^emod n. Блоки c_i и есть зашифрованное сообщение.

Их можно спокойно передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название " логарифмирование в конечном поле" и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по c_i прочесть исходные сообщения m_i он не может никак, кроме как полным перебором m_i.

На приемной стороне процесс расшифрованияпроизводится с помощью хранимого в секрете числа d. Достаточно давно была доказана теорема Эйлера, частный случай которой утверждает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство

(x^(p-1)(q-1))mod n = 1.

Для дешифрования RSA-сообщений используется эта формула. Возведем обе ее части в степень (-y): (x^{(-y) (p-1) (q-1)}) mod n = 1^(-y) = 1. Теперь умножим обе ее части на x :

(x^(-^{y) (}^{p-1) (}^{q-1) +1})mod n = 1*x = x

(c_i)^dmod n =((m_i)^e*dmod n = m_i.

Алгоритм RSA основан на использовании односторонней функции с лазейкой. Зная публично известные n и e, мы можем найти С = M^e (mod n) по заданному M, но не наоборот (если злоумышленник перехватит C, то восстановить M вычислительно трудная задача). При этом, если мы знаем как n раскладывается на множители, то выполнить обратную операцию легко. Разложение числа n на множители и есть та самая лазейка. Наличие лазейки позволяет применять RSA как для шифрования, так и в схеме цифровой подписи.

⇐ Предыдущая 1 2 3 456 7 Следующая ⇒