[Cryptography] 13. Digital Signature Standard, RSA and DSA Signing

  앞서 전자서명에 대해서 간략하게 다루었다. 이번 게시글에서는 이에 대해 조금 더 깊이 알아보고, 현실에서 실제로 쓰이는 전자서명표준인 Digital Signature Standard (이하 DSS) 에 대해서 알아보도록 하자. 일반적으로 DSS라고 하면, DSA로 서명한 표준을 일컫는다.

 

 Digital Signature 이란, 내가 보내려는 메시지가 실제로 내가 보냈다는 것을 상대방에게 알려주기 위해 필요한 것이다. 이 서명 기법을 통해서 상대방은 대표적으로 Nonrepudiation 을 확보 할수있다. 수업에서는 Sender Authentication 이라는 단어로 대신 사용하였다.

 

❖ Nonrepudiation :  데이터를 송신한 자가 송신 사실을 허위로 부인하는 것으로부터 수신자를 보호하기 위하여 송신자의 발신 증거를 제공하거나, 수신자가 수신 사실을 거짓으로 부인하는 것으로부터 송신자를 보호하기 위하여 수신 증거를 제공하는 보안 서비스의 일종 (Wiki)

 

✤ Digital Signature 개요

 기존에 Public Key Cipher 을 다룰때, 간략하게 다루었던 내용은 다음과 같다. 

Digital Signature 개요 (출처 : Wikipedia)

$M$ 이라는 메세지를 상대방에게 보내고 싶을때, ( $ E_k $ 와 $D_k $ 는 Public Key Cipher 에서의 Encrypt, Decrypt 함수)

 

1. 송신자는 Decrypt gkatn $D_k$로 메시지 $M$ 에 서명을 한다. $Sign$ = $D_k$($M$)

2. 원본 메시지 $M$에 $Sign$을 붙인다. 

3. 수신자는 수신한 메시지 $M$||$Sign$ 에서 $Sign$ 부분을 분리, 공개되어있는 송신자의 Public Key 를 이용하여 서명을 확인한다.

4. $E_k(D_k($M$))$ = $M$ 이면 수신자는 송신자의 서명을 확인한 것이다. 

 

 이제 위에서 간략히 확인한 추상적인 Digital Signature 을 구체화 시켜보자.

 

우선 가장 먼저, 어떤 Public Key Cipher을 사용해야할지 선택해야한다.

 

가장 잘 알려져있고 안전하다고 평가받는 Public Key Cipher 이라하면 바로 RSA 와 ElGamal 그리고 Elliptic Curve, 이 3개를 떠올릴 수 있다. 

 

앞에서 다루었지만,

RSA는 Factorization problem의 어려움, 즉 소인수 분해의 어려움 에 기반한 공개키 암호화 기법이며,

Elgamal 와 Elliptic Curve 는  Discrete Lograithm 의 어려움, 이산 로그문제 어려움에 기반한 공개키 암호화 기법이다.

 

Digital Signature Standard 라고 함은, Modified Elgamal Cipher (DSA)을 응용한 서명기법과, RSA를 이용한 서명기법이 있다.

자세한 내용은 NIST 공식 문서를 확인하자 : csrc.nist.gov/csrc/media/publications/fips/186/3/archive/2009-06-25/documents/fips_186-3.pdf 

 

DSS 도 여러 버전이 있으며 세부 규정에 따라 'FIPS 186-3 ' 에서 FIPS 뒤에 번호가 바뀐다.

 

이번 게시물에서는 RSA를 응용한 Digital Signature, 그리고 DSA 을 응용한 Digital Signature 만 다루어 보도록 하자.

 

✣ RSA Based Digital Signature

RSA 를 이용한 전자서명은 크게 복잡하지 않다. 위에서 설명한 개요에서 단순 해싱만 중간에 추가되었다는 것 뿐이다.

 

RSA Digital Signature

 위 그림에서 볼 수 있듯이, 송신자는 메세지 $M$에 서명을 덧붙여서 송부한다. 서명은 $M$ 을 hash 한다.

참고로, 위 방법에는 다양한 종류의 해시함수가 쓰일 수 있다.

예를들어, RSA-SHA1 Signature Suite 은 해시함수로 SHA1 을 사용하는 표준이다. (참고 :www.w3.org/PICS/DSig/RSA-SHA1_1_0.html)

 

메세지의 해시값 $h(M)$은 Sign함수 $D_k$의 입력으로 주어진다. 이때 $k_d$는 송신자의 Private Key이다. (전자서명시 Decrpyt 함수를 서명함수, 즉 Sign함수 라고 하기도한다. )

 

마찬가지로 수신자는 수신한 메세지에서 서명부분을 분리하여 공개키 $K_e$ 를 사용하여 $E_k$ 로 연산하고,

message를 해시하여 그값을 비교, 동일하면 서명을 활용하여 송신자를 인증하는 과정이 끝나게 되는 것이다.

이렇게 연산하는 이유는 해시는 오직 One Directional 하기때문이다.

 

여기서 이런 의문이 들수 있다.

 

1. 왜 해시가 필요하며 왜 하필 $D_k$ 앞에 연산되어야 하는가?

 

