Задание 12. Рассмотрим схему Диффи—Хеллмана. Схема позволяет выработать общий ключ в условиях прослушиваемого канала связи. Алиса и Боб фиксируют: \((g,p)\) — публичные параметры; \(a\) — секрет Алисы; \(b\) — секрет Боба. Алиса передаёт Бобу \(A=g^a\mod p\), а Боб Алисе — \(B=g^b\mod p\). После этого Алиса может вычислить \(B^a=g^{ab}\mod p\), а Боб — \(A^b=g^{ba}\mod p\). Исследователи перехватили обмен числами: \(g=2, p=13; A=8, B=11\). Какой секретный ключ выработали стороны?

Найдём секрет Боба \(b\) из условия \(2^b\equiv 11\pmod{13}\). Последовательно возводя 2 в степень по модулю 13, получаем: \(2^7=128\equiv 11\pmod{13}\). Значит, можно вычислить общий ключ как \(A^b\bmod p\).

\(8^2=64\equiv 12\pmod{13}\), поэтому \(8^4\equiv 12^2=144\equiv 1\pmod{13}\). Тогда \(8^7=8^4\cdot 8^2\cdot 8\equiv 1\cdot 12\cdot 8=96\equiv 5\pmod{13}\).

Ответ: 5.