Фантазии о Вселенной и мой личный сайт
Алгоритм RSA

Алгоритм RSA

В моем понимании. Полная статья тут

О шифровании

Алгоритм RSA заключается в том, чтобы с помощью открытых и закрытых ключей можно было передавать зашифрованное сообщение. У того, кто хочет отправить сообщение, должен быть особый ключ, и этот ключ - это пара целых чисел, т.е. {e, n}, с их помощью он и кодирует свое сообщение.

Вот представим, что, например, мы хотим отослать своему другу зашифрованное сообщение. Для простоты это будет какое-то не очень большое число, допустим, это число будет 7 (условно берем). Что нужно сделать? Разберем по шагам.

  • У нашего друга должны быть для нас ключи. Эти ключи называются "открытый" и "закрытый". Наш друг их создает сам, т.е. ключи создает только тот, кому мы шлем сообщение. Получается, что если кто-то хочет послать нам сообщение, то мы должны подготовить собственную связку ключей для этого.
  • Наш друг делится с нами открытым ключом, просто передавая нам его вконтакте или в скайпе, или вообще на сайте своем опубликовав на всеобщее обозрение, хотя это и немного опрометчиво... но даже и так можно! В общем, ключи мы получили.
  • Мы берем его ключ, который он нам дал (а закрытый ключ находится у него и он никакого права не имеет его публиковать), и начинаем шифровать наше число для передачи. Когда мы его зашифровываем с помощью его ключа (а это пара чисел), отсылаем сообщение через вконтакте или по скайпу или просто в каком-нибудь чате.
  • Наш друг принимает наше сообщение и начинает расшифровывать. Чтобы расшифровать, он достает закрытый ключ и применяет к нашему числу, которое мы ему прислали. Расшифровка удается успешно! Вот и все.

Когда мы передаем сообщение в зашифрованном виде, никто не может узнать его, имея только лишь один открытый ключ. Чтобы его расшифровать, необходимо знать закрытый ключ, а его нет. Зная открытый ключ, можно его попробовать разложить на 2 простых числа, что не получится так просто, потому что это слишком сложный процесс. И еще, расшифровав сообщение, там написано "Привет Вася" и зачем так маяться, когда можно просто прийти к Васе и просто получить закрытый ключ? Шутка. В которой доля правды. Но не об этом речь сейчас.

