Funkcja Eulera w algorytmie RSA

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
patricia__88
Użytkownik
Użytkownik
Posty: 367
Rejestracja: 15 gru 2010, o 12:27
Płeć: Kobieta
Lokalizacja: podkarpacie
Podziękował: 3 razy

Funkcja Eulera w algorytmie RSA

Post autor: patricia__88 »

Szyfrowanie:
\(\displaystyle{ C = M^e \pmod{n}}\)
wykonuje nadawca B wiadomości do A

Deszyfrowanie:
\(\displaystyle{ C^d \pmod{n} = M}\)
wykonuje odbiorca A szyfrogramu C.

Aby pokazać jakim cudem jest to deszyfrowane tak, że faktycznie otrzymujemy wiadomość, policzmy to krok po kroku:

\(\displaystyle{ C^d \pmod{n} = M^{ed} \pmod{n} = M^{1+k\varphi} \pmod{n} = M\cdot M^{\varphi k}\pmod{n} = \\ / M^\varphi \pmod{n} = 1 / = M\pmod{n} = M}\)

Nie rozumiem skąd bierze się, że \(\displaystyle{ M^{ed} \pmod{n} = M^{1+k\varphi} \pmod{n}}\) oraz skąd wiemy, że \(\displaystyle{ M^\varphi \pmod{n} = 1}\)? To drugie wygląda mi na twierdzenie Eulera, ale wówczas musimy mieć założenie, że \(\displaystyle{ (M,n)=1}\), a my takiego założenia nie mamy. Wiemy jeszcze, że \(\displaystyle{ \varphi (n)=\varphi}\)

Podaję stronkę z tymi danymi, może tam coś więcej jest, skąd to się bierze, ale ja nic takiego nie widzę: ... ogia&art=6 podpunkt IV
dexter90
Użytkownik
Użytkownik
Posty: 391
Rejestracja: 11 lis 2011, o 09:48
Płeć: Mężczyzna
Pomógł: 32 razy

Funkcja Eulera w algorytmie RSA

Post autor: dexter90 »

\(\displaystyle{ ed = 1(mod \varphi)}\)

to musi być taka liczba \(\displaystyle{ \in \ Z}\), że \(\displaystyle{ ed=1+k\phi}\)

Dałem odpowiedź na 2 pytania. Co do twojego założenia to proponuje dokładnie zapoznać się z algorytmami asymetrycznymi. Tam na końcu pewnie brakuje \(\displaystyle{ gcd(..)=1}\). Wynika to z idei RSA. Do zrozumienia rzeczy niezrozumiałych w RSA koniecznie trzeba zapoznać się z Tw. Fermata.
patricia__88
Użytkownik
Użytkownik
Posty: 367
Rejestracja: 15 gru 2010, o 12:27
Płeć: Kobieta
Lokalizacja: podkarpacie
Podziękował: 3 razy

Funkcja Eulera w algorytmie RSA

Post autor: patricia__88 »

Ok \(\displaystyle{ ed=1+k\varphi}\) już rozumiem. Ale skąd wiemy, że \(\displaystyle{ M^{\varphi} \pmod{n}=1}\)?

-- 27 lip 2012, o 22:25 --

To chyba jednak twierdzenie Eulera, czyli powinno być to założenie o liczbach względnie pierwszych? Czy mógłbyś zerknąć na tą stronkę, jakoś nie mogę tego założenia nigdzie znaleźć.


Wiemy tylko, że \(\displaystyle{ 0 \le M<n}\), ale nie ma nigdzie informacji, że liczby \(\displaystyle{ M}\) i \(\displaystyle{ n}\) są względnie pierwsze.

-- 27 lip 2012, o 22:33 --

i wiemy, że \(\displaystyle{ (\varphi , e)=1}\)
dexter90
Użytkownik
Użytkownik
Posty: 391
Rejestracja: 11 lis 2011, o 09:48
Płeć: Mężczyzna
Pomógł: 32 razy

Funkcja Eulera w algorytmie RSA

Post autor: dexter90 »

Nie pisz od tak, że \(\displaystyle{ (\varphi,e)=1}\) tylko, że \(\displaystyle{ gcd(\varphi,e)=1}\)

