Крепление коротких ключей RSA

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

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

Ответ 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.

Ответ 2

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

sqrt(10142789312725007) = 100711415.9999997567

Первый штрих ниже этого - 100711409, всего 6 ниже sqrt (N).

10142789312725007 / 100711409 = 100711423

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

Ответ 3

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

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

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

Он отмечает, что обычно 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.

Примечания:

Все должно быть целым числом, поэтому дискриминант должен быть идеальным квадратом, иначе мы можем отбросить k и попробовать следующий. Кроме того, числитель должен делиться на 2*k.
Иногда лямбда-функция Кармайкла используется вместо фи-функции Эйлера. Это немного усложняет ситуацию, потому что теперь мы должны также угадать 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 из М.Дж. Винер "Криптоанализ коротких секретных показателей RSA" можно напрямую восстановить p и q.

Ответ 4

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

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

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

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

Ответ 5

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

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

Ответ 6

Вот реализация 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)

Ответ 7

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

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

Ответ 8

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

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

Ответ 9

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

Ответ 10

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

Ответ 11

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

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

Ответ 12

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