2014-10-31 12 views
4

저는 암호화 프로젝트 작업을하고 있습니다. 우리는 NTL big num 라이브러리를 사용해야하며 특히 라이브러리의 CRT 함수를 사용하여 공개 키를 생성해야합니다. 라이브러리의 CRT 기능은 표준 중국어 잉여 정리 알고리즘을 사용하지 않습니다. 그것은 수정 된 버전이며 정확하게 작동하는 방법을 이해하는 데 문제가 있습니다.문제 이해/수정 된 CRT 기능 사용

CRT (A, B, C, D)는 %의 B ==의 C % d의 경우 내가 CRT를 무엇을 말할 수에서

1 반환하지만 항상 다음과 같은 결과에서와 같은 경우가 아니라 어디 세트 B = 5, D = 6 및 A = C 1-6 사이의 임의의 정수이다

% B를 3 C % d의 3 CRT : 1

%의 B : 0 ℃ % d에 5 CRT : 1

%의 B 2 C % d에 2 CRT : 0

% B를 1 C % d에 1 CR T : 0

%의 B : 4 C % d의 4 CRT : 1

% B를 1 C % d에 0 CRT : 이하

1에서 CRT 함수의 코드 도서관. ZZ는 큰 수를 나타내는 데 사용되는 라이브러리 특정 유형입니다.

long CRT(ZZ& gg, ZZ& a, const ZZ& G, const ZZ& p){ 
    long modified = 0; 

    ZZ g; 

    if (!CRTInRange(gg, a)) { 
    modified = 1; 
    ZZ a1; 
    rem(g, gg, a); // g = gg%a 
    RightShift(a1, a, 1); // a1 = (a >> 1) 
    if (g > a1) sub(g, g, a); 
    } 
    else 
    g = gg; 


    ZZ p1; 
    RightShift(p1, p, 1); 

    ZZ a_inv; 
    rem(a_inv, a, p); 
    InvMod(a_inv, a_inv, p); // a_inv = a_inv^{-1} mod p, 0 <= a_inv < p 

    ZZ h; 
    rem(h, g, p); 
    SubMod(h, G, h, p); // return h = (G-h)%p 
    MulMod(h, h, a_inv, p); // return h = (h*a_inv)%p 
    if (h > p1) 
    sub(h, h, p); 

    if (h != 0) { 
    modified = 1; 
    ZZ ah; 
    mul(ah, a, h); 

    if (!IsOdd(p) && g > 0 && (h == p1)) 
    sub(g, g, ah); 
    else 
    add(g, g, ah); 
    } 

    mul(a, a, p); 
    gg = g; 

    return modified; 
    } 

아래는 유일한 정보입니다. 저는 이산 수학에 능숙하지 않습니다. 누구든지이 기능이하는 일을 평신도의 용어로 정확히 설명 할 수 있습니까?

중국어 남은 것.

이 버전은 v3.7에 새로 추가되었으며 이전 버전보다 훨씬 간단하고 빠르다 입니다.

이 함수는 입력 g, A, G, P 는> 0, 0 < = G < P 및 GCD (a, P) = 1 그것은 계산되도록하는 'A * P는 = 같이 얻어 g '= g (mod a)와 같은 g'; * g '= G (mod p); * -a '/ 2 < g'< = a '/ 2. 그런 다음 g : = g '및 a : = a'를 설정하고 g가 변경되면 1을 반환합니다.

정상적인 사용 하에서, 입력 값 g는 -a/2를 만족한다. < g < = a/2; 그러나 이것은 이전 버전 인 에서 문서화되거나 시행되지 않았으므로 이전 버전과의 호환성을 유지하기 위해 아무 제한도 적용되지 않습니다. on g. 하지만이 루틴은 -a/2 인 경우 더 빠르게 실행됩니다. < g < = a/2, 이 루틴이 수행하는 첫 번째 작업은이 상태를 유지하는 것입니다. .

또한 정상적인 사용 상태에서 a와 p는 모두 홀수입니다. 그러나 이것이 사실이 아니더라도 루틴 은 여전히 ​​작동합니다.

루틴은 다음과 같은 간단한 사실을 기반으로합니다.

은 -a/2 <g <은 A/2 = H 및는 * g의 H + A = G (MOD p)를 충족합시다; * -p/2 <h < = p/2. 또한 p = 2 * h 및 g> 0 인 경우 g ': = g - a h; 그렇지 않으면 g ': = g + a h로 설정하십시오. 이렇게 정의 된 g '는 위의 요구 사항을 충족시킵니다. g가 합치 조건을 충족시키는 것을 보는 것은 쉽습니다. 유일하게 "밸런싱"조건이 -a '/ 2 < g'< = a '/ 2인지 확인하는 것입니다.

+1

나는 CRT (Cathode Ray Tube) (CRT), C Run Time 라이브러리와 같은 약어를 정말로 싫어한다. –

+0

첫 번째 단락에서 이것을 썼습니다 : Chinese Remainder Theorem – nhoughto

답변

4

NTL : CRT 그래서이 반복적으로 동시 congruences의 시스템을 해결하기 위해 수치 적 방법이다 "증분 중국어 Remaindering" 이라고 구현합니다. 따라서 증분 중국어 나머지는 같은 목표 (AND RESULT)으로 중국어 나머지 정리는이지만 이전에는 한 반복에서 두 개의 동시 합병 시스템을 해결합니다. 두 번째 반복에서 1 차 반복과 3 번째 합동의 출력 시스템을 해결합니다. GCD (GCD (n1, n2), n3)의 세 숫자의 GCD를 찾는 것과 같은 방법입니다. NTL :: CRT와 고전 중국어 잉여 정리의 계산이 다음 예 (합치 시스템)에서 동일한 결과를 나타냅니다. a '= b1 mod m1, a'= b2 mod m2, a '= b3 mod m3을 찾아야한다.

enter image description here

93

는 '== 지금 NTL 라이브러리와 같은 시스템을 해결할 수 있습니다. 두 번의 CRT 통화.

#include <cassert> 
#include "NTL/ZZ.h" 

int main() 
{ 
    using std::cout; 
    using std::endl; 
    using namespace NTL; 
    ZZ b1, b2, b3; 
    ZZ m1, m2, m3; 
    b1 = 1; 
    b2 = 3; 
    b3 = 2; 

    m1 = 4; 
    m2 = 5; 
    m3 = 7; 

    ZZ a, p, A, P; // named as in CRT implementation 

    // first iteration 
    a = b1; p = m1; 
    A = b2; P = m2; 
    assert(CRT(a, p, A, P)); // CRT returns 1 if a's value changed 

    cout << "1st iteration a: " << a << "\tp: " << p << endl; 

    // next iteration 
    // a and p == m1 * m2 contain result from first iteration 
    A = b3; P = m3; 
    assert(CRT(a, p, A, P)); 

    cout << "2nd iteration a: " << a << "\tp: " << p << endl; 
    return 0; 
} 

출력 :

첫번째 반복 A : -7 P : 20

2 반복 A : -47 P : 140

그래서 결과 인 '== (-47 + 140 == 93). 고전적인 중국어 나머지 알고리즘과 동일합니다.