Algorytmy kryptograficzne | Laboratorium 10

Zaimplementuj prostą wersję kryptosystemu ElGamala, umożliwiającą generowanie klucza, szyfrowanie i deszyfrowanie wiadomości.

Dane: $$ \begin{aligned} p &= 115792089237316195423570985008687907853269984665640564039457584007908834671663,\\ g &= 2,\\ x &= 987654321098765432109876543210987654321,\\ m &= 123456789012345678901234567890,\\ k &= 123456789012345678901234567890123456789. \end{aligned} $$

• Wyznacz klucz publiczny.
• Zaszyfruj wiadomość $m$ jako $(y_1,y_2)$.
• Odszufruj szyfrogram $(y_1,y_2)$.

Zaimplementuj atak na problem logarytmu dyskretnego algorytmem Shanksa (baby-step giant-step).

Dane: $$ p=2147483647,\qquad g=5,\qquad a=723883728. $$

Znajdź $x\in {0,1,\dots,p-1}$ spełniające równość $$ g^x \equiv a \pmod p. $$