2022. 8. 25. 12:00ㆍ22-여름방학/암호학
전자 서명
1. 들어가며
서명의 목적은 메세지가 서명자에게서 왔음을 증명하고, 문서 작성으로 인해 발생하는 모든 문제에 대한 책임이 서명자에게 있음을 명시하는 것으로, 전자 서명은(Digital Signature)은 서명의 이런 특징을 암호학적으로 구현한 것이다.
전자 서명은 공개키 암호가 만들어지며 같이 만들어졌고, 1978년 RSA 암호 알고리즘이 만들어지면서 전자 서명이 사용되기 시작했다.
전자 서명 알고리즘에는 공개키 알고리즘에서의 개인키로 서명을 생성하고, 공개키로 그 서명에 대한 검증을 진행한다. 이때, 서명을 생성하는 개인키를 서명키(Signing Key), 검증에 사용되는 공개키를 검증키(Verificaion Key)라고 한다.
전자 서명은 주로 메세지의 무결성과 부인 방지를 위해 사용된다.
2. 전자 서명
1. 기본 원리
-서명과 검증
- 공개키 암호에서의 공개키, 개인키와 유사하게 전자 서명에서 사용하는 검증키는 공개된 키이며, 서명키는 서명자 본인만 알고 있어야 하는 비밀키이다.
- 메세지를 서명키로 암호화하는 과정을 서명 작성(Signing), 서명을 검증키로 복호화하고 받은 메세지와 비교하는 과정을 서명 검증(Verification)이라고 한다.
- RSA에서는 수신인의 공개키로 데이터를 암호화해서 전송하고, 수신인이 이를 개인키로 복호화했다면, 전자 서명은 정확히 반대 과정으로 이루어진다.
- 검증키를 pk, 서명키를 sk, 서명 검증 알고리즘을 Ver, 서명 생성 알고리즘을 Sig라고 할 때 메세지 m에 대한 서명 s는 s = Sigsk(m)의 수식으로 생성된다.
- 이렇게 만들어진 서명을 메세지와 함께 보내면 수신자는 서명자의 검증키를 이용해 Verpk(m,s)값을 계삲여 이를 검증한다.
- 서명자의 개인키로 서명했을 때만 검증을 통과할 수 있으므로 서명이 올바르다면 메세지는 서명자로부터 왔음이 증명된다. 따라서, 전자 서명을 사용하면 메세지의 무결성을 증명할 수 있고, 서명자는 자신이 메세지를 보냈음을 부인할 수 없다.
-해시 함수를 이용한 전자 서명
- 전자 서명은 앞서 배운 공개키 암호를 사용하기 때문에 서명하는 메세지의 크기가 N(modulus)보다 작아야 한다.
- 그래서 만약 메세지의 크기가 N보다 크다면 이를 나누어 서명해야 한다. 이러한 불편함을 해소하고, 데이터의 크기와 상관없이 한 번에 서명하기 위해 일반적으로 해시 함수를 같이 사용한다.
- 전자 서명에서 해시 함수를 이용할 경우 효율성뿐만 아니라 안전성 향상에도 도움이 된다.
2. RSA 전자 서명
- RSA 전자 서명은 RSA 공개키 암호를 사용하여 서명과 검증이 이루어진다.
- RSA 공개키 암호에서의 공개키는 검증키로 사용되고 개인키는 서명키로 사용된다.
- RSA 공개키에서 나왔던 똑같은 키 생성 방법을 통해 나온 공개키 (n,e)를 검증키로, 개인키 d를 서명키로 사용한다.
-서명 생성
: 서명키 d로 메세지 m에 대한 서명 s를 s ≡ m^d(mod n)을 통해 생성한다.
-서명 검증
- 서명 값 s와 메세지 값 m에 대한 검증을 검증키 (n,e)를 통해 수행한다.
- m′ ≡ s^e(mod n)을 계산하고 m′과 메세지 m이 같은 값인지 확인한다. 같은 값이라면 s는 유효한 서명이고, 그렇지 않으면 유효한 서명이 아니다.
-RSA 전자 서명 공격
- 공격자가 검증키 (n,e)를 알면, 유효한 메세지와 서명 쌍 (m,s)를 생성할 수 있다.
- 공격자가 두 개의 유효한 메세지와 이에 대응되는 서명 쌍 (m1, s1), (m2, s2)를 알고 있다면, 다른 유효한 평문과 서명의 쌍 (m1m2, s1s2)를 생성할 수 있다.
-해시를 이용한 RSA 전자 서명
- 해시를 이용하면 공격으로부터 안전한 전자 서명을 설계할 수 있다.
- 해시를 이용한 RSA 전자 서명에 공격들을 수행하려면, h(m) = s^e(mod n) 또는 h(m) = h(m1)h(m2)을 만족하는 m을 구할 수 있어야 하는데, 이는 해시 함수의 역상 저항성(Preimage Resistance)으로 인해 매우 어렵다.
3. EIGamal 전자 서명
- 1984년 Taher EIGamal에 의해서 발표된 EIGamal 전자 서명은 이산 대수 문제의 어려움에 기반하여 설계되었다.
- EIGamal 전자 서명을 모태로 하여 DSA 전자 서명 등 다양한 전자 서명이 설계되었다.
- EIGamal 전자 서명 과정에서 해시를 사용한다.
-EIGamal 키 생성
- 큰 소수 p와 키를 만드는 생성원g를 선택한다.그 뒤, p - 1 보다 작고 1보다 큰 정수 x를 임의로 선택한다. y = g^x(mod p)를 계산하여 (y, g, p)를 검증키로, x를 서명키로 사용한다.
-서명 생성
- 메세지 m과 서명키 x에 대한 서명 값 s를 아래의 과정에 따라 생성한다.
-서명 검증
- 서명 s = , 메시지 , 검증키 (y,g,p)가 있을 때, 서명 s에 대한 검증은 g^m와 y^(γ) γ^(δ)의 비교로 이뤄진다.
- 만약 이 둘이 같은 값이라면 s는 유효한 서명이다.
4. EIGamal 전자 서명 공격
- EIGamal 전자 서명은 서명 생성 과정에서 매번 서명을 할 때마다 새로운 난수 k를 선택하여 사용하기 때문에 동일한 메세지에 대해서도 서명 값이 항상 변한다.
- 이러한 특성을 비결정적(Nondeterministic) 성질아라고 하며, 이로 인해 RSA 서명 기법에 존재하던 문제점이 EIGamal에서는 대부분 해결된다.
- 그러나 EIGamal은 난수 k를 매번 같은 값으로 고정하면 서명키 x가 노출될 수 있다.
- 난수 k가 노출되면 공격자는 서명 값과 k를 통해 서명키 x를 구할 수 있다.
- 서명키 x를 알면 원하는 메세지의 서명값 또한 구할 수 있기 때문에 매우 위험한 취약점임을 알 수 있다.
- 따라서 k 같은 고정된 값이 아닌 적절한 난수값으로 정해야 한다.
5. DSA 전자 서명
- DSA 전자 서명은 1991년 NIST에 의해서 제안되었으며 1994년 12월에 미국의 전자 서명 기법 표준으로 제정되었다.
- DSA 전자 서명은 다른 서명에 비해서 훨씬 짧은 서명 길이를 가지는 장점이 있다. 또한, 성능 면에서도 RSA 전자 서명보다 빠르다.
-DSA 키 생성
~ q - 1 범위의 난수 를 임의로 선택한 뒤, 서명 값 s 을 계산한다.
-서명 검증
-> 따라서 올바른 서명 s에 대해, 계산한 r'이 r와 동일하다면, 그 서명은 유효하다.
3. 마치며
- 전자 서명을 사용하는 사례로 공동인증서(구 공인인증서)가 있다.
- 공동인증서에는 발급 대상의 신원 정보와 함께 공인 인증 기관이 작성한 전자 서명이 포함되어 있다.
- 사용자가 인증을 요구하는 서비스에 공동 인증서를 제출하면, 서버는 인증서의 서명을 검증하여 인증서에 적힌 개인의 신원을 신뢰한다.
- 해당 신원은 공인 인증 기관이 보증하는 것이므로, 보안에 민감한 금융 서비스나 전자 정부 서비스는 공동 인증서를 이용하여 개인을 식별한다
- 또한, HTTPS 프로토콜은 웹 서버가 인증서를 게재하게 하여 사용자가 웹 서버를 검증할 수 있게 하고 있다.
- 몇몇 브라우저들은 여기서 더 나아가 웹 인증서가 조작되거나 만료된 것은 아닌지 사용자에게 알려주어 위험한 웹사이트임을 인지할 수 있게도 한다.
