Спрашивается, как в RSA найти $е$ данный $д$ и $N$. Я проигнорирую требование вопроса о том, что $е$ взаимно прост с $N$, что весьма необычно и не имеет математического значения. я тоже предположу $p\neq$, так как это необходимо для изложенного $\varphi(N)=(p-1)\cdot(q-1)$ держать.
С определением вопроса RSA метод поиска $е$ идет
- Фактор $N$ найти $р$ и $q$
- Вычислить $\varphi=(p-1)\cdot(q-1)$
- Вычислить $е$ зная $e\cdotd\bmod\varphi=1$ и $1<e<\varphi$. Что $е$ определяется однозначно, а модульная обратная $д$ в мультипликативная группа целых чисел по модулю $\varphi$. Для небольших чисел рабочий метод — метод проб и ошибок небольших нечетных чисел. $е>1$. Более конструктивным методом является (половина)-расширенный алгоритм Евклида, который вычисляет $e=d^{-1}\bmod \varphi$ напрямую. Для практического алгоритма, который использует только неотрицательные целые числа:
- $a\getsd\bmod\varphi$ , $b\получает\varphi$ , $х\получает0$ и $y\gets1$
Примечание: $a\cdot x+b\cdot y=\varphi$ будет продолжать держать
- если $а=1$, затем вывод "желаемый обратный $е$ из $д$ по модулю $\varphi$ является $у$" и остановись
- Если $а=0$, затем вывод "желаемый обратный $е$ из $д$ по модулю $\varphi$ не существует" и остановись
- $r\gets\lfloor b/a\rfloor$
- $b\получает b-a\cdot r$ и $x\получает x+r\cdot y$
- если $б=1$, затем вывод "желаемый обратный $е$ из $д$ по модулю $\varphi$ является $\varphi-x$" и остановись
- Если $б=0$, затем вывод "желаемый обратный $е$ из $д$ по модулю $\varphi$ не существует" и остановись
- $r\gets\lfloor a/b\rfloor$
- $a\получает a-b\cdot r$ и $y\получает y+r\cdot x$
- Продолжить на 2
Этот же метод обычно используется для вычисления $д$ от $е$, поскольку $д$ и $е$ симметричны в $e\cdotd\bmod\varphi=1$. Однако это не так $д=11$ было вычислено в вопросе; по какой-то странной причине вопрос требует $е<\varphi(N)$ но нет $d<\varphi(N)$, или более привычный $d<N$ или же $d<\operatorname{lcm}(p-1,q-1)$.
Серьезная проблема с этим подходом к RSA на практике (таким образом, очень большая $N$, по крайней мере сотни десятичных цифр): Это не сработает, потому что $N$ будет настолько большим, что его нельзя будет разложить на множители, поэтому $\varphi$ нельзя вычислить таким образом.
Также условие вопроса $e\cdotd\bmod\varphi(N)=1$ является достаточным, но не необходимым условием для учебника RSA-шифрования с использованием $(е,N)$ быть отменено расшифровкой RSA с использованием $(д,Н)$, наоборот. Необходимое условие $e\cdotd\bmod\лямбда(N)=1$, куда $\lambda(N)=\operatorname{lcm}(p-1,q-1)$. Это условие часто используется на практике: это разрешено ПККС#1, и по поручению ФИПС 186-4. Искусственно маленький пример: $N=341$, $е=7$, $д=13$ отлично работает для учебника по шифрованию/дешифрованию RSA, но $e\cdotd\bmod\varphi(N)=1$ не выполняется (в этом примере $р=11$, $q=31$, $\varphi(N)=300$, $\лямбда(N)=30$ ).
Однако, как это практикуется в RSA, $е$ мала, часто настолько мала, что $е$ можно найти перечислением. Таким образом, метод может быть:
- вычислять $c\gets2^d\bmod N$
- вычислять $c_2\получает c^2\bmod N$
- установлен $e\gets1$
- повторение
- установлен $е\получает е+2$
- установлен $c\gets c\cdot c_2\bmod N$; уведомление $c=2^{d\cdot e}\bmod N$
- если $с=2$
- за $м$ первая сотня нечетных простых чисел (примечание: для малых $N$, мы хотим остановиться, как только $м^2>N$ )
- если $m^{e\cdot d}\bmod N\ne m$, продолжить в повторение выше
- вывод $е$ и остановись.
Почти наверняка, если $е$ выводится, это действительно в том смысле, что шифрование учебника RSA с использованием $(е,N)$ отменяется расшифровкой RSA с использованием $(д,Н)$, и (эквивалентно) $e\cdotd\bmod\лямбда(N)=1$. это не совсем точно $e\cdotd\bmod\varphi(N)=1$, но зная $e\cdotd$ и $N$ можно учитывать $N$ (с использованием это алгоритм), а затем вычислить в $е$ с $e\cdotd\bmod\varphi(N)=1$ и $1<e<\varphi(N)$, если по какой-то причине это желательно.
Дополнение: вышеизложенное далеко не оптимально. Когда $\дельта=\ln(e)/\ln(N)$ находится ниже определенного порога, порядка $0.292$, есть способы факторизовать $N$ (и, таким образом, решить задачу первым обсуждаемым методом). По сути, мы обмениваемся $д$ и $е$ Дэн Боне и Гленн Дерфи Криптоанализ RSA с закрытым ключом $д$ Меньше, чем $N^{0,292}$, в материалы Eurocrypt 1999. Видеть там для большего.
