1

我需要一种计算方法：

m = a. b ^(p-1-x) mod p

在 JavaScript 中。我发现了这个计算base^exp%mod的算法：

function expmod(base, exp, mod){
if (exp == 0) return 1;
if (exp % 2 == 0){
    return Math.pow((this.expmod(base, (exp / 2), mod)), 2) % mod;
}
else {
    return (base * (this.expmod(base, (exp - 1), mod))) % mod;
}

}

而且效果很好。但我似乎无法找到一种方法来做到这一点

m         = a. b ^(p-1-x) mod p

如果这个问题不完美，我很抱歉。这是我在这里的第一个问题。谢谢你。

4

1 回答 1

4

我没有密码学经验，但是，由于没有其他人回答，我会试一试。

你的问题对我来说不太有意义，所以我决定用 JavaScript 实现一个完整的 Elgamal，这样我就可以在上下文中理解你的问题。这是我想出的：

// 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!"

因此，基本上，在需要时Crypto使用所有 Elgamal 算法。modPow我认为该modPow功能是您最初所追求的，不是吗？您最初发布的版本使用重复平方而不是普通求幂，大概是出于性能目的，但它们都相当快。

不过，我仍然不清楚为什么你需要一个不同的算法来做“ m = a. b ^(p-1-x) mod p”。在实现我的 Elgamal 时我从来不需要这样的东西，所以我不确定这对应的是什么。我确实需要实现一个计算模乘逆的函数，我称之为modInv。那是你想要的吗？我使用了扩展欧几里得算法的精简版来制作它。

如果有帮助，请随时为您的项目复制我的部分或全部代码。

而且，如果您对此有任何疑问，请问我！

编辑：请注意，此代码不适用于实际的生产级加密。这实际上只是算法的概念证明。然而，只要做一些工作，它就可以变得更加安全。让我知道。

编辑：要加密和解密文本，请执行以下操作：

创建一个新Crypto对象来加密文本，然后保存它：

var Alice=Crypto(Alphabet, 69);

这里，Alice只是一些变量，Alphabet是我在代码顶部定义的 29 个符号字母表，69是一个原始根 mod 91744613。

然后，创建另一个 Crypto 对象来解密文本，然后保存它：

var Bob=Crypto(Alphabet, 69);

尽管Bob以与 相同的方式创建Alice，但它们是不同的对象。Bob 不能解密给 Alice 的文本，而 Alice 也不能解密给 Bob 的文本。

现在，使用Alice's encrypt 方法加密一些文本，并保存结果：

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

这里，message是一个空变量，"HELLO, WORLD."是要加密的文本（或文本文件的内容）。Bob.key 是 Bob 的公钥。我们必须在加密中使用 Bob 的密钥，以便 Bob（并且只有 Bob）可以解密文本。生成的加密文本将如下所示："Pl)7t&rfGueuL@|)H'P,*<K\.hxw+∆d*?Io)lg~Adz-6xrR"`。请注意，即使使用相同的消息，每次都会生成不同的输出。它仍将始终解密为相同的值。

现在，理论上，我们可以通过任何我们想要的不安全通道发送此加密文本，并且没有人能够对其进行解码。然而，当 Bob 收到加密文本时，他可以对其进行解码。去做这个：

var plainMessage=Bob.decrypt(codedMessage);

现在，plainMessage将包含文本"HELLO, WORLD."，您可以阅读或做任何您想做的事情。

所以，总而言之，只要这四行就可以做到：

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."

如果您特别想对文本文件执行此操作，则可以将内容复制并粘贴到 javascript 中，或者您可以考虑将文本文件的内容加载到 javascript 中。要开始，请参阅这个 SO和这个 HG。

于 2014-04-20T17:46:44.953 回答