[암호학] RSA 암호화 기법의 원리와 방법

 

 

 

<목표>  [암호학] RSA 암호화 기법의 원리와 방법

   

  오늘은 공개키 암호화 방식인 RSA 암호화 방법에 대해서 알아보겠습니다. Ron Rivest, Adi Shamir, Leonard Adleman 의 세 사람이 개발하여서, 그 앞 머리를 딴 RSA가 그 암호화 방법의 명칭이 되었습니다. 큰 숫자의 소인수분해의 어려움을 이용하여 안전성을 높이고 있습니다. 모듈러(Mod) 연산을 통한 큰 숫자의 암호화 연산은 쉽지만, 그 역을 추적해하는 것은 매우 어렵기 때문에 RSA 방식의 안전도가 보장이 됩니다. RSA의 예제를 살펴보고, RSA 기법의 원리와 키 셋업, RSA 암호화 기법에서의 지수 연산 처리에 대해서 알아보겠습니다.

 

 

   

STEP 1  RSA 암호화 기법의 원리

 

  RSA 암호화 기법은 구현이 간단하고, 안전성이 높기 때문에 많이 사용되고 있습니다. 블록단위로 암호화를 하며, 각 블록은 n(키 값의 곱)보다 작은 바이너리 값으로 이루어져 있습니다. 블록 사이즈는 log₂(n) 보다 작거나 같습니다. 암호화 방법은 C = M^e mod n 방법으로 되며, 복호화는 M = C^d mod n = (M^e)^d mod n = M^ed mod n 의 형태로 됩니다. 송신자와 수신자는 서로 n값을 알고 있으며, 공개키는 {e, n}이며, 비밀키는 {d, n} 입니다. 암호화 방법에 있어서 M^e mod n 의 연산은 매우 쉽지만, 반대로 그 역 연산은 매우 어렵습니다. Mod 연산을 통해서 수 없이 많은 값들이 M 값이 될 수 있기 때문이지요. RSA에서의 오일러 토션 함수와 오일러 함수의 특성이 들어가 있습니다. 수학적 증명은 생략하겠습니다.

  오일러 함수로부터, a^ø(n)+1 = a (mod n), where gcd(a,n)=1, ed=ø(n)+1 à ed mod ø(n)= 1 가 정의되고, 이는 ed = 1 mod ø(n). d=e^-1 mod ø(n) 형태로도 표현이 가능합니다. 역 역산이 어려운 이유도, e와 d가 mod ø(n).에서 많은 inverse가 존재하기 때문입니다. 이러한 수학적인 연산의 어려움 때문에(Discrete Logarithm Problem) 키 없이 암호문을 해독하기가 매우 어렵습니다. 전수 조사를 통한 해결 밖에 방법이 없는데, 이 연산의 지수적으로 표현되기 때문에 시간이 매우 오래 걸립니다. 컴퓨터의 성능이 발달하게 되면서, 연산의 속도가 빨라졌기 때문에, 그 만큼 키 값의 크기도 증가시켜줘야 안전도에 문제가 없습니다. 그래서 현재는 1024 비트 이상의 키를 사용하도록 권장하고 있습니다.

  수학적인 증명은 다소 어렵지만, 실제로 암호, 복호에 쓰이는 연산은 매우 간단합니다. STEP 4의 예제를 먼저 보시면 이해하기가 쉬울 거라 생각이 듭니다.

 

 

 

STEP 2  RSA 암호화 키 셋업

   

  각 유저는 공개키와 비밀키를 가지고 있습니다. 우선 매우 큰 임의의 소수 p, q를 선택합니다. 그리고 이 둘의 곱( n = pq )을 구합니다. p와 q 소수이기 때문에 오일러 토션 함수에 의해서 ø(n)=(p-1)(q-1) 가 됩니다. 암호화를 위한 키 e 를 선택합니다. 이 때, 1<e<ø(n), gcd(e,ø(n))=1 를 만족해야 합니다. 즉, ø(n)보다 작은 양수이며, ø(n)과도 서로소가 되어야 합니다. 이제 복호화키 d를 구해야합니다 이 때, ed = 1 mod ø(n) and 0≤d≤n 식을 만족하는 d를 구해야 합니다. 그러면 키 셋업은 끝이 납니다. 공개키는 {e, n}이 되며, 비밀키는 {d, p, q}가 됩니다.

 

 

 

STEP 3  RSA 암호화 기법에서의 지수 처리

 

  RSA 에서 모듈러 연산을 하기 위해서, 지수 연산을 많이 하게 됩니다. 암호화, 복호활할 때, 각각 쓰이게 되는데요, 이를 실수 연산을 한 뒤에 모듈러 연산을 하게 되면 메모리와 연산 속도에서 현저히 떨어지게 됩니다. 이를 조금더 쉽고 빠르게 연산하기 위해서 알고리즘이 존재합니다. 모듈러 하는 값의 바이너리 값을 이용해서 연산을 하는 방식입니다. 아래의 알고리즘을 통해 연산을 해봅시다.

 

  a^b mod n 의 연산을 하고자 할 때, 아래의 알고리즘을 이용하면 간단하게 연산을 할 수 있습니다.

  여기서 b는 바이너리 형태로 존재합니다. 즉, b는 b_kb_k-1…b₀ 로 표현합니다.

 

▲ mod 연산에서의 효과적인 지수 처리 방법

 

  위의 알고리즘을 이용하는 예제를 봅시다. a^b mod n 연산에서 a=7, b = 560 =1000110000, n=561 라고 하면 아래와 같은 형태로 연산이 이루어집니다.

 

▲ 위의 알고리즘을 이용한 연산 과정

 

 

 

STEP 4  RSA 암호화 예제

 

1. 두 개의 소수를 선택합니다.	p = 17 와 q= 11
2. n을 계산 합니다.	n = p × q = 17 × 11 = 187
3. e 를 선택합니다. gcd(e,160)=1	e = 7
4. d 를 결정합니다. de=1 mod 160 and d < 160	d = 23 [ 23 × 7 = 161 = 10 × 160 + 1 ]
5. 공개키를 결정합니다. PU = {e, n}	PU = { 7, 187 }
6. 비밀키를 가지고 있습니다. PR={d, p, q}	PR = { 23, 17, 11 }

 

 

 < 마무리 >  RSA 암호화 기법

 

  오늘은 RSA암호화 기법에 대해서 알아보았습니다. 간단한 방법을 통해 암호화가 가능하다니 새삼 놀랍습니다. 큰 소수만 있으면, 얼마든지 암호화가 가능하니까요. 하지만, 이런 큰 소수를 찾는 것도 쉬운 일은 아니겠지요? Discrete Logarithm Problem을 통한 암호화 기법으로써, 키 값을 알 때는 매우 쉬운 연산이 되지만, 키 값을 모를 때에는 수 없이 많은 값들을 조사하여야 되기 때문에 연산 시간이 많이 걸려, 해독 불가능하게 만듭니다. 전수 조사 방식이 그 방법이 되겠지요. 컴퓨터의 속도가 빨라진 만큼, 현재는 키 값도 1024 비트 이상이 되어야 안전성에 문제가 없다고 합니다. 큰 숫자의 소인수분해의 획기적인 알고리즘이 개발된다면, 문제가 되는 알고리즘이기도 합니다. 수학적인 증명법은 다소 어려워서, 정의만 옮겨 놓았습니다.

   

 

 

[참고자료]  

• 위키 백과 사전 : RSA 암호
• Computer Security
• RSA 알고리즘

   

 

Posted by 맥박