'RSA'에 해당되는 글 2건

  1. 2006.04.27 소인수 분해에 기초한 공개키 암호
  2. 2006.04.07 컴퓨터도 풀 수 없는 암호. (2)

(1) RR


Rabin의 방식은 합성수 모듈러에 관하여 제곱근을 찾기 어렵다는 사실로부터 안전성을 얻는다. 이러한 문제는 인수 분해 문제를 푸는 어려움과 동등한 문제이다. RSA 암호 방식에서 공개키 (n, e)의 e를 b로 바꾼 것이 Rabin 암호 방식이다. 먼저 소수 p, q를 선택해 비밀로 한다. n= pq의 합성수 n과 0≤b〈n에서 임의로 선택한 b를 공개한다. 메시지M의 크기는 n보다 작아야하는데 메시지 M의 크기를 x라 하면 암호문C는 다음과 같이 계산된다.


C = M(M+b) mod n


메시지를 복호화하는 방법은 f(x) = +bx - C의 근을 GF(p)와 GF(q)에서 구한 후 중국인의 나머지 정리를 이용해 메시지 M을 구한다. Rabin 암호 방식은 평문 x의 이차식으로 표현되므로, 복호 시 mod (p, q)에 의해 네 개의 평문이 구해지는 결점이 있다.


(2) RSA


1978년 R. Rivest, A. Shamir, L. Adleman이 제안한 RSA는 수년 동안에 제안된 모든 공개키 알고리즘 중에서 이해 및 구현하기가 가장 용이한 알고리즘으로 평가받고 있다. 또한 이 알고리즘은 가장 대중적으로 알려졌으며, 아직까지 수많은 암호 분석을 이겨내고 있다. 비록 암호분석이 RSA의 안전성을 증명하지도 반증하지도 못했지만, 나름대로의 알고리즘의 신뢰 수준을 제시하고 있다.

RSA는 큰 수의 인수분해의 어려움에서 안전성을 얻고 있으며, 공개키 및 비밀키 쌍은 큰 소수를 사용한다. 다음은 메시지 암호화 및 복호화를 위한 키 생성 단계를 나타낸 것이다.


. 두개의 큰 소수 p와 q를 선정하여 합성수 n=pq를 법(public modulo)으로 한다. (pq는 비밀)

. n을 공개하고 φ(n)과 서로소인 임의의 정수 e를 선택, 공개키로 한다.

  (n이 두 소수의 곱일 때 φ(n)=(p-1)(q-1))

. ed ≡1 ( mod φ(n) )이 되는 d를 구해 비밀키로 삼는다.


이러한 절차를 거쳐 공개키와 유클리드 알고리즘을 이용한 비밀키가 생성되고 다음과 같이 암호화 및 복호화가 수행된다.


. 공개키 : n, e

. 비밀키 : p, q, d

. 암호와 : C ≡ Me (mod n)

             (공개키로 암호화)

. 복호화 : M ≡ Cd (mod n)

             (비밀키로 복호화)


여기서, 만약 공개키 n과 e로부터 비밀키 d를 구할 수 있다면 RSA는 해독되게 된다. 이렇게 되기 위해서는 공개키 n으로부터 φ(n)=(p-1)(q-1)을 구해내야 한다. φ(n)을 구하게 되면 유클리드 알고리즘을 이용하여 쉽게 d를 구할 수가 있게 되므로 RSA 알고리즘의 안전성은 n의 소인수 분해, 즉 p와 q를 구해내는 것에 달려 있다. 다음은 이와 관련하여 RSA의 안전성을 결정하는 조건들을 기술한 것이다.


(가) 소인수 분해 문제와의 관계


RSA 암호의 안전성의 필요조건은 소인수 분해의 어려움이다. 현재까지 소인수분해하지 않고 RSA암호를 해독하는 방법은 나와있지 않다.


(나) 부분 정보의 안전성


