Какие математические функции используются в алгоритме шифрования rsa

RSA: от простых чисел до электронной подписи

Выясняем, как и откуда можно получить электронную подпись на примере криптосистемы RSA.

Содержание

Определения и обозначения

Описание криптосистемы RSA

Асимметричные криптографические системы

Шифрование и дешифрование

Получение подписи сообщения по RSA

Электронная подпись документов

Введение

Наверняка вы сталкивались с таким понятием, как «электронная подпись». Если обратиться к федеральному закону, то можно найти следующее её определение:

«Электронная подпись — информация в электронной форме, которая присоединена к другой информации в электронной форме (подписываемой информации) или иным образом связана с такой информацией и которая используется для определения лица, подписывающего информацию»

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

Задача ЭП ясна, теперь хотелось бы увидеть и прочувствовать, что именно скрывается за этими двумя словами. Копаясь дальше в гугле, можно найти довольно много различных алгоритмов создания цифровой подписи (DSA, ГОСТ Р 34.10-2012, RSA-PSS и т.д.), разбираться в которых неподготовленному пользователю сложно.

Спасти эту ситуацию и помочь разобраться в том, что есть ЭП, может криптосистема RSA, разработанная Ривестом, Шамиром и Адлеманом в 1978 году. Она не загромождена безумным количеством алгоритмов и основывается на относительно простой математике. В связи с этим можно шаг за шагом прийти от модульной арифметики к алгоритму создания электронной подписи, чему я и хочу посвятить данную статью.

Теорминимум

(На картинке изображён Лев Ландау, автор «теорминимума», серии экзаменов по теоретической физике)

Сформируем небольшой словарик терминов, которые нам пригодятся далее:

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

Шифртекст – данные, полученные в результате применения шифра к открытому тексту

Шифр – совокупность обратимых преобразований, зависящая от некоторого параметра (ключа)

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

Факторизация – процесс разложения числа на простые множители.

НОД – наибольший общий делитель.

Числа a и b называются взаимно простыми, если НОД этих чисел равен 1.

Функция Эйлера φ(n) – функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним.

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

Как оно устроено

Прежде, чем ~~окунуться в необъятный мир математики~~ рассмотреть, как именно устроена RSA, обратимся к тому, как работают

Асимметричные криптосистемы

Рассмотрим задачу сохранности содержимого посылки при передаче от отправителя к адресату. Вот картинка с многим полюбившимся Алисой и Бобом:

Алиса хочет передать Бобу посылку. Для начала Боб на своей стороне создает уникальные замок и ключ к нему (открытый и закрытый ключ соответственно). Далее, Боб делится с окружающим миром своим замком, чтобы любой желающий отправить ему посылку смог её закрыть. Поскольку ключ от подобного замка один и находится только у Боба, никто, кроме Боба, просмотреть содержимое после защёлкивания замка не сможет. В конце концов, Алиса с помощью полученного замка закрывает посылку и передаёт Бобу, который открывает её своим ключом. Таким образом устроены асимметричные криптографические системы, которой как раз является RSA.

В схеме передачи посылки все объекты вполне материальны. Однако сообщения, которые мы хотим шифровать, являются ничем иным, как последовательностью бит, которую нельзя «закрыть» на физический замок. Таким образом возникают вопросы: что такое ключ и замок? Как Бобу создать ключи? Каким образом ключи связаны и как с их помощью зашифровать сообщение? Здесь нам поможет математика.

Теперь к математике

Асимметричные криптографические системы основаны на так называемых односторонних функциях с секретом. Под односторонней понимается такая функция я y=f(x), которая легко вычисляется при имеющемся x, но аргумент x при заданном значении функции вычислить сложно. Аналогично, односторонней функцией с секретом называется функция y=f(x, k), которая легко вычисляется при заданном x, причём при заданном секрете k аргумент x по заданному y восстановить просто, а при неизвестном k – сложно.

Подобным свойством обладает операция возведения числа в степень по модулю:

Здесь φ(n) – функция Эйлера числа n. Пока условимся, что это работает, далее это будет доказано более строго. Теперь нужно понять, что из это является ключами Боба, а что сообщением. В нашем распоряжении имеются числа c, m, n, e, d.

Давайте посмотрим на первое выражение. Здесь число c получено в результате возведения в степень по модулю числа m. Назовём это действие шифрованием. Тогда становится очевидно, что m выступает в роли открытого текста, а c – шифртекста. Результат c зависит от степени e, в которую мы возводим m, и от модуля n, по которому мы получаем результат шифрования. Эту пару чисел (e, n) мы будем называть открытым ключом. Им Алиса будет шифровать сообщение.

Смотрим на второе действие. Здесь d является параметром, с помощью которого мы получаем исходный текст m из шифртекста c. Этот параметр мы назовём закрытым ключом и выдадим его Бобу, чтобы он смог расшифровать сообщение Алисы.

Что есть что разобрались, теперь перейдём к конкретике, а именно – генерации ключей Боба. Давайте выберем число n такое, что:

где p и q – некоторые разные простые числа. Для такого n функция Эйлера имеет вид:

Такой выбор n обусловлен следующим. Как вы могли заметить ранее, закрытый ключ d можно получить, зная открытый e. Зная числа p и q, вычислить функцию Эйлера не является вычислительно сложной задачей, ровно как и нахождение обратного элемента по модулю. Однако в открытом ключе указано именно число n. Таким образом, чтобы вычислить значение функции Эйлера от n (а затем получить закрытый ключ), необходимо решить задачу факторизации, которая является вычислительно сложной задачей для больших n (в современных системах, основанных на RSA, n имеет длину 2048 бит).

Возвращаемся к генерации ключей. Выберем целое число e:

Для него вычислим число d:

Для отыскания числа, обратного по модулю, можно воспользоваться алгоритмом Евклида.

Мы завершили с этапом генерации ключей. Теперь Боб публикует свой открытый ключ (e, n), прячет закрытый d, а мы переходим к Алисе.

Шифруем, дешифруем.

Возьмём в качестве сообщения число m (m ∈ [1, n − 1]). Чтобы Алисе зашифровать его, необходимо возвести его в степень e по модулю n. Эти числа идут вместе с открытым ключом Боба:

Здесь за с обозначен шифртекст, который Алиса будет должна передать Бобу. Отметим также, что c ∈ [1, n − 1], как и m. Расшифруем шифртекст, возведя его в степень закрытого ключа Боба d:

А теперь ответим на вопрос, почему m ≡ m′ . Ниже я приведу доказательство данного утверждения, но если оно (доказательство) вам не сильно интересно, то можете его пропустить и просто поверить, что это так.

Здесь нам понадобится теорема Эйлера:

Также полезной будет китайская теорема об остатках:

Получаем подпись сообщения

Ещё раз напишем две ключевые формулы шифрования и расшифрования соответственно:

Теперь давайте предположим, что Боб хочет отправить Алисе открытку m от своего имени. У Боба в распоряжении уже имеются два ключа (e, n) и d, которые он сгенерировал по алгоритму, описанному ранее. Поскольку d является закрытым ключом, то можно им воспользоваться как уникальным идентификатором Боба. Давайте «зашифруем» m с помощью d:

Результат данной операции и есть подпись сообщения Боба. Заметим, что подпись напрямую зависит от подписываемого сообщения, а не только от того, что его подписывает Боб. Далее, Алиса получает сообщение m, подпись s и открытый ключ (e, n). По аналогии с расшифрованием, проверка подписи осуществляется возведением подписи s в степень открытой экспоненты e:

Если Алиса получила, что m ≡ m′, то подпись считается правильной.

Дочитавших до этого места хочу поздравить с получением первой цифровой подписи «на бумаге»!

Подпись документов

Рассмотренный алгоритм получения подписи изящен и прост в осознании, однако операция возведения в степень несколько «мешается». Наша текущая задача – подписать объёмный документ. Чтобы сэкономить время, мы не будем подписывать содержимое документа, а прибегнем к помощи хэш-функций (если вы не знаете, что такое хэш-функция, рекомендую почитать википедию). Скажу лишь то, что выходная последовательность хэш-функции имеет небольшую (по сравнению с размером ключей) длину, а также по имеющемуся хэшу нельзя однозначно восстановить исходные данные.

На картинках наглядно показано, в какой момент мы используем хэширование. Создание подписи:

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

Заключение

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

Отмечу, что другие существующие алгоритмы создания ЭП основаны на схожих принципах, поэтому надеюсь, что после прочтения этой статьи вам будет проще разобраться в них. «Следующей по сложности» я обозначу криптосистему Эль-Гамаля, но о ней уже не в этом посте.

Спасибо за внимание!

Источники

Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone

Криптографические методы защиты информации: учеб. пособие / С. М. Владимиров, Э. М. Габидулин, А. И. Колыбельников, А. С. Кшевецкий; под ред. А. В. Уривского. – М.: МФТИ, 2016

Маховенко Е. Б. Теоретико-числовые методы в криптографии — М.: Гелиос АРВ, 2006.

NIST Special Publication 800-57 Part 3 Revision 1

Молдовян Н.А. Теоретический минимум и алгоритмы цифровой подписи. – СПб.: БХВ-Петербург, 2010. — Учебное пособие

Какие математические функции используются в алгоритме шифрования rsa

Криптосистема [math]\mathtt[/math] стала первой системой, пригодной и для шифрования, и для цифровой подписи.

Содержание

Реализация

Алгоритм [math]\mathtt[/math] включает в себя четыре этапа: генерация ключей, передача ключей, шифрование и расшифрование.

Криптографические системы с открытым ключом используют так называемые односторонние функции.

Определение:

Односторонняя функция (англ. one-way function) — математическая функция, которая легко вычисляется для любого входного значения, но задача нахождения аргумента по заданному значению функции относится к классу NP-полных задач.

Под односторонностью понимается не теоретическая однонаправленность, а практическая невозможность вычислить обратное значение, используя современные вычислительные средства, за обозримый интервал времени.