Prawdą jest, że:

\(\displaystyle{ M \ mod \ n = M}\)

oraz, że:

\(\displaystyle{ M^{\varphi} \ mod \ n=1}\)

Małe twierdzenie Fermata. Względnie pierwsze mają być \(\displaystyle{ M}\) oraz \(\displaystyle{ \varphi}\). \(\displaystyle{ n=pq}\) także nie musi być pierwsza, tak samo M. Poczytaj o względności.
patricia__88
Użytkownik
Użytkownik
Posty: 367
Rejestracja: 15 gru 2010, o 12:27
Płeć: Kobieta
Lokalizacja: podkarpacie
Podziękował: 3 razy

Funkcja Eulera w algorytmie RSA

Post autor: patricia__88 »

dexter90 pisze:Nie pisz od tak, że \(\displaystyle{ (\varphi,e)=1}\) tylko, że \(\displaystyle{ gcd(\varphi,e)=1}\)
Można tak oznaczać, ja tak piszę w swojej pracy.

Piszesz, że prawdą jest, że \(\displaystyle{ M^{\varphi}\pmod{n}=1}\), ale skąd to wiadomo?

Małe twierdzenie Fermata brzmi: Jeżeli \(\displaystyle{ p}\) jest liczbą pierwszą, to dla każdej liczby całkowitej \(\displaystyle{ a}\) liczba \(\displaystyle{ a^p - a}\) jest podzielna przez \(\displaystyle{ p}\), czyli \(\displaystyle{ a^p - a \equiv 0 \pmod p.}\) Lub inaczej jeśli \(\displaystyle{ p}\) jest liczbą pierwszą, a \(\displaystyle{ a}\) jest taką liczbą całkowitą, że liczby \(\displaystyle{ a}\) i \(\displaystyle{ p}\) są względnie pierwsze, to \(\displaystyle{ a^{p-1} - 1}\) dzieli się przez \(\displaystyle{ p}\). Innymi słowy, \(\displaystyle{ a^{p-1} - 1 \equiv 0 \pmod p}\), albo \(\displaystyle{ a^{p-1} \equiv 1 \pmod p}\).
Piszesz, że \(\displaystyle{ M}\) ma być względnie pierwsza, a za chwilę że nie musi, więc już się pogubiłam.-- 27 lip 2012, o 23:42 --Skąd wiemy, że \(\displaystyle{ M}\) i \(\displaystyle{ \varphi}\) są względnie pierwsze? Bo to musi zachodzić, skoro \(\displaystyle{ M^{\varphi} \ mod \ n=1}\)
dexter90
Użytkownik
Użytkownik
Posty: 391
Rejestracja: 11 lis 2011, o 09:48
Płeć: Mężczyzna
Pomógł: 32 razy

Funkcja Eulera w algorytmie RSA

Post autor: dexter90 »

Mam książkę Menzesa, przepisuję poniżej może lepiej zrozumiały dla Ciebie dowód ( kawałek kartki jest oblany kawą, także postaram się nie pomylić ), niedługo będę ją sprzedawał:

Strona 418, rozdział 8 - Szyfrowanie z kluczem publicznym
Dowód poprawności deszyfrowania:

Ponieważ \(\displaystyle{ ed=1(mod \phi)}\), istnieje taka liczba całkowita k, że \(\displaystyle{ ed=1+k\phi}\). Teraz jeśli \(\displaystyle{ gcd(m,p)=1}\) to na podstawie twierdzenie Fermata:

\(\displaystyle{ m^{p-1}=1(mod \ p)}\)

Podniesienie obu stron tej kongruencji do potęgi \(\displaystyle{ k(q-1)}\), a następnie przemnożenie obu stron przez \(\displaystyle{ m}\) daje:

