Программа rsa что это

Содержание

Программирование на C, C# и Java

Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы

Алгоритм RSA

В этой статье рассмотрим еще один один алгоритм шифрования — алгоритм RSA. Будет приведено описание и программная реализация на языке программирования C#.

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

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

mod — операция взятия остатка от деления.

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

Шаги алгоритма RSA

Теперь опишем последовательность шагов алгоритма RSA:

выбрать два больших простых числа p и q;
вычислить: n = p ⋅ q, m = (p — 1) ⋅ (q — 1);
выбрать случайное число d, взаимно простое с m;
определить такое число e, для которого является истинным выражение: (e ⋅ d) mod (m) = 1;
числа e и n — это открытый ключ, а числа d и n — это закрытый ключ;

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

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

разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа M(i);

Обычно блок берут равным одному символу и представляют этот символ в виду числа — его номера в алфавите или кода в таблице символов (например ASCII или Unicode).

шифрование алгоритмом RSA производится по формуле: C(i) = (M(i) e ) mod n;
расшифровка сообщения производится с помощью формулы: M(i) = (C(i) d ) mod n.

Алгоритм RSA. Программная реализация

Программа для шифрования алгоритмом RSA имеет интерфейс, представленный на рисунке 1.

RSA - Пользовательский интерфейс программы

Рисунок 1. Пользовательский интерфейс программы

В программе будем использовать следующий алфавит:

Источник: vscode.ru

Основы шифрования (часть 2) — Алгоритм RSA

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

Теперь по шагам рассмотрим процесс шифрования и дешифрования:

Чтобы зашифровать сообщение, используем формулу E = m^e mod n (m – сообщение).
Чтобы расшифровать сообщение, используем формулу E ^ d mod n.

Доказательство того, что Дешифровка( Шифровка ( M ) ) = M приводится в Википедии. Здесь мы еще больше погружаемся в математику и доказательство теорем. Если вы не особо подкованы в этой области, просто попробуйте позапускать скрипт с различными ключами и сообщениями и убедитесь, что все работает корректно.

RSA алгоритм. Шифровка. Информационная безопасность, криптография, тайнопись. Простые числа.

Рискну предположить, что многим из вас интересно, как взломать систему, построенную на основе алгоритма RSA. Злоумышленник знает числа n и e. Если взломщик сможет найти число t, то вычислит секретный ключ. Задача заключается в том, чтобы факторизовать публичный ключ. Однако целочисленная факторизация – довольно сложная задача, и именно поэтому алгоритм RSA довольно устойчив. Возможно, когда появятся квантовые машины, вычислить секретный ключ не будет составлять особого труда, но сейчас достаточной длинный ключ сможет защитить наши данные.

Дополнительные размышления

При чтении статьи у вас, возможно, возник следующий вопрос: «Как мне удостовериться в том, что полученный публичный ключ именно того человека, которому я хочу отослать сообщение?». Если мы можем обнародовать публичный ключ, то с таким же успехом могли бы поделиться и секретным ключом. Более того, я не могу сходить в офис Амазона и получить от них публичный ключ.

Я веду к тому, что мне нужно получить этот ключ каким-то образом. Инфраструктура открытых ключей (Public Key Infrastructure, PKI) – технология, позволяющая управлять всеми этими ключами. Мы используем шифрование для подтверждения наших ключей, предназначенных для шифрования (получается замкнутый круг). Рассмотреть эту проблему в рамках одной статьи не получится. Если вы хотите узнать подробности, гугл вам в помощь.

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

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

Надеюсь, вы подчерпнули для себя нечто новое. Шифруйте и подписывайте свои сообщения!

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

Источник: www.securitylab.ru

Иллюстрация работы 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 , вы отправляете мне.

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

Я получил ваши данные ( 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. Надесь, удалось.

Источник: www.michurin.net

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

Получаем свою первую электронную подпись по алгоритму RSA.

Содержание

Введение
Определения и обозначения
Описание криптосистемы RSA

Асимметричные криптографические системы
Генерация ключей
Шифрование и дешифрование
Получение подписи сообщения по RSA

Введение

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

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

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

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

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

Теорминимум

(На картинке изображён Лев Ландау, автор «теорминимума»)

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

Открытый текст – данные, подлежащие шифрованию или полученные в результате расшифрования
Шифртекст – данные, полученные в результате применения шифра к открытому тексту
Шифр – совокупность обратимых преобразований, зависящая от некоторого параметра (ключа)
Ключ – параметр шифра, определяющий выбор одного преобразования из совокупности.
Факторизация – процесс разложения числа на простые множители.
НОД – наибольший общий делитель.
Числа a и b называются взаимно простыми, если НОД этих чисел равен 1.
Функция Эйлера φ(n) – функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним.

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

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

Прежде, чем окунуться в необъятный мир математики рассмотреть, как именно устроена 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 обусловлен следующим. Как вы могли заметить ранее, закрытый ключ можно получить, зная открытый. Зная числа 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. — Учебное пособие

Источник: temofeev.ru

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

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

Содержание

Введение
Определения и обозначения
Описание криптосистемы RSA

Асимметричные криптографические системы
Генерация ключей
Шифрование и дешифрование
Получение подписи сообщения по RSA

Введение

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

Теорминимум

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

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

Открытый текст – данные, подлежащие шифрованию или полученные в результате расшифрования
Шифртекст – данные, полученные в результате применения шифра к открытому тексту
Шифр – совокупность обратимых преобразований, зависящая от некоторого параметра (ключа)
Ключ – параметр шифра, определяющий выбор одного преобразования из совокупности.
Факторизация – процесс разложения числа на простые множители.
НОД – наибольший общий делитель.
Числа a и b называются взаимно простыми, если НОД этих чисел равен 1.
Функция Эйлера φ(n) – функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним.