RSA 암호

리베스트-샤미르-애들먼(Rivest-Shamir-Adleman, RSA)^[1] 암호는 공개 키 암호 방식의 하나로, 암호화뿐만 아니라 전자서명이 가능한 최초의 알고리즘으로 알려져 있다. RSA가 갖는 전자서명 기능은 인증을 요구하는 전자 상거래 등에 RSA의 광범위한 활용을 가능하게 하였다.

1978년 로널드 리베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman)의 연구에 의해 체계화되었으며, RSA라는 이름은 이들 3명의 이름 앞글자를 딴 것이다. 이 세 발명자는 이 공로로 2002년 튜링상을 수상했다. 그러나 RSA 방식을 제일 먼저 개발한 사람은 영국 GCHQ에 근무하던 수학자였으며, 이보다 빠른 1973년도에 개발하게 된다. 이 내용은 GCHQ에서 비밀로 취급되었으며, 이후 1997년 세상으로 발표되게 된다.^[1]

RSA 암호체계의 안정성은 큰 숫자를 소인수 분해하는 것이 어렵다는 것에 기반을 두고 있다. 그러므로 큰 수의 소인수 분해를 획기적으로 빠르게 할 수 있는 알고리즘이 발견된다면 이 암호 체계는 가치가 떨어질 것이다. 1993년 피터 쇼어는 쇼어 알고리즘을 발표하여, 양자 컴퓨터를 이용하여 임의의 정수를 다항 시간 안에 소인수 분해하는 방법을 발표하였다. 따라서 양자 컴퓨터가 본격적으로 실용화되면 RSA 알고리즘은 무용지물이 될 것이다. 그러나 양자 컴퓨터가 이 정도 수준으로 실용화되려면 아직 여러 해가 더 필요할 것으로 보인다.

RSA 암호화 알고리즘은 1983년에 발명자들이 소속되어 있던 매사추세츠 공과대학교(MIT)에 의해 미국에 특허로 등록되었고, 2000년 9월 21일에 그 특허가 만료되었다.

RSA는 두 개의 키를 사용한다. 여기서 키란 메시지를 열고 잠그는 상수(constant)를 의미한다. 일반적으로 많은 공개키 알고리즘의 공개키(public key)는 모두에게 알려져 있으며 메시지를 암호화(encrypt)하는데 쓰이며, 암호화된 메시지는 개인키(private key)를 가진 자만이 복호화(decrypt)하여 열어볼 수 있다.

공개키 알고리즘은 누구나 어떤 메시지를 암호화할 수 있지만, 그것을 해독하여 열람할 수 있는 사람은 개인키를 지닌 단 한 사람만이 존재한다는 점에서 대칭키 알고리즘과 차이를 가진다.

RSA는 소인수 분해의 난해함에 기반하여, 공개키만을 가지고는 개인키를 의미론적으로 안전한 암호화 시스템(semantically secure cryptosystem)을 보장하도록 디자인되어 있다.

보다 이해하기 쉬운 예를 들자면, A라는 사람에게 B라는 사람이 메시지를 전하고자 할 때 B는 A의 열린 자물쇠를 들고 와 그의 ��시지를 봉인(공개키 암호화 과정에 해당)하고, 그런 다음 A에게 전해 주면, 자물쇠의 열쇠(개인키에 해당)를 가지고 있는 A가 그 메시지를 열어보는(개인키 복호화 과정에 해당) 식이 된다. 중간에 그 메시지를 가로채는 사람은 그 열쇠를 가지고 있지 않으므로 메시지를 열람할 수 없다.

메시지와 공개키 모두를 알 수 있다면 변조된 메시지를 보낼 수 있기 때문에, 실제로는 수신측의 공개키만을 사용하여 암호화하는 경우는 드물다. 송수신 양측의 키쌍을 사용하는 방법으로는 A의 개인키로 암호화 -> B의 공개키로 암호화 한 메시지를 전달하고 복호화 과정은 B의 개인키로 복호화 -> A의 공개키로 복호화로 구성된 방식이 일반적이다. RSA의 디자인 상, 그 열쇠(개인키에 해당)는 자물쇠의 형태(공개키에 해당)만 보고서는 쉽게 제작할 수가 없게 되어 있다.

