RSA: вычисление закрытого ключа с помощью расширенного алгоритма Евклида

Я старшеклассник, пишу статью по RSA, и я делаю пример с очень маленькими простыми числами. Я понимаю, как работает система, но я не могу вычислить закрытый ключ, используя расширенный алгоритм Евклида.

Вот что я сделал до сих пор:

• Я выбрал простые числа p = 37 и q = 89 и вычислено N = 3293
• Я вычислил (p-1) (q-1) = 3168
• Я выбрал число e так, чтобы e и 3168 были взаимно простыми. Я проверяю это стандартным евклидовым алгоритмом, и он работает очень хорошо. My e = 25

Теперь мне просто нужно вычислить закрытый ключ d, который должен удовлетворять ed = 1 (mod 3168)

. Используя расширенный алгоритм Евклида, чтобы найти d такое, что de + tN = 1, я получаю -887 • 25 + 7 • 3168 = 1. Я выбрасываю 7 и получаю d = -887. Однако попытка расшифровать сообщение не сработает.

Я знаю из своей книги, что d должно быть 2281, и это работает, но я не могу понять, как они пришли к этому числу.

Могут. кто-нибудь поможет? Я пытался решить эту проблему последние 4 часа и везде искал ответ. Я делаю Расширенный алгоритм Евклида вручную, но поскольку результат работает, мои расчеты должны быть верными.

Заранее спасибо,

Мэдс