Как водится: если хочешь в чем-то разобраться, то сядь и запрись с этим на неделю. Пришлось мне для курсовой работы взять темку шифрования RSA. Поначалу было боязно браться за шифрование, но уже через несколько секунд эта мысль сменилась любопытством. Ведь если делают другие, то почему не могу я?
Как оказалось, принцип RSA-шифрования весьма прост. В основе лежат два ключа — публичный и приватный. Зашифрованное публичным ключом послание с успехом расшифровывается только лишь его коллегой — приватным, и наоборот (доказательство такого поведения можно найти в малой теореме Ферма). В этом и заключается важное свойство RSA-шифрования — асимметричность.
Пара слов о ключах. В основе генерации ключей лежат три параметра — назовём их e, d, n. Публичным ключом называется пара (e, n), а приватным — пара (d, n). Чтобы не создавалось впечатление, что что-то происходит без нашего участия, немного углубимся в способ их получения.
- Выбираем (наобум) два любых простых числа p, q
- Вычисляем n = p * q
- Вычисляем m = (p — 1) * (q — 1)
- Подбираем такое e (1<e<m), чтобы оно было взаимно простое с числом m
- Подбираем такое d, чтобы (e * d — 1) делилось на m
Всё, после этого у нас есть необходимые e, d, n. И, соответственно, уже можно собрать публичный ключ из пары (e, n) и приватный из пары (d, n).
Теперь о том, как шифровать. Шифровать нужно в две стороны — чтобы зашифровать и чтобы расшифровать. Соответственно, и формул шифрования всего две.
- C = O^e mod n
- D = C^d mod n
Казалось бы: каким образом понимать такую формулу, если я хочу зашифровать своё имя? Тут пора вспомнить, что всё, что хранится или передается по цифровым каналам – это биты и байты. А биты и байты без труда могут быть распознаны как числа, что бы в них ни хранилось. Таким образом, нужное сообщение разбивается на части, каждая из которых интерпретируется как отдельное число, шифруется по этой формуле и возвращается к общей куче.
Чтобы зашифровать сообщение (число), нужно возвести его в степень e, и после взять остаток от деления этого результата на n. С расшифровкой всё то же самое, но махинации надо проводить над зашифрованным посланием, а вместо e возводить в степень d.
Казалось бы, тут всё совсем без проблем, кроме суматохи по генерации ключей. Но на самом деле, чем надёжнее ключ RSA (1024 бита и выше), тем сложнее вести шифрацию. Ведь в степень-то нужно возводить не в третью и не в седьмую, а в тысячные степени (хотя для учебного примера для себя любимого можно обойтись и 4-битным ключом).
Так что, лично я для себя вижу в теме RSA всего два острых камешка: процесс генерации ключей и процесс шифрации (для которого требуются сторонние библиотеки по работе с большими числами, ведь стандартно система понимает не более 64 бит для числа). А в целом – весьма легкая для понимания тема.