- RSA 암호화/복호화.
1). 두 개의 큰 소수 p와 q를 선정한 다음에 법n 과 φn 을 계산한다.
법n = p*q
φn = (p-1)*(q-1)
2). 공개키 e는 φn과 서로 소(素)의 관계가 되게 임의로 선정한다.
3). e*d Mod φn = 1 의 관계에 있는 개인키 d를 유클리드 알고리즘을 통해 구한다.
유클리드 알고리즘 : 두 정수의 최대공약수를 구하는 것은 가장 고전적인 정수론 문제중의 하나이다. 유클리드알고리즘은 최대공약수를 구하는데에 사용되는 가장 효율적인 방법이다.
1). 두 개의 큰 소수 p와 q를 선정한 다음에 법n 과 φn 을 계산한다.
법n = p*q
φn = (p-1)*(q-1)
2). 공개키 e는 φn과 서로 소(素)의 관계가 되게 임의로 선정한다.
3). e*d Mod φn = 1 의 관계에 있는 개인키 d를 유클리드 알고리즘을 통해 구한다.
유클리드 알고리즘 : 두 정수의 최대공약수를 구하는 것은 가장 고전적인 정수론 문제중의 하나이다. 유클리드알고리즘은 최대공약수를 구하는데에 사용되는 가장 효율적인 방법이다.
s = a
t = b
Do While (t > 1)
r = s Mod t
s = t
t = r
Loop
Return(s)
4). {e, n}을 공개키로 공개하고, {d} 는 개인키로 자신이 안전하게 보관한다.
m = 평문, e,n = 공개키, d = 개인키, c = 암호문
Mod 연산 아시죠? 나머지 공식. (2 Mod 3 = 2, 5 Mod 3 = 2, 6 Mod 3 = 0)
RSA 암호화공식 : Ｅke(m) = m^e Mod n = c
RSA 복호화공식 : Ｄke(c) = ((m^e)^d) Mod n = c^d Mod n = m
예제) n = p * q = 7 * 11 = 77. (큰소수 p와 q를 넣어야되지만 너무크면 시간이 너무 마니걸려서 일단은 작은숫자로 해봅시다.)
φn = (p-1) * (q-1) = 6*10 = 60.
공개키e 는 φn과 서로소의 관계에 있는 임의의 정수 7로 선정한다.
e = 7
따라서, 개인키는 유클리드 알고리즘을 이용하면 개인키d = 43 이 된다.
평문m 을 8로 하고 RSA암호화공식을 통해 암호문을 구해보면
c = 8^7 Mod 77
= 2097152 Mod 77
= 57
(※ 계산기로 직접 해보면 결과가 바로바로 나옴.
계산기를 공학용에 놓고하면 ^연산이나 Mod연산이 있어서 계산해보는게 훨씬 편하기도 함.
암산이 빠르면 직접 하든가.. -.-;)
이제 평문m(=8)이 암호문c(=57)로 암호화되었다.
그렇다면 이제 개인키d(=43)을 사용하여 다시 암호문 c(=57)를 복호화해보면 RSA복호화공식에 따라
m = 57^43 Mod 77
= 3181403788572786716059998378326698266679069780899509454959934125355133265193 Mod 77
= 8
m = 8로 다시 복호화 된다.
(※ 57^43은 계산기가지고 계산이 안된다...암호학(?)에서는 항상 실수가 아닌 정수만을 가지고 해야하기 때문에 계산기로 57^43을 계산하면 3.1814037885727867160599983783267e+75 라고 나와서 계산에 오차가 생겨 정확한 답이 나오질 않는다. 그렇다면 계산을 어떻게 할것인가는 비베로 직접 프로그래밍 해야된다...참고로 마음만 먹으면 몇만자리까지 계산이 가능하다...현재 나는 5000자리까지만 지정해놓고 계산하고 있다...5000자리면 얼마나되지?? 위에 57^43을 계산한것만 해도 정확히 안세어봤는데 75자리정도...눈아
퍼..-.-; 비베로 계산할수 있는 자릿수는 몇자리 안됨...열자리 안넘어갈껄요...아마...)
공개키 암호화란
Alice라는 사람이 위의 e, n, d 를 구해놓고
e와 n을 공개적으로 공개해서
Bob이 공개키e와 n을 이용해 평문m을 암호화해서 Alice에게 보내면
Alice는 개인키 d를 이용해서 암호문c를 복호화해서
평문m을 알아낼수가 있습니다.
만약 누군가 암호문c를 몰래 입수했다고 합시다.
개인키d를 모르는 상태에서 평문m을 구하려고 하면
개인키d를 알아야 복호화를 할수 있는데 개인키를 구하는공식은
(e * d) Mod φn = 1
e는 이미 공개한 상태이므로 알수 있다. 그렇지만 φn의 값은 알수가 없다.
이제 φn의 값을 구해보자.
일단 n의 값을 알고있다. n과 e를 공개했으므로
그렇다면 위의 예제를 보면 n은 77이다. 7 * 11 = 77은 쉽게 구할수 있지만
예제에서는 숫자가 적었지만 숫자가 크다면??? 반대로 구하기는 어렵다.
책에나온 예를 보면
n = 1,807,082,088,687,404,805,951,656,164,405,905,566,278,102,516,
769,401,349,170,127,021,450,056,662,540,244,048,387,341,127,590,
812,303,371,781,887,966,563,182,013,214,880
을 p와 q로 만들수 있겠는가?
1 mips-year는 1초당 1백만개의 명령어를 처리하는 컴퓨터가 1년동안 수행해야하는
계산량을 의미한다. 1983년도에 71자리의 10진수를 소인수분해하는데에는
0.1 mips-year가 소요됐다. 이것은 한대의 CRAY X-MP 슈퍼컴퓨터로 9.5 CPU시간이
소요되는 계산량이다. 5000 mips-year가 소요된 RSA-129의 소인수분해 작업은
인터넷을 통해 전 세계적으로 1600여대의 워크스테이션, 대형컴퓨터, 슈퍼컴퓨터들이
연결되어 소인수분해작업을 분담하여 계산하였다. 전반적인 집계와 분석이 이루어진
가운데 최종작업까지 약 8달이 걸렸다고한다. RSA-130의 소인수분해에는 RSA-129에
소요된 계산량의 10분의 1정도인 약 500 mips-year가 소요됐다.
위의 n값이 RSA-130이다.
그렇다면 위의 n값을 소인수 분해한 p와 q는
p = 39,685,999,456,597,454,290,161,126,161,883,786,067,
576,449,112,810,064,832,555,157,243
q = 귀챦어용... -.-;;
이정도...그래서 반대로 계산하는것을 언제하겠는가~
늙어 죽어도 자손이 계산을 해야하고 그 자손에 자손이... -.-;;
이래서 암호화를 하기는 쉽지만 복호화하기 어렵다고 한다...
하지만 RSA암호화/복호화방법은 계산하는데 시간이 많이걸려서 피곤하다.
공개키를 설명하다 다른데로 흘렀군요..
아무튼 이렇게 자신만의 공개키를 공개하고 누군가가 암호화해서 보내면
자신은 개인키로 간단히 열어서 볼수 있게 하는 암호화 방법을
공개키암호화라고 합니다.
출처: http://blog.naver.com/shu777/120005550944
