[암호학] 19. RSA 암호

사전지식 (정수론)

유클리드 호제법

합동

페르마 소정리

중국인의 나머지 정리

오일러 피 함수

분할정복을 이용한 거듭제곱

 

대칭키 시스템

Key

$p$ : 큰 소수

$e$ : 암호화 키 (홀수)

$d$ : 복호화 키 (홀수)

$ed \equiv 1 \mod p-1$

$\gcd(e, p-1) = 1$

 

이렇게 3개의 키를 사용한 암호화 알고리즘을 사용한다.

$p$는 큰 소수이기 때문에 홀수임이 자명하다.

$C \equiv m^e \mod p$으로 암호화된 $C$를 구할 수 있다. ($m$은 원본 데이터)

반대로 $m \equiv C^d \mod p$로 복호화할 수 있다.

$m = C^d = (m^e)^d = m^{ed} = m$임을 사용한 심플한 알고리즘이다.

 

문제점은 메시지를 보내는 sender와 그 메시지를 받는 receiver사이에 $p, e$라는 두개의 키를 공유하면서 남들에겐 공개되면 안된다. ($d$는 $e, p$만 있으면 구할 수 있다.)

이렇게 서로 같은 키를 가지고 있는 것을 대칭키 시스템이라고 한다.

그런데 여기에서 sender가 2명의 receiver에게 메시지를 보내려고 한다면?

$(p_1, e_1), (p_2, e_2)$의 두 쌍의 키가 필요하다.

이를 일반화하면 sender가 $N$명, receiver가 $M$명 있으면 생성해야하는 키는 $2NM$개가 되고 이는 굉장히 많다.

전세계에 컴퓨터가 수십억대가 있는걸 생각하면 현실성이 떨어진다.

게다가 각 키는 적어도 2000bit는 돼야 안전하므로 용량도 많이 차지하게 된다. ($2^{2000}$은 $10^{600}$정도 되는 굉장히 큰 수이다.)

 

Public Key System

위의 키 개수 문제를 해결하기 위해 Public Key System(공개키 시스템)이 등장했다.

암호화 키 $e$를 대중에게 공개하고 복호화 키 $d$만 개인이 비밀로 가지고 있는 것이다. ($e$로부터 $d$는 알 수 없음)

그렇게 되면 1개의 키로 많은 사람들과 암호화 통신을 할 수 있다.

 

RSA System

RSA는 이런 Public Key System을 사용한 알고리즘이다.

$p, q$ : 큰 소수 (비밀 키)

$e$ : 암호화 키 (공개 키)

$d$ : 복호화 키

$n = pq$ : 공개 키

$ed \equiv 1 \mod (p-1)(q-1)$ 여기에서 $(p-1)(q-1) = \phi (n)$

 

RSA도 위의 알고리즘과 유사하게 작동한다.

$C \equiv m^e \mod n$ (암호화)

$m \equiv C^d \mod n$ (복호화)

 

이렇게 소수를 2개만 쓰더라도 공격하기 굉장히 어려운 암호 시스템이 된다.

 

$e, n$가 공개돼 있으면 $\phi (n)$을 알아내면 $d$를 알 수 있는거 아닌가요?

$n=pq$으로부터 $(p-1)(q-1)$을 알아낸다는 것과 같다.

$(p-1)(q-1) = pq-p-q+1 = n-p-q+1$

$pq = n$

식 2개에 미지수 $p,q$로 2개이므로 위의 주장이 성립하면 $n$을 소인수분해 할 수 있다는 것과 같다.

소인수분해는 $NP$에 속한다고 했으므로 그런일이 일어나기는 힘들다.

 

즉 RSA를 공격하기 위해서는 소인수분해 문제를 해결해야한다.

 

남은 문제

RSA는 상당히 좋은 암호시스템인데 당연하다고 생각하고 넘어간 사실이 있다.

1. 거듭제곱

2. 큰 소수 구하는 법

 

1번은 암호화 과정중 $m^e$연산을 해야하는데 $e > 2^{2000}$이므로 상당히 큰 수를 제곱해야한다.

이 문제는 사전지식에 있는 분할정복을 이용한 거듭제곱을 사용해서 해결할 수 있다.

 

2번으로 2000비트가 넘는 큰 소수를 구하는 방법이 있어야한다.

이는 다음시간에 알아볼 예정이다.