Algorytmy kryptograficzne | Laboratorium 9

Zaimplementuj prostą wersję kryptosystemu RSA umożliwiającą generowanie klucza o zadanej długości oraz szyfrowanie i deszyfrowanie wiadomości.

Wiadomość $m$ została wysłana do trzech odbiorców używających kryptosystemu RSA, których klucze publiczne są postaci $$ (n_i, b), \qquad i = 1, 2, 3, $$ przy czym $$ \begin{aligned} n_1 &= 856205355226618825334201920757106189619224699081629760978379,\\ n_2 &= 1328989703057549513436915621825085287854653749432700959218047,\\ n_3 &= 454354335307926896909207147444504297415186755348139088337797 \end{aligned} $$ oraz $b=3$. Szyfrogramy tej wiadomości są następujące: $$ \begin{aligned} \hat m_1 &= 740425793465388555119503964648476369739800418029540350718050,\\ \hat m_2 &= 379024675447467155328545229780563222680646766208695846228599,\\ \hat m_3 &= 411198195497414070662759224293482345584589805255958400512866. \end{aligned} $$ Odszyfruj wiadomość $m$.

Kluczem publicznym RSA jest para $$ \begin{aligned} n &= 1313515961823594815575154913315852207747386471941686554907750978089,\\ b &= 33952409280164118828863932489364912227773802472046082146931865987. \end{aligned} $$ Znamy również klucz prywatny $$ a = 916068662416111846290622300265918825790030273088625292735182448923. $$ Znajdź rozkład $n$ na czynniki pierwsze.

Przy generowaniu klucza do systemu RSA Bob popełnił błąd i wybrał liczby pierwsze $p$ i $q$ zbyt bliskie sobie. Jego kluczem publicznym jest $$ \begin{align*} n = 21065697565526050283709340617359483226129252608263375868118038621,\\ b = 16293777489894186846358032589196527500195521068667278107937310471. \end{align*} $$ Znajdź klucz prywatny Boba.