Рейтинг:1

Расшифровать RSA с известным открытым ключом и модулем и диапазоном dp

флаг in

Как расшифровать RSA при наличии $e$,$n$ и диапазон $дп$ ?

e=2953544268002866703872076551930953722572317122777861299293407053391808199220655289235983088986372630141821049118015752017412642148934113723174855236142887
n=6006128121276172470274143101473619963750725942458450119252491144009018469845917986523007748831362674341219814935241703026024431390531323127620970750816983

пока $дп$ находится в пределах $(1,2^{20})$

Maarten Bodewes avatar
флаг in
Это кажется достаточно маленьким, чтобы учитывать, что вы пробовали? Обратите внимание, что домашние задания / задания не по теме, но мы можем давать подсказки в комментариях, если было приложено достаточно усилий.
Manc avatar
флаг in
Я прошел диапазон dp и попытался вычислить p с i в диапазоне (1, e), затем p = ((dp * e-1)/i) + 1, но публичный показатель слишком велик для прохождения
Рейтинг:1
флаг pe

предположительно $d_p$ это количество $d \bmod (p-1) = e^{-1} \bmod (p-1)$, откуда получаем основное свойство $$ e\cdot d_p \equiv 1 \pmod{p-1}\,. $$ Для небольшого $d_p$ мы можем легко, методом грубой силы, найти количество $e\cdot d_p -1 = k\cdot (p-1)$ для некоторого большого неизвестного целого числа $к$.

Здесь мы можем взять подсказку от Полларда $p-1$ метод факторизации — имеем $2^{k(p-1)} = 1 \pmod{p}$, и поэтому $\gcd(n, 2^{e\cdot d_p - 1} - 1 \bmod n)$ будет $р$ за право $d_p$.

В вашем примере $d_p = 915155$.

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

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