Øistein Wind wrote:
> Hej. Jeg er(ligesom mange andre) ved at forberede mig til eksamen i
> matematik (A+) i gymnasiet. Vi har beskæftiget os med RSA systemet som
> valgfrit emne, men noget af det er sku lidt svært...
> Derfor tænkte jeg på, om i ku give en hjælpende hånd.
>
> Jeg ved, at den krypterede tekst er givet ved c = M^e (mod n)... sådan er
> den defineret.
> Men hvordan når man frem til, at den dekrypterede tekst bliver til c^d (mod
> n)? Det kan jeg ikke gennemskue.
Nedenstående stump er hugget fra Preben Møller Henriksens side
(hvor ellers). Jeg har dog ændret de brugte betegnelser,
så de passer med din bog.
<
http://home3.inet.tele.dk/pmh/Tema/r1.htm>
>RSA nøgler konstrueres ud fra to store primtal p og q ( i praksis skal
>de begge helst have mindst 100 cifre ! ). Tallene ganges sammen til
>tallet n. Dernæst vælges et tal e som er mindre end og primisk med
>(p-1)·(q-1). Den offentlige kode består af (e,n). Den hemmelige kode
>består af et enkelt tal d, som er bestemt ved at
> e·d (mod (p-1)·(q-1)) = 1 .
> Tallene p og q skal destrueres, når nøglen er lavet.
> Krypteringen foregår ved at oversætte teksten tegnvis til talkoder,
> som dernæst samles til flercifrede tal, som er mindre end n. Koden
> dannes dernæst ved at beregne
> c = M^e (mod n)
> for hvert af de fremkomne tal m.
> Dekryptering af et tal k sker ved at beregne c^d (mod n) og dernæst
> oversætte tilbage til teksttegn.
Lad os se, hvad der sker, når vi prøver at afkode beskeden c.
Alle lighedstegn gælder modulo n:
c^d = (M^d)^e = M^(d·e) (mod n)
Da d·e=1 mod (p-1)(q-1) og (p-1)(q-1)=phi(n) har vi:
c^d = M^(d·e) = M^phi(n) (mod n)
Fermats sætning giver så:
c^d = M^phi(n) = M (mod n)
> Og et tillægsspørgsmål til de heldige
:
>
> Når man har: (M^e ( mod n))^d (mod n) hvordan
> bliver det så til M^e*d (mod > n)?
Hvordan har I defineret notationen (mod n) ?
Er (mod n) et tal eller er det noget man kan
skrive efter en ligning?
Er udregningerne ovenfor nok?
> Hvordan fjernes det ene modulo n?
>
> Det er der nok nogen der ved lidt om ...
Kig lidt på
<
http://home3.inet.tele.dk/pmh/Tema/krypt0.htm>
Har I fået historien om, at Rivest, Shamir og Adleman fik
æren for opfindelsen af RSA-systemet selvom en "stakkels"
mand hos det engelske efterretningsvæsen som fandt på
det først. Han havde bare ikke lov til at offentliggøre
sin opdagelse?
--
Jens Axel Søgaard