/*
 * Encrypt E-mail JavaScript Library
 *
 * Copyright (C) 2007 Alexander Kiel
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */

//---------------------------------------------------------------------------------------------
// CryptedEmail
//---------------------------------------------------------------------------------------------

var EncryptedEmail = Class.create({

// Constructor
    initialize : function(cssClassName) {

        if (cssClassName) {
            this.cssClassName = cssClassName;
        } else {
            this.cssClassName = "encrypted-email";
        }

        // RSA Cryption object place holder (set it with setRSA)
        this.rsa = EncryptedEmail.getDefaultRSA512();

        // Default button
        this.decryptButton = new DecryptButton("show", "Please click to show the e-mail as link.");

        // Default all button
        this.decryptAllButton = new DecryptAllButton("show all", "Please click to show all the e-mails as link.");

        this.ciphertextAccessor = new AttributeCiphertextAccessor("ciphertext");

        // Default e-mail link title
        this.linkTitle = "Click to send an e-mail.";

        // array of known encrypted email elements
        this.encryptedEmailElements = new Array();

        var instance = this;

        this.addEvent(window, 'load', function() {
            instance.replaceDOM();
        });
    },

    setRSA : function(rsa) {
        this.rsa = rsa;
    },

    setDecryptButton : function(decryptButton) {
        this.decryptButton = decryptButton;
    },

    setCiphertextAccessor : function(ciphertextAccessor) {
        this.ciphertextAccessor = ciphertextAccessor;
    },

    setLinkTitle : function(linkTitle) {
        this.linkTitle = linkTitle;
    },

    registerCiphertext : function(emailId, ciphertext) {
        var encryptedEmailElement = document.getElementById(emailId);
        if (encryptedEmailElement) {
            encryptedEmailElement.setAttribute("ciphertext", ciphertext);
        }
    },

    getEncryptedEmailElements : function() {
        return this.encryptedEmailElements;
    },

// (private)
    replaceDOM : function() {

        // Check for DOM support
        if (!document.getElementsByTagName || !document.createTextNode || !document.getElementsByClassName) {
            return;
        }

        var decryptAllButtons = new Array();

        // Process all html elements (tags) with our cssClassName
        var encryptedEmailElements = document.getElementsByClassName(this.cssClassName, null);
        for (var i = 0; i < encryptedEmailElements.length; i++) {
            var encryptedEmailElement = encryptedEmailElements[i];

            // The actual email element
            if (encryptedEmailElement.hasClassName("email")) {

                var ciphertext = this.ciphertextAccessor.getCiphertext(encryptedEmailElement);

                // TODO: else warning?
                if (ciphertext != null) {

                    // Register the ciphertext
                    encryptedEmailElement.setAttribute("ciphertext", ciphertext);
                    this.encryptedEmailElements.push(encryptedEmailElement);

                    if (!encryptedEmailElement.hasClassName("no-button")) {

                        // Create a button for this e-mail
                        var button = this.decryptButton.createButton(this, encryptedEmailElement);

                        // Insert the button into the e-mail span-element
                        if (button != null) {
                            var space = document.createTextNode(" ");
                            encryptedEmailElement.appendChild(space);
                            encryptedEmailElement.appendChild(button);
                        }
                    }
                }

            } else if (encryptedEmailElement.hasClassName("decrypt-all-button")) {
                decryptAllButtons.push(encryptedEmailElement);
            } else if (encryptedEmailElement.hasClassName("remove")) {
                encryptedEmailElement.parentNode.removeChild(encryptedEmailElement);
            } else if (encryptedEmailElement.hasClassName("encrypter")) {
                if (encryptedEmailElement.tagName.toLowerCase() == "div") {
                    this.buildEncrypter(encryptedEmailElement);
                }
            } else if (encryptedEmailElement.hasClassName("keygen")) {
                if (encryptedEmailElement.tagName.toLowerCase() == "div") {
                    this.buildKeygen(encryptedEmailElement);
                }
            }
        }

        // Iterate through all previously remembered buttons
        for (i = 0; i < decryptAllButtons.length; i++) {
            var decryptAllButton = decryptAllButtons[i];

            // Create a button for this e-mail
            var allButton = this.decryptAllButton.createButton(this, this.getEncryptedEmailElements());

                // Insert the button into the element
            if (allButton != null) {
                if (decryptAllButton.childNodes.length > 0) {
                    var allSpace = document.createTextNode(" ");
                    decryptAllButton.appendChild(allSpace);
                }
                decryptAllButton.appendChild(allButton);
            }
        }
    },

    buildEncrypter : function(encryptedEmailElement) {

        // Create the text input
        var cleartextInput = document.createElement("input");
        cleartextInput.setAttribute("type", "text");
        cleartextInput.setAttribute("size", "57");

        // Create the output textarea
        var ciphertextOutput = document.createElement("textarea");
        ciphertextOutput.setAttribute("cols", "70");
        ciphertextOutput.setAttribute("rows", "5");

        // Create the button
        var button = document.createElement("button");
        button.setAttribute("type", "button");
        button.appendChild(document.createTextNode("encrypt"));

        var instance = this;
        button.onclick = function() {
            instance.encrypt(cleartextInput, ciphertextOutput, 64);
        };

        var p1 = document.createElement("p");
        p1.setAttribute("class", "input");
        p1.appendChild(cleartextInput);
        p1.appendChild(document.createTextNode(" "));
        p1.appendChild(button);

        var p2 = document.createElement("p");
        p2.setAttribute("class", "output");
        p2.appendChild(ciphertextOutput);

        // Remove all childrens
        while (encryptedEmailElement.hasChildNodes()) {
            encryptedEmailElement.removeChild(encryptedEmailElement.firstChild);
        }

        // Add the text input and the button
        encryptedEmailElement.appendChild(p1);
        encryptedEmailElement.appendChild(p2);
    },

    buildKeygen : function(encryptedEmailElement) {

        var bitDepthLabel = document.createElement("label");
        bitDepthLabel.setAttribute("for", "rsa-keygen-bit-depth");
        bitDepthLabel.appendChild(document.createTextNode("Bit depth:"));

        // Create the bit depth text input
        var bitDepthInput = document.createElement("input");
        bitDepthInput.setAttribute("id", "rsa-keygen-bit-depth");
        bitDepthInput.setAttribute("type", "text");
        bitDepthInput.setAttribute("size", "5");

        var pubExpLabel = document.createElement("label");
        pubExpLabel.setAttribute("for", "rsa-keygen-pub-exp");
        pubExpLabel.appendChild(document.createTextNode("Public exponent (hex):"));

        // Create the public exponent text input
        var pubExpInput = document.createElement("input");
        pubExpInput.setAttribute("id", "rsa-keygen-pub-exp");
        pubExpInput.setAttribute("type", "text");
        pubExpInput.setAttribute("size", "5");

        var rsaCryptLabel = document.createElement("label");
        rsaCryptLabel.setAttribute("for", "rsa-keygen-rsa-crypt");
        rsaCryptLabel.appendChild(document.createTextNode("RSACrypt Setter:"));

        // Create the RSACrypt textarea
        var rsaCryptOutput = document.createElement("textarea");
        rsaCryptOutput.setAttribute("id", "rsa-keygen-rsa-crypt");
        rsaCryptOutput.setAttribute("readonly", "readonly");
        rsaCryptOutput.setAttribute("cols", "70");
        rsaCryptOutput.setAttribute("rows", "12");

        // Create the button
        var button = document.createElement("button");
        button.setAttribute("type", "button");
        button.appendChild(document.createTextNode("generate"));

        var instance = this;
        button.onclick = function() {
            instance.generate(bitDepthInput, pubExpInput, rsaCryptOutput, 64);
        };

        var p1 = document.createElement("p");
        p1.setAttribute("class", "input");
        p1.appendChild(bitDepthLabel);
        p1.appendChild(document.createTextNode(" "));
        p1.appendChild(bitDepthInput);
        p1.appendChild(document.createTextNode(" "));
        p1.appendChild(pubExpLabel);
        p1.appendChild(document.createTextNode(" "));
        p1.appendChild(pubExpInput);
        p1.appendChild(document.createTextNode(" "));
        p1.appendChild(button);

        // Remove all childs
        while (encryptedEmailElement.hasChildNodes()) {
            encryptedEmailElement.removeChild(encryptedEmailElement.firstChild);
        }

        // Add the text input and the button
        encryptedEmailElement.appendChild(p1);
        encryptedEmailElement.appendChild(this.wrapWithParagraph(rsaCryptLabel));
        encryptedEmailElement.appendChild(this.wrapWithParagraph(rsaCryptOutput));
    },

// (private)
    wrapWithParagraph : function(element) {
        var p = document.createElement("p");
        p.appendChild(element);
        return p;
    },

// (public)
    encrypt : function(cleartextInput, ciphertextOutput, width) {
        var value = cleartextInput.value;
        if (value) {
            var result = this.rsa.encrypt(value);
            if (result) {
                ciphertextOutput.value = this.linebrk(result, width);
            }
        }
    },

// (public)
    decrypt : function(encryptedEmailElement, button) {

        var debug = encryptedEmailElement.hasClassName("debug");
        var ciphertext = encryptedEmailElement.getAttribute("ciphertext");
        var before;

        if (debug) {
            before = new Date();
        }

        // Decrypt the ciphertext
        var email = this.rsa.decrypt(ciphertext);

        // Create a hyperlink for the email
        var link = document.createElement("a");
        link.setAttribute("id", encryptedEmailElement.getAttribute("id"));
        link.setAttribute("class", encryptedEmailElement.getAttribute("class"));
        link.setAttribute("href", "mailto:" + email);
        link.setAttribute("title", this.linkTitle);
        link.appendChild(document.createTextNode(email));

        // Replace the span element of the text email with the new hyperlink
        encryptedEmailElement.parentNode.replaceChild(link, encryptedEmailElement);

        if (debug) {
            var duration = (new Date() - before);
            link.appendChild(document.createTextNode(" (duration: " + duration + " ms)"));
        }
    },

// (public)
    decryptAll : function(encryptedEmailElements, button) {
        for (var i = 0; i < encryptedEmailElements.length; i++) {
            this.decrypt(encryptedEmailElements[i], null);
        }
        if (button) {
            button.parentNode.removeChild(button);
        }
    },

// (public)
    generate : function(bitDepthInput, pubExpInput, rsaCryptOutput, width) {
        var bitDepth = bitDepthInput.value;
        var pubExp = pubExpInput.value;
        if (bitDepth && pubExp) {
            var rsa = new RSACrypt();
            rsa.generate(bitDepth, pubExp);

            var tab = '\u00A0\u00A0\u00A0\u00A0';
            var result = "encryptedEmail.setRSA(new RSACrypt(\n";
            result += tab + '"' + rsa.n.toString(16) + '",\n';
            result += tab + '"' + rsa.e.toString(16) + '",\n';
            result += tab + '"' + rsa.d.toString(16) + '",\n';
            result += tab + '"' + rsa.p.toString(16) + '",\n';
            result += tab + '"' + rsa.q.toString(16) + '",\n';
            result += tab + '"' + rsa.dmp1.toString(16) + '",\n';
            result += tab + '"' + rsa.dmq1.toString(16) + '",\n';
            result += tab + '"' + rsa.iqmp.toString(16) + '"\n));\n';
            rsaCryptOutput.value = result;
        }
    },

// (private)
    linebrk : function(s, n) {
        var ret = "";
        var i = 0;
        while (i + n < s.length) {
            ret += s.substring(i, i + n) + "\n";
            i += n;
        }
        return ret + s.substring(i, s.length);
    },

/* addEvent function from http://www.quirksmode.org/blog/archives/2005/10/_and_the_winner_1.html */
    addEvent : function (obj, type, fn) {
        if (obj.addEventListener) {
            obj.addEventListener(type, fn, false);
        } else if (obj.attachEvent) {
            obj["e" + type + fn] = fn;
            obj[type + fn] = function() {
                obj["e" + type + fn](window.event);
            };
            obj.attachEvent("on" + type, obj[type + fn]);
        }
    }
});

