matematikk.net

Jeg har møtt veggen når det gjelder en del av RSA-krypteringen:

Hvis p og q er to primtall og q*p=N. Meldingen M blir kryptert på følgende måte: M^e [symbol:identisk] C(modN) der C er chifferteksten.
Så langt greit, men jeg forstår ikke hvorfor man kan dekryptere med først å finne d i utrykket:
e*d [symbol:identisk] 1(mod(p-1)(q-1))
og så å sette:

C^d(mod N)=M?

Snille? jeg står fullstendig fast.

RSA, ja. En ganske morsom sak.

Det sentral her er Eulers teorem (også kjent som Euler-Fermats teorem)

Hvis [tex]\gcd(a,n) = 1[/tex]

Så er [tex]a^{\phi(n)} \equiv 1\ \rm{mod}\ n [/tex]

Hvor [tex]\phi[/tex] er Eulers totientfunksjon.

For [tex]n = pq[/tex] er [tex]\phi(n) = (p-1)(q-1)[/tex]

Ser du nå hvorfor du kan dekryptere på den måten?

Aha! nå falt det litt mer på plass! Genialt.
Tusen takk, det gjorde dagen min.