Side 2 - Bevis RSA (kryptering)

Fra Eulers sætning ved du, at hvis (m,n) = 1 så er m^φ(n) ≡ 1 (mod n). Hvis vi nu tager en vilkårlig eksponent, lad os sige q, og skriver den på formen q=k·φ(n)+r, ser vi at:

m^q = m^k·φ(n)·m^r

Hvis (m,n) = 1 så er (m^k,n) = 1, og derfor giver Eulers sætning os, at m^k·φ(n) ≡ 1 (mod n). Deraf ser vi så, at m^q ≡ m^r (mod n), fordi den første faktor er kongruent med 1 og derfor kan udelades. Konklusionen bliver følgende resultat udledt af Eulers sætning:

For tal m,n med (m,n)=1 og to eksponenter q≡r (mod φ(n)) har vi at m^q≡m^r (mod n).

Anvendt på det konkrete tilfælde har vi altså, at (m,n)=1 og eksponenterne ed≡1 (mod φ(n)), hvorfor m^ed≡m¹ (mod n), hvilket skulle vises.

Okay jeg forstår at:

m^q ≡ m^r (mod n)

Hvilket jo må betyde at m^ed ≡ 1 (mod n)

Men skulle vi ikke finde at m^ed ≡ m¹ (mod n) ?????

Please hjælp mig lige det sidste. Jeg er så tæt på.

Hey Fluen på væggen.

Nu har jeg kikket på teksten lidt mere på teksten, og set om jeg forstod den. Nu har jeg prøvet at sætte nogle ord på det. Jeg er ikke helt sikker om det er helt 100 rigtigt.

Men prøv lige at se på det jeg har skrevet: http://www.shafh.dk/01.doc

Er det korrekt? Hvad har jeg misforstået?

Sorry har lige lavet en opdatering:

http://www.shafh.dk/02.doc

Ahh. Vent lige. NU FORSTÅR JEG. AHH VAR DET BARE DET :)

He he. Tussind tak for hjælpen Fluen på væggen. Du har sku virkelig hjulpet