Какие математические функции используются в алгоритме шифрования 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–2024

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

Author24 — интернет-сервис помощи студентам

Столкнулся в тесте с таким вопросом, ответил возведение в степень и модуль, оказалось не правильно (наверное не все правильные выбрал, либо ошибся сам со своими ответами).
Какие же функции есть правильными?

— деление с остатком

— абсолютное значение (модуль числа)

— извлечение квадратного корня

— возведение в степень

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Какие математические функции используются в алгоритме шифрования RSA?
Столкнулся в тесте с таким вопросом, ответил возведение в степень и модуль, оказалось не правильно.

Какие математические функции используются в алгоритме шифрования RSA?
Столкнулся в тесте с таким вопросом, ответил возведение в степень и модуль, оказалось не правильно.

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

Status 418

Эксперт Python

4578 / 2345 / 602
Регистрация: 26.11.2017
Сообщений: 5,265
Записей в блоге: 3
Причем тут Python?
Регистрация: 14.12.2018
Сообщений: 17
В универе учим алгоритм этот. Именно на этом предмете — (Программирование на Python)

Эксперт Python

5418 / 3842 / 1214
Регистрация: 28.10.2013
Сообщений: 9,554
Записей в блоге: 1

ЦитатаСообщение от JonathanHiggs Посмотреть сообщение

Именно на этом предмете

Python это инструмент, а не предмет.
Иди в раздел алгоритмов.
Если бы ты спросил, какой либой в Python это делают — другое дело.

Регистрация: 14.12.2018
Сообщений: 17

Молодой, я назвал «предмет», потому что у меня в универе предметы, предмет — Философия, предмет — Английский язык, предмет — Физика, не думай, что я всё называю предметами из-за своих не знаний в этой теме

87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

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

Какие есть слабые места в алгоритме шифрования побитовый xor с ключом 256 бит?
какие есть слабые места в алгоритме шифрования: побитовый xor с ключом 256 бит? Добавлено через.

Какие основные функции используются для неформатированного доступа к файлу?
Подскажите: какие основные функции используются для неформатированного доступа к файлу? Спасибо!

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

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

Или воспользуйтесь поиском по форуму:

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 помогает обезопасить интернет

Иллюстрация работы RSA на примере

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

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

Итак. Допустим, я хочу получить от вас некие данные. Мы с вам не хотим, чтобы эти данные узнал кто-то, кроме нас. И у нас нет никакой уверенности в надёжности канала передачи данных. Приступим.

Шаг первый. Подготовка ключей

Я должен проделать предварительные действия: сгенерировать публичный и приватный ключ.

  • Выбираю два простых числа. Пусть это будет p=3 и q=7 .
  • Вычисляем модуль — произведение наших p и q : n=p×q=3×7=21 .
  • Вычисляем функцию Эйлера: φ=(p-1)×(q-1)=2×6=12 .
  • Выбираем число e , отвечающее следующим критериям: (i) оно должно быть простое, (ii) оно должно быть меньше φ — остаются варианты: 3, 5, 7, 11, (iii) оно должно быть взаимно простое с φ ; остаются варианты 5, 7, 11. Выберем e=5 . Это, так называемая, открытая экспонента.

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

Мне нужно вычислить число d , обратное е по модулю φ . То есть остаток от деления по модулю φ произведения d×e должен быть равен 1. Запишем это в обозначениях, принятых во многих языках программирования: (d×е)%φ=1 . Или (d×5)%12=1 . d может быть равно 5 ( (5×5)%12=25%12=1 ), но чтобы оно не путалось с e в дальнейшем повествовании, давайте возьмём его равным 17. Можете проверить сами, что (17×5)%12 действительно равно 1 ( 17×5-12×7=1 ). Итак d=17 . Пара — это секретный ключ, его я оставляю у себя. Его нельзя сообщать никому. Только обладатель секретного ключа может расшифровать то, что было зашифровано открытым ключом.

Шаг второй. Шифрование

Теперь пришла ваша очередь шифровать ваше сообщение. Допустим, ваше сообщение это число 19. Обозначим его P=19 . Кроме него у вас уже есть мой открытый ключ: = . Шифрование выполняется по следующему алгоритму:

  • Возводите ваше сообщение в степень e по модулю n . То есть, вычисляете 19 в степени 5 (2476099) и берёте остаток от деления на 21. Получается 10 — это ваши закодированные данные.

Строго говоря, вам вовсе незачем вычислять огромное число «19 в степени 5». При каждом умножении достаточно вычислять не полное произведение, а только остаток от деления на 21. Но это уже детали реализации вычислений, давайте не будем в них углубляться.

