Разбор алгоритма rsa (rivest-shamir-adleman)

Tartuga

Бывалый
ПРОВЕРЕННЫЙ ПРОДАВЕЦ
PREMIUM USER

Tartuga

Бывалый
ПРОВЕРЕННЫЙ ПРОДАВЕЦ
PREMIUM USER
Регистрация
7 Фев 2020
Сообщения
525
Реакции
98
Репутация
147
RSA (Rivest-Shamir-Adleman) - алгоритм асимметричной криптографии. Асимметричность означает, что он работает с двумя ключами, то есть с открытым и закрытым ключом.

Простейший пример применения асимметричной криптографии:
1) Клиент отправляет свой открытый ключ на сервер и запрашивает некоторые данные.
2) Сервер шифрует данные с использованием открытого ключа клиента и отправляет зашифрованные данные.
3) Клиент получает эти данные и расшифровывает их.
Поскольку это асимметрично, никто, кроме клиента, не сможет расшифровать данные, даже если у третьей стороны есть открытый ключ.
Впервые RSA был публично описан в 1977 году Роном Ривестом, Ади Шамиром и Леонардом Адлеманом (от сюда и название:) из Массачусетского технологического института, хотя впервые алгоритм с открытым ключом был разработан еще в 1973 годом британским математиком Клиффордом Коксом... Но, как обычно это бывает, проект был засекречен британским GCHQ до 1997 года.

Многие протоколы, такие как Secure Shell , OpenPGP, S / MIME и SSL / TLS, используют RSA для функций шифрования и цифровой подписи . Проверка подписи RSA является одной из наиболее часто выполняемых операций в системах, подключенных к сети.



Краткое описание идеи алгоритма
Открытый ключ состоит из двух чисел, одно из которых является умножением двух больших простых чисел. И закрытый ключ также получен из тех же двух простых чисел. Что влечет за собой большие временные затраты на извлечение исходных простых чисел. И если кто-то сможет разложить данное большое число, закрытый ключ будет взломан. Следовательно, надежность шифрования полностью зависит от размера ключа, и если мы удвоим или утроим размер ключа, сила шифрования возрастет в геометрической прогрессии. Длина ключей RSA обычно составляет 1024 или 2048 бит. Но полноценно

Пожалуйста Авторизуйтесь или Зарегистрируйтесь для просмотра скрытого текста.

алгоритм был лишь в 2017 году группой ученых из США, Нидерландов и Австралии.

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

Пожалуйста Авторизуйтесь или Зарегистрируйтесь для просмотра скрытого текста.

. Модуль n рассчитывается путем умножения p и q. Этот номер используется как открытым, так и закрытым ключами и обеспечивает связь между ними.

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

Закрытый ключ состоит из модуля n и частного показателя d, который вычисляется с использованием расширенного алгоритма Евклида.



Работа алгоритма


Генерируем открытый ключ
:

1) Выберем 2 простых числа. Предположим, что p = 37 и q =43 . Тогда первая часть открытого ключа будет: n = p * q = 1591



2) Берем показатель е :

1 <e < ф(n)

ф(n) вычисляется следующим образом: ф(n) = (p-1)(q-1),

Поэтому в нашем случае ф(n) = 1512.

И мы можем взять e = 5

(Таким образом наш открытый ключ состоит из n и e)



Генерируем закрытый ключ:

3) Вычислим закрытый ключ, d : d = (k * Φ (n) + 1) / e для некоторого целого числа k.

Возьмем k = 2. Значение d тогда равно 605.



Теперь допустим мы передаем в сообщение M, значение которого равно 9.

Алгоритм шифрует это сообщение по формуле: c = M^e mod n

Те в нашем случае зашифрованное сообщение будет иметь значение 182.

Для приема и расшифровки сообщения используется формула: M = c^d mod n.



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





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

И, если вдруг не случится непредвиденного прорыва в квантовых вычислениях, пройдет много лет, прежде чем потребуются более длинные ключи, но

Пожалуйста Авторизуйтесь или Зарегистрируйтесь для просмотра скрытого текста.

(ECC) завоевывает популярность у многих экспертов по безопасности в качестве альтернативы RSA для реализации криптографии с открытым ключом. Он может создавать более быстрые и более эффективные криптографические ключи.

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