В основу криптографической системы с открытым ключом [math]\mathtt[/math] положена сложность задачи факторизации произведения двух больших простых чисел. Для шифрования используется операция возведения в степень по модулю большого числа. Для дешифрования (обратной операции) за разумное время необходимо уметь вычислять функцию Эйлера от данного большого числа, для чего необходимо знать разложение числа на простые множители. В криптографической системе с открытым ключом каждый участник располагает как открытым ключом (англ. public key), так и закрытым ключом (англ. private key). В криптографической системе [math]\mathtt[/math] каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме [math]\mathtt[/math] образуют «согласованную пару» в том смысле, что они являются взаимно обратными. То есть для любых допустимых пар открытого и закрытого ключей [math](p,s)[/math] существуют соответствующие функции шифрования [math]E_p(x)[/math] и расшифрования [math]D_s(x)[/math] такие, что для любого сообщения [math]m \in M[/math] , где [math]M[/math] — множество допустимых сообщений, [math]m=D_s(E_p(m))=E_p(D_s(m)).[/math]

Создание открытого и секретного ключей

[math]\mathtt[/math] -ключи генерируются следующим образом:

Выбираются два различных случайных простых числа [math]p[/math] и [math]q[/math] заданного размера (например, [math]1024[/math] бита каждое).
Вычисляется их произведение [math]n=p\cdot q[/math] , которое называется модулем.
Вычисляется значение функции Эйлера от числа [math]n[/math] : [math]\varphi(n) = (p-1)\cdot (q-1).[/math]
Выбирается целое число [math]e[/math] ( [math]1 \lt e \lt \varphi(n)[/math] ), взаимно простое со значением функции [math]\varphi(n)[/math] . Обычно в качестве [math]e[/math] берут простые числа, содержащие небольшое количество единичных бит в двоичной записи.
- Число [math]e[/math] называется открытой экспонентой (англ. public exponent)
- Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в [math]e[/math] .
- Слишком малые значения [math]e[/math] , например [math]3[/math] , потенциально могут ослабить безопасность схемы [math]\mathtt[/math] .
Вычисляется число [math]d[/math] , мультипликативно обратное к числу [math]e[/math] по модулю [math]\varphi(n)[/math] , то есть число, удовлетворяющее сравнению: [math]d\cdot e \equiv 1 \pmod<\varphi(n)>.[/math] Примечание Сравнеие двух целых чисел по модулю натурального числа [math]m[/math] — математическая операция, позволяющая ответить на вопрос о том, дают ли два выбранных целых числа при делении на [math]m[/math] один и тот же остаток. Любое целое число при делении на [math]m[/math] дает один из [math]m[/math] m возможных остатков: число от [math]0[/math] до [math]m-1[/math] .
- Число [math]d[/math] называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.
Пара [math]\left\< e, n \right\>[/math] публикуется в качестве открытого ключа [math]\mathtt[/math] (англ. [math]\mathtt[/math] public key).
Пара [math]\left\< d, n \right\>[/math] играет роль закрытого ключа [math]\mathtt[/math] (англ. [math]\mathtt[/math] private key) и держится в секрете.

Определение:

Случайное простое число (англ. random prime numbers) — в криптографии, простое число, содержащее в двоичной записи заданное количество битов.

Передача ключей

Предположим, что Боб хочет отправить Алисе информацию . Если они решат использовать [math]\mathtt[/math] , Боб должен знать открытый ключ Алисы для того чтобы зашифровать сообщение, а Алиса должна использовать свой закрытый ключ для расшифрования сообщения. Чтобы позволить Бобу отправлять свои зашифрованные сообщения, Алиса передает свой открытый ключ Бобу через надежный, но не обязательно секретный маршрут. Закрытый ключ Алисы никогда никому не передается.

Шифрование

Предположим, Боб хочет послать Алисе сообщение [math]m[/math] . Сообщениями являются целые числа в интервале от [math]0[/math] до [math]n — 1[/math] , то есть [math]m \in \mathbb_[/math] . Алгоритм:

Взять открытый ключ [math](e,n)[/math] Алисы
Взять открытый текст [math]m[/math]
Зашифровать сообщение с использованием открытого ключа Алисы: [math]c = E(m) = m^e \mod n

Расшифрование

Принять зашифрованное сообщение [math]c[/math]
Взять свой закрытый ключ [math](d,n)[/math]
Применить закрытый ключ для расшифрования сообщения: [math]m = D(c) = c^d \mod n

Корректность схемы [math]\mathtt[/math]

Действительно, для [math]\forall m \in \mathbb_[/math]

[math]\forall m \in \mathbb_: m^ \equiv m \pmod

[/math] .

Возможны два случая:

[math]m \not\equiv 0 \pmod
[/math] .

Поскольку числа [math]e[/math] и [math]d[/math] являются взаимно обратными относительно умножения по модулю [math]\varphi(n)=(p-1)(q-1)[/math] , то есть

[math]ed=1+k(p-1)(q-1)[/math] для некоторого целого [math]k[/math] ,

[math]\begin m^ & \equiv m^ <1 + k\left(

\right)\left( \right)> \pmod

\\ & \equiv m\left( > \right)^ \right)> \pmod

\\ & \equiv m\left( 1 \right)^ \right)> \pmod

\equiv m \pmod

\end[/math]

где второе тождество следует из теоремы Ферма.

Рассмотрим второй случай:

[math]m^ \equiv 0 \pmod

\equiv m \pmod

[/math]

Таким образом, при всех [math]m[/math] выполняется равенство

[math]m^ \equiv m \pmod

[/math]

Аналогично можно показать, что:

[math]\forall m \in \mathbb_: m^ \equiv m \pmod[/math] .