Полученные данные E=10 , вы отправляете мне.

Здесь надо заметить, что сообщение P=19 не должно быть больше n=21 . иначе ничего не получится.

Шаг третий. Расшифровка

Я получил ваши данные ( E=10 ), и у меня имеется закрытый ключ = .

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

  • Я делаю операцию, очень похожую на вашу, но вместо e использую d . Возвожу E в степень d : получаю 10 в степени 17 (позвольте, я не буду писать единичку с семнадцатью нулями). Вычисляю остаток от деления на 21 и получаю 19 — ваше сообщение.

Заметьте, никто, кроме меня (даже вы!) не может расшифровать ваше сообщение ( E=10 ), так как ни у кого нет закрытого ключа.

В чём гарантия надёжности шифрования

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

Постараюсь это показать на примере. Давайте разложим на множители число 360:

  • сразу ясно, что оно делится на два (получили 2)
  • оставшееся 180 тоже, очевидно чётное (ещё 2)
  • 90 — тоже чётное (ещё двойка)
  • 45 не делится на 2, но следующая же попытка оказывается успешной — оно делится на три (получили 3)
  • 15 тоже делится на 3
  • 5 — простое.

Мы на каждом шагу, практически без перебора, получали всё новые и новые множители, легко получив полное разложение 360=2×2×2×3×3×5

Давайте теперь возьмём число 361. Тут нам придётся помучиться.

  • оно не чётное
  • три — нет, не делится
  • пять (допустим, мы поступаем умно и перебираем только простые числа, хотя, на практике, поиск больших простых чисел, сам по себе, является сложной задачей) — не подходит
  • семь? — нет.
  • и только 19 даст нам ответ: 361=19×19.

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

А как это всё работает на практике?

Многие читатели спрашивают, как всё это применяется на практике. Давайте рассмотрим чуть более приближенный к жизни пример. Зашифруем и расшифруем слово «КРОТ», предложенное одним из читателей. А заодно, бегло рассмотрим, какие проблемы при этом встречаются и как они решаются.

Сперва сгенерируем ключи с чуть бо́льшими числами. Они не так наглядны, но позволят нам шифровать не только числа от нуля до 20.

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

Мы готовы к шифрованию. Переведём наше слово в цифровое представление. Мы можем взять просто номера букв в алфавите. У нас получится последовательность чисел: 11, 17, 15, 19.

Мы можем зашифровать каждое из этих чисел открытым ключом = и получить шифровку 197, 272, 2, 304. Эти числа можно передать получателю, обладающему закрытым ключом = и он всё расшифрует.

Немного о сложностях

На самом деле, изложенный способ шифрования очень слаб и никогда не используется. Причина проста — шифрование по буквам. Одна и та же буква будет шифроваться одним и тем же числом. Если злоумышленник перехватит достаточно большое сообщение, он сможет догадаться о его содержимом. Сперва он обратит внимание на частые коды пробелов и разделит шифровку на слова. Потом он заметит однобуквенные слова и догадается, как кодируются буквы «a», «и», «o», «в», «к»… Путём недолгого перебора, он вычислит дополнительные буквы по коротким словам, типа «но», «не», «по». И по более длинным словам без труда восстановит все оставшиеся буквы.

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

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

Упрощённо, это выглядит так. Перед шифрованием, мы применяем к сообщению правило: b := (b + a) % n . Где a — предыдущая часть сообщения, а b — следующая. То есть наше сообщение (11, 17, 15, 19) изменяется. 11 остаётся без изменений. 17 превращается в (11 + 17) % 323 = 28 . 15 становится (15 + 28) % 323 = 43 . A 19 превращается в 62.

Последовательность (11, 28, 43, 62) получается «запутанной». Все буквы в ней как бы перемешаны, в том смысле, что на каждый код влияет не одна буква, а все предыдущие.

Тот, кто получит ваше сообщение, должен будет проделать обратную операцию, со знаком «минус»: b := (b — a) % n . И только тогда он получит коды букв.

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

То есть мы можем добавить случайное число в начало и получить (299, 11, 17, 15, 19). После перемешивания получится: 299, 310, 4, 19, 38. После шифрования уже невозможно будет догадаться где была какая буква.

В реальной жизни всё ещё немного сложнее. Блоки, на которые бьётся сообщение длиннее одной буквы. Поэтому, сперва применяются алгоритмы выравнивания, потом алгоритмы разбиения на блоки с перепутыванием, и только потом применяется само RSA-шифрование.

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

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

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

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