EncryptedEmail.getDefaultRSA512 = function() {
    return new RSACrypt(
            "BC86E3DC782C446EE756B874ACECF2A115E613021EAF1ED5EF295BEC2BED899D\n26FE2EC896BF9DE84FE381AF67A7B7CBB48D85235E72AB595ABF8FE840D5F8DB",
            "3",
            "7daf4292fac82d9f44e47af87348a1c0b9440cac1474bf394a1b929d729e5bbc\nf402f29a9300e11b478c091f7e5dacd3f8edae2effe3164d7e0eeada87ee817b",
            "ef3fc61e21867a900e01ee4b1ba69f5403274ed27656da03ed88d7902cce693f",
            "c9b9fcc298b7d1af568f85b50e749539bc01b10a68472fe1302058104821cd65",
            "9f7fd9696baefc6009569edcbd19bf8d576f89e1a439e6ad4905e50ac8899b7f",
            "867bfdd7107a8bca39b503ce09a30e267d567606f02f7540cac03ab5856bde43",
            "412d6b551d93ee1bd7dccafc63d7a6d031fc66035ecc630ddf75f949a378cd9d"
            );
};

EncryptedEmail.getDefaultRSA1024 = function() {
    return new RSACrypt(
            "ABC30681295774F7CECA691EC17F4E762DA6DE70F198EAEE3CCE3A435FC006B9\n71DC24E55904F1D2705758C041C2B0B18E8BFAE2C9CD96B50082D7D8C7342CBA\nB7F6E0622DA53B8B56DBDB24174F00173263CFECAE604795CDA2A037BC3A69B7\nC0090AA2DE1568998BCD6D70CC2E0574755B9F7986AE01CE8714A26144279CDB",
            "3",
            "728204561b8fa34fdf319b69d654def973c4944b4bbb47497dded1823fd559d0\nf692c34390adf68c4ae4e5d5812c75cbb45d51ec86890f2355ac8fe5da22c87b\n62449e2aa754422bc43d3ca32efa866227ad58178e7803897d074f1312740aa7\n61cfc7ed753bb829d7a2ab091289d1676809bfd61276b43bb3a395714f167beb",
            "e200731c6e934a0fdc1d5ce5f66d08ba9478280f46e9cbed777029dd4811a7cd\n4aa66ad8365c5aa67b06b97e54ee8fec03adb2134f7359a427c7ffc468ef0231",
            "c28f8005c4138e39d462a3495a6a2dc96267a3ba11c2765a1aa77fbdd87ab1ef\n62aaf3e677df79b44d52b364db70bb6d559f4da51b8899d0d1d74272e496e0cb",
            "96aaf76849b786b53d68e8994ef35b270da5700a2f4687f3a4f5713e300bc533\n87199c90243d91c452047ba98df45ff2ad1e76b78a4ce66d6fdaaa82f09f56cb",
            "81b50003d80d097be2ec6cdb919c1e86419a6d26b681a43c11c4ffd3e5a7214a\n41c74d444fea5122de3722433cf5d248e3bf8918bd05bbe08be4d6f7430f4087",
            "a318fb95d3b10d6cfb0096fc3a3173377cf0952bf5d50fd3ccf678dd636ca1a1\naeed8da416c8fba4395b00dc3e22823d1b2add8a4e1222d562af11bd6c78ad94"
            );
};

//---------------------------------------------------------------------------------------------
// Buttons
//---------------------------------------------------------------------------------------------

var DecryptButton = Class.create({

    initialize : function(text, title) {
        this.text = text;
        this.title = title;
    },

    createButton : function(encryptedEmail, encryptedEmailElement) {
        var button = document.createElement("button");
        button.setAttribute("type", "button");
        if (this.title != "") {
            button.setAttribute("title", this.title);
        }
        button.appendChild(document.createTextNode(this.text));
        button.onclick = function() {
            encryptedEmail.decrypt(encryptedEmailElement, this);
        };
        return button;
    }
});

var NoOpButton = Class.create({

    initialize : function() {
    },

    createButton : function(encryptedEmail, encryptedEmailElement) {
        return null;
    }
});

var DecryptIconButton = Class.create({

    initialize : function(src, alt, title) {
        this.src = src;
        this.alt = alt;
        this.title = title;
    },

    createButton : function(encryptedEmail, encryptedEmailElement) {
        var button = document.createElement("input");
        button.setAttribute("type", "image");
        button.setAttribute("src", this.src);
        button.setAttribute("alt", this.alt);
        if (this.title != "") {
            button.setAttribute("title", this.title);
        }
        button.onclick = function() {
            encryptedEmail.decrypt(encryptedEmailElement, this);
        };
        return button;
    }
});

var DecryptAllButton = Class.create({

    initialize : function(text, title) {
        this.text = text;
        this.title = title;
    },

    createButton : function(encryptedEmail, encryptedEmailElements) {
        var button = document.createElement("button");
        button.setAttribute("type", "button");
        if (this.title != "") {
            button.setAttribute("title", this.title);
        }
        button.appendChild(document.createTextNode(this.text));
        button.onclick = function() {
            encryptedEmail.decryptAll(encryptedEmailElements, this);
        };
        return button;
    }
});

//---------------------------------------------------------------------------------------------
// CiphertextAccessors
//---------------------------------------------------------------------------------------------

var AttributeCiphertextAccessor = Class.create({

    initialize : function(attributeName) {
        this.attributeName = attributeName;
    },

    prepare : function() {},

    getCiphertext : function(encryptedEmailElement) {
        return encryptedEmailElement.getAttribute(this.attributeName);
    }
});

var HiddenFieldCiphertextAccessor = Class.create({

    initialize : function() {
        this.ciphers = new Object();
    },

    prepare : function() {

        // Get ciphertexts from hidden fields
        this.ciphers = new Object();
        var inputs = document.getElementsByTagName("input");
        for (var i = 0; i < inputs.length; i++) {
            var input = inputs[i];
            if (input.getAttribute("type") == "hidden") {
                var name = input.getAttribute("name");
                var value = input.getAttribute("value");
                if (name && name.length > 0 && value && value.length > 0) {
                    this.ciphers[name] = value;
                }
            }
        }
    },

    getCiphertext : function(encryptedEmailElement) {
        return this.ciphers[encryptedEmailElement.id];
    }
});