Криптографическая стойкость

Стойкость алгоритма основывается на сложности вычисления обратной функции к функции шифрования

[math]c = E(m) = m ^ e \mod n[/math] .

Для вычисления [math]m[/math] по известным [math]c, e, n[/math] нужно найти такой [math]d[/math] , чтобы

[math]e \cdot d \equiv 1 \pmod<\varphi(n)>,[/math]

Вычисление обратного элемента по модулю не является сложной задачей, однако злоумышленнику неизвестно значение [math]\varphi(n)[/math] . Для вычисления функции Эйлера от известного числа [math]n[/math] необходимо знать разложение этого числа на простые множители. Нахождение таких множителей и является сложной задачей, а знание этих множителей — «потайной дверцей» (англ. backdoor), которая используется для вычисления [math]d[/math] владельцем ключа. Существует множество алгоритмов для нахождения простых сомножителей, факторизации, самый быстрый из которых на сегодняшний день — общий метод решета числового поля, скорость которого для k-битного целого числа составляет

[math] \exp (( c + o(1))k^<\frac<1><3>> \log^<\frac<2><3>>k)[/math] для некоторого [math]c \lt 2[/math] .

В [math]2010[/math] году группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта [math]\mathtt[/math] длиной [math]768[/math] бит. Нахождение простых сомножителей осуществлялось общим методом решета числового поля. По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только [math]\mathtt[/math] -ключи длиной [math]1024[/math] бита и более. Причём от шифрования ключом длиной в [math]1024[/math] бит стоит отказаться в ближайшие три-четыре года. С [math]31[/math] декабря [math]2013[/math] года браузеры Mozilla перестали поддерживать сертификаты удостоверяющих центров с ключами [math]\mathtt[/math] меньше [math]2048[/math] бит.

Применение

Система [math]\mathtt[/math] используется для защиты программного обеспечения и в схемах цифровой подписи. Также она используется в открытой системе шифрования PGP [1] и иных системах шифрования (к примеру, DarkCryptTC [2] и формат xdc [3] ) в сочетании с симметричными алгоритмами.

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

Алгоритм шифрования сеансового ключа выглядит следующим образом:

Шифрование

Взять открытый ключ [math](e,n)[/math] Алисы
Создать случайный сеансовый ключ [math]m[/math]
Зашифровать сеансовый ключ с использованием открытого ключа Алисы: [math]c = E(m) = m^e \mod n[/math]
Расшифровать сообщение [math]C[/math] с помощью сеансового ключа симметричным алгоритмом: [math]M_A = D_m(C)[/math]

Расшифрование

Принять зашифрованный сеансовый ключ Боба [math]c[/math]
Взять свой закрытый ключ [math](d,n)[/math]
Применить закрытый ключ для расшифровывания сеансового ключа: [math]m = D(c) = c^d \mod n[/math]
Зашифровать сообщение [math]M_A[/math] с помощью сеансового ключа симметричным алгоритмом: [math]C = E_m(M_A)[/math]

Минусы

Алгоритм [math]\mathtt[/math] намного медленнее, чем AES [4] и другие алгоритмы, использующие симметричные блочные шифры.

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

