[PHP] RSA script - waar zit de fout?

[Kaastosti]

Ik ben via een aantal puzzelsites al een paar keer uitgekomen op RSA encryptie. Nou heb ik me daarin verdiept en vind het eigenlijk best wel interessant. Verscheidene sites doorgelezen vol met formules, vergelijkingen en bewijsvoeringen.

Toen wilde ik zelf wel eens proberen of ik een dergelijke encryptie kon schrijven. Aangezien ik hier op stage geen C++Builder of JBuilder tot m'n beschikking heb, ben ik maar in php begonnen, wat natuurlijk mogelijk moet zijn, alhoewel enorme getallen niet echt fijn zijn voor deze webtaal. Dat terzijde gelaten moet het iig lukken voor getallen van redelijke omvang.

Ik gebruik, om te testen of ik het goed doe, deze site: Deze dus. Hier wordt vrij uitgebreid uitgelegd hoe het in z'n werk gaat.

Als test, werk ik dan ook met het woord WHATEVER van die site, waar ik de daar gegeven formules op los laat. Bij de eerste letter krijg ik echter al een andere uitkomst dan bedoeld.

Als ik op pagina 2 van de site kijk, hebben ze daar een scriptje van de encryptie / decryptie uitvoert. Daarin wordt de letter W (letternummer 23) gecodeerd naar naar nummer 948 volgens de formule y = x^r (mod n). In deze formule weet ik:

x = 23
r = 25
p = 29
q = 37
n = p * q = 1073

Ik bereken dan dus:

y = 23^25 (mod 1073), wat zoveel betekent als dat y en 23^25 (23 tot de macht 25) bij een deling door 1073 dezelfde rest over houden. Daarbij kom ik voor y op een waarde van 761.

Daar klopt dus ergens iets niet. Ik vermoed dat mijn fout in de implementatie van de modulo zit, maar hoe ik deze precies zou moeten veranderen kan ik niet vinden. Ik heb een aantal sites en wiskunde fora er op nageslagen, maar vind daar helaas geen antwoord waarmee dit opgelost is. Waar zit 'm de fout, zodat ik _wel_ op 948 uitkom?

Hier is m'n (foutieve) stukje code voor het encrypten van die letter:

PHP:

$encrypted = (bcpow($string, $r) % $n);

[ Voor 5% gewijzigd door Kaastosti op 25-06-2003 10:54 ]

[Glimi]

Toevallig weet ik nog twee topics die hierover gegaan zijn
[rml][ PHP] RSA-algoritme in PHP: probleem[/rml]
inverse mod (RSA encrypting)

HTH

[Kaastosti]

Heh jij bent er dus ook al eens mee bezig geweest
Maaruh.. wat is HTH?

[Verwijderd]

Kaastosti schreef op 25 June 2003 @ 11:03:
Heh jij bent er dus ook al eens mee bezig geweest
Maaruh.. wat is HTH?

http://www.sensei.co.il/languages/acronyms.html

[Kaastosti]

Kijk eens aan, een handige site cadeau... dan begrijp ik 't tenminste ook weer

Maar als ik het zo bekijk doet Doenderrr precies hetzelfde als ik:

(ascii code)^(macht) modulo n

bcpow($string, $r) % n

Hij gaat er duidelijk van uit dat dat goed is, waarom krijg ik dan andere data terug dan de applet van de site in m'n eerste posting? Die werkt namelijk goed bij zowel encryptie als decryptie. Ik kan alleen maar encrypten, decrypten werkt niet. Natuurlijk wel heel veilig enzo, maar niet erg handig als het om een public key systeem gaat

[ Voor 75% gewijzigd door Kaastosti op 25-06-2003 11:16 ]

[Verwijderd]

Als je iets verder leest zie je dat hij dat vervangen heeft door het volgende:

PHP:

bcmod(bcpow($string, $r), $n);

@ Kaastosti hieronder: Ten eerste is %n sowieso fout, en moet het %$n zijn

[ Voor 25% gewijzigd door Verwijderd op 25-06-2003 11:21 ]

[Kaastosti]

Hmm gevonden...

Als ik bcmod(bcpow($string, $r), $n) gebruik komt ie er _wel_ uit. Dat ligt dus op een of andere manier wel aan php. Er is natuurlijk een verschil tussen modulo en modulus, maar in deze zie ik 'm niet echt. Ondanks dat werkt het nu wel

--
Heh je was me voor, maar inderdaad... nou nog even uitzoeken wat nu precies het verschil is tussen %n en bcmod()

[ Voor 20% gewijzigd door Kaastosti op 25-06-2003 11:20 ]

[Verwijderd]

Oh btw, je kan ook:

PHP:

bcpowmod($string, $r, $n);

gebruiken, als je het nog mooier wilt

En het is nog sneller dan:

PHP:

bcmod(bcpow($string, $r), $n);

ook...

En bcpowmod() accepteert grotere getallen

Edit: lama, tis alleen in PHP 5 naja weet ik dat vast voor de toekomst

[ Voor 62% gewijzigd door Verwijderd op 25-06-2003 11:27 . Reden: domme fout ]

[Kaastosti]

Hmmm call to undefined function bcpowmod...

bcpowmod
(PHP 5 CVS only)

Ach ja... je kan niet alles hebben

[Kaastosti]

Alles werkt dus perfect, ik heb het script helemaal afgemaakt en kan nu voor ieder willekeurig woord een encryptie en decryptie krijgen. Nu bedenk ik mij echter dat een bericht wat RSA encrypted is, altijd gewoon uit karakters bestaat en niet uit nummers.

Ik kom nu per karakter op een nieuw nummer uit, waarbij het originele nummer gewoon de positie van de letter in het alfabet is. Voor het woord WHATEVER krijg ik (geconverteerd naar lowercase) voor de letter W het getal 948. Dat is natuurlijk niet te converteren naar een ASCII karakter. Ook een lucratieve deling door n heeft hier weinig zin, aangezien je dat nooit meer terug komt op 948

Kortom, wat gebeurd er met RSA nadat je een karakter gecodeerd hebt.

[dusty]

ModTip: Gebruik soms :