yeolyi.com성열의 컴퓨터공학

디지털 서명

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

은행이 “100원을 보내라”는 메시지를 받으면 계좌 주인이 보낸 것이 맞는지, 중간에 금액이 바뀌지 않았는지 알아야 합니다. 공개 키로 잠그는 일은 누구나 할 수 있으니 이를 알려 주지 못합니다.

거꾸로 쓰는 자물쇠

RSA를 거꾸로 써 봅시다. 보내는 쪽은 메시지 m을 개인 키로 거듭제곱해 s = m^d mod n을 만듭니다. 받는 쪽은 공개 키로 s^e mod n을 계산해 m과 같은지 봅니다.

잠갔다 열 때와 거듭제곱하는 순서만 다릅니다. 나머지 연산 글에서 본 것처럼 중간에 나머지를 구해도 결과는 같으니, 둘 다 m을 e × d제곱해 n으로 나눈 나머지입니다. 그래서 열 때처럼 언제나 m이 돌아옵니다.

개인 키는 주인만 가졌으니 s는 주인만 만들 수 있고, 확인은 공개 키를 가진 누구나 할 수 있습니다. 종이 문서의 도장과 같은 이 s를 디지털 서명(digital signature)이라 합니다.

보낼 금액 m 100
보낸 쪽 (개인 키 d = 2753)메시지 100서명 1002753 mod 3233 = 1391
받은 쪽 (공개 키 e = 17)메시지 100서명 139117 mod 3233 = 100

서명을 풀면 100, 받은 메시지와 같습니다. 개인 키 주인이 보낸 그대로입니다.

중간에서 메시지를 바꿀 수는 있어도, 개인 키가 없으니 바뀐 메시지에 맞는 서명을 새로 만들 수 없습니다. 그래서 서명이 맞으면 두 가지를 함께 알 수 있습니다. 개인 키 주인이 보냈고, 보낸 뒤로 한 글자도 바뀌지 않았습니다.

요약값에 서명하기

RSA는 n보다 작은 수만 다루니 긴 메시지는 그대로 서명할 수 없습니다. 그래서 실제 서명은 메시지를 짧게 줄인 요약값(digest)에 합니다. 줄이는 방법은 해시 테이블 글의 해시 함수처럼 긴 값을 넣으면 짧은 값이 나오는 함수입니다.

해시 테이블에서는 서로 다른 키가 같은 칸에 부딪히는 충돌을 피할 수 없었습니다. 서명에 쓰는 함수도 충돌이 아예 없지는 않지만, 같은 요약값이 나오는 다른 메시지를 일부러 찾기가 사실상 불가능하도록 설계합니다. 이런 함수를 암호용 해시 함수(cryptographic hash function)라 합니다. 그래서 요약값에 한 서명은 메시지 전체에 한 서명과 같은 역할을 합니다.

도전 문제

주인의 공개 키는 n = 85, e = 3이고, 요약값 없이 메시지 수에 바로 서명합니다. 엿보는 사람이 주인이 메시지 2에 단 서명 8과 메시지 7에 단 서명 48을 모았습니다. 개인 키 없이 이 둘만으로 메시지 28의 확인을 통과하는 서명(0 이상 85 미만)을 만들 수 있습니다. 그 서명은 얼마일까요? 숫자로 답하세요.