공개키 암호와 디지털 서명

디지털 서명

인터넷에서 다운로드한 프로그램을 실행할 때 한번쯤은 "게시자를 확인할 수 없음"과 비슷한 경고를 보았을 것이다.

이러한 경고 메시지가 뜨는 이유를 찾아보면, 다운로드한 프로그램에 디지털 서명이 없기 때문이라고 하는 이야기를 주로 한다. 예술가들이 그림을 그리고 나서 자신의 그림임을 보장하기 위해 자신의 이름으로 서명하는 것처럼, 컴퓨터공학에도 비슷한 개념이 존재한다. 디지털 서명이 있는 프로그램은 프로그램 개발자가 만든 그대로의 프로그램임을 보장하지만, 그렇지 않은 프로그램은 악의적인 의도를 가진 사람^[1]이 프로그램을 조작했을 가능성이 있어서 이러한 경고를 보여 주는 것이다. 하지만 이 정도의 설명만을 들으면, 서명도 결국 데이터인데 악의적인 의도를 가진 사람이 복제하지 않을까 하는 의문이 들 것이다. 이 의문에 대한 답은 디지털 서명이 서명하는 데이터에 따라 달라진다는 것인데, 디지털 서명이 어떻게 데이터마다 다르게 이루어지는지, 그리고 어떻게 활용되는지를 알아보려면 글을 끝까지 읽어보자.

디지털 서명의 생성 과정

우선 디지털 서명이 만들어지는 과정부터 살펴보자.

1. 비밀 키와 공개 키를 생성한다.
2. 서명하려는 데이터를 해시 함수에 입력하여 해시값을 구한다.
3. 해시값과 비밀키를 이용하여 특수한 계산을 한다. 이 계산의 결과값이 디지털 서명이다.

비밀 키는 어떤 데이터를 서명할 때에 사용되고, 공개 키는 데이터에 대한 서명이 유효한지 검증하는데 사용된다. 공개 키 암호는 바로 이 공개 키와 비밀 키의 존재에 그 특성이 있다고 할 수 있다. AES와 같은 일반적인 대칭 키 암호는 암호화와 복호화에 사용되는 키가 같은 반면, 공개 키 암호는 그렇지 않기 때문에 대칭 키 암호에서 구현하기 힘든 디지털 서명을 구현할 수 있다. 3번에서 언급한 해시 함수^[2]는 임의의 길이의 데이터를 받아서 데이터마다 고유한 값, 해시값을 계산해서 주는 함수이다. 해시 함수는 일방향성을 가지는데, 이는 아무 데이터나 가져와서 해시값을 계산하는 것은 쉽지만 해시값만으로 원래 데이터를 알아내기는 불가능에 가까울 정도로 어렵다는 것을 의미한다.^[3] 이 해시 함수의 종류는 여러 가지가 있고, 어떤 해시 함수를 사용하여 디지털 서명을 만들어 내는지는 디지털 서명의 표준에 따라 달라진다.

3번에서 수행하는 '특수한 계산'의 결과는 서명하는 데이터의 해시값, 생성한 비밀 키와 공개 키에 따라 달라진다. 어떤 계산을 하는지는 서명 알고리즘에 따라 달라지는데, 여기서는 RSA 디지털 서명 방식에 대해 알아보자.

사례 연구: RSA 디지털 서명 알고리즘

중학교 소인수분해를 배울 때, 흔히 "이것이 왜 쓸모가 있는가"에 대한 예시로 RSA 암호체계^[4]가 자주 나온다. 여기에서는 이 RSA 암호화를 사용해 디지털 서명을 생성하는 과정을 다룰 것이다.

키 생성 과정

RSA 암호체계에서의 키 생성은 다음과 같은 과정으로 이루어진다.^[5]

1. 무작위로 서로 다른 큰 소수 \(p\), \(q\)를 생성한다. 이때 생성한 소수의 크기가 비슷하면서도 몇 자리수 차이가 나야 한다는 조건이 있는데, 이는 소인수분해를 어렵게 만들기 위해서이다. 대부분의 소인수분해 알고리즘은 소인수의 개수가 적을수록 비효율적으로 동작하기 때문이다.
2. 공개키의 일부 \(n=pq\)를 계산한다.
3. \(\mathrm{gcd}(d, (p-1)(q-1))=1\)인 \(d\)를 고른다. 여기서 \(d\)가 비밀키가 된다.
4. \(e\equiv d^{-1}\;(\text{mod }(p-1)(q-1))\)을 계산한다. \(e\)는 공개키의 일부가 된다.^[6]

