Взлом N-битного RSA по модулю чисел

Question

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

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

Для целей аргументации давайте предположим, что пользователь может видеть до 1000 таких выходных данных.Может ли он использовать какие-нибудь алгоритмы, подобные алгоритму Поллы, или что-нибудь подобное, чтобы взломать мои 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:Пользователь не видит букву "e", как в стандартном алгоритме RSA.Он может видеть только наборы ввода-вывода.

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

Кроме того, значение 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 является квадратичным остатком по модулю p, то зашифрованный текст должен быть квадратичным остатком по модулю 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 за 20 мс.Как описано, для этого не обязательно знать e, хотя ваш выбор e = 65537 легко угадать, и его также можно использовать.

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

Answer 2

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

Как это сломать:

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

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

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

x1 = (y0 * y)^d mod n x1 = y0 ^d * y ^d mod n Ξ x0 * x

x1*x0^-1 = x

x - это расшифровка y.

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

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

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

Answer 3

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

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