Matemagik
Konkurs nr 10
Data konkursu: 2013-04-02
Liczba uczestników: 13
Klucz: klucz dostępny po zalogowaniu
Zadanie
Szyfr RSA
Zadanie
Zaszyfruj wiadomość (liczbę naturalną $x$) za pomocą RSA.
Procedura szyfrowania RSA
1. Wybieram dwie duże liczby pierwsze $p$ i $q$
2. Obliczamy $n = p \cdot q$
3. Wybieramy liczbę $e$ względnie perwszą z $(p-1)\cdot(q-1)$
4. Para liczb $(n, e)$ jest kluczem publicznym.
5. Liczbę $x$ szyfrujemy za pmocą wzoru: $S(x) = x^e \mod n $, gdzie $ mod $ to reszta z dzielenia liczby $x^e$ przez liczbę $n$.
6. Klucz prywatny: wyznaczamy liczbę całkowitą $d$, $0 \lt d \lt (p-1)(q-1)$ taką, że $e \cdot d \mod (p-1)(q-1) = 1$
Liczba $d$ jest odwrotnością liczby $e$ modulo $\phi(n)$.
7. Para $(n, d)$ to klucz prywatny pozwalający odszyfrować zakodowaną wiadomość.
8. Funkcję deszyfrującą określamy wzorem: $D(x) = x^d \mod n$, gdzie $x$ to zaszyfrowana wiadomość.
Za pomocą podanej pary liczb $n$ i $e$ zaszyfruj wiadomość: liczbę naturalną $x$.
Każdy test to para liczb $n$ i $e$ oraz liczba $x \lt n$, którą należy zaszyfrować za pomocą klucza $(n,e)$.
Przykład
1. Wybieram dwie liczby lierwsze $p$ i $q$. (np.: $3$ i $11$)
2. $n = 3 \cdot 11 = 33$
3. Wybieram liczbę $e$ względnie pierwszą z $(3-1)\cdot(11-1) = 20$. Na przykład $e = 9$
4. Klucz publiczny to $(33, 9)$
Szyfrujemy przykładowe liczby kluczem $(33,9)$:
liczba 13: $13^9 \mod 33 = 10604499373 \mod 33 = 28$
liczba 18: $18^9 \mod 33 = 30$
zaszyfrowana liczba $13$ to $28$
zaszyfrowana liczba $18$ to $30$
Przykładowe testy
$(33, 9), 13$ (wynik: $28$)
$(33, 9), 18$ (wynik: $30$)
$(65, 11), 4$ (wynik: $49$)
$(65, 11), 38$ (wynik: $12$)
Testy:
$(35, 5), 11$
$(35, 5), 30$
$(35, 7), 33$
$(65, 23), 37$
$(85, 15), 7$
$(77, 41), 38$
$(143, 61), 46$
$(221, 125), 75$
$(3599, 1001), 10$
$(21511043, 11111), 2013$