결론적으로 비밀키는 \(d\)이고, 공개키는 \((n, e)\)가 된다. 위 단계들에서 정수론의 몇 가지 개념들이 필요한데, 여기서 잠깐 알아보자. 가장 기본이 되는 것은 합동식이라는 개념이다. \(a\)와 \(b\)가 \(n\)으로 나눈 나머지가 같을 때, 다음과 같이 쓸 수 있다.

\[a\equiv b\quad(\text{mod }n)\]

또한, 4번 단계에서 \(d^{-1}\)이라는 모듈러 역원이 나오는데, 이는 우리가 익숙하게 여기는 실수체의서의 '역수'와는 약간 다른 개념이다. 어떤 정수 \(x\)의 모듈러 역원 \(x^{-1}\)은 다음 합동식을 만족하는 수로 정의된다.

\[x\cdot x^{-1}=1\quad(\text{mod }n)\]

이는 실수에서 \(x\)와 그의 역수 \(x^{-1}\)을 곱했을 때 1이 되는 것과 비슷하다.^[7]

디지털 서명 알고리즘

이제 RSA 암호체계를 사용해 디지털 서명을 생성하는 과정을 알아보자. 서명하려는 데이터의 해시값은 SHA-2-256과 같은 적당한 해시 함수를 이용해 계산하고, 이를 \(h\)라고 하자. 이때 디지털 서명은 \(h^d\)를 \(n\)으로 나눈 나머지와 같다.^[8] 디지털 서명을 검증하기 위해서는 공개 키의 일부 \(e\)를 사용하여 \((h^d)^e\)를 \(n\)으로 나눈 나머지를 계산하면 된다. 서명이 유효하다면 계산의 결과는 \(h\)여야 하므로, 계산 결과를 데이터에서 구한 해시값 \(h\)와 비교만 하면 된다.

공격자가 자신이 가진 데이터에서 서명을 위조하기 위해서는 비밀키를 알아야 하는데, 이를 알기 위해서는 \(n\)을 소인수분해하여 \(p\)와 \(q\)를 구하고, \(e\)를 통해 \(d\)를 구해야 하므로 서명의 위조가 어렵게 된다.

알고리즘의 정당성 증명

앞서 설명한 디지털 서명 알고리즘이 원하는 대로 동작함을 알기 위해서는, 서로 다른 소수 \(p\), \(q\)와 모든 정수 \(m\)과 \(ed\equiv 1\;(\text{mod }(p-1)(q-1))\)을 만족하는 \(e\)와 \(d\)에 대해 다음 식이 만족함을 보여야 한다.

\[(m^e)^d\equiv m\quad(\text{mod }pq)\]

이 증명을 위해 오일러의 정리를 사용할 수 있다. 오일러의 정리는 서로소인 정수 \(n\)과 \(a\)에 대해, 다음이 성립함을 알려 준다. 여기서 \(\varphi(n)\)은 오일러 파이^[9] 함수라고 부르는데, 1부터 \(n\)까지 \(n\)과 서로소인 수들의 개수를 세는 함수이다.^[10]

\[a^{\varphi(n)}\equiv 1\quad(\text{mod }n)\]

한편, 오일러 파이 함수의 정의를 생각하면 소수 \(p\)에 대해 \(\varphi(p)=p-1\)이다. 또한, 오일러 파이 함수는 곱으로 쪼갤 수 있기 때문에 다음이 성립한다.

\[\varphi(pq)=\varphi(p)\varphi(q)=(p-1)(q-1)=pq-(p+q)+1\]

한편, \(d\)는 정의에 따라 \(\varphi(pq)=(p-1)(q-1)\)과 서로소이기 때문에 \(d\)의 모듈러 역원 \(e\)는 존재한다. \(ed\equiv 1\;(\text{mod }\varphi(pq))\)를 이용하면, 다음이 성립함을 알 수 있다. 여기서 \(k\)는 어떤 자연수이다.

