Obliczanie “d” w algorytmie RSA – prosty sposób

Obliczanie "d" dla szyfrowania RSA - Łatwy sposób

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

Author: Seweryn

Mam na imię Seweryn i komputerami oraz informatyką interesuje się od roku 1996. Ukończyłem Birkbeck University of London na kierunku Information Technology profil Web Design. Moją kolejna wielką pasją jest gotowanie. Lubię grać w StarCrafta (od 1999 roku) , siłownię oraz moje koty. Man nadzieję, że przydadzą Ci się informacje zawarte na mojej stronie. W razie pytań pisz do mnie. Postaram się odpowiedzieć jak szybko mogę.

Leave a Reply