使用Java BigInteger从g^(xr)和x计算g^r

Question

我正在尝试使用Java的BigInteger对象实现类似ElGamal的加密算法。

• q是形如2p+1的安全素数
• g是群的生成元

我想计算，但我遇到了麻烦。使用modInverse可以计算，但如果我将这个值与modPow一起使用，结果就会出错。

我在网上找到的唯一示例是这个，作者使用modInverse计算：

        BigInteger temp = c1.modPow(a,p);
        temp = temp.modInverse(p);

        // Print this out.
        System.out.println("Here is c1^ -a = "+temp);

我尝试了一些变体（包括使用modPow和-1），但是无法使它工作。我认为数学应该是正确的，但是任何帮助都将不胜感激。

这是我的代码:

final static BigInteger q = new BigInteger("179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624225795083");
final static BigInteger p = new BigInteger("89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112897541");
final static BigInteger g = new BigInteger("117265744532406309959187881490003058805548219220442880294934902019840205433866971629230940840348591638390822573295684678850519428432938503385192533090834775615734759306193531798190548626342600942782601381215002354918333367595380233608085319759193895027739039963819751637948789055533978566423454988608037601806");

/**
 * @param args
 */
public static void main(String[] args) {
    BigInteger x = new BigInteger("1143167411333064507035595976576260123572705969224418468247407610494944119131645169381885774886951623439260024159767473519706771572117243833759909829897948112642480886709322424314787175230081859236165044801596619590783556439791012887937120324676147585272259948372265307207312838134079528284932292492131276823586631161241002772401238870376093826305673839039010423270418706970005486897400");
    BigInteger r = new BigInteger("28622599320501138892999789676320846139720948572640603818980549097364886339367");

    // g^(xr) = g^(x*r)
    BigInteger g_xr = g.modPow(x.multiply(r), q);

    // 1/x
    BigInteger x_inverse = x.modInverse(q);
    System.out.println(x.multiply(x_inverse).mod(q)); // -> 1 --> correct

    // g^r = g^(xr) ^ (1/x)
    BigInteger g_r = g_xr.modPow(x_inverse, q); // FIXME: wrong result

    System.out.println(g_r); //result
    System.out.println(g.modPow(r, q)); // expected result
}

- nurio

Answer 1

我不熟悉BigInteger，但我相信 g^x * g^r = g^(x+r)。 看起来你的代码是基于 g^x * g^r = g^(x*r)。 这有帮助吗？

- David Dubois

---

谢谢，我已经纠正了，但是我仍然得到错误的结果。 - nurio

Answer 2

多项式群的阶是q-1，也就是说g^q-1=1 mod q。因此，你需要找到的不是x模q的逆元，而是模q-1的逆元。

（另外，user1008646正确指出g^xr=(g^x)^r≠g^xg^r=g^x+r。）

---

编辑：总结下面的讨论，OP正在实现的算法的论文中存在一个错字：他需要在其中的阶为p的子群中工作，而不是。 （此外，该论文使用p和q的方式与OP在此处使用它们的方式相反。）

- Ilmari Karonen

---

如果x在模q-1下不可逆（即它是偶数或等于p），那么就不存在y使得对于所有的r，g^(xry) = g^r。如果你需要一个y，那么要么你的算法有问题，要么你在实现中犯了一些错误。看到算法的原始描述将有助于确定哪种情况。 - Ilmari Karonen

顺便提一下，在标准的ElGamal加密中，您应该计算g^r = g^(xr) / g^x = g^(xr) g^(-x)。您不需要为此计算任何模反元素；只需使用g_r = g_xr.multiply( g.modPow(-x,p) ).mod(p)即可。 - Ilmari Karonen

再次感谢。该算法来自于这篇论文，其中相关部分为第11页：“选择两个质数p和q，使得q|p−1且q的位长度为安全参数κ。让g成为G群的生成器，该群是Zq的子群，其阶为q。”你是对的——指定了该群具有素数阶，这将使得找到逆元素成为可能。但是是否可能找到一个Zq的子群，其阶为q呢？ - nurio

不，那一定是打错了。他们的意思是“Z_p^*的阶为q的子群”。（附：对于p = 2q+1，找到一个阶为q的子群G的生成元g的简单方法是选择一个模p的随机数r，将其平方并检查结果是否不等于1。如果不是，则g = r^2是G的生成元。） - Ilmari Karonen

感谢您的提示和付出的时间！ - nurio