\[m^{ed}\equiv m^{k\varphi(pq)+1}\quad(\text{mod }pq)\]

\(m\)이 \(pq\)와 서로소인 경우, 오일러의 정리를 사용하면 간단하게 증명된다.

\[m^{k\varphi(n)+1}=m\left(m^{\varphi(n)}\right)^k\equiv m\quad(\text{mod }pq)\]

\(m\)이 \(pq\)와 서로소가 아닌 경우는 매우 드물기 때문에 증명하지 않고 넘어간다... 라고도 할 수 있지만 사실 이 때도 상관은 없다. 다음 식을 보자.

\[m^{k\varphi(n)+1}\equiv m\quad(\text{mod }p)\]

\(m\)과 \(p\)가 서로소라면, 위 식은 오일러의 정리에 의해 성립한다. \(m\)과 \(p\)가 서로소가 아니라면, 양변은 모두 0과 합동이므로 그래도 성립한다. 이러한 논리를 \(q\)에 대해서도 비슷하게 사용할 수 있으므로, 다음과 같이 \(m^{ed}\)을 나타낼 수 있다. (\(a\), \(b\)는 어떤 자연수이다.)

\[m^{ed}=ap+m=bq+m\]

이를 이용하면 \(m\)이 \(pq\)와 서로소가 아닐 때에도 역시 \(m^{ed}\equiv m\;(\text{mod }pq)\)임이 증명된다.

디지털 서명의 사용: PE 파일 포맷

여기까지 디지털 서명이 무엇인지와 RSA 암호체계를 이용해 디지털 서명을 구현하는 방법에 대해 알아보았다. 이제 앞서 말한 "게시자를 확인할 수 없음" 경고로 돌아가 보자. 프로그램의 실행 파일에서 디지털 서명은 어떻게 사용될까? 이를 알기 위해서는 OS의 실행 파일 포맷을 살펴볼 필요가 있다. 여기서는 널리 사용되는 OS 중에서도 디지털 서명과 관련된 경고를 자주 볼 수 있는 윈도우를 기준으로 설명할 것이다.

윈도우의 실행 파일 포맷은 PE 파일 포맷이라고 부른다. PE 파일 포맷에서는 실행 파일의 종류, 파일에 있는 section들의 오프셋, 사용하는 라이브러리 등을 PE 헤더에 저장한다. 이 PE 헤더 중에서 OS에서 실행 타임에 사용할 수 있도록 메모리에 로드할 데이터가 저장되는 곳이 있다. 이를 데이터 디렉터리라고 하고, IMAGE_OPTIONAL_HEADER32라는^[11][12] 헤더 데이터에 저장된다. 이 데이터 디렉터리에서 attribute certificate table 이라는 것이 있다. 이 테이블의 wCertificateType 필드에 인증서 종류가 저장되는데, 현재로서 윈도우는 PKCS#7 SignedData만 지원한다. 인증서의 데이터가 저장되는 곳은 bCertificate이다. PE 파일의 디지털 서명은 마이크로소프트에서 "Authenticode PE Image Hash"라고 부르는 해시값으로 만든다. 이 해시값은 PE 파일에서 인증서나 체크섬이 저장되는 부분들만 제외하고 SHA-2-256 함숫값을 구한 것이다.^[13] 해시값은 앞서 설명한 대로 디지털 서명을 하는 데 사용된다.

지금까지 흔히 볼 수 있는 윈도우의 경고 메시지에서 RSA 암호체계에 기반한 디지털 서명 알고리즘, PE 파일 포맷에 디지털 서명이 저장되는 방법에 대해 알아 보았다. 공개 키 암호체계에 기반한 디지털 서명 알고리즘은 실생활을 지탱하고 있는 중요한 알고리즘 중 하나라고 할 수 있고, 최근 들어 RSA 암호체계 대신 타원 곡선^[14] 암호를 활용한 ECDSA도 널리 사용되고 있다. 현재와 같은 수준의 보안이 있게 한 이 알고리즘들을 더욱 자세히 알아보는 것도 좋은 경험이 될 것이다.

더 읽을거리

