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 og phi-funksjoner.
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
Bogfjellmo
- Cantor
- Innlegg: 142
- Registrert: 29/10-2007 22:02
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?
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?