8주차 암호학 정리

서명

• = 행위자가 자신의 신원을 표기하기 위해 사용하는 것
• = 메세지가 서명자에게서 왔음을 증명하고, 문서작성으로 인해 발생하는 모든 문제에 대한 책임이 서명자에게 있음을 명시하는 것

 

전자 서명(Digital Signature)

= 서명의 특징을 암호학적으로 구현한 것

• 공개키 암호가 만들어지며 함께 만들어짐
• 공개키 알고리즘에서의 개인키로 서명을 생성하고, 공개키로 그 서명에 대한 검증을 진행함
• 서명키(Signing Key) = 서명을 생성하는 개인키
• 검증키(Verification Key) = 검증에 사용되는 공개키

 

 

 

1. 서명과 검증

• 서명 작성(Signing) = 메시지를 서명키로 암호화하는 과정
• 서명 검증(Verification) = 서명을 검증키로 복호화하고 받은 메시지와 비교하는 과정
• 공개키를 먼저 사용해 암호화하고 개인키로 복호화하는 RSA와는 정확히 반대 과정
• 서명은 서명 생성 알고리즘(함수)에 서명키를 사용하여 메시지를 인수 삼아 암호화한 함숫값
• 검증은 서명 검증 알고리즘에 검증키를 이용해 메시지와 서명을 인수 삼아 복호화, 함숫값을 도출해내는 과정
• 서명자의 개인키로 서명했을 때만 검증을 통과할 수 있음 -> 서명이 올바르다면 메시지는 서명자로부터 왔음이 증명됨
• 서명을 사용하면 메시지의 무결성을 증명할 수 있고 / 서명자가 메시지를 보냈다는 사실이 부인 불가해짐

 

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

• 전자서명은 공개키 암호를 사용하므로 -> 서명하는 메시지의 크기가 N(modulus)보다 작아야 함
• = 메시지의 크기가 N보다 크다면 이를 나누어 서명할 필요가 있음
• => 데이터 크기와 상관없이 한 번에 서명하기 위해 -> 일반적으로 해시 함수 사용
• 해시 함수를 이용할 경우 암호화 전 메시지 자체를 해시 함수에 넣어 해시값을 생성하고,
• 서명은 이 해시값에 대해 생성하게 됨 (서명 시와 검증 시 모두 해시값이 평문의 메시지를 대체한다)
• 효율성뿐만 아니라 안전성 향상에도 도움이 되는 방법임.

 

3-1. RSA 전자 서명

• RSA 공개키 암호를 사용하여 서명과 검증을 수행하는 방법
• 공개키->검증키, 개인키->서명키
• 안전성은 RSA 공개키 암호와 마찬가지로 인수분해 문제의 어려움에 기반
• RSA에서와 동일하게 공개키 (n, e)를 검증키로, 개인키 d를 서명키로 사용
• 생성: s ≡ m^d (mod n)
• 검증: m' ≡ s^e (mod n) -> 식으로 도출한 m'과 메시지 m이 같은 값인지 확인. 일치해야만 s가 유효한 서명이 됨

 

 

3-2. RSA 전자 서명의 취약점

• 공격자가 검증키 (n, e)를 알면 유효한 메시지와 서명 쌍 (m, s)를 생성할 수 있음
• 공격자가 두 개의 유효한 메시지와 이에 대응되는 서명 쌍 (m1, s1), (m2, s2)를 알고 있다면 다른 유효한 평문과 서명의 쌍 (m1m2, s1s2)을 생성할 수 있음
• 해시 함수를 이용하면 역상 저항성으로 인해 위 취약점이 보완됨

 

 

4. ElGamal 전자 서명

• 이산 대수 문제의 어려움에 기반하여 설계된 전자서명
• 해시를 사용함

 

4-1. 키 생성

1. 큰 소수 p와 키 생성원 g를 선택
2. 1과 p-1 사이인 정수 x를 임의 선택
3. y = g^x (mod p)를 계산하여 (y, g, p)를 검증키로, x를 서명키로 사용

 

4-2. 서명 생성

• p-1보다 작고 서로소인 정수 k를 임의로 선택
• 다음 계산으로 서명 값 생성
• γ ≡ gk(modp)
• δ ≡ (m−xγ)k^−1 (modp−1)
• s = (γ,δ)

 

 

4-3. 서명 검증

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

 

4-4. ElGamal 전자 서명 공격

• ElGamal 전자서명은 매번 서명을 생성할 때마다 난수 k를 매번 새로 선택하므로
• 동일 메시지에 대해서도 서명 값이 항상 가변적임 (비결정적, Nondeterministic 성질)
• -> RSA 서명 기법에서의 문제점은 대부분 해결할 수 있음
• / 난 수 k를 매번 같은 값으로 고정하면 서명키 x가 노출될 수 있음
• 서명키 x를 알면 원하는 메시지의 서명값 또한 구할 수 있기 때문에 매우 위험한 취약점임.
• 반드시 고정이 아닌 난수값으로 할 것

 

 

5. DSA 전자 서명

• 미국의 전자 서명 표준 기법
• 타 서명에 비해 훨씬 짧은 서명길이를 가지며, RSA 전자서명보다 빠름

 

5-1. 키 생성

1. 큰 소수 p와 p-1의 약수이며 소수인 q 선택
2. 1과 p-1 사이의 정수인 h 선택
3. 생성원 g ≡ h^{(p−1)/q} (modp) 계산 (계산한 g가 1이 되면 h를 다시 선택하여 1이 아닌 g 구하기)
4. 1과 q-1 사이의 큰 정수 x 임의선택
5. y = g^x (mod p) 계산 -> (y, g, p, q)를 검증키로, x를 서명키로 사용
6. 안전한 해시 함수 h 선택