[Cryptography] stage6_전자서명

전자 서명 알고리즘은 공개키 알고리즘에서의 개인키로 서명을 생성하고, 공개키로 그 서명에 대한 검증을 진행한다. 여기서 서명을 생성하는 개인키를 서명키(Signing Key), 검증에 사용되는 공개키를 검증키(Verification Key)라고 한다.

 

전자 서명의 목적은 메시지의 무결성과 부인 방지에 있다. 

 

 

 

*기본 원리

검증키는 앞서 말했듯 공개된 키이고, 서명키는 서명자만 알고 있어야 하는 비밀키이다. 메시지를 서명키로 암호화하는 과정을 서명 작성(Signing), 서명을 검증키로 복호화하고 받은 메시지와 비교하는 과정을 서명 검증(Verification)이라고 한다. 

 

RSA의 경우 공개키로 암호화를 진행하여 데이터를 송신한 뒤, 수신자가 이를 비밀키로 복호화 하였다면, 서명의 경우 비밀키(서명키)로 암호화하여 생성한 뒤, 공개키(검증키)로 복호화를 하니 정확히 반대의 과정이다.

 

검증키를 pk, 서명키를 sk, 서명 검증 알고리즘을 Ver, 서명 생성 알고리즘을 Sig라고 할 때, 메시지 m에 대한 서명 s는 다음의 수식을 통해 생성된다.

 

s = Sig sk(m)

 

위와 같은 과정을 통해 만들어진 서명을 메시지와 함께 보내면, 수신자는 서명자의 검증키를 이용해 Ver pk(m, s)를 계산해 검증하게 된다. -> 서명자의 개인키로 만들어진 서명만 검증을 통과할 수 있으므로, 서명이 올바르다면 메시지의 송신인이 서명자임이 증명되는 것이다. -> 메시지의 무결성과 동시에 부인 방지가 가능하다.

 

전자 서명은 공개키 암호를 사용하므로 서명하는 메시지의 크기가 N(modulus)보다 작아야 함 -> 메시지의 크기가 N보다 크다면 나누어 서명해야 함 -> 근데 그건 불편하니 해시 함수를 이용

 

해시 함수를 이용한 전자 서명의 경우 해시 함수로 메시지의 해시 값을 생성한 뒤 이 값에 대한 서명을 생성한다. 

 

s = Sig sk​(h(m))

Ver pk​(h(m), s)

 

위의 수식에서 h는 임의의 암호학적 해시 함수이다. 

 

전자 서명에서 해시 함수를 이용할 경우 효율성과 안전성 둘 다에 도움이 된다.

 

 

 

*RSA전자 서명

RSA공개키 암호를 이용해 서명과 검증 과정이 진행된다. RSA공개키 암호에서의 공개키는 검증키로, 개인키는 서명키로 사용되는 것이다. -> 이 친구의 안전성도 RSA암호와 마찬가지로 인수분해 문제의 어려움에 기반한다.

 

RSA에서 설명했던 것과 같은 키 생성 방법을 통해 생성된 공개키 (n, e)를 검증키로, 개인키 d를 서명키로 이용한다.

 

https://orcinus-orca.tistory.com/103

[Cryptography] stage4_공개키암호: RSA

 

 

서명키 d를 이용해 메시지 m에 대한 서명 s를 생성한다.

 

s = m^d (mod n)

 

서명 값 s와 메시지 값 m에 대한 검증의 경우 다음과 같이 진행된다.

 

m` = s^e (mod n)을 계산한 뒤 m`과 m이 같은지 확인 -> 같으면 s는 유효한 서명

 

 

RSA전자 서명 공격: RSA는 여러 공격들에 취약하다.

 

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

m = s^e (mod n) -> 임의의 서명 값 s를 선택하고 메시지 m을 이와 같은 식으로 생성하면 가능하다.

 

-> 공격자가 두 개의 유효한 메시지와 서명 쌍을 알고 있으면, 다른 유효한 메시지-서명 쌍을 생성할 수 있다.

s1 = (m1)^d (mod n), s2 = (m2)^d (mod n)이 성립하면 -> s1*s2 = (m1*m2)^d (mod n)도 성립하기 때문

 

 

해시를 이용한 RSA전자 서명: 

해시를 이용하면 위 공격으로부터 안전한 전자 서명을 설계할 수 있다. 해시를 썼을 때 위 공격을 수행하기 위해서는 h(m) = s^e (mod n) 이나 h(m) = h(m1)h(m2)을 만족할 수 있는 m을 구할 수 있어야 하는데, 이는 해시의 역상 저항성 떄문에 힘들다.

 

 

 

*El Gamal 전자 서명

이 전자 서명은 이산 대수 문제의 어려움에 기반한다. 이 전자 서명을 모태로 DSA(Digital Signature Algorithm)전자 서명과 같은 다양한 전자 서명이 설계되었다.

 

이 전자 서명 역시 해시를 이용한다. 

 

ElGamal 키 생성: 큰 소수 p와 키를 만드는 생성원 g를 선택한 뒤, 1 < x < p-1 를 만족하는 정수 x를 임의로 선택한다. -> y = g^x (mod p)를 계산해 (y, g, p)는 검증키, x는 서명키로 이용한다.

 

서명 생성: p - 1보다 작고, p - 1과 서로소인 정수 k를 임의로 선택한다. 

γ ≡ g^k (modp)

δ ≡ (m−xγ)*k^(−1) (mod p−1)

s = (γ,δ)

위와 같은 식을 통해 서명값을 생성한다. (m은 해시값)

 