RSA암호의 암호문에서 평문의 최하위의 1비트를 구하는 일은 암호문을 완전히 구하는 것과 같은 정도로 어렵다는 것이 증명되어져 있다.


(다) e가 작은 값을 갖는 경우의 안전성


통상의 이용환경에서는 안전하지만 여러 사용자가 동일한 공개키를 사용할 경우, 중국인의 나머지 정리를 적용하여 M은 쉽게 구하여지고, 2개의 평문이 선형관계를 갖고 e가 작다면 암호문으로부터 메시지를 쉽게 구할 수 있다.


(라) 소수의 조건


RSA에서 사용되는 소수는 아래와 같은 조건을 충족해야 한다.


p-1이 커다란 소수를 포함. (그 커다란 소수를 r이라 한다.)

p+1이 커다란 소수를 포함.

r-1이 커다란 소수를 포함.


(마) 키 사이즈


1996년 이후 소인수분해 알고리즘의 진보와 계산 능력의 향상에 의해 키 사이즈는 1024비트까지 커졌다. 앞으로도 키 사이즈는 계속 증가할 것이다.


(바) 안전성을 높인 이용방법


RSA 암호 방식을 이용할 경우, 평문이 한정된 공간에서 선택된다면 암호문에서 평문을 쉽게 구하는 것이 가능하다. 이러한 공격을 피하기 위해서는 난수 성분을 도입하여 해결 할 수 있다. RSA사의 PKCS#1는 이러한 생각에 근거한 RSA암호의 이용 방법을 제시하고 있다.

만약 RSA를 응용 분야에 적용하고자 한다면, 상기 조건들을 고려하여 사용함으로서 안전성을 유지해야 할 것이다. 그러나 현재 사용되는 RSA는 키를 선택함에 있어 계산상 큰 수를 사용함으로써 속도가 느리다는 단점을 가지고 있다.

Posted by 엔시스
출처:이정환닷컴

'RSA 공개열쇠 방식'의 암호화는 다음의 3단계 과정이 필요하다.

1단계 : 공개 열쇠 만들기.

1. 암호를 받는 쪽에서는 아무거나 두 소수, p와 q를 생각한다.
2. p와 q를 곱해 N을 만든다.

3. 아무 숫자나 다음 식을 만족하는 두 숫자를 생각한다.

1=(e*d)mod[(p-1)(q-1)]

4. mod()는 나머지를 구하는 함수다. 40mod(7)은 40을 7로 나눈 나머지를 구하라는 말이다. 답은 5다.

5. N과 e는 공개 열쇠다. 전화로 불러줘도 되고 사람들에게 알려줘도 된다. 전혀 문제가 없다.

2단계 : 암호 만들기.

1. 암호를 만드는 쪽에서는 공개 열쇠 N과 e를 써서 암호를 만든다. 문제는 다른 사람들도 모두 이 공개 열쇠를 알고 있다는 사실이다. 열쇠는 공개돼 있지만 받는쪽에서만 풀 수 있어야 한다.

2. 먼저, 문서의 모든 글자를 이진수로 바꾸고 다시 십진수로 바꾼다. 이 숫자를 M이라고 한다. 우리는 지금부터 M을 암호로 바꾼다.

3. 다음 식을 써서 암호 C를 만든다.

C=Memod(N)

3단계 : 암호 풀기.

1. 암호 C를 받아서 원래 문서 M으로 풀어보자.
2. 공식은 간단하다. N과 d를 집어넣으면 된다.

M=Cdmod(N)

3. N과 e는 공개돼 있지만 다른 사람들은 p와 q를 알 방법이 없다. 한번 더 계산해서 만든 d는 더 알 수 없다.




백문이 불여일견, 예제를 풀어보자.

1단계 : 공개 열쇠 만들기.

1. 이정환은 두 소수 11과 17을 생각하고 곱해서 공개 열쇠 N을 187로 잡는다.

2. 이정환은 대충 d를 23로 놓고 다음 공식에 넣어서 공개 열쇠 e를 7으로 잡는다.

