RSA 암호 해독을위한 개인 키 C++

Question

확장 유클리드 알고리즘을 사용하여 RSA 용 개인 키를 찾기 위해 함수를 작성하려고했지만 오류를 찾을 수는 없지만 처음부터 다시 시작하고 싶지는 않습니다! 특정 값에 대해서는 정확하지만 다른 사람에게는 그렇지 않은데 왜 작동하지 않을 수 있습니다.이 질문이 너무 모호하다면 도움에 감사 드리며 유감 스럽습니다 (나는 사람들을 괴롭히는 경향이 있음을 알고 있습니다). 누구든지 오류를 찾을 수 있습니까? 미리 감사드립니다.

unsigned long long int modinv(unsigned long long int u, unsigned long long int v) 
{ 
    unsigned long long int inv, u1, u3, v1, v3, t1, t3, q; 
    unsigned long long int iter; 

    u1 = 1; 
    u3 = u; 
    v1 = 0; 
    v3 = v; 

    iter = 1; 

    while (v3 != 0) 
    { 

     q = u3/v3; 
     t3 = u3 % v3; 
     t1 = u1 + q * v1; 

     u1 = v1; v1 = t1; u3 = v3; v3 = t3; 
     iter = -iter; 
    } 

    if (u3 != 1) 
     return 0; 
    if (iter < 0) 
     inv = v - u1; 
    else 
     inv = u1; 
    return inv; 
} 

Answer 1

알고리즘을 무효화하기 때문에 여기서 부호없는 값을 사용하지 마십시오. 따라서 unsigned long long int 대신 long long int을 사용할 수 있습니다. 또한 부호가없는 값을 사용하면 의도하지 않은대로 iter = -iter이 작동하지 않으므로 언더 플로우가 발생합니다. iter = 1이 있고 -iter이 -1이 아니라 18446744073709551615 (= 2^64 - 1)이 아니라고 가정 해 봅시다. iter < 0에 대한 검사도 항상 false입니다.

실제 응용 프로그램의 경우 64 비트 유형보다 훨씬 큰 숫자가 필요합니다. 이 작업을 수행하는 방법은 여러 가지가 있지만 GMP (GNU 다중 정밀도 라이브러리)은 해독 단계에서 사용할 수있는 mpz_powm(r, base, exp, mod)입니다. 더 많은 정보 here. 그래서 기본적으로 당신이 당신의 암호 텍스트 c와 개인 키는 다음과 같은 일반 텍스트 m에 c의 암호를 해독 할 수 n (= P * Q)와 d로 정의했다면

:

#include <gmp.h> // requires GMP lib to be installed. 
void rsaDecrypt(const mpz_t c, const mpz_t n, const mpz_t d, mpz_t m) { 
    mpz_init(m); 
    mpz_powm(m, c, d, n); // m = c^d (mod n) 
}