Из-за низкой скорости шифрования (около [math]30[/math] кбит/с при [math]512[/math] битном ключе на процессоре [math]2[/math] ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным сеансовым ключом (например, IDEA [5] , Serpent [6] , Twofish [7] ), а с помощью [math]\mathtt[/math] шифруют лишь этот ключ, таким образом реализуется гибридная криптосистема.

Алгоритм RSA

Криптография – специальная система изменения обычного письма, используемая с целью сделать текст понятным лишь для ограниченного числа лиц, знающих эту систему [1].

Криптография – наука о защите информации с использованием математических методов [2].

Современная криптография включает в себя:

системы электронной цифровой подписи (ЭЦП);

получение скрытой информации;

Симметричное шифрование — симметричными называются алгоритмы, в которых для шифрования и дешифрования используется один и тот же (известный только отправителю и получателю) секретный ключ.

Распространенные алгоритмы симметричного шифрования:

AES (англ. Advanced Encryption Standard) — американский стандарт шифрования;

ГОСТ 28147-89 — отечественный стандарт шифрования данных;

DES (англ. Data Encryption Standard) — стандарт шифрования данных в США до AES;

3DES (Triple-DES, тройной DES);

IDEA (англ. International Data Encryption Algorithm);

SEED — корейский стандарт шифрования данных;

Camellia — сертифицированный для использовании в Японии шифр;

XTEA — наиболее простой в реализации алгоритм [3].

Асимметричные криптоалгоритмы призваны в первую очередь устранить основной недостаток симметричных криптосистем – сложность управления и распространения ключей.

Основой всех асимметричных криптоалгоритмов является большая вычислительная сложность восстановления открытого текста без знания закрытого ключа.

Примеры асимметричных криптоалгритмов:

RSA – Rivest, Shamir, Adelman – основан на сложности задачи разложения на множители больших чисел за короткое время;

DSA – Digital Signature algorithm, стандарт США;

ГОСТ Р 34.10 – 94, 2001, стандарты РФ [4].

В данном реферате подробно рассмотрим ассиметричный криптоалгоритм шифрования – алгоритм RSA.

Основная часть

Алгоритм RSA (буквенная аббревиатура от фамилий Rivest, Shamir и Adleman) – криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел. Криптосистема RSA стала первой системой, пригодной и для шифрования, и для цифровой подписи.

История создания

Опубликованная в ноябре 1976 года статья Уитфилда Диффи и Мартина Хеллмана «Новые направления в криптографии» перевернула представление о криптографических системах, заложив основы криптографии с открытым ключом. Разработанный впоследствии алгоритм Диффи — Хеллмана позволял двум сторонам получить общий секретный ключ, используя незащищенный канал связи. Однако этот алгоритм не решал проблему аутентификации. Без дополнительных средств пользователи не могли быть уверены, с кем именно они сгенерировали общий секретный ключ.

Изучив эту статью, трое учёных Рональд Ривест (англ. Ronald Linn Rivest), Ади Шамир (англ. Adi Shamir) и Леонард Адлеман (англ. Leonard Adleman) из Массачусетского Технологического Института (MIT) приступили к поискам математической функции, которая бы позволяла реализовать сформулированную Уитфилдом Диффи и Мартином Хеллманом модель криптографической системы с открытым ключом. После работы над более чем 40 возможными вариантами, им удалось найти алгоритм, основанный на различии в том, насколько легко находить большие простые числа и насколько сложно раскладывать на множители произведение двух больших простых чисел, получивший впоследствии название RSA. Система была названа по первым буквам фамилий её создателей.

Описание алгоритма

Первым этапом любого асимметричного алгоритма является создание пары ключей – открытого и закрытого и распространение открытого ключа «по всему миру».

Создание ключей

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

Выбираются два очень больших простых числа and .

Вычисляется их произведение , которое называется модулем.

Вычисляется значение функции Эйлера от числа :

Выбирается произвольное число ( ), взаимно простое со значением функции .

Число называется открытой экспонентой

С помощью алгоритма Евклида вычисляется число , которое удовлетворяет условию

Пара публикуется в качестве открытого ключа RSA.

Пара играет роль закрытого ключа RSA и держится в секрете.

Шифрование и расшифрование

Предположим, отправитель хочет послать получателю сообщение .

Сообщениями являются целые числа в интервале от 0 до , т.е . . На рисунке 1 представлена схема алгоритма RSA.

Рисунок 1 – Схема алгоритма RSA

Алгоритм Отправителя:

Взять открытый ключ получателя

Взять открытый текст

Зашифровать сообщение с использованием открытого ключа получателя:

Алгоритм Получателя:

Принять зашифрованное сообщение

Взять свой закрытый ключ

Применить закрытый ключ для расшифрования сообщения:

Уравнения (1) и (2), на которых основана схема RSA, определяют взаимно обратные преобразования множества [5].

Пример использования

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

Какие математические функции используются в алгоритме шифрования rsa

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

Криптосистема RSA стала первой системой, пригодной и для шифрования, и для цифровой подписи. Алгоритм используется в большом числе криптографических приложений, включая PGP, S/MIME, TLS/SSL, IPSEC/IKE и других. [1]

Содержание

История

Опубликованная в ноябре 1976 года статья Уитфилда Диффи и Мартина Хеллмана «Новые направления в криптографии» (англ. New Directions in Cryptography ) [2] перевернула представление о криптографических системах, заложив основы криптографии с открытым ключом. Разработанный впоследствии алгоритм Диффи — Хеллмана позволял двум сторонам получить общий секретный ключ, используя незащищенный канал связи. Однако этот алгоритм не решал проблему аутентификации. Без дополнительных средств пользователи не могли быть уверены, с кем именно они сгенерировали общий секретный ключ.

Изучив эту статью, трое учёных Рональд Ривест, Ади Шамир и Леонард Адлеман из Массачусетского технологического института (MIT) приступили к поискам математической функции, которая бы позволяла реализовать сформулированную Уитфилдом Диффи и Мартином Хеллманом модель криптографической системы с открытым ключом. После работы над более чем 40 возможными вариантами, им удалось найти алгоритм, основанный на различии в том, насколько легко находить большие простые числа и насколько сложно раскладывать на множители произведение двух больших простых чисел, получивший впоследствии название RSA. Система была названа по первым буквам фамилий её создателей.

В августе 1977 года в колонке «Математические игры» Мартина Гарднера в журнале Scientific American, с разрешения Рональда Ривеста [3] появилось первое описание криптосистемы RSA. [4] Читателям также было предложено дешифровать английскую фразу, зашифрованную описанным алгоритмом:

9686 1477 8829 7431 0816 3569 8962 1829

9613 1409 0575 9874 2982 3147 8013 9451

7546 2225 9991 6951 2514 6622 3919 5781

2206 4355 1245 2093 5708 8839 9055 5154

В качестве открытых параметров системы были использованы числа n= 1143816. 6879541 (129 десятичных знаков, 425 бит, также известно как RSA-129 и e=9007. За расшифровку была обещана награда в 100 долларов США. По заявлению Ривеста, для факторизации числа потребовалось бы более 40 квадриллионов лет. [5] [1] Однако чуть более чем через 15 лет, 3 сентября 1993 года было объявлено о старте проекта распределённых вычислений с координацией через электронную почту по нахождению сомножителей числа RSA-129 и решению головоломки. На протяжении полугода более 600 добровольцев из 20 стран жертвовали процессорное время 1600 машин (две из которых были факс-машинами). В результате были найдены простые множители и расшифровано исходное сообщение, которое представляет собой фразу «THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE (англ.)» («Волшебные слова — это брезгливый ягнятник»). [6] [7] Полученную награду победители пожертвовали в фонд свободного программного обеспечения.

После публикации Мартина Гарднера полное описание новой криптосистемы любой желающий мог получить, выслав по почте запрос Рональду Ривесту, с приложенным конвертом с обратным адресом и марками на 35 центов. [4] Полное описание новой криптосистемы было опубликовано в журнале «Communications of the ACM» в феврале 1978 года. [8]

Заявка на патент была подана 14 декабря 1977 года, в качестве владельца был указан MIT. Патент 4405829 был выдан 20 сентября 1983 года, а 21 сентября 2000 года срок его действия истёк. [9] Однако за пределами США у изобретателей патента на алгоритм не было, так как в большинстве стран его необходимо было получить до первой публикации. [10]

В 1982 году Ривест, Шамир и Адлеман организовали компанию RSA Data Security (англ.) (в настоящий момент — подразделение EMC). В 1989 году RSA, вместе с симметричным шифром DES, упоминается в RFC 1115, тем самым начиная использование алгоритма в зарождающейся сети Internet [11] , а в 1990 году использовать алгоритм начинает министерство обороны США. [12]

В ноябре 1993 года открыто публикуется версия 1.5 стандарта PKCS1 (англ.), описывающего применение RSA для шифрования и создания электронной подписи. Последние версии стандарта также доступны в виде RFC (RFC 2313 — 1.5, 1993 год; RFC 2437 — 2.0, 1998 год; RFC 3447 — 2.1, 2002 год).

В декабре 1997 года была обнародована информация, согласно которой британский математик Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал криптосистему аналогичную RSA в 1973 году. [13]

Описание алгоритма

Введение

Криптографические системы с открытым ключом используют так называемые односторонние функции, которые обладают следующим свойством:

Если известно , то вычислить относительно просто
Если известно , то для вычисления нет простого (эффективного) пути.

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

В криптографической системе с открытым ключом каждый участник располагает как открытым ключом (англ. public key ), так и закрытым ключом (англ. private key ). В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме RSA образуют «согласованную пару» в том смысле, что они являются взаимно обратными, то есть:

$\forall$ сообщения $m \in M$ , где — множество допустимых сообщений $\forall$ допустимых открытого и закрытого ключей и $\exist\,$ соответствующие функции шифрования E_p(x) и расшифрования D_s(x) , такие что m=D_s(E_p(m))=E_p(D_s(m)).

Алгоритм создания открытого и секретного ключей

RSA-ключи генерируются следующим образом: [14]

Выбираются два различных случайных простых числаи заданного размера (например, 1024 бита каждое).
Вычисляется их произведение $n=p\cdot q$ , которое называется модулем.
Вычисляется значение функции Эйлера от числа : $\varphi(n) = (p-1)(q-1).$
Выбирается целое число (), взаимно простое со значением функции . Обычно в качестве берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые числа Ферма 17, 257 или 65537.
- Число называется открытой экспонентой (англ. public exponent )
- Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в .
- Слишком малые значения , например 3, потенциально могут ослабить безопасность схемы RSA. [15]
Вычисляется число , мультипликативно обратное к числу по модулю $\varphi(n)$ , то есть число, удовлетворяющее условию: $d\cdot e \equiv 1 \mod <\varphi(n)>.» width=»» height=»» /> <ul> <li>Число <img decoding=$ называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.
Пара $\left\< e, n \right\>» width=»» height=»» /> публикуется в качестве открытого ключа RSA (англ. RSA public key ).</li> <li>Пара <img decoding=$

Предположим, Боб хочет послать Алисе сообщение .

Сообщениями являются целые числа в интервале от до , т.е $m \in \mathbb<Z>_<n>\,» width=»» height=»» />. <ul> <li>Взять открытый ключ<img decoding=$ Алисы
Взять открытый текст
Зашифровать сообщение с использованием открытого ключа Алисы: $c = E(m) = m^e \mod n </ul> <ul> <li>Принять зашифрованное сообщение <img decoding=$
Взять свой закрытый ключ
Применить закрытый ключ для расшифрования сообщения: и , на которых основана схема RSA, определяют взаимно обратные преобразования множества
- .
Поскольку числа и являются взаимно обратными относительно умножения по модулю $\varphi(n)=(p-1)(q-1)$ , т.e

для некоторого целого ,

$\begin<align>m^ <ed>& \equiv m^ <1 + k\left( \right)\left( <q - 1>\right)> & \equiv & \mod p \\ & \equiv m\left( <m^ > \right)^ <k\left( <q - 1>\right)> & \equiv & \mod p \\ & \equiv m\left( 1 \right)^ <k\left( <q - 1>\right)> & \equiv m & \mod p \end<align>» width=»» height=»» /> где второе тождество следует из теоремы Ферма. <ul> <li>Рассмотрим второй случай:</li> </ul> <img decoding=$

Таким образом, при всех выполняется равенство

$m^<ed>\equiv m \mod p» width=»» height=»» /> Аналогично можно показать, что: <img decoding=$ Этап Описание операции Результат операции Генерация ключей Выбрать два простых числа , Вычислить модуль $n = p \cdot q = 3557 \cdot 2579 = 9173503$ Вычислить функцию Эйлера $\varphi(n) = (p-1) (q-1) = 9167368$ Выбрать открытую экспоненту Вычислить секретную экспоненту $d = e^<-1>\mod \varphi(n)» width=»» height=»» /> <img decoding=$ Опубликовать открытый ключ $\<e, n\>= \<3,9173503 \>» width=»» height=»» /></td> </tr> <tr> <td>Сохранить закрытый ключ</td> <td> <img decoding=$ Шифрование Выбрать текст для зашифровки Вычислить шифротекст $\begin<align>c &= E(m) \\ &= m^e \mod n \\ &= 111111^3 \mod 9173503 \\ &= 4051753 \end<align>» width=»» height=»» /></td> </tr> <tr> <th>Расшифрование</th> <td>Вычислить исходное сообщение</td> <td> <img decoding=$ ) нужно отправить Бобу (стороне ) сообщение , подтверждённое электронной цифровой подписью.
- Взять открытый текст
- Создать цифровую подпись с помощью своего секретного ключа $\left\< d, n \right\>» width=»» height=»» />:</li> </ul> <ul> <li>Передать пару <img decoding=$ и
Поскольку цифровая подпись обеспечивает как аутентификацию автора сообщения, так и подтверждение целостности содержимого подписанного сообщения, она служит аналогом подписи, сделанной от руки в конце рукописного документа.

Важное свойство цифровой подписи заключается в том, что её может проверить каждый, кто имеет доступ к открытому ключу её автора. Один из участников обмена сообщениями после проверки подлинности цифровой подписи может передать подписанное сообщение ещё кому-то, кто тоже в состоянии проверить эту подпись. Например, сторона $A\,$ может переслать стороне $B\,$ электронный чек. После того как сторона $B\,$ проверит подпись стороны $A\,$ на чеке, она может передать его в свой банк, служащие которого также имеют возможность проверить подпись и осуществить соответствующую денежную операцию.

Заметим, что подписанное сообщение не зашифровано. Оно пересылается в исходном виде и его содержимое не защищено от нарушения конфиденциальности. Путём совместного применения представленных выше схем шифрования и цифровой подписи в системе RSA можно создавать сообщения, которые будут и зашифрованы, и содержать цифровую подпись. Для этого автор сначала должен добавить к сообщению свою цифровую подпись, а затем — зашифровать получившуюся в результате пару (состоящую из самого сообщения и подписи к нему) с помощью открытого ключа принадлежащего получателю. Получатель расшифровывает полученное сообщение с помощью своего секретного ключа [16] . Если проводить аналогию с пересылкой обычных бумажных документов, то этот процесс похож на то, как если бы автор документа поставил под ним свою печать, а затем положил его в бумажный конверт и запечатал, с тем чтобы конверт был распечатан только тем человеком, кому адресовано сообщение.

Скорость работы алгоритма RSA

Поскольку генерация ключей происходит значительно реже операций, реализующих шифрование, расшифрование, а также создание и проверку цифровой подписи, задача вычисления $a=b^c \mod n$ представляет основную вычислительную сложность. Эта задача может быть разрешена с помощью алгоритма быстрого возведения в степень. С использованием этого алгоритма для вычисления $m^e \mod n$ требуется $O\left( \ln e \right)$ операций умножения по модулю [17] .
- представим в двоичной системе счисления:
- положим и затем для $i = 1, \dots, k$ вычислим
- найденное $M_k \,$ и будет искомым значением $M^e \bmod n \,$
Т. к. каждое вычисление на шаге 2 требует не более трёх умножений по модулю $n \,$ и этот шаг выполняется $k \le \log_2 e \,$ раз, то сложность алгоритма может быть оценена величиной $O( \ln e) \,$ .

Чтобы проанализировать время выполнения операций с открытым и закрытым ключами, предположим, что открытый ключ $\left\< e, n \right\>» width=»» height=»» /> и закрытый ключ <img decoding=$ , $\log_2 d \le \beta$ . Тогда в процессах их применения выполняется соответственно $O \left( 1 \right)$ и $O \left( \beta \right)$ умножений по модулю.

Таким образом время выполнения операций растёт с увеличением количества ненулевых битов в двоичном представлении открытой экспоненты e. Чтобы увеличить скорость шифрования, значение e часто выбирают равным 17, 257 или 65537 — простым числам, двоичное представление которых содержит лишь две единицы: 17₁₀=10001₂, 257₁₀=100000001₂, 65537₁₀=10000000000000001₂ (простые числа Ферма).

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

Алгоритм RSA намного медленнее чем AES и другие алгоритмы блочного шифрования.

Криптоанализ RSA [18]

Стойкость алгоритма основывается на сложности вычисления обратной функции к функции шифрования

$c = E(m) = m ^ e \mod n$

.

Для вычисления по известным нужно найти такой , чтобы

$e \cdot d \equiv 1 \pmod<\varphi(n)>,» width=»» height=»» /> <img decoding=$ . Для вычисления функции Эйлера от известного числа необходимо знать разложение этого числа на простые множители. Нахождение таких множителей и является сложной задачей, а знание этих множителей — «потайной дверцей» (англ. backdoor ), которая используется для вычисления владельцем ключа. Существует множество алгоритмов для нахождения простых сомножителей, так называемой факторизации, самый быстрый из которых на сегодняшний день — общий метод решета числового поля, скорость которого для k-битного целого числа составляет

$\exp (( c + o(1))k^<\frac<1><3>> \log^<\frac<2><3>>k)» width=»» height=»» /> для некоторого <img decoding=$ .

В 2010 году группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта RSA длиной 768 бит. Нахождение простых сомножителей осуществлялось общим методом решета числового поля. [19] По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только RSA-ключи длиной 1024 бита и более. Причём от шифрования ключом длиной в 1024 бит стоит отказаться в ближайшие три-четыре года. [20]

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

Атаки на алгоритм RSA

Атака Винера на RSA

В некоторых приложениях требуется ускорить процесс шифрования в алгоритме RSA. Поэтому выбирается небольшая шифрующая экспонента. В случае когда шифрующая экспонента $d < N^<\frac<1><4>>» width=»» height=»» /> можно определить <img decoding=$ за полиномиальное время с помощью атаки Винера, [21] опирающейся на непрерывные дроби.

$\alpha \in \mathbb R$

По вещественному числу определим последовательности:

$\alpha_0 = \alpha, p_0 = q_0 = 1, p_1 = a_0a_1 + 1, q_1 = a_1,$
$\alpha_i = \lfloor \alpha_i \rfloor, \alpha_<i+1>= \frac<1><\alpha_i - a_i>,» width=»» height=»» /> <img decoding=$

Целые числа называются непрерывной дробью, представляющей $\alpha,$ а рациональные числа $\frac<p_i> <q_i>-» width=»» height=»» /> подходящими дробями. Каждая из подходящих дробей несократима, а скорость роста их знаменателей сравнима с показательной. Один из важных результатов теории непрерывных дробей: Если несократимая дробь <img decoding=$ в непрерывную дробь.

Пусть у нас есть модудь причём Допустим нападающему известна шифрующая экспонента E, обладающая свойством
$Ed = 1 (mod \varphi),$
где $\varphi = \varphi (N) = (p - 1)(q - 1).$ Будем также считать, что $E < \varphi,$ поскольку это выполнено в большинстве приложений. Из предположений следует, что
$Ed - k\varphi = 1.$
Следовательно,

$\left|\frac<E> <\varphi>— \frac<k><d>\right| = \frac<1><d\varphi>.» width=»» height=»» /> <img decoding=$ очевидно, Кроме того, так как предполагалось, что $d < \frac<1><4>N^<\frac<1><4>>.» width=»» height=»» /> Значит, <img decoding=$ то $\frac<k> <d>-» width=»» height=»» /> подходящая дробь в разложении дроби <img decoding=$

для некоторого случайного числа Получив равенство, найдём Общее число подходящих дробей, которое придётся проверить оценивается как

Обобщённая атака Винера

Атака Винера, описанная выше, возможна лишь в том случае, когда атакующему известно о неравенстве

$d \le \frac<1> <3>N^<\frac<1><4>>,» width=»» height=»» /> где <img decoding=$ — секретная экспонента, а — модуль RSA. Бонех и Дерфи, используя двумерный аналог теоремы Копперсмита, смогли обобщить атаку Винера [21] на случай, когда

$d \le N^<0,292>.» width=»» height=»» /> <h3>Применение RSA</h3> Система RSA используется для защиты программного обеспечения и в схемах цифровой подписи. Также она используется в открытой системе шифрования PGP и иных системах шифрования (к примеру, DarkCryptTC и формат xdc) в сочетании с симметричными алгоритмами. Из-за низкой скорости шифрования (около 30 кбит/с при 512 битном ключе на процессоре 2 ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным ключом (сеансовый ключ), а с помощью RSA шифруют лишь этот ключ, таким образом реализуется гибридная криптосистема. Такой механизм имеет потенциальные уязвимости ввиду необходимости использовать криптостойкий генератор случайных чисел для формирования случайного сеансового ключа симметричного шифрования и эффективно противостоящий атакам симметричный криптоалгоритм (в данное время широкое применение находят AES, IDEA, Serpent, Twofish). Алгоритм шифрования сеансового ключа выглядит следующим образом [16] : <ul> <li>Взять открытый ключ<img decoding=$ Алисы
Создать случайный сеансовый ключ
Зашифровать сеансовый ключ с использованием открытого ключа Алисы: $c = E(m) = m^e \mod n </ul> <ul> <li>Принять зашифрованный сеансовый ключ Боба <img decoding=$
Взять свой закрытый ключ
Применить закрытый ключ для расшифрования сеансового ключа: $m = D(c) = c^d \mod n </ul> Далее оба участника шифруют свои сообщения с помощью одного сеансового ключа. <div class='yarpp yarpp-related yarpp-related-website yarpp-template-list'>  <div>Похожие публикации:</div><ol> <li><a href=$ Keeper security что это за программа
Как перенести ссылку в ворде на следующую строку
Как разбить число на цифры в excel
Как установить rusvpn на андроид