Взломать короткие ключи RSA

StackOverflow https://stackoverflow.com/questions/4078902

Вопрос

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

Public Key: (10142789312725007, 5)
Private Key: (10142789312725007, 8114231289041741)
Это было полезно?

Решение

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

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

что значит

n = 10142789312725007
e = 5

куда N. это модуль и свидетельствовать является публичным показателем.

Кроме того, вы даете

Частный ключ: (10142789312725007, 8114231289041741)

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

 d = 8114231289041741

куда подразделение Это дешифрование, которое должно оставаться в секрете.

Вы можете «сломать» 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 = e^-1 mod phi(n)
  = e^-1 mod (p-1)*(q-1)

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

d * e = 40571156445208705 = 1 mod 10142789111302176

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

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. и ан свидетельствовать 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. Отказ Вы можете найти хорошее описание одного такого алгоритма в руководстве прикладной криптографии, Глава 8., Раздел 8.2.2. Вы можете найти эти главы онлайн для бесплатного скачивания здесь. Отказ Алгоритм по сути является тщательной разработкой Ответ Henno Brandsma на этот самый вопрос.

Обновление 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.2 + (D * E - K * N - K - 1) * x + k * n = 0.
Теперь у нас есть уравнение формы точка2 + bx + c = 0, и мы можем решить для x с помощью квадратичной формулы. Таким образом, мы можем попробовать значения k в небольшом диапазоне вокруг e И должен быть только один целочисленный раствор для квадратичного, решение для правильного k.

Примечания:

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

Вольфрам Альфа говорит мне, что факторы 100711409 и 100711423

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

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 внедрение метода быстрой факторинга из справочника прикладной криптографии Глава 8. Раздел 8.2.2 (Благодаря Грегам на его нахождение):

/**
 * 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)

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

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

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

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

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

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

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

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 поставляется со встроенным - встроенным целочисленным типом данных уже произвольная длина.

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top