Obliczanie “d” w algorytmie RSA nie należy do najłatwiejszych jeżeli robimy to ręcznie i do tego nasz poziom matematyki nie jest zbyt wysoki. Co zrobić jeżeli nie chcemy wykorzystać Rozszerzonego Algorytmu Euklidesa aby obliczyć “d” w szyfrowaniu RSA ? Zobacz ten prosty sposób na obliczenie “d” w RSA.
Obliczanie “d” dla szyfrowania RSA – prosty sposób
Przyjmijmy że :
- p = 11
- q = 17
- e = 3
W takim razie
- n = p*q = 11 * 17 = 187
- phi(n) = (p-1) * (q-1) = 10 * 16 = 160
Obliczanie “d” dla szyfrowania RSA – prosty sposób
de = 1 mod 160
3d = 1 mod 160
Teraz szukamy wielokrotności 160 (+1) która jest podzielna przez 3 (e) :
- 160 + 1 = 161 / 3 = 53.66666666666… (nie jest podzielna przez 3)
- 320 + 1 = 321 / 3 = 107 ok ! podzielna przez 3 !
Podstawiamy do wzoru wyżej de = 1 mod 160
107 * 3 = 107 mod 160
321 = 107 mod 160
1 = 107 mod 160
d = 107
Przykład 2 na obliczanie “d” dla RSA
Niech
- p = 47
- q = 61
- n = 2867
- phi(n) = 2760
- e = 7
- d = ?
d = 7^(-1) mod 2760 – to byłoby proste obliczenie na kalkulatorze
Nasz prosty sposób na obliczenie “d” dla szyfrowania RSA
de = 1 mod 2760
7d = 1 mode 2760
Szukamy wielokrotności 2760 +1 podzielnej przez 7
- 2760 +1 = 2761 / 7 = 394.4285 … (nie jest podzielne przez 7)
- 2760 X 2 +1 = 5520 + 1 = 5521 / 7 = 788.7154 … ( nie jest podzielne przez 7 )
- 2760 x 3 +1 = 8280 + 1 = 8281 / 7 = 1183 ! ok !
Podstawiamy do wzoru
7*1183 = 1183 mod 2760
8281d = 1183 mod 2760
1d = 1183 mod 2760
d = 1183