//---------------------------------------------------------------------------------------------
// RSACrypt
//---------------------------------------------------------------------------------------------

var RSACrypt = Class.create({

// Constructor
    initialize : function (n, e, d, p, q, dmp1, dmq1, iqmp) {

        if (n != null && e != null) {
            this.n = this.parseBigInt(n, 16);
            this.e = parseInt(e, 16);
        } else {
            this.n = null;
            this.e = 0;
        }

        if (d != null && p != null && q != null && dmp1 != null & dmq1 != null && iqmp != null) {
            this.d = this.parseBigInt(d, 16);
            this.p = this.parseBigInt(p, 16);
            this.q = this.parseBigInt(q, 16);
            this.dmp1 = this.parseBigInt(dmp1, 16);
            this.dmq1 = this.parseBigInt(dmq1, 16);
            this.iqmp = this.parseBigInt(iqmp, 16);
        } else {
            this.d = null;
            this.p = 0;
            this.q = null;
            this.dmp1 = null;
            this.dmq1 = null;
            this.iqmp = null;
        }
    },

// Return the PKCS#1 RSA encryption of "text" as an even-length hex string
    encrypt : function(text) {
        var m = this.pkcs1pad2(text, (this.n.bitLength() + 7) >> 3);
        if (m == null) {
            return null;
        }
        var c = this.doPublic(m);
        if (c == null) {
            return null;
        }
        var h = c.toString(16);
        if ((h.length & 1) == 0) {
            return h;
        } else {
            return "0" + h;
        }
    },

// Return the PKCS#1 RSA decryption of "ctext".
// "ctext" is an even-length hex string and the output is a plain string.
    decrypt : function(ctext) {
        var c = this.parseBigInt(ctext, 16);
        var m = this.doPrivate(c);
        if (m == null) {
            return null;
        }
        return this.pkcs1unpad2(m, (this.n.bitLength() + 7) >> 3);
    },

// Generate a new random private key B bits long, using public expt E
    generate : function(B, E) {
        var rng = new SecureRandom();
        var qs = B >> 1;
        this.e = parseInt(E, 16);
        var ee = new BigInteger(E, 16);
        for (; ;) {

            // Search p
            for (; ;) {
                this.p = new BigInteger(B - qs, 1, rng);
                if (this.p.subtract(BigInteger.ONE).gcd(ee).compareTo(BigInteger.ONE) == 0 &&
                    this.p.isProbablePrime(10)) break;
            }

            // Search q
            for (; ;) {
                this.q = new BigInteger(qs, 1, rng);
                if (this.q.subtract(BigInteger.ONE).gcd(ee).compareTo(BigInteger.ONE) == 0 &&
                    this.q.isProbablePrime(10)) break;
            }

            if (this.p.compareTo(this.q) <= 0) {
                var t = this.p;
                this.p = this.q;
                this.q = t;
            }

            var p1 = this.p.subtract(BigInteger.ONE);
            var q1 = this.q.subtract(BigInteger.ONE);
            var phi = p1.multiply(q1);
            if (phi.gcd(ee).compareTo(BigInteger.ONE) == 0) {
                this.n = this.p.multiply(this.q);
                this.d = ee.modInverse(phi);
                this.dmp1 = this.d.mod(p1);
                this.dmq1 = this.d.mod(q1);
                this.iqmp = this.q.modInverse(this.p);
                break;
            }
        }
    },

// convert a (hex) string to a bignum object
    parseBigInt : function(str, radix) {
        return new BigInteger(str, radix);
    },

// Perform raw public operation on "x": return x^e (mod n)
    doPublic : function(x) {
        return x.modPowInt(this.e, this.n);
    },

// Perform raw private operation on "x": return x^d (mod n)
    doPrivate : function(x) {
        if (this.p == null || this.q == null) {
            return x.modPow(this.d, this.n);
        }

  // TODO: re-calculate any missing CRT params
        var xp = x.mod(this.p).modPow(this.dmp1, this.p);
        var xq = x.mod(this.q).modPow(this.dmq1, this.q);

        while (xp.compareTo(xq) < 0) {
            xp = xp.add(this.p);
        }
        return xp.subtract(xq).multiply(this.iqmp).mod(this.p).multiply(this.q).add(xq);
    },

// PKCS#1 (type 2, random) pad input string s to n bytes, and return a bigint
    pkcs1pad2 : function(s, n) {
        if (n < s.length + 11) {
            alert("Message too long for RSA");
            return null;
        }
        var ba = new Array();
        var i = s.length - 1;
        while (i >= 0 && n > 0) {
            ba[--n] = s.charCodeAt(i--);
        }
        ba[--n] = 0;
        var rng = new SecureRandom();
        var x = new Array();
        while (n > 2) { // random non-zero pad
            x[0] = 0;
            while (x[0] == 0) {
                rng.nextBytes(x);
            }
            ba[--n] = x[0];
        }
        ba[--n] = 2;
        ba[--n] = 0;
        return new BigInteger(ba);
    },

// Undo PKCS#1 (type 2, random) padding and, if valid, return the plaintext
    pkcs1unpad2 : function(d, n) {
        var b = d.toByteArray();
        var i = 0;
        while (i < b.length && b[i] == 0) {
            ++i;
        }
        if (b.length - i != n - 1 || b[i] != 2) {
            return null;
        }
        ++i;
        while (b[i] != 0) {
            if (++i >= b.length) {
                return null;
            }
        }
        var ret = "";
        while (++i < b.length) {
            ret += String.fromCharCode(b[i]);
        }
        return ret;
    }
});

//---------------------------------------------------------------------------------------------
// BigInteger
//---------------------------------------------------------------------------------------------

