Rozważmy system kryptograficzny RSA z modułem \(\displaystyle{ n = 71 * 103}\) i wykładnikiem publicznym \(\displaystyle{ e = 19}\). Oblicz, ile komunikatów \(\displaystyle{ M \in \{0, ... , n-1\}}\) jest punktami stałymi szyfrowania, tzn. spełnia warunek \(\displaystyle{ S(M)=M}\)
Proszę, w miarę możliwości, krok po kroku ;]
Punkty stałe w RSA
-
Heniek1991
- Użytkownik
- Posty: 111
- Rejestracja: 14 paź 2010, o 16:58
- Płeć: Mężczyzna
- Lokalizacja: Lublin / Warszawa
- Podziękował: 1 raz
- Pomógł: 1 raz
Punkty stałe w RSA
Szukamy liczb postaci \(\displaystyle{ M^e \equiv M ( \mod p \cdot q)}\) Z chińskiego tw. o resztach, ta kongruencja jest równoważna:
\(\displaystyle{ \begin{cases} M^e \equiv M ( \mod p)\\ M^e \equiv M ( \mod q)\end{cases}}\)
Jednym rozwiązaniem jest \(\displaystyle{ M=0}\), więc poza tym mamy:
\(\displaystyle{ \begin{cases} M^{e-1} \equiv 1 ( \mod p)\\ M^{e-1} \equiv 1 ( \mod q)\end{cases}}\)
Tylko, że co dalej zrobić to nie wiem.
Znalazłem jakiś materiał na ten temat, ale prosiłbym o wytłumaczenie, bo nie wiem dlaczego tak należy postąpić, jak w tym linku napisane.
\(\displaystyle{ \begin{cases} M^e \equiv M ( \mod p)\\ M^e \equiv M ( \mod q)\end{cases}}\)
Jednym rozwiązaniem jest \(\displaystyle{ M=0}\), więc poza tym mamy:
\(\displaystyle{ \begin{cases} M^{e-1} \equiv 1 ( \mod p)\\ M^{e-1} \equiv 1 ( \mod q)\end{cases}}\)
Tylko, że co dalej zrobić to nie wiem.
Znalazłem jakiś materiał na ten temat, ale prosiłbym o wytłumaczenie, bo nie wiem dlaczego tak należy postąpić, jak w tym linku napisane.
-
MichalKulis
- Użytkownik
- Posty: 47
- Rejestracja: 19 sty 2011, o 08:15
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
-
Xitami
Punkty stałe w RSA
0, 1, 355, 356, 1704, ..., razem 21 sztuk
\(\displaystyle{ \frac{21}{n}=0,00287...}\)
\(\displaystyle{ \frac{21}{n}=0,00287...}\)
-
Rodis
- Użytkownik
- Posty: 23
- Rejestracja: 25 lut 2009, o 21:22
- Płeć: Mężczyzna
- Podziękował: 1 raz
- Pomógł: 1 raz
Punkty stałe w RSA
W tamtym pdfie jest przedstawione mniej więcej takie rozumowanie:
Jeśli \(\displaystyle{ M}\) jest punktem stałym przekształcenia \(\displaystyle{ S(M)=M^e \mod n}\), to znaczy, że \(\displaystyle{ M^e \mod n = M}\), tj. \(\displaystyle{ M^e-M \mod n = 0}\), tj. \(\displaystyle{ (n=pq)|M(M^{e-1}-1)}\), z czego mamy, że \(\displaystyle{ p|M \wedge q|M^{e-1}-1}\) lub \(\displaystyle{ q|M \wedge q|M^{e-1}-1}\) lub \(\displaystyle{ pq | M^{e-1}-1}\), co można skrótowo zapisać \(\displaystyle{ (p|M \vee p|M^{e-1}-1) \wedge (q|M \vee q|M^{e-1}-1)}\). Zauważmy, że \(\displaystyle{ 0\leqslant M < pq}\), a tutaj patrzymy na podzielność przez \(\displaystyle{ p}\) i \(\displaystyle{ q}\), więc niech \(\displaystyle{ b = M \mod p}\), \(\displaystyle{ c = M \mod q}\) i wtedy mamy \(\displaystyle{ p|b^{e-1}-1}\) itd. Stąd, jeśli znajdziemy jakieś b i c spełniające nasze "mniejsze" równania (dokładniej dalej), to wtedy mając układ kongruencji
\(\displaystyle{ M \equiv b \pmod p}\)
\(\displaystyle{ M \equiv c \pmod q}\)
z Chińskiego tw. o resztach mamy jednoznacznie wyznaczone \(\displaystyle{ M \in \{0, \ldots n-1\}}\).
Teraz mamy do znalezienia \(\displaystyle{ b}\) takie, że \(\displaystyle{ b \in \{0, \ldots p-1\} \wedge (p|b \vee p|b^{e-1} -1)}\). I analogicznie dla (\(\displaystyle{ q}\) i \(\displaystyle{ c}\)).
Pierwszy przypadek to po prostu \(\displaystyle{ b=0}\). Od tej pory zakładamy \(\displaystyle{ b\neq 0}\) (i na końcu dodamy 1 do wyniku). Mamy w takim razie \(\displaystyle{ 0<b<p}\) i \(\displaystyle{ p|b^{e-1}-1}\), tj. \(\displaystyle{ b^{e-1} \equiv 1 \pmod p}\). Dalej wykorzystany jest taki pomysł. Niech \(\displaystyle{ 0<v<p}\) będzie taką liczbą, że \(\displaystyle{ \{v^0=1, v^1, v^2, \ldots, v^{p-2}\} = \{1, \ldots, p-1\}}\), tj. \(\displaystyle{ v}\) do różnych potęg da różne liczby i wszystkie w ten sposób dostaniemy. Taka liczba istnieje, bo jest to generator grupy cyklicznej \(\displaystyle{ \mathbb{Z}_p^{*}}\) z działaniem mnożenia.
Niech \(\displaystyle{ b = v^x}\). Teraz \(\displaystyle{ \left(v^x\right)^{e-1} \equiv 1 \pmod p}\) i szukamy \(\displaystyle{ x}\) (a tak właściwie, to liczby \(\displaystyle{ x}\)'ów spełniających to równanie). Ponieważ \(\displaystyle{ p-1}\) jest najmniejszą niezerową potęgą, do której trzeba podnieść coś, aby otrzymać jedynkę, to mamy \(\displaystyle{ p-1|x(e-1)}\), tj \(\displaystyle{ x(e-1) \equiv 0 \pmod {p-1} (*)}\). Jeśli \(\displaystyle{ d = NWD(e-1, p-1)}\), to możemy podzielić stronami (trzema stronami) przez d: \(\displaystyle{ x\frac{e-1}{d} \equiv \frac{0}{d} \pmod{\frac{p-1}{d}}}\). Teraz możemy znaleźć \(\displaystyle{ x'}\) będącą odwrotnością \(\displaystyle{ \frac{e-1}{d}}\) modulo \(\displaystyle{ \frac{p-1}{d}}\) i mamy \(\displaystyle{ x' \cdot x \frac{e-1}{d} \equiv 0 \cdot x' \pmod {\frac{p-1}{d}}}\), czyli \(\displaystyle{ x \equiv 0 \pmod {\frac{p-1}{d}}}\), stąd rozwiązaniami \(\displaystyle{ (*)}\) jest \(\displaystyle{ 0, \frac{p-1}{d}, 2\frac{p-1}{d}, \ldots}\), łącznie \(\displaystyle{ d}\) rozwiązań.
Dodając nasze "zapomniane" zero mamy \(\displaystyle{ NWD(e-1, p-1) + 1}\) rozwiązań na \(\displaystyle{ b}\) i analogicznie \(\displaystyle{ NWD(e-1, q-1) + 1}\) rozwiązań na \(\displaystyle{ c}\). Każda para rozwiązań \(\displaystyle{ (b, c)}\) da z Chtwor'a inne \(\displaystyle{ M}\), więc mamy łącznie \(\displaystyle{ (NWD(e-1, p-1) + 1)(NWD(e-1, q-1) + 1) = (NWD(18, 70) + 1)(NWD(18, 102) + 1) = (2+1)(6+1) = 21}\) punktów stałych.
Ufff...
Jeśli \(\displaystyle{ M}\) jest punktem stałym przekształcenia \(\displaystyle{ S(M)=M^e \mod n}\), to znaczy, że \(\displaystyle{ M^e \mod n = M}\), tj. \(\displaystyle{ M^e-M \mod n = 0}\), tj. \(\displaystyle{ (n=pq)|M(M^{e-1}-1)}\), z czego mamy, że \(\displaystyle{ p|M \wedge q|M^{e-1}-1}\) lub \(\displaystyle{ q|M \wedge q|M^{e-1}-1}\) lub \(\displaystyle{ pq | M^{e-1}-1}\), co można skrótowo zapisać \(\displaystyle{ (p|M \vee p|M^{e-1}-1) \wedge (q|M \vee q|M^{e-1}-1)}\). Zauważmy, że \(\displaystyle{ 0\leqslant M < pq}\), a tutaj patrzymy na podzielność przez \(\displaystyle{ p}\) i \(\displaystyle{ q}\), więc niech \(\displaystyle{ b = M \mod p}\), \(\displaystyle{ c = M \mod q}\) i wtedy mamy \(\displaystyle{ p|b^{e-1}-1}\) itd. Stąd, jeśli znajdziemy jakieś b i c spełniające nasze "mniejsze" równania (dokładniej dalej), to wtedy mając układ kongruencji
\(\displaystyle{ M \equiv b \pmod p}\)
\(\displaystyle{ M \equiv c \pmod q}\)
z Chińskiego tw. o resztach mamy jednoznacznie wyznaczone \(\displaystyle{ M \in \{0, \ldots n-1\}}\).
Teraz mamy do znalezienia \(\displaystyle{ b}\) takie, że \(\displaystyle{ b \in \{0, \ldots p-1\} \wedge (p|b \vee p|b^{e-1} -1)}\). I analogicznie dla (\(\displaystyle{ q}\) i \(\displaystyle{ c}\)).
Pierwszy przypadek to po prostu \(\displaystyle{ b=0}\). Od tej pory zakładamy \(\displaystyle{ b\neq 0}\) (i na końcu dodamy 1 do wyniku). Mamy w takim razie \(\displaystyle{ 0<b<p}\) i \(\displaystyle{ p|b^{e-1}-1}\), tj. \(\displaystyle{ b^{e-1} \equiv 1 \pmod p}\). Dalej wykorzystany jest taki pomysł. Niech \(\displaystyle{ 0<v<p}\) będzie taką liczbą, że \(\displaystyle{ \{v^0=1, v^1, v^2, \ldots, v^{p-2}\} = \{1, \ldots, p-1\}}\), tj. \(\displaystyle{ v}\) do różnych potęg da różne liczby i wszystkie w ten sposób dostaniemy. Taka liczba istnieje, bo jest to generator grupy cyklicznej \(\displaystyle{ \mathbb{Z}_p^{*}}\) z działaniem mnożenia.
Niech \(\displaystyle{ b = v^x}\). Teraz \(\displaystyle{ \left(v^x\right)^{e-1} \equiv 1 \pmod p}\) i szukamy \(\displaystyle{ x}\) (a tak właściwie, to liczby \(\displaystyle{ x}\)'ów spełniających to równanie). Ponieważ \(\displaystyle{ p-1}\) jest najmniejszą niezerową potęgą, do której trzeba podnieść coś, aby otrzymać jedynkę, to mamy \(\displaystyle{ p-1|x(e-1)}\), tj \(\displaystyle{ x(e-1) \equiv 0 \pmod {p-1} (*)}\). Jeśli \(\displaystyle{ d = NWD(e-1, p-1)}\), to możemy podzielić stronami (trzema stronami) przez d: \(\displaystyle{ x\frac{e-1}{d} \equiv \frac{0}{d} \pmod{\frac{p-1}{d}}}\). Teraz możemy znaleźć \(\displaystyle{ x'}\) będącą odwrotnością \(\displaystyle{ \frac{e-1}{d}}\) modulo \(\displaystyle{ \frac{p-1}{d}}\) i mamy \(\displaystyle{ x' \cdot x \frac{e-1}{d} \equiv 0 \cdot x' \pmod {\frac{p-1}{d}}}\), czyli \(\displaystyle{ x \equiv 0 \pmod {\frac{p-1}{d}}}\), stąd rozwiązaniami \(\displaystyle{ (*)}\) jest \(\displaystyle{ 0, \frac{p-1}{d}, 2\frac{p-1}{d}, \ldots}\), łącznie \(\displaystyle{ d}\) rozwiązań.
Dodając nasze "zapomniane" zero mamy \(\displaystyle{ NWD(e-1, p-1) + 1}\) rozwiązań na \(\displaystyle{ b}\) i analogicznie \(\displaystyle{ NWD(e-1, q-1) + 1}\) rozwiązań na \(\displaystyle{ c}\). Każda para rozwiązań \(\displaystyle{ (b, c)}\) da z Chtwor'a inne \(\displaystyle{ M}\), więc mamy łącznie \(\displaystyle{ (NWD(e-1, p-1) + 1)(NWD(e-1, q-1) + 1) = (NWD(18, 70) + 1)(NWD(18, 102) + 1) = (2+1)(6+1) = 21}\) punktów stałych.
Ufff...