[Web] Dreamhack STAGE 6

https://dreamhack.io/lecture/roadmaps/3

Cryptography

---

[ web stage 6: 전자서명 ]

 

* 서론

 - 전자 서명(digital signature)은 서명의 특징을 암호학적으로 구현한 것

 - 전자서명은 공개키 암호와 함께 만들어짐

 - 공개키 알고리즘에서의 개인키로 서명을 생성하고, 공개키로 그 서명에 대한 검증 진행

   이때, 서명을 생성하는 개인키는 서명키(signing key) / 검증에 사용되는 공개키는 검증키(verification key)

 - 주로 메시지의 무결성과 부인 방지를 위해 사용됨

 

 

* 기본원리

1. 서명과 검증

 - 공개키 암호에서의 공개키, 개인키와 유사하게 전자 서명에서 사용하는 검증키는 공개된 키이며, 서명키는 서명자

    본인만 알고 있어야 하는 비밀키임.

 - 메시지를 서명키로 암호화하는 과정을 서명 작성(signing), 서명을 검증키로 복호화하고 받은 메시지와 비교하는

    과정을 서명 검증(verification)이라고 함.

 

→ 위의 과정을 통해 만들어진 서명을 메시지와 함께 보내면 수신자는 서명자의 검증키를 이용해 $$ Ver_{pk}(m,s)$$ 값을 계산하여 이를 검증함

→ 서명자의 개인키로 서명했을 때만 검증을 통과할 수 있으므로 서명이 올바르다면 메시지는 서명자로부터 왔음이 증명됨.

→ 전자 서명을 사용하면 메시지의 무결성을 증명할 수 있고, 서명자는 자신이 메시지를 보냈음을 부인할 수 없음

 

2. 해시 함수를 이용한 전자 서명

 - 전자서명은 공개키 암호를 사용하기 때문에 서명하는 메시지의 크기가 N(modulus)보다 작아야 함

 - 따라서 만약 메시지의 크기가 N보다 크다면 이를 나누어 서명해야 함.

 - 위와 같은 불편함을 해소하고, 데이터의 크기와 상관없이 한 번에 서명하기 위해 일반적으로 해시 함수를 같이 사용함

→ 해시 함수를 이용한 전자 서명에서는 해시 함수로 메시지의 해시 값을 생성하고, 이 값에 대한 서명을 생성함.

   이를 수식으로 표현한다면 다음과 같으며, 이때 h는 임의의 암호학적 해시함수를 의미함

→ 전자 서명에서 해시 함수를 이용할 경우 효율성 뿐만 아니라 안전성 향상에도 도움이 됨

 

 

* RSA 전자 서명

 - RSA 전자 서명은 RSA 공개키 암호를 사용하여 서명과 검증이 이루어짐

 - RSA 공개키 암호에서의 공개키는 검증키로 사용되고 개인키는 서명키로 사용됨

 - RSA 전자 서명의 안전성은 RSA 공개키 암호와 마찬가지로 인수분해 문제의 어려움에 기반하고 있음.

→ RSA 공개키에 나왔던 똑 같은 키 생성 방법을 통해 나온 공개키 (n,e)를 검증키로, 개인키는 d를 서명키로 사용함

 

1. 서명 생성

- 서명키 d로 메시지 m에 대한 서명 s를 다음 수식을 통해 생성

 

2. 서명 검증

 - 서명 값 s와 메시지 값 m에 대한 검증을 검증키 (n,e)를 통해 다음과 같이 수행함

 - 위의 수식을 계산하고 m’과 메시지 m이 같은 값인지 확인한다.

→ 그 결과 같은 값이라면 s는 유효한 서명이고, 그렇지 않다면 유효한 서명이 아님.

 

3. RSA 전자 서명 공격

 1) 공격자가 검증키 (n,e)를 알면 유효한 메시지와 서명 쌍 (m,s)를 생성할 수 있음

    → 임의의 서명값 s를 선택하고 메시지 m을 아래의 식으로 생성하면 유효한 메시지, 서명 쌍을 생성할 수 있음

 

  2) 공격자가 두 개의 유효한 메시지와 이에 대응되는 서명 쌍 (m1, s1,), (m2,s2)을 알고 있다면, 다른 유효한 평문과 서명의 쌍 (m1m2, s1s2)를 생성할 수 있음

 

 

4. 해시를 이용한 RSA 전자 서명

 - 해시를 이용한 RSA 전자 서명에 위의 공격들을 수행하려면, 아래의 식을 만족하는 m을 구할 수 있어야 함

 

 - 위와 같은 상황은 해시 함수의 역상 저항성(preimage resistance)으로 인해 매우 어려움

 

 

* ElGamal 전자 서명

 - 이산 대수 문제의 어려움에 기반하여 설계

 - ElGamal 전자 서명을 모태로하여 DSA(Digital Signature Algorithm) 전자 서명 등 다양한 전자 서명이 설계됨

 - ElGamal 전자 서명 과정에서도 해시를 사용함

 

1. ElGamal 키 생성

 - 큰 소수 p와 키를 만드는 생성원 g를 선택함.

 - 그 뒤, p-1보다 작고 1보다 큰 정수 x를 임의로 선택함

 - $$ y=g^{x}(mod\, p)$$   를 계산하여 (y,g,p)를 검증키로, x를 서명키로 사용

 

2. 서명 생성

 - 메시지 m과 서명키 x에 대한 서명 값 s를 아래의 과정에 따라 생성 

- p-1보다 작고, 이와 서로소인 정수 k를 임의로 선택하고, 아래의 계산을 통해 서명 값을 생성

 

3. 서명 검증

'

 

* ElGamal 전자 서명 공격

 - 서명 생성 과정에서 매번 서명을 할 때마다 새로운 난수 k를 선택하여 사용하기 때문에 동일한 메시지에 대해서도 서명 값이 항상 변함

   → 비결정적(Nondeterministic) 성질

     : 이로 인해 RSA 서명 기법에 존재하던 문제점이 ElGamal에서는 대부분 해결됨

 - 다만, 난수 k를 매번 같은 값으로 고정하면 서명키 x가 노출될 수 있음

 - 서명키 x를 알면 원하는 메시지의 서명 값 또한 구할 수 있기 때문에 매우 위험한 취약점임

 - 따라서 k 값은 고정된 값이 아닌 적절한 난수 값으로 정해야 함

 

 

* DSA 전자 서명

 - 1991년 NIST에 의해서 제안되었으며 1994년 12월에 미국의 전자 서명 기법 표준으로 제정됨

 - 다른 서명에 비해서 훨씬 짧은 서명 길이를 가지는 장점이 있음

 - 사용하는 소수 p가 1024비트라면 ElGamal 서명은 2048비트 크기의 서명을 생성하는 반면, DSA는 320비트로 매우

    작은 서명을 생성함

 - 성능 면에서도 RSA 전자 서명보다 빠르다고 알려져 있음

 

1. DSA 키 생성

 - 큰 소수 p와 p-1의 약수이면서 소수인 q를 선택함

 - 이후 p-1보다 작고 1보다 큰 정수 h를 선택하고 생성원 g를 계산함

 - 만일 계산한 g가 1이 되면 h를 다시 선택하여 1이 아닌 g를 구한다

 

2. 서명 생성

 - 1~q-1 범위의 난수 k를 임의로 선택한 뒤, 아래의 수식으로 서명 값 계산

 

3. 서명 검증