[JS/PHP] Rekenen met grote getallen (machten, modulo)

[Verwijderd]

Ik wil, als uitdaging, een RSA-like encryptiesysteem maken dat via Javascript een bericht versleuteld, deze verstuurd naar de server. De server ontsleuteld vervolgens het bericht en gaat er mee verder werken. Heb naar wt zoeken en dergelijke wel door hoe het allemaal werkt, mede dankzij de volgende wikipedia: http://en.wikipedia.org/wiki/RSA.

Encryptie: Het bericht word omgezet in een nummer n die kleiner is als de modulus N. Dit getal n word tot de macht e verheven (de publieke exponent), vervolgens word van de uitkomst de rest-deling met N berekent:

Oftewel: versleuteld = pow(naarGetal(text), e) mod N;

Decryptie: Het versleutelde bericht (een getal) word verheven tot de macht d (de geheime exponent), ver, vervolgens word van de uitkomst de rest-deling met N berekent. Het getal wat daar uitkomt is via een reverse naarGetal om te zetten in de originele text.

Oftewel: text = naarText(pow(versleuteld, d) mod N);

So far so good: ik weet hoe het werkt, en in pseudocode heb ik alles al af: Maar voor mij blijft er een probleem, namelijk de enorme grote van de getallen: Het nummer n is een 192bits getal, dat maakt de modulus dus groter dan 192bits, deze word waarschijnlijk groter dan 512bits. Verder zullen de uitkomsten van de machtsverheffing ronduit gigantisch zijn. Dus zo te zien geen getallen waar PHP mee om kan gaan, laat staan javascript.

Nou heb ik al wel wat gezocht, en vond op de wikipedia-site het volgende: http://en.wikipedia.org/wiki/Modular_exponentiation

code:

Bignum modpow(Bignum b, Bignum e, Bignum m) {

   Bignum result = 1;

   while (e > 0) {
      if (e & 1 > 0) result = (result * b) % m;
      e >>= 1;
      b = (b * b) % m;
   }

   return result;
}

Daar word heel netjes en mooi de belangrijkste bewerking verklaart hoe die beter/efficienter/sneller kan. Maar dan blijft het probleem: hoe vermenigvuldig ik, hoe bereken ik de modulus, of hoe doe ik een bitshift op zulke grote getallen.

Nou heb ik al gezocht via google, vind ook meerdere uitgewerkte voorbeelden (bijvoorbeeld: www.leemon.com). Maar ik wil zelf weten hoe ik het aan de gang krijg en wat ik aan het doen ben. Via google heb ik geen tutorial/uitleg of iets dergelijks niets kunnen vinden.

Dus mijn vraag: Hoe ga je om/hoe reken je met grote getallen in een omgeving die die grote van de getallen niet natief ondersteund. En dit op een manier die je helemaal snapt.

[Koeniepoenie]

Grappig, hier ben ik ook een keer aan begonnen, helaas niet geheel afgemaakt. Ik heb destijds ook een vraag gehad over deze functie, want ik kwam er ook niet geheel uit (dit topic). Daar kwam .oisyn met een heel fijne oplossing, die ik rekentechnisch eigenlijk nog niet helemaal snap, maar afijn.. Dit is de functie die hij gaf:

PHP:

function modpow ($a, $m, $n)  // a^m % n
{
    $r = 1;
    $num = (int)(log ($m) / log (2));
    for ($i = $num; $i >= 0; $i--)
    {
        $r = $r * $r % $n;
        if (($m & (1 << $i)) != 0)
            $r = ($r * $a) % $n;
    }
    return $r;
}

[matthijsln]

Hier heb ik eens een keer een functie voor gemaakt; zie

http://groups.google.nl/g...ed6a50afd7c30?hl=nl&fwc=1

PHP:

function modpow_using_bc($num, $exp, $mod) {

        if(!is_numeric($num) || !is_numeric($exp) || !is_numeric($mod)) {
                trigger_error("modpow_using_bc() only accepts numeric "
                             ."arguments",
                              E_USER_ERROR);
        }

        if($exp > 0x7ffffff || $exp < 0 || !is_int($exp)) {
                trigger_error("modpow_using_bc() argument exp must be "
                             ."an integer in range 0 <= exp <= 0x7fffffff",
                              E_USER_ERROR);
        }

        $mask = 0x40000000;
        while(($exp & $mask) == 0) {
                $mask = $mask >> 1;
        }

        $result = "1";

        while($mask != 0) {

                $result = bcmul($result, $result);

                if(($exp & $mask) != 0) {
                        $result = bcmul($result, $num);
                }

                $result = bcmod($result, $mod);

                $mask = $mask >> 1;
        }

        return $result;

}

[Verwijderd]

Even een voorbeeld van sleutels:

code:

e = 73
d = 15257188452545504162742193419007167394598139503017201927979344559234431057764531296740752487449375793445894979483401610670558125904570669507844547845535134123365133250183187814862114835456601625232228819887621079219013652643388186393859821985844941022251186039998746429948403030795855537638407205860134932417
N = 27165237976483458631223905355793249263552784968786725383963223239612523590653921577123778819117181290769520329324105306803676663195942899367625658359123542163566934583811222361595550003804546660497952442670711340541254944697438699301510844229315652711690381833781395833638744616016606768577456777851553983179

Met bovenstaande functie (een vrije vertaling in PHP van mijn pseudocode) kan je dus heel goed encrypten: Maar encrypten gebeurt dus in Javascript (en daar heb ik heen bcmul/bcmod). Het decrypten gaat wel in PHP, maar de functie bovenstaand kan dat dan weer niet omdat de exponent veel te groot is.


Ben nu dus een soort van bcmul/bcmod in Javascript aan het bedenken

[ Voor 6% gewijzigd door Verwijderd op 06-06-2005 11:23 ]

[matthijsln]

Ik heb de precieze werking van RSA even niet paraat maar volgens mij heb je geen modpow met een BigNum exponent nodig voor encryptie danwel decryptie dacht ik.

[Verwijderd]

Heb met een beetje gerommel in PHP een bignum exponent gemaakt.

Nu heb ik nog de volgende delen nodig: bcmul/bcmod in Javascript, of een bcpowmod (zou helemaal mooi zijn).

