RSA 数字签名失败

Question

我正在尝试实现 RSA 盲数字签名方案，使用 BigInteger class 生成大质数。 Samantha 生成 public 密钥，私钥，选择一条消息，屏蔽它，然后签名，然后 Victor 验证签名。

问题：只要我用modPow来自BigIntegerclass，一切正常（验证算法 returns 每次都正确）。但是，我已经构建了一个自定义 class，我自己实现了几个代数算法；当我用我的 modExp 方法切换 modPow 调用时，我不断从验证算法中得到 false returns（大约 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() 方法可能更方便比较大整数和零。

RSA 数字签名失败

RSA digital signature failing

java

cryptography

rsa

biginteger

modular-arithmetic