// MiniiRSA.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//
#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
/*
2005/03/25 bro 조경민 (bro@shinbiro.com)
RSA Algorithm For understanding
===================================================
목적 : 간단한 상황을 만들어 RSA 알고리즘을 이해
용어 : RSA - 정수론을 이용하여 만든 공개키 알고리즘
공개키 알고리즘 - 데이터를 보낼 때 상대방의 공개키로 암호화 하여
보내면 상대방은 암호문을 자신이 갖고있는 개인키로
복호화하여 데이터를 받을 수 있는 알고리즘
공개키 - 암호화하는 키로 평문(Plain Text)를 암호문(Cipher)로 만듬
개인키 - 보곻화하는 키 또는 비밀키로 암호문을 평문으로 만듬
----------------------------------------------
기본지식 : 정수론
약수 - 어떤 수가 작은수의 곱으로 표현될때 이 작은수를 약수라함
Ex) 12 = 1,2,3,4,6,12 는 약수
공약수 - 두 수의 약수중 서로 같은 약수
Ex) 12 = 1,2,3,4,6,12 8=1,2,4,8 일때 공약수 1,2,4
최대공약수 - 두 수의 약수중 가장큰 약수gcd로 표현 gcd(12,8) = 4
유클리드 호제법 - 최대공약수를 구하는 방식 gcd(큰수,작은수) = gcd(작은수,큰수/작은수의 나머지)
gcd(100,86) = gcd(86,14) = gcd(14,4) = gcd(4,1) 이므로 최대공약수는 4
서로소 - 서로 공약수가 1밖에 없음 Ex) 23, 11은 서로소
----------------------------------------------
설명 :
임의의 두 소수 p와 q가 있을때
p * q = N
( p - 1 ) * ( q - 1 ) = z
이 때, z와 E는 서로소이며 E < z 여야 함
공개키는 (N,E)
E와 D를 곱한 것을 z로 나눈 나머지가 1일 때
E * D = 1 ( mod z )
개인키는 D
상황 : 키와 plain 은 모두 작은 값이다.
plain은 N을 넘을 수 없다.
개선사항 : Big Number지원
소수 찾기 알고리즘
알고리즘 최저화
*/
// 최대공약수를 구하는 유클리드 호제법
// gcd(100,86) = gcd(86,14) = gcd(14,2) = gcd(2,1)
// 리턴이 1이면 서로소
int gcd(int max, int min)
{
if( min == 0 )
return max;
else
return gcd( min, max%min );
}
// 서로소인 수를 찾는 함수
// 최대공약수가 1이면 서로소이다.
int disjoint( int z, int _E = 2 )
{
int E;
for( E = _E; E < z; E++ )
{
if( gcd( z, E ) == 1 )
return E;
}
return 0;
}
// 공개키 (pN, pE) 개인키 (pD) 를 찾는 함수
// 초기 소수 p와 q는 입력해주어야 한다. (개선의 여지가 있음)
int get_keys( int p, int q, int* pN, int* pE, int* pD )
{
int N,z,E,D;
// 먼저 N, z, E를 마련한다.
N = p*q;
z = (p-1)*(q-1);
// 공개키를 구하자.
// E는 z보다 작은 서로소이다.
E = disjoint( z );
// 개인키를 구하자.
// E*D = 1 ( mod z )
// E*D/z 로 나눈 나머지는 1
while( E > 0 && E < z )
{
// 공식을 만족하는 개인키 D를 계속 찾아본다.
for( D = 2; D < z ; D++ )
{
if( (E*D)%z == 1 )
{
// 개인키를 찾았다.
*pN = N;
*pE = E;
*pD = D;
return 1;
}
}
// z와 다음 서로소를 구한다.
E = disjoint( z, E+1 );
}
return 0;
}
// plain과 공개키 (N,E)로 암호화 하는 함수
// plain을 E번 곱하되, 곱한 중간 값이 N을 넘으면
// N으로 나눈 나머지로 만들어준다. ( N으로 계속 빼주는 방식도 된다)
int encrypt( int plain, int N, int E )
{
int enc = 1;
for( int i = 0 ; i < E; i ++ )
{
enc = enc*plain;
if( enc > N )
enc = enc % N;
}
return enc;
}
// 암호문과 개인키 (N,D)로 암호를 푸는 함수
// encrypt와 동일하다.
int decrypt( int enc, int N, int D )
{
int plain = 1;
for( int i = 0 ; i < D; i ++ )
{
plain = plain*enc;
if( plain > N )
plain = plain % N;
}
return plain;
}
int _tmain(int argc, _TCHAR* argv[])
{
printf("100과 84의 최대공약수 = %d \r\n", gcd( 100, 84) );
printf( "24 와 서로소인 수는 = %d \r\n" , disjoint( 24 ) );
int N,E,D;
get_keys( 5,7, &N, &E, &D );
printf( "p=5, q=7 의 공개키(N,E)=(%d,%d) 비밀키D=%d \r\n", N, E, D );
int plain = 13;
int enc = encrypt( plain, N, E );
int dec = decrypt( enc, N, D );
printf( " plain = %d encrypt(plain,N,E) = %d , decrypt(enc,N,D) = %d \r\n" , plain, enc, dec );
getch();
return 0;
}
------------------------------------------------------------------
네이버 지식인 발췌
정수론이 발달함에 의해서 혁신 적인 보안 시스템이 만들어 졌죠.. DES 시스템의 단점을 보완한 공개키 시스템 RSA는 상당히 큰 정수의 소인수분해가 힘들다는 점을 이용해 만들었습니다. R. Rivest, A. Shamir, L. Adleman 의 첫 글자를 따서 붙였다고 배웠습니다. 오일러 파이함수나, 일차 합동식, 유클리드 알고리듬 정도는 이해 하셔야 할 것입니다.
1) 적당히 비슷하고 큰 소수 p, q를 구합니다.
2) 공개키 n을 생성합니다. (n=pq)
3) φ를 구합니다. φ = (p-1)(q-1)
4) 최대공약수 gcd(s,φ)=1을 만족하는 즉 서로 소인 또다른 공개키 s를 생성합니다. 1< s < φ
5) 유클리드 알고리듬을 이용하여 비밀키 d를 만듭니다. d = s^-1 (mod φ) (sd≡1 (mod φ) 를 구하는 것이지요. 무엇을 선택하든 상관없습니다.) 를 구하는 것이지요. 1< d < φ
※ 확장된 유클리드 알고리듬으로 정수 d를 구하는 법
t_0 = 0
t_1 = 1
t_j = t_(j-2)-q_(j-1)t_(j-1) mod r_0 (단, j≥2)
위 방법을 이용하여 d를 구한다.
암호화) n보다 작은 수로 메세지 M을 정한 다음,암호문 c = M^s (mod n) 을 계산하여 암호문 c를 보낸다.
복호화) M = c^d (mod n)을 사용해 복호한다.
이렇게 쓰기만 하면 잘 모르니, 예를 들어보지요.
1) 소수 5와 7을 골랐습니다.
2) 공개키 n=35를 만들었지요.
3) φ=24를 구했습니다.
4) 24와 서로소인 11=s를 구했습니다.
5) 현재 공개키 (n,s) = (35,11)을 구했지요
6) 비밀키 d를 구합니다.
d = 11^-1 (mod 24)
확장된 유클리드 알고리듬의 적용.
11^-1 (mod 24) --- 주어진 식
24 = 2*11+2(=r1)
--- 이것은 이해 하죠? 24(=n)를 앞의 11(=s)로 나누어 몫과 나머지 형태로 나타낸 것입니다. n = q(=몫)*s+r1(=나머지1)
(t_2)0-2*1 (mod 24) = -2 (mod 24) = 22(=r2) (mod 24)
--- 여기도 쉽습니다.t_(2-2)=0이므로 0-2(=q)*1(t_(2-1)=1) (mod 24) = -2 (mod 24) = 24-2 (mod 24) = 22 (mod 24)
11 = 5(=q2)*2(r1)+1(r3)
---s를 앞에서 나온 나머지 r1으로 나눈 것이죠. 검산식 형태.. (현재 여기서는 나머지가 1이 나왔기 때문에 유클리드 알고리듬은 끝이 난 것입니다.)
(t_3)1-22*5 (mod 24) = -109 (mod 24) = 11 (mod 24)
--- 1(=t_(3-2)) - 22(r2)*5(q2) (mod 24) = -109 (mod 24) = 24*5-109 (mod 24)=11(mod 24)
따라서 d = 11.
암호화) 메세지 3을 암호화 해본다. 암호문 c = 3^11 (mod 35) = 12
복호화) 암호문 12를 복호화 해본다. 메세지 M = 12^11 (mod 35) = 3.
복호화가 제대로 되었죠.. 확장된 유클리드 알고리듬을 적용할 때, 나머지가 1이 나올 때까지 계속 반복하시면 됩니다.
죄송합니다.암호화 된 것이 복호화 되는 과정의 증명까지는 지금 시간이 다되서 다 못쓰겠네요. 도움이 되셨기를..
(φ는 사실 φ(n)을 뜻하는 오일러 함수 값입니다.)
(http://203.253.25.15/~mhkim/c200012/rsa.ppt 를 가보면 설명이 자세히는 되지 않았지만 많은 예를 볼 수 있습니다.)
-----------------------------------------------------------------------
서로소 [relatively prime/disjoint]
요약
1 이외에 공약수를 갖지 않는 두 자연수.
본문
예를 들면 두 자연수 4와 9는 서로소이다. 즉 4의 약수는 1, 2, 4이고 9의 약수는 1, 3, 9이므로 두 수의 공약수는 1밖에 없다. 마찬가지로 7과 13, 또는 20과 21, 또는 33과 98 등이 서로소이다. 두 수가 서로소인가를 알아보는 데에는 유클리드의 계산법을 많이 사용한다. 일반적으로 두 다항식 f(x)와 g(x)가 공통인수를 갖고 있지 않을 때 f(x)와 g(x)는 서로소라고 한다. 또 두 집합 A와 B에 공통으로 속하는 원소가 없을 때, 즉 A∩B＝Ø일 때 집합 A와 B는 서로소라고 한다. 예를 들어 A=｛1, 2, 3｝이고 B=｛4, 5｝일 때 A와 B는 서로소이다. 이것을 벤다이어그램으로 나타내면 집합 A와 B가 서로 겹치는 부분이 없이 떨어져 있다.
----------------------------------------------------------------------
유클리드 호제법은 최대공약수를 구할때 사용합니다.
A,B의 최대공약수를 G라 할때
A=Ga, B=Gb(a,b는 서로소)로 나타낼 수 있습니다.
A=BQ+R에 A=Ga, B=Gb를 대입하면
Ga=GbQ+R
R=G(a-bQ)인데
a-bQ와 Gb는 서로소이므로(왜냐면 a,b가 서로소이므로)
B와R의 최대공약수도 G가 나옵니다.
요약하자면
A와B의 최대공약수가 B와 R(A를B로 나눈 나머지)의 최대공약수와 같다는것입니다.
--------------------------------------------------------------------------
최대공약수 [最大公約數, greatest common measure]
요약
2개 이상의 수의 공약수 중에서 최대인 것.
본문
이를테면, 18의 약수는 1, 2, 3, 6, 9, 18 12의 약수는 1, 2, 3, 4, 6, 12 로서 6이 최대공약수이며, 이것을 (12,18)＝6으로 쓴다. 다른 공약수는 모두 6의 약수이다, 최대공약수를 구하는 방법은, 우선 소인수(素因數)로 분해하여 공통의 수를 택하여 곱해주면 된다. 예를 들면 (12,18)을 구할 경우 12＝2×3, 18＝2×3이므로 (12,18)＝2×3＝6이 된다. 또, 주어진 수가 커서소인수분해하기 곤란할 때에는 유클리드의 호제법을 이용하는 것이 더 간편하다.
두 수 A,B의 최대공약수를 G, 또 A,B를 각각 G로 나누었을 때의 몫을 a,b라 하면, A＝aG, B＝bG인 관계가 성립한다. 이 때 a, b는 서로 소(素), 즉 (a,b)＝1이다. 또 A,B의 최소공배수가 L이면, LG＝AB인 관계가 성립한다. 세 수의 경우 (A,B,C)＝((A,B),C), 즉 두 수의 최대공약수와 나머지 한 수의 최대공약수를 구하면 결국 세 수의 최대공약수가 된다. 네 수 이상에서도 마찬가지로 생각할 수가 있으며, 최소공배수에서도 ［A,B,C］＝［［A,B］,C］가 성립한다.
----------------------------------------------------------------------------
소인수 [素因數, prime factor]
요약
인수 중에서 소수(素數)인 것.
본문
예컨대, 12의 약수 1, 2, 3, 4, 6, 12 중에서 2와 3은 소수이지만, 1, 4, 6, 12는 소수가 아니다. 따라서 12의 소인수는 2와 3이다.
----------------------------------------------------------------------------
약수 [約數, divisor]
요약
어떤 수를 나누어 떨어지게 할 수 있는 수.
본문
즉 정수(整數) a가 둘 이상의 정수의 곱으로 표시되어 a=b ·c ·d ·…가 될 때 b,c,d,…를 각각 a의 약수 또는 인수(因數)라 한다. 이것에 대하여 a를 b,c,d,… 등의 배수라고 한다. 예를 들면, 12＝1×2×6=4×3이므로 1,2,3,4,6,12는 각각 12의 약수이고, 또 12는 1,2,3,4,6,12의 각각의 배수이다.
0이 아닌 수의 배수는 무수히 많으며, 약수는 한정되어 있고, 0은 모든 수의 배수이나 어떤 수의 약수는 되지 않는다. 0이 아닌 수는 그 수 자신의 배수인 동시에 약수도 된다. 또, 다항식(多項式) f(x)도 f(x)＝h(x) ·g(x) · …와 같이 둘 이상의 식으로 분해가 될 때 h(x), g(x) 등을 각각 f(x)의 약수 또는 인수라 한다. 예를 들면, (x＋1)(x＋2)는 x(x＋1)(x＋2)2의 약수 또는 인수이다.
------------------------------------------------------------------------
공약수 [公約數, common divisor]
요약
2개 이상의 정수, 또는 다항식에 공통인 약수.
본문
즉, 정수 m이 2s 이상의 정수 a1,a2,a3,…,as의 각각의 약수가 될 때, 이를 m을 a1,a2,a3,…,as의 공약수라 한다.
이를테면, 6은 3개의 정수 24,36,60의 공약수이다. 또, 18의 약수는 1,2,3,6,9,18이며, 12의 약수는 1,2,3,4,6,12이다. 이 중에서 공통인 약수는 1,2,3,6이므로 1,2,3,6은 18과 12의 공약수이다.
공약수 중에서 가장 큰 공약수를 최대공약수라 하고, 보통 G.C.M.으로 나타낸다. m이 a1,a2,a3,…,as의 공약수이면, m의 약수 역시 a1,a2,a3,…,as의 공약수이다. 다항식에서도 정수에서와 마찬가지로 공약수라는 말을 쓴다.
즉, 변수 a1,a2,a3,…,as의 다항식 f(x1,x2,…,xn)가 2개 이상의 다항식 g1(x1,x2,…xn),…, gs(x1,x2,…,xn)의 각각을 나누어 떨어지게
-----------------------------------------------------------------------
[답변] 유클리드 호제법에 관하여... 푸른하늘
휴............
또 요즘 내 주는 수행평가가 그런 건가보죠?
아니면, 한 분이 계속 이름 바꿔가며 올리시는 건???!!! ^.^
농담이구요, 암튼, 너무 많은 분이 올리시네엽. 수행평가마저도 획일적 교육이 되다니...
유클리드 호제법에 관해 간단히 설명드리겠습니다.
목적은 두 수의 최대공약수를 찾아내는 겁니다. 계산이 여러분이 이미 배운 최대공약수 구하는 방법에 비해 그렇게 효율적이지는 않지만, 단순한 계산의 반복이기 때문에 컴퓨터에서 잘 사용되는 알고리즘이기도 합니다.
원리는 다음과 같습니다.
A=BQ + R 의 관계가 성립할 때
A와 B의 최대공약수는 B와 R과의 최대공약수와 같다는 원리입니다. 한 번 증명해 보겠습니다.
A와 B의 최대공약수를 G라고 하면 각각 A=aG, B=bG (단, a, b는 서로 소)라고 쓸 수 있습니다. 그러면 위의 식은 다음과 같이 됩니다.
aG = bGQ + R
(a-bQ)G = R
좌, 우변 모두 정수이므로, R은 G의 약수여야 합니다. 이상으로 증명이 끝났습니다.
계산법은 뭐냐면요, 뭐, 위의 원리를 그대로 쓰는 거지만... 두 수의 최대공약수를 구할 때, 작은 수와, 나머지와의 최대공약수를 구한다고 생각하시면 됩니다. 음... 100과 60의 최대공약수를 유클리드 호제법으로 구하면,
100 = 60 * 1 + 20 이니까 (60, 20)을 생각해보면 됩니다.
60 = 20 * 3 이므로 최대공약수는 20이 됩니다.
우.... 너무 쉬운 예를 들어서... 다른 거 하나 더 해볼까요? 100하고... 84로 해 볼까요?
100 = 84 * 1 + 16 --- (100,84) = (84,16)
84 = 16 * 5 + 4 ----- (84, 16) = (16, 4)
16 = 4 * 4
그러므로 (100, 84) = 4가 되겠군요.
유클리드 호제법은 단순한 계산 방법으로 인해, 단순히 두 수만이 아니라 두 다항식의 최대공약수를 구하는데도 강력한 힘을 발휘합니다.
--------------------------------------------------------
http://blog.naver.com/muse1472/120010861477
내 블로그에 담기
카페에 담기
프린트 하기
스크랩 : 금지됨
카페에 담기
오픈사전에 등록
프린트 하기
스크랩 : 금지됨
카페에 담기
프린트 하기
목록보기 | 컴관련__________▣ (62) 스크랩 엮인글 목록열기 ▼ 목록닫기 ▲
RSA 알고리즘 개요 | ▣ 컴 관련 2005/03/07 09:42
http://blog.naver.com/muse1472/120010861477
인터넷과 암호
컴퓨터에 조금만 관심이 있는 사람이면 누구나 인터넷으로 오고가는 각종 정보에 암호가 사용되고 있다는 것을 알고 있습니다. 인터넷 세계를 열심히 서핑하는 사람이라면 어쩌면 PGP(Pretty Good Privacy)라는 암호 프로그램을 알고 있을지 모릅니다.
좀 더 관심이 있는 사람이라면 PGP의 암호화 알고리즘이 전자상거래, 금융, 전자서명 등의 보안에 사용되고 있는 RSA라는 수학적 알고리즘이라는 것까지도 알고 있을 것입니다. 그러나 수학이나 암호에 전문적인 지식이 없다면 그 RSA에 의한 암호화와 복호의 비밀을 알고 있는 사람은 아마도 흔치 않을 것입니다. RSA가 대체 무엇이며, 왜 그것이 마법의 암호라고 불리울까? 이 글은 이러한 궁금증에 대한 초보적인 대답을 드림으로써 아마추어의 지적 호기심에 부응하고자 하는 목적에서 작성하였습니다.
잠그는 열쇠와 여는 열쇠가 다른 암호
암호화(encoding, enciphering, cryptography, encryption)는 흔히 자물쇠를 채우는 행위, 반대로 복호(decoding, decryption)는 자물쇠를 여는 행위에 비유되곤 합니다. 이 때문에 암호화와 복호에 사용되는 수단을 key라고 부르고, 그것이 문장이나 숫자인 경우에는 keyword라고 부릅니다. 우리가 "종합판례정보시스템"에서 검색용으로 사용하는 주제어를 의미하는 keyword와는 물론 다른 의미의 keyword입니다.
1976년 어쩌면 1978년 이전까지 암호화의 key와 복호의 key는 항상 동일한 것이었습니다.복호 작업은 언제나 암호화 작업을 반대방향으로 되풀이하는 것이기 때문에 복호를 위해서는 반드시 암호화에 사용된 key와 동일한 key가 필요하고 이것이 보통사람들의 상식에 부합하는 것입니다.
그런데 만일 잠그는 key와 여는 key가 다르다면, 잠그는 key로 암호화하고 나면 그 key로는 복호할 수 없고 반드시 또 다른 key가 있어야만 열 수 있다면 무척 편리할 것입니다. 여러분은 그 여는 key를 일반에 공개하고 여러분에게 보내는 편지를 그 공개 key로 암호화할 것을 요구할 수 있을 것입니다. 일단 암호화된 편지는 여는 key를 갖고 있는 당신 외에는 이 세상 누구도, 심지어는 그 암호문을 작성한 사람까지도 열어 볼 수 없을 것입니다.
또 이런 경우도 있을 수 있습니다. 먼저 A회사가 많은 고객의 신용정보(예컨대 비밀번호)를 보관하고 있다고 가정해 봅시다. A회사의 컴퓨터 어딘가에는 그 많은 고객들의 신용정보가 들어 있을 것이고, 그 정보가 유출될 경우 A회사는 엄청난 손해배상책임을 부담하게 될 위험성이 있습니다. 그래서 A회사는 이 평문(plain text, 암호화하기 전의 자료를 지칭합니다)으로 된 신용정보를 암호화하여 저장한 후 평문을 폐기하기로 결정하였습니다. 그런데 문제가 생겼습니다. 암호화와 복호 작업을 위하여 key를 컴퓨터 어딘가에 보관해 두어야겠는데 그 key가 암호화된 정보와 함께 유출되면 역시 엄청난 손해배상책임을 부담하게 될 것이기 때문입니다.
결국 A회사는 다음과 같은 보안 시스템을 생각해 내었습니다. 고객과 거래를 시작할 때 잠그는 key와 여는 key를 만들어 여는 key를 고객의 카드에 기록하고, 회사의 컴퓨터에는 잠그는 key와 그 key로 암호화된 정보만을 기록해 두기로 하였습니다(평문 정보는 고객의 머리에 기록되어 있습니다). 이렇게 되면 암호화 작업이 끝난 후에는 A회사 스스로도 평문 정보를 알 수 없게 되기 때문에 암호화된 정보와 잠그는 key가 사고로 유출되더라도 고객들에게 피해를 줄 염려가 없게 됩니다.
그런 후에 인출작업의 순서는 다음과 같습니다. 고객이 A회사의 단말기에 카드를 삽입하고 keybord를 이용하여 평문 정보를 입력하면 단말기는 주(main) 컴퓨터로부터 암호화된 고객의 정보를 제공받고 고객의 카드로부터는 고객의 여는 key를 제공받아 이 key를 사용하여 암호화된 고객 정보를 평문 정보로 복호한 후 고객이 입력한 평문 정보와 비교합니다. 이것이 일치하면 인출을 승인하고 이것이 불일치하면 인출을 거부하게 됩니다. 이제 A회사는 여는 key와 평문정보 어느 것도 보관하지 않으면서 고객의 신분을 확인할 수 있게 되었습니다.
물론 고객이 카드와 비밀번호를 함께 분실한다면 고객에게 손해가 발생하겠지만, 첫째 이는 고객의 잘못으로 인한 것이기 때문에 손해배상책임을 부담하지 않을 것이고, 둘째 설사 책임을 부담한다고 하더라도 이는 대규모 정보유출에 비하면 극히 작은 손해이므로 직접 부담하거나 보험에 의하여 보장받을 수 있습니다. 이러한 보안 시스템은 이미 만들어져 있고 멀지 않은 장래에 IC카드의 보급과 함께 실용화될 것으로 예상됩니다. 어쩌면 이미 실용화되었는지도 모릅니다.
이러한 암호체계가 실제로 가능할까요? 개념상으로야 이러한 암호체계의 가능성이 오래 전부터 제기되어 왔고, 1976년 Diffie와 Hellman에 의하여 공개 key 개념이 제안되기는 하였지만, 실용화할 수 있는 최초의 암호 알고리즘은 1978년 MIT 공대 연구팀 소속의 세 학자 Rivest, Shamir, Adleman이 개발한 RSA입니다.
마법의 수 트리플
RSA를 이해하기 위해서는 먼저 RSA가 key로 사용하는 "마법의 수 트리플"를 만드는 방법을 알아야 합니다.
① 먼저 소수(素數, prime number) 2개를 선택하여 p와 q라고 합니다.
② p × q ＝ N의 방법으로 N을 구합니다.
③ (p-1) × (q-1) ＝ z의 방법으로 z를 구합니다.
④ z와 공약수를 갖지 않는 수 하나를 선택하여 E라고 이름짓습니다.
통상의 계산의 편의를 위하여 z보다 작은 수 중 소수 하나를 선택합니다. E는 공개 key(잠그는 key)가 됩니다.
⑤ 비밀 key(여는 key)를 구하는 방법은 조금 까다로운데, 비밀 key를 D라고 할 때 D는 D × E / z의 계산에서 나머지가 1이 남아야 한다.
즉, E × D ≡ 1(mod z)을 충족하여야 합니다.
이 방법에 의하여 공개 key N과 E, 그리고 비밀 key D가 모두 완성이 되었습니다.
다음으로 이 공개 key N과 E를 사용하여 암호화하는 방법은 다음과 같습니다.
① 먼저 평문을 수학계산을 수행할 수 있는 수(number)로 변환하여야 하는데, 컴퓨터에서는 이미 모든 문자와 기호를 수로 변환하여 사용하기 때문에 특별한 작업을 요하지 않습니다.
② 평문숫자를 E번 곱하는데 그 과정에서 나오는 중간 수가 N보다 크면 그 중간 수에서 N을 뺍니다. 그 수가 N보다 크면 몇 번이고 뺄셈을 반복하여 N을 뺍니다. N보다 작은 수가 나오면 이를 다시 평문숫자와 곱합니다. 위 작업을 반복하면 그 결과 N보다 작은 수가 남게 되는데 이것이 암호숫자입니다.
③ 위 ②의 계산결과는 또 다른 방법으로 구할 수 있습니다. 평문숫자를 E번 곱한 다음 N으로 나누면 딱 떨어지지 않고 나머지가 남게 되는데 그 나머지가 바로 암호숫자입니다. 공개 key가 작은 수일 경우에는 ③의 방법이 계산하기 쉽지만 큰 수인 경우에는 ③의 방법으로는 계산이 불가능하고 ②의 방법으로 계산하여야 합니다.
실제 공개 key로는 1억 단위 이상의 수가 계산되는데 ③의 방법으로 이러한 계산을 수행할 수 있는 컴퓨터는 없습니다. 위 ②와 ③의 계산결과가 동일하다는 것은 여러분 각자 증명해 보십시오. 시간을 좀 걸리겠지만 이 글을 읽으시는 분들 정도의 실력이라면 증명할 수 있을 것입니다.
이제 위와 같은 방법으로 만들어진 암호숫자를 공개 key N과 E를 사용하여 평문숫자로 복호할 수 있는지를 생각해 보십시오. 잠시만 생각해 보아도 이것이 불가능하다는 것을 알 수 있습니다.
위 암호숫자를 평문숫자로 복호하기 위해서는 비밀 key D가 필요합니다. 그 복호의 과정은 다음과 같습니다.
① 암호숫자를 D번 곱하는데 한번 곱할 때마다 그 중간수에서 N을 뺍니다. N을 뺀 수가 N보다 크면 그 숫자가 N보다 작아질 때까지 N을 뺍니다.
② 그 중간수가 N보다 작아지면 다시 암호숫자를 곱하고, 이런 계산 방법을 D번 되풀이합니다. 그 결과 N보다 작은 수가 나오는데 그 수가 바로 평문숫자입니다.
이제 여러분은 마법의 수 트리플을 만드는 방법과 그 수를 key로 사용하는 RSA의 연산방법을 알게 되었습니다. 이 시점에서 여러분은 당연히 이러한 의문을 갖게 될 것입니다. 위 연산을 시작하기 전의 평문숫자와 위 암호화와 복호 연산 결과 얻은 숫자가 과연 항상 동일한 숫자일까? 이 의문에 대한 가장 적절한 대답은 위 RSA 연산 값이 참임에 대한 수학적 증명일 것입니다. 그 증명은 너무나도 어렵고 복잡하여 아마추어로서는 이해하기 어려울 뿐만 아니라 증명과정만 하나의 논문 분량이 되므로 이 곳에 소개할 수가 없습니다. 솔직히 말씀드리면 저도 잘 모릅니다.
진짜 비밀은 소수(prime number)의 성질
여러분의 또 다른 의문은 과연 공개 key인 N과 E만으로 암호숫자를 평문숫자로 복호할 수 없는가 하는 것과 N과 E만으로 비밀 key인 D를 알 수 없는가 하는 것일 것입니다.
먼저 첫째 의문은 위에서도 말했다시피 조금만 생각해 보면 금방 그 답이 나옵니다. 암호화 연산을 역산하기 위해서는 암호숫자에 N을 더해야 하는데 당장 처음부터 몇 번을 더해야 할지 알 수 없기 때문에 그 역산은 불가능해집니다. 즉 하나의 해답이 아니라 무한한 경우의 수가 역산으로 도출될 수 있기 때문에 이 연산은 이론적으로도 불가능하다고 할 수 있습니다.
두 번째 의문에 대한 답은 조금 어려워집니다. 가장 타당한 답은 yes and no인데, 이론적으로는 yes(알 수 있다)이고, 현실적으로는 no(불가능하다)라는 의미입니다. 마법의 수 트리플은 일정한 법칙에 의하여 만들어지고 먼저 N과 E가 정해진 후에는 간단한 연산에 의하여 D 값이 쉽게 구해지게 됩니다. 그런데 D 값은 N과 E로부터 곧바로 구해지는 것이 아니라 N의 약수인 p와 q로 결정되기 때문에 p와 q 값을 먼저 알아야만 D 값을 구할 수 있습니다. 어려움은 여기에 있습니다. p와 q는 소수이고 N ＝ p × q인데 아직 우리는 소수에 일반적인 규칙을 알지 못합니다. 대부분의 수학자들은 소수에는 일반적인 규칙이 없을 것으로 생각하기도 합니다.
물론 소수의 규칙과 관련하여 몇 가지 성질이 관찰된 바는 있습니다.
첫째 쌍둥이 소수(prime number twins)라는 것이 있는데 어떤 소수에 2를 더한 수가 역시 소수인 쌍을 말합니다. 예를 들면, 2/3으로부터 시작해서 9,900,0641/9,900,0643과 같은 숫자의 쌍을 말합니다. 수학자들은 그 쌍둥이 수의 개수가 무한할 것으로 추측하는데 아직 이를 증명한 사람은 없습니다.
둘째 "2보다 큰 모든 짝수는 두 소수의 합이다"라는 Christian von Goldbach의 가정(假定, 또는 추측, 수학에서 참임이 증명되지 않았지만 거짓임이 밝혀지지도 않은 명제를 말합니다)이 있는데 이 역시 아직은 증명되지 않았습니다.
셋째, 정수론(number theory) 중 가장 놀라운 정리 중 하나로 꼽히는 소수정리(prime number theorem)가 있습니다. 이 글에서 수학공식을 입력하기가 어려워 소수정리의 내용을 설명하기는 어렵지만, 이 정리 또한 연역적 방식으로 증명된 것은 아니고 컴퓨터에 의한 연산을 통하여 증명되었기 때문에 이 또한 엄격한 의미에서 증명되었다고 할 수는 없습니다(물론 컴퓨터에 의한 증명도 인정하여야 한다는 반대 견해도 있습니다).
이 중 어느 하나만 증명하여도 평생 판결 작성으로 얻을 수 있는 것보다 더 큰 명성을 얻을 수 있고, 전 세계가 인정하는 천재의 대열에 끼어들 수 있습니다. 여러분은 한 번 도전해 볼 생각이 없으신지?
이야기가 엉뚱한 방향으로 흘렀습니다. 각설하고 본론으로 돌아가면, 아주 큰 수의 소수를 구하는 방법은 2부터 시작하여 알려진 모든 소수로 일일이 나누기 계산을 해 보는 방법 외에는 다른 방법이 없습니다. 타원함수를 응용한 계산방법 등이 개발되었으나 아직은 가장 단순한 나누기 계산보다 더 효율적인 계산방법은 발견되지 않고 있습니다.
따라서 아주 큰 소수인 p와 q를 곱하여 더 큰 수 N을 구할 경우 그 N의 약수 p와 q를 알아내는 방법은 역시 2부터 시작한 모든 소수로 실제 나누기 계산을 해 보는 방법밖에 없습니다. N이 50자리만 되면 약 140억번의 계산을 수행하여야 p와 q를 찾아낼 수 있습니다. RSA가 발표된 1978년경의 컴퓨터로는 200자리의 N에서 p와 q를 찾아내기 위해서는 지구의 나이만큼(약 45억년)의 시간이 필요하다고 합니다. 그렇다면 현실적으로 그 계산은 불가능하고 p와 q의 값을 모르는 이상 공개 key D 값도 알 수 없다는 결론을 내릴 수 있습니다.
조금만 더 전문적으로 들어가 보겠습니다. 두 소수의 곱으로 만들어지는 N에 문제가 전혀 없는 것은 아닙니다. 1977년 8월 3명의 수학자가 Scientific American(이 잡지는 영국의 Nature와 더불어 세계에서 가장 유명한 과학전문잡지입니다. http://www.sciam.com/를 찾아가시면 놀라운 지식의 보고를 접하게 됩니다.)에 두 소수의 곱으로 만들어진 129자리의 수를 올려놓고 이 수의 소인수 분해에 100달러의 상금을 걸었습니다. 출제자는 아마도 이 문제를 푸는 사람이 없을 것이라고 확신하였을 것입니다. 그런데 5년 후 1992년 4명의 수학자가 전세계 25개국의 자원봉사자 600명을 모집한 후 인터넷을 통하여 공동작업을 벌인 결과 64자리 수의 소인수를 찾아내고 말았습니다. 참여자들에게 돌아간 상금은 1인당 17센트였다고 합니다.
그런데 같은 해에 Lester와 Bernstein이라는 사람이 단 한 대의 컴퓨터로 3주일간 16만번의 연산을 거듭한 결과 157자리의 숫자를 인수분해하는 데에 성공하였습니다. 엄청난 횟수의 연산이기는 하지만 이 정도의 연산으로 N이 소인수 분해될 수 있다면 RSA는 실용화될 수 없는 믿을 수 없는 암호체계가 되고 맙니다. 그러나 다행히도 그 소인수는 2의 523승에서 1을 뺀 수였는데 2의 n승에서 1을 뺀 소수는 쉽게 계산된다는 것이 알려졌습니다. 그 이후 RSA에 사용되는 N을 만드는 데에는 이러한 수는 제외되게 되었습니다.
실제 사용하는 RSA 시스템은 굉장히 큰 N(큰 경우에는 300자리 이상)을 만들어 1 회사에서 1개의 N을 사용하기도 하는데 이 1개의 수로부터 많은 개수(N이 그렇게 클 경우에는 거의 무한한 개수)의 E와 D를 구하여 고객별로 다른 공개 key와 비밀 key를 제공하는 방법을 사용하고 있습니다. 위험은 피할 수 없는 것이 그 system 어딘가에는 N을 구성하는 p와 q가 들어가 있습니다. 세상에 완벽한 보안이란 역시 존재하지 않는 것 같습니다.
PGP 맛보기
PGP는 Pretty Good Privacy의 약자인데 RSA 팀이 만든 공개 프로그램입니다. 인터넷상에서 이 프로그램을 구할 수 있는 곳은 많습니다. 그 중 한 곳을 소개하면 다음과 같습니다.
http://www.uni-mannheim.de/studorg/gahg/PGP
이 프로그램은 1개의 N을 사용하는데 사용자가 컴퓨터의 지시에 따라 긴 문장을 타이핑하면 그 타이핑 리듬에 따라 E와 D를 결정합니다. 그리고 이를 이용하여 암호화, 복호, 디지털 서명을 할 수 있습니다.
마무리
제가 많은 분들이 생소하게 생각할 분야에 관하여 이런 글을 쓰는 이유 중의 하나는 다음과 같습니다. 현재 디지털 서명 시스템은 RSA에 의존하고 있을 뿐 아니라 다른 대안이 전혀 없기 때문에 우리나라가 디지털 서명 제도를 채택한다면 어쩔 수 없이 RSA에 의존할 수밖에 없습니다. 그 법제도를 만들고 운영해 갈 여러분들이 RSA의 이론적, 기술적 기초를 이해하고 있어야만 RSA의 안전성과 위험성에 대한 정당한 평가를 할 수 있을 것이고, 결국 정당한 정책적 판단을 할 수 있을 것이라고 믿기 때문입니다.
또 다른 이유는 재미 때문입니다. 프랑스의 천재 수학가 Pierre de Fermat(페르마)의 현실세계에서의 직업이 판사였다는 것을 알고 계십니까? 법학이 연구대상으로 삼는 현실세계는 불확정성이론과 chaos이론이 적용되는 복잡계인 반면, 수학이 연구대상으로 삼는 가상의 세계는 지극히 단순한 세계여서 정연한 질서가 있습니다. 질서에는 아름다움이 있습니다. 현실적으로 복잡계에 존재하는 Fermat가 아름다운 질서를 연구하면서 재미를 찾았듯이 이 글을 읽는 분들 중에는 분명히 질서와 논리의 아름다움에 빠지는 재미를 아는 분들이 있을 것입니다.
장차 RSA에 의하여 비밀이 유지되는 세상이 형성되면 그 세계의 안전은 전적으로 소수의 불규칙성에 의존하게 됩니다. 누군가가 소수에 존재하는 밝혀지지 않은 질서를 발견하게 된다면 그는 우주의 비밀까지는 아니더라도 이 세상 모든 사람의 비밀을, 어쩌면 이 세상 모든 사람의 돈까지도 손에 쥐게 될 것입니다. 물론 이 세상에는 대재앙이 되고 말 것입니다.
덧붙임
2001. 6. 28.자 동아일보에 "타원곡선 암호체계 뜬다"라는 제목에 "소수암호 해독 길 열려 30년 독점 끝 "이라는 부제를 단 기사(현재는 http://www.donga science.com/에서 보실 수 있는데, 시일이 지나면 회원가입을 하셔야 볼 수 있습니다)가 실렸기 때문에 이 글을 보완할 필요가 생겼습니다. 위 기사를 쓴 기자는 동아사이언스 기자인데 암호에 많은 관심을 갖고 있는 것 같고 저보다는 더 전문적인 지식을 갖고 있는 것 같습니다. 이 기사는 "도너츠 암호로 불리는 '타원곡선 암호'가 암호계의 터주대감인 소수 암호에 강력한 도전장을 던지고 있다. 도너츠 암호는 25∼27일 고등과학원에서 열린 암호론 학술대회에서 논문 발표의 60~70%를 차지할 정도로 뜨거운 관심을 모으는 등 암호의 역사를 고쳐 쓰고 있다" 그리고 이어서 "99년 네덜란드 학자들이 소수 암호칩을 해독하면서 난공불락의 성이 무너졌다. 이들은 당시 소수암호칩 제조 회사에서 2,000달러의 상금을 받기도 했다"라고 적고 있습니다.
위 기사를 기회로 수학에 관한 조금 더 전문적인 언급을 하겠습니다.
이 글에서도 소수를 찾아내는 방법으로 타원함수를 이용하는 방법이 있다는 언급을 하였습니다. 고등학교 수학을 공부한 사람은 누구나 알다시피 방정식은 함수로 표현될 수 있고 함수는 그래프상의 자취로 형상화될 수 있습니다. 따라서 타원방정식, 타원함수, 타원곡선은 모두 수학적 동의어로 사용될 수 있습니다. 19세기 수학을 거치면서 정수론에서는 밝혀질 수 있는 것은 모두 밝혀졌기 때문에 더 이상의 새로운 발견은 없을 것이라는 예상도 있었습니다만, 20세기에 들어 정수론은 그 예상을 뒤엎고 새로운 발전을 거듭하였는데 그 중 많은 것이 타원곡선과 관련됩니다.
위 글에서도 언급하였던 프랑스의 판사 겸 수학자 Fermat는 바셰가 프랑스어로 번역한 Arithmetica(디오판토스의 저술로서 총 13권 중 6권만이 전해지고 있습니다. 유클리드의 The Elements에 비견되는 중요한 저술입니다) 8번 문제 여백에 다음과 같은 주석을 달았습니다.
"임의의 세제곱수는 다른 두 세제곱수의 합으로 표현될 수 없다. 임의의 네제곱수 역시 다른 두 네제곱수의 합으로 표현될 수 없다. 일반적으로 3 이상의 지수를 자진 정수는 이와 동일한 지수를 가진 다른 두 수의 합으로 표현될 수 없다."
그리고 그는 이어서 장난기 어린 다음과 같은 주석을 붙였습니다.
"나는 경이적인 방법으로 이 정리를 증명하였다. 그러나 책의 여백이 너무 좁아 여기에 옮기지는 않겠다,"
이 정리(또는 추측)가 300년 이상 전세계의 수많은 수학자들의 자존심을 여지없이 짓밟아 놓은 "페르마의 마지막 정리(Fermat's Last Theorem)"입니다.
"페르마의 마지막 정리"는 많은 일화를 남겼는데 다음과 같은 믿어지지 않은 이야기도 있습니다.
독일 다름슈타트 출신의 실업가인 Paul Wolfskehl은 실연으로 상심하여 자살을 결심하였습니다. 그는 먼저 죽기에 알맞은 날과 시간을 정한 후 모든 업무를 정리하고 가족들과 친구들에게 남기는 편지를 일일이 작성하였습니다. 마지막 편지를 마무리짓고 시계를 보니 아직도 자살할 시간에 몇 시간이 남아 있었습니다. 그는 자살 시간에 맞추기 위하여 서재에서 수학서적을 뒤적이다가 페르마의 마지막 정리에 관한 쿰머의 논문을 읽기 시작했습니다. 수학에 상당한 조예를 갖고 있던 그는 당 시대 최고수준의 수학자인 쿰머의 논문에 오류가 있음을 발견하고 이에 몰두하였습니다. 그 사이에 자살시간을 훨씬 지나 동이 트고 말았습니다. 결국 그는 생에 새로운 의미를 찾아 자살을 포기하는 대신 자신의 재산 대부분인 10만 마르크를 페르마의 마지막 정리를 증명하는 자에 대한 상금으로 기부하였습니다. 그 때가 1908년이었는데 위 상금을 기부 받은 괴팅겐의 왕립과학원은 2007. 9. 13.을 시한으로 한 현상광고를 하였습니다.
1997. 6. 27. 위 상금은 수많은 수학자들의 박수를 받으면서 그리고 또 다른 많은 수학자들의 아쉬움 속에, 그리고 전 세계 아마추어 수학자들의 허탈감을 뒤로 한 채 영국의 수학자 Andrew Wiles(와일즈)에게 수여되었습니다.
페르마의 마지막 정리의 증명을 담은 그의 논문은 "Modular elliptic curves and Fermat's last theorem"(우리말로 변역하면 "모듈형식의 타원곡선과 페르마의 마지막 정리"가 될 것입니다)라는 제목으로 "Annals of Mathematics" 141권 3호(1995. 3.)에 게재되었습니다. 위 잡지는 1884년 발간을 시작하여 현재는 미국 프린스턴 대학과 고등학술원(the Institute for Advanced Study)에 의하여 발간되고 있는 수학전문학술지입니다. ID가 없으면 그 내용에는 접근할 수 없지만 http://www.math.princeton.edu/~annals/으로 찾아가시면 보다 상세한 정보를 얻을 수 있습니다.
암호를 말하다가 갑자기 왜 페르마의 마지막 정리를 장황하게 언급하였는가 그 이유를 말하면 페르마의 마지막 정리에 나온 문제는 정수론의 문제이면서 타원방정식 문제이고 동시에 modue 수학과 관련되기 때문입니다(module 수학이 타원곡선과 연결된 것은 일본의 수학자인 타니야마와 시무라의 업적입니다). Andrew Wiles의 증명은 정수론과 타원곡선과 module 수학을 하나로 엮은 대통일 수학의 출발점으로 평가됩니다.
본론으로 돌아가 보면, 저는 타원곡선이 정확히 어떤 알고리즘을 사용하여 암호화와 복호를 수행하는지 알지 못합니다. 더욱이 그 암호 시스템이 대칭암호시스템인지 비대칭암호시스템인지(RSA처럼 암호화 key와 복호 key가 다른 시스템을 비대칭암호시스템이라고 합니다)도 알지 못합니다. 다만 타원곡선은 너무나 다양하고 비정형적이기 때문에(다양한 타원곡선 사이의 공통적 성질이 밝혀지지 않았다는 의미입니다) 암호에 사용될 수 있는 가능성은 오래전부터 제기되어 왔습니다.
다만 위 기사는 "1999년 네덜란드 학자들이 소수암호칩을 해독하면서 난공불락의 성이 무너졌다"라고 적고 있는데 이에 대한 상세한 정보가 없어서 네덜란드의 학자들이 소수암호칩의 내용을 disassembling하는 데에 성공하였다는 것인지 아니면 N을 p와 q로 소인수분해하는 데에 성공하였다는 것인지 알 수 없습니다. 만일 후자라면 RSA 시스템의 보안성에 큰 문제가 되는 것이고, 전자라면 큰 문제가 아닙니다. RSA 시스템은 key 생성 시스템, 암호화 시스템, 복호 시스템의 3 시스템으로 구성될 수 있습니다.
참고로 위에서 소개한 PGP는 초보적인 RSA 시스템이므로 3 시스템이 하나의 프로그램에 포함되어 있을 뿐입니다. RSA 시스템에서 p와 q는 key 생성 시스템에만 들어가 있을 뿐 암호화 시스템과 복호 시스템에는 들어가 있지 않기 때문에 암호화 시스템과 복호 시스템이 disassembling되는 것만으로는 N만을 알려질 뿐이고 key 생성 시스템이 유출되지 않는 이상 N을 소인수 하는 방법 외에는 p와 q를 알 수 있는 방법이 없습니다.
이후에라도 보다 상세한 추가적인 정보를 접하게 되면 이 글을 보완하기로 약속하고 이만 줄이겠습니다.
(법원 웹진)
덧글쓰기 | 엮인글 쓰기 이 포스트를..
muse1472 ⓜⓤⓢⓔ①④⑦② RSA 알고리즘 개요
muse1472 ⓜⓤⓢⓔ①④⑦② RSA 알고리즘 개요
▲ 이전글 - 베다 수학 (Vedic Maths) 전체 포스트 보기
▼ 다음글 - 백년에한번나올까말까한영웅(박정희)
//
#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
/*
2005/03/25 bro 조경민 (bro@shinbiro.com)
RSA Algorithm For understanding
===================================================
목적 : 간단한 상황을 만들어 RSA 알고리즘을 이해
용어 : RSA - 정수론을 이용하여 만든 공개키 알고리즘
공개키 알고리즘 - 데이터를 보낼 때 상대방의 공개키로 암호화 하여
보내면 상대방은 암호문을 자신이 갖고있는 개인키로
복호화하여 데이터를 받을 수 있는 알고리즘
공개키 - 암호화하는 키로 평문(Plain Text)를 암호문(Cipher)로 만듬
개인키 - 보곻화하는 키 또는 비밀키로 암호문을 평문으로 만듬
----------------------------------------------
기본지식 : 정수론
약수 - 어떤 수가 작은수의 곱으로 표현될때 이 작은수를 약수라함
Ex) 12 = 1,2,3,4,6,12 는 약수
공약수 - 두 수의 약수중 서로 같은 약수
Ex) 12 = 1,2,3,4,6,12 8=1,2,4,8 일때 공약수 1,2,4
최대공약수 - 두 수의 약수중 가장큰 약수gcd로 표현 gcd(12,8) = 4
유클리드 호제법 - 최대공약수를 구하는 방식 gcd(큰수,작은수) = gcd(작은수,큰수/작은수의 나머지)
gcd(100,86) = gcd(86,14) = gcd(14,4) = gcd(4,1) 이므로 최대공약수는 4
서로소 - 서로 공약수가 1밖에 없음 Ex) 23, 11은 서로소
----------------------------------------------
설명 :
임의의 두 소수 p와 q가 있을때
p * q = N
( p - 1 ) * ( q - 1 ) = z
이 때, z와 E는 서로소이며 E < z 여야 함
공개키는 (N,E)
E와 D를 곱한 것을 z로 나눈 나머지가 1일 때
E * D = 1 ( mod z )
개인키는 D
상황 : 키와 plain 은 모두 작은 값이다.
plain은 N을 넘을 수 없다.
개선사항 : Big Number지원
소수 찾기 알고리즘
알고리즘 최저화
*/
// 최대공약수를 구하는 유클리드 호제법
// gcd(100,86) = gcd(86,14) = gcd(14,2) = gcd(2,1)
// 리턴이 1이면 서로소
int gcd(int max, int min)
{
if( min == 0 )
return max;
else
return gcd( min, max%min );
}
// 서로소인 수를 찾는 함수
// 최대공약수가 1이면 서로소이다.
int disjoint( int z, int _E = 2 )
{
int E;
for( E = _E; E < z; E++ )
{
if( gcd( z, E ) == 1 )
return E;
}
return 0;
}
// 공개키 (pN, pE) 개인키 (pD) 를 찾는 함수
// 초기 소수 p와 q는 입력해주어야 한다. (개선의 여지가 있음)
int get_keys( int p, int q, int* pN, int* pE, int* pD )
{
int N,z,E,D;
// 먼저 N, z, E를 마련한다.
N = p*q;
z = (p-1)*(q-1);
// 공개키를 구하자.
// E는 z보다 작은 서로소이다.
E = disjoint( z );
// 개인키를 구하자.
// E*D = 1 ( mod z )
// E*D/z 로 나눈 나머지는 1
while( E > 0 && E < z )
{
// 공식을 만족하는 개인키 D를 계속 찾아본다.
for( D = 2; D < z ; D++ )
{
if( (E*D)%z == 1 )
{
// 개인키를 찾았다.
*pN = N;
*pE = E;
*pD = D;
return 1;
}
}
// z와 다음 서로소를 구한다.
E = disjoint( z, E+1 );
}
return 0;
}
// plain과 공개키 (N,E)로 암호화 하는 함수
// plain을 E번 곱하되, 곱한 중간 값이 N을 넘으면
// N으로 나눈 나머지로 만들어준다. ( N으로 계속 빼주는 방식도 된다)
int encrypt( int plain, int N, int E )
{
int enc = 1;
for( int i = 0 ; i < E; i ++ )
{
enc = enc*plain;
if( enc > N )
enc = enc % N;
}
return enc;
}
// 암호문과 개인키 (N,D)로 암호를 푸는 함수
// encrypt와 동일하다.
int decrypt( int enc, int N, int D )
{
int plain = 1;
for( int i = 0 ; i < D; i ++ )
{
plain = plain*enc;
if( plain > N )
plain = plain % N;
}
return plain;
}
int _tmain(int argc, _TCHAR* argv[])
{
printf("100과 84의 최대공약수 = %d \r\n", gcd( 100, 84) );
printf( "24 와 서로소인 수는 = %d \r\n" , disjoint( 24 ) );
int N,E,D;
get_keys( 5,7, &N, &E, &D );
printf( "p=5, q=7 의 공개키(N,E)=(%d,%d) 비밀키D=%d \r\n", N, E, D );
int plain = 13;
int enc = encrypt( plain, N, E );
int dec = decrypt( enc, N, D );
printf( " plain = %d encrypt(plain,N,E) = %d , decrypt(enc,N,D) = %d \r\n" , plain, enc, dec );
getch();
return 0;
}
------------------------------------------------------------------
네이버 지식인 발췌
정수론이 발달함에 의해서 혁신 적인 보안 시스템이 만들어 졌죠.. DES 시스템의 단점을 보완한 공개키 시스템 RSA는 상당히 큰 정수의 소인수분해가 힘들다는 점을 이용해 만들었습니다. R. Rivest, A. Shamir, L. Adleman 의 첫 글자를 따서 붙였다고 배웠습니다. 오일러 파이함수나, 일차 합동식, 유클리드 알고리듬 정도는 이해 하셔야 할 것입니다.
1) 적당히 비슷하고 큰 소수 p, q를 구합니다.
2) 공개키 n을 생성합니다. (n=pq)
3) φ를 구합니다. φ = (p-1)(q-1)
4) 최대공약수 gcd(s,φ)=1을 만족하는 즉 서로 소인 또다른 공개키 s를 생성합니다. 1< s < φ
5) 유클리드 알고리듬을 이용하여 비밀키 d를 만듭니다. d = s^-1 (mod φ) (sd≡1 (mod φ) 를 구하는 것이지요. 무엇을 선택하든 상관없습니다.) 를 구하는 것이지요. 1< d < φ
※ 확장된 유클리드 알고리듬으로 정수 d를 구하는 법
t_0 = 0
t_1 = 1
t_j = t_(j-2)-q_(j-1)t_(j-1) mod r_0 (단, j≥2)
위 방법을 이용하여 d를 구한다.
암호화) n보다 작은 수로 메세지 M을 정한 다음,암호문 c = M^s (mod n) 을 계산하여 암호문 c를 보낸다.
복호화) M = c^d (mod n)을 사용해 복호한다.
이렇게 쓰기만 하면 잘 모르니, 예를 들어보지요.
1) 소수 5와 7을 골랐습니다.
2) 공개키 n=35를 만들었지요.
3) φ=24를 구했습니다.
4) 24와 서로소인 11=s를 구했습니다.
5) 현재 공개키 (n,s) = (35,11)을 구했지요
6) 비밀키 d를 구합니다.
d = 11^-1 (mod 24)
확장된 유클리드 알고리듬의 적용.
11^-1 (mod 24) --- 주어진 식
24 = 2*11+2(=r1)
--- 이것은 이해 하죠? 24(=n)를 앞의 11(=s)로 나누어 몫과 나머지 형태로 나타낸 것입니다. n = q(=몫)*s+r1(=나머지1)
(t_2)0-2*1 (mod 24) = -2 (mod 24) = 22(=r2) (mod 24)
--- 여기도 쉽습니다.t_(2-2)=0이므로 0-2(=q)*1(t_(2-1)=1) (mod 24) = -2 (mod 24) = 24-2 (mod 24) = 22 (mod 24)
11 = 5(=q2)*2(r1)+1(r3)
---s를 앞에서 나온 나머지 r1으로 나눈 것이죠. 검산식 형태.. (현재 여기서는 나머지가 1이 나왔기 때문에 유클리드 알고리듬은 끝이 난 것입니다.)
(t_3)1-22*5 (mod 24) = -109 (mod 24) = 11 (mod 24)
--- 1(=t_(3-2)) - 22(r2)*5(q2) (mod 24) = -109 (mod 24) = 24*5-109 (mod 24)=11(mod 24)
따라서 d = 11.
암호화) 메세지 3을 암호화 해본다. 암호문 c = 3^11 (mod 35) = 12
복호화) 암호문 12를 복호화 해본다. 메세지 M = 12^11 (mod 35) = 3.
복호화가 제대로 되었죠.. 확장된 유클리드 알고리듬을 적용할 때, 나머지가 1이 나올 때까지 계속 반복하시면 됩니다.
죄송합니다.암호화 된 것이 복호화 되는 과정의 증명까지는 지금 시간이 다되서 다 못쓰겠네요. 도움이 되셨기를..
(φ는 사실 φ(n)을 뜻하는 오일러 함수 값입니다.)
(http://203.253.25.15/~mhkim/c200012/rsa.ppt 를 가보면 설명이 자세히는 되지 않았지만 많은 예를 볼 수 있습니다.)
-----------------------------------------------------------------------
서로소 [relatively prime/disjoint]
요약
1 이외에 공약수를 갖지 않는 두 자연수.
본문
예를 들면 두 자연수 4와 9는 서로소이다. 즉 4의 약수는 1, 2, 4이고 9의 약수는 1, 3, 9이므로 두 수의 공약수는 1밖에 없다. 마찬가지로 7과 13, 또는 20과 21, 또는 33과 98 등이 서로소이다. 두 수가 서로소인가를 알아보는 데에는 유클리드의 계산법을 많이 사용한다. 일반적으로 두 다항식 f(x)와 g(x)가 공통인수를 갖고 있지 않을 때 f(x)와 g(x)는 서로소라고 한다. 또 두 집합 A와 B에 공통으로 속하는 원소가 없을 때, 즉 A∩B＝Ø일 때 집합 A와 B는 서로소라고 한다. 예를 들어 A=｛1, 2, 3｝이고 B=｛4, 5｝일 때 A와 B는 서로소이다. 이것을 벤다이어그램으로 나타내면 집합 A와 B가 서로 겹치는 부분이 없이 떨어져 있다.
----------------------------------------------------------------------
유클리드 호제법은 최대공약수를 구할때 사용합니다.
A,B의 최대공약수를 G라 할때
A=Ga, B=Gb(a,b는 서로소)로 나타낼 수 있습니다.
A=BQ+R에 A=Ga, B=Gb를 대입하면
Ga=GbQ+R
R=G(a-bQ)인데
a-bQ와 Gb는 서로소이므로(왜냐면 a,b가 서로소이므로)
B와R의 최대공약수도 G가 나옵니다.
요약하자면
A와B의 최대공약수가 B와 R(A를B로 나눈 나머지)의 최대공약수와 같다는것입니다.
--------------------------------------------------------------------------
최대공약수 [最大公約數, greatest common measure]
요약
2개 이상의 수의 공약수 중에서 최대인 것.
본문
이를테면, 18의 약수는 1, 2, 3, 6, 9, 18 12의 약수는 1, 2, 3, 4, 6, 12 로서 6이 최대공약수이며, 이것을 (12,18)＝6으로 쓴다. 다른 공약수는 모두 6의 약수이다, 최대공약수를 구하는 방법은, 우선 소인수(素因數)로 분해하여 공통의 수를 택하여 곱해주면 된다. 예를 들면 (12,18)을 구할 경우 12＝2×3, 18＝2×3이므로 (12,18)＝2×3＝6이 된다. 또, 주어진 수가 커서소인수분해하기 곤란할 때에는 유클리드의 호제법을 이용하는 것이 더 간편하다.
두 수 A,B의 최대공약수를 G, 또 A,B를 각각 G로 나누었을 때의 몫을 a,b라 하면, A＝aG, B＝bG인 관계가 성립한다. 이 때 a, b는 서로 소(素), 즉 (a,b)＝1이다. 또 A,B의 최소공배수가 L이면, LG＝AB인 관계가 성립한다. 세 수의 경우 (A,B,C)＝((A,B),C), 즉 두 수의 최대공약수와 나머지 한 수의 최대공약수를 구하면 결국 세 수의 최대공약수가 된다. 네 수 이상에서도 마찬가지로 생각할 수가 있으며, 최소공배수에서도 ［A,B,C］＝［［A,B］,C］가 성립한다.
----------------------------------------------------------------------------
소인수 [素因數, prime factor]
요약
인수 중에서 소수(素數)인 것.
본문
예컨대, 12의 약수 1, 2, 3, 4, 6, 12 중에서 2와 3은 소수이지만, 1, 4, 6, 12는 소수가 아니다. 따라서 12의 소인수는 2와 3이다.
----------------------------------------------------------------------------
약수 [約數, divisor]
요약
어떤 수를 나누어 떨어지게 할 수 있는 수.
본문
즉 정수(整數) a가 둘 이상의 정수의 곱으로 표시되어 a=b ·c ·d ·…가 될 때 b,c,d,…를 각각 a의 약수 또는 인수(因數)라 한다. 이것에 대하여 a를 b,c,d,… 등의 배수라고 한다. 예를 들면, 12＝1×2×6=4×3이므로 1,2,3,4,6,12는 각각 12의 약수이고, 또 12는 1,2,3,4,6,12의 각각의 배수이다.
0이 아닌 수의 배수는 무수히 많으며, 약수는 한정되어 있고, 0은 모든 수의 배수이나 어떤 수의 약수는 되지 않는다. 0이 아닌 수는 그 수 자신의 배수인 동시에 약수도 된다. 또, 다항식(多項式) f(x)도 f(x)＝h(x) ·g(x) · …와 같이 둘 이상의 식으로 분해가 될 때 h(x), g(x) 등을 각각 f(x)의 약수 또는 인수라 한다. 예를 들면, (x＋1)(x＋2)는 x(x＋1)(x＋2)2의 약수 또는 인수이다.
------------------------------------------------------------------------
공약수 [公約數, common divisor]
요약
2개 이상의 정수, 또는 다항식에 공통인 약수.
본문
즉, 정수 m이 2s 이상의 정수 a1,a2,a3,…,as의 각각의 약수가 될 때, 이를 m을 a1,a2,a3,…,as의 공약수라 한다.
이를테면, 6은 3개의 정수 24,36,60의 공약수이다. 또, 18의 약수는 1,2,3,6,9,18이며, 12의 약수는 1,2,3,4,6,12이다. 이 중에서 공통인 약수는 1,2,3,6이므로 1,2,3,6은 18과 12의 공약수이다.
공약수 중에서 가장 큰 공약수를 최대공약수라 하고, 보통 G.C.M.으로 나타낸다. m이 a1,a2,a3,…,as의 공약수이면, m의 약수 역시 a1,a2,a3,…,as의 공약수이다. 다항식에서도 정수에서와 마찬가지로 공약수라는 말을 쓴다.
즉, 변수 a1,a2,a3,…,as의 다항식 f(x1,x2,…,xn)가 2개 이상의 다항식 g1(x1,x2,…xn),…, gs(x1,x2,…,xn)의 각각을 나누어 떨어지게
-----------------------------------------------------------------------
[답변] 유클리드 호제법에 관하여... 푸른하늘
휴............
또 요즘 내 주는 수행평가가 그런 건가보죠?
아니면, 한 분이 계속 이름 바꿔가며 올리시는 건???!!! ^.^
농담이구요, 암튼, 너무 많은 분이 올리시네엽. 수행평가마저도 획일적 교육이 되다니...
유클리드 호제법에 관해 간단히 설명드리겠습니다.
목적은 두 수의 최대공약수를 찾아내는 겁니다. 계산이 여러분이 이미 배운 최대공약수 구하는 방법에 비해 그렇게 효율적이지는 않지만, 단순한 계산의 반복이기 때문에 컴퓨터에서 잘 사용되는 알고리즘이기도 합니다.
원리는 다음과 같습니다.
A=BQ + R 의 관계가 성립할 때
A와 B의 최대공약수는 B와 R과의 최대공약수와 같다는 원리입니다. 한 번 증명해 보겠습니다.
A와 B의 최대공약수를 G라고 하면 각각 A=aG, B=bG (단, a, b는 서로 소)라고 쓸 수 있습니다. 그러면 위의 식은 다음과 같이 됩니다.
aG = bGQ + R
(a-bQ)G = R
좌, 우변 모두 정수이므로, R은 G의 약수여야 합니다. 이상으로 증명이 끝났습니다.
계산법은 뭐냐면요, 뭐, 위의 원리를 그대로 쓰는 거지만... 두 수의 최대공약수를 구할 때, 작은 수와, 나머지와의 최대공약수를 구한다고 생각하시면 됩니다. 음... 100과 60의 최대공약수를 유클리드 호제법으로 구하면,
100 = 60 * 1 + 20 이니까 (60, 20)을 생각해보면 됩니다.
60 = 20 * 3 이므로 최대공약수는 20이 됩니다.
우.... 너무 쉬운 예를 들어서... 다른 거 하나 더 해볼까요? 100하고... 84로 해 볼까요?
100 = 84 * 1 + 16 --- (100,84) = (84,16)
84 = 16 * 5 + 4 ----- (84, 16) = (16, 4)
16 = 4 * 4
그러므로 (100, 84) = 4가 되겠군요.
유클리드 호제법은 단순한 계산 방법으로 인해, 단순히 두 수만이 아니라 두 다항식의 최대공약수를 구하는데도 강력한 힘을 발휘합니다.
--------------------------------------------------------
http://blog.naver.com/muse1472/120010861477
내 블로그에 담기
카페에 담기
프린트 하기
스크랩 : 금지됨
카페에 담기
오픈사전에 등록
프린트 하기
스크랩 : 금지됨
카페에 담기
프린트 하기
목록보기 | 컴관련__________▣ (62) 스크랩 엮인글 목록열기 ▼ 목록닫기 ▲
RSA 알고리즘 개요 | ▣ 컴 관련 2005/03/07 09:42
http://blog.naver.com/muse1472/120010861477
인터넷과 암호
컴퓨터에 조금만 관심이 있는 사람이면 누구나 인터넷으로 오고가는 각종 정보에 암호가 사용되고 있다는 것을 알고 있습니다. 인터넷 세계를 열심히 서핑하는 사람이라면 어쩌면 PGP(Pretty Good Privacy)라는 암호 프로그램을 알고 있을지 모릅니다.
좀 더 관심이 있는 사람이라면 PGP의 암호화 알고리즘이 전자상거래, 금융, 전자서명 등의 보안에 사용되고 있는 RSA라는 수학적 알고리즘이라는 것까지도 알고 있을 것입니다. 그러나 수학이나 암호에 전문적인 지식이 없다면 그 RSA에 의한 암호화와 복호의 비밀을 알고 있는 사람은 아마도 흔치 않을 것입니다. RSA가 대체 무엇이며, 왜 그것이 마법의 암호라고 불리울까? 이 글은 이러한 궁금증에 대한 초보적인 대답을 드림으로써 아마추어의 지적 호기심에 부응하고자 하는 목적에서 작성하였습니다.
잠그는 열쇠와 여는 열쇠가 다른 암호
암호화(encoding, enciphering, cryptography, encryption)는 흔히 자물쇠를 채우는 행위, 반대로 복호(decoding, decryption)는 자물쇠를 여는 행위에 비유되곤 합니다. 이 때문에 암호화와 복호에 사용되는 수단을 key라고 부르고, 그것이 문장이나 숫자인 경우에는 keyword라고 부릅니다. 우리가 "종합판례정보시스템"에서 검색용으로 사용하는 주제어를 의미하는 keyword와는 물론 다른 의미의 keyword입니다.
1976년 어쩌면 1978년 이전까지 암호화의 key와 복호의 key는 항상 동일한 것이었습니다.복호 작업은 언제나 암호화 작업을 반대방향으로 되풀이하는 것이기 때문에 복호를 위해서는 반드시 암호화에 사용된 key와 동일한 key가 필요하고 이것이 보통사람들의 상식에 부합하는 것입니다.
그런데 만일 잠그는 key와 여는 key가 다르다면, 잠그는 key로 암호화하고 나면 그 key로는 복호할 수 없고 반드시 또 다른 key가 있어야만 열 수 있다면 무척 편리할 것입니다. 여러분은 그 여는 key를 일반에 공개하고 여러분에게 보내는 편지를 그 공개 key로 암호화할 것을 요구할 수 있을 것입니다. 일단 암호화된 편지는 여는 key를 갖고 있는 당신 외에는 이 세상 누구도, 심지어는 그 암호문을 작성한 사람까지도 열어 볼 수 없을 것입니다.
또 이런 경우도 있을 수 있습니다. 먼저 A회사가 많은 고객의 신용정보(예컨대 비밀번호)를 보관하고 있다고 가정해 봅시다. A회사의 컴퓨터 어딘가에는 그 많은 고객들의 신용정보가 들어 있을 것이고, 그 정보가 유출될 경우 A회사는 엄청난 손해배상책임을 부담하게 될 위험성이 있습니다. 그래서 A회사는 이 평문(plain text, 암호화하기 전의 자료를 지칭합니다)으로 된 신용정보를 암호화하여 저장한 후 평문을 폐기하기로 결정하였습니다. 그런데 문제가 생겼습니다. 암호화와 복호 작업을 위하여 key를 컴퓨터 어딘가에 보관해 두어야겠는데 그 key가 암호화된 정보와 함께 유출되면 역시 엄청난 손해배상책임을 부담하게 될 것이기 때문입니다.
결국 A회사는 다음과 같은 보안 시스템을 생각해 내었습니다. 고객과 거래를 시작할 때 잠그는 key와 여는 key를 만들어 여는 key를 고객의 카드에 기록하고, 회사의 컴퓨터에는 잠그는 key와 그 key로 암호화된 정보만을 기록해 두기로 하였습니다(평문 정보는 고객의 머리에 기록되어 있습니다). 이렇게 되면 암호화 작업이 끝난 후에는 A회사 스스로도 평문 정보를 알 수 없게 되기 때문에 암호화된 정보와 잠그는 key가 사고로 유출되더라도 고객들에게 피해를 줄 염려가 없게 됩니다.
그런 후에 인출작업의 순서는 다음과 같습니다. 고객이 A회사의 단말기에 카드를 삽입하고 keybord를 이용하여 평문 정보를 입력하면 단말기는 주(main) 컴퓨터로부터 암호화된 고객의 정보를 제공받고 고객의 카드로부터는 고객의 여는 key를 제공받아 이 key를 사용하여 암호화된 고객 정보를 평문 정보로 복호한 후 고객이 입력한 평문 정보와 비교합니다. 이것이 일치하면 인출을 승인하고 이것이 불일치하면 인출을 거부하게 됩니다. 이제 A회사는 여는 key와 평문정보 어느 것도 보관하지 않으면서 고객의 신분을 확인할 수 있게 되었습니다.
물론 고객이 카드와 비밀번호를 함께 분실한다면 고객에게 손해가 발생하겠지만, 첫째 이는 고객의 잘못으로 인한 것이기 때문에 손해배상책임을 부담하지 않을 것이고, 둘째 설사 책임을 부담한다고 하더라도 이는 대규모 정보유출에 비하면 극히 작은 손해이므로 직접 부담하거나 보험에 의하여 보장받을 수 있습니다. 이러한 보안 시스템은 이미 만들어져 있고 멀지 않은 장래에 IC카드의 보급과 함께 실용화될 것으로 예상됩니다. 어쩌면 이미 실용화되었는지도 모릅니다.
이러한 암호체계가 실제로 가능할까요? 개념상으로야 이러한 암호체계의 가능성이 오래 전부터 제기되어 왔고, 1976년 Diffie와 Hellman에 의하여 공개 key 개념이 제안되기는 하였지만, 실용화할 수 있는 최초의 암호 알고리즘은 1978년 MIT 공대 연구팀 소속의 세 학자 Rivest, Shamir, Adleman이 개발한 RSA입니다.
마법의 수 트리플
RSA를 이해하기 위해서는 먼저 RSA가 key로 사용하는 "마법의 수 트리플"를 만드는 방법을 알아야 합니다.
① 먼저 소수(素數, prime number) 2개를 선택하여 p와 q라고 합니다.
② p × q ＝ N의 방법으로 N을 구합니다.
③ (p-1) × (q-1) ＝ z의 방법으로 z를 구합니다.
④ z와 공약수를 갖지 않는 수 하나를 선택하여 E라고 이름짓습니다.
통상의 계산의 편의를 위하여 z보다 작은 수 중 소수 하나를 선택합니다. E는 공개 key(잠그는 key)가 됩니다.
⑤ 비밀 key(여는 key)를 구하는 방법은 조금 까다로운데, 비밀 key를 D라고 할 때 D는 D × E / z의 계산에서 나머지가 1이 남아야 한다.
즉, E × D ≡ 1(mod z)을 충족하여야 합니다.
이 방법에 의하여 공개 key N과 E, 그리고 비밀 key D가 모두 완성이 되었습니다.
다음으로 이 공개 key N과 E를 사용하여 암호화하는 방법은 다음과 같습니다.
① 먼저 평문을 수학계산을 수행할 수 있는 수(number)로 변환하여야 하는데, 컴퓨터에서는 이미 모든 문자와 기호를 수로 변환하여 사용하기 때문에 특별한 작업을 요하지 않습니다.
② 평문숫자를 E번 곱하는데 그 과정에서 나오는 중간 수가 N보다 크면 그 중간 수에서 N을 뺍니다. 그 수가 N보다 크면 몇 번이고 뺄셈을 반복하여 N을 뺍니다. N보다 작은 수가 나오면 이를 다시 평문숫자와 곱합니다. 위 작업을 반복하면 그 결과 N보다 작은 수가 남게 되는데 이것이 암호숫자입니다.
③ 위 ②의 계산결과는 또 다른 방법으로 구할 수 있습니다. 평문숫자를 E번 곱한 다음 N으로 나누면 딱 떨어지지 않고 나머지가 남게 되는데 그 나머지가 바로 암호숫자입니다. 공개 key가 작은 수일 경우에는 ③의 방법이 계산하기 쉽지만 큰 수인 경우에는 ③의 방법으로는 계산이 불가능하고 ②의 방법으로 계산하여야 합니다.
실제 공개 key로는 1억 단위 이상의 수가 계산되는데 ③의 방법으로 이러한 계산을 수행할 수 있는 컴퓨터는 없습니다. 위 ②와 ③의 계산결과가 동일하다는 것은 여러분 각자 증명해 보십시오. 시간을 좀 걸리겠지만 이 글을 읽으시는 분들 정도의 실력이라면 증명할 수 있을 것입니다.
이제 위와 같은 방법으로 만들어진 암호숫자를 공개 key N과 E를 사용하여 평문숫자로 복호할 수 있는지를 생각해 보십시오. 잠시만 생각해 보아도 이것이 불가능하다는 것을 알 수 있습니다.
위 암호숫자를 평문숫자로 복호하기 위해서는 비밀 key D가 필요합니다. 그 복호의 과정은 다음과 같습니다.
① 암호숫자를 D번 곱하는데 한번 곱할 때마다 그 중간수에서 N을 뺍니다. N을 뺀 수가 N보다 크면 그 숫자가 N보다 작아질 때까지 N을 뺍니다.
② 그 중간수가 N보다 작아지면 다시 암호숫자를 곱하고, 이런 계산 방법을 D번 되풀이합니다. 그 결과 N보다 작은 수가 나오는데 그 수가 바로 평문숫자입니다.
이제 여러분은 마법의 수 트리플을 만드는 방법과 그 수를 key로 사용하는 RSA의 연산방법을 알게 되었습니다. 이 시점에서 여러분은 당연히 이러한 의문을 갖게 될 것입니다. 위 연산을 시작하기 전의 평문숫자와 위 암호화와 복호 연산 결과 얻은 숫자가 과연 항상 동일한 숫자일까? 이 의문에 대한 가장 적절한 대답은 위 RSA 연산 값이 참임에 대한 수학적 증명일 것입니다. 그 증명은 너무나도 어렵고 복잡하여 아마추어로서는 이해하기 어려울 뿐만 아니라 증명과정만 하나의 논문 분량이 되므로 이 곳에 소개할 수가 없습니다. 솔직히 말씀드리면 저도 잘 모릅니다.
진짜 비밀은 소수(prime number)의 성질
여러분의 또 다른 의문은 과연 공개 key인 N과 E만으로 암호숫자를 평문숫자로 복호할 수 없는가 하는 것과 N과 E만으로 비밀 key인 D를 알 수 없는가 하는 것일 것입니다.
먼저 첫째 의문은 위에서도 말했다시피 조금만 생각해 보면 금방 그 답이 나옵니다. 암호화 연산을 역산하기 위해서는 암호숫자에 N을 더해야 하는데 당장 처음부터 몇 번을 더해야 할지 알 수 없기 때문에 그 역산은 불가능해집니다. 즉 하나의 해답이 아니라 무한한 경우의 수가 역산으로 도출될 수 있기 때문에 이 연산은 이론적으로도 불가능하다고 할 수 있습니다.
두 번째 의문에 대한 답은 조금 어려워집니다. 가장 타당한 답은 yes and no인데, 이론적으로는 yes(알 수 있다)이고, 현실적으로는 no(불가능하다)라는 의미입니다. 마법의 수 트리플은 일정한 법칙에 의하여 만들어지고 먼저 N과 E가 정해진 후에는 간단한 연산에 의하여 D 값이 쉽게 구해지게 됩니다. 그런데 D 값은 N과 E로부터 곧바로 구해지는 것이 아니라 N의 약수인 p와 q로 결정되기 때문에 p와 q 값을 먼저 알아야만 D 값을 구할 수 있습니다. 어려움은 여기에 있습니다. p와 q는 소수이고 N ＝ p × q인데 아직 우리는 소수에 일반적인 규칙을 알지 못합니다. 대부분의 수학자들은 소수에는 일반적인 규칙이 없을 것으로 생각하기도 합니다.
물론 소수의 규칙과 관련하여 몇 가지 성질이 관찰된 바는 있습니다.
첫째 쌍둥이 소수(prime number twins)라는 것이 있는데 어떤 소수에 2를 더한 수가 역시 소수인 쌍을 말합니다. 예를 들면, 2/3으로부터 시작해서 9,900,0641/9,900,0643과 같은 숫자의 쌍을 말합니다. 수학자들은 그 쌍둥이 수의 개수가 무한할 것으로 추측하는데 아직 이를 증명한 사람은 없습니다.
둘째 "2보다 큰 모든 짝수는 두 소수의 합이다"라는 Christian von Goldbach의 가정(假定, 또는 추측, 수학에서 참임이 증명되지 않았지만 거짓임이 밝혀지지도 않은 명제를 말합니다)이 있는데 이 역시 아직은 증명되지 않았습니다.
셋째, 정수론(number theory) 중 가장 놀라운 정리 중 하나로 꼽히는 소수정리(prime number theorem)가 있습니다. 이 글에서 수학공식을 입력하기가 어려워 소수정리의 내용을 설명하기는 어렵지만, 이 정리 또한 연역적 방식으로 증명된 것은 아니고 컴퓨터에 의한 연산을 통하여 증명되었기 때문에 이 또한 엄격한 의미에서 증명되었다고 할 수는 없습니다(물론 컴퓨터에 의한 증명도 인정하여야 한다는 반대 견해도 있습니다).
이 중 어느 하나만 증명하여도 평생 판결 작성으로 얻을 수 있는 것보다 더 큰 명성을 얻을 수 있고, 전 세계가 인정하는 천재의 대열에 끼어들 수 있습니다. 여러분은 한 번 도전해 볼 생각이 없으신지?
이야기가 엉뚱한 방향으로 흘렀습니다. 각설하고 본론으로 돌아가면, 아주 큰 수의 소수를 구하는 방법은 2부터 시작하여 알려진 모든 소수로 일일이 나누기 계산을 해 보는 방법 외에는 다른 방법이 없습니다. 타원함수를 응용한 계산방법 등이 개발되었으나 아직은 가장 단순한 나누기 계산보다 더 효율적인 계산방법은 발견되지 않고 있습니다.
따라서 아주 큰 소수인 p와 q를 곱하여 더 큰 수 N을 구할 경우 그 N의 약수 p와 q를 알아내는 방법은 역시 2부터 시작한 모든 소수로 실제 나누기 계산을 해 보는 방법밖에 없습니다. N이 50자리만 되면 약 140억번의 계산을 수행하여야 p와 q를 찾아낼 수 있습니다. RSA가 발표된 1978년경의 컴퓨터로는 200자리의 N에서 p와 q를 찾아내기 위해서는 지구의 나이만큼(약 45억년)의 시간이 필요하다고 합니다. 그렇다면 현실적으로 그 계산은 불가능하고 p와 q의 값을 모르는 이상 공개 key D 값도 알 수 없다는 결론을 내릴 수 있습니다.
조금만 더 전문적으로 들어가 보겠습니다. 두 소수의 곱으로 만들어지는 N에 문제가 전혀 없는 것은 아닙니다. 1977년 8월 3명의 수학자가 Scientific American(이 잡지는 영국의 Nature와 더불어 세계에서 가장 유명한 과학전문잡지입니다. http://www.sciam.com/를 찾아가시면 놀라운 지식의 보고를 접하게 됩니다.)에 두 소수의 곱으로 만들어진 129자리의 수를 올려놓고 이 수의 소인수 분해에 100달러의 상금을 걸었습니다. 출제자는 아마도 이 문제를 푸는 사람이 없을 것이라고 확신하였을 것입니다. 그런데 5년 후 1992년 4명의 수학자가 전세계 25개국의 자원봉사자 600명을 모집한 후 인터넷을 통하여 공동작업을 벌인 결과 64자리 수의 소인수를 찾아내고 말았습니다. 참여자들에게 돌아간 상금은 1인당 17센트였다고 합니다.
그런데 같은 해에 Lester와 Bernstein이라는 사람이 단 한 대의 컴퓨터로 3주일간 16만번의 연산을 거듭한 결과 157자리의 숫자를 인수분해하는 데에 성공하였습니다. 엄청난 횟수의 연산이기는 하지만 이 정도의 연산으로 N이 소인수 분해될 수 있다면 RSA는 실용화될 수 없는 믿을 수 없는 암호체계가 되고 맙니다. 그러나 다행히도 그 소인수는 2의 523승에서 1을 뺀 수였는데 2의 n승에서 1을 뺀 소수는 쉽게 계산된다는 것이 알려졌습니다. 그 이후 RSA에 사용되는 N을 만드는 데에는 이러한 수는 제외되게 되었습니다.
실제 사용하는 RSA 시스템은 굉장히 큰 N(큰 경우에는 300자리 이상)을 만들어 1 회사에서 1개의 N을 사용하기도 하는데 이 1개의 수로부터 많은 개수(N이 그렇게 클 경우에는 거의 무한한 개수)의 E와 D를 구하여 고객별로 다른 공개 key와 비밀 key를 제공하는 방법을 사용하고 있습니다. 위험은 피할 수 없는 것이 그 system 어딘가에는 N을 구성하는 p와 q가 들어가 있습니다. 세상에 완벽한 보안이란 역시 존재하지 않는 것 같습니다.
PGP 맛보기
PGP는 Pretty Good Privacy의 약자인데 RSA 팀이 만든 공개 프로그램입니다. 인터넷상에서 이 프로그램을 구할 수 있는 곳은 많습니다. 그 중 한 곳을 소개하면 다음과 같습니다.
http://www.uni-mannheim.de/studorg/gahg/PGP
이 프로그램은 1개의 N을 사용하는데 사용자가 컴퓨터의 지시에 따라 긴 문장을 타이핑하면 그 타이핑 리듬에 따라 E와 D를 결정합니다. 그리고 이를 이용하여 암호화, 복호, 디지털 서명을 할 수 있습니다.
마무리
제가 많은 분들이 생소하게 생각할 분야에 관하여 이런 글을 쓰는 이유 중의 하나는 다음과 같습니다. 현재 디지털 서명 시스템은 RSA에 의존하고 있을 뿐 아니라 다른 대안이 전혀 없기 때문에 우리나라가 디지털 서명 제도를 채택한다면 어쩔 수 없이 RSA에 의존할 수밖에 없습니다. 그 법제도를 만들고 운영해 갈 여러분들이 RSA의 이론적, 기술적 기초를 이해하고 있어야만 RSA의 안전성과 위험성에 대한 정당한 평가를 할 수 있을 것이고, 결국 정당한 정책적 판단을 할 수 있을 것이라고 믿기 때문입니다.
또 다른 이유는 재미 때문입니다. 프랑스의 천재 수학가 Pierre de Fermat(페르마)의 현실세계에서의 직업이 판사였다는 것을 알고 계십니까? 법학이 연구대상으로 삼는 현실세계는 불확정성이론과 chaos이론이 적용되는 복잡계인 반면, 수학이 연구대상으로 삼는 가상의 세계는 지극히 단순한 세계여서 정연한 질서가 있습니다. 질서에는 아름다움이 있습니다. 현실적으로 복잡계에 존재하는 Fermat가 아름다운 질서를 연구하면서 재미를 찾았듯이 이 글을 읽는 분들 중에는 분명히 질서와 논리의 아름다움에 빠지는 재미를 아는 분들이 있을 것입니다.
장차 RSA에 의하여 비밀이 유지되는 세상이 형성되면 그 세계의 안전은 전적으로 소수의 불규칙성에 의존하게 됩니다. 누군가가 소수에 존재하는 밝혀지지 않은 질서를 발견하게 된다면 그는 우주의 비밀까지는 아니더라도 이 세상 모든 사람의 비밀을, 어쩌면 이 세상 모든 사람의 돈까지도 손에 쥐게 될 것입니다. 물론 이 세상에는 대재앙이 되고 말 것입니다.
덧붙임
2001. 6. 28.자 동아일보에 "타원곡선 암호체계 뜬다"라는 제목에 "소수암호 해독 길 열려 30년 독점 끝 "이라는 부제를 단 기사(현재는 http://www.donga science.com/에서 보실 수 있는데, 시일이 지나면 회원가입을 하셔야 볼 수 있습니다)가 실렸기 때문에 이 글을 보완할 필요가 생겼습니다. 위 기사를 쓴 기자는 동아사이언스 기자인데 암호에 많은 관심을 갖고 있는 것 같고 저보다는 더 전문적인 지식을 갖고 있는 것 같습니다. 이 기사는 "도너츠 암호로 불리는 '타원곡선 암호'가 암호계의 터주대감인 소수 암호에 강력한 도전장을 던지고 있다. 도너츠 암호는 25∼27일 고등과학원에서 열린 암호론 학술대회에서 논문 발표의 60~70%를 차지할 정도로 뜨거운 관심을 모으는 등 암호의 역사를 고쳐 쓰고 있다" 그리고 이어서 "99년 네덜란드 학자들이 소수 암호칩을 해독하면서 난공불락의 성이 무너졌다. 이들은 당시 소수암호칩 제조 회사에서 2,000달러의 상금을 받기도 했다"라고 적고 있습니다.
위 기사를 기회로 수학에 관한 조금 더 전문적인 언급을 하겠습니다.
이 글에서도 소수를 찾아내는 방법으로 타원함수를 이용하는 방법이 있다는 언급을 하였습니다. 고등학교 수학을 공부한 사람은 누구나 알다시피 방정식은 함수로 표현될 수 있고 함수는 그래프상의 자취로 형상화될 수 있습니다. 따라서 타원방정식, 타원함수, 타원곡선은 모두 수학적 동의어로 사용될 수 있습니다. 19세기 수학을 거치면서 정수론에서는 밝혀질 수 있는 것은 모두 밝혀졌기 때문에 더 이상의 새로운 발견은 없을 것이라는 예상도 있었습니다만, 20세기에 들어 정수론은 그 예상을 뒤엎고 새로운 발전을 거듭하였는데 그 중 많은 것이 타원곡선과 관련됩니다.
위 글에서도 언급하였던 프랑스의 판사 겸 수학자 Fermat는 바셰가 프랑스어로 번역한 Arithmetica(디오판토스의 저술로서 총 13권 중 6권만이 전해지고 있습니다. 유클리드의 The Elements에 비견되는 중요한 저술입니다) 8번 문제 여백에 다음과 같은 주석을 달았습니다.
"임의의 세제곱수는 다른 두 세제곱수의 합으로 표현될 수 없다. 임의의 네제곱수 역시 다른 두 네제곱수의 합으로 표현될 수 없다. 일반적으로 3 이상의 지수를 자진 정수는 이와 동일한 지수를 가진 다른 두 수의 합으로 표현될 수 없다."
그리고 그는 이어서 장난기 어린 다음과 같은 주석을 붙였습니다.
"나는 경이적인 방법으로 이 정리를 증명하였다. 그러나 책의 여백이 너무 좁아 여기에 옮기지는 않겠다,"
이 정리(또는 추측)가 300년 이상 전세계의 수많은 수학자들의 자존심을 여지없이 짓밟아 놓은 "페르마의 마지막 정리(Fermat's Last Theorem)"입니다.
"페르마의 마지막 정리"는 많은 일화를 남겼는데 다음과 같은 믿어지지 않은 이야기도 있습니다.
독일 다름슈타트 출신의 실업가인 Paul Wolfskehl은 실연으로 상심하여 자살을 결심하였습니다. 그는 먼저 죽기에 알맞은 날과 시간을 정한 후 모든 업무를 정리하고 가족들과 친구들에게 남기는 편지를 일일이 작성하였습니다. 마지막 편지를 마무리짓고 시계를 보니 아직도 자살할 시간에 몇 시간이 남아 있었습니다. 그는 자살 시간에 맞추기 위하여 서재에서 수학서적을 뒤적이다가 페르마의 마지막 정리에 관한 쿰머의 논문을 읽기 시작했습니다. 수학에 상당한 조예를 갖고 있던 그는 당 시대 최고수준의 수학자인 쿰머의 논문에 오류가 있음을 발견하고 이에 몰두하였습니다. 그 사이에 자살시간을 훨씬 지나 동이 트고 말았습니다. 결국 그는 생에 새로운 의미를 찾아 자살을 포기하는 대신 자신의 재산 대부분인 10만 마르크를 페르마의 마지막 정리를 증명하는 자에 대한 상금으로 기부하였습니다. 그 때가 1908년이었는데 위 상금을 기부 받은 괴팅겐의 왕립과학원은 2007. 9. 13.을 시한으로 한 현상광고를 하였습니다.
1997. 6. 27. 위 상금은 수많은 수학자들의 박수를 받으면서 그리고 또 다른 많은 수학자들의 아쉬움 속에, 그리고 전 세계 아마추어 수학자들의 허탈감을 뒤로 한 채 영국의 수학자 Andrew Wiles(와일즈)에게 수여되었습니다.
페르마의 마지막 정리의 증명을 담은 그의 논문은 "Modular elliptic curves and Fermat's last theorem"(우리말로 변역하면 "모듈형식의 타원곡선과 페르마의 마지막 정리"가 될 것입니다)라는 제목으로 "Annals of Mathematics" 141권 3호(1995. 3.)에 게재되었습니다. 위 잡지는 1884년 발간을 시작하여 현재는 미국 프린스턴 대학과 고등학술원(the Institute for Advanced Study)에 의하여 발간되고 있는 수학전문학술지입니다. ID가 없으면 그 내용에는 접근할 수 없지만 http://www.math.princeton.edu/~annals/으로 찾아가시면 보다 상세한 정보를 얻을 수 있습니다.
암호를 말하다가 갑자기 왜 페르마의 마지막 정리를 장황하게 언급하였는가 그 이유를 말하면 페르마의 마지막 정리에 나온 문제는 정수론의 문제이면서 타원방정식 문제이고 동시에 modue 수학과 관련되기 때문입니다(module 수학이 타원곡선과 연결된 것은 일본의 수학자인 타니야마와 시무라의 업적입니다). Andrew Wiles의 증명은 정수론과 타원곡선과 module 수학을 하나로 엮은 대통일 수학의 출발점으로 평가됩니다.
본론으로 돌아가 보면, 저는 타원곡선이 정확히 어떤 알고리즘을 사용하여 암호화와 복호를 수행하는지 알지 못합니다. 더욱이 그 암호 시스템이 대칭암호시스템인지 비대칭암호시스템인지(RSA처럼 암호화 key와 복호 key가 다른 시스템을 비대칭암호시스템이라고 합니다)도 알지 못합니다. 다만 타원곡선은 너무나 다양하고 비정형적이기 때문에(다양한 타원곡선 사이의 공통적 성질이 밝혀지지 않았다는 의미입니다) 암호에 사용될 수 있는 가능성은 오래전부터 제기되어 왔습니다.
다만 위 기사는 "1999년 네덜란드 학자들이 소수암호칩을 해독하면서 난공불락의 성이 무너졌다"라고 적고 있는데 이에 대한 상세한 정보가 없어서 네덜란드의 학자들이 소수암호칩의 내용을 disassembling하는 데에 성공하였다는 것인지 아니면 N을 p와 q로 소인수분해하는 데에 성공하였다는 것인지 알 수 없습니다. 만일 후자라면 RSA 시스템의 보안성에 큰 문제가 되는 것이고, 전자라면 큰 문제가 아닙니다. RSA 시스템은 key 생성 시스템, 암호화 시스템, 복호 시스템의 3 시스템으로 구성될 수 있습니다.
참고로 위에서 소개한 PGP는 초보적인 RSA 시스템이므로 3 시스템이 하나의 프로그램에 포함되어 있을 뿐입니다. RSA 시스템에서 p와 q는 key 생성 시스템에만 들어가 있을 뿐 암호화 시스템과 복호 시스템에는 들어가 있지 않기 때문에 암호화 시스템과 복호 시스템이 disassembling되는 것만으로는 N만을 알려질 뿐이고 key 생성 시스템이 유출되지 않는 이상 N을 소인수 하는 방법 외에는 p와 q를 알 수 있는 방법이 없습니다.
이후에라도 보다 상세한 추가적인 정보를 접하게 되면 이 글을 보완하기로 약속하고 이만 줄이겠습니다.
(법원 웹진)
덧글쓰기 | 엮인글 쓰기 이 포스트를..
muse1472 ⓜⓤⓢⓔ①④⑦② RSA 알고리즘 개요
muse1472 ⓜⓤⓢⓔ①④⑦② RSA 알고리즘 개요
▲ 이전글 - 베다 수학 (Vedic Maths) 전체 포스트 보기
▼ 다음글 - 백년에한번나올까말까한영웅(박정희)
'KB > C/C++' 카테고리의 다른 글
| code profiler (0) | 2006.04.17 |
|---|---|
| 함수 링크 순서 정해주기 (0) | 2005.10.28 |
| [펌] vc 5, 6 stl 버그 픽스 (0) | 2004.09.10 |
| [펌] C++ Reverse Disassembly (0) | 2004.09.10 |
| [stl] 소트 하기 (0) | 2004.03.19 |