Rsa что такое
Перейти к содержимому

Rsa что такое

  • автор:

Что такое RSA?

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

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

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

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

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

Алгоритм шифрования RSA

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

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

Рассмотрим алгоритм RSA с практической точки зрения.

  • Возьмем два больших простых числа p and q.
  • Определим n, как результат умножения p on q (n= p*q).
  • Выберем случайное число, которое назовем d. Это число должно быть взаимно простым (не иметь ни одного общего делителя, кроме 1) с результатом умножения (p-1)*(q-1).
  • Определим такое число е, для которого является истинным следующее соотношение (e*d) mod ((p-1)*(q-1))=1.
  • Hазовем открытым ключем числа e и n, а секретным — d и n.
  • разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа M(i)=0,1,2. n-1( т.е. только до n-1).
  • зашифровать текст, рассматриваемый как последовательность чисел M(i) по формуле C(i)=(M(I)^e)mod n.

Чтобы расшифровать эти данные, используя секретный ключ , необходимо выполнить следующие вычисления: M(i) = (C(i)^d) mod n. В результате будет получено множество чисел M(i), которые представляют собой исходный текст.

Следующий пример наглядно демонстрирует алгоритм шифрования RSA:

  • Выберем p=3 and q=11.
  • Определим n= 3*11=33.
  • Hайдем (p-1)*(q-1)=20. Следовательно, d будет равно, например, 3: (d=3).
  • Выберем число е по следующей формуле: (e*3) mod 20=1. Значит е будет равно, например, 7: (e=7).
  • Представим шифруемое сообщение как последовательность чисел в диапозоне от 0 до 32 (незабывайте, что кончается на n-1). Буква А =1, В=2, С=3.

Теперь зашифруем сообщение, используя открытый ключ

C1 = (3^7) mod 33 = 2187 mod 33 = 9;
C2 = (1^7) mod 33 = 1 mod 33 = 1;
C3 = (2^7) mod 33 = 128 mod 33 = 29;

Теперь расшифруем данные, используя закрытый ключ .

M1=(9^3) mod 33 =729 mod 33 = 3(С);
M2=(1^3) mod 33 =1 mod 33 = 1(А);
M3=(29^3) mod 33 = 24389 mod 33 = 2(В);

При публикации статьи установка активной индексируемой гиперссылки на источник — сайт E-NIGMA.RU обязательна!

Все права защищены © 2006–2023

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] -ключи генерируются следующим образом:

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

Gg1.png

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

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

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

Уравнения [math](1)[/math] и [math](2)[/math] , на которых основана схема [math]\mathtt[/math] , определяют взаимно обратные преобразования множества [math]\mathbb_n[/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^ \right)\left( \right)> \pmod

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

\\ & \equiv m\left( 1 \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,[/math]

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

[math] \exp (( c + o(1))k^> \log^>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] ) в сочетании с симметричными алгоритмами.

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

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

Oo1.jpg

Шифрование

  • Взять открытый ключ [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] шифруют лишь этот ключ, таким образом реализуется гибридная криптосистема.

См. также

Примечания

  1. ↑Wikipedia — PGP
  2. ↑Русскоязычная база знаний о Total Commander — DarkCryptTC
  3. ↑DarkCrypt IV description
  4. ↑Wikipedia — AES
  5. ↑Википедиа — IDEA
  6. ↑Википедиа — Serpent
  7. ↑Википедиа — Twofish

Источники информации

  • [math]\mathtt[/math] (cryptosystem)
  • [math]\mathtt[/math]

RSA простыми словами и в картинках

Ассиметричный алгоритм криптографии RSA, датой возникновения концепции которого считается 1976 год сейчас очень активно используется для обмена данными, верификацией источника программного обеспечения и в других сферах, где необходимо обмениваться данными или верифицировать отправителя. Кроме того, он является базовой частью HTTPS протокола, использование которого в России достигло 98% по данным Яндекс.Радара.

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

Но что же это за алгоритм такой и как он работает? В этой статье я постараюсь разложить по полочкам основные принципы его работы и ассиметричной криптографии в целом.

RSA ключи и шифрование данных

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

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

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

Предположим, Боб хочет передать Алисе какое-то сообщение, но лично он это сделать не может, поэтому ему необходимо использовать посредника, например Стива. Однако Боб передаёт Алисе информацию про сюрприз для Стива на его день рождения, так что не может допустить, чтобы Стив это сообщение увидел. И тут ему пригодится протокол RSA.

  1. Перед обменом сообщением, Боб просит у Алисы её открытый ключ
  2. После получения ключа, переданного через Стива, Боб шифрует своё сообщение ключом Алисы
  3. Далее Боб, через Стива, передаёт Алисе зашифрованное сообщение
  4. Алиса расшифровывает сообщение своим закрытым ключом

Таким образом, Стив видел открытый ключ Алисы и зашифрованное сообщение от Боба, но без закрытого ключа Алисы это сообщение не расшифровать. То есть, пусть Стив и держал в руках все передаваемые данные, но он не может узнать, что Боб передал Алисе!

RSA шифрование сообщений

Вы можете задаться вопросом, а почему Стив не может подменить ключ Алисы на свой, расшифровать сообщение, а потом, подглядев его, зашифровать обратно на ключ Алисы? Ещё как может, это называется атака «человек посередине» (Man in the middle (MITM)), и выглядит она следующим образом:

