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.
RSA private key bepalen
Re: RSA private key bepalen
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?
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?
Re: RSA private key bepalen
Beste Arie,arie schreef:
Lukt het nu om de d te vinden in jouw versleuteling?
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?
Re: RSA private key bepalen
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.
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.
Re: RSA private key bepalen
Oké helder! Hartelijk bedankt voor je hulp.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.