이동식 저장소

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

이산 로그 (Discrete Log)

• $Z_n^{\ast }=\{g,g^2,\cdots ,g^{\phi (n)}(=1)\}$이면 $g$는 $Z_n^{\ast }$의 Generator이다.

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

• $Z_n^{\ast }$의 Generator가 존재한다 $\iff n=2,2^2,p^k,2p^k$, $p$는 홀수 소수

$Z_7^{\ast }=\{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^{\ast }$의 Generator이다.

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

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

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

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

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

디피-헬먼 키 교환

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

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

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

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

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

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

엘가말 (ElGamal)

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

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

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

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

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

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

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

서명

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

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

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