MITM

Но есть ли решение этой проблемы? Да! Chain of Trust, или «Цепочка доверия»

Подпись данных и цепочка доверия

Перед тем как разбирать что такое «Цепочка доверия», нужно знать про ещё одну возможность закрытого ключа – подпись информации. Она осуществляется с помощью закрытого ключа и проверяется открытым.

То есть, если Боб и Алиса заранее обменялись своими открытыми ключами, они могут писать друг другу сообщения и прикреплять к ним некий набор данных. Если взять этот набор данных, открытый ключ и само сообщение, можно проверить действительно ли сообщение было отправлено собеседником и не подменил ли его кто-то по дороге.

RSA подпись данных

С функцией подписи закрытого ключа разобрались, действительно полезная штука! Но как это решает проблему человека по середине, ведь если Боб и Алиса не могут без посредников обменяться открытыми ключами, Стив может подменить их при передаче и постоянно перехватывать сообщения?

А всё просто! Поскольку, с помощью закрытого ключа можно подписать какие-то данные, с его помощью можно подписать и сам открытый ключ.

Если есть кто-то, предположим Грант, которому Боб и Алиса могут доверять и чей открытый ключ у них уже есть, то Грант может подписать их открытые ключи. Таким образом, если Стив попытается подменить открытый ключ Алисы, которая посылает его Бобу, то Боб сразу обнаружит подмену, ведь на ключе не будет подписи Гранта.

Также Грант может подписать открытый ключ Марку, который подпишет открытые ключи Боба и Алисы, создав таким образом ту самую «цепочку доверия».

В реальном мире существуют доверенные корневые центры сертификации (Грант), промежуточные центры (Марк) и конечные получатели (Боб и Алиса).

Chain of Trust

Компрометация ключей и списки отзыва

А теперь предположим, что Алиса оставила на виду свой закрытый ключ, его увидел Стив и теперь может подписывать любые сообщения, а также перехватывать и расшифровывать все данные, которые шифруются на открытый ключ Алисы. Такая проблема называется «Компрометация ключа».

На такой случай, умные люди придумали «список отзыва» (Certificate Revocation List (CRL)), в котором будут публиковаться скомпрометированные ключи, к которым больше нет доверия.

Адрес, где находится такой список отзыва встроен во все сертификаты корневых и промежуточных центров сертификации. То есть, если Алиса заподозрит, что Стив увидел её закрытый ключ, она должна будет немедленно сказать от этом Марку, который опубликует номер её сертификата в своём списке отзыва. Боб со своей стороны, при получении старого сертификата, которым попытается воспользоваться Стив, найдёт запись о его отзыве в списке Марка и будет понимать, что Алиса была скомпрометирована и доверять её старому сертификату уже нельзя.

CRL в сертификате

Под капотом

С базовыми аспектами RSA алгоритма разобрались, теперь давайте заглянем «под капот» и посмотрим, как работает эта магия.

Вся ассиметричная криптография держится на принципе «в одну сторону быстро, в другую неразумно долго».

Например, если мы перемножим числа 592939 и 592967 мы получим число 351593260013. Но как имея только число 351593260013 узнать числа 592939 и 592967? А если каждое из этих двух чисел будут длиной более 1000 знаков? Это называется «сложность задачи факторизации произведения двух больших простых чисел», т.е. в одну сторону просто, а в обратную невероятно сложно.

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

  1. Выбираем два случайных простых числа p и q
  2. Вычисляем их произведение: N = p * q
  3. Вычисляем функцию Эйлера: (N) = (p-1) * (q-1)
  4. Выбираем число e (обычно простое, но необязательно), которое меньше (N) и является взаимно простым с (N) (не имеющих общих делителей друг с другом, кроме 1).
  5. Ищем число d, обратное числу e по модулю (N) .Т.е. остаток от деления (d*e) и (N) должен быть равен 1. Найти его можно через расширенный алгоритм Евклида (под спойлером)

Расширенный алгоритм Евклида

После вычисления x2 и y2 вычисляем d по простой формуле, где x — меньшее из этих двух чисел

После произведённый вычислений, у нас будут:

e и n – открытый ключ

d и n – закрытый ключ

А теперь создадим эти ключи на примере малых простых чисел:

Пусть p = 19, q = 41

Ключи мы с вами вычислили, теперь перейдём к шифрованию сообщений.

Предположим, что Боб спрашивает у Алисы во сколько сегодня вечеринка. Алиса знает, что вечеринка в 21, но что ей нужно сделать чтобы передать это Бобу так, чтобы Стив об этом не узнал?

Для этого Алисе необходимо знать открытый ключ Боба, возьмём его из предыдущих вычислений . Далее ей нужно возвести сообщение в степень e (691) по модулю n (779), а Бобу потом нужно будет возвести полученное от Алисы число в степень d (571) по модулю n (779). Давайте изобразим это наглядно

Заключение

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

Также рекомендую почитать пару интересных статей на тему криптографии от коллег с Хабра:

Первые несколько миллисекунд HTTPS соединения – про то, как работает криптография работает на сайтах

Полное руководство по переходу с HTTP на HTTPS – о том как настроить HTTPS у себя на сайте

Let’s Encrypt выдал миллиард сертификатов – о том как Let’s Encrypt помогает обезопасить интернет

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *