12주차 1차시

저번 시간까지 RSA에 대해 공부했다. 이제 두 번째 암호에 대해 알아보자.

이산 로그 (Discrete Log)

• $Z_{n}^{*}=\{ g,g^{2},\cdots,g^{\varphi (n)} (=1) \} $이면 $g$는 $Z_{n}^{*}$의 ``Generator``이다.

``Generator``가 항상 존재하지는 않는다. 예를 들어 $Z_{15}^{*}$의 ``Generator``는 존재하지 않는다. 사실 ``Generator``가 존재할 조건은 다음과 같다.

 

• $Z_{n}^{*}$의 ``Generator``가 존재한다 $\Leftrightarrow~n=2,2^{2},p^{k},2p^{k}$, $p$는 홀수 소수

$Z_{7}^{*}=\{1,2,3,4,5,6\}$의 ``Generator`` $g=3$이다. $\{3,2,6,4,5,1\}$이 되기 때문. $g=5$도 $\{5,4,6,2,3,1\}$이 되기 때문에 $Z_{7}^{*}$의 ``Generator``이다.

이산 로그 문제 (DL, Discrete Log Problem)

$n,~g,~x$가 주어질 때, $g^{k}=x \mod n$을 만족하는 $k$를 찾으시오.
($g$는 $Z_{n}^{*}$의 ``Generator``, $x$는 나머지)

이 문제는 ``로그 문제``와 형태가 비슷하기 때문에 이산 로그 문제라고 불린다. $s<t$이면 $3^{s}<3^{t}$이므로 로그 문제는 이진 탐색과 비슷하게 풀 수 있다. 그런데 잉여계에서는 $s<t$라고 해서 $s \mod n < t \mod n$이 성립하는 건 아니기 때문에 매우 풀기 어렵다.

 

사실 DL 문제는 $NP \cap co-NP$에 속한다. 소인수분해와 동등한 문제가 아닐까 추측된다고 한다.

 

지금까지 배운 내용을 토대로 암호를 만들어 보자.

디피-헬먼 키 교환

이건 암호는 아니고, 수신자와 송신자가 키를 안전하게 교환할 수 있도록 하는 방법이다.

 

• $p$와 $g$는 공개된다. 사실 모든 사람이 같은 $p$와 $g$를 사용해도 된다.
• Alice의 공개 키: $g^{a} \mod p$
• Alice의 비밀 키: $a \in Z_{p}^{*}$
• Bob의 공개 키: $g^{b} \mod p$
• Bob의 비밀 키: $b \in Z_{p}^{*}$

이제 다음의 과정을 수행한다.

• Alice는 $(g^{b})^{a}=g^{ab} \mod p$를 계산한다. Alice는 $g^{a}$를 알고 있으므로 이 값으로부터 $b$를 얻을 수 있다.
• Bob은 $(g^{a})^{b}=g^{ab} \mod p$를 계산한다. Bob은 $g^{b}$를 알고 있으므로 이 값으로부터 $a$를 얻을 수 있다.

위의 과정을 통해 $g^{ab}$가 공유된다.

 

DL을 풀지 못해도 $a$ 또는 $b$를 얻을 수 있는지는 확실하지 않다. 반면 RSA를 깨려면 소인수분해를 풀 수 있어야 함이 증명되어 있다. 그런 이유로 디피-헬먼 키 교환은 RSA보다는 살짝 약하지만, 실용적으로는 충분히 강력하다.

엘가말 (ElGamal)

디피-헬먼 키 교환과 같은 가정을 사용한다.

 

• $p$와 $g$는 공개된다. 
• Alice의 공개 키: $g^{a} \mod p$
• Alice의 비밀 키: $a \in Z_{p}^{*}$
• Bob의 공개 키: $g^{b} \mod p$
• Bob의 비밀 키: $b \in Z_{p}^{*}$

이제 메시지 $m$을 전송해 보자. Bob이 Alice에게 전송한다고 가정한다.

 

1. Bob은 임의의 $k$를 골라서 Alice에게 $(g^{k} \mod p, m(g^{a})^{k} \mod p)$를 전송한다.
2. Alice는 $(g^{k})^{a} = g^{ak} \mod p$를 계산한다.
3. Alice는 $mg^{ak}(g^{ak})^{-1}=m \mod p$를 계산하여 메시지 $m$을 얻는다.

이정도는 식으로 이해해야 한다. 예제를 봐도 전혀 도움 안 될걸? (실제로 하신 말)

 

사실 엘가말 암호는 위의 디피-헬먼 키 교환에서 Bob이 비밀 키 $k$를 가질 때와 거의 같다. 그런데 같은 $m$을 여러번 전송하면 같은 암호문 $mg^{ak} \mod p$가 생성되므로, 제3자가 암호문을 보고 (어떤 메시지인지는 모르지만) 같은 메시지가 전송되고 있음을 알 수 있다. $k$를 랜덤하게 고르는 이유가 바로 그 때문이다.

# 해결법 (펼치기)

한번에 1000비트를 전송할 수 있다고 하자. 1000비트 중 앞의 900비트는 $m$으로, 나머지 100비트는 랜덤 문자열로 채우면 위의 문제를 해결할 수 있다. 그런데 100비트를 매번 생성하기가 귀찮기 때문에 ElGamal에서는 그냥 랜덤한 정수 $k$를 만드는 방법으로 해결한 것이다.

이제 RSA와 엘가말을 이용하여 실제로 사용되는 보안 방식에 대해 알아 보자.

서명

서명이란 서명의 주인을 판별할 수 있도록 한 것이다. 현실 세계에서도 문서에 서명을 하고, 컴퓨터 세계에서도 전자 문서에 전자 서명한다. 

 

현실에서는 모든 문서에 대해 같은 서명을 한다. 문서에서 서명을 분리할 수 없기 때문이다(설령 분리하더라도 티가 난다). 그런데 컴퓨터 세상에서는 서명을 복사해서 다른 문서에 붙일 수 있다. 갑자기 그분이 생각났다. 따라서 모든 문서에 서로 다른 전자 서명을 해야 하고, 한 전자 서명을 이용하여 다른 전자 서명을 만들 수도 없어야 한다. 요컨대 다른 사람이 나를 사칭할 수 없어야 한다는 뜻이다.

 

아니, 그러면 애초에 전자 서명이 가능하기나 한가? 비밀 키에서는 어렵지만, 공개 키 시스템에서는 가능하다. 다음 시간에 계속 이야기한다.