RSA 암호화 - RSA의 동작 방식

RSA 암호화

• RSA 암호화 - 개념편
• RSA 암호화 - 수학편: RSA와 소수
• RSA 암호화 - 수학편: 나머지 계산
• RSA 암호화 - RSA의 동작 방식
• RSA 암호화 - RSA의 작동 원리

[알림] 이 글은 RSA 암호화 시리즈의 4편입니다. 앞선 편을 모두 읽고 이 편을 읽는 것을 추천합니다!

---

RSA의 작동 방식

RSA는 다음 방식으로 작동한다.

 

키 쌍 생성:

1. 아주 큰 두 소수 $p$, $q$를 생성한다.
2. $N=pq$를 계산한다.
3. $(p-1)(q-1)$과 서로소인 정수 $e$를 하나 정한다.
4. $ed$를 $(p-1)(q-1)$로 나눈 나머지가 1인 정수 $d$를 계산한다.
5. $p$와 $q$, $p-1$, $q-1$은 삭제한다.
6. 공개키는 $N$과 $e$가 되고 비밀키는 $d$가 된다.

3단계에서 $e$와 $(p-1)(q-1)$이 서로소여야 하는 이유는 4단계 때문이다.

4단계의 작업은 어떤 정수 $x$가 있을 때 다음 식으로 요약할 수 있다.

$ed=(p-1)(q-1)x+1$

 

$e=gE$, $(p-1)(q-1)=gQ$라고 하면 위의 식은 다음과 같이 바뀐다.

$gEd-gQx=1$

 

여기서 1은 $g$를 인수로 가져야 한다. 만약 $g \neq 1$이라면 1은 절대 $g$를 인수로 가질 수 없으므로 $g=1$이여야 한다.

이는 곧 $e$와 $(p-1)(q-1)$의 최대공약수가 1, 즉 서로소라는 것을 의미한다.

 

암호화:

1. 암호화하고자 하는 원문 $a$를 준비한다. 이때 $a$는 $N$ 미만의 정수여야 한다.
2. $x = a^e\:\mathrm{mod}\:N$을 만족하는 $x$를 계산한다.
3. $x$의 값이 암호화된 값이다.

복호화:

1. 복호화하고자 하는 암호문 $x$를 준비한다.
2. $a^{\prime}=x^d\:\mathrm{mod}\:N$인 $a^{\prime}$을 계산한다.
3. $a^{\prime}$이 원문이다.

암복호화 과정은 꽤 간단하다. 각자 알고 있는 $e$와 $d$의 거듭제곱을 취하고 $N$으로 나눈 나머지를 구하면 된다. 이때 $e$, $d$, $a$나 $x$의 값은 꽤 큰 수이므로 거듭제곱을 그냥 계산하지는 않고 이 방법을 사용한다.

 

암호화에서 원문이 $N$ 미만이어야 하는 이유는 만일 원문이 $N$보다 커도 된다면 다른 원문이 같은 암호문을 가지는 오류가 발생할 수 있기 때문이다.

 

구체적으로 $a=pN+q$라고 하면 (단, $p,q$는 정수이고 $0 \leq q < N$) $a^e=(pN+q)^e$이다. 여기서 다음이 성립한다.

$(pN+q)^e \equiv q^e\:(\mathrm{mod}\:N)$

 

이 이유는 $q^e$ 외에는 모든 항이 $N$을 최소 1개는 가지고 있기 때문이다. 이 결과는 $a$가 $N$보다 크더라도 $N$보다 작은 것과 구분할 수 없음을 말한다. 이는 명백한 오류이다. 따라서 원문의 크기가 $N$보다 큰 경우 원문을 일정한 규칙으로 잘라서 따로따로 암호화한다.

 

---

예시

RSA 암호화를 직접 해보자

우선 소수 2개를 선택한다. $p=7$, $q=13$이라고 하자. 물론 실제로는 이렇게 작은 소수를 사용하지 않는다.

필요한 값들을 계산하자. $N=91$, $(p-1)(q-1)=72$이다.

72와 서로소인 적당한 정수 29를 $e$로 하고($e=29$)

$ed$를 72로 나눈 나머지가 1 이도록 $d$의 값을 계산하면 $d=5$일 때 $ed=145$가 돼서 72로 나눈 나머지가 1이다.

 

이제 공개키는 $N=91$, $e=29$이고

비밀키는 $d=5$이다.

 

한번 19를 암호화해보자. 19는 91 미만이므로 문제가 없다.

$19^{29}\:\mathrm{mod}\:91=80$

암호화된 암호문은 80이다.

 

이제 80을 복호화해보자.

$80^5\:\mathrm{mod}\:91=19$

문제없이 원문이 나온다.

 

RSA는 양방향으로 암복호화가 가능하다. 다시 말해 개인키로 암호화한 내용을 공개키로 열어볼 수 있으며, 이 성질은 디지털 서명에 사용된다.

 

한번 30을 개인키로 암호화해보자. 30은 91 미만이므로 문제가 없다.

$30^{5}\:\mathrm{mod}\:91=88$

암호화된 암호문은 88이다.

 

이제 88을 공개키로 복호화해보자.

$88^{29}\:\mathrm{mod}\:91=30$

문제없이 원문이 나온다.