kodowanie RSA

twilightkid · Post autor: **twilightkid** » 29 gru 2006, o 18:11

oto moje pytanie odnośnie kodowania RSA:

załóżmy że chce zakodowac liczbe 21. liczby pierwsze jakie wyberam to p,q odpowiednio 11 13
w tym przypadku n =pq= 143 funkcja eulera od n fi(n)=120=(p-1)(q-1)
wybieram liczbe pierwsza do fi(n). np 7. liczba odwrotna do 7 modulo 120 to 103.
Funkcja kodujaca K(m)=$\displaystyle{ m^{7}(mod 143)}$
funkcja dekodujaca D(l)=$\displaystyle{ l^{103}(mod 143)}$

K(21)=109
D(109)=$\displaystyle{ 109^{103}(mod 143)}$

moj kalkulator zwracu to 26.. co nie jest rowne 21. nie wiem czy kalkulator źle liczy czy ja cos źle robie..
to raczej ta druga opcja.. tylko nie wiem co. czy da sie takie równanie rozwiazac bez 'liczydła"?

gdzie popełniam błąd?

dzieki za pomoc.
Mateusz

yorgin · Post autor: **yorgin** » 29 gru 2006, o 18:15

Nie znam się na kodowaniu RSA ale tak jak na to patrzę to tak się zastanawiam czy nie powinno być $\displaystyle{ 113\ $zamiast$\ 103?}$
Mogę się mylić

twilightkid · Post autor: **twilightkid** » 29 gru 2006, o 18:23

7*103(mod120)=1 wiec chyba 103 jest odwrotnoscia.. tzn tak mi sie wydaje..hmm

max · Post autor: **max** » 29 gru 2006, o 18:29

$\displaystyle{ 7\cdot 103 = 721 \equiv 1 \ \ (\mod 120\ )}$
więc jest dobrze.

W kalkulatorze masz chyba za mały typ całkowitoliczbowy. Interpreter pythona mówi mi, że jest OK

Do postu poniżej:
nie może - mój błąd - głupia literówka

twilightkid · Post autor: **twilightkid** » 29 gru 2006, o 18:32

tak na marginesie to czemu mod 3 tez moze byc?

max · Post autor: **max** » 29 gru 2006, o 18:35

Już poprawiłem.
W każdym razie dobrze liczysz, wina leży po stronie kalkulatora.

twilightkid · Post autor: **twilightkid** » 29 gru 2006, o 18:42

okej wielkie dzieki MAX czyli takiego rownania nie da sie policzyc jakos recznie.. bez komputera i algorytmu (modular exponentation)?

max · Post autor: **max** » 29 gru 2006, o 19:09

Chodzi Ci o liczenie np $\displaystyle{ 109^{103} \ \ (\mod 143 \ )}$ na kartce? Ja nie umiem...
(Ale interpreter pythona wypluł mi wynik w niezauważalnym ułamku sekundy.)

twilightkid · Post autor: **twilightkid** » 29 gru 2006, o 19:18

i dobry wynik wyszedł?

a sory... nie zauwazylem postu wyzej... tzn nie doczytalem...

moglbys mi wyslac ten skrypt i powiedziec jak go odpalic... w sumie to nie jest strasznie pilne... jak bedziesz mial czas.. i tak mi juz duzo pomogles i czasu oszczędziłeś.. dzieki

max · Post autor: **max** » 29 gru 2006, o 19:42

Wynik wyszedł dobry, python obsługuje dowolnie długie liczby całkowite (policzył dokładnie nawet 32000! )

A wracając jeszcze do mnożenia na kartce to chyba jednak dałoby radę (najwyżej podpierając się kalkulatorem lub mnożeniem i dzieleniem pisemnym (w granicach rozsądku)):
$\displaystyle{ 109^{2} \equiv 12 \ \ (\mod 143 \ )\\
109^{4} \equiv 1 \ \ (\mod 143 \ )\\
109^{100} \equiv 1 \ \ (\mod 143\ )\\
109^{102} \equiv 12 \ \ (\mod 143 \ )\\
109^{103} \equiv 21 \ \ (\mod 143 \ )\\}$

Na kalkulatorze policzyłem tylko: $\displaystyle{ 109^{2} - 143 \lfloor \frac{109^{2}}{143} \rfloor = 12}$
oraz $\displaystyle{ 12 109 - 143\lfloor \frac{12\cdot 109}{143} \rfloor = 21}$ - pierwsze można policzyć pisemnie, drugie nawet w pamięci...

twilightkid · Post autor: **twilightkid** » 29 gru 2006, o 19:42

ok juz mam udalo sie z tym pythonem dziale rzeczywiscie. thx