2.5.2. Алгоритмы асимметричного шифрования

Привет, Вы узнаете о том , что такое алгоритмы асимметричного шифрования, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое алгоритмы асимметричного шифрования , настоятельно рекомендую прочитать все из категории Криптография и криптоанализ, Стеганография и Стегоанализ.

Исторически первой системой с открытым ключом стал метод экспоненциального ключевого обмена Диффи - Хеллмана, разработанный в 1976 году. Метод предназначен для передачи секретного ключа симметричного шифрования. В обмене задействованы два участника А и Б. Сначала они выбирают большие простые числа n и g<n (эти числа секретными не являются). Затем участник A выбирает большое целое число х,  вычисляет Х=g^x mod n и передаетХ участнику Б. Б в свою очередь выбирает большое целое число y, вычисляет Y=g^y mod n и передает Y участнику А. Б вычисляет K^’=X^y mod n,  А вычисляетK^’’=Y^x mod n. Легко заметить, что

K^’=K^’’=g^xy mod n, и это значение оба участника могут использовать в качестве ключа симметричного шифрования. Криптостойкость этого метода определяется трудоемкостью вычисления дискретного логарифма в конечном поле. Действительно, злоумышленник может узнать такие параметры алгоритма, как n, g, X, Y, но вычислить по ним значения x или y – задача, требующая очень больших вычислительных мощностей и времени. Метод легко можно обобщить на случай ключевого обмена большего количества участников. Использование метода Диффи - Хеллмана на практике должно сопровождаться сертификацией  «открытых» ключей X и Y. Иначе злоумышленник может провести атаку, которая известна под названием «человек посередине» (man-in-the-middle), когда передаваемые участниками А и Б сообщения перехватываются злоумышленником и подменяются сообщениями X^’и Y^’, вычисленными на основе его закрытого ключа. В итоге будут установлены два соединения «А - зломышленник» и «Б - злоумышленник», причем А и Б будут уверены, что обмениваются сообщениями друг с другом. Необходимо также отметить, что алгоритм Диффи - Хеллмана не является асимметричным алгоритмом шифрования, шифрование при его использовании необходимо выполнять с использованием симметричного шифра. Примером действительно асимметричного алгоритма шифрования, основанного на проблеме дискретного логарифма, является алгоритм Эль-Гемаля, разработанный в 1985 г. Последовательность действий при генерации ключей, шифровании и дешифрации представлена на рис. 2.14.

Рис.2.14. Схема шифрования алгоритма Эль-Гемаля

Необходимо пояснить процедуру дешифрования. Так как a^xºg^kxmod p, то имеем:

Таким образом, кодируемое сообщение М разбивается на части, каждая из которых m интерпретируется как число в диапазоне [0 .. p-1], и выполняется операция шифрования согласно схеме на рис.2.14. На практике при использовании данного алгоритма рекомендуется выбирать ключи размером 768, 1024 и 1536 бит.

Самым первым, действительно асимметричным алгоритмом стал алгоритм RSA, названный так по первым буквам фамилий своих разработчиков. Алгоритм был разработан в 1978 году. В основу криптостойкости RSA положена задача факторизации (разложения на множители) больших (более 200 двоичных разрядов) целых чисел.

Процедуры генерации ключей, шифрования и дешифрования для этого алгоритма представлены на рис. 2.15.

Рис.2.15. Схема шифрования алгоритма RSA

На этапе генерации ключей формируется пара ключей: закрытыйd и открытый e. Шифрование данных должно начинаться с его разбиения на блоки m размером k=[log₂ (n)] бит каждое, чтобы блок m можно было рассматривать как целое число в диапазоне [0.. n-1]. Обратимость операции шифрования и дешифрования RSA требует доказательства. Из теоремы Эйлера  известно, что для двух целых чисел n и  x, таких, что (n,x)=1, выполняется:

         x^j(n)º1 mod n,                                                                                           (2.2)

где j(n) – функция Эйлера, значение которой равно количеству чисел меньших n и взаимно простых с ним. Об этом говорит сайт https://intellect.icu . Для n=p×q из алгоритма RSA, где p и q – простые числа, можно записать j(n)=(p-1)(q-1).

         Тогда (2.2) можно переписать в виде:

x^(p-1)(q-1)º1 mod n                                                                                      (2.3)

Возведем обе части (2.3) в степень –y:

x^{(-y)(p-1)(q-1)} º 1^(-y) mod n º 1 mod n                                                             (2.4)

         Умножим обе части (2.4) на x:

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

         Но при генерации ключей мы получили e и d такие, что ed º 1 mod (p-1)(q-1), а это означает, что в (2.5) можно заменить 1-y(p-1)(q-1) на ed:

          x^ed mod n = x

         Тогда, если мы возведем шифротекста c=m^e mod n в степень d по модулю n, как мы это и делаем при дешифровании, то получим:

         (c^d ) mod n= (m^e mod n)^d mod n = m^ed mod n = m

         Очевидно, что основная задача криптоаналитика при взломе этого шифра – узнать закрытый ключ d. Для этого он должен выполнить те же действия, что и получатель при генерации ключа – решить в целых числах уравнение    ed + y (p-1)(q-1) =1  относительно d и y. Однако, если получателю известны входящие в уравнение параметры p и q, то криптоаналитик знает только число n – произведение p и q. Следовательно, ему необходимо произвести факторизацию числа n, то есть разложить его на множители. Для решения задачи факторизации к настоящему времени разработано множество алгоритмов: квадратичного решета, обобщенного числового решета, метод эллиптических кривых. Но для чисел большой размерности  это очень трудоемкая задача. Ее трудоемкость можно подтвердить следующими цифрами [11]: для факторизации числа 100D (число с 100 десятичными разрядами) потребовалась вычислительная мощность 7MY (1 MY – величина, равная годовой производительности компьютера, выполняющего один миллион целочисленных инструкций в секунду), для числа 130D – 500MY, для числа 140D – 2000 MY.  Современная криптография к надежным ключам шифрования RSA относит ключи длиной 768, 1024, 2048 бит.

         Необходимо отметить, что математически не была доказана единственность способа восстановления m по  с и e  разложением n на множители. Криптоаналитики не  исключают, что может быть открыт совсем иной способ криптоанализа  RSA, и тогда алгоритм станет абсолютно непригодным для практического использования.

