СТАНДАРТ АСИММЕТРИЧНОГО ШИФРОВАНИЯ RSA_

СТАНДАРТ АСИММЕТРИЧНОГО ШИФРОВАНИЯ RSA

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

ГЕНЕРАЦИЯ КЛЮЧЕЙ

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

Выбираются два простых (!) числа p и q

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

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

то есть e должно быть взаимно простым с числом (p-1)(q-1).

Решается в целых числах (!) уравнение:

e*d+(p-1)(q-1)*y=1.

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

Два числа (e,n) – публикуются как открытый ключ.

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

 

ШИФРОВАНИЕ/РАСШИФРОВАНИЕ

 

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

Подобный блок может быть интерпретирован как число из диапазона (0;2^k-1). Для каждого такого числа (назовем его m_i) вычисляется выражение c_i=((m_i)^e)mod 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.

А теперь тем же методом, что были созданы открытый и закрытый ключи, подберем такое d, что:

e*d+(p-1)(q-1)*y=1,

то есть e*d=(-y)(p-1)(q-1)+1.

А следовательно в последнем выражении предыдущего абзаца можем заменить показатель степени на число (e*d). Получаем (x^e*d)mod n = x. То есть для того чтобы прочесть сообщение c_i=((m_i)^e)mod n достаточно возвести его в степень d по модулю m:

((c_i)^d)mod n = ((m_i)^e*d)mod n = m_i.

Общий вид криптосистемы RSA приведен на рис. 3.1.

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

Контрольный пример : Если p = 47 и q = 71, то n = pq = 3337

Ключ е не должен иметь общих множителей с (p-1)*(q-1) = 3220. Выберем (случайно ) е равным 79. В этом случае d = e^-1mod((p-1)*(q-1)) = 1019

Опубликуем e и n, оставив d в секрете. Отбросим p и q. Для шифрования сообщения сначала разделим его на маленькие блоки

Например m = 688232687966668003 разбивается как

m₁ = 688, m₂ = 232, m₃ = 687, m₄ = 966, m₅ = 668, m₆ = 003

Первый блок шифруется как 688⁷⁹ mod 3337 = 1570 = c₁

Выполняя ту же операцию для следующих блоков, получаем

С = 1570 2756 2091 2276 2423 158

Для дешифрования нужно выполнить такое же возведение в степень, используя ключ дешифрования 1019

1570₁₀₁₉ mod 3337 = 688 = m₁

Аналогично восстанавливается остальная часть сообщения

1. Какая процедура является более производительной – асимметричное шифрование/ дешифрование или симметричное шифрование/дешифрование?

Симметричное шифрование быстрее асимметричного примерно в 1000 раз, т.к все алгоритмы асимметричного шифрования используют медленные операции возведения в степень по модулю, нахождение обратных элементов и.т.п.

2. К какому типу криптоалгоритма (с точки зрения его устойчивости к взлому) и почему относится алгоритм RSA? Шифр RSA обладает практической стойкостью, т.к при его взломе методом полного перебора ключей требуется неоправданно большое количество времени и вычислительных ресурсов, тем не менее существует вероятность нахождения ключа за конечное время.

3. Какая трудноразрешимая математическая задача лежит в основе стойкости алгоритма RSA? В основе RSA положена проблема разложения числа на простые множители. Пока что не найдено алгоритмов, решающих ее за полиномиальное время

4. В чем заключаются проблемы разложения больших чисел на простые множители и вычисления корней алгебраических уравнений? Невозможно кроме как перебором разложить число на простые множители. Невозможно непосредственно вычислить корни алгебраического уравнения в конечном поле

 Пример 1. Пусть р = 5, а q = 11, тогда значение n = 55. В качестве открытого ключа е выберем число 7, таким образом, весь открытый ключ имеет вид (е=7, n=55).

Вычислим закрытый ключ d: уравнение e  d + (p-1)  (q-1)  y = 1 приобретает вид

7  d + 40  y = 1 и имеет в целых числах решение d = 23, y = - 4. Таким образом, закрытым ключом являются числа (23, 55).

Пусть произвольный отправитель хочет передать абоненту комбинацию бит 100111₂ , ее числовой эквивалент 39₁₀ . Возводим 39 в степень открытого ключа е = 7 по модулю n = 55: (39⁷ mod 55) = 19. Число 39 является шифрограммой и передается по каналу связи. Получатель по приходу сообщения возводит его в степень d = 23: (19²³ mod 55) = 39. Исходное значение восстановлено.

Пример 2. Зашифруем сообщение “САВ”.

1. Выберем p=3 и q=11.

2. Определим n=3*11=33.

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

4. Выберем число е. В качестве такого числа может быть взято любое число, для которого удовлетворяется соотношение (е3) (mod 20) = 1, например 7.

5. Представим шифруемое сообщение как последовательность целых чисел с помощью отображения: А1, В2, С3. Тогда сообщение принимает вид (3,1,2). Зашифруем сообщение с помощью ключа {7,33}.

ШТ1 = (3⁷) (mod 33) = 2187 (mod 33) = 9,

ШТ2 = (1⁷) (mod 33) = 1 (mod 33) = 1,

ШТ3 = (2⁷) (mod 33) = 128 (mod 33) = 29.

6. Расшифруем полученное зашифрованное сообщение (9,1,29) на основе закрытого ключа {3,33}:

ИТ1 = (9³) (mod 33) = 729 (mod 33) = 3,

ИТ2= (1³) (mod 33) = 1 (mod 33) = 1,

ИТ3 = (29³) (mod 33) = 24389 (mod 33) = 2.

Здесь ШТ – шифротекст, ИТ – исходный текст.

Итак, в реальных системах алгоритм RSA реализуется следующим образом: каждый пользователь выбирает два больших простых числа, и в соответствии с описанным выше алгоритмом выбирает два простых числа e и d. Как результат умножения первых двух чисел (p и q) устанавливается n.

{e,n} образует открытый ключ, а {d,n} - закрытый (хотя можно взять и наоборот).

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

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

Для непосредственного засекречивания информации двухключевые шифры находят ограниченное применение.