Введение

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

В настоящее время алгоритм RSA уже постепенно и планомерно заменяется асимметричной криптографией на эллиптических кривых за счёт сохранения старого уровня безопасности с меньшей длиной ключа. Но всё же, он до сих пор занимает лидирующие позиции по своему применению и вполне оправданно, учитывая его относительно долгую историю для раздела асимметричной криптографии.

На Хабре алгоритм RSA не раз обсуждался и критиковался, как например тут, тут, тут, но весь анализ сводился либо к анализу конкретного недостатка / уязвимости, либо к неправильному использованию / применению старого стандарта. Всё это неплохо, но не даёт полной картины того, чем всё же может быть опасна чистая математическая структура алгоритма RSA.

RSA в двух словах

Генерация ключей:

1. Генерируем пару больших простых чисел p,q, где p ≠ q,

2. Создаём число n = pq,

3. Создаём число e, где НОД(e, ф(n)) = 1, ф(n) = ф(pq) = ф(p)ф(q) = (p-1)(q-1),

4. Находим число d, где d ≡ e^-1 (mod ф(n)).

Числа {e,n} - публичный ключ, числа {d, n} - приватный ключ. Числа e и d - открытая и закрытая экспоненты соответственно, являются друг к другу обратными числами: d = e^-1 => ed ≡ 1 (mod ф(n)). ф(n) - функция Эйлера - количество взаимнопростых чисел к числу n от 1 до n-1 включительно. НОД - наибольший общий делитель, если НОД(a, b) = 1, тогда считается, что a, b - взаимнопростые числа (нет общих делителей кроме единицы).

Шифрование / расшифрование:

1. Шифрование: c ≡ m^e (mod n),

2. Расшифрование: m ≡ c^d (mod n).

Корректность расшифрования базируется преимущественно на теореме Эйлера, которая гласит:

Теорема Эйлера

Если НОД(a, n) = 1, то a^ф(n) ≡ 1 (mod n)

Следовательно, если НОД(m, n) = 1, тогда m^1+ф(n) ≡ m¹ ≡ m (mod n). При шифровании и расшифровании происходит следующее: c^d ≡ (m^e)^d ≡ m^ed ≡ m^ed+ф(n) ≡ m^1+ф(n) ≡ m (mod n). Существует два частных случая, которые не подпадают под условие теоремы Эйлера, а именно когда НОД(m, n) = p ≠ 1 или НОД(m, n) = q ≠ 1. В таком случае, m ≡ 0 (mod p) или m ≡ 0 (mod q), и как следствие, m^ed всегда ≡ m (mod p) или ≡ m (mod q). Как итог, из китайской теоремы об остатках следует, что m^ed всегда ≡ m (mod n).

Китайская теорема об остатках

Пусть n₁, n₂, ..., n_k — натуральные попарно взаимно простые числа, а r₁, r₂, ..., r_k — некоторые целые числа, тогда существует такое целое число M, что оно будет решением системы сравнений:

M ≡ r₁ (mod n₁)
M ≡ r₂ (mod n₂)
...
M ≡ r_k (mod n_k)

При этом для любых двух решений A и B этой системы справедливо A ≡ B (mod n₁n₂...n_k), то есть решение системы сравнений существует и единственно по модулю n₁n₂...n_k.

Безопасность RSA, в первую очередь, основывается на задаче факторизации, при которой сложно вычислить ф(n) не зная чисел p,q. В настоящее время все методы поиска ф(n) имеют в своей основе алгоритм полного перебора по большому множеству чисел, но факт того, что сама задача факторизации является сложной - не доказан. Мы можем лишь руководствоваться историей данной задачи и попытками её решения.

Может в будущем всё же будет найден алгоритм быстрого нахождения ф(n), или будет доказано P = NP (что приведёт к доказательству отсутствия существования однонаправленных функций), или будет создан квантовый компьютер с большим количеством стабильных кубитов (на котором будет возможно дальнейшее применение алгоритма Шора).

