. asdf: Arytmetyka modularna: Udowodnij indukcyjnie: n = p*q: p, q są liczbami pierwszymi, więc: Φ(n) = (p−1)*(q−1) e*d ≡ 1 mod Φ(n) To sobie wyprowadziłem: c = x^d mod n to: x = c^e mod n ale tego nie wiem: Pokaż, że dla wartości: 0,1, n−1: c = x^e mod n to: c = x, a wiec: x^d = c^d mod n => x^d = c^d dla wartosci 0: 0 = 0^e mod n = 0..to wiadome dla wartosci 1: 1 = 1^e mod n = 1..to wiadome a jak dla wartosci: n−1 = (n−1)^e mod n ?

asdf: najogolniej: chodzi o to, zeby udowodnic, że: (n−1) ≡ (n−1)^e mod n, n jest liczba pierwszą. 0 < e < n−1

asdf: sorry: 0 < e ≤ n−1

Saizou : ale w sumie co masz udowodnić ?

asdf: (n−1) ≡ (n−1)^e mod n

asdf: mam zrobić: pokaż, że dla wartości: 0, 1, n−1 jesli: c = x^e mod n, to c = x. dla x = 0: c = 0^e mod n, = > c = 0..czyli: c = x dla x = 1: c = 1^e mod n, = > c = 1..czyli c = x dla x = n−1: c = (n−1)^e mod n, = > c = (n−1)..czyli c = x, i wlasnie tego ostatniego nie wiem jak udowodnic dodam, ze: gcd(e,n) = 1 oraz 0 < e ≤ n −1

asdf: :(

zombi: A to ma zachodzić dla wszystkich e, z tego przedziału, które spełniają warunek (e,n) = 1?

asdf: Rozpatrzmy system RSA. Pokaż, korzystając z indykcji matematycznej, że szyfrogramy odpowiadające wiadomościom o wartościach 0, 1 i (n−1) są równe tym wiadomościom. Uwaga! Proszę skorzystać z własności algorytmu RSA, z której wynika, że wykładnik klucza publicznego (e) musi być nieparzysty. algorytm jest prosty: n = p*q Φ(n) = (p−1)*(q−1) nastepnie mam dwie liczby: e − wykladnik publiczny d − wykladnik prywatny e*d ≡ 1 mod Φ(n) ⇒ ed ≡ 1 mod (q−1)(p−1) mam pokazać, że: szyfrogramy odpowiadające wiadomościom o wartościach 0, 1 i (n−1) są równe tym wiadomościom. szyfrogram powstaje z takiej właśności: m − wiadomość c = m^e mod n a później mogę odtworzyć m w taki sposób: m = c^d mod n i mam udowodnić, że szyfrogram (c) odpowiada wiadomości (m) o wartości n−1, czyli: m = n−1 a wiec: c = m = n−1 Jesli cos jest nadal niejasne, prosze pytac. Dostalem takie zadanie od kumpla, probuje je rozwiazac.

asdf: :(

Saizou : nie lubię RSA wiec nie pomogę za bardzo, ale wiemy że (n−1)≡(n−1)^e mod n i NWD(n−1,n)=1 bo n jest pierwsze (n−1)^e−1≡1 mod n a z MTF mamy że a^p−1≡1 mod p, czyli e−1=n−1⇒e=n ale coś mi w tym nie gra

asdf: (n−1)^e−1 ≡ 1 mod e, to jest MTF

Saizou : fakt, zresztą n=pq , to co napisałem wcześniej jest bez sensu

asdf: kazdemu sie zdarza

asdf: masz jakis pomysl?

Saizou : jak na razie nie