Создание ключей

  1. На самом деле, создать ключи не так-то и просто, как может показаться на первый взгляд. Сначала, надо выбрать два ОГРОМНЫХ простых числа, а это тоже нелегко. Эти два числа называются p и q. И чем больше эти два числа будут, тем более стойким будет шифрование. Сейчас выбирают такие числа p и q, в которых нереальное количество десятичных цифр, к примеру, 2048-битное шифрование - это p * q = 22048 ~ 3,23*10616, попробуй такое число еще разложи на простые множители. Это почти нереально сейчас, а вот квантовые компы с этим справляются сравнительно быстро. Произведение p * q = n. Это число очень важно! Это и есть вторая часть ключа.
  2. Потом, вычислим функцию Эйлера φ(n) = (p - 1) * (q - 1).
  3. Выберем так называемую "открытую" экспоненту "e", она должна быть такой, что 1 < e < φ(n), и при этом (важно!), быть взаимно простой к φ(n). Что это значит? Это значит, что ни у "e" ни у φ(n) не должно быть каких-нибудь делителей общих.
  4. Приведу примеры: число 3 и 7 - взаимно простые. Почему? Ни одно из них не получится ни на что поделить ни на какое число, кроме 1. То есть 3 делится на 1, а 7 делится на 1, но если мы поделим 3 на 3 - то оно делится, а вот 7 на 3 не делится. А вот например числа 3 и 21 - не взаимно простые. Берут обычно 3, 17, 65537 - чтобы поменьше было единичных бит в этом числе. На самом деле, можно взять совершенно любое число, но только, чтобы отвечал критериям выше. Можно брать любое число e от 3 до φ(n) - 1.
  5. Теперь самое интересное. Надо вычислить секретную экспоненту d. Как написано на Википедии, там d = e-1 mod φ(n). Написано красиво, но мне было абсолютно непонятно ничего из абсолютно доступного объяснения. В общем, что я понял в итоге. На самом деле, d умножить на e, и потом разделить на φ(n), и остаток от деления должен равняться 1!

    т.е. (d * e) mod φ(n) = 1 → d = e-1 mod φ(n)

    Возьмем какой-нибудь простой пример, к примеру, вот у нас:

    p = 5 и q = 7, а e = 5;
    n = p*q = 35;
    φ(n) = (p - 1)*(q - 1) = (5 - 1) * (7 - 1) = 24

    Проверим. Так, у нас e=5 а φ(n) = 24, общего делителя нет, т.е. нельзя 24 и 5 разделить одновременно на какое-то такое число, которое не 1. Все в порядке. Что должно быть? Подставим e и φ(n) куда требуется:

    (d * 5) mod 24 = 1

    Итак, надо перебрать d и посмотреть, какое у нас будет такое d, чтобы удовлетворяло данным условиям. Возьмем d = 4 ==> (4*5) % 24 = 20. Не подходит. Давайте d=5: (5*5) % 24 = 1. Подошло! Хотя это очень плохой пример, на самом деле. Надо, чтобы секретная экспонента не совпадала с публичной. Но суть ясна. Чтобы вычислить секретную экспоненту, зная e и φ(n), применяют "расширенный алгоритм Евклида". О нем позже.
  6. Итак, у нас получилось, что открытый ключ задается в виде {e, n} а закрытый - {d, n}. В примере выше e = 5, d = 5, это неверно, нужно, чтобы "e" не был равен d никогда.
  7. Зашифруем что-нибудь, это делается так: c = E(m) = me mod n. Вот у нас есть n = 35 (5*7), и есть e = d = 5. Шифруем число 7. Возводим в степень: 75 mod 35 = 7. Хотя это логично, поскольку d = e.

    Расшифровка производится аналогично m = D(c) = ce mod n. Понятное дело, что D(c) = E(m) тут, т.е. 7.

  8. Давайте подберем какие-нибудь другие d и e. Например:

    p = 7 и q = 11; n = p*q = 77;
    φ(n) = (p-1)*(q-1) = (7-1)*(10-1)=70.

    Итак, e у нас допустим, будет 3, потому что 70 не делится на 3 без остатка.

    Рассчитаем, какое тут будет число d в (d*3) mod 70 = 1. Путем перебора (не применял метод Евклида пока), d=47. Проверим. 47 * 3 = 141, делим на 70, получается остаток 1. Все верно.

    Итак, у нас d = 47, а e = 3. Зашифруем c = 73 mod 77 = 343 % 77 = 35. Число 7 представлено в зашифрованном виде как 35.

    Расшифруем с помощью секретной экспоненты d=47, итак m = 3547 mod 77. Я немного схитрил, т.к. на калькуляторе это не вычислить, использовал алгоритм быстрого возведения в степень, о нем речь ниже. В итоге, результат получился 7 - исходное число.

    Все, процесс шифрования и дешифрования завершен.


Расширенный алгоритм Евклида

Я, на самом деле, еще не до конца понял как выводится алгоритм Евклида. Пока что напишу, что я понимаю, а потом как-нибудь допишу, что я понял.

Для RSA вот что важно. Чтобы найти d в соотношении d = e-1 mod φ(n), нужно вычислить НОД от числа "e" и от числа φ(n). Он всегда будет равен 1, потому что эти 2 числа - взаимно простые, а значит, их наибольший общий делитель - это 1 (единица). Но нам нужно именно "расширенный" вариант НОД, который представляется вот так:

НОД(a,b) = a*x + b*y = d;

В нашем случае a = e, b = φ(n), а d = 1 всегда, т.е.

НОД(e, φ(n)) = e*x + φ(n)*y = 1;

Расширенный алгоритм Евклида как раз и находит числа x и y, и часто x меньше 0, а y = 1.

Приведу программу на C:

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;
}

Если что, я пока эту программу не понял.