var BigInteger = Class.create({

// (public) Constructor
    initialize : function(a, b, c) {
        if (a != null) {
            if ("number" == typeof a) {
                this.fromNumber(a, b, c);
            } else if (b == null && "string" != typeof a) {
                this.fromString(a, 256);
            } else {
                this.fromString(a, b);
            }
        }
    },

// am: Compute w_j += (x*this_i), propagate carries,
// c is initial carry, returns final carry.
// c < 3*dvalue, x < 2*dvalue, this_i < dvalue
// We need to select the fastest one that works in this environment.

// am1: use a single mult and divide to get the high bits,
// max digit bits should be 26 because
// max internal value = 2*dvalue^2-2*dvalue (< 2^53)
    am1 : function(i, x, w, j, c, n) {
        while (--n >= 0) {
            var v = x * this[i++] + w[j] + c;
            c = Math.floor(v / 0x4000000);
            w[j++] = v & 0x3ffffff;
        }
        return c;
    },

// am2 avoids a big mult-and-extract completely.
// Max digit bits should be <= 30 because we do bitwise ops
// on values up to 2*hdvalue^2-hdvalue-1 (< 2^31)
    am2 : function(i, x, w, j, c, n) {
        var xl = x & 0x7fff, xh = x >> 15;
        while (--n >= 0) {
            var l = this[i] & 0x7fff;
            var h = this[i++] >> 15;
            var m = xh * l + h * xl;
            l = xl * l + ((m & 0x7fff) << 15) + w[j] + (c & 0x3fffffff);
            c = (l >>> 30) + (m >>> 15) + xh * h + (c >>> 30);
            w[j++] = l & 0x3fffffff;
        }
        return c;
    },

// Alternately, set max digit bits to 28 since some
// browsers slow down when dealing with 32-bit numbers.
    am3 : function(i, x, w, j, c, n) {
        var xl = x & 0x3fff, xh = x >> 14;
        while (--n >= 0) {
            var l = this[i] & 0x3fff;
            var h = this[i++] >> 14;
            var m = xh * l + h * xl;
            l = xl * l + ((m & 0x3fff) << 14) + w[j] + c;
            c = (l >> 28) + (m >> 14) + xh * h;
            w[j++] = l & 0xfffffff;
        }
        return c;
    },

    int2char : function(n) {
        return BigInteger.BI_RM.charAt(n);
    },

    intAt : function(s, i) {
        var c = BigInteger.BI_RC[s.charCodeAt(i)];
        return (c == null) ? -1 : c;
    },

// returns bit length of the integer x
    nbits : function(x) {
        var r = 1, t;
        if ((t = x >>> 16) != 0) {
            x = t;
            r += 16;
        }
        if ((t = x >> 8) != 0) {
            x = t;
            r += 8;
        }
        if ((t = x >> 4) != 0) {
            x = t;
            r += 4;
        }
        if ((t = x >> 2) != 0) {
            x = t;
            r += 2;
        }
        if ((t = x >> 1) != 0) {
            x = t;
            r += 1;
        }
        return r;
    },

// (protected) copy this to r
    copyTo : function(r) {
        for (var i = this.t - 1; i >= 0; --i) {
            r[i] = this[i];
        }
        r.t = this.t;
        r.s = this.s;
    },

// (protected) set from integer value x, -DV <= x < DV
    fromInt : function (x) {
        this.t = 1;
        this.s = (x < 0) ? -1 : 0;
        if (x > 0) {
            this[0] = x;
        } else if (x < -1) {
            this[0] = x + this.DV;
        } else {
            this.t = 0;
        }
    },

// (protected) set from string and radix
    fromString : function(s, b) {
        var k;
        if (b == 16) {
            k = 4;
        } else if (b == 8) {
            k = 3;
        } else if (b == 256) {
            k = 8; // byte array
        } else if (b == 2) {
            k = 1;
        } else if (b == 32) {
            k = 5;
        } else if (b == 4) {
            k = 2;
        } else {
            this.fromRadix(s, b);
            return;
        }
        this.t = 0;
        this.s = 0;
        var i = s.length, mi = false, sh = 0;
        while (--i >= 0) {
            var x = (k == 8) ? s[i] & 0xff : this.intAt(s, i);
            if (x < 0) {
                if (s.charAt(i) == "-") {
                    mi = true;
                }
                continue;
            }
            mi = false;
            if (sh == 0) {
                this[this.t++] = x;
            } else if (sh + k > this.DB) {
                this[this.t - 1] |= (x & ((1 << (this.DB - sh)) - 1)) << sh;
                this[this.t++] = (x >> (this.DB - sh));
            } else {
                this[this.t - 1] |= x << sh;
            }
            sh += k;
            if (sh >= this.DB) {
                sh -= this.DB;
            }
        }
        if (k == 8 && (s[0] & 0x80) != 0) {
            this.s = -1;
            if (sh > 0) {
                this[this.t - 1] |= ((1 << (this.DB - sh)) - 1) << sh;
            }
        }
        this.clamp();
        if (mi) {
            BigInteger.ZERO.subTo(this, this);
        }
    },

// (protected) clamp off excess high words
    clamp : function() {
        var c = this.s & this.DM;
        while (this.t > 0 && this[this.t - 1] == c) {
            --this.t;
        }
    },

// (public) return string representation in given radix
    toString : function(radix) {
        if (this.s < 0) {
            return "-" + this.negate().toString(radix);
        }
        var k;
        if (radix == 16) {
            k = 4;
        } else if (radix == 8) {
            k = 3;
        } else if (radix == 2) {
            k = 1;
        } else if (radix == 32) {
            k = 5;
        } else if (radix == 4) {
            k = 2;
        } else {
            return this.toRadix(radix);
        }
        var km = (1 << k) - 1, d, m = false, r = "", i = this.t;
        var p = this.DB - (i * this.DB) % k;
        if (i-- > 0) {
            if (p < this.DB && (d = this[i] >> p) > 0) {
                m = true;
                r = this.int2char(d);
            }
            while (i >= 0) {
                if (p < k) {
                    d = (this[i] & ((1 << p) - 1)) << (k - p);
                    d |= this[--i] >> (p += this.DB - k);
                } else {
                    d = (this[i] >> (p -= k)) & km;
                    if (p <= 0) {
                        p += this.DB;
                        --i;
                    }
                }
                if (d > 0) {
                    m = true;
                }
                if (m) {
                    r += this.int2char(d);
                }
            }
        }
        return m ? r : "0";
    },

// (public) -this
    negate : function() {
        var r = BigInteger.nbi();
        BigInteger.ZERO.subTo(this, r);
        return r;
    },

// (public) |this|
    abs : function() {
        return (this.s < 0) ? this.negate() : this;
    },

// (public) return + if this > a, - if this < a, 0 if equal
    compareTo : function(a) {
        var r = this.s - a.s;
        if (r != 0) {
            return r;
        }
        var i = this.t;
        r = i - a.t;
        if (r != 0) {
            return r;
        }
        while (--i >= 0) {
            if ((r = this[i] - a[i]) != 0) {
                return r;
            }
        }
        return 0;
    },

// (public) return the number of bits in "this"
    bitLength : function() {
        if (this.t <= 0) {
            return 0;
        }
        return this.DB * (this.t - 1) + this.nbits(this[this.t - 1] ^ (this.s & this.DM));
    },

// (protected) r = this << n*DB
    dlShiftTo : function(n, r) {
        var i;
        for (i = this.t - 1; i >= 0; --i) {
            r[i + n] = this[i];
        }
        for (i = n - 1; i >= 0; --i) {
            r[i] = 0;
        }
        r.t = this.t + n;
        r.s = this.s;
    },

// (protected) r = this >> n*DB
    drShiftTo : function(n, r) {
        for (var i = n; i < this.t; ++i) {
            r[i - n] = this[i];
        }
        r.t = Math.max(this.t - n, 0);
        r.s = this.s;
    },

// (protected) r = this << n
    lShiftTo : function(n, r) {
        var bs = n % this.DB;
        var cbs = this.DB - bs;
        var bm = (1 << cbs) - 1;
        var ds = Math.floor(n / this.DB), c = (this.s << bs) & this.DM, i;
        for (i = this.t - 1; i >= 0; --i) {
            r[i + ds + 1] = (this[i] >> cbs) | c;
            c = (this[i] & bm) << bs;
        }
        for (i = ds - 1; i >= 0; --i) {
            r[i] = 0;
        }
        r[ds] = c;
        r.t = this.t + ds + 1;
        r.s = this.s;
        r.clamp();
    },

// (protected) r = this >> n
    rShiftTo : function(n, r) {
        r.s = this.s;
        var ds = Math.floor(n / this.DB);
        if (ds >= this.t) {
            r.t = 0;
            return;
        }
        var bs = n % this.DB;
        var cbs = this.DB - bs;
        var bm = (1 << bs) - 1;
        r[0] = this[ds] >> bs;
        for (var i = ds + 1; i < this.t; ++i) {
            r[i - ds - 1] |= (this[i] & bm) << cbs;
            r[i - ds] = this[i] >> bs;
        }
        if (bs > 0) {
            r[this.t - ds - 1] |= (this.s & bm) << cbs;
        }
        r.t = this.t - ds;
        r.clamp();
    },

// (protected) r = this - a
    subTo : function(a, r) {
        var i = 0, c = 0, m = Math.min(a.t, this.t);
        while (i < m) {
            c += this[i] - a[i];
            r[i++] = c & this.DM;
            c >>= this.DB;
        }
        if (a.t < this.t) {
            c -= a.s;
            while (i < this.t) {
                c += this[i];
                r[i++] = c & this.DM;
                c >>= this.DB;
            }
            c += this.s;
        } else {
            c += this.s;
            while (i < a.t) {
                c -= a[i];
                r[i++] = c & this.DM;
                c >>= this.DB;
            }
            c -= a.s;
        }
        r.s = (c < 0) ? -1 : 0;
        if (c < -1) {
            r[i++] = this.DV + c;
        } else if (c > 0) {
            r[i++] = c;
        }
        r.t = i;
        r.clamp();
    },

// (protected) r = this * a, r != this,a (HAC 14.12)
// "this" should be the larger one if appropriate.
    multiplyTo : function(a, r) {
        var x = this.abs(), y = a.abs();
        var i = x.t;
        r.t = i + y.t;
        while (--i >= 0) {
            r[i] = 0;
        }
        for (i = 0; i < y.t; ++i) {
            r[i + x.t] = x.am(0, y[i], r, i, 0, x.t);
        }
        r.s = 0;
        r.clamp();
        if (this.s != a.s) {
            BigInteger.ZERO.subTo(r, r);
        }
    },

// (protected) r = this^2, r != this (HAC 14.16)
    squareTo : function(r) {
        var x = this.abs();
        var i = r.t = 2 * x.t;
        while (--i >= 0) {
            r[i] = 0;
        }
        for (i = 0; i < x.t - 1; ++i) {
            var c = x.am(i, x[i], r, 2 * i, 0, 1);
            if ((r[i + x.t] += x.am(i + 1, 2 * x[i], r, 2 * i + 1, c, x.t - i - 1)) >= x.DV) {
                r[i + x.t] -= x.DV;
                r[i + x.t + 1] = 1;
            }
        }
        if (r.t > 0) {
            r[r.t - 1] += x.am(i, x[i], r, 2 * i, 0, 1);
        }
        r.s = 0;
        r.clamp();
    },

// (protected) divide this by m, quotient and remainder to q, r (HAC 14.20)
// r != q, this != m.  q or r may be null.
    divRemTo : function(m, q, r) {
        var pm = m.abs();
        if (pm.t <= 0) {
            return;
        }
        var pt = this.abs();
        if (pt.t < pm.t) {
            if (q != null) {
                q.fromInt(0);
            }
            if (r != null) {
                this.copyTo(r);
            }
            return;
        }
        if (r == null) {
            r = BigInteger.nbi();
        }
        var y = BigInteger.nbi(), ts = this.s, ms = m.s;
        var nsh = this.DB - this.nbits(pm[pm.t - 1]);	// normalize modulus
        if (nsh > 0) {
            pm.lShiftTo(nsh, y);
            pt.lShiftTo(nsh, r);
        } else {
            pm.copyTo(y);
            pt.copyTo(r);
        }
        var ys = y.t;
        var y0 = y[ys - 1];
        if (y0 == 0) {
            return;
        }
        var yt = y0 * (1 << this.F1) + ((ys > 1) ? y[ys - 2] >> this.F2 : 0);
        var d1 = this.FV / yt, d2 = (1 << this.F1) / yt, e = 1 << this.F2;
        var i = r.t, j = i - ys, t = (q == null) ? BigInteger.nbi() : q;
        y.dlShiftTo(j, t);
        if (r.compareTo(t) >= 0) {
            r[r.t++] = 1;
            r.subTo(t, r);
        }
        BigInteger.ONE.dlShiftTo(ys, t);
        t.subTo(y, y); // "negative" y so we can replace sub with am later
        while (y.t < ys) {
            y[y.t++] = 0;
        }
        while (--j >= 0) {
            // Estimate quotient digit
            var qd = (r[--i] == y0) ? this.DM : Math.floor(r[i] * d1 + (r[i - 1] + e) * d2);
            if ((r[i] += y.am(0, qd, r, j, 0, ys)) < qd) {    // Try it out
                y.dlShiftTo(j, t);
                r.subTo(t, r);
                while (r[i] < --qd) {
                    r.subTo(t, r);
                }
            }
        }
        if (q != null) {
            r.drShiftTo(ys, q);
            if (ts != ms) {
                BigInteger.ZERO.subTo(q, q);
            }
        }
        r.t = ys;
        r.clamp();
        if (nsh > 0) {
            r.rShiftTo(nsh, r); // Denormalize remainder
        }
        if (ts < 0) {
            BigInteger.ZERO.subTo(r, r);
        }
    },

// (public) this mod a
    mod : function(a) {
        var r = BigInteger.nbi();
        this.abs().divRemTo(a, null, r);
        if (this.s < 0 && r.compareTo(BigInteger.ZERO) > 0) {
            a.subTo(r, r);
        }
        return r;
    },

// (protected) return "-1/this % 2^DB"; useful for Mont. reduction
// justification:
//         xy == 1 (mod m)
//         xy =  1+km
//   xy(2-xy) = (1+km)(1-km)
// x[y(2-xy)] = 1-k^2m^2
// x[y(2-xy)] == 1 (mod m^2)
// if y is 1/x mod m, then y(2-xy) is 1/x mod m^2
// should reduce x and y(2-xy) by m^2 at each step to keep size bounded.
// JS multiply "overflows" differently from C/C++, so care is needed here.
    invDigit : function() {
        if (this.t < 1) {
            return 0;
        }
        var x = this[0];
        if ((x & 1) == 0) {
            return 0;
        }
        var y = x & 3; // y == 1/x mod 2^2
        y = (y * (2 - (x & 0xf) * y)) & 0xf;    // y == 1/x mod 2^4
        y = (y * (2 - (x & 0xff) * y)) & 0xff;  // y == 1/x mod 2^8
        y = (y * (2 - (((x & 0xffff) * y) & 0xffff))) & 0xffff; // y == 1/x mod 2^16
        // last step - calculate inverse mod DV directly;
        // assumes 16 < DB <= 32 and assumes ability to handle 48-bit ints
        y = (y * (2 - x * y % this.DV)) % this.DV;  // y == 1/x mod 2^dbits
        // we really want the negative inverse, and -DV < y < DV
        return (y > 0) ? this.DV - y : -y;
    },

// (protected) true iff this is even
    isEven : function() {
        return ((this.t > 0) ? (this[0] & 1) : this.s) == 0;
    },

// (protected) this^e, e < 2^32, doing sqr and mul with "r" (HAC 14.79)
    exp : function(e, z) {
        if (e > 0xffffffff || e < 1) {
            return BigInteger.ONE;
        }
        var r = BigInteger.nbi(), r2 = BigInteger.nbi(), g = z.convert(this), i = this.nbits(e) - 1;
        g.copyTo(r);
        while (--i >= 0) {
            z.sqrTo(r, r2);
            if ((e & (1 << i)) > 0) {
                z.mulTo(r2, g, r);
            } else {
                var t = r;
                r = r2;
                r2 = t;
            }
        }
        return z.revert(r);
    },

// (public) this^e % m, 0 <= e < 2^32
    modPowInt : function(e, m) {
        var z;
        if (e < 256 || m.isEven()) {
            z = new Classic(m);
        } else {
            z = new Montgomery(m);
        }
        return this.exp(e, z);
    },

// (public)
    clone : function() {
        var r = BigInteger.nbi();
        this.copyTo(r);
        return r;
    },

// (public) return value as integer
    intValue : function() {
        if (this.s < 0) {
            if (this.t == 1) {
                return this[0] - this.DV;
            } else if (this.t == 0) {
                return -1;
            }
        } else if (this.t == 1) {
            return this[0];
        } else if (this.t == 0) {
            return 0;
        }

  // assumes 16 < DB < 32
        return ((this[1] & ((1 << (32 - this.DB)) - 1)) << this.DB) | this[0];
    },

// (public) return value as byte
    byteValue : function() {
        return (this.t == 0) ? this.s : (this[0] << 24) >> 24;
    },

// (public) return value as short (assumes DB>=16)
    shortValue : function() {
        return (this.t == 0) ? this.s : (this[0] << 16) >> 16;
    },

// (protected) return x s.t. r^x < DV
    chunkSize : function(r) {
        return Math.floor(Math.LN2 * this.DB / Math.log(r));
    },

// (public) 0 if this == 0, 1 if this > 0
    signum : function() {
        if (this.s < 0) {
            return -1;
        } else if (this.t <= 0 || (this.t == 1 && this[0] <= 0)) {
            return 0;
        } else {
            return 1;
        }
    },

// (protected) convert to radix string
    toRadix : function(b) {
        if (b == null) {
            b = 10;
        }
        if (this.signum() == 0 || b < 2 || b > 36) {
            return "0";
        }
        var cs = this.chunkSize(b);
        var a = Math.pow(b, cs);
        var d = BigInteger.nbv(a), y = BigInteger.nbi(), z = BigInteger.nbi(), r = "";
        this.divRemTo(d, y, z);
        while (y.signum() > 0) {
            r = (a + z.intValue()).toString(b).substr(1) + r;
            y.divRemTo(d, y, z);
        }
        return z.intValue().toString(b) + r;
    },

// (protected) convert from radix string
    fromRadix : function(s, b) {
        this.fromInt(0);
        if (b == null) {
            b = 10;
        }
        var cs = this.chunkSize(b);
        var d = Math.pow(b, cs), mi = false, j = 0, w = 0;
        for (var i = 0; i < s.length; ++i) {
            var x = this.intAt(s, i);
            if (x < 0) {
                if (s.charAt(i) == "-" && this.signum() == 0) {
                    mi = true;
                }
                continue;
            }
            w = b * w + x;
            if (++j >= cs) {
                this.dMultiply(d);
                this.dAddOffset(w, 0);
                j = 0;
                w = 0;
            }
        }
        if (j > 0) {
            this.dMultiply(Math.pow(b, j));
            this.dAddOffset(w, 0);
        }
        if (mi) {
            BigInteger.ZERO.subTo(this, this);
        }
    },

// (protected) alternate constructor
    fromNumber : function(a, b, c) {
        if ("number" == typeof b) {
            // new BigInteger(int,int,RNG)
            if (a < 2) {
                this.fromInt(1);
            } else {
                this.fromNumber(a, c);
                // force MSB set
                if (!this.testBit(a - 1)) {
                    this.bitwiseTo(BigInteger.ONE.shiftLeft(a - 1), this.op_or, this);
                }
                if (this.isEven()) {
                    this.dAddOffset(1, 0); // force odd
                }
                while (!this.isProbablePrime(b)) {
                    this.dAddOffset(2, 0);
                    if (this.bitLength() > a) {
                        this.subTo(BigInteger.ONE.shiftLeft(a - 1), this);
                    }
                }
            }
        } else {
            // new BigInteger(int,RNG)
            var x = new Array(), t = a & 7;
            x.length = (a >> 3) + 1;
            b.nextBytes(x);
            if (t > 0) {
                x[0] &= ((1 << t) - 1);
            } else {
                x[0] = 0;
            }
            this.fromString(x, 256);
        }
    },

// (public) convert to bigendian byte array
    toByteArray : function() {
        var i = this.t, r = new Array();
        r[0] = this.s;
        var p = this.DB - (i * this.DB) % 8, d, k = 0;
        if (i-- > 0) {
            if (p < this.DB && (d = this[i] >> p) != (this.s & this.DM) >> p) {
                r[k++] = d | (this.s << (this.DB - p));
            }
            while (i >= 0) {
                if (p < 8) {
                    d = (this[i] & ((1 << p) - 1)) << (8 - p);
                    d |= this[--i] >> (p += this.DB - 8);
                }
                else {
                    d = (this[i] >> (p -= 8)) & 0xff;
                    if (p <= 0) {
                        p += this.DB;
                        --i;
                    }
                }
                if ((d & 0x80) != 0) {
                    d |= -256;
                }
                if (k == 0 && (this.s & 0x80) != (d & 0x80)) {
                    ++k;
                }
                if (k > 0 || d != this.s) {
                    r[k++] = d;
                }
            }
        }
        return r;
    },

    equals : function(a) {
        return(this.compareTo(a) == 0);
    },

    min : function(a) {
        return(this.compareTo(a) < 0) ? this : a;
    },

    max : function(a) {
        return(this.compareTo(a) > 0) ? this : a;
    },

// (protected) r = this op a (bitwise)
    bitwiseTo : function(a, op, r) {
        var i, f, m = Math.min(a.t, this.t);
        for (i = 0; i < m; ++i) {
            r[i] = op(this[i], a[i]);
        }
        if (a.t < this.t) {
            f = a.s & this.DM;
            for (i = m; i < this.t; ++i) {
                r[i] = op(this[i], f);
            }
            r.t = this.t;
        }
        else {
            f = this.s & this.DM;
            for (i = m; i < a.t; ++i) {
                r[i] = op(f, a[i]);
            }
            r.t = a.t;
        }
        r.s = op(this.s, a.s);
        r.clamp();
    },

// (public) this & a
    op_and : function(x, y) {
        return x & y;
    },

    and : function(a) {
        var r = BigInteger.nbi();
        this.bitwiseTo(a, this.op_and, r);
        return r;
    },

// (public) this | a
    op_or : function(x, y) {
        return x | y;
    },

    or : function(a) {
        var r = BigInteger.nbi();
        this.bitwiseTo(a, this.op_or, r);
        return r;
    },

// (public) this ^ a
    op_xor : function(x, y) {
        return x ^ y;
    },

    xor : function(a) {
        var r = BigInteger.nbi();
        this.bitwiseTo(a, this.op_xor, r);
        return r;
    },

// (public) this & ~a
    op_andnot : function(x, y) {
        return x & ~y;
    },

    andNot : function(a) {
        var r = BigInteger.nbi();
        this.bitwiseTo(a, this.op_andnot, r);
        return r;
    },

// (public) ~this
    not : function() {
        var r = BigInteger.nbi();
        for (var i = 0; i < this.t; ++i) {
            r[i] = this.DM & ~this[i];
        }
        r.t = this.t;
        r.s = ~this.s;
        return r;
    },

// (public) this << n
    shiftLeft : function(n) {
        var r = BigInteger.nbi();
        if (n < 0) {
            this.rShiftTo(-n, r);
        } else {
            this.lShiftTo(n, r);
        }
        return r;
    },

// (public) this >> n
    shiftRight : function(n) {
        var r = BigInteger.nbi();
        if (n < 0) {
            this.lShiftTo(-n, r);
        } else {
            this.rShiftTo(n, r);
        }
        return r;
    },

// return index of lowest 1-bit in x, x < 2^31
    lbit : function(x) {
        if (x == 0) {
            return -1;
        }
        var r = 0;
        if ((x & 0xffff) == 0) {
            x >>= 16;
            r += 16;
        }
        if ((x & 0xff) == 0) {
            x >>= 8;
            r += 8;
        }
        if ((x & 0xf) == 0) {
            x >>= 4;
            r += 4;
        }
        if ((x & 3) == 0) {
            x >>= 2;
            r += 2;
        }
        if ((x & 1) == 0) {
            ++r;
        }
        return r;
    },

// (public) returns index of lowest 1-bit (or -1 if none)
    getLowestSetBit : function () {
        for (var i = 0; i < this.t; ++i) {
            if (this[i] != 0) {
                return i * this.DB + this.lbit(this[i]);
            }
        }
        if (this.s < 0) {
            return this.t * this.DB;
        } else {
            return -1;
        }
    },

// return number of 1 bits in x
    cbit : function(x) {
        var r = 0;
        while (x != 0) {
            x &= x - 1;
            ++r;
        }
        return r;
    },

// (public) return number of set bits
    bitCount : function() {
        var r = 0, x = this.s & this.DM;
        for (var i = 0; i < this.t; ++i) {
            r += this.cbit(this[i] ^ x);
        }
        return r;
    },

// (public) true iff nth bit is set
    testBit : function(n) {
        var j = Math.floor(n / this.DB);
        if (j >= this.t) {
            return(this.s != 0);
        } else {
            return((this[j] & (1 << (n % this.DB))) != 0);
        }
    },

// (protected) this op (1<<n)
    changeBit : function(n, op) {
        var r = BigInteger.ONE.shiftLeft(n);
        this.bitwiseTo(r, op, r);
        return r;
    },

// (public) this | (1<<n)
    setBit : function(n) {
        return this.changeBit(n, this.op_or);
    },

// (public) this & ~(1<<n)
    clearBit : function(n) {
        return this.changeBit(n, this.op_andnot);
    },

// (public) this ^ (1<<n)
    flipBit : function(n) {
        return this.changeBit(n, this.op_xor);
    },

// (protected) r = this + a
    addTo : function(a, r) {
        var i = 0, c = 0, m = Math.min(a.t, this.t);
        while (i < m) {
            c += this[i] + a[i];
            r[i++] = c & this.DM;
            c >>= this.DB;
        }
        if (a.t < this.t) {
            c += a.s;
            while (i < this.t) {
                c += this[i];
                r[i++] = c & this.DM;
                c >>= this.DB;
            }
            c += this.s;
        }
        else {
            c += this.s;
            while (i < a.t) {
                c += a[i];
                r[i++] = c & this.DM;
                c >>= this.DB;
            }
            c += a.s;
        }
        r.s = (c < 0) ? -1 : 0;
        if (c > 0) {
            r[i++] = c;
        } else if (c < -1) {
            r[i++] = this.DV + c;
        }
        r.t = i;
        r.clamp();
    },

// (public) this + a
    add : function(a) {
        var r = BigInteger.nbi();
        this.addTo(a, r);
        return r;
    },

// (public) this - a
    subtract : function(a) {
        var r = BigInteger.nbi();
        this.subTo(a, r);
        return r;
    },

// (public) this * a
    multiply : function(a) {
        var r = BigInteger.nbi();
        this.multiplyTo(a, r);
        return r;
    },

// (public) this / a
    divide : function(a) {
        var r = BigInteger.nbi();
        this.divRemTo(a, r, null);
        return r;
    },

// (public) this % a
    remainder : function(a) {
        var r = BigInteger.nbi();
        this.divRemTo(a, null, r);
        return r;
    },

// (public) [this/a,this%a]
    divideAndRemainder : function(a) {
        var q = BigInteger.nbi(), r = BigInteger.nbi();
        this.divRemTo(a, q, r);
        return new Array(q, r);
    },

// (protected) this *= n, this >= 0, 1 < n < DV
    dMultiply : function(n) {
        this[this.t] = this.am(0, n - 1, this, 0, 0, this.t);
        ++this.t;
        this.clamp();
    },

// (protected) this += n << w words, this >= 0
    dAddOffset : function(n, w) {
        while (this.t <= w) {
            this[this.t++] = 0;
        }
        this[w] += n;
        while (this[w] >= this.DV) {
            this[w] -= this.DV;
            if (++w >= this.t) {
                this[this.t++] = 0;
            }
            ++this[w];
        }
    },

// (public) this^e
    pow : function(e) {
        return this.exp(e, new NullExp());
    },

// (protected) r = lower n words of "this * a", a.t <= n
// "this" should be the larger one if appropriate.
    multiplyLowerTo : function(a, n, r) {
        var i = Math.min(this.t + a.t, n);
        r.s = 0; // assumes a,this >= 0
        r.t = i;
        while (i > 0) {
            r[--i] = 0;
        }
        var j;
        for (j = r.t - this.t; i < j; ++i) {
            r[i + this.t] = this.am(0, a[i], r, i, 0, this.t);
        }
        for (j = Math.min(a.t, n); i < j; ++i) {
            this.am(0, a[i], r, i, 0, n - i);
        }
        r.clamp();
    },

// (protected) r = "this * a" without lower n words, n > 0
// "this" should be the larger one if appropriate.
    multiplyUpperTo : function(a, n, r) {
        --n;
        var i = r.t = this.t + a.t - n;
        r.s = 0; // assumes a,this >= 0
        while (--i >= 0) {
            r[i] = 0;
        }
        for (i = Math.max(n - this.t, 0); i < a.t; ++i) {
            r[this.t + i - n] = this.am(n - i, a[i], r, 0, 0, this.t + i - n);
        }
        r.clamp();
        r.drShiftTo(1, r);
    },

// (public) this^e % m (HAC 14.85)
    modPow : function(e, m) {
        var i = e.bitLength(), k, r = BigInteger.nbv(1), z;
        if (i <= 0) {
            return r;
        } else if (i < 18) {
            k = 1;
        } else if (i < 48) {
            k = 3;
        } else if (i < 144) {
            k = 4;
        } else if (i < 768) {
            k = 5;
        } else {
            k = 6;
        }
        if (i < 8) {
            z = new Classic(m);
        }
        else if (m.isEven()) {
            z = new Barrett(m);
        }
        else {
            z = new Montgomery(m);
        }

  // precomputation
        var g = new Array(), n = 3, k1 = k - 1, km = (1 << k) - 1;
        g[1] = z.convert(this);
        if (k > 1) {
            var g2 = BigInteger.nbi();
            z.sqrTo(g[1], g2);
            while (n <= km) {
                g[n] = BigInteger.nbi();
                z.mulTo(g2, g[n - 2], g[n]);
                n += 2;
            }
        }

        var j = e.t - 1, w, is1 = true, r2 = BigInteger.nbi(), t;
        i = this.nbits(e[j]) - 1;
        while (j >= 0) {
            if (i >= k1) {
                w = (e[j] >> (i - k1)) & km;
            } else {
                w = (e[j] & ((1 << (i + 1)) - 1)) << (k1 - i);
                if (j > 0) {
                    w |= e[j - 1] >> (this.DB + i - k1);
                }
            }

            n = k;
            while ((w & 1) == 0) {
                w >>= 1;
                --n;
            }
            if ((i -= n) < 0) {
                i += this.DB;
                --j;
            }
            if (is1) {    // ret == 1, don't bother squaring or multiplying it
                g[w].copyTo(r);
                is1 = false;
            }
            else {
                while (n > 1) {
                    z.sqrTo(r, r2);
                    z.sqrTo(r2, r);
                    n -= 2;
                }
                if (n > 0) {
                    z.sqrTo(r, r2);
                } else {
                    t = r;
                    r = r2;
                    r2 = t;
                }
                z.mulTo(r2, g[w], r);
            }

            while (j >= 0 && (e[j] & (1 << i)) == 0) {
                z.sqrTo(r, r2);
                t = r;
                r = r2;
                r2 = t;
                if (--i < 0) {
                    i = this.DB - 1;
                    --j;
                }
            }
        }
        return z.revert(r);
    },

// (public) gcd(this,a) (HAC 14.54)
    gcd : function(a) {
        var x = (this.s < 0) ? this.negate() : this.clone();
        var y = (a.s < 0) ? a.negate() : a.clone();
        if (x.compareTo(y) < 0) {
            var t = x;
            x = y;
            y = t;
        }
        var i = x.getLowestSetBit(), g = y.getLowestSetBit();
        if (g < 0) {
            return x;
        }
        if (i < g) {
            g = i;
        }
        if (g > 0) {
            x.rShiftTo(g, x);
            y.rShiftTo(g, y);
        }
        while (x.signum() > 0) {
            if ((i = x.getLowestSetBit()) > 0) {
                x.rShiftTo(i, x);
            }
            if ((i = y.getLowestSetBit()) > 0) {
                y.rShiftTo(i, y);
            }
            if (x.compareTo(y) >= 0) {
                x.subTo(y, x);
                x.rShiftTo(1, x);
            }
            else {
                y.subTo(x, y);
                y.rShiftTo(1, y);
            }
        }
        if (g > 0) {
            y.lShiftTo(g, y);
        }
        return y;
    },

// (protected) this % n, n < 2^26
    modInt : function(n) {
        if (n <= 0) {
            return 0;
        }
        var d = this.DV % n, r = (this.s < 0) ? n - 1 : 0;
        if (this.t > 0) {
            if (d == 0) {
                r = this[0] % n;
            } else {
                for (var i = this.t - 1; i >= 0; --i) {
                    r = (d * r + this[i]) % n;
                }
            }
        }
        return r;
    },

// (public) 1/this % m (HAC 14.61)
    modInverse : function(m) {
        var ac = m.isEven();
        if ((this.isEven() && ac) || m.signum() == 0) {
            return BigInteger.ZERO;
        }
        var u = m.clone(), v = this.clone();
        var a = BigInteger.nbv(1), b = BigInteger.nbv(0), c = BigInteger.nbv(0), d = BigInteger.nbv(1);
        while (u.signum() != 0) {
            while (u.isEven()) {
                u.rShiftTo(1, u);
                if (ac) {
                    if (!a.isEven() || !b.isEven()) {
                        a.addTo(this, a);
                        b.subTo(m, b);
                    }
                    a.rShiftTo(1, a);
                } else if (!b.isEven()) {
                    b.subTo(m, b);
                }
                b.rShiftTo(1, b);
            }
            while (v.isEven()) {
                v.rShiftTo(1, v);
                if (ac) {
                    if (!c.isEven() || !d.isEven()) {
                        c.addTo(this, c);
                        d.subTo(m, d);
                    }
                    c.rShiftTo(1, c);
                } else if (!d.isEven()) {
                    d.subTo(m, d);
                }
                d.rShiftTo(1, d);
            }
            if (u.compareTo(v) >= 0) {
                u.subTo(v, u);
                if (ac) {
                    a.subTo(c, a);
                }
                b.subTo(d, b);
            } else {
                v.subTo(u, v);
                if (ac) {
                    c.subTo(a, c);
                }
                d.subTo(b, d);
            }
        }
        if (v.compareTo(BigInteger.ONE) != 0) {
            return BigInteger.ZERO;
        }
        if (d.compareTo(m) >= 0) {
            return d.subtract(m);
        }
        if (d.signum() < 0) {
            d.addTo(m, d);
        } else {
            return d;
        }
        if (d.signum() < 0) {
            return d.add(m);
        } else {
            return d;
        }
    },

// (public) test primality with certainty >= 1-.5^t
    isProbablePrime : function(t) {
        var i, x = this.abs();
        if (x.t == 1 && x[0] <= BigInteger.lowprimes[BigInteger.lowprimes.length - 1]) {
            for (i = 0; i < BigInteger.lowprimes.length; ++i) {
                if (x[0] == BigInteger.lowprimes[i]) {
                    return true;
                }
            }
            return false;
        }
        if (x.isEven()) {
            return false;
        }
        i = 1;
        while (i < BigInteger.lowprimes.length) {
            var m = BigInteger.lowprimes[i], j = i + 1;
            while (j < BigInteger.lowprimes.length && m < BigInteger.lplim) {
                m *= BigInteger.lowprimes[j++];
            }
            m = x.modInt(m);
            while (i < j) {
                if (m % BigInteger.lowprimes[i++] == 0) {
                    return false;
                }
            }
        }
        return x.millerRabin(t);
    },

// (protected) true if probably prime (HAC 4.24, Miller-Rabin)
    millerRabin : function(t) {
        var n1 = this.subtract(BigInteger.ONE);
        var k = n1.getLowestSetBit();
        if (k <= 0) {
            return false;
        }
        var r = n1.shiftRight(k);
        t = (t + 1) >> 1;
        if (t > BigInteger.lowprimes.length) {
            t = BigInteger.lowprimes.length;
        }
        var a = BigInteger.nbi();
        for (var i = 0; i < t; ++i) {
            a.fromInt(BigInteger.lowprimes[i]);
            var y = a.modPow(r, this);
            if (y.compareTo(BigInteger.ONE) != 0 && y.compareTo(n1) != 0) {
                var j = 1;
                while (j++ < k && y.compareTo(n1) != 0) {
                    y = y.modPowInt(2, this);
                    if (y.compareTo(BigInteger.ONE) == 0) {
                        return false;
                    }
                }
                if (y.compareTo(n1) != 0) {
                    return false;
                }
            }
        }
        return true;
    }
});

