Рейтинг:0

Как знание факторов ключа помогает мне расшифровать?

флаг cn

Недавно я начал изучать криптографию и ее квантовый аспект, и я наткнулся на алгоритм Шора (который решает следующую задачу: «Дано целое число N, найти его простые множители»).

Я также наткнулся на это видео под названием "Как квантовые компьютеры взламывают шифрование | Объяснение алгоритма Шора"

Я все еще не понимаю, как знание факторов ключа поможет мне решить проблему.

kelalaka avatar
флаг in
[Этот ответ может быть полезен] (https://crypto.stackexchange.com/a/70215/18298)
Рейтинг:1
флаг my

Я наткнулся на алгоритм Шора (который решает следующую задачу: «Дано целое число N, найти его простые множители»).

Фактически алгоритм Шора решает задачу «дана периодическая функция $ф$, то есть если $\underbrace{f(f(... f(a))...)}_{k\text{times}} = a$, что такое $к$?"

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

В любом случае, что вы на самом деле спрашиваете, так это «если мы можем факторизовать ключ, как это поможет нам взломать RSA»? Обратите внимание, что, полагаясь на сложность факторизации, от чего зависит RSA; другие методы (например, Диффи-Хеллмана) в равной степени уязвимы для алгоритма Шора, но они используют другой $ф$ функция.

Ну, с RSA, публичным экспонентом $е$ и частный показатель $д$ связаны $e \cdot d \equiv 1 \pmod{\text{lcm}(p-1, q-1)}$. Оказывается, если мы знаем простые множители $р, д$ и мы знаем общественный показатель $е$ (который дан в открытом ключе), легко вычислить закрытый показатель степени $д$; что немедленно дает нам способ расшифровать через $P = C^d \bmod n$.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.