RSA шифрование

Всем привет!

В этой статье я старался рассказать максимально простым языком про то, как устроено RSA шифрование

Хочу сделать серию статей, чтобы плавно подойти к тому, как работают ZK-SNARK штуки

Почему симметричное шифрование = неудобно?

Существует два вида шифрования: симметричное и ассиметричное

Приведу простой пример симметричного шифрования

Есть такая штука, называется шифр цезаря (любители генопетс оценят)

Чтобы зашифровать сообщение, мы берем слово, в моем случае это будет слово "дверь", какое-то число не больше размера алфавита (например 2), и заменяем каждую букву на ту, которая находится на 2 буквы дальше

д->ё

в->д

е->ж

р->т

ь->ю

Получаем "ёджтю"

Теперь отправляем нашему другу это сообщение, а при встрече говорим, что число на которое надо сдвигать - это 2, он получает сообщение, и расшифровывает, зная размер сдвига

НО!

Представим ситуацию, что у нас 8531 друг, и каждый сейчас в другой стране

Возникнут некоторые проблемы

Почему асимметричное шифрование = круто?

Объясню пример этого метода на картинках

Представим, что у нас есть замок и ключ от него, а у нашего друга есть сообщение которое он хочет передать, мы "открываем" наш замок, ключом, которые есть только у нас

Отправляем открытый замок нашему другу СДЭКом или любым другим способом

Наш друг получает это замок, прикрепляет к нему свою бумажку с сообщением, закрывает замок и отправляет с бумажкой обратно по почте

Мы получаем сообщение с замком и ключом, который есть только у нас, открываем его и видим сообщение

Победа! Теперь нам не нужно встречаться с каждым другом, чтобы передать сообщение

RSA

Алгоритм шифрования RSA основан на 2 вещах:

1. Произведение двух простых чисел делается просто. Умножить на калькуляторе 5569 и 821 займет меньше 5 секунд, а понять, на какие простые множители раскладывается число, сложно. Какие числа перемножили, чтобы получить 467149?
2. ОЧЕНЬ большие числа длинной 1024 бита. Если кто-то захочет подобрать значения, то уйдут десятки лет

Принцип работы RSA на пальцах

шаг 1. Случайно генерируем два простых числа prime1 и prime2

шаг 2. Вычисляем const n = prime1 * prime2;

и ϕ const phiN = (prime1 - 1) * (prime2 - 1);

ТУТ можно почитать, что за функция ϕ, и почему ϕ(ab)=ϕ(a)*ϕ(b), но в самом алгоритме это несильно важно

шаг 3. Выбираем значение encyptionKey такое, чтобы оно было меньше phiN и было взаимно простое c phiN НОД(encyptionKey, phiN)==1 - его мы будем использовать для шифрования сообщения

шаг 4. Вычисляем значение decryptionKey - его мы будем использовать для расшифровки сообщения (дальше объясню как его считать)

Все! Больше ничего не нужно, теперь шифруем

USER 1 (он хочет получить сообщение). Передает USER 2 n (шаг 2) и encyptionKey (шаг 3)

USER 2 (он хочет отправить сообщение). Получает n и encyptionKey от USER 1, берет свое сообщение m (делаем из текста число, ТУТ написано, как это делается, я использую упрощенный пример m = 5)

и считает encryptedMessage = m^(encyptionKey) mod n

далее предает encryptedMessage USER 1

USER 1. Получает encryptedMessage возводит в степень decryptionKey и берет остаток от деления на n

другими словами decryptedMessage = encryptedMessage^decryptionKey mod n

Победа! decryptedMessage будет равно сообщению, которое мы передали

Проще всего будет понят суть алгоритма на примере кода

Сначала зададим функцию, чтобы проверять простое число или нет. Тут интересный момент, что цикл идет от 2 до sqrt(num), почему это работает написано ТУТ

function isPrime(num) {
  for (let j = 2, n = Math.sqrt(num); j <= n; j++) {
    if (num % j === 0) {
      return false;
    }
  }
  return num;
}

Далее я создаю функцию чтобы, находить случайные простые числа определенной длинны, и путем умножения создаю переменную n, мы будем дальше ее использовать, когда будем хранить, публичный и приватный ключ

const k = 3;
const prime1 = getPrime(k);
const prime2 = getPrime(k);
const n = prime1 * prime2;

Создадим переменную phiN и encyptionKey(взаимно простое с phiN и n)

const phiN = (prime1 - 1) * (prime2 - 1);
const encyptionKey = getEncryptionKey(phiN, n);

function getEncryptionKey(phiN, N) {
  for (let i = 2; i < phiN; i++) {
    if (gcd(i, phiN) === 1 && gcd(i, N) === 1) {
      return i;
    }
  }
}

Тут я использую функцию gcd или Наибольший Общий Делитель по-русски

Существует алгоритм Евклида для поиска НОД, мы вычитаем из наибольшего числа наименьшее, пока одно из них не станет нулем, значит второе - это НОД

Чтобы ускорить процесс мы можем не вычитать, а брать остатки от деления

В JS это выглядит так:

function gcd(a, b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}

Теперь давайте разберемся, как нам найти decriptionKey, чтобы расшифровать сообщение, которое мы потом получим

Нам нужно найти такое значение d(decriptionKey), что при умножении на e(encryptionKey) и получения остатка от деления на ϕ(phiN) получится 1

Это можно сделать перебором, но если числа большие, то процессору будет больно, поэтому используем расширенный алгоритм Евклида ТУТ про то, как он работает, а ТУТ про реализацию, которая работает, потому что важно, чтобы функция не выдавала отрицательные числа, иначе ничего не получится

Вот код на JS:

const decryptionKey = modInv(encyptionKey, phiN);

function modInv(u, v) {
  let u1 = 1;
  let u3 = u;
  let v1 = 0;
  let v3 = v;
  let iter = 1;
  while (v3 != 0) {
    q = Math.floor(u3 / v3);
    t3 = u3 % v3;
    t1 = u1 + q * v1;
    u1 = v1;
    v1 = t1;
    u3 = v3;
    v3 = t3;
    iter--;
  }
  if (u3 != 1) {
    return 0;
  }
  if (iter < 0) {
    inv = v - u1;
  } else {
    inv = u1;
  }
  return inv;
}

Теперь у нас есть encryptionKey, decryptionKey и n

Отправляем второму пользователю encryptionKey и n

Он берет сообщение m(5) возводит в степень encryptionKey и берет остаток от деления на n

Я использовал ethers.js чтобы работать с BigNumber

const m = 5; //less than n-1
const encryptedMessage = BigNumber.from(m).pow(encyptionKey).mod(n);

И отправляет encryptedMessage обратно нам

а мы берем его сообщение и делам почти тоже самое: возводим в степень decryptionKey и берем остаток от деления на n

const decryptedMessage = encryptedMessage.pow(decryptionKey).mod(n);

Ура! Мы расшифровали сообщение и получили 5

Надеюсь статья была полезной

Спасибо за прочтение

Мой телеграм - https://t.me/chpotldev