// return new, unset BigInteger
BigInteger.nbi = function() {
    return new BigInteger(null);
};

// return bigint initialized to value
BigInteger.nbv = function(i) {
    var r = BigInteger.nbi();
    r.fromInt(i);
    return r;
};

// "constants"
BigInteger.ZERO = BigInteger.nbv(0);
BigInteger.ONE = BigInteger.nbv(1);
BigInteger.lowprimes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509];
BigInteger.lplim = (1 << 26) / BigInteger.lowprimes[BigInteger.lowprimes.length - 1];

// Javascript Capability Detection
BigInteger.detectJS = function(debug) {

    // Bits per digit
    var dbits;

    // JavaScript engine analysis
    var canary = 0xdeadbeefcafe;
    var j_lm = ((canary & 0xffffff) == 0xefcafe);

    if (j_lm && (navigator.appName == "Microsoft Internet Explorer")) {
        BigInteger.prototype.am = BigInteger.prototype.am2;
        dbits = 30;
        if (debug) {
            alert("AM2");
        }
    } else if (j_lm && (navigator.appName != "Netscape")) {
        BigInteger.prototype.am = BigInteger.prototype.am1;
        dbits = 26;
        if (debug) {
            alert("AM1");
        }
    } else { // Mozilla/Netscape seems to prefer am3
        BigInteger.prototype.am = BigInteger.prototype.am3;
        dbits = 28;
        if (debug) {
            alert("AM3");
        }
    }

    BigInteger.prototype.DB = dbits;
    BigInteger.prototype.DM = ((1 << dbits) - 1);
    BigInteger.prototype.DV = (1 << dbits);

    var BI_FP = 52;
    BigInteger.prototype.FV = Math.pow(2, BI_FP);
    BigInteger.prototype.F1 = BI_FP - dbits;
    BigInteger.prototype.F2 = 2 * dbits - BI_FP;

    // Digit conversions
    BigInteger.BI_RM = "0123456789abcdefghijklmnopqrstuvwxyz";
    BigInteger.BI_RC = new Array();
    var rr,vv;
    rr = "0".charCodeAt(0);
    for (vv = 0; vv <= 9; ++vv) {
        BigInteger.BI_RC[rr++] = vv;
    }
    rr = "a".charCodeAt(0);
    for (vv = 10; vv < 36; ++vv) {
        BigInteger.BI_RC[rr++] = vv;
    }
    rr = "A".charCodeAt(0);
    for (vv = 10; vv < 36; ++vv) {
        BigInteger.BI_RC[rr++] = vv;
    }
};

