[암호학] 6.1 The RSA Algorithm (RSA 알고리즘)

공개키 암호화(비대칭키 암호화)의 대표적인 방식

---

Alice가 Bob에게 메시지를 보내고자 할 때 작동 과정은 아래와 같다.

 

1. Bob은 서로 다른 큰 소수 p, q를 선택한다.

2. Bob은 p, q를 곱한 n을 구한다.

3. Bob은 암호화 지수(encryption exponent) e를 구한다. 단, e는 아래의 조건을 만족한다.

4. Bob은 Alice에게 공개키 (n, e)를 전송한다. 이때 p, q는 비밀키이다. (Bob의 적이 될 수 있는 Alice에게 비밀키를 보내지 않는다.)

5. Alice는 메시지 m(m < n 가정)을 암호화 한다. (이때, n < m이면 메시지 m을 각각 n보다 작은 block으로 나눈다.)

6. Alice는 Bob에게 암호문 c를 전송한다.

7. Bob은 p, q, e를 알고 있으므로 (p-1)(q-1)를 계산할 수 있어 복호화 지수(decryption exponent) d를 구할 수 있다.

8. Bob은 암호문 c를 아래와 같이 복호화하고 메시지를 확인할 수 있다.

---

RSA 알고리즘 과정을 정리하면 아래와 같다.

1. Bob은 비밀키 소수 p, q를 선택하고 n=pq를 계산한다.
2. Bob은 gcd(e, (p-1)(q-1))=1인 e를 선택한다.
3. Bob은 de=1 (mod (p-1)(q-1))인 d를 계산한다.
4. Bob은 공개키로 (n, e)를 만들고 p, q, d를 비밀키로 가진다.
5. Alice는 메시지 m을 c=m^c (mod n)으로 암호화하고, 암호문 c를 Bob에게 보낸다.
6. Bob은 m=c^d (mod n)을 계산하여 복호화한다.

---

Example.

Bob이 선택한 소수 p, q가 위와 같다고 가정하자.

n=pq를 계산하면 위와 같다.

암호화 지수 e는 위와 같다고 가정하자.

 

이후 (n, e)는 Alice에게 전송된다.

Alice가 암호화하고자 하는 메시지 m은 cat이다. a=0가 아닌, a=01 ~ z = 26로 바꾸어 가정하자.

(이전에 a=0으로 설정하게 되면, 문자 a가 시작 부분에 나타나면 message number가 00으로 시작하여 사라질 수 있기 때문이다.)

c = 03 a=01 t=20

그렇다면 메시지는 이렇게 표현할 수 있다.

 

Alic는 암호문 c를 계산할 수 있다.

그리고 c를 Bob에게 전송한다.

 

Bob은 p, q를 알고 있으므로 (p-1)(q-1)도 알고 있다. Bob은 확장 유클리드 알고리즘을 활용해서 아래의 조건을 만족하는 복호화 지수 d를 계산한다.

Bob은 암호문 c를 복호화 하기위해 양변에 복호화 지수 d를 제곱해준다.

이제 메시지를 확인할 수 있다.

 

이때 m=c^d (mod n)가 어떻게 성립하는가에 대해서는 설명이 더 필요하다. Section 3.6의 오일러의 정리를 생각해보면 gcd(a, n)=1이면 a^ϕ(n)= (mod n)이다. 이 경우, ϕ(n) = ϕ(pq) = (p-1)(q-1)이다. gcd(m, n)=1을 가정해보면, p, q가 매우 크므로 m은 두 수를 인자로 가지지 않을 것이다.

=> 즉, de = 1 (mod ϕ(n))이므로, 일부 정수 k에 대해서 de = 1+k*ϕ(n)라고 쓸 수 있다.

이렇게 Bob은 메시지를 복호화한다. 만약 gcd(m, n) != 1이라면, Bob은 계속해서 메시지 복호화를 시도해야할 것이다.

---

1. 공격자 Eve가 비밀키 p, q, d를 모른채 공개키 (n, e)와 암호문 c를 가로챘다면 어떻게 될까? 

- 우리는 Eve가 n을 소인수분해할 방법이 없다(=p, q를 알아내지 못한다)고 가정한다. 그렇다면 Eve가 d를 계산하기 위해서는 ϕ(n)을 알아야 한다. 하지만 이것은 p, q를 아는 것과 같은 수준이다. 따라서, Eve가 복호화 지수 d를 발견할 확률은 매우 적다. 하지만 Eve가 d까지 알아냈다고 가정한다면, n을 소인수분해하는 것이 가능해진다.

 

- Eve는 c=m^c (mod n)을 알고있으므로 c에 제곱근 e를 적용하면 되지 않을까? mod n을 적용하지 않는 경우 가능하지만, RSA 알고리즘에서는 mod n을 수행하므로 매우 어렵다. 예를 들어, m^3=3 (mod 85)의 경우 ∛3(=1.4422...)를 계산하지 못하므로 mod 85의 연산을 줄일 수 없다. 무작정 하나하나씩 찾다보면 m=7이라는 결과를 얻을 수 있겠지만, n이 큰 수이면 이와 같은 방법을 적용하는 것이 불가능하다. (시간이 매우 오래 걸림)

 

2. Bob은 p, q를 어떻게 선정하는가?