Еще одной проблемой является генерация больших простых чисел для алгоритма. Строгое доказательство простоты сгенерированного случайного числа требует решение той же самой задачи факторизации, поэтому большинство общепринятых тестов устанавливает простоту числа с некоторой вероятностью. Что произойдет, если p или q окажется составным? Тогда у модуля n будет три или более делителей. Соответственно некоторые делители будут меньше рекомендованной величины, что, в свою очередь, открывает возможности для атаки путем факторизации модуля.

Некоторые атаки используют уязвимость протокола использования алгоритма RSA [12]. Важно понимать, что само по себе использование RSA не обеспечивает требуемого уровня безопасности систе­мы. Рассмотрим некоторые возможные атаки на протокол шифрования RSA.

Если злоумышленнику удалось перехватить сообщение c, зашифрованное с помощью откры­того RSA-ключа пользователя А, то для раскрытия m = с^d он сначала выбирает первое случайное число r, меньшее n, и затем, воспользовавшись открытым клю­чом А е, вычисляет

x = r^e mod n,

y = xc mod n,

t = r^-1 mod n.

Если х = r^e mod n , то r= x^dmod n

Далее злоумышленник каким-либо способом вынуждает А закодировать сообщение y на его секретном ключе. А посылает злоумышленнику

u = y^d mod n

Теперь злоумышленник раскрывает m, вычисляя

tu mod n =r^-1y^d mod n = r^-1 x^dc^d mod n =c^d mod n = m

Еще одной известной атакой является атака на основе общего RSA-модуля

Если раздать всем абонентам криптосети одинаковый модуль n, но каждому — свои значения показателей степени (e1, d1), (e2, d2), то при шифро­вании одного и того же сообщения разными показателями степени (при фиксированном модуле) при условии, что  показатели e1 и e2 — взаимно-простые числа, открытый текст может быть раскрыт даже при неизвестных ключах дешифрования. Пусть заданы: m — открытый текст, e₁ и e₂ — два ключа шифрования,n — общий модуль. Шифротекстами сообщения являются:

c₁ = m^e1 mod n,

c₂ = m^e2 mod n,

Криптоаналитик знает n, e₁, e₂, c₁ и c₂. Так как e₁ и e₂ — взаимно-простые числа, то, воспользовавшись расширенным алгоритмом Евклида, можно найти такие числа r и s, что

re₁ + se₂ = 1.

Полагая r отрицательным (или r, или s должно быть отрицательным), можно снова воспользоваться расширенным алгоритмом Евклида для вычисления c₁^-1. Тогда

(c₁^-1)^-rc₂ ^s = (m^e1 mod n)^r (m^e2 mod n)^s = m^e1r+e2s mod n =m mod n.

Таким образом, использование общего для группы пользователей параметра n может отрицательно сказаться на уровне безопасности криптосети.

Еще одно требование к криптопротоколам вытекает из возможности атаки «шифрование коротких сообщений». Известно, что криптосистема RSAобладает низкой криптостойкостью при зашифрованном на малом e коротком сообщении. Действительно, при c = m^e < n открытый текст m может быть восстановлен по шифротексту c при помощи процедуры извлечения корня. Однако меры противодействия также очевидны, — либо открытый ключ eдолжен быть достаточно большим, либо открытый текст не должен быть коротким. Выбор малого e обусловлен соображениями вычислительной эффективности шифрования и проверки подписи. Таким образом, разумный подход заключается в ис­кусственном наращивании коротких открытых текстов («набивки»).

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

         Рассмотрим еще один алгоритм асимметричного кодирования – схему Рабина.

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

Рис.2.16. Схема шифрования алгоритма Рабина

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

         Список алгоритмов асимметричного шифрования на этом, безусловно, не исчерпывается, более полный их перечень приведен в [12]. В заключение обзора хотелось бы отметить еще два алгоритма, которые строятся на иных трудновычислимых задачах. Криптосистема МакЭлиса основана на методах теории помехоустойчивого кодирования. Эта криптосистема использует декодирование кода с исправлением ошибок и использует тот факт, что линейный код в общем случае не имеет полиномиального алгоритма декодирования. Криптосистема на основе эллиптических кривых, использует свойства эллиптической кривой (ЭК), которая представляет собой множество точек на плоскости, удовлетворяющих уравнению:

y² = x³ + ax + b mod p,

Криптостойкость ЭК основана на трудности решения задачи дискретного логарифмирования в группе точек эллиптической кривой над конечным полем. Более подробно криптосистемы на эллиптических кривых будут рассмотрены в главе 4.

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