Атаки на чистый RSA

Чистый алгоритм RSA уязвим к большому количеству способов взлома. Давайте попробуем разобрать некоторые из них. Большинство примеров я постараюсь сопроводить программными кодами.

Атака перебором открытых текстов

Каждое сообщение в алгоритме RSA представлено числом m, не превышающим числа n. Число n всегда должно быть достаточно большим, что обуславливается необходимостью такового выбора числами p и q. Тем не менее число m не обладает таковым ограничением, как следствие, оно может иметь любой размер в диапазоне 0 ⩽ m < n в зависимости от прикладного использования.

Если прикладная логика использования RSA сводится, как пример, к шифрованию выдаваемых зарплат x: c = E_k(x), тогда даже при очень больших суммах, перебор будет являться лёгкой задачей - достаточно лишь перебирать числа от 0 до max(зарплата), шифровать их и сравнивать результаты.

// ms = max_salary
// ds = dec_salary
bool decrypt(pubkey_t pk, ciphertext_t c, uint64_t ms, uint64_t *ds) {
  ciphertext_t сi;
  for (uint64_t i = 0; i < ms; ++i) {
    encrypt(&ci, pk, i);
    if (equal(c, ci)) {
      *ds = i;
      return true;
    }
  }
  return false;
}

Сама проблема базируется на детерминируемости функции шифрования E: при одинаковых вводных условиях (e, n, m) будет получаться один и тот же шифртекст c. От подобной атаки можно избавиться кодированием открытого текста до этапа шифрования: c = E(Encode(m)). Кодирование при этом должно обладать недетерминируемым свойством, привносить в текст случайные байты, так, чтобы (c₁ = E(Encode(m))) ≠ (c₂ = E(Encode(m))) при многократном использовании. В эту же очередь, должна существовать такая функция декодирования, которая бы однозначно возвращала первичный открытый текст без искажений: Decode(D(c₁)) = Decode(D(c₂)) = m. В современном мире для этого используется схема шифрования OAEP (Optimal Asymmetric Encryption Padding).

Атака логарифмирования

Хоть базовая задача, на которой основывается RSA, действительно является задачей факторизации, тем не менее, она не является единственной. Когда RSA исполняет функцию расшифрования, то начинает играть лидирующую роль задача дискретного логарифмирования.

Задача дискретного логарифмирования сводится к поиску числа x из имеющегося числа y ≡ g^x (mod n). Отличие обычной задачи логарифмирования от дискретного сводится к существованию модуля n, через который число y = g^x "обрезается". Таким образом, в задаче логарифмирования y - это есть результат возведения в степень, в задаче дискретного логарифмирования y - это есть остаток от деления результата возведения в степень.

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

Атака логарифмирования на алгоритм RSA сводится к ошибке выбора малых открытых экспонент, как например e = 3, при которых начинает возникать ситуация: m^e < n. Это, в свою очередь, приводит к возможности лёгкого восстановления закрытого ключа, как в обход задачи дискретного логарифмирования: g^x (mod n) = g^x, так и в обход задачи факторизации: 1/e = d ≡ e^-1 (mod ф(n)). Таким образом, если существует шифртекст c, который был получен в ходе использования малой открытой экспоненты e: c ≡ m^e (mod n), то велика вероятность, что шифртекст можно расшифровать следующим образом: m = c^1/e, в обход модуля n.

uint64_t p = 17, q = 101;
uint64_t n = p*q; // 1717
uint64_t fn = (p-1)*(q-1); // 1600
uint64_t e = 3;
assert(gcd(e, fn) == 1); // НОД(e, ф(n)) = 1 => существует d
    
uint64_t d = invmod(e, fn); // d = e^(-1) (mod ф(n)) = 3^(-1) (mod 1600) = 1067
uint64_t m = 4;
uint64_t c = expmod(m, e, n); // c = m^e = 4^3 = 64
uint64_t r1 = round(pow(c, 1./e)); // c^(1/e) = 64^(1/3) = 4
uint64_t r2 = expmod(c, d, n); // c^d mod n = 64^1067 mod 1717 = 4
assert(r1 == r2);

