Secreta

암호학 - Public Key Cipher :: RSA-CRT 본문

Cryptography

암호학 - Public Key Cipher :: RSA-CRT

준♡ 2011.07.06 15:15

굉장히 오랫만의 암호학 포스팅입니다 ...
게다가 6월 말 부터는 바빠서 블로그 관리도 안된 상태였죠 ;;;;;
마지막 암호학 포스팅이 2010년 11월이었으니 무려 8개월만에 블로그의 정체성(?)에 맞는 글을 쓰게 되는군요 ...

RSA에 관한 내용은 앞서 포스팅한 RSA 알고리즘 및 예제(http://reinliebe.tistory.com/79)를 참고 하시고
오늘 포스팅은 RSA-CRT에 관련된 내용 입니다.
실제로 RSA-CRT는 다양한 방면에 걸쳐 두루 쓰이고 있기도 해서
전부터 포스팅 해야지 해야지 하고 마음만 먹고 있었는데 ... 귀찮 어른의 사정에 의해 그냥 방치해 두고 있었죠;;

아울러 본 포스팅의 내용은 http://www.di-mgt.com.au/crt_rsa.html 출처를 기반으로 정리 ...
...라고 쓰고 발번역 이라고 읽는 작업을 통하여 완성하였습니다.

사실 RSA나 RSA-CRT나 결과론적으로 계산 값은 같지만, 어떻게 계산하느냐의 문제인 지라
알고리즘의 전반적인 내용은 크게 다르지 않습니다.

우선 RSA-CRT에 들어가기 앞서, CRT에 대하여 먼저 알아보도록 하겠습니다.
CRT는 The Chinese Remainder Theorem, 중국인의 나머지 정리라고 알려져있지요 ...
왜 중국인인지는 ... ... 제 지혜의 샘위키에 잘 나와있습니다
(http://en.wikipedia.org/wiki/Chinese_Remainder_Theorem)

CRT 내용도 위의 링크를 따라 들어가면 잘 나와있지만 간략하게 정리하면,
CRT의 special case로, 서로 다른 두 소수에 p, q에 대하여  n=pq라고 정의 합니다.
0≤x<n를 만족하는 임의의 x에 대하여
0≤x1<p, 0≤x2<q를 만족하는 유일한 (x1, x2)가 존재한다는걸 기본 전제로 합니다.

그리고 아래와 같은 RSA-CRT 알고리즘을 이용하여 계산을 합니다.
CRT 계산을 하려면 dP, dQ, qInv와 같은 값들을 먼저 계산해야 합니다.
dP = (1/e) mod (p-1)
dQ = (1/e) mod (q-1)
qInv = (1/q) mod p

다음으로 실제 RSA-CRT는 위에서 미리 계산된 값을 이용하여,
m1 = cdP mod p
m2 = cdQ mod q
h = qInv.(m1 - m2) mod p
m = m2 + h.q

이렇게 계산됩니다 ...

장점이라면 ... ... 누가 뭐래도 빠르다는 것입니다 ...
RSA연산에 있어서 성능 저하를 가져 오는 부분이 제곱연산인데,
dP, dQ 크기가 절반으로 줄면서 계산이 빠르죠 ...
(4배정도 빨리 계산된다고 합니다.)
단점이라면 ... ...dP, dQ값 계산할 때 p q가 필요하기에
RSA-CRT를 사용하는 시스템에 대한 다양한 공격에 일부 취약점이 비교적 근래에 발견 되었다는 것 정도겠군요
(사실 그게 문제 ... -_-)

RSA-CRT의 계산 예를 들면,
p = 137, q = 131, n = 137.131 = 17947, e = 3, d = 11787, m = 513
라고 할때
c = 5133 mod n = 8363 으로 계산됩니다.

그럼, m은 일반 RSA의 경우,... m = 836311787 mod 17947 = 513 으로 복호화 되겠지요 ...
836311787 계산이 참 ... ... 오래 걸리죠 ... (뒤에 mod 17947 가 있지만 일단 그걸 빼고 생각하면요)

RSA-CRT의 경우는,
dP = d mod (p-1) = 11787 mod 136 = 91
dQ = d mod (q-1) = 11787 mod 130 = 87
qInv = q-1 mod p = 131-1 mod 137 = 114
m1 = cdP mod p = 836391 mod 137 = 102
m2 = cdQ mod p = 836387 mod 131 = 120
h = qInv.(m1 - m2) mod p = 114.(102-120+137) mod 137 = 3
[여기서 덧셈은 ... 양수를 만들어 주기 위함이니 신경 쓰시지 않아도 됩니다]
m = m2 + h.q = 120 + 3.131 = 513

dP, dQ 값을 이용하여, 836391와 836387만 계산하면 되니 836311787계산보단 당연히 빠르겠지요 ...



3 Comments
댓글쓰기 폼