Взлом коротких ключей RSA

Ваш учитель дал вам:

Открытый ключ: (10142789312725007, 5)

что значит

n = 10142789312725007
e = 5 

где n — модуль, а e — общедоступный показатель степени.

Кроме того, вам дается

Закрытый ключ: (10142789312725007, 8114231289041741)

означающий, что

 d = 8114231289041741

где d — показатель степени расшифровки, который должен оставаться в секрете.

Вы можете «сломать» RSA, зная, как разложить «n» на его простые множители «p» и «q»:

n = p * q

Вероятно, самый простой способ — проверить все нечетные числа, начинающиеся чуть ниже квадратного корня из n:

Floor[Sqrt[10142789312725007]] = 100711415

Вы получите первый множитель за 4 попытки:

10142789312725007 mod 100711415 = 100711367
10142789312725007 mod 100711413 = 100711373
10142789312725007 mod 100711411 = 100711387
10142789312725007 mod 100711409 = 0 <-- Winner since it evenly divides n

Итак, у нас есть

 p = 100711409

В настоящее время,

 q = n / p 
   = 10142789312725007 / 100711409
   = 100711423

Почему это важно? Это потому, что d — это специальное число, такое что

d = e^-1 mod phi(n)
  = e^-1 mod (p-1)*(q-1)

Мы можем проверить это

d * e = 40571156445208705 = 1 mod 10142789111302176

Это важно, потому что если у вас есть открытое текстовое сообщение m, то зашифрованный текст

c = m^e mod n

а вы его расшифровываете

m = c^d = (m^e)^d = (m^(e*d)) = (m^(e*e^-1)) = m^1 (mod n)

Например, я могу «зашифровать» сообщение 123456789, используя открытый ключ вашего учителя:

m = 123456789

Это даст мне следующий зашифрованный текст:

c = m^e mod n 
  = 123456789^5 mod 10142789312725007
  = 7487844069764171

(Обратите внимание, что на практике «e» должно быть намного больше, потому что для небольших значений «m» вы даже не превышаете n)

В любом случае, теперь у нас есть "c", и мы можем поменять его местами на "d".

m = c^d mod n
  = 7487844069764171^8114231289041741 mod 10142789312725007
  = 123456789

Очевидно, что вы не можете вычислить "7487844069764171^8114231289041741" напрямую, потому что оно состоит из 128 808 202 574 088 302 цифр, поэтому вы должны использовать модуль возведение в степень трюк.

В «реальном мире» n явно намного больше. Если вы хотите увидеть реальный пример того, как HTTPS использует RSA под прикрытием с 617-значным n и e из 65537, см. мою запись в блоге "Первые несколько миллисекунд соединения HTTPS".

Вот относительно простой способ взглянуть на это (и тот, который выполним вручную). Если бы вы должны были полностью разложить число на множители, то самый высокий фактор, который вам нужно было бы учитывать, - это sqrt (N):

sqrt(10142789312725007) = 100711415.9999997567

Первое простое число ниже этого — 100711409, всего на 6 меньше, чем sqrt(N).

10142789312725007 / 100711409 = 100711423 

следовательно, это два множителя N. Ваш профессор сделал это довольно просто — хитрость в том, чтобы признать, что никто не выберет маленький p или q, поэтому начните проверку снизу (как в скрипте Python кто-то написал) это плохая идея. Если это будет практично вручную, большие p и q должны лежать около sqrt(N).

Существуют различные быстрые алгоритмы для решения задачи факторизации n при заданных n, e и d. Вы можете найти хорошее описание одного из таких алгоритмов в Handbook of Applied Cryptography, Глава 8, раздел 8.2.2. Вы можете найти эти главы онлайн для бесплатной загрузки здесь. Алгоритм, по сути, представляет собой тщательную разработку ответа Хенно Брандсма на этот самый вопрос.

ОБНОВЛЕНИЕ 25 сентября 2019 г.:

В комментарии ниже пользователь Imperishable Night предлагает альтернативный метод, который должен быть, по крайней мере, концептуально более простым для понимания.