// Алгоритм Евклида
uint64_t gcd(uint64_t a, uint64_t n) {
    uint64_t t;
    while(n != 0) {
      t = a;
      a = n;
      n = t%n;
    }
    return a; 
}

// Расширенный алгоритм Евклида
uint64_t invmod(uint64_t a, uint64_t n) {
    uint64_t tx = 0, x0 = 1, x1 = 0;
    uint64_t q = 0, r = 0;
    uint64_t tn = n;
    while (n != 0) {
        q = a / n, r = a % n;
        tx = x0 - q * x1;
        a = n, n = r;
        x0 = x1, x1 = tx;
    }
    return (x0 + tn) % tn;
}

// Быстрое возведение в степень по модулю
uint64_t expmod(uint64_t a, uint64_t b, uint64_t n) {
	uint64_t result = 1;
	for (uint64_t bit = 1; bit <= b; bit *= 2) {
		if (bit & b)
			result = (result * a) % n;
		a = (a * a) % n;
	}
	return result;
}

Чтобы избежать такую атаку, необходимо выбирать умеренно большую открытую экспоненту e. Чаще всего используется открытая экспонента следующего вида: e = 2^{2^4}+1 = 2¹⁶+1 = 65537. Такое число является пятым числом Ферма (отчёт с нуля) и выбрано не случайно. Суть заключается в том, что бинарное представление всех чисел Ферма содержит только две единицы: 1000000...0000001, что позволяет совершать меньше операций умножения за счёт применения алгоритма быстрого возведения в степень. Но такое свойство будет являться безопасным, только при шифровании или проверках подписи. Когда используется расшифрование или подписание, т.е. когда используется приватный ключ, применение быстрого возведения в степень должно всегда осуществляться с двумя операциями умножения, вне зависимости от нулей и единиц в двоичном представлении ключа. В противном случае, на приватный ключ могут распространяться атаки по времени.

Плюс к этому, в частных случаях, даже выбирая относительно большую открытую экспоненту e = 2¹⁶+1 может возникнуть ситуация некорректного шифрования, когда m^e всё также будет меньше модуля n. Этим частным случаем являются открытые тексты m = 0 и m = 1, которые не будут никак шифроваться. Чтобы избавиться от этого недостатка, необходимо также применять схемы кодирования до этапа шифрования или подписания.

Атака единого ключа

Алгоритм RSA способен не только шифровать информацию, но и подписывать её. При всём этом, функция подписания информации S равносильна функции её расшифрования D, а функция проверки подписи V равносильна функции шифрования E. Иными словами, если существует текст x, то: S(x) = D(x) = x^d mod n, V(x) = E(x) = x^e mod n.

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

Предположим, что существует некий сервис, который способен подписывать отправленную ему информацию закрытым ключом k^-1. При этом, секретное общение с этим же сервисом ведётся благодаря его публичному ключу k. В таком случае, чтобы узнать содержимое отправленного секретного текста c = E_k(m), злоумышленник может просто навсего попросить у самого сервиса подписать шифртекст: S_k^-1(c) = S_k^-1(E_k(m)) = D_k^-1(E_k(m)) = m.

Но можно также предположить, что сервис учитывает ранее принятые шифртексты и дважды их не обрабатывает. В таком случае, злоумышленник может поступить хитрее - отправить не c, а c' ≡ r^kc (mod n), где r - случайное сгенерированное число с условием НОД(r, n) = 1. При таком сценарии произойдёт следующее: S_k^-1(c') = S_k^-1(r^kc) = S_k^-1(E_k(r)E_k(m)) = D_k^-1(E_k(rm)) = rm. Всё что остаётся злоумышленнику - умножить полученный результат на обратное число случайному: r^-1rm ≡ m (mod n).

