WisFaq!

RSA: Berekening Ontcijfersleutel

Hallo,

Ik heb een (eenvoudige) opgave gekregen ivm RSA.

De gegevens zijn:
n = 10201
v = vercijfelsleutel = 71

Gevraagd: bepaald o = ontcijfersleutel

Ik probeer dit op te lossen, maar ik weet even niet hoe ik verder moet:

Wat ik al heb is dit:
p & q zijn priemgetallen
n = p*q, dus na enig zoekwerk weet je dat p en q = 101

(p-1)*(q-1) = 100*100 = 10000

Ik weet dat:
o * v congruent is met 1(mod 10000)
dus:
o * 71 is congruent met 1 (mod 10000)

Vervolgens bepaal ik de kettingbreuk hiervan:

10000/71

= 140 + 1/(1+1/(5+1/(2+1/5)))

Mijn probleem is dat ik nu niet meer weet hoe ik verder moet.
Iemand enig idee?
(met maple kom ik 1831 uit (msolve-commando), maar ik had graag geweten hoe ik het handmatig doe)

Dank bij voorbaat,

Vincent Claeys

Vincent Claeys
23-12-2002

Antwoord

De vraag komt neer op 'hoe bereken je de inverse van 71 (mod 10000)?'

Eerst de ggd van 71 en 10000 berekenen:
10000 = 140 · 71 + 60 Þ 60 = 10000 - 140 · 71
71 = 1 · 60 + 11 Þ 11 = 71 - 1 · 60
60 = 5 · 11 + 5 Þ 5 = 60 - 5 · 11
11 = 2 · 5 + 1 Þ 1 = 11 - 2 · 5

Nu terug rekenen:
1 = 11 - 2 · 5
1 = 1 · 11 - 2 · (60 - 5 · 11)
1 = 11 · 11 - 2 · 60
1 = -2 · 60 + 11 · (71 - 1 · 60)
1 = -13 · 60 + 11 · 71
1 = 11 · 71 - 13 · (10000 - 140 · 71)
1 = 1831 · 71 - 13 · 10000

de inverse van 71 (mod 10000) is 1831 (mod 10000)

Controle:
71 · 1831 = 130001
130001 (mod 10000) = 1

Zie Bereken de inverse van a (mod b) [http://www.wiswijzer.nl/pagina.asp?nummer=216]

WvR
23-12-2002