• RSA 논문: RSA 암호화를 처음 개발한 연구자들의 논문이다.
• PKCS#1: IETF에서 현재 사용되고 있는 RSA 암호화의 표준을 정해 놓은 문서이다. 이 글에서는 원래 논문에서의 RSA 알고리즘을 다룬 것과는 달리, PKCS#1에서 설명하는 것은 현재 사용되는 알고리즘과 더 비슷하다.
• OpenSSL 소스 코드: 널리 사용되고 있는 암호화 라이브러리인 OpenSSL의 소스 코드이다. RSA 암호화를 어떻게 구현했는지 코드를 읽어보는 것도 도움이 될 것이다. RSA 키 생성의 구현은 RSA_generate_key_ex, 디지털 서명의 생성 구현은 RSA_sign, 디지털 서명의 검증 구현은 RSA_verify 함수에서 보면 된다.^[15]
• PE 파일 포맷: 윈도우의 PE 파일 포맷을 설명한 문서이다. 윈도우의 역사 동안 호환성을 지키면서 변경되었기 때문에 현재 기준으로 필요 없는 부분도 꽤나 많아 양이 방대하다.
• SEC 1: 끝내면서 잠깐 언급했던 타원 곡선 암호를 활용한 ECDSA를 표준으로 정해 놓은 문서이다. 필요한 수학적 배경부터 알고리즘까지 상세하게 설명되어 있기 때문에 관련 지식이 부족하더라도 읽을 만 할 것이다.

참고 문헌

• R. L. Rivest, A. Shamir, and L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems," Communications of the ACM, vol. 21, no. 2, pp. 120–126, Feb. 1978.
• OpenSSL, "openssl/openssl," GitHub, Jan-1999. [Online]. Available: https://github.com/openssl/openssl. [Accessed: 28-May-2021].
• 이민섭, 현대암호학, 2nd ed. 동대문구, 서울: 교우사, 2008.
• Microsoft Corporation, "PE Format - Win32 apps," Win32 apps | Microsoft Docs, 31-Mar-2021. [Online]. Available: https://docs.microsoft.com/en-us/windows/win32/debug/pe-format#the-attribute-certificate-table-image-only. [Accessed: 28-May-2021].

---

1. 영어에는 adversary라는 매우 편리한 단어가 있지만 한국어에서는 어떻게 단어 선택을 해도 느낌이 안 나온다... ↩︎

2. 사실 여기서 말하는 해시 함수는 암호학적 해시 함수라고 하는 것이 더 정확하다. 해시 함수에는 여러 종류가 있지만 디지털 서명에 사용할 정도가 되려면 preimage resistance와 같은 성질이 필요하기 때문이다. ↩︎

3. 예리한 독자들은 해시값으로 가능한 값은 많아야 \(2^{512}\)개 정도지만 넣을 수 있는 데이터의 가짓수는 이보다 더 많다는 생각을 할 것이다. 이는 합당한 지적인데, 해시 함수는 다른 2개의 데이터에 대해 같은 해시값을 주는 충돌 쌍이 존재할 수밖에 없다. 잘 설계된 해시 함수에서는 이 충돌 쌍을 찾는 것은 매우 어렵지만, 가끔 성공하는 사례들이 있다. ↩︎

4. 중학교 1학년 때 소인수분해를 배울 때, 수학의 유용성 이야기를 할 때 자주 거론되는 RSA 암호체계는 큰 수의 소인수분해가 컴퓨터에서 비효율적임을 전제해 만들어진 알고리즘이다... 라고들 하지만 이는 제대로 된 설명이 아니다. RSA 암호체계를 공격하기 위해 풀어야 하는 문제는 RSA 문제이고 현재까지 이 문제를 해결하는 가장 효율적인 방식이 큰 수의 소인수분해를 사용하는 것일 뿐이다. RSA 문제가 소인수분해 문제만큼 어려운지는 아직도 밝혀지지 않았기 때문에, 그냥 막연하게 RSA 암호체계는 소인수분해 문제가 어렵다는 전제 하에 만들어진 알고리즘이라고 하기에는 논리적으로 문제가 있다. 물론 소인수분해를 사용하지 않고 RSA 문제를 해결하는 것도 결코 만만한 문제는 아니다. 70년대에 발명된 알고리즘이 2021년에도 계속 사용되고 있다는 것을 생각하면 말이다. ↩︎

