RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел. Криптосистема RSA стала первой системой, пригодной и для шифрования, и для цифровой подписи. Алгоритм используется в большом числе криптографических приложений, включая PGP, S/MIME, TLS/SSL, IPSEC/IKE и других или читайте далее из Wikipedia.
Как появился RSA?
Дата начала данного алгоритма уходит к далекому 1976 году, когда в ноябре этого года появилась опубликованная статья Уитфилда Диффи и Мартина Хеллмана под заголовком «Новые направления в криптографии» (англ. New Directions in Cryptography). В то пору, это был новый подход в криптографии, перевернувший представление о криптографических системах, заложив основы к использованию открытых ключей в криптографии.
Разработанный впоследствии алгоритм Диффи — Хеллмана позволял двум сторонам получить общий секретный ключ, используя незащищенный канал связи. Однако этот алгоритм не решал проблемуаутентификации. Без дополнительных средств пользователи не могли быть уверены, с кем именно они сгенерировали общий секретный ключ.
Изучив эту статью, трое учёных Рональд Ривест, Ади Шамир и Леонард Адлеман из Массачусетского технологического института (MIT) приступили к поискам математической функции, которая бы позволяла реализовать сформулированную Уитфилдом Диффи и Мартином Хеллманом модель криптографической системы с открытым ключом. После работы над более чем 40 возможными вариантами им удалось найти алгоритм, основанный на различии в том, насколько легко находить большие простые числа и насколько сложно раскладывать на множители произведение двух больших простых чисел, получивший впоследствии название RSA. Система была названа по первым буквам фамилий её создателей.
В августе 1977 года в колонке «Математические игры» Мартина Гарднера в журнале Scientific American, с разрешения Рональда Ривеста появилось первое описание криптосистемы RSA. Читателям также было предложено дешифровать английскую фразу, зашифрованную описанным алгоритмом.
Описание и понимание алгоритма RSA
Алгоритм RSA основан на трудности разложения на множители больших чисел, которые имеют 2 и только 2 фактора (простых чисел). Система работает на открытом и закрытом ключах (Public and Private keys). Открытый ключ доступен для всех. С этим ключом пользователь может зашифровать данные, но не может расшифровать их и это может только пользователь, у кого закрытый ключ, который, с помощью этого ключа, умеет расшифровать их . Конечно, теоретически их может расшифровать и обычный пользователь с публичным ключом, но это экстремально сложно — генерировать закрытый ключ из открытого. Данный метод зашифровки и расшифровки данных пользователей носит название алгоритма RSA, который очень популярен в зашифровке данных на данный момент. Безопасность RSA зависит от вычислительной сложности факторизации больших чисел.
Генерация двух больших простых чисел
Для того, чтобы привести простой пример будем использовать небольшие цифры, но отметим, что в реальности это не безопасно. Чтобы найти случайные простые числа, мы начнем с случайного числа и поднимемся по возрастанию до нечетного числа, пока мы не найдем простое число. Пусть имеем:
p = 7
q = 19
Пусть n = p*q:
n = p*q = = 7 * 19 = 133
Пусть m = (p – 1)(q – 1):
m = (p – 1)(q – 1) = (7 – 1)(19 – 1) = 6 * 18 = 108
Возьмем маленькие числа e до значения числа m. Числа e – простые по отношению к m и не превышают его значение, это означает, что большое число, которое может точно разделиться как e, так и на m (их наибольший общий делитель, или НОД) равен 1. Алгоритм Евклида используется для поиска наибольшего общего делителя двух чисел, но детали здесь опускаются. Отсюда имеем:
e = 2 => gcd (e, 108) = 2 (нет)
e = 3 => gcd (e, 108) = 3 (нет)
e = 4 => gcd (e, 108) = 4 (нет)
e = 5 => gcd (e, 108) = 1 (да!)
Находим такое число d, что d*e % m = 1(т.е., чтобы он разделился без остатка). Это эквивалентно нахождению d, удовлетворяющую d*e = 1 + n*m, где n – любое целое число. Мы можем переписать это как d = (1 + n*m) / e. Теперь мы работаем через значения n до целочисленного решения, т.е. пока не будет найдено целочисленное деление:
n = 0 => d = 1 / 5 (нет)
n = 1 => d = 109 / 5 (нет)
n = 2 => d = 217 / 5 (нет)
n = 3 => d = 325 / 5 = 65 (да!)
Для выполнения этого действия с большими числами необходимо использовать алгоритм Евклида.
Открытый ключ (Public key) будет равен:
n = 133
e = 5
Закрытый ключ (Private key) будет равен:
n = 133
d = 65
Небольшой пример зашифровки и дешифровки алгоритмом RSA
Зашифровка. Сообщение должно быть числом, меньшим, чем p и q. Тем не менее, на данный момент мы не знаем р или q, поэтому на практике нижняя граница р и q должны быть опубликованы. Это может быть несколько ниже их реального значения и поэтому не является главным вопросом безопасности. Для этого примера, будем использовать сообщение «6».
C = p * e % n = 65 % 133 = 7776 % 133 = 62
Дешифровка. Это работает очень похоже на процесс шифрования, но включает в себя большое распределение, которое разбивается на несколько шагов.
P = C*d % n = 6265 % 133 = 62 * 6264 % 133 = 62 * (622)32 % 133 = 62 * 384432 % 133 = 62 * (3844 % 133)32 % 133 = 62 * 12032 % 133
Теперь повторим последовательность операций, снижения 6265 до 12032, чтобы уменьшить показатель до 1.
...= 62 * 3616 % 133 = 62 * 998 % 133 = 62 * 924 % 133 = 62 * 852 % 133 = 62 * 43 % 133 = 2666 % 133 = 6
И то, что получилось мы ставим в начало открытого текста, вот так алгоритм и работает.
