Создание ключей, шифрование и дешифрование сообщений в системе RSA | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 20 марта, печатный экземпляр отправим 24 марта.

Опубликовать статью в журнале

Авторы: ,

Рубрика: Математика

Опубликовано в Молодой учёный №45 (283) ноябрь 2019 г.

Дата публикации: 10.11.2019

Статья просмотрена: 1052 раза

Библиографическое описание:

Наумчик, Н. С. Создание ключей, шифрование и дешифрование сообщений в системе RSA / Н. С. Наумчик, С. А. Васи. — Текст : непосредственный // Молодой ученый. — 2019. — № 45 (283). — С. 1-3. — URL: https://moluch.ru/archive/283/63831/ (дата обращения: 06.03.2021).



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

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

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

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

Таким образом, криптографическая система RSA остается на сегодняшний день одной из самых надежных (при длине ключе от 1024 бит).

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

На этапе создания ключей производятся следующие операции:

  1. Выбираются два больших простых числа p и q.
  2. Вычисляется их произведение , называемое модулем.
  3. Вычисляется значение функции Эйлера от полученного произведения .
  4. Выбирается произвольное число e, такое, что , причем
  5. С помощью алгоритма Евклида вычисляется некоторое число d, удовлетворяющее условию .

На этапе распределения ключей:

  1. Пара {e,n} выступает в качестве открытого ключа RSA.
  2. Пара {d,n} выступает в качестве закрытого ключа RSA.

На этапе шифрования и дешифрования:

Со стороны отправителя:

  1. Взять открытый ключ {e,n} получателя.
  2. Взять открытый текст m.
  3. Зашифровать сообщение с использованием открытого ключа получателя: .

Со стороны получателя:

  1. Принять зашифрованное сообщение C.
  2. Взять свой закрытый ключ (d,n).
  3. Применить закрытый ключ для дешифрования сообщения: .

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

Пример. Этап создания ключей:

1.Выберем два простых числа и , причем таких, что . Пусть и ;

2.Вычислим произведение взятых чисел:

3.Вычислим функцию Эйлера. Для этого воспользуемся формулой . Тогда ;

4.Выберем произвольное число e. Пусть ;

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

Переходим к этапу распределения ключей.

  1. Назначаем пару {3,9173503} в качестве открытого ключа;
  2. Назначаем пару {6111579,9173503} в качестве закрытого ключа.

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

  1. Выбираем некоторый текст m, который необходимо зашифровать (шифрование будем выполнять с помощью открытого ключа). Пусть .
  1. Шифруем сообщение с использованием открытого ключа получателя: .

.

Заключительным этапом будет этап дешифрования.

  1. Возьмем полученный зашифрованный текст c и дешифруем его с помощью закрытого ключа .

Итак, поскольку , то

.

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

Литература:

  1. RSA [электронный ресурс] — Режим доступа: URL: https://ru.wikipedia.org/wiki/RSA. Дата обращения 06.10.2019.
  2. Бернет С., Пэйн С. Криптография. Официальное руководство RSA Security/ Бернет С., Пэйн С. — Бином, 2002–381с.
  3. Виноградов, И. М. Основы теории чисел: учебное пособие [Текст] / И. М. Виноградов. — 12-е изд. — М.: Лань, 2009. — 176 с.
  4. Коутинхо С. Введение в теорию чисел. Алгоритм RSA/ Коутинхо С. — М.: Постмаркет, 2011 -328с.
Основные термины (генерируются автоматически): RSA, открытый ключ, закрытый ключ, число, криптографическая система, GCHQ, MIT, помощь алгоритма, произвольное число, этап распределения ключей.


Похожие статьи

Исследование криптосистем с открытым ключом на основе...

RSAкриптографический алгоритм с открытым ключом, основывающийся на

В RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и

В настоящее время криптографическая система RSA получила широкое распространение.

Реализация алгоритма шифрования RSA на языке...

Статья посвящена реализации алгоритма шифрования на открытом ключе RSA. LabVIEW (англ.

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

Криптография с открытым ключом. Криптосистема RSA

Криптосистема с открытым ключом составляют следующие элементы

В дальнейшем ключ шифрования Кea составляет пара чисел naи ea (отметим, что Кeaесть открытый ключ).

RSA, MISHA, открытый ключ, закрытый ключ, открытый текст, число, односторонняя функция...

RSA, открытый ключ, простое число, криптосистема...

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

Анализ алгоритма RSA. Некоторые распространённые...

В основу криптографической системы с открытым ключом RSA находится задача умножения и разложения составных чисел на простые

В криптографической системе с открытым ключом каждый участник имеет в своем распоряжении как открытым ключ (англ. public key...

Шифрование и криптоанализ | Статья в журнале «Молодой ученый»

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

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

История развития криптологии. Этапы | Статья в журнале...

Этот ключ является типичным примером номенклатора — криптографической системы

В основе криптографических систем с открытым ключом лежит теория необратимых

Реализация алгоритма шифрования RSA на языке... Криптосистема RSA стала первой...

Теория чисел в криптографии | Статья в журнале...

Криптографическая система RSA с открытым ключом, предложенная в работе [2, с. 120] получила широкое распространение в настоящее время. Эта системаподдерживает большинство электронных коммерческих коммуникаций.

Способ хранения закрытого ключа криптосистемы цифровой...

Пользователь может хранить закрытый ключ на своем персональном компьютере

С облака часть ключа передается зашифрованной, с помощью любого ассиметричного алгоритма

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

Похожие статьи

Исследование криптосистем с открытым ключом на основе...

RSAкриптографический алгоритм с открытым ключом, основывающийся на

В RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и

В настоящее время криптографическая система RSA получила широкое распространение.

Реализация алгоритма шифрования RSA на языке...

Статья посвящена реализации алгоритма шифрования на открытом ключе RSA. LabVIEW (англ.

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

Криптография с открытым ключом. Криптосистема RSA

Криптосистема с открытым ключом составляют следующие элементы

В дальнейшем ключ шифрования Кea составляет пара чисел naи ea (отметим, что Кeaесть открытый ключ).

RSA, MISHA, открытый ключ, закрытый ключ, открытый текст, число, односторонняя функция...

RSA, открытый ключ, простое число, криптосистема...

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

Анализ алгоритма RSA. Некоторые распространённые...

В основу криптографической системы с открытым ключом RSA находится задача умножения и разложения составных чисел на простые

В криптографической системе с открытым ключом каждый участник имеет в своем распоряжении как открытым ключ (англ. public key...

Шифрование и криптоанализ | Статья в журнале «Молодой ученый»

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

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

История развития криптологии. Этапы | Статья в журнале...

Этот ключ является типичным примером номенклатора — криптографической системы

В основе криптографических систем с открытым ключом лежит теория необратимых

Реализация алгоритма шифрования RSA на языке... Криптосистема RSA стала первой...

Теория чисел в криптографии | Статья в журнале...

Криптографическая система RSA с открытым ключом, предложенная в работе [2, с. 120] получила широкое распространение в настоящее время. Эта системаподдерживает большинство электронных коммерческих коммуникаций.

Способ хранения закрытого ключа криптосистемы цифровой...

Пользователь может хранить закрытый ключ на своем персональном компьютере

С облака часть ключа передается зашифрованной, с помощью любого ассиметричного алгоритма

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

Задать вопрос