Blind Signature based RSA

 

1. Parameter on RSA

p,q: Large Prime Numbers

n= pq

pi(n)= (p-1)(q-1), the function pi mean euler's one.

e: small odd number

d: multicative inverse of e under modulo pi(n)

private key: d

public key: (e, n)

 

본포스팅에 자세히 적지는 못하지만, e값은 랜덤하게 선택하면 되고, d 값은 e 값에 따라 계산하여 얻는다. 단, ed = 1 mod pi(n)이 성립하도록 구한다. 그러면 mod n 에서 지수가 1이 되기 떄문에 어떤 수라도 ed 승하면 자기 자신이 된다. 이 내용을 정확하게 이해하려면 정수론 지식이 조금 필요하다. 당장은 me을 d 승하여 med가 되면 지수가 1이 되어 m이 튀어 나온다는 점만 이해하고 넘어가자.

 

2. Enc/Dec

For message m, enc(m) = m^d mod n, dec(c) = c^e= (md)e= m^ed= m mod n

물론 Full Spec의 암복호화는 훨씬 엄밀하다. (왠만한 대학원생들도 구현 안해봤을 듯)

 

3. Sign/Verify

For message m, sign(m) = m^d, Verify(s) = s^e= (md)e= m^de= m mod n

마찬가지로 Full Spec은 훨씬 엄밀하다.

 

RSA의 암복호화 스킴과 서명 스킴은 전송자와 수신자가 바뀌어 있을뿐 동일하다.

 

4. Blind Signature

서명이란, 어떤 문서의 출처를 알 수 있게 하는 표식이다. 해당 문서의 내용을 서명자가 보장한다는 의미를 가진다. 전자 서명 또한 그 의미는 동일하다. 임의 크기의 문서(데이터)를 특정 길이의 서명 값으로 압축한다. 또한 압축 작업시 서명자의 개인키를 활용하여 그 출처를 분명하게 한다. 이론상 그 개인키를 알지 못하는 사람(개체)는 동일한 서명 값을 만들 수 없으므로 전자 서명은 해당 문서의 출처를 의미하게 된다. 일반 서명과 전자 서명은 마찬가지로 원본 문서와 함께 동봉된다. 응용에 따라 원본문서를 감추고 싶은 상황은 얼마든지 발생한다. Blind Signature가 이 문제를 해결한다.

 

Blind Signature는 3가지 개체로 구성된다. Sender, Signer, Receiver.

Sender는 메시지의 주인이고, Signer, Receiver는 각각 서명을 하고 검증을 한다. Sender의 메시지가 효력이 발생하려면, 예를 들어 상위 기관의 서명이 필요할 수 있다. 따라서 Sender는 서명을 생성하기 위해 메시지를 Signer에게 보내고, Signer는 해당 메시지에 자신의 서명을 생성하여 돌려준다. 메시지와 서명을 획득한 Sender는 Receiver에게 그것들을 전송하여 메시지의 효력을 발생하게 한다. Receiver는 서명을 검증하여 메시지를 처리 여부를 결정한다.

실생활 예를 들자면, 회사에서 내 휴가원이 통과되려면 팀장의 서명을 받아서 인사팀에 제출해야한다. 이때 나는 Sender가 되고 팀장님이 Signer가 된다. 팀장님의 서명을 받아서 인사팀에 제출하면, 인사팀은 그 서명을 검증하고 휴가원을 처리해줄 것이다.

이때, 휴가원 내용 중에 팀장님이 모르셨으면 하는 내용이 있다면...? 서명은 받아야하겠고.. 내용은 숨기고 싶고... 이때 사용되는 것이 Blind Signature 이다. Signer가 내용을 모르고 서명하게 하는 방법이다. 물론 팀장님이 몰랐으면 하는 내용은 애초에 안쓰면 된다.

 

Sender는 자신만 알고 있는 난수 r을 생성한뒤 Blind Message m'= m*r^emod n을 생성한다. 그리고 m'을 Signer에게 전송한다.

Signer는 m'에 대한 서명을 진행한다. sign(m')= (m')^dmod n = s' mod n, 여기서 s'는 Blinded signature가 된다. 즉, 서명자는 진짜 m을 본적이 없지만 서명은 했다.그리고 해당 서명을 다시 돌려준다.

Sender는 Blinded Signature를 일반 Signature로 바꿀 수 있다.

m' = m* r^e에 대하여 Signer가 d제곱 했으므로, m'^d= m^d * r^ed= md* r 이 된다. r 값을 아는 Sender는 받은 Blinded Signature를 r로 나눠주기면 하면 일반 서명을 획득할 수 있다.

이 일반 서명을 Receiver에게 전송하여 검증하게 하는 등의 응용을 하면된다.