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

RSA: общий множитель между M и n

флаг cn
Marth83

Допустим, у нас есть классическое шифрование RSA с n = p*q. Я видел в Интернете, что для данного C RSA может быть слабым, если мы знаем, что открытый текст M и n имеют общий множитель. Однако мне не удалось найти доказательств этого.

Мы знаем это $M=C^e \пробел по модулю\;n$, где e является открытым ключом. Я пытался сказать, что $М = а + к*п$, где a и k — положительные целые числа, и переделать алгоритм. Следовательно :

$C = M^e\;mod\;n = (a + k*n)^e\;mod\;n = a^e\;mod\;n$

И

$M = C^d\;mod\;n = a^{d*e}\;mod\;n$

Однако это звучит бесполезно, так как мы не знаем a (даже при грубой силе нам пришлось бы вычислять много значений, если бы $n$ большой) и $д$, очевидно, поскольку это закрытый ключ. Кто-нибудь может помочь мне в этом?

83
0 + 0
Рейтинг:3
poncho avatar Crypto
флаг my
poncho

Я видел в Интернете, что для данного C RSA может быть слабым, если мы знаем, что открытый текст M и n имеют общий множитель. Однако мне не удалось найти доказательств этого.

Это довольно просто; мы знаем обоих $С$ и $n$; если $ млн $ имеет общий множитель с $n$, так же $С$. Итак, мы можем просто вычислить $\НОД(С, п)$. Поскольку мы знаем, что $ млн $ и $n$ имеют общий множитель, то это не 1; мы предполагаем, что $С < п$, так это не $n$. Следовательно, это должен быть надлежащий фактор $n$; если $n$ является произведением двух простых чисел, тогда это будет одно из них, и поэтому два простых множителя $n$ тогда $\НОД(С, п)$ и $n / \gcd(C, n)$.

Когда у нас есть факторизация $n$ тогда (при условии, что мы знаем значение $е$), вычисления $д$ является прямолинейным.

0 + 0
poncho avatar
флаг my
poncho
@Marth83: лучше?
0
Ответить
Marth83 avatar
флаг cn
Marth83
Да, это то, что мне было интересно, спасибо!
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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