Ладно, допустим, надо нам вычислить НОД от чисел e=3 и φ(n)=70 из примера выше. Запустив программу, мы получим следующее: x = -23, y = 1, d = 1. Нас интересует только коэффициент перед числом "e", а он там -23 (т.е. это x). Перед числом φ(n) может быть совершенно любой целочисленный коэффициент, это не влияет ни на что, потому что y*φ(n) mod φ(n) = 0 в любом случае, т.к. φ(n) делится на себя без остатка при любом коэффициенте.

Чтобы коэффициент -23 превратить в нужный положительный нам коэффициент и не испортить ничего, мы добавим к "y" некое слагаемое и оно будет равно наше "e".

Пример, найден x = -23, y = 1, что выходит в виде формулы: (-23*e + 1*φ(n)) % φ(n) = 1.

Добавим +e к y=1, т.е. -23*e + e*φ(n) + 1*φ(n), а поскольку добавлять можно сколько угодно, мы выберем так, чтобы это совпало c "e". Итак, мы получаем e*(-23 + φ(n)) + y*φ(n), что в любом случае будет равно по модулю 1.

Получается, что если у нас будет отрицательный "x", чтобы сделать его положительным, надо добавить φ(n), что и будет равняться секретной экспоненте d. Т.е. -23 + 70 = 47. Коэффициент 47 и будет наша секретная экспонента, т.е. (d * e) % φ(n) = 1.

Что-то больно сложно выходит.

Алгоритм быстрого возведения в степень

С ним я разбирался как-то довольно долго, но в итоге понял. Суть алгоритма быстрого возведения в степень в том, что мы не делаем последовательно n умножений числа, которое мы возводим в степень, а пользуемся его бинарным представлением.

Например, надо нам срочно возвести в степень число 3, а степень немалая, она 5226. Мы можем тупо взять и начать перемножать 3 по 5226 раз, а можем вспомнить математику и оказаться хитрее. Итак, в математике есть такое правило: ab * ac = ab + c

Совершенно любое число можно разложить на степени двоек, т.е. число 5226 у нас разложится в такую последовательность = 4096 + 1024 + 64 + 32 + 8 + 2. А это значит, что:
a5226 = a(2 + 8 + 32 + 64 + 1024 + 4096) = a2a8a32a64a1024a4096.

Как мы можем также видеть, число 522610 представляется в виде бинарного числа 10100011010102, где единицы - это и есть сомножители в нужной степени.

Ниже представлена программа на C, которая рассчитывает такую степень, но по модулю m. То есть, программа рассчитывает "a" в степени "b" по модулю "c".

Алгоритм работы программы:

  • Вначале, мы умножаем все на 1, r = 1
  • Начинаем смотреть слева направо - со старших разрядов
  • Если текущий разряд (возводимого в степень числа) равен 1, то умножаем на "r" на "a", или, если 0, то на единицу - нет множителя
  • После умножения, возводим в степень 2 (или в степень 1, если смотрим самый младший разряд)
  • Рассчитываем модуль по "m" от полученного "r"
  • Повторяем, пока не завершатся все разряды

В итоге, самые старшие разряды будут возведены в степень столько раз, в котором этот разряд находится, и все они будут перемножены между собой, где разряд = 1.

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;
}

printf("%li\n", fpow(20735, 23527, 33389)); // =84

Примеры

Простой пример быстрого возведения в степень по модулю:

Возвести в степень (3 ^ 9) % 17, где 10012 = 9
Итак: r=1

    1: (r*a)^2 % c = r
    0: (r*1)^2 % c = r
    0: (r*1)^2 % c = r
    1: (r*a)^1 % c = r

Результат =14

    (1*3)^2 % 17 = 9
    (9*1)^2 % 17 = 13
    (13*1)^2 % 17 = 16
    (16*3)^1 % 17 = 14

Бинго!

Алгоритм быстрого возведения в степень по модулю:

    Ri+1 = (Ri * abi)2 mod c,

Где bi = 0 или 1 слева направо, в последнем разряде ^2 ==> ^1