현존 최강의 암호화 알고리즘 RSA

RSA 암호화 알고리즘

컴퓨터 연산 과정의 한계를 이용해서 만든 최강의 보안 RSA는 세 명의 수학자인 로널드 라이베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman)이 만들었다.

 

현존 최강인 만큼 전 세계 보안 유지 기업에서 RSA를 사용한다.

당연하게도, 금융기관에서 사용하는 RSA는 슈퍼 컴퓨터로도 풀어낼 수 없다. (혹은 매우 오랜 시간이 걸린다.)

 

이제 RSA의 원리에 대해서 알아보자.

 

우선 RSA는 비대칭키 암호이다. 비대칭키란 공개키 암호(Public-key Encryption)이라고도 하며, 암호화, 복호화에 서로 다른 키를 사용하는 알고리즘을 말한다.

 

정리하자면, 암호화할 때 공개키(public key)를 사용하고 복호화할 때 개인키(private key)를 사용한다.

공개키는 말 그대로 공개되어 있다. 그래서 누구든지 해당 키를 가지고 암호화할 수 있다. 하지만 일단 암호화하고 난 다음에는 공개키로 복호화할 수 없다. 오직 개인키만으로 복호화가 가능하다.

 

이 모든 문제는 아래에 등장하는 Alice와 Bob이 직접 만나면 해결될 일이지만 두 사람이 멀리 떨어진 상태에서 오직 둘만이 알 수 있는 편지를 주고받고자 할 때 필요하다.

 

1. Alice와 Bob은 멀리 떨어진 상태에서 둘만이 볼수있는 편지를 주고받고자 한다.
2. 우선 Bob은 편지로 공개키를 Alice에게 전달한다.
3. 공개키가 Alice에게 전달되는 와중에 없어지거나 누군가에게 탈취되어도 문제없다.
4. 이제 Alice가 편지를 쓰고 이를 공개키로 암호화해서 Bob에게 보낸다.
5. 공개키로 암호화되었기때문에 누군가에게 탈취되어도 문제없다. 이는 오직 개인키로만 복호화가 가능하다.
6. 공개키로 암호화된 편지를 받은 Bob은 가지고 있는 개인키로 복호화를 진행한다.
7. 비밀스러운 편지 내용을 읽는다.

 

 

(n, e)는 공개키로 상대방(Alice)과 내(Bob)가 가지고 있다.

d는 개인키이다.

공개키는 암호화 or 복호화하는 사람 입장에서 필요하다.

개인키는 복호화하는 사람 입장에서 필요하다.

 

Bob : 내가 공개키(n, e)를 줄 테니까 공개키와 암호화 공식을 이용해서 암호문(C)을 보내면 돼!

Alice : 응. 메세지(M)를 암호화해서 보낼게!

Bob: 암호문(C)을 받으면 내 개인키(d)와 복호화 공식으로 메시지를 알아내야지!

 

RSA 공식

d값(개인키) : e mod(p-1)(q-1)의 역
n값(공개키) : p x q (단, p, q는 소수)
e값(공개키) : (p-1)*(q-1)과 서로소 (1 < e < n)  *서로소 : 1 이외의 공약수가 없는 관계
암호화 공식 : M이 메시지일 때, M^e mod n = C (0 <= M <=n-1)
복호화 공식 : C가 암호문일 때, C^d mod n = M

 

참고 사이트

정수론 - 현존 최강의 암호화 RSA 소개 & 공개키로 개인키 구하는 로직 - SHA Computing