WisFaq!

RSA en Euclides

Ik ben bezig met een oefenvraag voor een tentamen waar het algoritme van Euclides wordt toegepast. Ik heb echter geen idee wat dit inhoud.

Voorbeeld:

Een creditcard maatschappij heeft de priemen p = 17 en q = 7. Dan is p*q=119.
Maak 119 bekend. Als dit product van twee priemgetallen groot genoeg is, kan het met de huidige computer techniek niet (op tijd) ontbonden worden. Verder is (17-1)*(7-1)=96. (Maak 96 NIET bekend). Neem bijvoorbeeld t=11, zodat t geen factor gemeen heeft met 96.
Maak 11 ook bekend. Bereken vervolgens s (en u) als volgt (algoritme van Euclides):

Vanaf hier snap ik niet wat er gebeurd:
96 - 8*11 = 8
11 - 1*8 = 3
8 - 2*3 = 2
3 - 1*2 = 1
3 - 1*(8 - 2*3) = 1
-1*8 + 3*3 = 1
-1*8 + 3*(11 - 1*8) = 1
3*11 - 4*8 = 1
3*11 - 4*(96 - 8*11) = 1
-4*96 + 35*11 = 1

Bij de gekozen en vrijgegeven t = 11 wordt dus s = 35 gevonden. Maak 35 NIET bekend, de u = -4 wordt niet gebruikt maar moet eveneens NIET bekend worden.

Mijn vraag is dus of u dit kunt toelichten/uitleggen bij wat er gebeurd en met name in de berekening.

met vriendelijke groet

Dennis
25-5-2004

Antwoord

Met behulp van het algoritme van Euclides bepaal je van twee getallen de grootst gemeenschappelijke deler.

Je kunt het bovenstaande opvatten als een toepassing algoritme van Euclides om de vraag te beantwoorden:

Voor welke a geldt 11·a = 1 (mod 96)?

Hiervoor gebruik je dan het algoritme van Euclides in omgekeerde volgorde! Dus:

Eerst de ggd van 11 en 96 berekenen

96 = 8 · 11 + 8 ® 8 = 96 - 8 · 11
11 = 1 · 8 + 3 ® 3 = 11 - 1 · 8
8 = 2 · 3 + 2 ® 2 = 8 - 2 · 3
3 = 1 · 2 + 1 ® 1 = 3 - 1 · 2

Nu terug rekenen:

1 = 3 - 1 · 2
1 = 1 · 3 - 1 · (8 - 2 · 3)
1 = 3 · 3 - 1 · 8
1 = -1 · 8 + 3 · (11 - 1 · 8)
1 = -4 · 8 + 3 · 11
1 = 3 · 11 - 4 · (96 - 8 · 11)
1 = 35 · 11 - 4 · 96

de inverse van 11 (mod 96) is 35 (mod 96)
de inverse van 11 (mod 96) is 35

Controle:
11 · 35 = 385
385 (mod 96) = 1

Kijk maar eens goed.

WvR
30-5-2004