计算从g g ^ r ^(xr)和x先导入BigInteger。使用Java

I am trying to implement a ElGamal-like crypto algorithm using Java's BigInteger objects.

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

q is a safe prime in the form 2p+1
q是2p+1形式的安全素数
g is a generator of the group
g是组的生成器

I want to calculate calculate 计算从g g ^ r ^(xr)和x先导入BigInteger。使用Java but i am having troubles. Using modInverse i can calculate but if i use this value with modPow i only get wrong results.

我想计算一下，但我遇到了麻烦。使用modInverse，我可以计算，但是如果我使用这个值，我只能得到错误的结果。

The only Example i found on the web is this one where the author uses modInverse to calculate 计算从g g ^ r ^(xr)和x先导入BigInteger。使用Java :

我在网上找到的唯一一个例子是作者用modInverse计算的:

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

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

I tried some variants (including using modPow with -1) but just cannot get it to work. I think the math should be right but any help is appreciated.

我尝试了一些变体(包括使用modPow和-1)，但就是不能让它工作。我认为数学应该是对的，但是任何帮助都是值得感激的。

Here is my code:

这是我的代码:

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
}

2 个解决方案

#1

The multiplicative group 计算从g g ^ r ^(xr)和x先导入BigInteger。使用Java is of order q−1 — that is to say, g^q−1 = 1 mod q. Thus, what you need to find is not the inverse of x modulo q, but modulo q−1.

乘法群的顺序问−1 -也就是说,gq−1 = 1 mod q。因此,你需要找到的不是x的逆模q,但模问−1。

(Also, user1008646 is right that g^xr = (g^x)^r ≠ g^xg^r = g^x+r.)

(另外,user1008646 gxr =是正确的(gx)r≠gxgr = gx + r。)

Edit: To summarize the discussion below, the paper describing the algorithm the OP is implementing has a typo: instead of working in 计算从g g ^ r ^(xr)和x先导入BigInteger。使用Java , he needs to work in the order-p subgroup of it. (Also, the paper is using p and q in the opposite sense to the way the OP is using them here.)

编辑:为了总结下面的讨论，描述OP正在实现的算法的文章有一个错别字:他需要在order-p子组中工作，而不是在其中工作。(另外，本文使用p和q的意义与OP在这里使用它们的方式相反。)

#2

I'm not familiar with BigInteger, but I believe g^x * g^r = g^(x+r). It looks like you're basing your code on g^x * g^r = g^(x*r). Does that help?

先导入BigInteger,我不熟悉但我相信g ^ x * g ^ r = g ^(x + r)。它看起来像你代码基于g ^ x * g ^ r = g ^(x * r)。这有帮助吗?

#1