Во избежание такой проблемы необходимо либо применять разные ключи шифрования, либо разные схемы кодирования. Так например, в реальном мире для шифрования используется схема OAEP, а для подписания PSS (Signature Scheme with Appendix-Probabilistic Signature Scheme).

Атака «встреча посередине»

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

E_k(m₁)E_k(m₂) = E_k(m₁m₂) <=> m₁^em₂^e ≡ (m₁m₂)^e ≡ c (mod n)

Такое интересное свойство, помимо возможного дальнейшего прикладного применения, приносит и ряд дополнительных неприятностей, а именно: что если, число m будет составным? Такое условие более чем реально, т.к. вероятность того, что число m окажется составным выше, чем если бы оно оказалось простым.

Основная теорема арифметики

Любое натуральное число n > 1 можно разложить на простые множители, т.е. записать в виде n = p₁^d₁p₂^d₂...p_k^d_k, где p_i - простые множители, d_i - натуральные числа.

Предположим, что составное число m представлено двумя простыми множителями p₁ и p₂. В таком случае, алгоритм RSA будет проявлять мультипликативное свойство: E_k(m) = E_k(p₁p₂) = E_k(p₁)E_k(p₂) <=> p₁^kp₂^k ≡ c (mod n). Далее предположим, что под числом m = p₁p₂ понимается случайный 64-битный симметричный ключ шифрования. В таком случае, для нахождения правильного ключа шифрования злоумышленнику потребуется осуществить не 2⁶⁴ операций шифрования, а всего лишь 2³³.

Такое становится возможным за счёт сравнивающего перебора с двух сторон вычислений для 2 ⩽ y ⩽ 2³², 2 ⩽ x ⩽ 2⁶⁴ => p₁^kp₂^k(x^k)^-1 ≡ y^k (mod n). Результатом расшифрования станут числа (x = p₁, y = p₂) или (x = p₂, y = p₁) => p₁p₂ = m.

import math

p = 129765116189934447386218567135214456447225548887413779366409285893621919735749
q = 52464445694847850526312013404560730738901192255658078180137041242614031905553
n = p*q # n = 512 bit
fn = (p-1)*(q-1)
e = (1<<16)+1 # e = 2^16+1 = 65547 
assert math.gcd(e, fn) == 1

def gcd_extended(a, b):
    if a == 0 :
        return b, 0, 1
    gcd,x1,y1 = gcd_extended(b%a, a)
    x = y1 - (b//a) * x1
    y = x1
    return gcd, x, y

def decrypt(enck: int, kbits: int):
    full_maxv = 1 << kbits
    half_maxv = 1 << (kbits//2)
    is_even = enck%2 == 0 
    mapi = {}
    for y in range(2, half_maxv):
        if is_even and y%2==0: continue 
        c_exp_y = pow(y, e, n)
        mapi[c_exp_y] = y
    for x in range(2, full_maxv):
        if is_even and x%2==0: continue 
        _, inv, _ = gcd_extended(pow(x, e, n), n)
        c_inv_exp_x = (enck*inv) % n
        if c_inv_exp_x in mapi:
            return x*mapi[c_inv_exp_x]
    raise "decrypt failed"

skey = 0xB3AF1FDF1F # 40-bit secret key = 771737247519
enck = pow(skey, e, n)
print(decrypt(enck, 40))

$ time python3 main.py                                                                                              INT ✘  46s  
> 771737247519
> python3 main.py  179,87s user 17,59s system 99% cpu 3:19,26 total

Чтобы обезопасить себя от подобной уязвимости, необходимо убрать свойство мультипликативности. Это становится возможным также за счёт применения схем кодирования по типу OAEP и PSS.

Заключение

В ходе нашего небольшого анализа мы смогли рассмотреть ряд уязвимостей чистого RSA и увидеть, что каждый рассмотренный недостаток был бы в действительности губителен, если бы не существовало дополнительных схем кодирования, по типу OAEP (для шифрования) и PSS (для подписания).