Kod RSA

[MPIS_pad]

Publicznym kodem jest para \(\displaystyle{ (r,s)=(1003,5)}\) i tylko my wiemy, że \(\displaystyle{ (r=pq=1003=17 \cdot 59)}\). Od znajomej otrzymaliśmy informację \(\displaystyle{ L}\), której kodem jest \(\displaystyle{ C=102}\). Wyznacz \(\displaystyle{ L}\).

Czy ktoś mógłby pomóc z tym?

[Jarek753]

Najpierw trzeba znaleźć klucz prywatny tzn. taką liczbę \(\displaystyle{ d}\), że \(\displaystyle{ d\cdot s=1 (\mod \varphi(r))}\), gdzie \(\displaystyle{ \varphi(r)}\) jest funkcją Eulera, czyli jest równa ilości liczb względnie pierwszych z \(\displaystyle{ r}\) nie większych od niej. Wiadomo, że jeśli \(\displaystyle{ r=pq}\) gdzie \(\displaystyle{ p,q}\) to liczby pierwsze, to \(\displaystyle{ \varphi(r)=(p-1)(q-1)}\). Do znalezienia \(\displaystyle{ d}\) można wykorzystać algorytm Euklidesa (szukanie liczby odwrotnej do danej liczby w arytmetyce modulo). Po znalezieniu \(\displaystyle{ d}\) należy rozwiązać kongruencję:
\(\displaystyle{ C^d=x (\mod r)}\).
\(\displaystyle{ x}\) jest szukaną wiadomością \(\displaystyle{ L}\).