RSA private key bepalen

Het forum voor overige vragen betreffende wiskunde uit het hoger onderwijs.
Plaats reactie
Kaart
Nieuw lid
Nieuw lid
Berichten: 6
Lid geworden op: 20 mei 2016, 15:48

RSA private key bepalen

Bericht door Kaart » 26 okt 2016, 12:50

Beste forumleden,

Voor school moet ik RSA sleutels kunnen bepalen. Het is eenvoudig een publieke sleutel uit te rekenen. Hiervoor neem ik 2 priemgetallen en deze vermenigvuldig ik.

In het voorbeeld van school is de publieke sleutel N = 23449 met e = 3.
Door N te ontbinden in priem factoren krijg je P = 131 en Q = 179.

Ik moet nu de private key d uitrekenen. Ik weet dat dit kan met het (uitgebreide) Euclidische algoritme. Alleen begrijp ik niet goed hoe ik deze moet gebruiken. Kan iemand mij een voorbeeld geven hoe ik dit algoritme gebruik om de sleutel d uit te rekenen? Alvast hartelijk bedankt.

arie
Moderator
Moderator
Berichten: 3051
Lid geworden op: 09 mei 2008, 09:19

Re: RSA private key bepalen

Bericht door arie » 26 okt 2016, 18:43

Een ander voorbeeld:

p = 211
q = 233
n = 49163
Phi(n) = 48720

kies e = 361
(controleer dat ggd(e,Phi(n)) = ggd(361,48720) = 1)

nu zoeken we d, zodanig dat
d*e = 1 (mod Phi(n))

en in dit geval:

d*361 = 1 (mod 48720)

dus willen we oplossen voor een geheel getal k:

d*361 = 1 + k*48720

ofwel

d*361 - k*48720 = 1 = ggd(361, 48720)

en dit lukt met het uitgebreide algoritme van Euclides.

48720 / 361 = 134 rest 346, dus

48720 = 134 * 361 + 346

En deze stap herhalen we totdat we bij rest = 1 (= ggd(361, 48720)) zijn:

[v1] 48720 = 134 * 361 + 346

[v2] 361 = 1 * 346 + 15

[v3] 346 = 23 * 15 + 1

Nu is de rest 1 en zijn we klaar met het eerste gedeelte.
In het tweede gedeelte herschrijven we deze vergelijkingen in omgekeerde volgorde:
we werken terug van de laatste (in dit geval [v3]) naar de eerste ([v1]).

Uit de laatste vergelijking, [v3], halen we:

[v4] 1 = 346 - 23 * 15

Merk op: we schrijven nu steeds dezelfde vergelijking in de vorm:
rest = .... - .... * .....

Uit vergelijking [v2] halen we:

[v5] 15 = 361 - 1 * 346

Dit resultaat vullen we in in vergelijking [v4]:

1 = 346 - 23 * 15 = 346 - 23 * (361 - 1 * 346)

ofwel, als we de haakjes wegwerken:

[v6] 1 = -23 * 361 + 24 * 346

Uit vergelijking [v1] halen we:

[v7] 346 = 48720 - 134 * 361

Dit resultaat vullen we in in vergelijking [v6]:

1 = -23 * 361 + 24 * 346 = -23 * 361 + 24 * (48720 - 134 * 361)

ofwel, als we de haakjes wegwerken:

1 = 24 * 48720 - 3239 * 361

En nu zijn we klaar met het algoritme.

Nemen we beide zijden (mod 48720), dan vinden we:

1 (mod 48720) = (24 * 48720 - 3239 * 361) (mod 48720)

ofwel (want 48720 = 0 (mod 48720)):

1 (mod 48720) = (- 3239 * 361) (mod 48720)

ofwel (want we mogen (mod 48720) ook 48720 (= 0) bij die -3239 optellen):

1 = (48720 - 3239) * 361 (mod 48720)

ofwel

1 = 45481 * 361 (mod 48720)

Dus in dit geval is de d die we zochten:

d = 45481

En nu is je RSA versleuteling klaar om gebruikt te worden:
Publiek: n en e
Prive: n en d (d blijft geheim)
Geheim maar niet meer nodig: p, q, Phi(n)

Lukt het nu om de d te vinden in jouw versleuteling?

Kaart
Nieuw lid
Nieuw lid
Berichten: 6
Lid geworden op: 20 mei 2016, 15:48

Re: RSA private key bepalen

Bericht door Kaart » 01 nov 2016, 21:55

arie schreef:
Lukt het nu om de d te vinden in jouw versleuteling?
Beste Arie,

Super bedankt voor de uitleg. Ik denk dat ik de "d" in mijn voorbeeld kan vinden.

p = 131
q = 179
n = 23449
Phi(n) = 23140
e = 3

23140 / 3 = 7713 rest 1.

Een docent heeft ons een handig algoritme uitgelegd. Ik zal hier verder niet te diep op ingaan maar het komt er op neer dat:
De inverse van 3 modulo 23140 = 15427.

Volgens mij is de "d" in m'n voorbeeld 15427. Klopt dit?

arie
Moderator
Moderator
Berichten: 3051
Lid geworden op: 09 mei 2008, 09:19

Re: RSA private key bepalen

Bericht door arie » 01 nov 2016, 22:32

Je kan je gevonden d eenvoudig controleren:
er moet immers gelden:
e*d (mod Phi(n)) = 1

d = 15427
e = 3
e*d = 46281
Phi(n) = Phi(23449) = 23140

e*d (mod Phi(n)) =
46281 (mod 23140) = 1

d = 15427 is dus een goed antwoord.

Kaart
Nieuw lid
Nieuw lid
Berichten: 6
Lid geworden op: 20 mei 2016, 15:48

Re: RSA private key bepalen

Bericht door Kaart » 01 nov 2016, 23:17

arie schreef:Je kan je gevonden d eenvoudig controleren:
er moet immers gelden:
e*d (mod Phi(n)) = 1

d = 15427
e = 3
e*d = 46281
Phi(n) = Phi(23449) = 23140

e*d (mod Phi(n)) =
46281 (mod 23140) = 1

d = 15427 is dus een goed antwoord.
Oké helder! Hartelijk bedankt voor je hulp.

Plaats reactie