1=(e*d)mod[(p-1)(q-1)]

1=(7*23)mod(10*16)
1=161mod(160)

3. N과 e, 187과 7을 공개한다. 얘들아, 우리 이걸로 암호 만들거다. 풀 수 있으면 풀어봐라.

2단계 : 암호 만들기.

1. 백우진은 'X'를 암호화하려고 한다. 이진수로 바꾸면 1011000, 다시 십진수로 바꾸면 M은 88이 된다. 백우진은 M을 공개 열쇠 N과 e, 187과 23을 써서 암호로 바꾼다.
2. 공식에 집어넣는다.

C=Memod(N)

C=887mod(187)
C=40867559636992mod(187)
C=11

3. 40867559636992을 187로 나누면 나머지가 11이 나온다는 이야기다. 11이 암호다. 11를 이정환에게 보낸다.

3단계 : 암호 풀기.

1. 이정환은 이제 암호 C, 11을 풀어 원래 숫자 M을 찾아내야 한다.

2. 공식에 집어넣는다. N과 d는 각각 187과 23이다. N은 공개 열쇠지만 d는 이정환만 아는 숫자다. 처음에 생각한 숫자 p와 q를 곱해서 N을 만들고 이걸 조합해서 d와 e를 만들었는데, 공개된 N과 e만 가지고 d를 찾기는 굉장히 어렵다. 거의 불가능하다.

M=Cdmod(N)

M=1123mod(187)
M=895430243255237372246531mod(187)
M=88

3. 88, 암호를 풀었다.




'RSA 공개 열쇠 방식'은 MIT 컴퓨터 사이언스 실험실의 론 리베스트와 아디 샤미르, 레너드 애들먼, 세 사람이 발명했다. RSA는 이들의 머릿글자 모음이다. 이 암호화 방식의 핵심은 소인수 분해에 있다.

두 소수 p와 q를 곱해서 공개 열쇠 N을 만들면 이걸 쥐고 아무리 난리법석을 떨어도 원래 숫자를 찾을 방법이 없다.

35가 5와 7로 나눠져 있다는 건 쉽게 알 수 있다. 소인수 분해는 하나하나 숫자를 맞춰보는 수밖에 딱히 방법이 없다. 숫자가 커지면 슈퍼컴퓨터를 돌려도 몇십년씩 걸린다. 17과 19607843을 곱하면 333333331이 된다는 건 쉽게 알 수 있지만 그걸 찾기가 어렵다는 이야기다. 실제로 수학자들은 수백년동안 이 숫자가 소수라고 생각해왔다.

여기서 문제를 한번 더 뒤집어 공개 열쇠를 두개 만들어 놓고 이걸 꼬아서 혼자만 아는 결정적인 열쇠 d를 만들어 놓으면 당신의 암호는 거의 완벽하다고 할 수 있다.

위의 예제에서 공개 열쇠 N과 d는 각각 187과 23이다. 이걸 풀려면 N이 먼저 뭐와 뭐의 곱인가 알아야 한다. 그리고 그 뭐와 뭐에서 각각 1을 뺀 숫자의 곱을 구하고 거기서 다시 1을 뺀 수가 d의 몇배인가도 알아야 한다. 몇배인가만 알면 암호는 풀리겠지만, 한번 해봐라. 결코 만만치 않다.

187 정도면 어떻게 풀릴 수도 있지만 보통은 자릿수가 308 이상이다. 한번 보겠는가.

4286280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744699627495237

이게 308자리 숫자다. 이게 뭐와 뭐, 두 소수의 곱으로 돼 있는가 맞춰봐라. 이 정도면 1억대의 PC를 한꺼번에 돌려도 1000년이 넘게 걸린다고 한다. 현재의 과학기술로는 이런 암호를 풀 방법이 없다.

도움 말씀 : 백우진.
참고문헌 : '코드북', '현대수학의 여행자, '수학: 양식의 과학', '영부터 무한대까지', '수학의 황제 가우스'.


Posted by 엔시스