Проблема: вы видите, как Майкл и Никита договариваются о секретном ключе, используя обмен ключами Диффи-Хеллмана. Майкл и Никита выбирают $р = 97$ и $г = 5$.
Никита выбирает случайное число n и говорит Майклу, что $g^n \эквив 3\pmod{97}$, и Майкл выбирает случайное число $м$ и говорит Никите
что $g^m ≡ 7 \pmod{97}$. Взломать их код грубой силой: в чем
секретный ключ, о котором договорились Никита и Майкл? Что $n$? Какие
является $м$?
Вот как обмен Диффи-Хеллмана определяется в учебнике:
- Вместе Майкл и Никита выбирают 200-значное целое число p, которое, вероятно,
быть простым, и выбрать число $г$ с $1 < г < р $.
- Никита тайно выбирает целое число $n$.
- Майкл тайно выбирает целое число $м$.
- Никита вычисляет $g^n\pmod{p}$ на своем карманном компьютере и рассказывает
Михаил, получившийся номер по телефону.
- Майкл говорит Никите $g^m \pmod{p}$.
- Затем общий секретный ключ $s\эквив г^{нм}\pmod{p}$
которые могут вычислить и Никита, и Майкл.
Мои мысли/попытки:
Попытка 1. Я пытался найти $n$ путем решения модульного уравнения $5^n\экв 3\pmod{97}.$ Тогда у нас есть $n\эквив\log_53\pmod{97},$ который не является целым числом и, следовательно, не имеет смысла.
Попытка 2. Я пытался найти ключ, используя $g^n$ и $г^м.$ Однако я не вижу способа достичь $г^{нм}$ поскольку $g^ng^m = g^{n+m},$ и мы не можем вычислить $(г^п)^м$ или же $(г^м)^п$ не зная $м$ или же $n,$
для которого из попытки 1 я не могу найти целые числа.
Был бы признателен за помощь! Спасибо
