Jestem uczniem szkoły średniej, piszącym artykuł na temat RSA i robię przykład z bardzo małymi liczbami pierwszymi. Rozumiem, jak działa system, ale nie mogę na całe życie obliczyć klucza prywatnego za pomocą rozszerzonego algorytmu euklidesowego.RSA: Kalkulacja klucza prywatnego z rozszerzonym algorytmem Euklidesowym
Oto co było dotąd:
- I wybrany liczb pierwszych p = 37 a q = 89 i oblicza się N = 3293
- I obliczana (p-1) (Q -1) = 3168
- Wybrałem numer e, aby e i 3168 były względnie pierwsze. Sprawdzam to za pomocą standardowego algorytmu euklidesowego, który działa bardzo dobrze. Mój e = 25
Teraz tylko muszę obliczyć d klucza prywatnego, który powinien zadowolić ed = 1 (mod 3168)
Korzystanie Extended algorytm Euklidesa znaleźć d takie, że de + tN = 1 Otrzymuję -887 • 25 + 7 • 3168 = 1. Rzucam 7 i otrzymuję d = -887. Próba odszyfrowania wiadomości nie działa.
Wiem z mojej książki, że d powinno być 2281, i działa, ale nie wiem, jak dotarły do tego numeru.
Czy ktoś może pomóc? Próbowałem rozwiązać ten problem przez ostatnie 4 godziny i wszędzie szukałem odpowiedzi. Robię Rozszerzony Algorytm Euklidesowy ręcznie, ale ponieważ wynik działa, moje obliczenia powinny być prawidłowe.
Dzięki z góry,
Mads
Jak zauważył Ninefingers, po prostu użyj dodatniej reszty. Równoważnie, aby podnieść coś do ujemnej mocy "x" najpierw obliczyć jej odwrotność, a następnie zwiększyć ją do mocy ("-x") ("-x" jest dodatnie, ponieważ "x" jest ujemne). –
Jestem zdezorientowany, jak uzyskać "de + tN = 1" -887 • 25 + 7 • 3168 = 1. Rozumiem e = 25, ale d, t, i N nie mają sensu. Co oznaczają d, t i N? I dlaczego wolno ci wyrzucić 7? Casey –