12주차 2차시

서명

서명이 있으면 암호화만 가지고는 못 하는 일들을 할 수 있다. 예를 들어 인터넷뱅킹. 내 입장에서 보면 상대가 은행인지 어떻게 아는가? 반대로 은행 측은 내가 계좌 주인인지 어떻게 아는가? 상대방을 확인할 수 있는 서명이 있다면, 서명이 누구의 것인지 확인할 수 있다면 많은 일을 할 수 있다.

 

이상적인 서명은 어때야 하는가? 단 한명만 만들 수 있는 서명, 누구나 그 서명의 주체를 확인할 수 있는 서명이 좋은 서명이다. 또, 내가 서명했다는 사실을 부인할 수 없어야 한다.

RSA 서명

다음의 상황을 가정한다.

 

• $p,~q$: 큰 소수 (공개됨)
• $n=pq$ (공개됨)
• $e$: 암호화 키 (공개)
• $d$: 복호화 키 (비공개)
• $ed=1 \mod (p-1)(q-1)$

메시지 $m$에 대해 서명 $s(m)=m^{d} \mod n$이다. 이제 메시지 $m$을 서명 $s(m)$과 함께 전송하면 된다. 서명 과정에서 비공개된 키 $d$를 사용하기 때문에, (RSA가 안전하다면) 키의 주인만이 $s(m)$을 만들 수 있다.

 

이제 이 서명의 주체를 확인해 보자. $v=(s(m))^{e} \mod n$을 계산하여 $v$와 $m$을 비교하면 서명의 주체를 확인할 수 있다. $n$과 $e$가 공개되었기 때문에 누구나 서명의 주체를 확인할 수 있다.

 

참 쉽죠? (실제로 하신 말)

엘가말 서명

다음의 상황을 가정한다.

 

• $p,~g$: 공개됨
• Alice의 공개 키: $y=g^{a} \mod p$
• Alice의 비밀 키: $a$

메시지를 $m$이라 하면, 임의의 $k$에 대해 $r=g^{k} \mod p$, $s=(m-ar)k^{-1} \mod (p-1)$이다. 이때 $(r,~s)$ 쌍이 서명이다.

 

서명의 주체를 확인하고 싶다면 $g^{m}=y^{r}r^{s} \mod p$인지 검사하면 된다. $y^{r}r^{s}=(g^{a})^{r}(g^{k})^{(m-ar)k^{-1}}=g^{ar+m-ar}=g^{m} \mod p$이므로 서명이 올바른지 확인할 수 있다.

 

그런데 엘가말 서명이 왜 안전한지 증명하는 건 꽤 어렵다. 여기서는 패스.

RSA와 엘가말 암호의 문제점

느리다!

송신자는 메시지를 잘라서 제곱을 계산하고, 수신자는 복잡한 복호화 과정을 거쳐야 하기 때문에.

 

아니 뭐 어쩌라고..

그래서 사람들이 빠른 공개 키 암호를 만들려고 노력해 봤는데, 잘 안 되더라. 그래서 지금까지도 고전 암호가 쓰이긴 한다. 고전 암호가 얼마나 안전한지도 잘 모르고, 기능도 별로 좋지 않지만 오로지 속도가 빠르다는 이유만으로 고전 암호를 쓰는 경우가 많다.

예를 들어 이런 거

정해진 규칙대로 알파벳을 바꾸는 암호 (예: A→C, B→Q, ...)

카이사르 암호라고도 불리는 암호이다. 근데 이 암호는 너무 쉽게 깨진다.

 

정해진 규칙대로 글자의 위치를 바꾸는 암호

이것도 쉽게 깨진다.

 

위의 두 방법을 같이 쓰는 암호

놀랍게도 이 암호는 아직 깨지지 않았다. 이것도 깨질 줄 알았지? 글자를 바꾸고, 순서를 바꾸고, 글자를 바꾸고... 이렇게 단순히 두 방법을 결합했을 뿐인데도.

 

여기에 속하는 암호로는 DES(상대적으로 취약함), AES(DES를 개량한 버전) 등이 있다.

실제로는 이렇게 한다

암호화 자체는 ``AES``로 하고, ``AES``에 사용된 키(임의로 생성됨)를 ``RSA``로 암호화한다. 빠르지만 상대적으로 취약한 ``AES``를 이용하여 긴 메시지를 암호화하고, 느리지만 강력한 ``RSA``를 사용하여 키를 암호화하는 것이다.

 

이 방법은 30년 넘게 사용되고 있는 방법이다. 프로세서의 발전에 따라 ``AES`` 키의 비트 수가 늘어나긴 했지만, 기본적인 틀 자체는 그대로이다.

또 다른 문제, 암호학적 해싱

# 이런 거짓말 (펼치기)

100비트짜리를 50비트로 줄이는 암호화는 존재하지 않는다. 이런 거짓말은 모르면 속아 넘어가기 쉽다. 놀랍게도 이런 말을 하는 사람들이 굉장히 많다는 점. 우리가 공부해야 하는 이유이기도 하다.

문서마다 하나의 서명이 생성되어야 하므로, 서명의 크기는 메시지의 크기와 거의 비슷할 것이다. 그런데 문서에 서명하는 이유는 문서를 바꿀 수 없게 하기 위해, 아니면 적어도 문서에 내가 서명했다는 사실 자체를 증명하고 싶기 때문이다. 따라서 서명이 너무 클 필요는 없어 보인다.

 

그런데 서명이 작아질수록 문서가 바뀌지 않았음을 보장하기 어려우므로, 적당히 몇천 비트 정도로 크게 잡자. 이 과정에서 사용되는 기술이 ``해싱``이다. 암호학에서는 긴 문서로부터 짧은 서명을 만들기 위해 해시를 사용한다. 이때 문서의 데이터에 따라 해싱 결과값이 달라진다.

 

따라서 해시를 사용하면 문서의 내용을 수정했을 때 해시 값(서명)이 달라지게 될 확률이 매우 높아진다. 실제로 어떻게 해시를 계산하는지는 12주차 2차시 2강 18:00~ 참고.

 

이러한 해시 기법의 예로 MD5, SHA 등이 있다.

생일 문제

생일이 같은 두 사람이 존재할 확률이 $p$가 되도록 하는 사람의 수 $n$을 구하시오.

$p=1$일 때 $n=366$이다. 그런데 $p=0.999$이려면 $n=70$이면 된다. $p=0.5$이려면 $n=23$이면 된다. 즉 $p$가 작아짐에 따라 $n$이 매우 급격하게 작아진다.

 

뜬금없이 뭔 소리냐고? 다음의 두 문제가 서로 다르다는 의미이다.

 

1. 메시지 $M_{1}$에 대해 $hash(M_{1})=hash(M_{2})$를 만족하는 $M_{2}$를 찾으시오.
2. $hash(M_{1})=hash(M_{2})$를 만족하는 두 메시지 $M_{1},~M_{2}$를 찾으시오.

2번이 1번보다 월등히 쉽다. 따라서 좋은 해시 알고리즘은 1번과 2번 모두 막아낼 수 있어야 한다.

정리

위에서 설명한 여러 기법을 실제로 어떻게 사용하는지 정리한다. (12주 2차시 2강 26:00~)

 

• RSA를 사용하여 AES 키를 암호화
• AES를 사용하여 전체 메시지를 암호화
• SHA를 사용하여 메시지의 해시 값을 계산
• RSA와 해시 값을 사용하여 서명을 만듦

이 방법은 90년대부터 사용된 방법이며, 아마 앞으로도 같은 방법을 사용하지 않을까 싶다.