elgamal decryption in javascript

Question

I have no experience with cryptography, but, since no one else is answering, I'll give it a shot.

Your question didn't quite make sense to me the way it was phrased, so I decided to implement a complete Elgamal in JavaScript so that I could understand your problem in context. Here's what I came up with:

// Abstract:

var Alphabet = "!\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~ \nπ®ƒ©∆";

Alphabet = Alphabet.split("");

var Crypto = function (alpha, gen, C) {
    var p, B, encrypt, decrypt, f, g, modInv, modPow, toAlpha, to10;
    toAlpha = function (x) {
        var y, p, l, n;
        if (x === 0) {
            return "!!!!";
        }
        y = [];
        n = 4;
        n = Math.ceil(n);
        while (n--) {
            p = Math.pow(alpha.length, n);
            l = Math.floor(x / p);
            y.push(alpha[l]);
            x -= l * p;
        }
        y = y.join("");
        return y;
    };
    to10 = function (x) {
        var y, p, n;
        y = 0;
        p = 1;
        x = x.split("");
        n = x.length;
        while (n--) {
            y += alpha.indexOf(x[n]) * p;
            p *= alpha.length;
        }
        return y;
    };
    modInv = function (gen, mod) {
        var v, d, u, t, c, q;
        v = 1;
        d = gen;
        t = 1;
        c = mod % gen;
        u = Math.floor(mod / gen);
        while (d > 1) {
            q = Math.floor(d / c);
            d = d % c;
            v = v + q * u;
            if (d) {
                q = Math.floor(c / d);
                c = c % d;
                u = u + q * v;
            }
        }
        return d ? v : mod - u;
    };
    modPow = function (base, exp, mod) {
        var c, x;
        if (exp === 0) {
            return 1;
        } else if (exp < 0) {
            exp = -exp;
            base = modInv(base, mod);
        }
        c = 1;
        while (exp > 0) {
            if (exp % 2 === 0) {
                base = (base * base) % mod;
                exp /= 2;
            } else {
                c = (c * base) % mod;
                exp--;
            }
        }
        return c;
    };
    p = 91744613;
    C = parseInt(C, 10);
    if (isNaN(C)) {
        C = Math.round(Math.sqrt(Math.random() * Math.random()) * (p - 2) + 2);
    }
    B = modPow(gen, C, p);
    decrypt = function (a) {
        var d, x, y;
        x = a[1];
        y = modPow(a[0], -C, p);
        d = (x * y) % p;
        d = Math.round(d) % p;
        return alpha[d - 2];
    };
    encrypt = function (key, d) {
        var k, a;
        k = Math.ceil(Math.sqrt(Math.random() * Math.random()) * 1E10);
        d = alpha.indexOf(d) + 2;
        a = [];
        a[0] = modPow(key[1], k, key[0]);
        a[1] = (d * modPow(key[2], k, key[0])) % key[0];
        return a;
    };
    f = function (message, key) {
        var n, x, y, w;
        y = [];
        message = message.split("");
        n = message.length;
        while (n--) {
            x = encrypt(key, message[n]);
            y.push(toAlpha(x[0]));
            y.push(toAlpha(x[1]));
        }
        y = y.join("");
        return y;
    };
    g = function (message) {
        var n, m, d, x;
        m = [];
        n = message.length / 8;
        while (n--) {
            x = message[8 * n + 4];
            x += message[8 * n + 5];
            x += message[8 * n + 6];
            x += message[8 * n + 7];
            m.unshift(x);
            x = message[8 * n];
            x += message[8 * n + 1];
            x += message[8 * n + 2];
            x += message[8 * n + 3];
            m.unshift(x);
        }
        x = [];
        d = [];
        n = m.length / 2;
        while (n--) {
            x[0] = m[2 * n];
            x[1] = m[2 * n + 1];
            x[0] = to10(x[0]);
            x[1] = to10(x[1]);
            d.push(decrypt(x));
        }
        message = d.join("");
        return message;
    };
    return {
        pubKey: [p, gen, B],
        priKey: C,
        decrypt: g,
        encrypt: f
    };
};

// Usage:

var Alice = Crypto(Alphabet, 69);

var Bob = Crypto(Alphabet, 69);

var message = "Hello!";
console.log(message);
// "Hello!"

message = Alice.encrypt(message, Bob.pubKey);
print(message);
// "Pl)7t&rfGueuL@|)H'P,*<K\.hxw+∆d*`?Io)lg~Adz-6xrR" or something like it.

message = Bob.decrypt(message);
console.log(message);
// "Hello!"

So, basically, Crypto handles all of the Elgamal algorithms, using modPow when it needs to. I think that the modPow function was what you were originally after, wasn't it? The version that you originally posted uses repeated squaring instead of ordinary exponentiation, presumably for purposes of performance, but they're both reasonably speedy.

It still isn't clear to me, though, why you needed a different algorithm for doing "m = a. b ^(p-1-x) mod p". I never needed anything like that in implementing my Elgamal, so I'm not sure what this corresponds to. I did need to implement a function that calculates the modular multiplicative inverse, which I called modInv. Is that what you wanted? I used a stripped-down version of the Extended Euclidean Algorithm to make it.

If it helps, feel free to copy part or all of my code for your project.

And, if you have any more questions about this, please ask me!

EDIT: Note, this code is not intended for actual production-grade encryption. It is really just a proof of concept for the algorithm. With a little work, however, it could be made more secure. Let me know.

EDIT: To encrypt and decrypt text, do the following:

Create a new Crypto object to encrypt the text, and then save it:

var Alice=Crypto(Alphabet, 69);

Here, Alice is just some variable, Alphabet is the 29-symbol alphabet that I defined at the top of the code, and 69 is a primitive root mod 91744613.

Then, create another Crypto object to decrypt the text, and then save it:

var Bob=Crypto(Alphabet, 69);

Although Bob was created in the same way as Alice, they are different objects. Bob cannot decrypt text intended for Alice, and Alice cannot decrypt text intended for Bob.

Now, use Alice's encrypt method to encrypt some text, and save the result:

var codedMessage=Alice.encrypt("HELLO, WORLD.", Bob.pubKey);

Here, message is an empty variable, "HELLO, WORLD." is the text to be encrypted (or the contents of a text file). Bob.key is Bob's public key. We must use Bob's key in the encryption so that Bob (and only Bob) can decrypt the text. The resulting encrypted text will look something like this: "Pl)7t&rfGueuL@|)H'P,*<K\.hxw+∆d*?Io)lg~Adz-6xrR"`. Note that even with the same message, different output will be generated each time. It will still always decrypt to the same value.

Now, in theory, we can send this encrypted text over whatever un-secure channel we want, and no one will be able to decode it. When Bob receives the encrypted text, however, he can decode it. To do this:

var plainMessage=Bob.decrypt(codedMessage);

Now, plainMessage will contain the text "HELLO, WORLD.", which you can read or do whatever you want with.

So, all together, just these four lines will do it:

var Alice=Crypto(Alphabet, 69);
var Bob=Crypto(Alphabet, 69);
var codedMessage=Alice.encrypt("HELLO, WORLD.", Bob.pubKey);
var plainMessage=Bob.decrypt(codedMessage);

// Now, plainMessage contains "HELLO, WORLD."

If you specifically want to do this with text files, then you can either copy-and-paste the contents into the javascript, or you can look into loading the contents of a text file into javascript. To get started, see this SO, and this HG.