=> 조금 더 일반화하여 Authentication과정에서 $E_k(h(M))$ 과 $h(E_k(m)$ 을 비교해보자,

암호학에서 어떤기법이 타 기법보다 낫다고 할때는, Efficiency 와 Security 를 항상 따져본다.

 

$E_k(h(M))$ 

- 장점 : 빠르다, 해시값은 항상 일정한 길이이며(일반적으로 메시지보다 짧은) 짧은 길이를 암호화 하므로 상대적으로 빠르다고 볼 수 있다.

- 단점 : 해시 충돌이 일어나면, 공격에 노출되기가 쉽다.

 

$h(E_k(m)$

- 장점 : 안전하다. 메시지는 $E_k$를 통과한 후, 해시되기 때문에, 적이 해시 충돌을 이용한 공격을 할 수가 없다.

- 단점 : 느리다. 매우 긴 메시지를 Encrypt 하는데에 시간이 오래걸릴 것이며, 심지어 복호화할때는 짧은 서명부분은 그대로 내버려두고, 길고 긴 원본메시지만을 두번 연산해야한다는 단점이 있다.

 

 결론 : 해시충돌에 안전한 해시함수를 사용한다는 전제하에, $E_k(h(M))$ 가 속도 측면에서 더 효율적이다. (안그래도 공개키 암호화 자체는 느린데...)

 

 

 

✣ Digital Signature Algorithm (Modified Elgamal based)

 

Digital Signature Standard 는 1994년 NIST에 의해 개발되었으며, 미국 정부에의해 공식적으로 승인된 전자서명 기법이다. 가장 대중화 되어있고 이 알고리즘을 Digital Signature Algorithm(DSA) 이라고 부르기도 한다. 

 

DSA Digital Signature Standard 

 

한눈에 봐도 복잡하다, 괜히 표준으로 제정된것이 아니다. 하나하나씩 뜯어보자.

송신자를 A, 수신자를 B 라고 하자, 당연히 $k_d$ 는 송신자의 private key 이다.

$k$ 는 현재 통신 세션을 위해 만들어진 랜덤한 값이며, 

또 $k_e(G)$ 는 Global Encryption key로, 현재 통신하는 그룹원 전체에게 알려진 특정한 값이다.

 

1. Signing

- 해쉬로는 SHA-1 을 사용한다.

- 입력값은 $k, k_d, k_e(G)$ 이다. 

- Sign 의 결과는 s,r 두개의 값이다.

 

수식을 옮겨적다가 날아가서 Cunsheng ding 교수님 강의자료의 수식을 복붙한다.

k_g 의 구성

DSA User Parameter

위 식에서, User's Public Key 가 $y=g^x mod p$ 임을 볼 수 있다. $p$ 는 소수이므로 위 식은 Discrete logarithm 인 것을 확인할 수 있다.

 

DSA Sigining

이때 $k$가 랜덤넘버이기 때문에 s 의 괄호 안의 값이 q 로 나누어 떨어져서 s의 값이 0 이된다면 다시계산해야한다. 하지만 그럴 확률은 매우 적다.

 

이렇게 나온 r,s값이 메시지 $M$ 의 DSA 서명이다.

DSA Signing

2. Verifying

- 마찬가지로 메세지와 서명부를 분리하여 메시지를 해시한다.

- s,r 그리고 메시지의 해시값을 verifying 함수에 통과시켜 s,r과 비교한다.

- 결과값이 s,r 으로 나오면 인증에 성공한다.

 

 

$k_g$ 의 구성 인 p,q,g 를 활용하여 검증한다.

아래 식에서 $s' , m', r'$ 은 수신한 값들을 의미한다. 

DSA Verifying

 

✣ RSA vs DSA Digital Signature 

 

그러면 DSA 와 RSA 의 차이를 알아보자.

종류	RSA	DSA
암호화 원리	소인수 분해의 어려움에 기반한다	Discrete Logarithm 문제의 어려움에 기반한다.
Key 생성	RSA는 Key 생성이 느리다.	ElGamal 비슷하게 사용하므로, RSA보다 Key 생성이 빠르다
Encryption (Verifying)	Encryption 이 DSA보다 빠르다	Encryption이 RSA보다 느리다
Decryption (Signing)	Decryption은 DSA보다 느리다	Decryption은 RSA보다 빠르다
비고	Encryption (검증)에 최적화	Decrpytion (서명)에 최적화

 

 보면, 장단점이 명확하다. 서명 (Signing) 은 DSA 가 훨씬 빠르고, 검증 (Verifying)은 RSA 가 훨씬 빠르다. 

보안 측면에서는 DSA 는 SSH 내에서는 안전하게 동작한다고 한다. RSA는 SSH2 에 서는 안전하게 동작한다. 최근에는 거의 모든 시스템이 SSH2를 적용하고 있기때문에 사용에 큰 구분은 없지만, 혹시라도 SSH를 실수로 사용할 것이 걱정된다면 DSA를 사용하는 것을 추천한다. 

하지만 Key 생성이 DSA가 빠르니까 NIST 에서 Standard로 하지 않았을까 싶다....

 

✣ Code 확인

 

간단하게 python crypto 라이브러리를 활용해서 공부한 내용을 확인해보자.

 

참고로 DSS 는 pycryptodome 라이브러리에 있고, pycrypto 에 없다. 실습전 import Crypto 가 반드시 pycryptodome 인지 확인하고 하자.

 

[DSA 실습]

DSA 를 활용한 Key 생성

위 코드에서 key는 필요한 global key, 공개키, 개인키 이다.

 

위와 같이 Key format 과 key 생성에 걸린 시간을 볼 수 있다. 

 

 

DSA - Signing

Signature, elapsed time for signing

 

 

DSA-Verifying

DSA- Elapsed Time for verifying

 여기까지 보면, DSA 는 signing 에 0.00168 초, verifying 에 0.0028초가 걸렸음을 알 수 있다. 알려진대로 verifying이 더 느리다.