Взлом 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)

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

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

ДЕТАЛИ ДОБАВЛЕНЫ Я пытаюсь представить пользователю последовательный идентификатор из базы данных. Поскольку это последовательно, я не хочу, чтобы пользователь угадывал идентификатор другого пользователя, выполнив несколько регистраций. Чтобы избежать этого, я должен зашифровать его до цифры <= 12. Было много ограничений вокруг этого, которые были объяснены в <a href="https://stackoverflow.com/questions/858476/12-digit-number-java-encryption-question"> этом вопросе .

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

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

Answer 1

RSA уязвим против атаки Chosen-Ciphertext. То есть, скажем, мы хотим разорвать зашифрованный текст 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 2

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

Но 40 бит - это только очень грубая верхняя граница. Злоумышленник может сделать намного лучше. Например, он может угадать фактор р. Затем он вычисляет символы якоби из сообщений и шифротекстов. Если сообщение m является квадратическим вычетом mod p, то зашифрованный текст должен быть квадратичным вычетом mod p, и наоборот. Следовательно, если это отношение не выполняется для пары сообщение / зашифрованный текст, он может отклонить предположение для 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 - ужасная идея. Я действительно не понимаю, почему вы не хотите использовать конструкцию Luby-Rackoff, как я предлагал ранее.

Answer 3

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

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