Verder een heel ander vraagje:
Hoe zet ik een rij decimale getallen om in text. Bij kleine getallen lukt dat wel (gewoon telkens bitschift 8 doen, dan de huidige waarde &0xFF en dat geheel in chr() stoppen, maar als ik dat doe met een decimale string, dan krijg ik dezelfde decimale string.

[Verwijderd]

Inmiddels is alles in PHP gelukt (encryptie, decryptie, met of zonder grote exponent, het vertalen van een decimale string naar elk willekeurige string, en van string naar decimale string), en bhet is vrijwel allemaal zonder problemen om te zetten naar Javascriptcode, met nog steeds twee uitzonderingen: hoe doen ik bcmul/bcmod in Javascript?

Iemand ideeen?

[Verwijderd]

Heb wat zitten rondlezen rondom Fast Fourier Transformatie, maar daar ben ik nog niet uit. Dus zowieso alle hulp blijft welkom voor een snelle multilpier en modulus in javascript (of meteen een power/modulus), zolang hij maar snel is en om kan met reuzachtige getallen.

[kris_112]

Ik weet absoluut niks van programmeren in javascript, dus ik heb geen idee of dit makkelijk te implementeren is in js, maar een snelle pow-functie is niet eens zo heel erg lastig te maken. Stel je wilt uitrekenen x^140.
Binair is dit x^10001100.
Dit is hetzelfde als x^10000000 * x^1000 * x^100 (nog steeds binair he)
De drie overgebleven machten zijn nu simpele bitshifts en je houdt nog slechts 3 vermenigvuldigingen over. Bij getallen met 100 cijfers zijn dit dan maximaal ca 350 vermenigvuldigingen.

Uitbreiden tot een modpow functie is ook geen probleem aangezien je de modulus-functie overal in je berekening tussen kunt zetten en het uiteindelijke resultaat hetzelfde blijft. Dus in bovenstaand voorbeeld levert (x^10000000 * x^1000 * x^100) mod Z hetzelfde op als
[[ (x^10000000 mod Z) * (x^1000 mod Z) ] mod Z * (x^100 mod Z)] mod Z
De poging om overzichtelijk te blijven door verschillende soorten haakjes te gebruiken is jammerlijk mislukt

Met andere woorden, zodra je ergens halverwege je berekening boven de Z uitkomt kun je hier weer een veelvoud van Z van aftrekken zonder het uiteindelijke resultaat te beinvloeden.

[Verwijderd]

thaRealKris schreef op zondag 12 juni 2005 @ 16:17:... verhaal ...

Het grote probleem is:
Een powerfunctie is niet zo moelijk, een modpow ook niet, maar javascript kent geen extreem grote getallen aan. Een algoritme voor de berekening heb ik dus al (zie onder voor pseudocode), en heb het ook al helemaal draaiend in PHP, het probleem is alleen dat javascript geen ingebakken super-maal en super-modulus heeftm waardoor ik beperkt ben tot 32/64 bits grote getallen, terwijl de getallen waarmee gerekent gaat worden zo ongeveer het 8 tot 16 voudige daarvan zijn (512 tot 1024 bits minimaal). En dat weet ik dus nog nie hoe dat moet (in JS dan).

code:

Bignum modpow(Bignum b, Bignum e, Bignum m) {

   Bignum result = 1;

   while (e > 0) {
      if (e & 1 > 0) result = (result * b) % m;
      e >>= 1;
      b = (b * b) % m;
   }

   return result;
}

en nogmaals: Een idee van de te gebruiken getallen (grote, minimaal, decimaal, 512bits):

code:

De modulus: 
791584609555246655067796814738636793790133773628262491708442170176454951008522619671145653216387461589922503399945357877560697894314935509698918299079867

De exponent waarmee versleuteld word:
714230201003899540152651109706371801059095441396196900217125652795269502831399373188517888486117352563790514451397083005974283339883367064999829807231427

De exponent waarmee ontsleuteld word: 101160001648006692063570713465818228891939038704656200838553928003462416251985445065154139226534016052397504883366058699554392879536544088947010730304803

En met die getallen werken, kan niet standaard in JS, dat is nu nog het eenigste probleem
En als dus iemand weet hoe maal en mod moet met zo'n getal in JS, of een idee heeft...

[brokenp]

even zoeken met google naar bigint en javascript levert deze site op:
http://www.leemon.com/crypto/BigInt.html

Met een speciale bigint.js classe

[Verwijderd]

brokenp schreef op zondag 12 juni 2005 @ 17:57:
even zoeken met google naar bigint en javascript levert deze site op:
http://www.leemon.com/crypto/BigInt.html

Met een speciale bigint.js classe

Klopt inderdaad, word ook genoemd in mijn startpost, precies ehetzelfde voorbeeld, maar ik snap niet echt veel van de achterliggende werking van die code.

[brokenp]

Wat begrijp je niet?
Ik denk dat het verstandig is om zelf een bigint library te implemeneteren. Om een representatie te hebben voor deze integers zou ik dezelfde manier gebruiken als op leemon.com
dus:

// This code defines a bigInt library for arbitrary-precision integers.
// A bigInt is an array of integers storing the value in chunks of bpe bits,
// little endian (buff[0] is the least significant word).
// Negative bigInts are stored two's complement.

VB:
stel bpe=8 dan is elke cel in de array een waarde tussen uit [0,256)
Dus als we het getal 10000 op willen slaan, dan doen we dit door
BI[2]=0 //10000 div 256*256
BI[1]=39 //(10000 mod 256*256) div 256
BI[0]=16 //(10000 mod 256*256) mod 256

Oftwel cel2 wordt gevuld met het hoevaak 256*256 erin past, cel1 met hoevaak 256 erinpast etc

256*39+16=10000
10000 is in bigint representatie met bpe=8 is 16,39,0,0...0

Als je met deze insteek probeert om modpow te berekenen, zal je de code van Leemon gaan begrijpen denk ik...