1. 전자 서명의 정의
- 2개의 디지털 파일이 생성됨
- 문서 : 작성한 메시지
- 서명 : 작성한 메시지(문서) 에 대한 승인
1-1. 종이 서명 vs. 전자 서명
1-1-1. 종이 서명
- 문서에 함께 포함되어있는 서명 : 날인, 도장, 서명 사인, …
- 문서의 서명을 별도로 가지고 있는 파일의 서명과 비교
- 서명 하나로 여러 문서에 승인 가능
- 원본과 복사본의 구분이 가능
1-1-2. 전자 서명
- 문서와 함께 포함되어있지 않는 서명 : 분리되어 있는 파일
- 사전에 정의된 점검 방법으로 문서와 서명을수신
- 하나의 서명은 반드시 하나의 문서에만 승인 가능
- 원본과 복사본의 구분이 불가능
- 문서가 같으면 서명은 항상 동일
1-2. 전자 서명 암호화, 복호화
- 송신자 : 서명 알고리즘을 통해 문서에 서명
- 수신자의 공개 키를 이용해 암호화 → \(E(Msg,\ 공개\,키)\)
- 수신자 : 검증 알고리즘을 통해 문서와 서명을 검증
- 수신자의 개인 키를 이용해 복호화 → \(D(Msg,\ 개인\,키)\)
1-2-1. 왜 공개 키로 암호화?
만약에 송신자의 개인 키로 암호화한다면?
→ 검증 시에 송신자의 공개 키를 이용해서 복호화해야함
→ 송신자 뿐만 아니라 다른 사람들도 복호화해버릴 수 있음
→ 개인 키로는 암호화 불가능
1-3. 다이제스트 서명
- 다이제스트 → 원본 메시지를 해시 함수로 돌린 결과
- 서명을 다이제스트에 하자
1-3-1. 왜 다이제스트에 서명을?
- 길이가 매우 긴 메시지에 바로 서명
- 매우 긴 시간이 소요됨
- 비효율적
- 암호 해싱으로 원본 메시지의 다이제스트 생성 → 다이제스트에 서명
1-3-2. 다이제스트 서명시 서명, 검증 과정
- 송신자는 원본 메시지를 암호 해싱으로 다이제스트 생성
- 다이제스트를 송신자의 개인 키로 서명
- 생성된 서명과 원본 메시지를 전송
- 수신자는 수신한 원본 메시지를 암호 해싱으로 다이제스트 생성
- 수신한 서명을 송신자의 공개 키로 복호화한 다이제스트와 생성한 다이제스트 비교
1-4. 전자 서명 서비스
- 메시지 인증
- 누가 보낸 메시지인지 인증
- 송신자의 공개 키로 검증이 되기 때문에 송신자가 보냈음을 인증
- 메시지 무결성
- 보낸 메시지가 훼손되거나 수정되지 않음을 검증
- 원본 메시지의 서명 ≠ 수정된 메시지의 서명
- 부인 방지
- 보내어진 메시지의 송신자가 자신이 아님을 검증
- 신뢰받는 제 3자를 이용
- 메시지를 송신자의 개인 키로 서명
- 제 3자는 송신자의 공개 키로 검증
- 확인 후 제 3자의 개인 키로 서명
- 수신자는 제 3자의 공개 키로 검증
2. RSA 디지털 서명 구조
- 키 생성
- 이전에 Asymmetric-Key Encipherment 에서 RSA 암호 시스템과 동일
- 공개 키 (e, n), 개인 키 (d)
2-1. RSA 디지털 서명, 검증
이 역시도 RSA 암호 시스템과 같은 구조를 가짐
2-1-1. 서명
$$ \begin{align*} 메시지=M(Message)\\서명=S(Sign) \end{align*} $$
$$ S=M^d\ mod\ n $$
서명(S) 과 메시지(M) 를 송신
2-1-2. 검증
1단계 - 서명을 복호화
$$ M^{'}=S^e\ mod\ n $$
2단계 - 복호화 해서 얻은 메시지(\(M^{'}\)) 와 수신받은 원본 메시지(\(M\)) 비교
$$ \begin{align*} M^{'}\ ==\ M\ \ (검증\ 성공) \\M^{'}\ !=\ M\ \ (검증\ 실패) \end{align*} $$
2-2. RSA 서명으로만은…
2-2-1 전수조사 공격
- (M, S) 를 중간에서 탈취
- \(M^{'}=S^e\ mod\ n\) 인 \(M^{'}\) 를 찾기위해 전수조사
- 현실적으로 불가능에 가까움
2-2-2. 선택 메시지 공격
- 곱셈 성질을 이용한 공격
- (M1, S1), (M2, S2) 를 중간에서 탈취
- \(M=(M_1*M_2)\ mod\ n\) 을 이용
$$ \begin{align*}S&=(S_1*S_2)\ mod\ n\\&=(M_1^d\ mod\ n\ *\ M_2^d\ mod\ n)\ mod\ n\\&=(M_1*M_2)\ mod\ n\\&=M^d\ mod\ n\end{align*} $$
공격자가 자기가 원하는 M 을 보내도록 M1 과 M2 를 유도하여 공격할 수 있음
2-3. 메시지 다이제스트 RSA 서명
- 암호 해싱을 거친 메시지 다이제스트를 RSA 서명
- 선택 메시지 공격을 어렵게 만들기 위함
- \(h(M)=h(M_1)*h(M_2)\) 의 계산이 가능은 함
- 그러나 \(h(M)\) 을 통해서 원본 메시지를 유추하는 것은 사실상 불가능
3. 타원 곡선 디지털 서명 구조 ECDSA
3-1. ECDSA 키 생성 과정
- 타원 곡선, p 값을 선택(p = 매우 큰 소수)
- ECC 에서 타원 곡선을 선택할 때의 그 p 와 동일한 역할
- q : 계산에서 사용할 다른 소수
- d : 개인 키로 쓰일 정수
- e1 : 곡선 상의 한 점
- e2 = d * e1 : 곡선 상의 또 다른 한 점을 계산
- 최종 키
- 공개 키 (p, q, e1, e2)
- 개인 키 (d)
3-2. 서명과 검증 과정
3-2-1. 서명
1단계
임의의 수 r 선택 → \(1<r<q-1\)
2단계
- 곡선 상의 한 점 \(P(x,\ y)=r*e1\)
- e1 → 제시되어있는 곡선 상의 한 점
3단계
- 메시지 M 의 서명 = \((S_1,\ S_2)\)
- \(S_1=P(x)\ \ \ \ \ (mod\ q)\)
- \(S_2=(h(M)+d*S_1)*r^{-1}\ \ \ \ \ (mod\ q)\)
3-2-2. 검증
1단계
- 중간 결과인 A, B 계산
- \(A=h(M)*S_2^{-1}\ \ \ \ \ (mod\ q)\)
- \(B=S_1*S_2^{-1}\ \ \ \ \ (mod\ q)\)
2단계
곡선 상의 한 점 \(T(x,\ y)\) 을 구하여 \(S_1\) 과 비교
→ 서명단계의 \(P(x,\ y)\) 의 x 좌표와 비교하여 검증하는 것
$$ \begin{align*} T(x,\ y)=A*e1+B*e2 \\x\ mod\ q\ ==\ S1\ mod\ q\ 라면\ 검증\ 성공 \end{align*} $$
\(T(x,\ y)=Ae1+Be2\) 증명
- S2 를 통해서 r 을 유추할 수 있음
$$ r = (h(M)+d*S_1)*S_2^{-1}\ \ \ \ \ (mod\ q) $$
- 분배 후 A 와 B 를 대입
$$ \begin{align*} (h(M)+d*S_1)*S_2^{-1}&=\underbrace{(h(M)*S_2^{-1})}_A+(d*\underbrace{S_1*S_2^{-1}}_B)\ \ \ \ \ (mod\ q) \\&=A+d*B\ \ \ \ \ (mod\ q) \end{align*} $$
- 최종적으로 곡선 위의 점인 \(T(x,\ y)\) 을 구하기 위해 \(e1\) 을 곱셈
$$ \begin{align*} (A+d*B)*e1&=A*e1+B\underbrace{d*e1}_{e2} \\&=A*e1+B*e2 \end{align*} $$
수신자의 경우 r 값을 유추할 수는 있지만
최종 검증을 하기 위해서는 r 과 d 를 알지 못해도 됨