A와 B가 보안이 보장되어 있지 않은 환경에서 서로 비밀 메시지를 주고 받고 싶다고 가정하자. B가 A에게 메시지를 전달하기 위해서는 A의 공개키가 필요하다. A는 아래와 같은 방법을 통해 그 만의 공개키와 개인키를 제작한다.

p 와 q 라고 하는 두 개의 서로 다른 (${\displaystyle p\neq q}$) 소수를 고른다.

1. 두 수를 곱하여 ${\displaystyle N=pq\,}$ 을 찾는다.
2. ${\displaystyle \varphi (N)=(p-1)(q-1)\,}$를 구한다.
3. ${\displaystyle \varphi (N)}$ 보단 작고, ${\displaystyle \varphi (N)}$와 서로소인 정수 e를 찾는다.
4. 확장된 유클리드 호제법을 이용하여 ${\displaystyle d\times e}$를 ${\displaystyle \varphi (N)}$로 나누었을 때 나머지가 1인 정수 d를 구한다. (${\displaystyle de\equiv 1{\pmod {\varphi (N)}}}$)

A의 공개키는 위에서 구한 두 개의 숫자로 이루어진 <N, e>이고, 개인키는 <N, d>이다. A는 <N, e>만을 B에게 공개하고, B는 이 공개키를 사용하여 자신의 메시지를 암호화하게 된다. 여기서 p와 q의 보안은 매우 중요하다. 이를 가지고 d와 e의 계산이 가능하기 때문이다. 그리하여 공개키와 개인키가 생성이 된 후에는 이 두 숫자를 지워버리는 것이 안전하다.

B가 M이란 메시지를 A에게 보내고 싶다고 하자. 일단 B는 이 M을 N보다 작은 숫자 m으로 변환한다. (이 변환법(padding scheme)은 A에게도 미리 알려져 있어야 한다. 이를테면, 메시지를 토막내어 하나의 메시지가 일정 수의 비트를 넘지 않게 하는 방법이 있다. 하지만 실제로는 이중보안을 위해 더욱 복잡한 변환법이 사용된다.) 그리고 B는 A의 공개키 <N, e>를 획득하고, 다음과 같이 c를 계산한다.

${\displaystyle c=m^{e}\mod {N}}$

그리고 이 c를 A에게 보낸다.

A는 암호화된 메시지 c를 B에게서 건네받았고, N과 d를 알고 있다. 다음 식을 통해 m을 찾는다.

${\displaystyle m=c^{d}\mod {N}}$

위에서 설명하였듯 m을 가지고 A는 M을 찾아낼 수 있는 방법을 알고 있다.

이 해독법이 가능한 이유는 다음과 같다.

${\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}\equiv m^{k(p-1)(q-1)+1}\equiv m{\pmod {N}}}$.

마지막 등식이 성립하는 이유는 다음과 같다. 위의 식에서 mod N 대신 mod p 사용하여 풀이했을 때,

${\displaystyle m^{k(p-1)(q-1)+1}\equiv (m^{p-1})^{k(q-1)}m{\pmod {p}}}$

가 된다. p가 소수이므로, m이 p의 배수가 아니라면 서로소이므로 페르마 소정리를 다음 식과 같이 적용할 수 있다. 만약 m이 p의 배수라면 양변이 p의 배수이므로 0과 동치가 되어 역시 다음 식이 성립된다.

${\displaystyle (m^{p-1})^{k(q-1)}m\equiv 1^{k(q-1)}m\equiv m{\pmod {p}}}$

mod q를 사용하여도 똑같은 풀이가 가능하다. N = pq 이므로, mod N에도 같은 식이 성립하게 된다.

RSA의 정확성 검증 관련하여 2가지 방안으로 설명하고자 한다.

