Трещина N бит RSA по модулю

Question

Это связано с моим previous post, где мой единственный вариант - иметь алгоритм RSA, который казался относительно слабым. Предположим, что я хочу кодировать 35-битное число (от 0 до 34359738367) с 36-битным модулем (между 34359738368 и 68719476735).

Ссылаясь на http://en.wikipedia.org/wiki/RSA, я вижу, что мой n находится между 34359738368 и 68719476735 случайным тотальмом (формы p-1 * q-1). Я выбираю случайный d и e. Я кодирую число и показываю, что в пользовательском интерфейсе.

В целях аргумента предположим, что пользователь может видеть до 1000 таких выходов. Может ли он использовать некоторые алгоритмы, такие как Polla или что-то подобное, чтобы взломать мои d, e или n и тем самым начать прогнозировать новые числа? Если да, то как это тяжело? (По просто зная, говорят, 1000 наборов входов/выходов)

В качестве примера (6 выходов рассмотреть в качестве образца на входе/выходного формата),

1. 10001621865,31116156015
2. 10001621866,33031668326
3. 10001621867,37351399313
4. 10001621868,06071714212
5. 10001621869,01188523761
6. 10001621870,18341011998

Может кто-нибудь сказать мне, что мои n, d, e были? (N между 34359738368 до 68719476735)

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

PS: Пользователь не видит «е», как стандартный алгоритм RSA. Он может видеть только наборы выходных выходных данных.

ДЕТАЛИ ДОБАВЛЕНО Я пытаюсь представить последовательный пользовательский идентификатор из БД для пользователя. Поскольку он является последовательным, я не хочу, чтобы пользователь угадал идентификатор другого пользователя, выполнив несколько регистраций. Чтобы этого избежать, я должен сцепить его до < = 12-значное число. Было много ограничений вокруг этого, которые были объяснены в this question.

Также значение n, d и e неизвестно пользователю. Максимум, который может видеть пользователь, - это несколько входных выводов (путем повторной регистрации)

Принимая ответ, отправленный Accipitridae, поскольку алгоритм «Якоби» можно использовать для взлома в течение нескольких секунд. Без знания n, e или p.

Answer 1

Нападающий может угадать коэффициент p из n и e mod (p-1). Каждая догадка может быть проверена путем принятия сообщения m, вычисления m^e mod p, а затем сравнения с c mod p, где c - соответствующий зашифрованный текст. Так как p и e mod (p-1) могут быть 20 бит каждый, это означает, что безопасность схемы не превышает 40 бит.

Но 40 бит - это очень грубая верхняя граница. Злоумышленник может сделать гораздо лучше. Например, он может угадать фактор p. Затем он вычисляет символы Якоби сообщений и зашифрованных текстов. Если сообщение m является квадратичным вычетом mod p, то зашифрованный текст должен быть квадратичным вычетом mod p и наоборот. Следовательно, если это соотношение не выполняется для пары сообщений/зашифрованного текста, он может отклонить предположение для p. Или злоумышленник может вычислять дискретные логарифмы между сообщением и зашифрованным текстом. Это дает гораздо более быстрый кандидат на e mod (p-1).

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

Обновление: Поскольку вы не дали мне 20 образцов для запуска эксперимента, мне пришлось их самостоятельно создавать. С помощью следующих образцов

m = 10001621865 c = 31116156015 
m = 10001621866 c = 33031668326 
m = 10001621867 c = 37351399313 
m = 10001621868 c = 6071714212 
m = 10001621869 c = 1188523761 
m = 10001621870 c = 18341011998 
m = 10001621871 c = 7620400191 
m = 10001621872 c = 36106912203 
m = 10001621873 c = 37615263725 
m = 10001621874 c = 7795237418 
m = 10001621875 c = 34774459868 
m = 10001621876 c = 4555747045 
m = 10001621877 c = 33123599635 
m = 10001621878 c = 34836418207 
m = 10001621879 c = 33962453633 
m = 10001621880 c = 6258371439 
m = 10001621881 c = 7500991556 
m = 10001621882 c = 5071836635 
m = 10001621883 c = 911495880 
m = 10001621884 c = 39558568485 

в качестве входных данных, описанный выше алгоритм находит факторы, 201821 и 206153 в 20ms. Как описано, это не нужно знать e, хотя ваш выбор e = 65537 легко угадать и может быть использован также.

Сила RSA заключается в том, что она основана на сложности факторизации больших целых чисел. Здесь вы устраняете эту трудность, и все остальное - все слабые стороны (т. Е. Математические отношения) RSA. Построение блочного шифра на основе RSA - ужасная идея. Я действительно не понимаю, почему вы не хотите использовать конструкцию Luby-Rackoff, как я предложил ранее.

Answer 2

RSA уязвим против атаки Chosen-Ciphertext. То есть, скажем, мы хотим разбить шифрованный текст y, мы можем использовать одну из пар шифрованного текста - открытого текста, чтобы сломать его.

Как разбить его:

выбрать x0 и y0, где x0 и y0 является открытым текстом-шифротекста пара, которая была предоставлена.

y1 = y0 * y mod n y1 - еще один из 1000 зашифрованных текстов, предоставленных пользователю, который удовлетворяет этим критериям. x1 является дешифрование y1, который также дал, это означает:

x1 = y1^d по модулю п (это было дано нам, мы уже знаем, x1)

x1 = (y0 * у)^д мод п x1 = у0^д * у^д мод п Ξ х0 * х

х1 * х0^-1 = х

й дешифровки у.

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

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

С дополнительной информацией: Без знания n, d или e, абсолютно никакой информации, предоставляемой вообще, что означает, что угадывание комбинаций n, d или e так же хорошо, как угадывание самого открытого текста. Чтобы найти n и e, существует как минимум 43 359 738 367 комбинаций n, чтобы угадать, а также все комбинации e могли бы быть. Это нелегко для кого-то даже с 1000 пар шифротекст-plaintext, чтобы иметь возможность взломать n и e.

Answer 3

Это ужасная идея, 36 бит RSA ?? Почему бы просто не пойти с блоком или потоковым шифром? Таким образом, вы получаете картографирование 1: 1 и гораздо более безопасным способом.

Альтернативным решением, которое я бы рекомендовал, было бы использование SHA-хэша в качестве UID и сохранение последовательного номера для каждого пользователя в базе данных в виде отдельного столбца.