\(\displaystyle{ m^{m+k(p-1)(q-1)}\)=m(mod p)[/latex],

jeśli \(\displaystyle{ gcd(m,p)=p}\), to ostatnia kongruencja jest ponownie prawdziwa, ponieważ każda strona jest kongruentna z 0 modulo \(\displaystyle{ p}\). Stąd w każdym wypadku:

\(\displaystyle{ m^{ed}=m(mod \ p)}\),

na podstawie tego samego dowodu:

\(\displaystyle{ m^{ed}=m(mod \ q)}\)

Ostatecznie ponieważ p i q są różnymi liczbami pierwszymi, wynika z tego, że:

\(\displaystyle{ m^{ed}=m(mod \ n)}\), stąd zaś:

\(\displaystyle{ c^d=(m^e)^d=m(mod \ n)}\)
Do tego dodaję:

\(\displaystyle{ n=pq \\ \phi =(p-1)(q-1)}\)

\(\displaystyle{ gcd(e,\phi)=1}\)

\(\displaystyle{ ed =1(mod \ \phi)}\)

Nie wiem jak piszesz w pracy, ale moim zdaniem winno być:

\(\displaystyle{ NWD(x,y)=1}\) bądź \(\displaystyle{ gcd(x,y)=1}\), chyba, że zaznaczyłaś to w jakimś fragmencie.

Pozdrawiam.
patricia__88
Użytkownik
Użytkownik
Posty: 367
Rejestracja: 15 gru 2010, o 12:27
Płeć: Kobieta
Lokalizacja: podkarpacie
Podziękował: 3 razy

Funkcja Eulera w algorytmie RSA

Post autor: patricia__88 »

Nadal nie do końca rozumiem, czy mógłbyć to pokazać na przykładzie mojego dowodu?

Dowód:
Aby pokazać jak to jest deszyfrowane, aby faktycznie otrzymać wiadomość, policzmy to krok po kroku:
\(\displaystyle{ C^d \ (mod \ n)=M^{ed} \ (mod \ n)}\),
wiemy, że \(\displaystyle{ d\equiv e^{-1} \ (mod \ \varphi(n))}\), zatem \(\displaystyle{ ed\equiv 1 \ (mod \ \varphi(n)) \ \Leftrightarrow \ \varphi |(ed-1)}\). Istnieje więc taka liczba \(\displaystyle{ k\in\mathbb{Z}}\), że
\(\displaystyle{ k\varphi |(ed-1) \ \Leftrightarrow \ ed-1=k\varphi \ \Leftrightarrow \ ed=1+k\varphi}\).
Mamy więc:
\(\displaystyle{ M^{ed} \ (mod \ n)=M^{1+k\varphi} \ (mod \ n)=M\cdot M^{k\varphi} \ (mod \ n)}\),

No i teraz jak pokazać końcówkę dowodu, czyli, że
\(\displaystyle{ M^{\varphi} \ (mod \ n)\equiv 1}\)
więc \(\displaystyle{ M\cdot M^{k\varphi} \ (mod \ n)\equiv M \ (mod \ n) = M}\).
patry93
Użytkownik
Użytkownik
Posty: 1251
Rejestracja: 30 sty 2007, o 20:22
Płeć: Mężczyzna
Lokalizacja: Koziegłówki/Wrocław
Podziękował: 352 razy
Pomógł: 33 razy

Funkcja Eulera w algorytmie RSA

Post autor: patry93 »

patricia__88 pisze:Mamy więc:
\(\displaystyle{ M^{ed} \ (mod \ n)=M^{1+k\varphi} \ (mod \ n)=M\cdot M^{k\varphi} \ (mod \ n)}\)
To nie będzie potrzebne w sposobie, który przedstawię poniżej (ale pewnie tą drogą też można by iść).

Najpierw możesz pokazać, że
\(\displaystyle{ M^{ed} \ (mod \ n)\equiv M \Leftrightarrow M^{ed} \ (mod \ p)\equiv M \wedge M^{ed} \ (mod \ q)\equiv M}\)
Zajmijmy się pierwszą kongruencją (druga idzie tak samo).
Wiemy, że \(\displaystyle{ \varphi |(ed-1)}\), więc \(\displaystyle{ p-1 | (ed - 1)}\), czyli \(\displaystyle{ k_1 = \frac{de-1}{p-1}}\) jest lb. naturalną.
Stąd
\(\displaystyle{ M^{ed} \ (mod \ n) = M \cdot M^{ed-1} \ (mod \ n) = M \cdot (M^{p-1})^{k_1} \ (mod \ n) = M \cdot 1^{k_1} \ (mod \ n) = M}\)
czyli to, co chcieliśmy.
patricia__88
Użytkownik
Użytkownik
Posty: 367
Rejestracja: 15 gru 2010, o 12:27
Płeć: Kobieta
Lokalizacja: podkarpacie
Podziękował: 3 razy

Funkcja Eulera w algorytmie RSA

Post autor: patricia__88 »

A skąd wiemy, że \(\displaystyle{ \varphi =p-1}\)?
Rozumiem, że to jest z tw. Fermata? Ale tam mamy założenie, że p jest liczbą pierwszą, a skąd tutaj mamy taką pewność?

A nie umiałbyś może pokazać tego w sposób, który proponowałam? Bardzo mi zależy na takim właśnie dowodzie.-- 28 lip 2012, o 16:23 --Ok już wiem, że p i q są pierwsze, to wynika z algorytmu RSA.
patry93
Użytkownik
Użytkownik
Posty: 1251
Rejestracja: 30 sty 2007, o 20:22
Płeć: Mężczyzna
Lokalizacja: Koziegłówki/Wrocław
Podziękował: 352 razy
Pomógł: 33 razy

Funkcja Eulera w algorytmie RSA

Post autor: patry93 »

Nie, \(\displaystyle{ \varphi}\) nie jest równe \(\displaystyle{ p-1}\). My ustalamy \(\displaystyle{ \varphi = (p-1)(q-1)}\) i mamy ciąg podzielności \(\displaystyle{ p-1 | (p-1)(q-1) = \varphi | (ed-1)}\)
Hm, mam takie odczucie, że troszkę się gubisz w tych literkach, zwłaszcza w kwestii które my sobie ustalamy, a które wychodzą "w praniu".
Gdyby jeszcze nie wszystko było jasne, polecam przejrzeć to: ... pId=129314
(uwaga, w tym skrypcie, przy dowodzie poprawności RSA, jest błąd - rozbijają na dwie kongruencje, a później w modulo i tak pojawią się "nierozbite" \(\displaystyle{ N}\) - wystarczy zamienić wystąpienia \(\displaystyle{ N}\) na \(\displaystyle{ p}\) lub \(\displaystyle{ q}\) i już będzie OK)
patricia__88
Użytkownik
Użytkownik
Posty: 367
Rejestracja: 15 gru 2010, o 12:27
Płeć: Kobieta
Lokalizacja: podkarpacie
Podziękował: 3 razy

Funkcja Eulera w algorytmie RSA

Post autor: patricia__88 »

Ok jednak w tym dowodzie jest potrzebna pewna własność kongruencji, mianowicie:
Jeżeli \(\displaystyle{ a\equiv b\pmod{m}}\) oraz \(\displaystyle{ d|m}\), to \(\displaystyle{ a\equiv b\pmod{d}}\)
Jak to udowodnić?-- 28 lip 2012, o 19:16 --Aha i jeszcze jedno tam korzystamy z małego twierdzenia Fermata prawda, bo na tej stronce jest błąd tam pisze że korzystamy z twierdzenia Eulera.
patry93
Użytkownik
Użytkownik
Posty: 1251
Rejestracja: 30 sty 2007, o 20:22
Płeć: Mężczyzna
Lokalizacja: Koziegłówki/Wrocław
Podziękował: 352 razy
Pomógł: 33 razy

Funkcja Eulera w algorytmie RSA

Post autor: patry93 »

Wystarczy definicja:
\(\displaystyle{ a\equiv b\pmod{m} \Leftrightarrow m|a-b}\)
Dasz radę, po prostu nie komplikuj zbytnio i wyjdzie ; )
patricia__88
Użytkownik
Użytkownik
Posty: 367
Rejestracja: 15 gru 2010, o 12:27
Płeć: Kobieta
Lokalizacja: podkarpacie
Podziękował: 3 razy

