WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

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 84¹⁸¹ 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 T¹⁸⁰ mod 703 gelijk is aan 1. Gevolg hiervan is dat T¹⁸¹=T (mod 703. Dat komt omdat het kleinste getal n waarvoor, voor zekere x, geldt dat xⁿ=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 x^kn=(xⁿ)^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 xⁿ=1, en dus xⁿ⁺¹=x^e=x (mod...)
Nu zijn er in de praktijk bij het RSA systeem altijd getallen die op zichzelf worden afgebeeld, bijv x¹, x²..

Nu heb ik in chap8,message concealing een formule gevonden (blz₈, 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.

Vragen naar aanleiding van dit antwoord? Klik rechts..!
zaterdag 24 maart 2007