RSA private key bepalen

Het forum voor overige vragen betreffende wiskunde uit het hoger onderwijs.

RSA private key bepalen

Berichtdoor 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.
Kaart
Nieuw lid
Nieuw lid
 
Berichten: 6
Geregistreerd: 20 Mei 2016, 15:48

Re: RSA private key bepalen

Berichtdoor 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?
arie
Moderator
Moderator
 
Berichten: 3003
Geregistreerd: 09 Mei 2008, 09:19

Re: RSA private key bepalen

Berichtdoor 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?
Kaart
Nieuw lid
Nieuw lid
 
Berichten: 6
Geregistreerd: 20 Mei 2016, 15:48

Re: RSA private key bepalen

Berichtdoor 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.
arie
Moderator
Moderator
 
Berichten: 3003
Geregistreerd: 09 Mei 2008, 09:19

Re: RSA private key bepalen

Berichtdoor 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.
Kaart
Nieuw lid
Nieuw lid
 
Berichten: 6
Geregistreerd: 20 Mei 2016, 15:48


Terug naar Hoger onderwijs - overig

Wie is er online?

Gebruikers in dit forum: Geen geregistreerde gebruikers en 4 gasten

Wie is er online?

Er zijn in totaal 4 gebruikers online :: 0 geregistreerd, 0 verborgen en 4 gasten (Gebaseerd op de gebruikers die actief waren gedurende 5 minuten)
De meeste gebruikers ooit tegelijkertijd online was 649 op 31 Okt 2014, 18:45

Gebruikers in dit forum: Geen geregistreerde gebruikers en 4 gasten
Copyright © 2009 Afterburner - Free GPL Template. All Rights Reserved.