Это алгоритм для шифрования сообщений. Он сложный, трудоемкий и напрямую не используется из-за своей очень невысокой скорости работы. А скорость работы у него невероятно медленная по той причине, что такой алгоритм оперирует гигантскими числами.
§ Открытый и закрытый ключи
Этот алгоритм основан на ключах, один из них открытый, другой – закрытый. Это называется пара ключей (публичный – то есть открытый, и приватный – закрытый). Ключи представляют собой просто очень большое число, то есть реально, просто число, и ничего более, кроме того, что оно гигантское. Для простоты и наглядности ключи у меня будут далее крайне простыми, не превышающие тысячи, поскольку чем больше ключ, тем сложнее его считать.
Теперь представим следующую ситуацию. Есть Алиса, и есть Боб. Они сверхсекретные агенты, и они не могут выдать то, о чем они болтают между собой, и какие сверхсекретные данные передают. Алиса сидит на телефоне, Боб сидит на другом конце телефона а посередине сидит их общий заклятый враг и внимательно слушает, о чем они говорят. Алисе надо передать Бобу очень секретное число, но просто сказать по телефону она ему не может – враг не дремлет.
Алиса спрашивает у Боба открытый ключ, он ей говорит его по телефону. Ключ становится известен всем, в том числе не только Алисе, но и еще тому, кто сидит и слушает их
Алиса берет это число (открытый ключ), производит определенные действия над тем числом, что хочет закодировать и отсылает Бобу. Человек посередине эту информацию тоже перехватил.
Боб же берет закрытый ключ, который он создал вместе с открытым и производя математические действия, расшифровывает число Алисы
Человек посередине не знает закрытого ключа Боба, а по открытому ключу он не может ничего сделать, потому что расшифровать сообщение можно только с помощью закрытого. Человек с досады кусает свои локти.
Вкратце:
Боб создает открытый и закрытый ключи (они взаимосвязаны, как Том и Джерри)
Алиса получает открытый ключ Боба
Кодирует с его помощью свое число
Отсылает число по небезопасному каналу связи
Боб расшифровывает число с помощью закрытого ключа
Более абстрактно:
Создать открытый и закрытый ключи
Передать открытый ключ тому, кто будет шифровать
Зашифровать сообщение с помощью открытого ключа
Передать зашифрованное сообщение по каналу связи
Расшифровать сообщение с помощью закрытого ключа
§ Открытый ключ
Задача создать открытый и закрытый ключи – очень сложна, если речь заходит о колоссальных цифрах. Сложность именно в том, как их быстро вычислить. Дело в том, что если взять два гигантских простых числа, и умножить, обратно потом найти эти простые числа уже весьма проблематично. Алгоритм RSA устройчив к взлому исключительно потому, что:
Невозможно быстро и эффективно разложить на множители огромные числа
Вот так вот. Если бы это было реально, то алгоритм RSA утратил бы свою криптостойкость и пришлось бы искать еще какой-нибудь метод. Сейчас рулят эллиптические кривые, но я без понятия как они работают, поэтому расскажу только про RSA.
Шаг 1. Взять два простых числа p и q
Кстати говоря, это далеко не так просто, как кажется. Если речь идет о небольших простых числах, не превышающих к примеру миллиарда, то их нахождение для взломщика не составляет вообще никакого труда. На любом процессоре разложить подобные числа можно за несколько миллисекунд. Однако, как только речь заходит о числах порядка аж 800-1000 десятичных знаков, то тогда никакой сверхмощной видеокарты, да и вообще вычислительной мощности всей планеты не хватит, чтобы даже за 1 год взломать такой код. Единственный, кто может справиться с этой задачей – это алгоритм Шора для квантовых компьютеров, которые сейчас находятся пока что в довольно неразвитой стадии на 2020 год.
Да, простые то числа взять можно, только вот надо чтобы они реально простые были, потому что составные числа работать не будут в RSA вообще. Они будут просто ломать всё. Это значит, что надо бы еще найти простые числа, а это сложная задача. Существуют разные тесты простоты, но в этой статье я их рассматривать не буду.
Получив простые числа p, q, надо их перемножить:
И получим n, который будет играть важную роль дальше.
Шаг 2. Вычислить открытую экспоненту e
Перед тем, как вычислить открытую экспоненту, надо рассчитать функцию Эйлера, которая считается для двух простых чисел невероятно простым способом:
То есть нужно лишь просто вычесть из p и q по единице и умножить их. Для чего это все? Здесь есть строгое математическое доказательство, приводить которое я тут не буду, потому что сложно и много. Просто надо поверить на слово. А если хочется проверить, то надо смотреть специальную литературу.
Теперь самый ответственный момент. Надо взять наобум число такое, которое бы попало в следующий диапазон:
И при этом его наибольший общий делитель (НОД) был равен 1, или, другими словами, чтобы ни одно целое число, кроме 1, не смогло поделить и , то есть, чтобы у этих двух чисел не было наибольшего общего делителя, больше чем 1.
Примеры:
Числа 5 и 15 имеют НОД(5,15) = 5 – число 15 делится на 5, и 5 делится на 5 без остатка
НОД(7, 14) = 7 – число 7 делится на 7, и 14 делится на 7 тоже
НОД(12, 15) = 3 – число 12 делится на 3, число 15 делится на 3
НОД(9, 11) = 1 – вот это в самый раз, ни одно число не делится, кроме как на 1
Шаг 3. Открытый ключ
Теперь появились все данные, чтобы найти открытый ключ, который представлен как пара {e, n}. Теперь перейду к практической части вычисления открытого ключа.
Берется (для примера) p=47, q=31, оба числа простые
Получается n = pq = 47*31 = 1457 – это число часть как открытого, так и закрытого ключа
Вычисляем = (47-1)(31-1) = 1380
Теперь, надо взять такое , чтобы НОД(, ) = 1, берем число e=257 (для примера), проверятся НОД(257, 1380) = 1, все верно
Открытый ключ {e, n} равен {257, 1457}.
§ Закрытый ключ
Теперь задача в том, чтобы сформировать закрытый ключ на числах p, q. Как я и говорил ранее, закрытый ключ нужен, чтобы расшифровать то сообщение, которое было зашифровано с помощью открытого ключа. Закрытый ключ базируется на тех же самых p,q, и потому у него будет точно та же компонента n, что и у открытого ключа. Закрытый же ключ будет представлен как пара {d, n}, где d – закрытая компонента, n = pq.
Существует формула для поиска закрытого ключа:
Но, ее понять сложно без подготовки. Лучше ее переписать в следующем виде:
И что это значит? Это значит, что надо найти такое, что при умножении на и потом после деления на получился остаток 1.
Вот возьмем простой пример, допустим = 7, = 60:
Теперь надо подобрать такое d, при котором остаток от деления на 60 был бы 1. Пробуем:
d = 1 – 7*1 mod 60 = 7, не подходит
d = 9 – 7*9 mod 60 = 63 mod 60 = 3, не подходит
d = 23 – 23*7 mod 60 = 161 mod 60 = 41, не подходит
d = 43 – 43*7 mod 60 = 301 mod 60 = 1, подошло
Получается, что для числа = 7 число = 43. Таким образом, мы смогли найти закрытый ключ {43, 77}, при этом открытый ключ был {7, 77}.
Поиск закрытого ключа происходит с помощью расширенного алгоритма Евклида, объяснение которого здесь тоже не приводится.
§ Пример шифрования и дешифрования
А теперь самое главное: как шифровать и дешифровать сообщение.
Шифрование числа происходит по следующей формуле:
Дешифрование происходит так:
И это весь алгоритм. Стоит только учесть, что так как числа и огромны, то не так просто будет возвести такие числа в такую вот степень.
Для начала, составим открытый и закрытый ключи. Генерация открытого ключа происходит по такому алгоритму:
Возьмем p=11, q=23, n = pq = 253
Число Эйлера
Выберем открытую экспоненту = 17, ибо НОД(17, 220) = 1
Итак, открытый ключ будет равен {17, 253}. Теперь надо найти закрытый ключ, используя вот это уравнение:
Пока что находим перебором, но можно искать с помощью расширенного алгоритма НОД. Но в данном случае просто перебором, про НОД позже расскажу.
Путем подбора (я просто программой перебрал числа d=1..253), оказалось равным 134. Проверим, 134*17 mod 253 = 1, все подошло. Закрытый ключ равен {134, 253}.
Теперь надо попробовать что-нибудь зашифровать и расшифровать. Поскольку число n у нас 253, то зашифровать можно сообщение только от 0 до 252 включительно, ибо если попытаться использовать 253, то такое сообщение просто превратится в 0 при расшифровке. Это не проблема, но надо учитывать, что шифровать число более чем n нельзя.
Выбираем a=110, теперь шифруем с помощью открытого ключа.
У нас получился b=77. Даже зная n=253, нельзя получить обратно 110, потому что нужен для этого закрытый ключ. Однако, если разложить 253 на простые множители p, q, то тогда можно найти и закрытый ключ d. Однако, при большом значении n это сделать невозможно. Расшифровка с помощью закрытого ключа делается так:
Что и требовалось сделать. Все работает корректно.
§ Нахождение закрытого ключа с помощью расширенного НОД
Существуют способы, при которых можно найти d, зная e, не используя при этом перебор, и этот способ – расширенный алгоритм Евклида, о котором я уже писал ранее в другой статье. То есть как находить коэффициенты к расширенному алгоритму, об этом здесь я говорить не стану, а только опишу самую суть того, почему надо использовать именно этот НОД.
Поскольку числа и взаимно простые, но их НОД будет равен 1:
НОД(, ) = = 1
Здесь значения x, y получаются из решения расширенного алгоритма НОД. Теперь применим модуль к левой и правой части:
Поскольку любой модуль от 1 будет 1, а модуль самого от себя, будет равняться 0, то уравнение сокращается:
Тут сразу же видно, что x – это как раз тот самый искомый d. В общем-то и всё.
§ Программный код
Получение значений расширенного НОД:
intNOD(int a, int b, int & x, int & y)
{
int x1, y1, d;
if (a == 0) { x = 0; y = 1; return b; }
d = NOD(b % a, a, x1, y1);
x = y1 - (int)(b / a) * x1;
y = x1;
return d;
}
Быстрое возведение в степень:
unsignedlong fpow(unsignedlong a, unsignedlong b, unsignedlong m)