RSA Benny: Stosując metodę RSA dla p=17, q=7, e=17 odkoduj liczbę 10. Nie mogę znaleźć jakiegoś przystępnego schematu.

jc: 61 ?

jc: Gdzieś sobie zapisałem taki opis: A wybiera dwie duże różne liczby pierwsze p, q, znajduje iloczyn n=pq, oblicza w=nww (p−1,q−1) (najmniejsza wspólna wielokrotność). A wymyśla liczbę s taką, że nwd (s,w)=1. Para (s,n) jest kluczem publicznym. A znajduje takie t, że ts=1+kw. W tym celu używa algorytmu Euklidesa. Parę (t,n) pozostawia sobie jako klucz prywatny. B dzieli swoją wiadomość na bloki będące nieujemnymi liczbami całkowitymi mniejszymi od n. Każdy blok x szyfruje obliczając y= x^s mod n. A odszyfrowuje wiadomość y obliczając y^t mod n= x^st mod n= x^kw+1 mod n = x

Benny: Z przykładem można?

jc: p=17, q=7, s=17 n=pq=119 10¹⁷ mod 119 = 61 61¹⁷ mod 119 = 10 Tu akurat klucz szyfrujący = klucz deszyfrujący.

Benny: Czym jest k?

jc: Nie potrzebujesz k. Chodziło o to, aby w | st−1, gdyż wtedy p−1 | st−1 oraz q−1 | st−1. U nas w = 16*6=96 17*17= 1 + 3*96 (no i mamy k=3, ale wartość k do niczego nie jest potrzebna). To nie jest najlepszy przykład, bo dwa klucze są równe.

Benny: p=7, q=17, e=13 zakoduj 32 wyszło mi l=53 Chociaż nie wiem czy dobrze, bo trudziłem się z 32¹³mod 119

jc: Dobrze policzyłeś. W przeciwną stronę podnosisz do 37 potęgi.

Benny: Czemu do 37?

jc: Bo 96 | 37*13 −1. Możesz sprawdzić, że 53³⁷ mod 119 = 32.

Benny: Dzięki