WisFaq!

RSA

Om een RSA vercijferd bericht te ontcijferen moet je de berekening y^d (mod m) uitvoeren. Omdat ik met de grote getallen y=14407, d=15823 en m=32651 zit moet ik dit in stapjes doen. Ik heb een mooie tabel gemaakt:

a	            a (mod 32651)
144071	              14407
144072	              31893
144074	              19497
144078	              10067
1440716	              28436	
1440732	               4081
1440764                2551
14407128	              10052
14407256               20510

...en nog verder...
Maar nu weet ik niet welke getallen ik wél en welke getallen ik níet moet gebruiken bij het verder rekenen en oplossen van het vercijferde bericht. Ik weet wel dat je ze niet allemaal moet gebruiken, want toen ik dat deed klopte mijn antwoord niet. Kunnen jullie me verder helpen?

Saar
13-12-2003

Antwoord

Beste Saar,

Je moet natuurlijk zorgen dat de som van de exponenten gelijk is aan d. Daarvoor helpt het als je d schrijft als binair getal.

Om even een eenvoudiger voorbeeld te nemen: stel we moeten 14407¹⁰ mod m bepalen.

10 = 1010 oftewel 2³ + 2¹ = 8 + 2.

Dus

14407¹⁰ mod m
= 14407⁸ · 14407² mod m
= 10067 · 31893 mod m
= 9548

Succes ermee.

FvL
13-12-2003