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

사실 필자의 수학 공부가 부족하고 배껴 넣기도 귀찮아서 알고리즘의 증명따위는 그냥 넘긴다
그러나 알고 싶은 분들을 위한 링크를 남기겠다
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

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

RSA 키 생성기

조금 버벅이기는 하지만 잘 만들어지는 것 같다
http://hc.pe.kr/

소수 모아논 헤더

그다지 쓸 모 없어 보이긴해도 간단한 용도로나 예제같은걸 해보는데에 쓸만할지도..

요새 공부한.. 공부하고 있는 알고리즘 ' '
대략 간단한 '유클리드 호제법'(Euclid's Algorithm), '페르마의 소정리'(Ferma's Little Theorem) 등을 이용한 소위 매우 간단한 알고리즘.
간단히 설명하면 암호화하는 키와 복호화하는 키가 다른 암호화 방식이랄까..

매우 매력적이다
특히 네트워크 상에서 누군가 패킷을 스니핑 한다 해도 소용이 없다
상당히 재미있다 혹시 모르시는 분들을 위해 설명을 간단히 하고 넘어가겠다

A 와 B 가 있다.
A 는 B 에게 뭔가 암호화된 중요한 자료를 주고 싶다.
A 는 B 에게 키를 달라 한다.
B 하나의 키 쌍을 만들어 암호화 할 수 있는 키를 A 에게 준다. (한 쌍 == 암호화키 + 복호화키)
A 는 B 에게 받은 키를 이용해 자료를 암호화 시킨다.
A 는 암호화 된 자료를 B에게 보낸다.
B 는 받은 암호화된 자료를 아까 자신이 만들었던 키 쌍중 복호화를 위한 키를 사용해 복호화한다

여기서 주고 받은 것을 정리해 보면 다음과 같다
A -> B : 키를 달라는 요청
B -> A : 암호화를 위한 키
A -> B : 암호화된 자료
즉, 복호화를 위한 키가 공개되지 않으므로 B외에는 이 암호화를 풀 수 없다.

근대 한가지 짚고 넘어갈 것이 있다
RSA 말고 다른 수학적 방법들로도 암호화를 위한 키와 복호화를 위한 키를 따로 만들 수 있다
그런데 왜 사용을 않는가??
암호화를 위한 키를 이용해 복호화를 위한 키를 추측할 수 있기 때문이다.
예를 들어 +1 이란 키가 암호화키였다면 복호화키는 -1 이 되는 거다
이것은 알고리즘이 공개되어있기 때문에 당연한 일이다
그런데.. 왜 RSA는 강력하다 하는가??
이는 키를 만드는 방식에 있다 (== 이 말의 뜻이 결국 알고리즘의 전체를 표현하는거겠지만ㅋ)

본론가기
http://2.azki.org/118