암호학 8주차 - 전자서명

0. 서론

서명의 목적: 메세지가 서명자에게서 왔음을 증명하고 문서 작성으로 인해 발생하는 모든 문제에 대한 책임이 서명자에게 있음을 명시

--> 전자 서명(Digital Signature) 은 서명의 특징을 암호화한 것

​

---

1. 전자서명

- 공개키 암호와 함께 만들어짐

- Diffie Hellman 이 전자 서명의 개념 소개, 1978년 RSA 암호 알고리즘이 만들어지면서 전자 서명 사용 시작

- 전자 서명 알고리즘: 공개키 알고리즘에서의 개인키로 서명 생성 -> 공개키로 그 서명에 대한 검증 진행

서명키( Signing Key): 서명을 생성하는 개인키

검증키( Verification Key): 검증에 사용되는 공개키

​

- 사용: 메세지의 무결성과 부인방지

​

---

2. 전자서명의 기본 원리

• 서명과 검증

- 검증키: 공개된 키, 서명키: 서명자 본인만 알고 있어야 하는 비밀키

- 서명 작성(Signing): 메시지를 서명키로 암호화하는 과정

- 서명 검증(Verification): 서명을 검증키로 복호화하고 받은 메시지와 비교하는 과정

 

• 전자서명의 과정

: RSA에서는 수신인이 공개키로 데이터를 암호화해서 전송하고 수신인이 이를 개인키로 복호화했는데.. !

이 과정을 반대로 하는 것이다.

1. 검증키를 pk, 서명키를 sk, 서명 검증 알고리즘을 Ver, 서명 생성 알고리즘을 Sig라고 할 때

메시지 m에 대한 서명 s는 아래의 수식으로 생성된다.

s = Sig_sk(m)

2. 서명 s를 메시지와 함께 보내면 수신자는 서명자의 검증키를 이용해 Verpk(m,s) 값을 계산하여 검증한다.

 

​

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

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

​

​

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

- 서명하는 메시지의 크기가 N(modulus)보다 작아야 한다.

- 데이터의 크기와 상관없이 한 번에 서명하기 위해 해시 함수를 같이 사용한다.

- 해시 함수로 메시지의 해시 값을 생성하고 이 값에 대한 서명을 생성한다. h는 임의의 암호학적 해시 함수이다.

​

s=Sigsk(h(m))

Verpk(h(m),s)

​

- 해시 함수를 이용하면 효율성 + 안전성 향상에 도움이 된다.

​

---

3. RSA 전자 서명

: RSA 공개키 암호를 사용하여 서명과 검증이 이루어진다.

- 공개키는 검증키로 사용되고 개인키는 서명키로 사용된다.

- RSA 전자 서명의 안전성은 인수분해 문제의 어려움에 기반한다.

​

• 서명 생성

서명키 d로 메시지 m에 대한 서명 s에 대해

• 서명 검증

서명 값 s와 메시지 값 m에 대한 검증을 검증키 (n, e)를 통해 수행한다.

m′≡se(modn) 을 계산하고 m'과 메시지 m이 같은 값인지 확인한다. 같은 값이면 s는 유효한 서명이고 그렇지 않으면 유효한 서명이 아니다.

​

​

• RSA 전자 서명 공격

- 취약한 공격

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

선택하고 메시지 m을 생성하면 유효한 메시지와 서명 쌍을 생성할 수 있다.

 

2. 공격자가 두 개의 유효한 메시지와 이에 대응되는 서명 쌍 (m1, s1), (m2, s2)를 알고 있다면 다른 유효한

평문과 서명의 쌍 (m1m2, s1s2)을 생성할 수 있다.

s1≡m1d(modn) , s2≡m2d(modn)이 성립하면 합동식의 성질에 따라 다음 식이 성립한다.

​

​

• 해시를 이용한 RSA 전자 서명 공격

해시를 이용하면 안전한 전자 서명을 설계할 수 있다. 위의 두 식을 만족하는 m을 구할 수 있어야 한다.

이는 해시 함수의 역상 저항성 (Preimage Resistance)으로 인해 매우 어렵다.

​

---

4. EIGamal 전자 서명

: 1984년 Taher Elgamal에 의해 발표되었고 이산 대수 문제의 어려움에 기반하여 설계되었다. EIGamal 전자 서명을 모태로 하여 DSA 전자 서명 등이 설계되어있다.

