// Arup Guha
// 11/18/2016
// Illustration of El Gamal Digital Signature

import java.util.*;
import java.math.BigInteger;

public class ElGamalSig {
	
	public static void main(String[] args) {
		
		Random r = new Random();
		Scanner stdin = new Scanner(System.in);
		BigInteger q;
		
		// Get a start spot to pick a prime from the user.
		System.out.println("Enter the approximate value of p you want.");
		String ans = stdin.next();
		q = getNextPrime(ans);
		BigInteger phiQ = q.subtract(BigInteger.ONE);
		
		// Create a "generator". (I am not validating that it's a generator.)
		BigInteger alpha = new BigInteger(q.bitLength()-1, r);		
			
		// Set secret key xA.
		BigInteger xA = new BigInteger(q.bitLength(), r);
		while (xA.compareTo(q) >= 0)
			xA = new BigInteger(q.bitLength(), r);
			
		// Create corresponding public key.
		BigInteger yA = alpha.modPow(xA, q);
		
		// Print all public keys.
		System.out.println("Prime = "+q);
		System.out.println("Alpha = "+alpha);
		System.out.println("PubKey yA = "+yA);
		
		// Generate random value for hash of message
		BigInteger mHash = new BigInteger(q.bitLength(), r);
		while (mHash.compareTo(q) >= 0)
			mHash = new BigInteger(q.bitLength(), r);
			
		// Print out original hash value.
		System.out.println("The correct hash value is "+mHash);
		System.out.println();
		
		// Generate a valid K that shares no factors with q-1.
		BigInteger K = new BigInteger(q.bitLength(), r);
		while (K.compareTo(phiQ) >= 0 || K.gcd(phiQ).compareTo(BigInteger.ONE) > 0)
			K = new BigInteger(q.bitLength(), r);
		
		// First part of signature.	
		BigInteger Sig1 = alpha.modPow(K, q);
		
		// Now calculate K inverse.
		BigInteger Kinv = K.modInverse(phiQ);
		
		// Build S2 - this is inner product.
		BigInteger tmp = xA.multiply(Sig1);
		tmp = tmp.mod(phiQ);
		
		// Make sure we don't have negatives.
		BigInteger Sig2 = mHash.subtract(tmp);
		if (Sig2.compareTo(BigInteger.ZERO) < 0)
			Sig2 = Sig2.add(phiQ);
			
		// Last part of the calculation for Sig2.
		Sig2 = Sig2.multiply(Kinv);
		Sig2 = Sig2.mod(phiQ);
		
		System.out.println("The signature is");
		System.out.println("S1 = "+Sig1);
		System.out.println("S2 = "+Sig2);
		System.out.println();
		
		// User verifies.
		
		// This is the first part of verification.
		BigInteger V1 = alpha.modPow(mHash, q);
		
		// Here we start the second part.
		BigInteger term1 = yA.modPow(Sig1, q);
		BigInteger term2 = Sig1.modPow(Sig2, q);
		System.out.println("To sign we get yA^S1 = "+term1);
		System.out.println("and S1^S2 = "+term2);
		System.out.println();
		
		// Calculate our more complicated verification term.
		BigInteger V2 = term1.multiply(term2).mod(q);
		
		// Print result of verification.
		if (V1.equals(V2)) {
			System.out.println("Message is verified, both terms equal:");
			System.out.println(V1);
		}
		else
			System.out.println("Oops, something went wrong.");
	}
	
	// Returns next prime >= int(ans).
	public static BigInteger getNextPrime(String ans) {
		BigInteger test = new BigInteger(ans);
		while (!test.isProbablePrime(99))
			test = test.add(BigInteger.ONE);
		return test;		
	}		
}