RSA 디지털 서명 실패

Question

큰 소수 생성을 위해 BigInteger 클래스를 사용하여 RSA 블라인드 디지털 서명 체계를 구현하려고합니다. 사만다는 공개 키, 개인 키를 생성하고, 메시지를 선택하고, 가면으로 서명 한 다음 서명 한 다음 빅터가 서명을 확인합니다.

문제 :만큼 나는 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() 방법은 제로로 큰 정수를 비교하기위한 더 편리 할 수 ​​있음을 관찰한다.