RSAデジタル署名が失敗する

Question

大きい素数を生成するためにBigIntegerクラスを使用して、RSA Blindデジタル署名方式を実装しようとしています。サマンサは、公開鍵、秘密鍵を生成し、メッセージを選択し、それをマスクし、それに署名し、次にビクターが署名を検証する。

問題：限り、私はBigIntegerクラスからmodPowべき乗剰余法を使用して、すべてが（検証アルゴリズムが真毎回返す）完璧に動作します。しかし、私は自分でいくつかの代数アルゴリズムを実装したカスタムクラスを構築しました。 modPowをmodExpメソッドで呼び出すと、私はそうしてはいけないのに、検証アルゴリズムから誤った戻り値を得ています（約50-60％の時間）。大きなランダムな整数を使用する代わりに、テスト目的のために小さなハードコーディングされた数値を設定すると、正しい結果が得られます。

質問：結果として、私は私のmodExp方法が問題であることをかなり確信している、しかし、私は見つけることができないよう私もアルゴリズムを数回変更した後、間違ったんです。何が問題ですか？これまで

マイコード：

RSA_test（） - 事前計算ステップのために使用される方法と署名と検証方法として

public static void RSA_test(){ 

    // The Signer (Samantha) picks p and q, 1024 bit primes 
    Random rng = new SecureRandom(); 
    BigInteger p = BigInteger.probablePrime(1024, rng); 
    BigInteger q = BigInteger.probablePrime(1024, rng); 
    /*BigInteger p = BigInteger.valueOf(7); 
    BigInteger q = BigInteger.valueOf(13);*/ 

    // The RSA modulus is computed 
    BigInteger n = p.multiply(q); 

    // phi(n) is computed 
    BigInteger phiN = (p.subtract(BigInteger.ONE) 
         .multiply(q.subtract(BigInteger.ONE))); 

    // Samantha chooses her message, m 
    BigInteger m = new BigInteger("22"); 

    // Samantha computes her public exponent 
    BigInteger v; 
    while(true){ 
     v = new BigInteger(phiN.bitLength(), rng); 
     if(v.compareTo(BigInteger.ONE) > 0 && 
      v.compareTo(phiN) < 0 && 
      ModularArithmetic.gcd(v, phiN).equals(BigInteger.ONE)) 
      break; 
    } 
    // v = BigInteger.valueOf(5); 

    // Samantha generates the blinding factor and masks her message 
    BigInteger r; 
    while(true){ 
     r = new BigInteger(512, rng); 
     if(ModularArithmetic.gcd(r, n).equals(BigInteger.ONE)) 
      break; 
    } 
    // r = BigInteger.valueOf(10); 

    BigInteger mBlinded = m.multiply(ModularArithmetic.modExp(r, v, n)); 

    // Samantha signs her message 
    BigInteger SBlinded = Cryptography.RSASignature(mBlinded, n, phiN, v); 

    // Samantha removes the blinding factor, obtaining S 
    BigInteger S = SBlinded.multiply(ModularArithmetic.modInv(r, n)); 

    // Victor verifies the signature 
    boolean result = Cryptography.RSAVerification(S, m, n, v); 

    String s = (result == true) ? "The signature has been verified" : "The signature has not been verified"; 
    System.out.println(s); 
} 

のテストのように、問題とは無関係です私はそれらが正しいことを確信しています、私はそれらを省略します。また、ここで私のmodExp方法：

public static BigInteger modExp(BigInteger base, BigInteger exponent, BigInteger modulus){ 

    if(exponent.equals(BigInteger.ZERO)) 
     return (modulus.equals(BigInteger.ONE)) ? BigInteger.ZERO : BigInteger.ONE; 
    if(base.equals(BigInteger.ONE)) 
     return (modulus.equals(BigInteger.ONE)) ? BigInteger.ZERO : BigInteger.ONE; 
    if(exponent.equals(BigInteger.ONE)) 
     return base.mod(modulus); 
    if(modulus.equals(BigInteger.ONE)) 
     return BigInteger.ZERO; 
    // The case when base does not have a multiplicative inverse 
    if((modulus.compareTo(BigInteger.ZERO) <= 0) || 
     ((exponent.compareTo(BigInteger.ZERO) < 0 && !(gcd(base,modulus).compareTo(BigInteger.ONE) == 0)))) 
     throw new ArithmeticException("BigInteger: modulus not positive"); 

    BigInteger result = BigInteger.ONE; 
    while(exponent.compareTo(BigInteger.ZERO) > 0){ 
     if(exponent.testBit(0)) 
      result = (result.multiply(base).mod(modulus)); 
     exponent = exponent.shiftRight(1); 
     base = (base.multiply(base)).mod(modulus); 
    } 

    return result.mod(modulus); 
} 

Answer 1

gcd(base, modulus) == 1ていることを確認する以外にあなたが、正しく負の指数を扱うことができません。次のスニペットは正しい方法を示しています。

if (exponent.signum() < 0 && gcd(base,modulus).equals(BigInteger.ONE)) { 
    return modExp(base.modInverse(modulus), exponent.negate(), modulus); 
} 

はsignum()方法がゼロに大きな整数を比較するためのより便利であり得ることを確認します。