RSA 공개키 암호화

요즘 암호학 책을 다시 읽고있는데 정보가 머리속에서 맴도는 것 같다. 그래서 정리할겸 쓴다.

RSA는 무엇일까?
큰 수의 소인수분해의 어려움을 이용하여 만든 공개키 알고리즘 중 하나로 최초의 전자서명이 가능한 알고리즘이라고 한다! 공개키로 평문을 암호화하면, 개인키로만 평문을 복호화 시킬 수 있다. 참고로 RSA라는 이름은 연구자의 이름의 앞글자를 따온것이라고 한다.(Rivest, Shamir, Adleman)

RSA의 키 생성
1) 서로 다른 두 소수 p,q를 결정
2) p*q의 값을 갖는 n을 구한다
3) (p-1)*(q-1)=Ø(n)값을 구한다.
4) 1<e<Ø(n) 범위를 만족하는 e값을 구한다.5) 합동식 d*e ≡ 1 (mod Ø(n))을 만족하는 d값을 구한다.이렇게 하면 공개키(n,e)와 개인키(n,d)를 찾을 수 있다.

암호화는 어떻게 하나요?
평문을 M, 암호문을 C라고 했을 때M^e (mod n)=C라는 것을 이용하여 암호화 한다.

그렇다면 복호화는?
M=c^d(mod n)을 이용한다.

RSA의 보안성이 깨질 위기에 있다는데... 그 이유는?
쇼어씨가 제안한 양자화 알고리즘인 쇼어알고리즘 때문이다. 만약 양자컴퓨터가 활성화(이거 단어를 뭐라고 해야하는지 모르겠는데 상용화 뭐 이런느낌 있잖....) 된다면 이때 쇼어알고리즘을 활용하여 큰 수의 소인수분해가 가능해지게 되는데!하필 이 알고리즘을 사용하면 시간이 오래걸리든 짧게걸리든 무조건 풀리게 되는지라.... 이 알고리즘부터 보고가자

* 알고리즘의 구현법 (회로는 차마.... 이해가 안가서^^)
1) 1보다 크고 n보다 작은 정수 a를 아무거나 선택한다.
2) 만일 n과 a의 최대공약수가 1이 아니면 소인수 p를 발견한것이다. p는 최대공약수, q는 n/p를 불러내고 종료한다.
3) 찾지 못했다면 여기로 넘어오자. 함수 f(x)=a^x (modN)의 주기 r을 찾고 주기 r이 짝수가 아니면 1번부터 다시 시작한다.(왜 r이 짝수여야 하는건가요)
4) 주기 r로 부터 두개의 최대 공약수를 찾는다.
5) 만약 찾았다면 두 수를 불러내고 종료. 찾은 두개의 수 중 하나라도 1이거나 n이면 1번부터 다시 시작한다!