§ Предисловие

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

§ Открытый и закрытый ключи

Этот алгоритм основан на ключах, один из них открытый, другой - закрытый. Это называется пара ключей (публичный — то есть открытый, и приватный — закрытый). Ключи представляют собой просто очень большое число, то есть реально, просто число, и ничего более, кроме того, что оно гигантское. Для простоты и наглядности ключи у меня будут далее крайне простыми, не превышающие тысячи, поскольку чем больше ключ, тем сложнее его считать.
Теперь представим следующую ситуацию. Есть Алиса, и есть Боб. Они сверхсекретные агенты, и они не могут выдать то, о чем они болтают между собой, и какие сверхсекретные данные передают. Алиса сидит на телефоне, Боб сидит на другом конце телефона а посередине сидит их общий заклятый враг и внимательно слушает, о чем они говорят. Алисе надо передать Бобу очень секретное число, но просто сказать по телефону она ему не может — враг не дремлет.
  • Алиса спрашивает у Боба открытый ключ, он ей говорит его по телефону. Ключ становится известен всем, в том числе не только Алисе, но и еще тому, кто сидит и слушает их
  • Алиса берет это число (открытый ключ), производит определенные действия над тем числом, что хочет закодировать и отсылает Бобу. Человек посередине эту информацию тоже перехватил.
  • Боб же берет закрытый ключ, который он создал вместе с открытым и производя математические действия, расшифровывает число Алисы
  • Человек посередине не знает закрытого ключа Боба, а по открытому ключу он не может ничего сделать, потому что расшифровать сообщение можно только с помощью закрытого. Человек с досады кусает свои локти.
Вкратце:
  • Боб создает открытый и закрытый ключи (они взаимосвязаны, как Том и Джерри)
  • Алиса получает открытый ключ Боба
  • Кодирует с его помощью свое число
  • Отсылает число по небезопасному каналу связи
  • Боб расшифровывает число с помощью закрытого ключа
Более абстрактно:
  • Создать открытый и закрытый ключи
  • Передать открытый ключ тому, кто будет шифровать
  • Зашифровать сообщение с помощью открытого ключа
  • Передать зашифрованное сообщение по каналу связи
  • Расшифровать сообщение с помощью закрытого ключа

§ Открытый ключ

Задача создать открытый и закрытый ключи - очень сложна, если речь заходит о колоссальных цифрах. Сложность именно в том, как их быстро вычислить. Дело в том, что если взять два гигантских простых числа, и умножить, обратно потом найти эти простые числа уже весьма проблематично. Алгоритм RSA устройчив к взлому исключительно потому, что:
Невозможно быстро и эффективно разложить на множители огромные числа
Вот так вот. Если бы это было реально, то алгоритм RSA утратил бы свою криптостойкость и пришлось бы искать еще какой-нибудь метод. Сейчас рулят эллиптические кривые, но я без понятия как они работают, поэтому расскажу только про RSA.
Шаг 1. Взять два простых числа p и q
Кстати говоря, это далеко не так просто, как кажется. Если речь идет о небольших простых числах, не превышающих к примеру миллиарда, то их нахождение для взломщика не составляет вообще никакого труда. На любом процессоре разложить подобные числа можно за несколько миллисекунд. Однако, как только речь заходит о числах порядка аж 800-1000 десятичных знаков, то тогда никакой сверхмощной видеокарты, да и вообще вычислительной мощности всей планеты не хватит, чтобы даже за 1 год взломать такой код. Единственный, кто может справиться с этой задачей - это алгоритм Шора для квантовых компьютеров, которые сейчас находятся пока что в довольно неразвитой стадии на 2020 год.
Да, простые то числа взять можно, только вот надо чтобы они реально простые были, потому что составные числа работать не будут в RSA вообще. Они будут просто ломать всё. Это значит, что надо бы еще найти простые числа, а это сложная задача. Существуют разные тесты простоты, но в этой статье я их рассматривать не буду.
Получив простые числа p, q, надо их перемножить:
n = pq
И получим n, который будет играть важную роль дальше.
Шаг 2. Вычислить открытую экспоненту e
Перед тем, как вычислить открытую экспоненту, надо рассчитать функцию Эйлера, которая считается для двух простых чисел невероятно простым способом:
\phi (n) = (p-1)(q-1)
То есть нужно лишь просто вычесть из p и q по единице и умножить их. Для чего это все? Здесь есть строгое математическое доказательство, приводить которое я тут не буду, потому что сложно и много. Просто надо поверить на слово. А если хочется проверить, то надо смотреть специальную литературу.
Теперь самый ответственный момент. Надо взять наобум число e такое, которое бы попало в следующий диапазон:
1 \lt e \lt \phi(n)
И при этом его наибольший общий делитель (НОД) был равен 1, или, другими словами, чтобы ни одно целое число, кроме 1, не смогло поделить e и \phi (n) , то есть, чтобы у этих двух чисел не было наибольшего общего делителя, больше чем 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 — это число часть как открытого, так и закрытого ключа
  • Вычисляем \phi (n) = (p-1)(q-1) = (47-1)(31-1) = 1380
  • Теперь, надо взять такое e , чтобы НОД( e , \phi (n) ) = 1, берем число e=257 (для примера), проверятся НОД(257, 1380) = 1, все верно
