Регистрация Войти
Рейтинг:0
avatar Crypto

RSA: получить закрытый ключ, используя плохо сгенерированный открытый ключ

флаг us
Uri

Мне нужно решить следующую задачу:

Что у меня есть:

  • $n$, 2048-битное число

Что мне нужно найти:

  • $р$ и $q$ такой, что $n = p\cdotq$.

Что я знаю:

  • С $p_1$ первая половина $р$ и $p_2$ вторая половина, то же самое с $q_1$ и $q_2$: $$p_1 = q_2\text{ и }\ p_2 = q_1$$

  • Поэтому найти $р$ вы также можете найти $q$ наоборот.

  • Размер обоих $р$ и $q$ составляет 1024 бита.

  • (очевидно) все, что предполагается в RSA, например $р$ и $q$ являются различными простыми числами.

Я пытался решить эту проблему в течение 6 часов, и я безнадежный, спасибо за любую помощь!

83
0 + 0
fgrieu avatar
флаг ng
fgrieu
Совет для начала: предположим, что «половинки» — это двоичное представление $p$ и $q$. Найдите количество битов в $p_1$ и $p_2$, обратите внимание, что $b$.Переведите _â$p_1$ первую половину $p$ и $p_2$ вторую половину_ в одно уравнение, содержащее $b$, $p$, $p_1$, $p_2$. То же самое с $q$. Что такое $n$ как функция от $b$, $p_1$, $p_2$? Теперь попробуйте найти $p_1$ и $p_2$.
1
Ответить
poncho avatar
флаг my
poncho
Дальнейшая подсказка (при условии, что она вам нужна): чтобы начать решение для $p_1, p_2$, сначала попробуйте восстановить $p_1 \times p_2$. Получив это, попробуйте восстановить $p_1 + p_2$.
1
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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