Использование алгоритма Шора для доступа к сообщениям RSA без факторинга

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

В случае RSA, если когда-либо будет построен реальный размер для Алгоритм нахождения периода Шора злоумышленник может факторизовать модуль, а затем может раскрыть сообщения, используя закрытый ключ, за полиномиальное время или лучше за БКП.

• Возможно ли это с помощью модифицированного алгоритма Шора (или другого), который не учитывает модуль, но выявляет сообщение, зашифрованное в соответствии с учебником RSA или правильно дополненным RSA?
• Есть ли опубликованная работа, подобная этой?

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

Я могу дать только очень простой ответ.

В книге Н. Дэвида Мермина Квантовая информатика: введение, в своем объяснении шифрования RSA в разделе 3.3 он говорит

Нахождение эффективного периода представляет интерес в этой криптографической установке не только потому, что оно ведет непосредственно к эффективному факторингу (как описано в разделе 3.10), но также и потому, что оно может напрямую привести Еву к альтернативному способу декодирования сообщения Алисы. $b$ без ее ведома или необходимости вычислять факторы $р$ и $q$ из $N$ [Открытый ключ Боба]. Вот как это работает:

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

Этот последний метод кажется мне несколько более сложным для понимания, но я не знаю, какой метод требует больше вычислительных ресурсов. Я подозреваю, что они довольно близки к эквиваленту, потому что я думаю, что они отличаются только классической постобработкой, а не использованием квантового преобразования Фурье. (Хотя я считаю, что классическая постобработка на самом деле является вычислительным узким местом для алгоритма Шора, так что, возможно, есть существенная разница в ресурсах.)

Для модуля RSA алгоритм Шора (с высокой вероятностью) вернет большой коэффициент мультипликативного порядка некоторого базового элемента по модулю $N$. Различные дополнительные классические алгоритмы могут использовать это для возврата коэффициентов $N$, но в равной степени можно напрямую использовать эти выходные данные для вычисления эффективного показателя дешифрования, не утруждая себя вычислением коэффициентов. В частности, если $к$ является результатом алгоритма Шора, а затем решает $de\equiv 1\pmod{100!k}$ вероятно, обеспечит эффективный показатель степени дешифрования $д$ (необходимо следить за тем, чтобы $100!$ не имеет общих факторов с $е$, но мы можем просто разделить их).

Этот подход действительно экономит время только на классической постобработке и ничего на квантовых вычислениях. Алгоритм Шора чертовски эффективен, и его трудно придумать для существенных улучшений. Один случай, когда я мог бы предположить, что одно сообщение обходится дешевле для атаки, — это если мы знаем/верим, что зашифрованный текст имеет значительно меньший множительный порядок по модулю. $N$. Затем мы можем специально выбрать наше сообщение в качестве основы для нашей атаки, используя алгоритм Шора. В этом случае мы можем параметризовать наше квантовое преобразование Фурье, чтобы восстановить порядки с точностью до некоторого предела. $b$ а не полный $\лямбда(N)$, требуя примерно 2 миллиарда долларов QFT-кубиты, а не $2\лямбда(N)$ Кубиты QFT. В учебнике RSA или RSA со стандартизированным дополнением нет ничего, что мешало бы маленьким мультипликативным порядкам, но это маловероятно.

ETA: Если мы восстановим небольшой заказ, скажем, $г$ затем решение $de\equiv 1\pmod r$ обеспечивает показатель степени дешифрования, который работает для элемента малого порядка, но не будет работать для общего зашифрованного текста. Вероятность наличия небольшого заказа будет сильно зависеть от факторов $p-1$ и $q-1$. А очень грубая верхняя граница доли шифротекстов, имеющих порядок менее $b$ будет $$\sum_{d|\lambda(N):d>\lambda(N)/b}\frac1d.$$