// 이산대수를 이용하는 영지식증명 방법 
// 증명자 A는 키쌍 (xa,ya)를 가지고 있음. ya=g^xa mod p 
// 검증자 B(서버)는 증명자 A의 신분을 확인하려고 함 
// 증명자 A(사용자)는 자신의 개인키 xa를 노출시키지 않으면서 자신의 신분을 증명하고자 함  

import java.math.BigInteger;
import java.util.Scanner;
import java.security.*;

public class ZKPSchnorrNI {
	public static void main(String[] args) throws NoSuchAlgorithmException {
		
		Scanner s;
		s = new Scanner(System.in);
		
		// ------------------- 시스템 파라메터 생성 ----------------------
		System.out.println("1. 시스템 파라메터 생성 "); 
		System.out.print("q의 비트수를 입력하세요 (160)>> ");
		int blq = s.nextInt();
		System.out.print("p의 비트수를 입력하세요 (1024)>> ");
		int blp = s.nextInt();
		
		BigInteger one = new BigInteger("1"); 
		BigInteger two = new BigInteger("2"); 
		BigInteger q, qp, p, a, g, xa, ya;
        int certainty = 10; // 소수일 확률을 정한다.
        SecureRandom sr = new SecureRandom(); // 난수를 생성한다.        
		 
        q = new BigInteger(blq, certainty, sr);   // blq 비트의 소수 
        System.out.println("q = "+q); 
        
        // p = 2*q*qp+1 인 소수 p를 선택 
		int i=0;
		qp = new BigInteger(blp-blq, certainty, sr);  // 비트수가 blp-blq인 소수를 난수로 생성  
		do {			
			p = q.multiply(qp).multiply(two).add(one); // p = 2*q*qp+1 를 계산 
			if (p.isProbablePrime(certainty)) break;   // 이렇게 계산된 p가 소수이면 선택  
			qp = qp.nextProbablePrime();               // 아니면 다른 소수를 시도 
			i++;
		} while (true);
		System.out.println("loop = "+i); 
		System.out.println("p = "+p); 
		System.out.println("p의 bit수  = "+p.bitLength()); 
		System.out.println();
		
		// g^q mod p = 1 를 만족하는 생성자 g를  선택 
		i=0;
		a = new BigInteger(blp-1, sr);  // blp 비트의 수를 난수로 생성  
		do {			
			g = a.modPow((p.subtract(one)).divide(q),p); // g = a^((p-1)/q) mod p = a^(2*qp) mod p 를 계산 
			if(g.modPow(q, p).equals(one)) break;  // g^q mod p = 1 이면 g를 생성자로 선택하고 break  
			a = a.add(one);  // 아니면 다른 수를 시도 
			i++;
		} while (true);
		System.out.println("loop = "+i);		
		System.out.println("g = "+g); 
		System.out.println("q|p-1 = "+(p.subtract(one)).mod(q)); // (p-1)은 q로 나누어 떨어지는 수인지 확인   
		System.out.println("g^q mod p = "+g.modPow(q, p));  // 이 값은 1이 되어야 함
		System.out.println();
		
		// ------------------- 증명자의 키쌍 생성 ----------------------
		System.out.println("2. 증명자 A의 키쌍 생성 "); 
		xa = new BigInteger(blq, sr);  // 개인키를 난수로 선택 
		ya = g.modPow(xa, p);          // 공개키 계산 
				
		System.out.println("A의 개인키 : x = "+ xa); 
		System.out.println("A의 공개키 : y = g^x mod p = "+ ya); 
		System.out.println(); 
		
		// ------------------- 영지식 증명 프로토콜 ----------------------
		System.out.println("3. 증명자 A의 영지식 증명 ");
		BigInteger t = new BigInteger(blq, sr);  // Commitment를 위한 난수 선택 
		BigInteger R = g.modPow(t, p);           // Commitment값 R 계산 
		
		MessageDigest md = MessageDigest.getInstance("SHA1"); 
		md.update(ya.byteValue());					   
		md.update(R.byteValue()); 				   
		byte[] digest = md.digest(); 	 				  // H(ya,R) 계산 
		BigInteger u = new BigInteger(1, digest);
		BigInteger w = t.subtract(u.multiply(xa).mod(q)).mod(q);  
		System.out.println("R = "+ R); 
		System.out.println("w = "+ w);
		System.out.println("A ---> B : (R,w)");
		System.out.println(); 
		
		System.out.println("4. 검증자 B의 검증 작업 "); 
		MessageDigest md1 = MessageDigest.getInstance("SHA1"); 
		md1.update(ya.byteValue());					   
		md1.update(R.byteValue()); 				   
		byte[] digest1 = md1.digest(); 						  // H(ya,R) 계산 
		BigInteger u1 = new BigInteger(1, digest1);
		
		BigInteger R1 = g.modPow(w,p).multiply(ya.modPow(u,p)).mod(p); 
		System.out.println("B computes R1 = g^w ya^u mod p = "+ R1); 
		
		if(R1.equals(R))
			System.out.println("Yes: R=R1이므로 증명자 A의 신분이 확인되었습니다."); 
		else 
			System.out.println("No: R!=R1이므로 증명자 A의 신분을 확인할 수 없습니다."); 
	}
}