5. 현재 사용되고 있는 RSA 알고리즘은 계산의 효율성 때문에 여기 설명된 방법과는 약간 다른 방법으로 키를 생성하지만, 원리는 거의 비슷하다. 여기서는 RSA 논문에서 설명된 대로 알고리즘을 설명하고 정당성을 증명할 것이다. ↩︎

6. 논문의 알고리즘에서는 \(d\)를 \(e\)보다 먼저 계산하므로 \(e\)가 \(d\)에 비해 클 가능성이 있다. 서명을 생성하고 검증할 때 어떤 수를 각각 \(d\)제곱, \(e\)제곱해야 하기 때문에 논문의 알고리즘은 서명의 생성이 검증보다 효율적이다. 반면 현재 사용되는 알고리즘은 \(e\)를 먼저 계산하기 때문에 서명의 검증이 생성보다 더 효율적이다. ↩︎

7. 수학이 언제나 그렇듯, 이 비슷함은 우연이 아니라 의도된 것이다. 궁금하다면 갈루아 군 \(\mathbb{F}_p\) (\(\mathrm{GF}(p)\)라고 쓰이기도 한다)에 대해 찾아보는 것도 좋을 것이다. ↩︎

8. 예리한 독자들은 \(d\)가 매우 큰 수(수백 비트는 넘어간다)인데 어떻게 컴퓨터에서 빠르게 계산할 수 있는지가 궁금할 것이다. 이를 최적화하기 위해서는 exponentation by squaring이라는 방법을 사용하는데, 간단히 말해 \(h\)를 제곱해 \(h^2\)을 구하고 이를 계속 제곱해 \(h^4\), \(h^8\)등을 얻은 뒤 필요한 수들을 적당히 곱해 \(h^d\)를 구하는 것이다. 이렇게 하면 곱셈의 횟수가 \(d\)가 아니라 \(\log_2 d\)에 비례하므로 더욱 효율적이다. ↩︎

9. 그리스 문자 \(\varphi\)는 한국어로 '파이'라고 표기하기 때문에 원주율이나 prime counting function, 강화 학습의 policy 등을 나타내는 \(\pi\)와 헷갈리기 쉽다. 말할 때 구분하고 싶다면 ㅍ을 f로 발음하면 된다. ↩︎

10. 이 정의를 듣고 "와! 어떤 수와 서로소인 수들의 개수를 센다니! 정말 쓸데없는걸?"이라는 생각이 들 수도 있다. 굳이 말하면 수학의 대부분은 "쓸데없는" 것으로 가득 차 있지만(사실 이런 식으로 따지면 수학뿐만 아니라 대부분의 학문은 "쓸데없다"), 오일러 파이 함수는 모듈로 \(n\)의 곱셈군 \((\mathbb{Z}/n\mathbb{Z})^\times\)의 원소 수라는 나름대로 중요한 의미를 가진다. 하지만 이 정의대로 설명하면 대수적 구조와 현대대수학을 통째로 설명해야 하고, 그것만으로 글 하나 분량이기 때문에 그나마 이해하기 쉬운 서로소를 사용한 정의를 사용하기로 했다. ↩︎

11. 64비트 바이너리라면 헤더의 이름이 IMAGE_OPTIONAL_HEADER64이다. ↩︎

12. 리버싱을 배울 때나 지금이나 헤더 이름이 optional header인지는 알다가도 모르겠다. 윈도우에서 PE 파일이 정상적으로 실행되기 위해서는 어쨌든 이 헤더가 필요하기 때문이다. ↩︎

13. 이전 버전에서는 해시 알고리즘으로 SHA1이나 MD5가 사용되었지만 두 알고리즘 모두 취약점이 발견되어 SHA-2-256을 사용 중이다. ↩︎

14. 놀랍게도 이름과 달리 타원 곡선은 하나도 타원처럼 안 생겼다. 심지어 암호체계를 만들기 위해서 타원곡선은 갈루아 군 \(\mathbb{F}_p\)나 \(\mathbb{F}_{2^{m}}\)위에서 정의되는데, 여기서 정의된 타원곡선은 '곡선'처럼 보이지도 않는다. ↩︎

15. OpenSSL의 RSA low-level API는 deprecated 되었기 때문에 여기 소개된 함수를 보안이 중요한 환경에서는 사용하지 않아야 한다. ↩︎