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

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

$(35,3)$ Źle

$(35,5)$ Dobrze

$(35,7)$ Źle

żaden z pozostałych Źle

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

$3$ Źle

$5$ Źle

$10$ Dobrze

$11$ Źle

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

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

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

znany jest algorytm wielomianowy, który mając na wejściu $n$ i $e$ wylicza $d$ takie, że $ed{\equiv }_{\phi (n)}1$ Źle

znany jest algorytm wielomianowy, który mając na wejściu $n,\phi (n)$ i $e$ liczy $d$ spełniające $ed{\equiv }_{\phi (n)}1$ Dobrze

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

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

$n$ jest pierwsza z prawdopodobieństwem $\frac{1}{2^k}$ Źle

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

żadna z pozostałych Dobrze

Liczba Carmichaela:

przechodzi test Fermata dla dowolnie wylosowanej podstawy Dobrze

jest iloczynem przynajmniej trzech liczb pierwszych Dobrze

mogą być parzyste Źle

mogą być podzielne przez $9$ Źle

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

$b^{n-1}{\equiv }_{n}1$ Dobrze

istnieje $0⩽r<s$ takie, że $b^{2^{r}t}{\equiv }_n-1$ Źle

$n$ jest pseudopierwsza przy podstawie $b$ Dobrze

jeśli $b^{2^{r}t}{\equiv }_{n}1$ dla pewnego $r>0$ to $b^{2^{r-1}t}{\equiv }_n-1$ Źle

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

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

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

$n$ jest pierwsza, o ile prawdziwa jest Uogólniona Hipoteza Riemanna Źle

żadna z pozostałych Źle