첫번째 방법은 페르마 소정리를 이용하여 검증하는 방법으로 다음과 같다.

RSA의 정확성에 대한 검증은 페르마 소정리에 근거하고 있다.

이 정리(theorem)는 p가 소수이고, p가 정수 a를 나눌 수 없다면 ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$이 성립함을 보여주고 있다.

p와 q가 별개의 소수이고 e와 d가 양의 정수이면서 ${\displaystyle ed\equiv 1{\pmod {\lambda ({pq})}}}$를 만족한다면

모든 정수 m에 대해

${\displaystyle m^{ed}\equiv m{\pmod {pq}}}$

이 성립함을 보이고자 한다. ${\displaystyle \lambda (pq)}$는 구성식에 의해 p–1과 q–1의 최소공배수로, p-1과 q-1로 나누어 질 수 있기 때문에 0 또는 양수 h와 k에 대하여

${\displaystyle ed-1=h(p-1)=k(q-1)}$

와 같이 표현할 수 있다.

(주: 특히, 위의 설명은 (p-1)(q-1)이 λ(pq) 또는 λ(pq)가 (p-1)&(q-1)로 나누어질 수 있기 때문에 어떤 e와 d에 대하여도 합동식 ${\displaystyle ed\equiv 1{\pmod {(p-1)(q-1)}}}$이 성립함을 나타내고 있다.

그러나 RSA의 최근 구현에서,약하지만 충분 조건<${\displaystyle ed\equiv 1{\pmod {\lambda ({pq})}}}$>을 만족하는 reduced private exponent d를 사용하는 것이 일반적이다)

두개의 숫자 m^ed와 m이${\displaystyle \mod {pq}}$에 대하여 합동인지, ${\displaystyle \mod {pq}}$가${\displaystyle \mod {p}}$ 와${\displaystyle \mod {q}}$ 각각의 경우에도 합동인지를 확인하기 위해(이 부문은 CRT검증의 부분이며, 중요한 부분은 아니지만) 아울러, ${\displaystyle m^{ed}\equiv m{\pmod {p}}}$ 인지를 알아 보기위해,

두가지의 케이스를 고려해 보자 m ≡ 0 (mod p) and m ≢ 0 (mod p).

첫번째 Case의 경우 m이 p의 배수이므로, ${\displaystyle m^{ed}}$가 p의 배수가 된다.

따라서 m^ed는 mod p에 대하여 나머지가 0인 합동이다.

두번째 Case의 경우

${\displaystyle m^{ed}=m^{ed-1}m=m^{h(p-1)}m=(m^{p-1})^{h}m\equiv 1^{h}m\equiv m{\pmod {p}}}$

관련하여, 페르마 소정리를 이용하여 m^p−1 mod p를 1로 대체하면 ${\displaystyle m^{ed}=m{\pmod {p}}}$가 성립함을 알 수 있다.

mod q의 경우에도 유사한 방법으로 수행하여

첫번째 Case의 경우 m^ed는 q의 배수이므로, m^ed는 mod q와 나머지가 zero인 합동이다.

두번째 Case의 경우 [${\displaystyle m^{ed}=m^{ed-1}m=m^{k(q-1)}m=(m^{q-1})^{k}m\equiv 1^{k}m\equiv m{\pmod {q}}}$]

관련하여, 페르마 소정리를 이용하여 m^q−1 mod q를 1로 대체하면

${\displaystyle m^{ed}\equiv m{\pmod {q}}}$가 성립함을 알 수 있다.

