---

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.

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 fjernes det ene modulo n?

Det er der nok nogen der ved lidt om ...

MVH
Øistein

---

Ø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.
>
> 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 fjernes det ene modulo n?
>
> Det er der nok nogen der ved lidt om ...

Jeg ved intet om det, men prøv at læse <URL:http://stocholm.dk/crypto/>
samt de følgende sider...

/Torben

---

Ø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

---

> 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>

Den dukkede ikke op hos google...

> 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:

Så langt er jeg med, men hvad er phi(n)?

> c^d = M^(d·e) = M^phi(n) (mod n)
>
> Fermats sætning giver så:
>
> c^d = M^phi(n) = M (mod n)

Jeps... hvis blot heg vidste hvad phi(n) var.. :)

> Hvordan har I defineret notationen (mod n) ?
> Er (mod n) et tal eller er det noget man kan
> skrive efter en ligning?

Hmm... Jeg er ikke helt sikker på, om vi skriver (mod n) som tal. Et
eksempel: 3^24=1 (mod 7)
Er det at skrive det som tal?

> Er udregningerne ovenfor nok?

Meget fine! Tusind tiak for hjælpen indtil videre...
> Kig lidt på
>
> <http://home3.inet.tele.dk/pmh/Tema/krypt0.htm>

Har kigget den igennem nu

> 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?

Næ! Det har vi ikke, men det har jeg nu!

Jeg takker mange gange for hjælpen, og undskylder hvis det er dumme
spørgsmål!

Mvh
Øistein

---

Øistein Wind wrote:
>>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>
>
>
> Den dukkede ikke op hos google...
>
>
>> 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:
>
>
> Så langt er jeg med, men hvad er phi(n)?

Det er Eulers phi-funktion. (Udtales fi)
Tallet phi(n) er antallet af tal mellem 1 og n,
som ikke andre divisorer til fælles med n end 1.

Eksempel
Beregning af phi(6)
sfd(1,6) = 1
sfd(2,6) = 2
sfd(3,6) = 3
sfd(4,6) = 2
sfd(5,6) = 1
sfd(6,6) = 6
Der er altså to tal mellem 1 og 2 som ikke har
andre divisorer til fælles med 6 end 1 (nemlig
tallene 1 og 5). Derfor er phi(6)=2.

Beregning af phi(7)
sfd(1,7) = 1
sfd(2,7) = 1
sfd(3,7) = 1
sfd(4,7) = 1
sfd(5,7) = 1
sfd(6,7) = 1
sfd(7,7) = 7
Her var der 6 tal, så phi(7)=6.

Ovenstående metode er lidt besværlig, så
man har fundet genveje. En genvej er at

phi(p) = p-1 , hvis p er et primtal

Vi kunne altså lynhurtigt have fundet phi(7)
sådan:

phi(7) = 7-1 = 6

Tallet 6 er ganget sammen af to primtal,
og sådanne tal er der også en genvej for

phi(p*q) = phi(p)*phi(q) hvor p og q er primtal

Vi kan nu udregne phi(6) sådan:

phi(6) = phi(2*3)
= phi(2)*phi(3) [genvej 2]
= (2-1) * (3-1) [genvej 1]
= 1*2
= 2

Smart, ikke?

Prøv at udregne phi(15) ved hjælp af begge metoder,
og se om tallene bliver de samme.

>> c^d = M^(d·e) = M^phi(n) (mod n)
>>
>>Fermats sætning giver så:
>>
>> c^d = M^phi(n) = M (mod n)
>
>
> Jeps... hvis blot heg vidste hvad phi(n) var.. :)

Er Fermats sætning i jeres bog, og hvordan ser den ud?
[Skriv den gerne af, så vi kan se den]

>>Hvordan har I defineret notationen (mod n) ?
>>Er (mod n) et tal eller er det noget man kan
>>skrive efter en ligning?
>
>
> Hmm... Jeg er ikke helt sikker på, om vi skriver (mod n) som tal. Et
> eksempel: 3^24=1 (mod 7)
> Er det at skrive det som tal?

Nej, det er at skrive det efter en ligning.
Så skriver jeg på samme måde som din bog.

> Jeg takker mange gange for hjælpen, og undskylder hvis det er dumme
> spørgsmål!

Spørg bare løs. Der er meget matematik, der er svært, indtil
man vænner sig til det.

--
Jens Axel Søgaard

---

