\require{AMSmath}
WisFaq - de digitale vraagbaak voor wiskunde en wiskunde onderwijs


Printen

Cryptografie, ongecodeerde tekens bij RSA?

Beste dames en heren,

Ik heb eeb vraag over het coderen en decoderen met het RSA systeem.
Ik heb de priemgetallen p=19 en q=37 genomen.
De n wordt dan 703 en f(n) wordt dan 18x36=648
Als ik nu voor e, het getal 181 kies (de ggd van 181 en 648 is volgend mij 1), dan kom ik op een d van 469.
Als ik nu bv de letter T wil coderen (T=84 (met ascII tabel)), dan krijg ik 84181 mod(703)=84 en dat is volgens mij niet de bedoeling. Hoe kan ik te weten komen bij welke e het coderen wel of niet goed gaat?

vriendelijke groeten uit roosendaal

Marcel
Leerling bovenbouw havo-vwo - woensdag 21 maart 2007

Antwoord

Het probleem is dat je e zo hebt gekozen dat e-1 deelbaar is door p-1 en door q-1. Dat heeft tot gevolg dat alle getallen tussen 1 en p·q gecodeerd worden tot zichzelf.
Probeer eerst maar eens voor een aantal waarden van T uit dat T180 mod 703 gelijk is aan 1. Gevolg hiervan is dat T181=T (mod 703. Dat komt omdat het kleinste getal n waarvoor, voor zekere x, geldt dat xn=1 (mod p·q) een deler is van phi(pq)=(p-1)·(q-1). Het gevolg daarvan is weer dat voor dit getal n geldt dat xkn=(xn)k=1 (mod pq). Nu kun je wel aanvoelen dat als n een veelvoud is van p-1 en van q-1 dat er dan heel veel getallen x zijn zo, dat xn=1, en dus xn+1=xe=x (mod...)
Nu zijn er in de praktijk bij het RSA systeem altijd getallen die op zichzelf worden afgebeeld, bijv x1, x2..

Nu heb ik in chap8,message concealing een formule gevonden (blz8, viii) die aangeeft hoeveel waarden van x er zijn die bij een zekere keus van e niet worden gecodeerd.
Die formule is (1+ggd(e-1,p-1))·(1+ggd(e-1,q-1)) (ggd=grootste gemene deler)
In jullie geval (e=181, p=19, q=37) moet je dus berekenen:
(1+ggd(180,18))·(1+ggd(180,36))=(1+18)·(1+36)=19·37. Dat wil dat zeggen alle getallen x van 1 tot 703 op zichzelf worden afgebeeld.
Conclusie: behalve de voorwaarde ggd(e,(p-1)(q-1))=1 is het ook nodig om ggd(e-1,p-1) en ggd(e-1,q-1) beide zo klein mogelijk te houden.
Bij de keus p=19 en q=37 betekent dat dus:
e-1 mag geen 4-voud zijn (anders is ggd(e-1,36) tenminste 4 en ggd(e-1,18) tenmiste 2)
e-1 mag geen 3 voud zijn (anders zijn ggd(e-1,36) en ggd(e-1,18) tenminste 6 en misschien wel 18)
Kort samengevat: de beste resultaten krijg je met een waarde van e waarvoor ggd(e-1,p-1)=2 en ggd(e-1,q-1)=2.


zaterdag 24 maart 2007

©2001-2024 WisFaq