[Cryptography] STAGE 6

STAGE 6

 

전자 서명 (Digital Signature)

- 서명: 행위자가 자신의 신원을 표기하려고 사용

- 전자 서명: 서명을 암호학적으로 구현한 것

- 공개키 암호가 만들어지며 만들어짐

- 1978년 RSA 암호 알고리즘이 만들어지면서 전자 서명이 사용되기 시작

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

 

 

 

전자 서명 알고리즘

- 개인키로 서명을 생성 → 서명키 (Signing Key)

- 공개키로 서명에 대한 검증 진행 → 검증키 (Verification Key)

 

 

 

서명과 검증

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

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

- RSA와 반대 과정으로 이루어짐

 

 

 

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

- 전자 서명에서 해시 함수를 이용하면 효율성, 안전성 향상에 도움이 됨

- 해시 함수로 메시지의 해시 값 생성 → 값에 대한 서명 생성

- 수식으로 나타내면 다음과 같음

 

 

 

RSA 전자 서명

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

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

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

- 인수분해 문제의 어려움에 기반

- 검증키: (n, e) / 서명키: d

 

 

 

서명 생성

- 서명키 d로 메시지 m에 대한 서명 s 생성

 

 

 

서명 검증

- 서명 값 s와 메시지 값 m에 대한 검증 수행

- 이 때, m'과 m이 같다면 s는 유효한 서명

 

 

 

RSA 전자 서명 공격

- 검증키 (n, e)를 알면 유효한 메시지와 서명 쌍 (m, s) 생성 가능

- 두 개의 유효한 메시지와 이에 대응하는 서명 쌍 (m1, s1), (m2, s2)을 알고 있다면 다른 유효한 평문과 서명의 쌍 (m1m2, s1s2) 생성 가능

 

 

 

해시를 이용한 RSA 전자 서명

- 해시를 이용한 RSA 전자 서명에 위의 공격을 수행하려면 아래의 식 만족

또는

- 역상 저항성 (Preimage Resistance)

 

 

 

ElGamal 전자 서명

- 이산 대수 문제의 어려움에 기반

- 이 전자 서명을 모태로 DSA(Digital Signature Algorithm) 전자 서명 등 설계

 

 

 

ElGamal 키 생성

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

- p-1보다 작고 1보다 큰 정수 x 임의 선택

- 검증키: (y, g, p) / 서명키: x

 

 

 

서명 생성

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

- 아래 계산을 통해 서명 값 생성

 

 

 

서명 검증

 

 

 

ElGamal 전자 서명 공격

- 비결정적 성질 (Nondeterministic): 서명을 할 때마다 새로운 난수 k 사용 → 동일한 메시지에서도 서명 값 변함

- 난수 k를 매번 같은 값으로 고정하면 서명키 x 노출 위험성

- 서명키 x를 알면 원하는 메시지의 서명값 노출

- k 값은 고정값 대신 적절한 난수값으로 지정

 

 

 

DSA 전자 서명

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

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

 

 

 

DSA 키 생성

- 큰 소수 p, p-1의 약수이자 소수인 q 선택

- p-1보다 작고 1보다 큰 정수 h 선택

- 생성원 g 계산

- g가 1이 되면 h를 다시 선택하여 1이 아닌 g를 구함

- 1부터 q-1 범위의 큰 정수 x 임의 선택

- y 계산

- 검증키: (y, g, p, q) / 서명키: x

- 안전한 해시 함수 h 선택

 

 

 

서명 생성

- 1부터 q-1 범위의 난수 k를 임의로 선택

- 아래의 수식으로 서명 값 s 계산

 

 

 

서명 검증

- 서명 값 s와 메시지 m에 대한 검증

- e1, e2 계산

- γ' 계산 후 서명값의 γ 값과 비교 (두 값이 같으면 s는 유효한 서명)

- w 정의

- δ 성립

- k 성립

- 아래 식을 만족하는 정수 n 존재

- 올바른 서명 s에 대해 계산한 r'과 r이 동일하면 서명 유효