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

RSA: почему $( e^{-1} ~\text{mod}~ n \cdot \varphi(n)) ~\text{mod}~ \varphi(n) = e^{-1} ~\text{ mod}~ \varphi(n)$ выполняется для конкретной настройки RSA

флаг in
Cryptomathician

Позволять $р,к$ являются простыми числами и $n = pq$ как и во всех настройках RSA, и теперь используйте случайный $е$ который обладает следующими свойствами

  • $gcd(e, \phi(n)) \neq 1$
  • $(e^{-1} ~\text{mod} ~\phi(n))^{4}\cdot3 < n$
  • $e^{-1} ~\text{mod} ~\phi(n) < \sqrt[3]{n}$ (целый квадратный корень), где $\sqrt[3]{n} \in \mathbb{Z}$

куда $\фи$ является тотиентной функцией Эйлера. Этот $е$ используется как открытый показатель для открытого ключа и $д$ является закрытым показателем для закрытого ключа.

Помните, что $\фи(п) | ред - 1$, как $ed = 1 + k \cdot \phi(n)$ держится за $k \in \mathbb{Z}$. Вопрос в том, почему он так считает $$(e^{-1} ~\text{mod}~ n \cdot \phi(n)) ~\text{mod}~ \ \phi(n) = e^{-1} ~\text{mod }~ \phi(n)\text{?}$$ Может ли кто-нибудь объяснить это математически или привести доказательство, почему это так?

Связанный вопрос относительно нескольких $\фи(п)$ спрашивается в этом вопрос. К сожалению, я не понимаю отношения между кратным $\фи(п)$, $gcd$ и почему это уравнение $ed = 1 ~\text{mod}~ k \cdot \phi(n)$ держит $ed = 1 ~\text{mod}~ \phi(n)$ за $k \in \mathbb{Z}$.

Кроме того, было бы неплохо прочитать доказательство для соответствующего вопроса относительно кратности $\фи(п)$, если кто-то знает, почему это так.

85
0 + 0
poncho avatar
флаг my
poncho
$(e^{-1} \bmod \phi(n))^4 \cdot 3
0
Ответить
Cryptomathician avatar
флаг in
Cryptomathician
Да, он должен быть уязвимым. @пончо
0
Ответить
Рейтинг:1
poncho avatar Crypto
флаг my
poncho

Вопрос в том, почему он так считает $(e^{â1} \bmod n \cdot \phi(n)) \bmod \phi(n)=e%{â1} \bmod \phi(n)$?

На самом деле, у нас есть более общее тождество $(A \bmod BC) \bmod C \equiv A \bmod C$, для любых целых чисел $А, Б, С$. В вашем конкретном случае имеем $A = e^{-1} \bmod \phi(n)$, $В = п$, и $C = \фи(n)$

Это более общее тождество можно легко увидеть из двух фактов:

$X \bmod Y = X + k \cdot Y$ для некоторого целого числа $к$ (что может быть отрицательным)

$X \bmod Y = Z \bmod Y$ если и только если $X - Z = k'\cdot Y$ для некоторого целого числа $к'$.

Из первого факта мы видим, что $A \bmod BC = A + kBC$ (для некоторого целого $к$ - нам все равно, что это за целое число)

Из второго факта мы видим, что $(A + kBC) \bmod C = A \bmod C$ держится, если у нас есть $A + kBC - A = k'C$ для некоторого целого числа $к'$; сразу видно, что это верно для целого числа $к'=кБ$, значит, это верно.

Поскольку общая идентичность сохраняется во всех случаях, она также сохраняется и в вашем конкретном случае.

0 + 0
Cryptomathician avatar
флаг in
Cryptomathician
Спасибо. Мне интересно, где gcd играет роль, как это упоминается в «правильном» ответе на соответствующий вопрос в обмене стеками mathoverflow. Должны ли e и n быть взаимно простыми ($gcd(e,n)$), чтобы сохранить это тождество?
0
Ответить
poncho avatar
флаг my
poncho
@Cryptomatician: ну, если $e$ и $n$ не взаимно просты, то $e^{-1} \bmod (n \cdot \phi(n))$ не существует.
1
Ответить
Cryptomathician avatar
флаг in
Cryptomathician
хорошо понял. Спасибо за подробное объяснение.
0
Ответить
Cryptomathician avatar
флаг in
Cryptomathician
это другой вопрос, когда я хочу знать, когда выполняется $y = x^{-1} ~(\text{mod}~ k \cdot \phi(n))$, так что также $xy \equiv 1 ~( \text{mod}~ \phi(n))$ выполняется для некоторого $k \in \mathbb{Z}$ ? Я тоже пытался выяснить, когда это происходит. @пончо
0
Ответить
poncho avatar
флаг my
poncho
@Cryptomatician: на самом деле это справедливо для всех $k \in \mathbb{Z}$; такая же логика: $y = x^{-1} \pmod{k \phi(n)}$ означает, что существует $k' \in \mathbb{Z}$ с $yx = 1 + k'( k \фи(п))$; отсюда следует, что существует $k''$ с $yx = 1 + k'' \phi(n)$, т. е. $yz \equiv 1 \pmod{\phi(n)}$
1
Ответить
Cryptomathician avatar
флаг in
Cryptomathician
Спасибо. Я сделал тот же расчет, что и вы, и хотел убедиться, что не ошибся. Спасибо! Вероятно, последнее уравнение должно быть $yx \equiv 1 ~(\text{mod}~ \phi(n))$ вместо $yz \equiv 1 ~(\text{mod}~ \phi(n))$, верно?
0
Ответить
poncho avatar
флаг my
poncho
@Cryptomatician: верно, $yz$ была опечаткой...
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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