[양방향 암호화] 비대칭 키/RSA 알고리즘 설명

오늘은 비대칭키에 대해 알아보려한다.

 

1. 비대칭 키 암호 개념

• 비대칭 키 암호는 공개 키 암호라고도 한다.
• 비대칭 키 암호화에는 공개 키(public key)와 비밀 키(private key)가 있다.
• 암호화 할때는 공개 키를 사용해서 암호화를 하고 이것을 복호화 할때는 비밀 키를 사용하여 복호화 한다.
• 그래서 보통 공개 키는 누구에게나 공개 되있지만 비밀 키는 개인이 잘 간직하고 있어야한다.
• 대표 알고리즘으로 RSA(Rivest, Shamir and Adleman)이 있다.

---

2. RSA 알고리즘

방금 위에서 말했듯이 비대칭 키 암호화에 사용되는 대표적인 알고리즘은 RSA다.

RSA 알고리즘은 소수, 소인수를 이용한 알고리즘이다.=

 

2.1 공개키 비밀키 생성

일단 두개의 소수 a1, a2와 a1*a2인 N이 있다.

a1=13,  a2=19,  N=13*19=247

1. 1부터 N-1까지 N과 서로소인 정수 개수를 구한다.(서로소는 두 숫자의 최대 공약수가 1인 수)
2. N이 소수면 서로수 개수는 N - 1개, N이 소수의 곱이면 (a1 - 1) * (a2 - 1)개 -> 오일러 파이(φ)라 한다.
   φ(N) = (13-1)*(19-1) = 216
   
   
3. φ(N)과 서로소인 e(공개키)를 생성 (1<e<φ(N))
   e = 5
   
   
4. (d*e)mod φ(N)=1인 d를 선택한다.-> z mod s는 s로 z를 나눴을 때의 나머지
   (d*5)mod 216=1     
   173*5mod 24=1     
   d = 173
   
   
5. N=247, e=5 이 두개는 공개키, d=173은 비밀키로 사용
   
   

2.3 암호화

M=123이라는 평문을 C로 암호화하려면
C = M^e mod N

C = 123^5 mod 247 = 54
C = 54

 

2.4 복호화

C라는 암호문을 복호화하려면

M=C^d mod N

M=3^7 mod 247 = 123

M=123

 

이 값은 N을 소인수분해하면 a1, a2를 구할 수 있고, 공개키 e와 a1,a2를 이용해 비밀키d를 얻을 수 있다.

---

이러한식으로 알고리즘이 진행된다. 지금은 숫자를 작게하여 계산으로도 풀리지만 암호화과정에서는 2048bit정도의 길이로 숫자를 정하고 한다. 즉, 1000자릿수의 숫자를 소인수 분해하여 a1, a2를 구해야하는 작업을 해야하는데 이거는 현재 컴퓨터로도 상당히 오랜 시간이 걸린다고 한다. 다음 포스팅에서는 대칭 암호화에 대해 포스팅 할 예정이다.

 

 

 

 

 

참고

https://dailyworker.github.io/AES-Algorithm-and-Chiper-mode/

https://bpsecblog.wordpress.com/2016/12/05/amalmot_6/

https://ko.wikipedia.org/wiki/%EA%B3%B5%EA%B0%9C_%ED%82%A4_%EC%95%94%ED%98%B8_%EB%B0%A9%EC%8B%9D