서명 검증: 서명 s = (γ,δ), 메시지 m, 검증키(y, g, p)가 있을 때 서명 s에 대한 검증은 g^m (mod p)와 y^γ * γ^δ (mod p)의 비교로 진행된다. (같은 값일 경우 s는 유효한 서명)

 

δ = (m - x*γ)*k^(-1) (mod p - 1)이므로 어떤 n에 대해 δ = (m - x*γ)*k^(-1) n*(p - 1) 이다.

 

y^γ * γ^δ = g^(x*γ) * g^(k*δ) = g^(x*γ + k*δ) = g^(xγ + k((m−xγ)*k^(−1) + n(p−1))) = g^(xγ+(m−xγ)) (∵g^(p−1) ≡ 1 (modp) ) = g^m (mod p)

->  g^m (mod p) = y^γ * γ^δ (mod p) 이면 서명값은 유효하다.

 

 

 

ElGamal 전자 서명 공격:

서명 생성 과정에서 매번 서명을 할 때 마다 새로운 난수 k를 선택해 사용함 -> 동일한 메시지에 대해서도 서명값이 항상 변한다. (비결정적(Nondeterministic) 성질) -> 이때문에 RSA에서 존재하던 문제점들이 대부분 해결되었다.

 

하지만 난수 k를 매번 같은 값으로 고정할 시 서명키 x가 노출될 수 있다.

 

공격자가 메시지 m1, m2에 대해 동일한 수 k를 이용한 서명 s1​ = (γ1​,δ1​), s2 ​= (γ2​,δ2​)를 가지고 있다고 하자. 

 

γ1​ ≡ g^k (mod p)

δ1​ ≡ (m1 ​− xγ1​)*k^(−1) (mod p−1)

γ2​ ≡ g^k (mod p)

δ2​ ≡ (m2​ − xγ2​)*k^(−1) (mod p−1)

 

위 4개의 식이 성립하게 된다.

 

δ1​ − δ2 ​≡ (m1 ​− xγ1​)*k^(−1) − (m2 ​− xγ2​)*k^(−1)

≡ (m1​ − xγ1 ​− m2 ​+ xγ2​)*k^(−1)

≡ (m1​ − m2​)*k^(−1) (mod p−1) (∵ γ1 ​= γ2​)

 

-> 여기서 δ1​ − δ2가 0이 아니라면 공격자는 k를 계산할 수 있다.

 

k ≡ (m1​ − m2​) (δ1​ − δ2​)^(−1) (mod p−1)

 

난수 k가 노출되면 -> 공격자는 서명값과 k를 통해 서명키 x를 구할 수 있게 된다.

 

x ≡ (m1 ​− δ1​k)*γ1^(−1)​ (mod p−1)

 

서명키 x를 알게 될 경우 원하는 메시지의 서명값을 구할 수 있기 때문에 매우 위험한 취약점이다. -> k는 고정된 값이어서는 안되며, 적절한 난수로 선택되어야 한다.

 

 

 

*DSA전자 서명

이 서명은 다른 서명에 비해 길이가 훨씬 짧다. 서명에 사용하는 소수 p가 1024비트라면, 엘가말 서명은 2048비트 크기의 서명을 생성하는데, DSA는 320비트의 서명을 생성한다. (성능 면에서도 RSA 서명보다 빠르다.)

 

DSA키 생성: 큰 소수 p를 선택하고, p - 1의 약수이면서 소수인 q를 선택한다. 1 < h < p-1 을 만족하는 정수 h를 선택하고, 생성원 g = h^((p - 1)/q) (mod p)를 계산한다. (g값이 1이 나오면 h를 다시 선택해 계산해야 한다.)

 

1 <= x <= p - 1을 만족하는 큰 정수 x를 임의로 선택한 뒤 y = g^x (mod p)를 계산해 (y, g, p, q)를 검증키로, x를 서명키로 이용한다. (그리고 해시를 이용하기 때문에 안전한 해시 함수 h도 선택한다.)

 

 

서명 생성: 1 <= k <= q - 1 을 만족하는 난수 k를 임의로 선택한 뒤, 다음과 같은 과정으로 서명값 s를 계산한다.

 

γ ≡ (g^k (mod p)) (mod q)

δ ≡ (h(m) + xγ)*k^(−1) (mod q)

s = (γ, δ)

 

 

서명 검증: 

(y, g, p, q)를 검증키로 이용한다.

 

e1 ​≡ h(m)*δ^(−1) (mod q)

e2 ​≡ γ*δ^(−1) (mod q)

위와 같은 과정으로 e1과 e2를 계산한 뒤.

 

γ′ ≡ (g^(e1) * ​y^(e2)​ (mod p)) (mod q) 의 값이 γ와 같다면 s는 유효한 서명이다. 

 

 

증명: 

w ≡ δ^(−1) (mod q)인 w 에 대해 δ ≡ (h(m) + xγ)*k^(−1) (mod q)이므로 k ≡ h(m)*δ^(−1) + xγδ^(−1) ≡ h(m)*w + xγw (mod q)이고, k = h(m)*w + xγw + nq를 만족하는 정수 n이 존재하게 된다. g ≡ h^((p−1)/q) (mod p)에서 페르마 정리에 의해 g^q ≡ h^(p−1) ≡ 1 (mod p) 이므로

g^k

≡ g^(h(m)*w + xγw + nq)

≡ g^(h(m)*w+xγw)

≡ g^(h(m)*w) * g^(xγw)

≡ g^(h(m)*w) * y^(γw)

≡ g^(e1) * ​y^(e2) ​(mod p)

 

위와 같이 되고, γ ≡ (g^k (mod p)) (mod q) ≡ (g^(e1) * ​y^(e2) ​(mod p))(mod q) 이렇게 되므로 γ′가 γ와 같다면 s는 유효한 서명이다.