RSA 암호

RSA 암호

• RSA는 공개 키 암호 중 하나로, 암호화뿐만 아니라 전자서명이 가능한 최초의 알고리즘이다.
• RSA라는 이름은 개발자 세 사람의 이름의 첫 글자를 따서 붙여졌다. (Rivest-Shamir-Adleman)
• RSA 암호화 알고리즘은 1983년에 발명자들이 소속되어 있던 매사추세츠 공과대학교(MIT)에 의해 미국에 특허로 등록되었고, 2000년 9월 21일에 그 특허가 만료되었다.
• 현재 SSL/TLS에서 가장 많이 사용되는 방식이다.

---

RSA 과정

• RSA는 공개 키 암호로 공개 키, 개인 키 두 개의 키를 사용한다.
• 일반적으로 대부분의 공개 키 방식의 암호는 공개 키로 암호화하고 개인 키로 복호화한다.
  하지만 RSA는 이러한 제약 조건이 없다. 즉, 개인 키로 암호화하고 공개 키로 복호화할 수도 있다.
• 메시지와 공개 키 모두를 알 수 있다면 변조된 메시지를 보낼 수 있기 때문에, 실제로는 수신 측의 공개 키만을 사용하여 암호화하는 경우는 드물다.
  송수신 양측의 키쌍을 사용하는 방법으로는 A의 개인 키로 암호화 -> B의 공개 키로 암호화 한 메시지를 전달하고 복호화 과정은 B의 개인 키로 복호화 -> A의 공개 키로 복호화로 구성된 방식이 일반적이다

키의 생성

키의 생성에는 임의의 소수 $!$p,q$!$ 소수를 사용해 구한 정수 $N, e, d$가 사용된다.