//---------------------------------------------------------------------------------------------
// Classic
//---------------------------------------------------------------------------------------------

// Modular reduction using "classic" algorithm
var Classic = Class.create({

    initialize : function(m) {
        this.m = m;
    },

    convert : function(x) {
        if (x.s < 0 || x.compareTo(this.m) >= 0) {
            return x.mod(this.m);
        } else {
            return x;
        }
    },

    revert : function (x) {
        return x;
    },

    reduce : function (x) {
        x.divRemTo(this.m, null, x);
    },

    mulTo : function (x, y, r) {
        x.multiplyTo(y, r);
        this.reduce(r);
    },

    sqrTo : function (x, r) {
        x.squareTo(r);
        this.reduce(r);
    }
});

//---------------------------------------------------------------------------------------------
// Montgomery Reduction
//---------------------------------------------------------------------------------------------

var Montgomery = Class.create({

    initialize : function(m) {
        this.m = m;
        this.mp = m.invDigit();
        this.mpl = this.mp & 0x7fff;
        this.mph = this.mp >> 15;
        this.um = (1 << (m.DB - 15)) - 1;
        this.mt2 = 2 * m.t;
    },

// xR mod m
    convert : function(x) {
        var r = BigInteger.nbi();
        x.abs().dlShiftTo(this.m.t, r);
        r.divRemTo(this.m, null, r);
        if (x.s < 0 && r.compareTo(BigInteger.ZERO) > 0) {
            this.m.subTo(r, r);
        }
        return r;
    },

// x/R mod m
    revert : function(x) {
        var r = BigInteger.nbi();
        x.copyTo(r);
        this.reduce(r);
        return r;
    },

// x = x/R mod m (HAC 14.32)
    reduce : function(x) {

        // pad x so am has enough room later
        while (x.t <= this.mt2) {
            x[x.t++] = 0;
        }
        for (var i = 0; i < this.m.t; ++i) {
            // faster way of calculating u0 = x[i]*mp mod DV
            var j = x[i] & 0x7fff;
            var u0 = (j * this.mpl + (((j * this.mph + (x[i] >> 15) * this.mpl) & this.um) << 15)) & x.DM;
    // use am to combine the multiply-shift-add into one call
            j = i + this.m.t;
            x[j] += this.m.am(0, u0, x, i, 0, this.m.t);
    // propagate carry
            while (x[j] >= x.DV) {
                x[j] -= x.DV;
                x[++j]++;
            }
        }
        x.clamp();
        x.drShiftTo(this.m.t, x);
        if (x.compareTo(this.m) >= 0) {
            x.subTo(this.m, x);
        }
    },

// r = "x^2/R mod m"; x != r
    sqrTo : function(x, r) {
        x.squareTo(r);
        this.reduce(r);
    },

// r = "xy/R mod m"; x,y != r
    mulTo : function(x, y, r) {
        x.multiplyTo(y, r);
        this.reduce(r);
    }
});

