Fiat-Shamir Protocol의 설명, 자바에서 큰 소수 구하기

[그림 1, 2] Fiat-Shamir Protocol의 기본적 이론

Fiat-Shamir Protocol은 Zero-Knowledge Authentication(영지식 인증)을 사용하며, 3rd Party(공인된 3자), Claimant(주장자), Verifier(검증자)로 구성된다. Verifier는 Claimant가 가진 비밀을 모르지만 Claimant가 비밀을 가지고 있는지 없는지(Y, N)에 대한 판별만 할 뿐이다.

1. 3rd Party는 두 개의 큰 소수를 정한다.(p, q, 비공개)
2. 3rd Party는 두 약수를 곱한 후 이를 공개한다(n=p*q)
3. Claimant는 1과 n-1사이의 정수 s를 선택한다
4. Claimant는 v = s^2 % n을 구하고 s는 비공개, v는 공개.

이 과정에서 p와 q는 매우 큰 소수이며 위의 과정을 미리 수행해 놓은 상태에서 아래 과정을 반복함으로서, 공격자가 암호를 추측할 수 있는 확률을 1/n^2 만큼 줄인다.  

1. Claimant는 0과 n-1사이의 정수 r을 선택한다
2. Claimant는 x = r^2 % n 을 구한다.
3. Claimant는 x를 Verifier에게 보낸다
4. Verifier는 시도(Challenge) c를 보낸다. C는 0 또는 1
5. Claimant는 응답(Response) y=rs^c % n을 계산하고 y를  보냄으로서 자신이 S를 알고 있다는 사실을 입증한다.
6. Verifier는 y^2 % n과 xv^c % n을 계산한 후 비교하여 Claimant를 검증.

위 두 과정을 그림으로 나타낸다면 다음과 같다.

[그림 3, 4] 다이어그램으로 표현한 Fiat-Shamir Protocol과 그 예


그러면 자바에서는 큰 랜덤한 소수를 어떻게 구할 수 있을까? 처음에는 따로 소수를 구하는 부분을 만들었지만 나중에보니 BigInteger 클래스에 다음과 같은 메소드가 있었다. 그야말로 비트길이와 랜덤시드만 주어지면 소수를 구하는 매우 편리한 메소드이다.
public static BigInteger probablePrime(int bitLength, Random rnd)


============================
이 이론을 사용하는 자바 프로그램을 만들어달라는 요청에 공부도 할겸 정리해봤다. 처음 책을 봤을때 편집이 약간 애매하게 되어있어서 이해하기 힘들었는데(계속 오타인줄 알고 오타를 나름 정정해서 이해하려 했지만 나중에 보니 그냥 위치상의 혼돈이었음..) 정리해보면 전혀 어려울게 없는 이론이다. 프로그램 만드는것도 위의 probablePrime만 알게 된다면 그냥 pow,mod의 반복이므로 굳이 올릴거 있나 할정도다. 영지식 인증을 사용한 예로 어떤것이 있을까? 물론 개체 인증이 기본적인 목표인데 좀 더 생활에 가까이 생각해보자면 문화상품권 인증?? 정도가 되지 않을까 싶다. 물론 상품권같은 경우에는 1:! 인증이겠지만(전에 대량으로 상품권을 구매하려니까 직원이 인증번호를 컴퓨터에 일일히 기입하느라 힘들어하더만..) 사용자가 인증번호를 추측 불가능하게 하고 자체적인 진위파악??을 한다는 측면에서는 이런것이 도움이 될것같다. 전에 상품권 코드 생성기를 만드려고 관련 이론을 정리하다 보니 공부하고 적용되는 이론들이 참많아서 수학을 좋아하지 않는 나로서는 어려운 시간이었다??