> > Så langt er jeg med, men hvad er phi(n)?
>
> Det er Eulers phi-funktion. (Udtales fi)
> Tallet phi(n) er antallet af tal mellem 1 og n,
> som ikke andre divisorer til fælles med n end 1.

Okay... så fik jeg styr på det.

> man har fundet genveje. En genvej er at
>
> phi(p) = p-1 , hvis p er et primtal
>
> Smart, ikke?

Super

> Er Fermats sætning i jeres bog, og hvordan ser den ud?
> [Skriv den gerne af, så vi kan se den]

Hermed Fermats _lille_ sætning:
Lad p være et primtal og antag at gcd(p,a) = 1. Der gælder da, at a^(p-1)
(er kongruent med) 1 (mod p) eller a^p (er kongrent med) a (mod p)


> Nej, det er at skrive det efter en ligning.
> Så skriver jeg på samme måde som din bog.

Ok.

Nu står der i vores bevis, at M^(e*d) = M^(k(p-1)(q-1)+1) =
M*M^(k(p-1)(q-1)) = M*(M^(q-1)^(k(p-1))
Ifølge fermats lille sætning er M^(q-1) kongruent med 1 (mod q). Herefter
siges det, at så må også M^(q-1)^(k(p-1)) kongruent med 1 (mod q).
Hvorfor det?

> Spørg bare løs. Der er meget matematik, der er svært, indtil
> man vænner sig til det.

Det er ialt fald rart at du gider hjælpe lidt...
Hele pensum sidder står helt klart i mit hoved, bortset fra dette.

MVH
Øistein

---

Øistein Wind wrote:
>>>Så langt er jeg med, men hvad er phi(n)?
>>
>>Det er Eulers phi-funktion. (Udtales fi)
>>Tallet phi(n) er antallet af tal mellem 1 og n,
>>som ikke andre divisorer til fælles med n end 1.
>
> Okay... så fik jeg styr på det.

Fino.

>> phi(p) = p-1 , hvis p er et primtal

>>Er Fermats sætning i jeres bog, og hvordan ser den ud?
>>[Skriv den gerne af, så vi kan se den]
>
>
> Hermed Fermats _lille_ sætning:
> Lad p være et primtal og antag at gcd(p,a) = 1. Der gælder da, at a^(p-1)
> (er kongruent med) 1 (mod p) eller a^p (er kongrent med) a (mod p)

Ok. I har den "lille" version

p-1
a = 1 (mod p) når gcd(p,a)=1

> Nu står der i vores bevis, at
> M^(e*d) = M^(k(p-1)(q-1)+1) =

Husk hvordan man valgte e og d.
Man sørgede for at vælge dem så

e·d (mod (p-1)·(q-1)) = 1

Det betyder, at hvis vi dividerer ed med (p-1)(q-1)
så får vi en til rest. Skal vi ikke sige at (p-1)(q-1)
går op k gange med 1 til rest. Så har vi nemlig:

ed = k*(p-1)(q-1) + 1

Så kan vi regne som i din bog:


M^(ed) = M^ (k*(p-1)(q-1) + 1)
= M * M^(k(p-1)(q-1))
= M * ( M^(q-1) ) ^ ( k(p-1) )

Nu siger Fermats lille sætning så at

M^(q-1) = 1 (mod q)

så

M^(ed) = M * 1^( k(p-1) ) (mod q)

Men 1 opløftet til noget er jo 1, så

M^(ed) = M * 1 (mod q)

M^(ed) = M (mod q)


Forresten. Har det været et godt valgfrit emne?


--
Jens Axel Søgaard

---

> M^(ed) = M^ (k*(p-1)(q-1) + 1)
> = M * M^(k(p-1)(q-1))
> = M * ( M^(q-1) ) ^ ( k(p-1) )
>
> Nu siger Fermats lille sætning så at
>
> M^(q-1) = 1 (mod q)
>
> så
>
> M^(ed) = M * 1^( k(p-1) ) (mod q)

Aahhh... Jeg har den måske nu(er ikke sikker, men det er et forsøg værd):

For at nå frem til
M^(ed) = M * 1^( k(p-1) ) (mod q)


Siger man først at
M^(q-1) = 1 (mod q)
Må man så herefter opløfte til (k(p-1))'te potens?
Og så gange med M?

ALtså:

M^(q-1)^k(p-1)) = 1^(k(p-1)) (mod q) <=>
M*M^(q-1)^k(p-1)) = M*1^(k(p-1))