//---------------------------------------------------------------------------------------------
// A "null" reducer
//---------------------------------------------------------------------------------------------

var NullExp = Class.create({

    initialize : function() {
    },

    convert : function(x) {
        return x;
    },

    revert : function(x) {
        return x;
    },

    mulTo : function(x, y, r) {
        x.multiplyTo(y, r);
    },

    sqrTo : function(x, r) {
        x.squareTo(r);
    }
});

//---------------------------------------------------------------------------------------------
// Barrett modular reduction
//---------------------------------------------------------------------------------------------

var Barrett = Class.create({

    initialize : function(m) {

        // setup Barrett
        this.r2 = BigInteger.nbi();
        this.q3 = BigInteger.nbi();
        BigInteger.ONE.dlShiftTo(2 * m.t, this.r2);
        this.mu = this.r2.divide(m);
        this.m = m;
    },

    convert : function(x) {
        if (x.s < 0 || x.t > 2 * this.m.t) {
            return x.mod(this.m);
        } else if (x.compareTo(this.m) < 0) {
            return x;
        } else {
            var r = BigInteger.nbi();
            x.copyTo(r);
            this.reduce(r);
            return r;
        }
    },

    revert : function(x) {
        return x;
    },

// x = x mod m (HAC 14.42)
    reduce : function(x) {
        x.drShiftTo(this.m.t - 1, this.r2);
        if (x.t > this.m.t + 1) {
            x.t = this.m.t + 1;
            x.clamp();
        }
        this.mu.multiplyUpperTo(this.r2, this.m.t + 1, this.q3);
        this.m.multiplyLowerTo(this.q3, this.m.t + 1, this.r2);
        while (x.compareTo(this.r2) < 0) {
            x.dAddOffset(1, this.m.t + 1);
        }
        x.subTo(this.r2, x);
        while (x.compareTo(this.m) >= 0) {
            x.subTo(this.m, x);
        }
    },

// r = x^2 mod m; x != r
    sqrTo : function(x, r) {
        x.squareTo(r);
        this.reduce(r);
    },

// r = x*y mod m; x,y != r
    mulTo : function(x, y, r) {
        x.multiplyTo(y, r);
        this.reduce(r);
    }
});

