3

JavaのBigIntegerオブジェクトを使用してElGamalのような暗号化アルゴリズムを実装しようとしています。

  • qは2p+1の形式の安全素数です
  • gは群の生成生成です Zq

計算したいのg ^（xr）およびxからのg ^ rですが、困っています。iを使用するとmodInverse計算できます1 / xが、この値を使用すると、modPow間違った結果しか得られません。

私がウェブ上で見つけた唯一の例は、作者がmodInverse計算に使用する例1 / xです。

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

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

いくつかのバリアント（-1でmodPowを使用することを含む）を試しましたが、動作させることができません。私は数学が正しいはずだと思いますが、どんな助けでもありがたいです。

これが私のコードです：

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
}
4

2 に答える 2

2

私は BigInteger に詳しくありませんが、信じていg^x * g^r = g^(x+r)ます。に基づいてコードを作成しているようですg^x * g^r = g^(x*r)。それは役に立ちますか？

于 2012-06-30T18:18:50.257 に答える
2

乗法群\mathbb Z^*_qは次数 q−1 です — つまり、g q−1 = 1 mod q です。したがって、求めなければならないのは x モジュロ q の逆数ではなく、モジュロ q−1 です。

(また、user1008646 は g xr = (g x ) r ≠ g x g r = g x+rであることは正しいです。)

編集: 以下の議論を要約すると、OP が実装しているアルゴリズムを説明する論文\mathbb Z^*_qにはタイプミスがあります。(また、論文では、OP がここで使用している方法とは逆の意味で p と q を使用しています。)

于 2012-06-30T18:36:08.433 に答える