Завершение шифрования RSA

Будучи новичком в криптологии, я пытаюсь понять, как выполнить шифрование RSA вручную. Пока я могу только следовать формуле, прежде чем сильно запутаться.

Я хочу зашифровать значение "123"

Сначала я должен выбрать 2 простых числа. Я выбираю: $$p = 101\ д = 103$$

Далее я вычисляю: $$n = p\cdot q = 10403$$.

После этого я вычисляю: $$\varphi(n) = (p-1)\cdot(q-1) = 10200$$

Теперь я хочу выбрать публичный показатель, и я выбираю для этого 3.

Я считаю, что формула для использования: $$d = e^{â1}\bmod\varphi(n)$$

Я не понимаю, как подключить эту формулу, и не знаю, как зашифровать «123», используя эту формулу. Кроме того, я не знаю, как найти показатель степени расшифровки.

Любая помощь приветствуется!

Фгрие, по сути, дал ответ в комментарии, я попытаюсь немного уточнить в форме ответа.

Вы можете использовать расширенный алгоритм Евклида, чтобы найти d из e, но обратите внимание, что выбранное вами e не будет работать. Поскольку e не взаимно просто с $\varphi(n)$ Вам нужно выбрать другой. Для эффективности нам обычно нравится выбирать маленькую букву e с несколькими установленными битами, обычно в форме $2^k+1$ поскольку 3 не работает, вы можете попробовать другие. https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm Вот онлайн-калькулятор: https://planetcalc.com/3298/

Это не только даст вам gcd (который должен быть равен 1), но также даст вам a, b, так что: $a*e + b*\varphi(n) = 1$ что по сути означает $a*e = 1 мод \varphi(n)$ что мы и хотели.

Затем вы шифруете, вычисляя $c = m^e\space mod(n)$ и расшифровать с помощью $ м = c ^ d \ пространство мод (п) $ Оба сделаны через https://en.wikipedia.org/wiki/Modular_exponentiation