//---------------------------------------------------------------------------------------------
// SecureRandom
//---------------------------------------------------------------------------------------------

var SecureRandom = Class.create({

    initialize : function() {
    },

    nextBytes : function(ba) {
        var i;
        for (i = 0; i < ba.length; ++i) {
            ba[i] = this.nextByte();
        }
    },

    nextByte : function() {
        if (SecureRandom.state == null) {
            SecureRandom.seed_time();
            SecureRandom.state = SecureRandom.newstate();
            SecureRandom.state.init(SecureRandom.pool);
            for (SecureRandom.pptr = 0; SecureRandom.pptr < SecureRandom.pool.length; ++SecureRandom.pptr) {
                SecureRandom.pool[SecureRandom.pptr] = 0;
            }
            SecureRandom.pptr = 0;
            //SecureRandom.pool = null;
        }
        // TODO: allow reseeding after first request
        return SecureRandom.state.next();
    }
});

// Pool size must be a multiple of 4 and greater than 32.
// An array of bytes the size of the pool will be passed to init()
SecureRandom.psize = 256;

SecureRandom.staticInit = function() {

    // Initialize the pool with junk if needed.
    if (SecureRandom.pool == null) {
        SecureRandom.pool = new Array();
        SecureRandom.pptr = 0;
        var t;
        if (navigator.appName == "Netscape" && navigator.appVersion < "5" && window.crypto) {

            // Extract entropy (256 bits) from NS4 RNG if available
            var z = window.crypto.random(32);
            for (t = 0; t < z.length; ++t) {
                SecureRandom.pool[SecureRandom.pptr++] = z.charCodeAt(t) & 255;
            }
        }
        while (SecureRandom.pptr < SecureRandom.psize) {  // extract some randomness from Math.random()
            t = Math.floor(65536 * Math.random());
            SecureRandom.pool[SecureRandom.pptr++] = t >>> 8;
            SecureRandom.pool[SecureRandom.pptr++] = t & 255;
        }
        SecureRandom.pptr = 0;
        SecureRandom.seed_time();
        //SecureRandom.seed_int(window.screenX);
        //SecureRandom.seed_int(window.screenY);
    }
};

// Mix in the current time (w/milliseconds) into the pool
SecureRandom.seed_time = function() {
    SecureRandom.seed_int(new Date().getTime());
};

// Mix in a 32-bit integer into the pool
SecureRandom.seed_int = function(x) {
    SecureRandom.pool[SecureRandom.pptr++] ^= x & 255;
    SecureRandom.pool[SecureRandom.pptr++] ^= (x >> 8) & 255;
    SecureRandom.pool[SecureRandom.pptr++] ^= (x >> 16) & 255;
    SecureRandom.pool[SecureRandom.pptr++] ^= (x >> 24) & 255;
    if (SecureRandom.pptr >= SecureRandom.psize) {
        SecureRandom.pptr -= SecureRandom.psize;
    }
};

// Plug in your RNG constructor here
SecureRandom.newstate = function() {
    return new Arcfour();
};

//---------------------------------------------------------------------------------------------
// Arcfour
//---------------------------------------------------------------------------------------------

var Arcfour = Class.create({

    initialize : function() {
        this.i = 0;
        this.j = 0;
        this.S = new Array();
    },

// Initialize arcfour context from key, an array of ints, each from [0..255]
    init : function(key) {
        var i, j, t;
        for (i = 0; i < 256; ++i) {
            this.S[i] = i;
        }
        j = 0;
        for (i = 0; i < 256; ++i) {
            j = (j + this.S[i] + key[i % key.length]) & 255;
            t = this.S[i];
            this.S[i] = this.S[j];
            this.S[j] = t;
        }
        this.i = 0;
        this.j = 0;
    },

    next : function() {
        var t;
        this.i = (this.i + 1) & 255;
        this.j = (this.j + this.S[this.i]) & 255;
        t = this.S[this.i];
        this.S[this.i] = this.S[this.j];
        this.S[this.j] = t;
        return this.S[(t + this.S[this.i]) & 255];
    }
});

//---------------------------------------------------------------------------------------------
// Initialization
//---------------------------------------------------------------------------------------------

// This is the code (and the only one) which runs automatically at script load time. All other code are
// class definitions.

SecureRandom.staticInit();
BigInteger.detectJS(false);
var encryptedEmail = new EncryptedEmail("encrypted-email");