7.1. 공개열쇠암호
기존에 배운 암호들은 대칭암호로 암호화 열쇠와 복호화 열쇠가 동일하기 때문에,
열쇠에 대한 보안도 필요 했었습니다.
문제는 여러사람들이 각각의 열쇠와 암호문을 지닌 상태로 실사용을 해보면,
열쇠관리에 상당한 부하가 걸린다는 것을 알 수 있습니다.
이를 해결하는 다른 암호모델로 “공개 열쇠 암호”(Public Key Cipher System)방식을 만들게 되었습니다.
핵심은 두 열쇠중 하나를 공개하여 공개된 열쇠를 가지고 암호화를 진행하고,
숨기는 다른 열쇠로 복호화를 하는 방법입니다.
이 구조는 수신자만이 숨김열쇠를 가지고 있으면 되기 때문에, 열쇠 관리에 다소 편한 방법이라 볼 수 있습니다.
이 공개 열쇠암호 방식에는 열쇠 설계(열쇠 생성 함수)의 가장 중요한 사항으로 다음 두 가지가 존재합니다.
1). “일방향 함수”(One-Way Function) : 암호화 함수 y = f(x)가 존재할 때,
x값에 대한 x의 “상”(Image)을 구하는 것은 쉽지만,
y값에 대한 y의 “역상”(Inverse Image)을 구하는 것은 거의 불가능한 함수를 의미합니다.
2). “덫문 일방향 함수”(Trapdoor One-Way Function) : 일방향 함수 중에서 y값에 대한 y의 역상을 구하는 것을
특정 조건을 부여하면, 쉽게 구할 수 있게 되는 함수를 의미합니다.
공개 열쇠 암호의 정의는 다음과 같습니다.
일방향 함수를 만드는데 수학적인 문제들을 사용하여 암호화 열쇠로부터 복호화 열쇠를 찾는 것이
거의 불가능하게 설계한 암호를 “비대칭 암호계”(Asymmetric Cipher System)라고 표현하고,
이를 “공개열쇠 암호”(Public Key Cipher System)방식이라고 표현합니다.
대칭암호에서 송수신자간의 통신을 위해서는 비밀열쇠를 공유하는 것이 까다롭습니다.
열쇠는 공개되선 안되지만, 두 대상은 열쇠를 알아야 통신이 가능합니다.
이를 “열쇠 배송 문제”라고 표현하고, 이를 해결하는 방법으로는 다음 네 가지가 있습니다.
1). 열쇠의 사전 공유 : 쉽게 안전한 방법으로 열쇠를 사전에 전송하는 방법입니다.
물론, 구체적이지 않기 때문에 사실상 힘든 방법이고, 전송방법들이 간단하지 않습니다.
2). 열쇠 배포 센터 : 열쇠를 전용으로 관리하는 “열쇠배포센터”(Key Distribution Center, KDC)를 사용하여
해결하는 방법입니다.
이 방법 역시 한계점이 존재하게 되는데 부하가 걸리는 것을 피할 수 없고,
결국 배포 센터가 대상자 마다 인증을 거쳐서 열쇠를 건네는 것이기 때문에 본질적인 해결법이 아닙니다.
3). 디피-헬만 열쇠 교환 : “디피-헬만”(Diffie-Hellman)열쇠 교환을 사용하여 해결하는 방법입니다.
디피-헬만 열쇠교환 방법은 공개 정보를 제공하여,
송수신자만 이 공개정보를 가지고 열쇠를 유추해낼 수 있도록 설계하는 방법입니다.
단순한 방법이기에 생기는 단점으로는 송, 수신자간의 인증을 제공할 수 없다는 점이 있습니다.
물론, 이를 해결하는 방법은 [공개열쇠 인증] 파트에 자세하게 언급되어 있습니다.
4). 공개 열쇠 암호 사용 : 공개 열쇠 암호를 사용하면, 열쇠는 공개해도 되기 때문에,
처음부터 열쇠 배송 문제등이 생기지 않는 방법입니다.
공개 열쇠 암호는 서로 다른 두 개의 열쇠를 사용하면서
기밀성, 열쇠배송문제, 인증과 서명 문제에서 뛰어난 성능을 보여줍니다.
공개 열쇠 암호에서 암호화열쇠를 공개하여 이를 “공개열쇠”(Public Key)라고 표현하고,
공개 열쇠 암호에서 복호화열쇠는 비공개 열쇠로 이를 “개인열쇠”(Private Key)라고 표현합니다.
추가로 공개열쇠암호는 “비대칭암호”로도 표현합니다.
공개열쇠암호는 크게 정수론에 기초하여 만들어진 RSA암호, LUC암호, 배낭암호들과
유한체론에 기초하여 만들어진, 이산대수암호, 타원곡선암호로 나눌 수 있습니다.
7.2. RSA 암호
RSA 암호는 공개 열쇠 암호의 대표적인 암호로 정수론, 소수에 관련하여 만들어진 암호방식입니다.
“RSA”의 약자는 RSA를 고안한 세 교수 “리베스트”(R. L. Rivest), “샤미르”(A. Shamir), “애들만”(L. Adleman)의
약자를 따서 RSA로 표현 되었습니다.
RSA암호의 암호화 과정은 다음과 같습니다.
먼저, N 은 N = p \times q : (p와 q는 비공개 된 두 소수)인 공개 값, e 는 공개된 지수 ,
d 는 d \times e = 1 mod (p – 1)(q – 1) 이고, d \in \mathbb{N} 이고, 비공개 값
P 는 평문(P \in \mathbb{N}) , C 는 암호문(C \in \mathbb{N}), E 는 암호화 함수, D 는 복호화 함수
들로 정의한다면,
암호문 C로 암호화는 C = E( P ) = P^e mod N 이고, 평문 P로 복호화는 P = D(C) = C^d mod N 입니다.
쉽게 풀어보면, 암호화는 평문에 공개 지수 e를 하여 나온 결과를 공개 값 N을 통해 진행하고,
복호화는 암호문에 비공개 지수 d를 하여 나올 결과를 비공개 값 N을 통해 진행하는 방식입니다.
열쇠 값들의 생성과정은 다음과 같습니다.
1). 충분히 큰 두 소수 p와 q를 선정합니다.
2). N = p \times q 로 N을 구합니다.
3). \phi(N) = \phi(p)\pji(q) = (p – 1)(q – 1) 을 구합니다.
4). 3 < d < \phi(N)이고, d 와 \phi(N) 이 서로소(즉, (d, \phi(N)) = 1) 가 되도록 d를 정합니다.
5). 1 < e < \phi(N)이고, e \times d 을 \phi(N)으로 나눈 나머지가 1이 되도록 e를 정합니다.
p와 q는 비공개이지만, N은 공개인 부분이 독특하지만, p와 q를 특정하기 어려운 정도로 수를 잡으면
아직은 다항시간 안에 N을 소인수분해 할 수 있는 알고리즘이 없어 안전한 편에 속합니다.
개인 열쇠는 d, (p, q)가 되고, 공개열쇠는 e, N이 됩니다.
암호화는 e와 N으로 가능하기에 공개열쇠로도 가능한 것이고,
복호화는 d와 N으로 가능하기에 개인열쇠가 필요한 것입니다.
그렇다면, 실제로 계산을 할 때, 열쇠들을 만드는 과정은 시간이 조금 걸려도 괜찮을 수 있지만,
암호화할 때 P^e 나 또는 복호화할 때 C^d 는 실제로 엄청난 크기로 되어있기 때문에,
단순 계산으로는 엄청난 시간이 걸릴 것입니다.
이 때, 이들을 빠르게 계산하는 방법으로 “제곱과 곱셈”(Square-And_Multiply)알고리즘을 사용하여
빠르게 구할 수 있습니다.
제곱과 곱셈 알고리즘은 다음과 같습니다.
1). 암호문 C를 1로 둡니다. ( 즉, C = 1 )
2). e를 비트열로 변환 했을 때, e_i를 i번째 비트라고 가정합니다.
3). 최대 i 값부터 i = 0 까지 i를 반복하면서 다음의 내용을 실행합니다.
e_i = 0 => C = ( C \times P ) mod N , e_i = 1 => C = ( C^2 ) mod N
(즉, 의사 코드로 표현하면, 다음과 같을 것입니다. )
for( i = max -> 0 ) {
if ( e_i == 0 ) then C = C * P % N
if ( e_i == 1 ) then C = C * C % N
}또한, 열쇠 값들의 생성과정 중에서 p와 q가 주어지면, N과 \phi(N) 까지는 비교적 단순하게 값을 구하고,
d는 조건을 성립하는 임의의 수를 선택하는 것이므로 어렵지 않은데,
e는 조건은 간단해 보이지만, 실제로 정수값으로 들어 맞기 위해서는 단순 연산으로는 복잡할 수 있습니다.
그래서 이 때, “확장된 유클리드”(Extended Euclidean)알고리즘을 사용하여 비교적 간단하게 구할 수 있습니다.
확장된 유클리드 알고리즘은 기존의 유클리드 알고리즘의 역연산 느낌으로 답을 찾는 느낌이라 볼 수 있습니다.
즉, GCD를 보고, GCD식이 나온 과정을 확장하여 마지막에
{ 목표 값 – 몫 \times 제수(Divisor) = GCD } 형태로 변환하는 것입니다.
RSA암호를 안전하게 사용하기 위한 설계조건으로는 다음 7가지가 있습니다.
1). 공개열쇠( e, N )로 부터 개인열쇠 d를 구하기가 어렵도록 해야합니다.
2). 암호변환에서 평문이 바뀌지 않고 고정되는 경우가 되도록 적어야 합니다.
3). 암호화 과정과 복호화 과정에서 사용되는 지수 승 계산을 빠르게 할 수 있어야 합니다.
4). p와 q는 같지 않고 거의 같은 크기의 자리 수이어야 합니다.
5). (p – 1)과 (q – 1)은 각각 큰 소인수를 가져야 합니다.
6). (p – 1)과 (q – 1)의 최대공약수는 작은 수이어야 합니다.
7). d는 기존의 조건에 충족되면서, max{p, q} + 1 보다 크게 선택해야 합니다.
7.3. RSA 분석
RSA 암호는 오일러 정리와 중국인의 나머지 정리에 의존한 암호방식임을 알 수 있습니다.
N = p \times q 🙁 p \neq q 인 두 소수 ) 와 ed = 1 mod \phi(N) 이면,
임의의 P에 대하여 P^{ed} = P mod N 이 성립합니다.
해당 수식은 공개열쇠 e와 N에 대하여 평문 P가 주어졌을 때, 개인 열쇠 d를 구할 수 있는 수식이라 볼 수 있습니다.
그렇기 때문에 ed = 1 mod \phi(N) 식이 어렵게 도출되도록 해야 암호해독이 쉽지 않을 것입니다.
이는 구체적으로 \phi(N)을 구하는 과정이 어려워야하고, 실제 \phi(N)은 N을 소인수 분해하여 구할 수 있습니다.
즉, N을 소인수 분해하는 복잡도가 RSA암호의 복잡도에 지대한 영향을 끼친다고 볼 수 있게 됩니다.
만약에, N은 공개되어있고, \phi(N)이 주어진다면, RSA암호를 공격할 수 있을까요?