Он отмечает, что обычно e мало. На самом деле e почти всегда равно 65537. В случае, когда e мало, вы можете построить квадратное уравнение с неизвестным простым числом p и, таким образом, легко решить его, используя, например, квадратичная формула. Чтобы продолжить, давайте установим x=p и найдем x, просто придерживаясь соглашения. Мы знаем, что ed = 1 mod phi(n) или, что то же самое, ed - 1 = k * (p-1)*(q-1). Теперь установив x=p и, следовательно, n/x=q, умножив обе части на x и переставив члены, мы имеем
k*x² + (d*e - k*n - k - 1)*x + k *n = 0.
Теперь у нас есть уравнение формы ax² + bx + c = 0, и мы можем найти x, используя квадратичную формулу. Таким образом, мы можем попробовать значения k в небольшом диапазоне около e, и должно быть только одно целочисленное решение квадратного уравнения, решение для правильного k.

Примечания:

1. Все должно быть целым числом, поэтому дискриминант должен быть полным квадратом, иначе мы можем отбросить k и попробовать следующее. Кроме того, числитель должен делиться на 2*k.
2. Иногда вместо фи-функции Эйлера используется лямбда-функция Кармайкла. Это немного усложняет ситуацию, потому что теперь мы также должны угадать g = gcd(p-1, q-1). g всегда четно, часто равно 2, а в остальном почти всегда немного кратно 2.

ОБНОВЛЕНИЕ 26 сентября 2019 г.:

Найти k на самом деле очень просто, когда e мало. Взяв уравнение ed - 1 = k * (p-1)*(q-1) и разделив обе его части на n, довольно легко увидеть, что floor((ed-1)/n) + 1 == k. Теперь, используя уравнения 31 и 32 из M.J. Винера "Криптоанализ коротких показателей секретности RSA" можно напрямую восстановить p и q.

Wolframalpha говорит мне, что коэффициенты равны 100711409 и 100711423.

Я только что написал наивный Python-скрипт для брутфорса. Как отметил amdfan, лучше начинать сверху:

p = 10142789312725007
for i in xrange(int(p**0.5+2), 3, -2):
    if p%i == 0:
        print i
        print p/i
        break

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

Определение RSA говорит вам, что модуль n = pq. Вы знаете n, поэтому вам просто нужно найти два числа p и q, которые умножаются на n. Вы знаете, что p и q простые числа, так что это проблема факторизации простых чисел.

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

Вот реализация метода быстрого факторинга на Java из главы Handbook of Applied Cryptography 8 раздел 8.2.2 (спасибо GregS за его нахождение):

/**
 * Computes the factors of n given d and e.
 * Given are the public RSA key (n,d)
 * and the corresponding private RSA key (n,e).
 */
public class ComputeRsaFactors
{
    /**
     * Executes the program.
     *
     * @param args  The command line arguments.
     */
    public static void main(String[] args)
    {
        final BigInteger n = BigInteger.valueOf(10142789312725007L);
        final BigInteger d = BigInteger.valueOf(5);
        final BigInteger e = BigInteger.valueOf(8114231289041741L);

        final long t0 = System.currentTimeMillis();

        final BigInteger kTheta = d.multiply(e).subtract(BigInteger.ONE);
        final int exponentOfTwo = kTheta.getLowestSetBit();

        final Random random = new Random();
        BigInteger factor = BigInteger.ONE;
        do
        {
            final BigInteger a = nextA(n, random);

            for (int i = 1; i <= exponentOfTwo; i++)
            {
                final BigInteger exponent = kTheta.shiftRight(i);
                final BigInteger power = a.modPow(exponent, n);

                final BigInteger gcd = n.gcd(power.subtract(BigInteger.ONE));
                if (!factor.equals(BigInteger.ONE))
                {
                    break;
                }
            }
        }
        while (factor.equals(BigInteger.ONE));

        final long t1 = System.currentTimeMillis();

        System.out.printf("%s %s (%dms)\n", factor, n.divide(factor), t1 - t0);
    }


    private static BigInteger nextA(final BigInteger n, final Random random)
    {
        BigInteger r;
        do
        {
            r = new BigInteger(n.bitLength(), random);
        }
        while (r.signum() == 0 || r.compareTo(n) >= 0);
        return r;
    }
}

Типичный вывод

100711423 100711409 (3ms)

Эти две статьи могли бы оказаться полезными

