아즈키의 블로그 Ver 2006 :: RSA 알고리즘

RSA 알고리즘 - 본론

Computer/속임의 정체 2007. 2. 15. 14:26

저번 서론에 이어 본론을 설명한닷 ㅇ_ㅇ

사실 필자의 수학 공부가 부족하고 배껴 넣기도 귀찮아서 알고리즘의 증명따위는 그냥 넘긴다
그러나 알고 싶은 분들을 위한 링크를 남기겠다
http://wizpia.com/documents/security/guardian4.html

증명을 다 넘기고 과정을 보면 다음과 같다

두개의 소수를 p, q를 구하고서

(p-1)*(q-1) 과 서로소인 수 e를 하나 구한다 이것을 공개키 e라 부르자.

그리고 (e * d) - 1 mod (p-1)*(q-1) = 0 인 d를 구한다. 이것을 비밀키 d라고 하자.

여기에서 왠지 모를 정리에 의해

암호화시킬 코드의 e 제곱을 (p*q)로 나눈 나머지 값과 (p*q)값, 그리고 비밀키 d로 암호화 시킬 코드를 복호화할 수 있다.

즉, 우리가 암호화 할 코드를 n 이라 하고,

n의 e승을 p곱하기 q로 나눈 나머지 값을 m이라 하자

그럼, m의 d승을 p곱하기 q로 나눈 나머지 값이 n이 되는 것이다

정리해보자

일단 p*q 값(p곱하기q)은 복잡하므로 이를 r이라고 부르겠다.

암호화에 필요한 것은 원래 값 n 그리고 공개키 e값과 r값. 그래서 나온 암호문이 m.

복호화에 필요한 것은 암호문 m과 그리고 비밀키 d값과 r값. 그래서 나온 복호문이 n.

상당히 간단하다 일단 단순한 숫자 암호를 암호화하고 복호화하는 것에 몇라인 들어가지않는다

crypt(n, e, r) { return (n^e) mod r; }
decrypt(m, d, r) { return (m^d) mod r; }

물론, 실제로 적용하자면 키 생성부분과 전송하는 부분과 암호화할 데이터를 블럭화하거나.. 어째꺼나 많이 늘겠지만, 원리는 위와 같이 간단하다.

암호의 쓰임새는 서론에서 말했었던거 같다. 음 예제까지 정리하기는 귀찮고..

그냥 몇가지 아마 예제를 구현하며 공부할 사람에게 필요 할지도 모르는 것들을 올려놓겠다..

RSA 알고리즘
꽤나 자세히 설명되어 있다. 웹에 찾아보면 많은데 다 거기서 거기인듯 하다. 나름 수학기호도 깔끔히 되어있다.
http://wizpia.com/documents/security/guardian4.html

RSA 암호 연습
실제로 자바스크립트로 간단한 RSA 암호화-복호화 과정을 실습해 볼 수 있어서 막막하다 싶을때 끄적거리기 좋다. 살짝 예외처리가 안되있는 경우도 있지만 잘 구현해 놓은 것 같다. 다 거기서 거기인 평범한 글로 설명되어 있는 보통의 사이트들과 사뭇 다른 사이트.
http://cissoft.dju.ac.kr/amho/sub/training/rsa.html

BIG_INT_LIB

invalid-file

큰 수를 다루도록 해준다
제곱 연산을 하는만큼 엄청 큰수에 대한 연산이 필요할 수도 있다
사실 글 쓴 녀석은 빅인트 라이브러리에서 제공하는 big_int_powmod() 함수를 이용해 제곱과 모듈러를 구현했다.
http://valyala.narod.ru/big_int/

RSA 키 생성기

invalid-file