Funkcja Eulera w algorytmie RSA

Post autor: patricia__88 »

No tak tylko ja potrzebuję takiego dosyć formalnego dowodu krok po kroku i nie wiem jak to za bardzo napisać.-- 28 lip 2012, o 19:29 --Aha i jeszcze jedno wiesz może gdzie mogę znaleźć jakiś fajnie napisany dowód małego tw. fermata?
dexter90
Użytkownik
Użytkownik
Posty: 391
Rejestracja: 11 lis 2011, o 09:48
Płeć: Mężczyzna
Pomógł: 32 razy

Funkcja Eulera w algorytmie RSA

Post autor: dexter90 »

Na wikipedii jest zrozumiały.
patricia__88
Użytkownik
Użytkownik
Posty: 367
Rejestracja: 15 gru 2010, o 12:27
Płeć: Kobieta
Lokalizacja: podkarpacie
Podziękował: 3 razy

Funkcja Eulera w algorytmie RSA

Post autor: patricia__88 »

A czy może być taki dowód?
Twierdzenie: Jeżeli \(\displaystyle{ p}\) jest liczbą pierwszą oraz \(\displaystyle{ a}\) i \(\displaystyle{ p}\) są względnie pierwsze, gdzie \(\displaystyle{ a\in\mathbb{Z}}\), to
\(\displaystyle{ a^{p-1}\equiv 1 \ (mod \ p)}\).
Dowód: Weźmy liczby \(\displaystyle{ n \ (mod \ p),2n \ (mod \ p),\ldots , (p-1)n \ (mod \ p)}\), gdzie \(\displaystyle{ p}\) jest liczbą pierwszą. Następnie przemnóżmy je przez siebie:
\(\displaystyle{ n\cdot (2n)\cdot \ldots \cdot \left(\left(p-1\right)n\right)\equiv \left(n \ (mod \ p)\right)\cdot \left(2n \ (mod \ p)\right)\cdot \ldots \cdot \left((p-1)n \ (mod \ p)\right)\equiv \\
\equiv (p-1)!}\)

