RSA
〈컴퓨터정보보안〉 수업 노트
RSA는 GCHQ의 Clifford Cocks, MIT의 Ronald Rivest, Adi Shamir, Leonard Adleman이 개발한 공개키 암호화 알고리즘(GCHQ와 MIT 각각 독립적으로 개발)이다.
기본적인 원리는 두 개의 큰 소수를 곱해 만든 수를 공개키로 사용하고, 이 수의 소인수분해가 어렵다는 점을 이용하여 암호화와 복호화를 수행하는 것이다.
원리
큰 소수 $p$, $q$ 를 선택하고 $N = p \cdot q$ 를 계산, $(p - 1)(q - 1)$ 과 서로소인 $e$ 를 선택한다. $e$ 는 공개키의 일부가 된다. 이어서 $e d = 1 \mod (p - 1)(q - 1)$ 을 만족하는 $d$ 를 계산한다. $d$ 는 비밀키로 사용된다.
- 공개키: $(N, e)$
- 비밀키: $d$
메시지 $M$ 을 정수로서 다루어1 다음의 수식을 계산해 암호문 $C$ 를 생성한다.
1 실제로 컴퓨터는 모든 문자를 바이너리, 혹은 수로 표현하므로, 메시지는 이미 정수로 간주할 수 있다.
\[C = M^e \mod N\]이것을 다시 복호화하려면 다음의 식을 계산하면 된다:
\[M = C^d \mod N\]만약 $N = p q$ (모듈러스; Modulus 라고 함) 소인수분해가 가능하다면 공격자는 $e$ 를 사용해 $d$ 를 쉽게 찾을 수 있다. $e d = 1 \mod (p - 1)(q - 1)$ 이므로 계산 가능하게 된다. 다시 말해 $N$ 의 소인수분해가 가능하면 RSA는 안전하지 않다.
RSA의 안전성과 소인수분해에 관련해 몇가지 주장이 있었다.
- 1967, Brillhart: 25자리 정수 인수분해는 불가능하다고 주장
- 1970, Morison: 39자리 정수의 인수분해 성공
- 1976, Guy: 20세기 내에 80자리 정수 인수분해는 불가능하다고 주장
- 1981: 인수분해에 성공함
- 1977, Rivest: 129자리 정수 인수분해는 당시의 가장 빠른 컴퓨터로 1,000조년 소요된다고 주장
- 1994: 인수분해에 성공함
RSA는 정말 작동하는가?
주어진 $C = M^e \mod N$ 에 대해, $M = C^d \mod N = M^{ed} \mod N$ 을 계산하면 원래의 메시지 $M$ 을 얻을 수 있다.
여기에는 오일러의 이론을 사용한다:
- $\bold{x}$ 가 $N$ 과 서로소이면, $\bold{x}^{\phi(N)} = 1 \mod N$ 이다.
- $e d = 1 \mod (p - 1)(q - 1)$
- $ed = k (p - 1)(q - 1) + 1$ $\dagger$
- $\phi(N) = (p - 1)(q - 1)$
- $ed - 1 = k (p - 1)(q - 1) = k \phi(N)$
- 따라서 $C^d = M^{ed} = M^{k \phi(N) + 1} = M^{k \phi(N)} M = (M^{\phi(N)})^k M = 1^k M = M \mod N$ 이다.
- $M^{ed} = M^{(ed - 1) + 1} = M \cdot M^{ed - 1}$
- $M \cdot M^{ed - 1} = M \cdot M^{k \phi(N)}$
$\dagger$ $ed = 1 \mod (p - 1)(q - 1)$ 이므로, $ed$ 를 $(p - 1)(q - 1)$ 로 나눈 나머지가 1이라는 의미이다. 따라서 $ed$ 는 $(p - 1)(q - 1)$ 의 배수에 1을 더한 수로 표현할 수 있다. 어떤 $k$ 는 존재하므로, $ed = k (p - 1)(q - 1) + 1$ 꼴로 표현할 수 있다.
다시 요약하여, $C^d = M \mod N$ 이므로, RSA의 암호화와 복호화는 유효하다.
더 효율적인 계산
비트시프트와 모듈러 연산
RSA의 계산은 일반적으로 큰 수를 다루어야 하므로 시간이 많이 소모된다.
\[5^{20} = 95 367 431 640 625 = 25 \mod 35\]하지만 시프트 연산은 큰 비용을 요구하지 않는다는 점을 이용해 다음과 같이 계산할 수 있다:
- $20 = 10100_2$
- $(1, 10, 101, 1010, 10100)_2 = (1, 2, 5, 10, 20)$
- $5^1 = 5 \mod 35$
- $5^2 = 25 \mod 35$
- $5^4 = 25^2 = 625 = 30 \mod 35$
- $5^5 = 5^4 \cdot 5^1 = 30 \cdot 5 = 150 = 10 \mod 35$
- $5^{10} = 10^2 = 100 = 30 \mod 35$
- $5^{20} = 30^2 = 900 = 25 \mod 35$
RSA는 큰 수를 그대로 다루지 않고 결국 모듈러 연산하여 작은 수로 다룬다. 따라서 처음부터 작은 수를 다루어 계산을 효율적으로 할 수 있다.
$e=3$ 와 세제곱근 공격
\[C = M^e \mod N\]만약 $e = 3$ 이라면, $C = M^3 \mod N$ 이다. 이렇게 되면 계산 절차가 두 번의 곱셈으로 단순해진다.
- $T = M \times M \mod N$
- $C = T \times M \mod N$
- $C = (M \times M) \times M \mod N$
이렇게 하여 RSA의 계산 속도를 더 확보할 수 있다.
이 방법의 단순화 자체는 RSA의 보안 능력에 크게 영향을 끼치지는 않는다. RSA는 여전히 임의의 소수 $p$, $q$ 로 만든 $N = p q$ 와 비밀키 $d$ 를 사용한다. $e$ 를 알더라도 $d$ 를 계산하기 위해서는 $N$ 의 소인수분해가 필요하다.
$e$ 가 작은 것은 $d$ 의 크기를 결정하는 데 아무런 관여를 하지 못한다. 공개키 연산의 암호화가 빨라질지 몰라도, 비밀키 연산의 복호화는 계산량이 많다.
세제곱근 공격
그러나 메시지가 충분히 작아서 $M < N^{1/3}$ 이라면, $C = M^3 \mod N$ 에서 $M^3 < N$ 이므로, 모듈러 연산이 필요하지 않게 된다. 따라서 $C = M^3$ 이고, 공격자는 세제곱근을 계산하여 $M$ 을 쉽게 찾을 수 있다. 이 과정에는 비밀키도, $N$ 의 소인수분해도 필요하지 않다.
방송 공격
메시지가 충분히 크더라도 정수 메시지 $M$ 을 패딩 없이 여러 인물에게 각각 암호화해 보내면 공격할 수 있다.
세 인물의 공개키가 각각 $(N_1, 3)$, $(N_2, 3)$, $(N_3, 3)$ 라고 할 때, 메시지 $M$ 을 세 인물에게 각각 암호화해 보낸다. 공격자는 세 개의 암호문 $C_1 = M^3 \mod N_1$, $C_2 = M^3 \mod N_2$, $C_3 = M^3 \mod N_3$ 를 얻는다.
공격자는 공개된 $N_1$, $N_2$, $N_3$, 가로챈 $C_1$, $C_2$, $C_3$ 을 알고 있다.
세 개의 서로소 정수 $N_1$, $N_2$, $N_3$ 가 쌍으로 서로소이므로, 중국인의 나머지 정리(Chinese Remainder Theorem; CRT)를 이용해 다음의 연립 합동식을 풀 수 있다.
- $X \equiv C_1 \mod N_1$
- $X \equiv C_2 \mod N_2$
- $X \equiv C_3 \mod N_3$
$M^3$ 도 세 합동식을 모두 만족하고, 메시지는 각 공개키의 유효 범위 내에 있다. 따라서
- $M < N_1$
- $M < N_2$
- $M < N_3$
- $M^3 < N_1 N_2 N_3$
이다. 중국인의 나머지 정리가 보장하는 이 범위의 해는 유일하므로 $X = M^3$ 이다. 따라서 공격자는 세제곱근을 계산하여 $M$ 을 쉽게 찾을 수 있다.
이 공격은 무작위로 생성하는 노이즈 패딩을 적용함으로써 방지할 수 있다. 무작위 패딩으로 각 암호문이 표현하는 평문이 변화한다. (RSA 암호화기에 입력하는 값이 각 시도 모두 다르다.)