Matematyka dyskretna 2/Test 7: Zastosowanie teorii liczb w kryptografii

From Studia Informatyczne

Dla małych wartości użytych liczb pierwszych łatwo można złamać RSA. Jeśli \displaystyle (35,5) jest kluczem publicznym RSA to kluczem dekodującym jest:

\displaystyle (35,3)

\displaystyle (35,5)

\displaystyle (35,7)

żaden z pozostałych


Załóżmy, że \displaystyle (35,11) jest naszym kluczem dekodującym w kryptosystemie RSA. Otrzymaliśmy jednostkę szyfrogramu o wartości \displaystyle 5. Wartość zdekodowanej jednostki to:

\displaystyle 3

\displaystyle 5

\displaystyle 10

\displaystyle 11


Niech \displaystyle n=pq dla pewnych liczb pierwszych \displaystyle p \neq q oraz niech \displaystyle n\perp e dla pewnego \displaystyle e. Wtedy:

znany jest algorytm wielomianowy, który mając na wejściu \displaystyle p i \displaystyle q liczy \displaystyle \varphi(n)

znany jest algorytm wielomianowy, który mając na wejściu \displaystyle n i \displaystyle \varphi(n) liczy \displaystyle p i \displaystyle q

znany jest algorytm wielomianowy, który mając na wejściu \displaystyle n i \displaystyle e wylicza \displaystyle d takie, że \displaystyle ed\equiv_{\varphi(n)}1

znany jest algorytm wielomianowy, który mając na wejściu \displaystyle n, \varphi(n) i \displaystyle e liczy \displaystyle d spełniające \displaystyle ed\equiv_{\varphi(n)}1


Jeśli liczba \displaystyle n przeszła \displaystyle k testów Fermata, to:

\displaystyle n jest złożona z prawdopodobieństwem \displaystyle \frac{1}{2^k}

\displaystyle n jest pierwsza z prawdopodobieństwem \displaystyle \frac{1}{2^k}

\displaystyle n jest liczbą Carmichaela z prawdopodobieństwem \displaystyle \frac{1}{2^k}

żadna z pozostałych


Liczba Carmichaela:

przechodzi test Fermata dla dowolnie wylosowanej podstawy

jest iloczynem przynajmniej trzech liczb pierwszych

mogą być parzyste

mogą być podzielne przez \displaystyle 9


Niech \displaystyle t będzie liczbą nieparzystą oraz \displaystyle n=2^st, gdzie \displaystyle s\geq 1. Jeśli \displaystyle n jest silnie pseudopierwsza przy podstawie \displaystyle b to:

\displaystyle b^{n-1}\equiv_n1

istnieje \displaystyle 0\leqslant r<s takie, że \displaystyle b^{2^rt}\equiv_n-1

\displaystyle n jest pseudopierwsza przy podstawie \displaystyle b

jeśli \displaystyle b^{2^rt}\equiv_n1 dla pewnego \displaystyle r>0 to \displaystyle b^{2^{r-1}t}\equiv_n-1


Jeśli liczba \displaystyle n przeszła \displaystyle k testów Millera-Rabina to:

\displaystyle n jest złożona z prawdopodobieństwem co najwyżej \displaystyle \frac{1}{4^k}

\displaystyle n jest pierwsza z prawdopodobieństwem co najwyżej \displaystyle \frac{1}{4^k}

\displaystyle n jest pierwsza, o ile prawdziwa jest Uogólniona Hipoteza Riemanna

żadna z pozostałych