• Андрей Дуйелла — вариант атаки Винера на RSA
• Андрей Дуйелла - Непрерывные дроби и RSA с малым секретным показателем

Наткнулся на них, когда проводил базовые исследования цепных дробей.

Алгоритм для этого (и он будет работать для любого примера, а не только для этого маленького, который может быть легко разложен на любом компьютере):

ed - 1 кратно phi(n) = (p-1)(q-1), поэтому оно как минимум кратно 4.
ed - 1 можно вычислить как 40571156445208704, что равно 2^7 * 316962159728193, и мы называем s=7 и t = 316962159728193. (вообще: любое четное число есть степень удвоенного нечетного числа). Теперь выберите a в [2,n-1) наугад и вычислите (путем последовательного возведения в квадрат по модулю n) последовательность a^t (mod n), a^(2t) (mod n), a^(4t) (mod n).. до не более чем a^((2^7)*t) (mod n), где последним гарантированно будет 1, путем построения e и d.

Теперь мы ищем первую 1 в этой последовательности. Тот, что перед ним, будет либо +1, либо -1 (тривиальный корень из 1, mod n), и мы повторяем с другим a или некоторым числом x, которое не равно +1 или -1 mod n. В последнем случае gcd(x-1, n) является нетривиальным делителем n, а значит, p или q, и мы закончили. Можно показать, что случайное a сработает с вероятностью около 0,5, поэтому нам нужно несколько попыток, но в целом не очень много.

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

Извините за некромантию, но друг спросил меня об этом, и, указав ему здесь, я понял, что мне не очень нравится ни один из ответов. После факторизации модуля и получения простых чисел (p и q) вам нужно найти тотиент, который равен (p-1)*(q-1).

Теперь, чтобы найти частную экспоненту, вы должны найти инверсию публичной экспоненты по модулю totient.

public_exponent * private_exponent = 1 mod totient

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

Я написал код:

// tinyrsa.c
//
// apt-get install libgmp-dev
// yum install gmp-devel
//
// gcc tinyrsa.c -o tinyrsa -lm -lgmp

#include<stdio.h>
#include<gmp.h>

int main()
{
  // declare some multi-precision integers
  mpz_t pub_exp, priv_exp, modulus, totient, fac_p, fac_q, next_prime;

  mpz_init_set_str(pub_exp,"5",10);
  mpz_init_set_str(modulus,"10142789312725007",10);

  mpz_init(priv_exp);
  mpz_init(totient);
  mpz_init(fac_p);
  mpz_init(fac_q);

  // now we factor the modulus (the hard part)
  mpz_init(next_prime);
  mpz_sqrt(next_prime,modulus);
  unsigned long removed=0;
  while(!removed)
  {
    mpz_nextprime(next_prime,next_prime);
    removed=mpz_remove(fac_p,modulus,next_prime);
  }

  mpz_remove(fac_q,modulus,fac_p);
  // we now have p and q

  // the totient is (p-1)*(q-1)  
  mpz_t psub, qsub;
  mpz_init(psub);
  mpz_init(qsub);

  mpz_sub_ui(psub,fac_p,1);
  mpz_sub_ui(qsub,fac_q,1);
  mpz_mul(totient,psub,qsub);

  // inverse of the public key, mod the totient..
  mpz_invert(priv_exp,pub_exp,totient);

  gmp_printf("private exponent:\n%Zd\n",priv_exp);

}

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

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

Вам нужно факторизовать модуль, это первый параметр открытого ключа, 10142789312725007. Подойдет грубая сила (проверьте каждое нечетное число от 3 до sqrt(n), если это фактор), хотя существуют более сложные/быстрые алгоритмы.

Поскольку число слишком велико, чтобы вписаться в обычное целое число (даже 64-битное), вам может понадобиться числовая библиотека, которая поддерживает целые числа произвольной длины. Для C есть GMP и MPIR (более удобный для Windows). Для PHP есть Bignum. Python поставляется со встроенным — встроенный целочисленный тип данных уже имеет произвольную длину.

Существует много плохих предположений о факторизации больших полупростых чисел, которые переходят к грубой силе или просеиванию, ни одно из которых не требуется для факторизации полупростых чисел. 64-битная версия занимает 1-2 секунды на моем компьютере, а 256-битная обычно менее 2 дней.