Открытый ключ {e, n} равен {257, 1457}.

§ Закрытый ключ

Теперь задача в том, чтобы сформировать закрытый ключ на числах p, q. Как я и говорил ранее, закрытый ключ нужен, чтобы расшифровать то сообщение, которое было зашифровано с помощью открытого ключа. Закрытый ключ базируется на тех же самых p,q, и потому у него будет точно та же компонента n, что и у открытого ключа. Закрытый же ключ будет представлен как пара {d, n}, где d - закрытая компонента, n = pq.
Существует формула для поиска закрытого ключа:
d = e^{-1}\ mod\ \phi (n)
Но, ее понять сложно без подготовки. Лучше ее переписать в следующем виде:
(de)\ mod\ \phi(n) = 1
И что это значит? Это значит, что надо найти d такое, что при умножении на e и потом после деления на \phi(n) получился остаток 1.
Вот возьмем простой пример, допустим e = 7, \phi(n) = 60:
7d \ mod\ 60 = 1
Теперь надо подобрать такое 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, подошло
Получается, что для числа e = 7 число d = 43. Таким образом, мы смогли найти закрытый ключ {43, 77}, при этом открытый ключ был {7, 77}.
Поиск закрытого ключа происходит с помощью расширенного алгоритма Евклида, объяснение которого здесь тоже не приводится.

§ Пример шифрования и дешифрования

А теперь самое главное: как шифровать и дешифровать сообщение.
Шифрование числа происходит по следующей формуле:
b = a^e\ mod\ n
Дешифрование происходит так:
a = b^d\ mod\ n
И это весь алгоритм. Стоит только учесть, что так как числа d и e огромны, то не так просто будет возвести такие числа в такую вот степень.
Для начала, составим открытый и закрытый ключи. Генерация открытого ключа происходит по такому алгоритму:
  • Возьмем p=11, q=23, n = pq = 253
  • Число Эйлера \phi(n) = (11-1)(13-1) = 220
  • Выберем открытую экспоненту e = 17, ибо НОД(17, 220) = 1
Итак, открытый ключ будет равен {17, 253}. Теперь надо найти закрытый ключ, используя вот это уравнение:
17d\ mod\ 253 = 1
Пока что находим перебором, но можно искать с помощью расширенного алгоритма НОД. Но в данном случае просто перебором, про НОД позже расскажу.
Путем подбора (я просто программой перебрал числа d=1..253), d оказалось равным 134. Проверим, 134*17 mod 253 = 1, все подошло. Закрытый ключ равен {134, 253}.
Теперь надо попробовать что-нибудь зашифровать и расшифровать. Поскольку число n у нас 253, то зашифровать можно сообщение только от 0 до 252 включительно, ибо если попытаться использовать 253, то такое сообщение просто превратится в 0 при расшифровке. Это не проблема, но надо учитывать, что шифровать число более чем n нельзя.
Выбираем a=110, теперь шифруем с помощью открытого ключа.
b = 110^{17}\ mod\ 253 = 77
У нас получился b=77. Даже зная n=253, нельзя получить обратно 110, потому что нужен для этого закрытый ключ. Однако, если разложить 253 на простые множители p, q, то тогда можно найти и закрытый ключ d. Однако, при большом значении n это сделать невозможно. Расшифровка с помощью закрытого ключа делается так:
a = 77^{134}\ mod\ 253 = 110
Что и требовалось сделать. Все работает корректно. Процедура для быстрого возведения в степень приведена в этой статье.

§ Нахождение закрытого ключа с помощью расширенного НОД

Существуют способы, при которых можно найти d, зная e, не используя при этом перебор, и этот способ - расширенный алгоритм Евклида, о котором я уже писал ранее в другой статье. То есть как находить коэффициенты к расширенному алгоритму, об этом здесь я говорить не стану, а только опишу самую суть того, почему надо использовать именно этот НОД.
Поскольку числа e и \phi(n) взаимно простые, но их НОД будет равен 1:
НОД( e , \phi(n) ) = xe + y\phi(n) = 1
Здесь значения x, y получаются из решения расширенного алгоритма НОД. Теперь применим модуль к левой и правой части:
xe\ mod\ \phi(n) + y\phi(n)\ mod\ \phi(n) = 1\ mod\ \phi(n)
Поскольку любой модуль от 1 будет 1, а модуль самого от себя, y\phi(n)\ mod\ \phi(n) будет равняться 0, то уравнение сокращается:
xe\ mod\ \phi(n) = 1
Тут сразу же видно, что x - это как раз тот самый искомый d. В общем-то и всё.

§ Программный код

Получение значений расширенного НОД:
int NOD(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;
}
Быстрое возведение в степень:
unsigned long fpow(unsigned long a, unsigned long b, unsigned long m) {

    int id;
    unsigned long r = 1;
    for (id = 31; id >= 0; id--) {
        if (b & (1 << id)) r = (r * a) % m;
        if (id) r = (r * r) % m;
    }
    return r;
}
22 ноя, 2020
© 2007-2022 Том штырит на работе