- 해시를 사용한다.

​

해시값을 m이라고 할 때

​

• EIGamal 키 생성

1. 큰 소수 p와 키를 만드는 생성원 g를 선택한다.

2. p-1보다 작고 1보다 큰 정수 x를 임의로 선택한다.

3.

을 계산하여 (y, g, p)를 검증키로, x를 서명키로 사용한다.

​

​

​

​

• 서명 생성

메시지 m과 서명키 x에 대한 서명값 s를 생성한다.

1. p-1보다 작고 이와 서로소인 정수 k를 임의로 선택한다.

2. 계산하여 서명 값을 생성한다.

계산식:

​

​

​

• 서명 검증

서명 s = (γ, δ), 메시지 m, 검증키 (y, g, p)가 있을 때 서명 s에 대한 검증은 g^m (mod p)와 y^γ g^δ (mod p)의 비교로 이루어진다. 둘이 같은 값이면 s는 유효한 서명이다.

​

증명)

이므로 어떤 n에 대해

이 성립한다.

다시 식을 정리하면

​

따라서 g^m(mod p)와 y^γ g^δ 가 같다면 서명값 s는 올바른 값이다.

​

​

​

​

​

• EIGamal 전자서명 공격

비결정적 (Nondeterministic) 성질: 서명 생성 과정에서 매번 서명을 할 때마다 새로운 난수 k를 선택해 사용하므로 동일한 메시지라도 서명값이 항상 변한다.

- RSA 서명 기법에 존재하던 문제점이 비결정적 성질을 가진 EIGamal에서는 대부분 해결 가능하다.

- 난수 k를 매번 같은 값으로 고정하면 서명키 x가 노출될 수 있다고 알려져 있다.

​

- 공격방법

가정: 공격자는 두 개의 메시지 m1, m2에 대해 같은 k를 사용한 서명 s1= (γ1, δ1), s2=(γ2, δ2)를 가지고 있다.

서명 생성 과정에서 다음 식이 성립한다.

​

이를 통해 다음 식을 얻을 수 있다.

​

이 때 δ1-δ2의 값이 0이 아니라면 공격자는 k를 계산할 수 있다.

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

​

서명키 x를 알면 원하는 메시지의 서명값도 구할 수 있게 된다.

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

---

5. DSA 전자 서명

: 1991년 NIST에 의해 제안되었고 1994년 12월에 미국의 전자 서명 기법 표준으로 제정되었다.

- 다른 서명에 비해 훨씬 짧은 서명 길이를 가진다.

ex. 사용하는 소수 p가 1024비트라면 EIGamal 서명은 2048비트의 크기의 서명을 생성하고

DSA는 320비트의 서명을 생성한다. 성능 면에서는 RSA 전자 서명보다 빠르다.

​

​

• DSA 키 생성

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

2. p-1보다 작고 1보다 큰 정수 h를 선택하고 생성원 g를 계산한다.

 

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

3. 1부터 q-1 범위의 큰 정수 x를 임의로 선택한다.

4. y=g^x (mod p)을 계산하여 (y, g, p, q)를 검증키로, x를 서명키로 사용한다.

5. 안전한 해시 함수 h를 선택한다.

​

​

​

• 서명 생성

1부터 q-1 범위의 난수 k를 임의로 선택한 후 서명 값 s = ( γ, δ)을 계산한다.

서명 값 s를 생성하는 수식

• 서명 검증

서명값 s=( γ, δ)와 메시지 m에 대한 검증을 검증키 (y, g, p, q)를 통해 수행한다.

1. e1, e2를 계산한다.

2. γ'을 계산하고 서명값의 γ값과 비교한다.

γ'계산식

두 값이 같으면 s는 유효한 서명이다.

​

증명)

 

인 w를 정의하면

이므로

가 성립한다. 그리고,

​

를 만족하는 정수 n이 존재한다. 여기에서 g≡h^((p-1)/q) (modp)이므로 페르마의 소정리에 의해 g^q≡h^(p-1)≡1 (mod p)가 된다. 따라서

최종적으로

​

올바른 서명 s에 대해 계산한 γ'과 γ이 동일하면 서명이 유효한 것이다.

​