1. 임의의 두 소수 $p$, $q$를 구한다.^{[각주:1] [각주:2]}
2. $p$와 $q$를 곱하여 $N$을 계산한다.
3. $N$의 오일러 피 함수 $\varphi(N)=(p-1)(q-1)$를 계산한다.
4. 1보다 크고 $\varphi(N)$보다는 작으면서 $\varphi(N)$와 서로소인 정수 $e$^[각주:3]를 찾는다. ($1<e<\varphi(N)$) 
5. 확장된 유클리드 호제법을 이용하여 $ed$를 $(p-1)(q-1)$으로 나눈 나머지가 1이 되도록 하는 $d$^[각주:4]를 찾는다. ($ed(mod$ $\varphi(N)=1$) 
6. 공개 키는<$N,e$> 비밀키는 <$N,d$>이며, $p$와 $q$를 가지고 키를 계산할 수 있기 때문에 생성 후에는 파기하는 게 안전하다.

 

암호화

송신자 A가 수신자 B에게 P라는 평문을 보낸다고 가정한다.

 

1. A는 P을 N보다 작은 숫자 m으로 변환한다. 변환법은 여러 방식이 있으며, 이에 사용된 변환법은 B에게도 미리 알려져 있어야 한다. ^[각주:5]
2. A는 B의 공개 키 <$N,e$>를 얻고 $c=m^e$ $mod$ $N$과정으로 $c$를 계산한다.
3. $c$를 B에게 보낸다.

복호화

1. B는 A로부터 $c$를 받고, $N$과 $d$를 알고 있다.
2. $m=c^d$ $mod$ $N$의 계산으로 m을 알아낸다.
3. m을 사용해 P를 알아낼 수 있다. 

증명

https://ko.wikipedia.org/wiki/RSA_%EC%95%94%ED%98%B8#%EC%A6%9D%EB%AA%85

예

키 생성

작은 수를 사용한 예로 실제로는 더 큰 수를 사용하게 된다.

 

1. 임의의 두 소수 $p$, $q$를 구한다.
   $p=61, q=53$
2. $p$와 $q$를 곱하여 $N$을 계산한다.
   $N=61\times53=3233$
3. $N$의 오일러 피 함수 $\varphi(N)=(p-1)(q-1)$를 계산한다.
   $\varphi(3233)=(61-1)(53-1) = 3120$
4. 1보다 크고 $\varphi(N)$보다는 작으면서 $\varphi(N)$와 서로소인 정수 $e$를 찾는다.
   ($1<e<\varphi(N)$)경우 중 $e=17$라고 가정한다.
5. 확장된 유클리드 호제법을 이용하여 $ed$를 $(p-1)(q-1)$으로 나눈 나머지가 1이 되도록 하는 $d$를 찾는다. ($ed(mod$ $\varphi(N)=1$)
   $17\times2753=46801=1(mod3120)$
   $d= 2753$

 

암호화

공개 키는 <$3233, 17$>이며^[각주:6] $m$은 아래 함수로 암호화할 수 있다.
$m^17(mod 3233)$

평문 P를 N보다 작은 수로 변환한 m의 값이 65라고 가정하면 ($m=65$)
$c=65^17 (mod 3233)=2790$

 

복호화

개인 키는 <$3233, 2753$>이며^[각주:7] $c$은 아래 함수로 암호화할 수 있다.
$c^2753 (mod 3233)$

암호문 $c=2790$는 $2790^2753 (mod 3233) = 65$ 으로 복호화된다.

위 예시는 수학적인 관점에서의 복호화이고 실제 프로그래밍으로 구현 시 $pq$같은 거대한 수의 연산은 부담이 되므로 암호화 라이브러리들에서는 중국인의 나머지 정리를 기초로 컴퓨터 연산에 효율적인 복호화를 수행한다.^[각주:8]

---

RSA의 안정성

• 암호화에 사용된 값이 작은 경우, 공격자가 암호화된 정보를 가로챘을 때, 공개된 $N$을 소인수 분해하여 p와 q를 구할 수 있으며, $\varphi(N)$값 과 $d$값  또한 쉽게 구할 수 있을 것이다.
• 이는 작은 수의 한정된 문제로, 큰 수의 소인수 분해의 어려움과 나머지 연산의 역연산의 어려움을 기반으로 한 RSA 암호는 N의 소인수 분해 자체가 거의 불가능하며, $ed(mod$ $\varphi(N)=1$ 를 만족하는 d값은 무수히 많기 때문에 정확한 d 값을 알아내기 매우 힘들다.^[각주:9]

1. 이들은 보통 굉장히 큰 홀수를 일단 랜덤 하게 만든 다음, 소수를 얻을 때까지 2씩 더해 가며 찾는다. 소수의 분포가 그리 희박하진 않기에 가능한 방식이다. [본문으로]
2. 현재까지 가장 확실한 소수 판정법은 에라토스테네스의 체를 이용한 방식으로 이는 작업 시간 상 현실적으로 불가능한 방법이다. 그래서 이 대신에 확률적으로 소수인지 아닌지를 판별하는 방법을 사용한다. 기본적으로 쓰는 방식이 페르마 소정리를 근거로 한 것인데, 이 정리의 대우 명제인 '임의의 정수 $a$에 대해 $a^{p-1}$ 를 $p$로 나눈 나머지가 1이 아니면 $p$는 소수가 아니다'라는 사실을 이용한 것이다. 이 방법을 쓰면 상당 확률로 소수를 걸러낼 수 있다고 한다. 하지만 물론 완전하진 않으며 이 때문에 다른 소수 판정법을 같이 쓰기도 한다. [본문으로]
3. e는 encryption에서 따왔으며, 공개 키에 사용된다. [본문으로]
4. d는 decryption에서 따왔으며, 개인 키에 사용된다. [본문으로]
5. 이를테면, 메시지를 토막 내어 하나의 메시지가 일정 수의 bit 넘지 않게 하는 방법이 있다. 하지만 실제로는 이중 보안을 위해 더욱 복잡한 변환법이 사용된다. [본문으로]
6. <$N, e$> [본문으로]
7. <$N, d$> [본문으로]
8. pq보다 작은 수인 p, q를 모듈러로 개별 연산 후 조합하는 방식을 취하므로 이 경우 p, q값을 보존하고 있어야 한다. [본문으로]
9. 물론 큰 수의 소인수 분해를 획기적으로 빠르게 할 수 있는 알고리즘이 발견된다면 이 암호 체계는 가치가 떨어질 것이다. 1993년 피터 쇼어는 쇼어 알고리즘을 발표하여, 양자 컴퓨터를 이용하여 임의의 정수를 다항 시간 안에 소인수 분해하는 방법을 발표하였다. 따라서 양자 컴퓨터가 본격적으로 실용화되면 RSA 알고리즘은 무용지물이 될 것이다. [본문으로]