Så står der jo nemlig, at M^(e*d) = M (mod q)

Håber det var den rigtige måde at gøre det på... ?

> Forresten. Har det været et godt valgfrit emne?

Det har været meget spændende... og svært! Men interessant har det været,
dog uden så mange historier og baggrundsfortællinger. Mest matematik. Det er
vores lærers egne noter vi sidder og bakser med. Du skal ha mange tak for
hjælpen ihvertfald!

Mvh
Øistein

---

Øistein Wind wrote:
>> M^(ed) = M^ (k*(p-1)(q-1) + 1)
>> = M * M^(k(p-1)(q-1))
>> = M * ( M^(q-1) ) ^ ( k(p-1) )
>>
>>Nu siger Fermats lille sætning så at
>>
>> M^(q-1) = 1 (mod q)
>>
>>så
>>
>> M^(ed) = M * 1^( k(p-1) ) (mod q)
>
>
> Aahhh... Jeg har den måske nu(er ikke sikker, men det er et forsøg værd):
>
> For at nå frem til
> M^(ed) = M * 1^( k(p-1) ) (mod q)
>
>
> Siger man først at
> M^(q-1) = 1 (mod q)
> Må man så herefter opløfte til (k(p-1))'te potens?
> Og så gange med M?

Ja lige præcis.

Du har lov til at opløfte på hver side, for I har sikkert
en sætning som siger:

SÆTNING 1
Hvis a=b (mod n)
så er a^m = b^m (mod n).

For at vise den skal man bruge

SÆTNING 2

Hvis a=b (mod n)
og c=d (mod n)
så er ac=db (mod n)

BEVIS (Sætning 2)

Da a=b (mod n) går n op i a-b, altså n|a-b.
Tilsvarende har vi, at n|c-d.

Vi skal undersøge om ac=db (mod n) altså
om n | ac-db . Lad os se:

ac-db = (a-b)c +bc -db = (a-b)c + b(c-d)

Ah! Da n|a-b så n|(a-b)c tilsvarende n|b(c-d).
Da n går op i begge led går n også op i summen.

BEVIS (Sætning 1)

Vi ved at a=b (mod n). Vi bruger nu sætning 2 med c=a og d=b.
Sætning 2 giver så:

aa = bb (mod n)

Nu kan vi igen bruge sætning 2:

aaa = bbb (mod n)

Og hvis vi fortsætter, så får vi for alle m>=1

a^m = b^m

[Øvelse: Hvorfor er a^0=b^0 (mod n) altid rigtig,
når a og b ikke er 0 ?]


[Øvelse: Lav ovenstående om til et "rigtigt" induktionsbevis]


> ALtså:
>
> M^(q-1)^k(p-1)) = 1^(k(p-1)) (mod q) <=>
> M*M^(q-1)^k(p-1)) = M*1^(k(p-1))
>
> Så står der jo nemlig, at M^(e*d) = M (mod q)
>
> Håber det var den rigtige måde at gøre det på... ?

Det er det.

>>Forresten. Har det været et godt valgfrit emne?
>
>
> Det har været meget spændende... og svært! Men interessant har det været,
> dog uden så mange historier og baggrundsfortællinger. Mest matematik. Det er
> vores lærers egne noter vi sidder og bakser med.

Okay. Har I brugt nogle computer- eller lommeregnerprogrammer i
forbindelse med emnet?

--
Jens Axel Søgaard

---

> > Håber det var den rigtige måde at gøre det på... ?
>
> Det er det.

Det var da herligt


> Okay. Har I brugt nogle computer- eller lommeregnerprogrammer i
> forbindelse med emnet?

Vi´har ikke brugt nogle computerprogrammer, men vi fik 3 programmer til
lommeregneren... jeg kan ikke lige huske hvad de hed. Men det ene var til at
finde en primfaktor oplæsning af et tal. Det andet beregnede vist d =
e^-1(mod (p-1)(q-1))

Men jeg var jo til eksamen idag, og trak eksponentialfunktioner. Det blev da
til et 11-tal... så det er helt okay!
Men tak for hjælpen alligevel!

Mvh
En meget glad Øistein

---

Øistein Wind wrote:

> Men jeg var jo til eksamen idag, og trak eksponentialfunktioner. Det blev da
> til et 11-tal... så det er helt okay!
> Men tak for hjælpen alligevel!
>
> Mvh
> En meget glad Øistein

Tillykke.

--
Jens Axel Søgaard