- p, q는 서로 다른 소수로 랜덤해야하며, 수의 크기는 필요한 보안 수준에 따라 달라진다. (단, 최소 100자리 이상이어야 한다.) p, q가 너무 작으면 암호 해독이 용이해지므로 주의해야 하고, 확인과정이 필요하다. 만약 p-1가 소인수만 가지는 경우에는 n이 p-1 method(section 6.4 폴라드의 p-1 알고리즘)에 의해 쉽게 소인수분해되므로 p를 다른 소수로 바꾸어야 한다.

 

3. Bob이 선택하는 암호화 지수 e의 조건이 gcd(e, (p-1)(q-1)) =1인 이유는?

- (Section 3.3 참고) de=1 (mod (p-1)(q-1))에서 d를 구하는 방법이 gcd(e, (p-1)(q-1))=1인 경우에만 존재하기 때문이다. 따라서, d가 존재하기 위해서는 해당 조건을 반족해야한다. d는 확장 유클리드 알고리즘을 사용하여 빠르게 계산할 수 있다. p-1은 짝수이므로 e=2는 성립할 수 없기 때문에 e=3을 사용하고 싶을 수 있다. 하지만 e를 작은 수로 설정하는 데에는 위험이 있어(Sectin 6.2, Section 17.3 참고) 일반적으로 큰 수로 설정하는 것이 권장된다. (Ex. 적당히 큰 소수 e인 경우 gcd(e, (p-1)(q-1)=1임을 확인하는 데 어려움이 없음)

 

4. 그외: 계산 속도와 보안성

- Alice는 메시지 m을 암호화할 때 m^e를 수행한다. 이때 모듈러 연산의 장점을 통해 연속 제곱을 통해 대용량 메모리 없이 상당히 빠르게 해당 작업을 수행할 수 있다. (만약 Alice가 처음을 계산하고 mod n을 줄이려고 m^c의 값을 저장하면 컴퓨터의 메모리가 오버플로우 될 수 있다.) 마찬가지로, c^d (mod n)을 계산하는 복호화 프로세스를 효율적으로 수행할 수 있게 한다는 장점도 있다. 따라서 암호화/복호화 작업 모두 신속하게 수행된다.(시간 복잡도가 log n 수준) 보안성은 n을 소인수분해 할 수 없다는 가정 하에 보장된다.

 

---

지금까지 했던 이야기들을 2가지 claim으로 정리할 수 있다. 핵심은 ϕ(n)이나 복호화 지수 d를 찾기는 n을 소인수분해하는 것만큼 어렵다는 것이다. 그러므로, 소인수분해가 어렵다는 것은 해당 과정이 매우 어렵고, 빠르게 처리할 수 있는 방법을 찾을 수 없다는 것이다.

 

Claim 1: n=pq 이 서로 다른 두 소수 p, q로 이루어졌을 때, n과 ϕ(n)를 알면 p, q를 빠르게 구할 수 있다.

위의 식을 생각해보자.

 

p*q와 p+q를 알면, 다항식의 근은 p, q이다.

p, q는 근의 공식으로 구할 수 있다.

Example.

n=221, ϕ(n)=192를 알고 있다고 가정한다면 이차방정식은 아래와 같다.

p, q를 구하기 위해 근의 공식을 적용한다면

쉽게 p, q를 구할 수 있다.

Claim 2: d, e를 안다면 n을 소인수분해할 수 있다.

(Section 6.4 참고) gcd(a, n)=1인 모든 a에 대해서 a^b=1 (mod n)을 만족하는 universal exponent인 b > 0를 구한다면 n을 소인수분해할 수 있는 가능성이 있다. de - 1은 ϕ(n)의 곱셈이므로, de - 1 = kϕ(n)라고 할 수 있다. 즉,

gcd(a, n)=1인 경우 위와 같다. 이후 universal exponents를 위한 method를 적용할 수 있다.

---

1. RSA 알고리즘 적용 예시

- 서로에게 재무 데이터를 전송하려는 은행이 여러 개 있는 경우를 생각해보자. 수천 개의 은행이 있다면 각 은행이 서로 비밀키를 갖는 것은 비현실적이다. 이때 RSA 알고리즘을 적용해보자. 각 은행은 정수 n, e를 선택한다.(이것들은 공개키로 공유된다.) 은행 A가 데이터를 은행 B로 보내려고 한다고 가정하자. 그러면 A는 B의 n과 e를 검색하여 메시지를 보내는 데 사용한다.

- 실제로는 RSA 알고리즘은 엄청난 양의 데이터를 전송할 만큼 빠르지 않기 때문에 종종 DES와 같은 더 빠른 암호화 방법을 위한 키 전송에 사용된다.

 

2. PGP

- PGP(= Pretty Good Privacy)는 널리 사용되는 전자 메일 암호화 방법이다. Alice는 밥에게 이메일 메시지를 보낼 때 Chapter 9에서 설명한 것 같이 디지털 서명 알고리즘을 사용하여 먼저 메시지에 서명한다. 그런 다음 임의로 선택한 128-bit 키(전송 시 마다 대해 새 임의의 키가 선택됨)로 triple DES(IDEA 또는 CAST-128를 이용하기도 함)와 같은 블록 암호를 사용하여 메시지를 암호화한다. 그런 다음 Bob의 공개 RSA 키를 사용하여 이 키를 암호화한다(다른 공개 키 방법도 사용할 수 있음). Bob은 이메일을 받으면 개인 RSA 키를 사용하여 임의의 키에 대한 복호화를 진행한다. 이후 이 임의의 키를 사용하여 메시지를 해독하고, 메시지를 Alice에게서 받았는지 확인하기 위해 서명을 확인한다.(PGP에 대한 자세한 내용은 Section 10.6 참고)