이것으로 어떤 정수 m, 그리고 e, d 관련하여, 다음의 합동식이 성립함을 검증하였다. [ed ≡ 1 (mod λ : (pq), (m^e)^d ≡ m(mod pq)]

두번째 방법은 오일러의 정리를 이용해 검증을 하고자 한다.

Rivest, Shamir, Adleman의 논문^[2]은 페르마의 소정리를 이용하여 RSA의 동작원리를 설명했지만, 오일러의 정리를 이용해 증명하는 것이 일반적이다.

${\displaystyle N=pq}$ (두 개의 서로 다른 소수 p와 q의 곱 N)과 ${\displaystyle ed\equiv 1{\pmod {\phi (n)}}}$를 만족하는 양의 정수 e와 d를 이용해

${\displaystyle m^{ed}\equiv m{\pmod {n}}}$

를 보이고자 한다.

e와 d가 양수이기 때문에 ${\displaystyle ed=1+h\phi (n)}$라고 쓸 수 있다.(h는 음이 아닌 정수)

m을 n과 서로소라고 가정하면,

${\displaystyle m^{ed}=m^{1+h\phi (n)}=m(m^{\phi (n)})^{h}\equiv m(1)^{h}\equiv m{\pmod {n}}}$

끝에서 두번째 합동식 ${\displaystyle m(m^{\phi (n)})^{h}\equiv m(1)^{h}}$는 오일러의 정리에 따른 것이다.

좀 더 일반적으로 ${\displaystyle ed\equiv 1{\pmod {\lambda (n)}}}$를 만족하는 임의의 e와 d는,

n과 서로소인 m은 ${\displaystyle m^{\lambda (n)}\equiv 1{\pmod {n}}}$라고 명시된 Carmichael의 '오일러 이론의 일반화'를 보면 알 수 있다.

m이 n과 서로소가 아니면 이 이론은 성립하지 않는다.

매우 드문 확률(${\displaystyle {\frac {1}{p}}+{\frac {1}{q}}-{\frac {1}{pq}}}$의 비율)이지만 이 경우에도 합동은 성립한다.

${\displaystyle m\equiv 0{\pmod {p}}}$나 ${\displaystyle m\equiv 0{\pmod {q}}}$, 그리고 이 경우는 이전의 증명으로 해결할 수 있다.

아래는 작은 수를 이용해 암호화 방식을 예로 든 것이다.

공개 키와 개인 키 생성 과정은 다음과 같다.

1. 서로 다른 두 소수를 선택한다.

   예를 들어 ${\displaystyle p=61}$과 ${\displaystyle q=53}$을 선택했다고 하자.

2. ${\displaystyle N=pq}$를 계산한다.

   ${\displaystyle N=61\times 53=3233}$.

3. ${\displaystyle N}$의 오일러 피 함수 ${\displaystyle \phi (N)=(p-1)(q-1)}$를 계산한다.

   ${\displaystyle \phi (3233)=(61-1)(53-1)=3120}$. 오일러 피 함수란 N보다 작은 N과 서로소인 수의 개수를 찾는 함수이다.

4. ${\displaystyle 1<e<3120}$인 숫자 ${\displaystyle e}$ 가운데 ${\displaystyle \phi (N)}$과 서로소인 임의의 숫자를 선택한다.

   ${\displaystyle e=17}$을 선택하자. .

5. ${\displaystyle e{\text{ (mod }}\phi (N){\text{)}}}$에 대해 곱의 역원, 즉 ${\displaystyle ed{\text{ (mod }}\phi (N){\text{)}}=1}$ 인 숫자 ${\displaystyle d}$를 계산한다.

   ${\displaystyle 17\times 2753=46801\equiv 1{\text{ (mod 3120) }}}$

   ${\displaystyle d=2753}$.

공개 키는 (${\displaystyle N=3233}$, ${\displaystyle e=17}$)이며, 평문 ${\displaystyle m}$은 다음 함수로 암호화할 수 있다. ${\displaystyle m^{17}{\text{ (mod }}3233{\text{)}}}$

개인 키는 (${\displaystyle N=3233}$, ${\displaystyle d=2753}$)이며, 암호문 ${\displaystyle c}$는 다음 함수로 복호화할 수 있다. ${\displaystyle c^{2753}{\text{ (mod }}3233{\text{)}}}$

예를 들어 평문 ${\displaystyle m=65}$는 다음과 같이 암호화된다

${\displaystyle c=65^{17}{\text{ (mod }}3233{\text{)}}=2790}$.

암호문 ${\displaystyle c=2790}$은 다음과 같이 복호화된다

${\displaystyle m=2790^{2753}{\text{ (mod }}3233{\text{)}}=65}$.

위는 수학적인 관점에서의 복호화이고 실제 프로그래밍으로 구현시 pq같은 거대한 수의 연산은 부담이 되므로 유명한 암호화 라이브러리(OpenSSL, Java and .NET)들에서는 중국인의 나머지 정리를 기초로 컴퓨터 연산에 효율적인 복호화를 수행한다. pq보다 작은 수인 p, q를 모듈러로 개별 연산 후 조합하는 방식을 취하므로 이 경우 p, q값을 보존하고 있어야 한다.

${\displaystyle d_{p}}$, ${\displaystyle d_{q}}$, ${\displaystyle q_{Inv}}$는 복호화시 항상 사용되는 값들이므로 미리 계산해 저장해둔다.

• ${\displaystyle d_{p}=d{\text{ (mod }}(p-1){\text{)}}=2753{\text{ (mod }}(61-1){\text{)}}=53}$
• ${\displaystyle d_{q}=d{\text{ (mod }}(q-1){\text{)}}=2753{\text{ (mod }}(53-1){\text{)}}=49}$
• ${\displaystyle q_{Inv}=q^{-1}{\text{ (mod }}p{\text{)}}=53^{-1}{\text{ (mod }}61{\text{)}}=38}$

암호문은 다음과 같이 복호화된다.

• ${\displaystyle m_{1}=c^{d_{p}}{\text{ (mod }}p{\text{)}}=2790^{53}{\text{ (mod }}61{\text{)}}=4}$
• ${\displaystyle m_{2}=c^{d_{q}}{\text{ (mod }}q{\text{)}}=2790^{49}{\text{ (mod }}53{\text{)}}=12}$
• ${\displaystyle h=(q_{Inv}\times (m_{1}-m_{2})){\text{ (mod }}p{\text{)}}=(38\times -8){\text{ (mod }}61{\text{)}}=1}$
• ${\displaystyle m=m_{2}+h\times q=12+1\times 53=65}$

결과는 같지만 더 작은 수를 이용해 계산하므로 연산이 빨라진다. 그리고 모듈러 연산이므로 h<p, 따라서 h의 최대값은 p-1, 마찬가지로 m2의 최대값은 q-1이므로 m2 + hq의 최대값은 q-1 + (p-1)q = pq-1이다. 이 값은 반드시 pq보다 작으므로 pq보다 큰 수인지 체크해서 나누는 과정을 수행할 필요 없이 바로 평문이 된다. 즉 복호화에서 연산부담이 되는 매우 큰 수 pq의 연산을 배제할 수 있게 된다.

<script>
<!-- this is tested on mozilla firefox 47.0 -->
function modular_multiplicative_inverse() {

var a =  Math.abs(document.form.e.value);
var n = Math.abs(document.form.mod.value);

   var t  = 0;
   var nt = 1;
   var r  = n;
   var nr = a % n;

        if (n < 0){
        	n = -n;
        }
        if (a < 0){
        	a = n - (-a % n);
        }
    	while (nr !== 0) {
    		var quot= (r/nr) | 0;
    		var tmp = nt;  nt = t - quot*nt;  t = tmp;
    		    tmp = nr;  nr = r - quot*nr;  r = tmp;
    	}
    	if (r > 1) { return -1; }
    	if (t < 0) { t += n; }

alert("d value="+t);

    	return t;

    }
</script>
<html>
<form name="form" >
e <input type="text" name="e">
mod() <input type = "text" name="mod">
</form>
<a href="javascript:void(0);" onclick=modular_multiplicative_inverse();>Click me to get the inverse value of mod for d...</a>
</html>

• RSA OAEP

• A Method for Obtaining Digital Signatures and Public-Key Cryptosystems Archived 2008년 12월 17일 - 웨이백 머신 R. Rivest, A. Shamir, L. Adleman, Communications of the ACM, Vol. 21 (2), 1978, pages 120--126.