[암호학]전자서명(Digital Signature): 어떻게 해?

* Medium에 게시한 글입니다. Medium에서 읽으시면 좀 더 좋은 환경에서 보실 수 있습니다.

[암호학]전자서명(Digital Signature): 어떻게 해?

이전 글에서 말했듯이 MAC은 아주 괜찮은 녀석이지만 전자서명 기능을 제공할 수 없다… 송수신자가 같은 Key를 공유하기 때문이다.

그래서 전자서명 기법이 따로 개발됐다. 송신자를 유일하게 식별할 수 있어야 하므로 공개키 기법을 사용한다.

전자서명은 다음과 같은 기능들을 제공해야 한다

• 메세지 내용 인증
• 메세지 작성자, 작성한날짜 인증
• 분쟁이 생겼을 경우 삼자에 의한 인증

그렇다면 본격적으로 살펴보자

전자서명의 requirements

• 현재 서명을 하는 메세지부터 생성돼야 한다.
• 송신자를 유일하게 식별할 수 있는 값을 이용해서 생성해야 한다. (부인방지!)
• 전자서명을 만들기 쉬워야한다!(computational한 부분에서)
• Verify하기도 쉬워야한다!
• 저장소에 서명의 copy를 저장하기 용이해야 한다.(즉, 크기가 작아야 한다)
• 전자서명을 다른 사람이 위조하기 어려워야한다. (현재 메세지에 대한 거짓 서명을 하기도 어려우며 현재 서명에 대한 거짓 메세지를 만들기도 어려워야 한다. 말이 어렵다지 불가능해야한다. 거어어어어의)

전자서명이루어지려면 우선 수신자는 송신자의 공개키를 알아야 한다.

전자서명은 세 가지 방법으로 만들 수 있다.

1. 송신자가 전체 메세지를 자신의 비밀키로 암호화한다.

2. 송신자가 전체 메세지를 해쉬한 후 자신의 비밀키로 암호화한다.

3. 송신자가 어떤 특정 전자서명-generation 알고리즘을 사용해 서명을 만들어 낸다.

대표적인 전자서명 알고리즘을 알아보자

DSA(Digital Signature Algorithm)

ElGamal & Schnorr scheme의 변형으로 전자서명만 제공한다! 암호화 용도가 아니다.

• 320bit의 서명을 만들어 낸다.
• 파라미터의 크기는 512~1024bit 사이로 소수(prime number)여야 한다.
• RSA보다 크기가 작고 빠르다
• 이 기법이 뚤릴 가능성은 Discrete logarithm 문제가 뚤릴 가능성과 같다.

다음 그림은 RSA와 DSA를 비교한 그림이다.

RSA는 Traditional 최초의 전자서명 기법이다.

RSA보다 복잡해 보이긴 하지만 그만큼 더 안전하다.

서명을 하는 절차를 살펴보자.

• Global public key 값인 (p, q, g)를 공유한다.

p는 아주 큰 소수로 다음을 만족한다.

2^(L-1) < p < 2^L

q는 다음을 만족하는 소수이다

2¹⁵⁹ < q < 2¹⁶⁰

g는 다음과 같이 계산한 값이다.

g = h^((p-1)/q)

이 때, 1 < h < p-1 && { h^((p-1)/q) mod p} > 1을 만족해야 한다.

유저는 비밀키를 이용해 공개키를 생성한다.

비밀키 x < q

공개키 y = g^x mod p

자 이제 송수신자가 DSA를 쓰기 위한 준비가 끝났다.

이제 한번 서명을 해보자

송신자

송신자가 q보다 작은 랜덤한 수를 생성한다(일회용이다)

k, k < q

이제 서명을 하자. 서명은 두 개의 수 (r,s)로 이뤄져있다.

r = (g^k mod p) mod q

s = (k^-1 (H(M) +xr)) mod q

이제 (r,s)를 메세지 M과 함께 전송!

수신자

수신자는 메세지 M과 서명 (r,s)를 받았다.

이제 이걸 어떻게 인증하냐! 다음과 같은 순서로 값을 계산한다.

w = s^-1 mod q

u1 = (H(M)w) mod q

u2 = rw mod q

v = ((g^u1*y^u2) mod p ) mod q

끝이다! v == r이라면 인증이 완료다.

사실…미안하다. 처음 보고 이걸 알아들을 수 있는 사람이 얼마나 있을까?

나 또한 더 공부해야한다.

전자서명은 굉장히 자주 사용되는 기법이니 잘 알아두자.