Взламывание коротких ключей RSA

Question

Учитывая следующие ключи RSA, как можно определить, какие значения p и q ?

Public Key: (10142789312725007, 5)
Private Key: (10142789312725007, 8114231289041741)

Answer 1

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

Открытый ключ: (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-соединения . "

Answer 2

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

sqrt(10142789312725007) = 100711415.9999997567

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

10142789312725007 / 100711409 = 100711423 

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

Answer 3

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

Answer 4

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

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

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

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

Answer 5

Вот реализация Java быстрого метода факторинга из Руководства по прикладной криптографии глава 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)

Answer 6

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

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

Answer 7

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

ed - 1 - это кратное phi(n) = (p-1)(q-1),так, по крайней мере, кратное 4.
ed - 1 может быть вычислено как 40571156445208704, что равно 2^7 * 316962159728193, и мы называем s=7 и t = 316962159728193.(в общем случае: любое четное число является степенью, в 2 раза большей нечетного).Теперь выберите случайным образом [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 или -1mod n.В последнем случае gcd(x-1, n) является нетривиальным делителем n, и поэтому p или q, и все готово.Можно показать, что случайный a будет работать с вероятностью около 0,5, поэтому нам нужно несколько попыток, но в целом не очень много.

Answer 8

Эти две статьи могут пригодиться

• Андрей Дюжелла - вариант атаки Винера на RSA
• Андрей Дюжелла - продолжение фракцийи RSA с небольшим секретным показателем

наткнулся на них, когда я проводил некоторые фундаментальные исследования по непрерывным дробям.

Answer 9

Извините за некромантию, но друг спросил меня об этом, и, указав его здесь, я понял, что мне не очень понравился ни один из ответов.После факторизации модуля и получения простых чисел (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 бит за разумное количество времени.

Answer 10

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