Oznacza to, że
\(\displaystyle{ (p-1)!n^{p-1}\equiv (p-1)! \ (mod \ p)}\),
w równaniu tym możemy usunąć wyrażenie \(\displaystyle{ (p-1)!}\), ponieważ liczba ta nie jest podzielna przez \(\displaystyle{ p}\).


Czy da się ten dowód jeszcze jakoś uszczegółowić i czy jest on w pełni poprawny?

-- 28 lip 2012, o 20:54 --
patry93 pisze: Stąd
\(\displaystyle{ M^{ed} \ (mod \ n) = M \cdot M^{ed-1} \ (mod \ n) = M \cdot (M^{p-1})^{k_1} \ (mod \ n) = M \cdot 1^{k_1} \ (mod \ n) = M}\)
czyli to, co chcieliśmy.
Jeszcze mam pytanie do tego dowodu czy tam nie powinno być czasem \(\displaystyle{ \pmod{p}}\), bo przeciez liczyliśmy najpierw dla \(\displaystyle{ p}\)

-- 28 lip 2012, o 20:56 --

I co z założeniem, że M i p są względnie pierwsze? O liczbie \(\displaystyle{ p}\) wiemy, że jest pierwsza, ale \(\displaystyle{ M}\)?

-- 28 lip 2012, o 21:08 --

A i jeszcze co do dowodu własności kongruencji:
Jeżeli \(\displaystyle{ a\equiv b \pmod{m}}\) oraz \(\displaystyle{ d|m}\), to \(\displaystyle{ a\equiv b \pmod{d}}\).

Czy może być taki dowód?
Z definicji mamy, że \(\displaystyle{ a\equiv b \pmod{m} \iff m|(a-b)}\). Zatem skoro \(\displaystyle{ d|m}\), a \(\displaystyle{ m|(a-b)}\), to również \(\displaystyle{ d|(a-b)}\), a stąd \(\displaystyle{ a\equiv b \pmod{d}}\).-- 28 lip 2012, o 21:09 --Wiem, że trochę tego nawaliłam na kupie tych pytań, ale będę bardzo wdzięczna za odpowiedź na każde z nich:)
ODPOWIEDZ