전자서명 기법 정리

* 참고

만약 전자서명의 대략적인 생성방법 정도만 알고싶으시면

https://gjwjdgnsrnlg.tistory.com/47?category=910140 

메세지 인증(MAC)과 해시 함수

위 글을의 밑부분을 읽어보시는게 좋습니다.

이 글은 전자서명이 생성되는 기법에 대해 원리(알고리즘)를 적어둔 글입니다.

이산수학에 대한 개념이 없으면 이해하시기가 힘들수 있습니다.

따라서 이에 대한 지식이 없으신 분은 간단히 시나리오 부분만 읽어보세요 

 

 

1. EIGamal 전자서명

2. Schnorr 전자서명 

3. DCDSA 전자서명 

 

EIGamal 매커니즘을 기반한 전자서명 방법입니다. 

기본 세팅은 아래와 같습니다.

1.q는 prime일 때 가정하고 사용합니다.

2. 알파는 primitive root of q  = 즉 알파를 mod q에서 generate 했을 때(재곱연산) 모든 나머지(1~q-1)를 만들어 낸다는 것

3. 알파의 m승이 modq 공간에서 1이된다. => m이 q-1이라고 보면 됨, 오일러 정리이다.

 

EIgamal에서는 메시지 전체에 대한 서명이 아니라 메시지의 해시값에 대한 서명을 진행합니다.

이전 글에서 본 것과 동일함 

시나리오(위의 글을 보면서 따라 보세요)

엘리스는 랜덤 하게 개인키 Xa(in mod q)를 생성하고 공개키 Ya를 Xa를 써서 만들어 냅니다. 

그리고 q, 알파, Ya를 공개합니다. 

 

메시지 M에 대해서 서명하기 위해 유저 A는 일단 해시를 취합니다. 

그리고 k라는 또 다른 랜덤 값을 생성합니다. 

근데 이 k는 q-1과 서로소인 관계여야 합니다.

왜냐하면 modq-1에서 k를 쓰는데 0이 되지 않기 위함입니다.

 

그리고 S1을 계산합니다. 다 알고 있는 숫자들이죠 

그리고 mod q-1 공간에서의 k의 inverse를 구합니다.

그리고 이 inverse를 통해 s2를 구합니다. 

이제 서명 s1, s2가 만들어졌습니다.

이것을 수신자에게 보냅니다.

 

수신자는 V1, V2의 식에 s1, s2를 적용해 이 두 개가 같으면 서명이 검증된 것입니다. 

이게 같으면 왜 유효한가?

일단 같다고 가정하고 봅시다.

가정하고 6번째 줄을 봅시다.  

우변의 a의 XaS1 이의 역원이 곱해져서 왼쪽에 붙었죠 

그럼 8번째 줄이 나옵니다. 그다음에 s2를 원래식으로 집어넣으니 K와 K의 inverse가 날아가서 같은 식이 나옵니다.

 

예제를 봅시다.

Q = 19일 때 primitive root 존재 

나는 10을 쓰겠다 

랜덤 한 xa값을 골랐다 =. 16

그리고 공개키를 생성함 - 공개 값 = {19,10,4} 

그리고 14라는 메세지에 대해sign 하고함께 전송할것이다

 

이를 위해 message당 랜덤값 5를 생성함 

s1과  k의 inverse를 구함 

그리고 이를 통해 s2를 생성함 

 

그리고 message와 

수신자는v1, v2를구해서 같음을 검증함

 

이번엔 시노아 디지털 서명입니다. 

이것도 동일하게 discrete lograrithms문제 기반입니다.

이것은 비밀키로 공개키를 어떻게 만드는가만드는가? 

이전과 다른 몇 가지특성이 숨어 있습니다.

그것은 서명 생성때 가장 오래 걸리는걸리는 연산에는 메세지와 관계없이 연산이 진행되어 미리 계산할수가 있어서 빠른 서명이 생성가능 합니다.

즉 큰 값 p에 대해서 하지 않고 p의 prime factor인 q를 활용, 서명 값공간 상에 있어서 서명값이 짧습니다

 

우리가 p공간 상에서 논의를 하고 p-1에는 prime factor를 = q

즉 p-1은 q공간에서 0이 된다 

그래서 시노아 시그니처는 기본 메시지 공간은 p공간인데 시그니처 공간은 q공간상에서 이루어질것 

그래서 p는1024 비트라하면 q는 160비트 공간을 가짐 

 

시나리오

Prime number인 p를 선택했다. 

p-1계 산 가능하고 prime factor q를 찾는다 

그리고 a의 q승이 1이 되는 a를 찾는다.

a, p, q가 public parameter가 됨

 

그리고 q공간에서 랜덤한 s값을 고른다 이건 private key가 됨 

그리고 s를 사용해서 v를 구한다.= public key

 

이제 서명을 생성해야함 

랜덤 한값을 구함= 메세지에 대한 랜덤값

r을 사용해서 x를 구한다. 메시지랑 단계 = preprocessig stage 

미리 해놓을수 있는 단계 

 

그리고 message가 도착하면 메세지와 x를 concatenate 하고 구함 = e

 

그리고 r, s(private key) e를 사용해서 서명 (e, y)가 됨  -mod q공간 

 

수신자는 x’을 받은 서명값과 공개키를 통해서 구한다. 

그리고 메세지에 x’을 concatenate 해서 e를 구한후 같은지 판단함 

a의 y승 * v의 e승은 a의 y-se승까지 됨

y-se는 r이다. 그리고 a의 r은 x였다 

결국 x’은 x가 됨 

 

이것은 타원곡선 기반입니다. 특징을 간단히 살펴보자면 아래와 같습니다.

curve정의, basepoint 정의, global parameter 가진다

Public private 생성 

적절하게 random 수 만든다

해시함수 사용해서 메세지에 대한 해시값에 서명을 함 

r, s가. 

적절한 연산을 통해 v=r로 검증함 - 앞과 동일

참고로 ECC원리를 모르면 좀 힘들 수도 있을 것 같네요. 

일단 해봅니다. 

- 기본 구조 

q는 prime

a, b는 curve의 parameter, 표준에서 정의

g는 이 curver의 basepoint 

N은 basepoint g에 대해서 n번만큼의 scalar를 하면 항등언 0가 나오게됨

 

서명자는 키 pair를 생성해야 한다.

‎랜덤 수 d를 생성 = private

‎q는 dg를 하는데 이때 q가 public key이다. 

시나리오

서명 생성방법

랜덤 한값 k를 선택한다.= 메세지당 랜덤값

kG로 p라는 point를 계산해낸다. 이때 x값이 r이 됨

k의 inverse는 t이다. 

메시지에대한 해시값을 구한다. 

구한 값들을 통해서 s, 서명값을 구한다.만약 s=0이라면 첨부터 다시함 

 

수신 측에서는과 s를 검증할거임 일단 유효한 범위인지 체크함 

해시함수를 사용해서 똑같이 e를 구함 

s의 inverse인 w를 구한다 

그리고 u1과 u2를 구함 이를 통해 x1, x2를 

이게 왜 같아지는지에 대한 설명입니다. 

이는 위 사진에서의 첫 식에 대해서 s의 역원이 w라고 앞서 정의한 것을 통해 

Now consider that까지... 식이 나오게 되죠

저기서 G로 묶이게 되는데 이때 (u1+u2d)가 K가 되는 ECC에서의 원리를 통해 Accept 된다..라고 이해하시면 될 것 같습니다

후에 타원 곡선에 대해 정리할 수 있으면 하도록 하겠습니다.