/*

 This unfinished Java code gives you hints on how to implement threshold RSA signatures.

 Shoup's RSA threshold signature scheme protocol I from
 "Practical Threshold Signatures" EUROCRYPT 2000

 For 6.857 Network and Computer Security
 http://web.mit.edu/6.857/www/

 Copyright 2001 Kevin Fu <fubob@mit.edu>
 
 May be freely reproduced for educational or personal use
*/


import java.math.*;
import java.io.*;
import java.util.*;

public class thresholdRsa
{
    
    static BigInteger TWO = new BigInteger("2");
    static Random rnd = new Random(); // insecure randomness, but good for problem set
    
    public static void main(String args[])
    {
	if (args.length != 2) {
	    System.out.println("Usage: java thresholdRsa <threshold> <groups> <...> (and more)");
	    System.exit(1);
	}
	
	int threshold = Integer.parseInt(args[0]);
	
	int groups   = Integer.parseInt(args[1]);
	BigInteger l = new BigInteger (args[1]);
	System.out.println ("l = " + l);
	
	// Pretend this is a hashed message
	BigInteger x = new BigInteger ("nisihaberesquiillisaequeactuipse", 36);
	System.out.println ("Message   = " + x);
	
	/*
	BigInteger mySigShare = genRsaSignatureShare (s[0], n, x, l);
	
	System.out.println ("Share from group " + v[0] + " = " + sigShare[0]);
	System.out.println ("Share from group " + v[1] +" = " + sigShare[1]);
	System.out.println ("Share from group " + v[2] +" = " + sigShare[2]);


	System.out.println ("Shares verification:");


	for (int i=0; i < threshold; i++) {
	    if (verifySignatureShare (s[i],  n, V, c, v[i],  z,  xhat, vt, xt)) {
		System.out.println ("s[" + i + "] good from group " + v[i]);
	    } else {
		System.out.println ("s[" + i + "] bad from group " + v[i]);
	    }
	    
	}	


	BigInteger combSig = combineRsaSignatureShares (sigShare, v, threshold, x, e, n, l);
	System.out.println ("combSig = " + combSig);

	if (verifyRsa (e, n, signature, x)) 
	    System.out.println ("Signature good");
	else
	    System.out.println ("Signature invalid");

	*/

    }
    
   
    // True if the signature is valid on x for the given public key (e,n)
    static boolean verifyRsa (BigInteger e, BigInteger n, BigInteger signature,
			      BigInteger x) {
	return false;
    }
    
    
    // Compute a hash.  It might not be CR or OW, but you can
    // assume it is.  If you break the CR or OW property,
    // we'll give you a bonus point.  The output is assumed to be
    // 128 bits
    // Return: h = 2^a[0] * 3^[1] * ... * p_numElements^a[numElements-1] mod modulus
    // where p_k is the kth prime number
    static BigInteger H (BigInteger a[], int numElements, BigInteger modulus) {
	BigInteger result = BigInteger.ONE;
	
	// ...

	return result;
    }

    static BigInteger genRsaSignatureShare (BigInteger s, BigInteger n, BigInteger x,
					    BigInteger l) {
	return BigInteger.ZERO;
    }

    static boolean verifySignatureShare (BigInteger share, BigInteger n,
					 BigInteger V, BigInteger c,
					 BigInteger v, BigInteger z, BigInteger xhat,
					 BigInteger vt, BigInteger xt) {
	
	return false;
    }
    
    static BigInteger combineRsaSignatureShares (BigInteger sigShare[], int sigShareIndex[],
						 int numShares,
						 BigInteger x, BigInteger e,
						 BigInteger n, BigInteger l) {
	// ...
	
	return BigInteger.ZERO;
	
    }
    
    // Given an array of signature shares and the indexes (whose share it is)
    // return the value w 
    static BigInteger lambdaProduct (BigInteger sigShare[], int sigShareIndex[], int numShares,
				     BigInteger l, BigInteger n) {
	BigInteger w = BigInteger.ONE;
	
	return w;
    }
    
    // might be helpful subroutine
    static BigInteger lambdaExponent (int sigShareIndex[], int numShares, int j, BigInteger l) {
	BigInteger lambda = factorial (l);

	return lambda;
    }
    
    static BigInteger[] extendedEuclid(BigInteger a, BigInteger b)
    {
	// [c, x, y] where gcd(a,b) = c = xa + yb
        BigInteger[] result = new BigInteger[3];
	
	// bogus code
        result[0] = BigInteger.ZERO;
	result[1] = BigInteger.ZERO;
	result[2] = BigInteger.ZERO;
        return result;
    }


    static BigInteger factorial(BigInteger l) {
	BigInteger result = BigInteger.ONE;

	// ...

	return result;
    }

    // **********************************************************************
    // **********************************************************************
    // The remaining routines are optional, but might be useful
    // for implementing the dealer code to double check your work.
    // **********************************************************************
    // **********************************************************************

    // Return: Sigma_{i=0}^{a.length-1} a[i]*group^i
    // Requires groups >= 1
    static BigInteger polynomial (int group, int threshold,
				  BigInteger a[], BigInteger modulus) {
	return BigInteger.ZERO;
    }

    // Returns a safe prime and (p-1)/2
    static BigInteger[] safePrime (int bitlen, int certainty) {
	BigInteger p[] = new BigInteger[2];
	p[0] = p[1] = BigInteger.ZERO;
	
	//...
	return p;
    }


    // Returns a number uniformly in the range 0..n-1
    static BigInteger bigRandom (BigInteger n) {
	
	BigInteger r = n;

	// Note, we must toss out any random number out of range.
	// Other operations like truncation would throw the distribution
	// out of wack
	while (r.compareTo (n) >= 0 || r.compareTo (BigInteger.ZERO) < 0) {
	    r = new BigInteger (n.bitLength (), rnd);
	}

	return r;
    }

    // Return true if "a" is a QR mod p where p prime.  False otherwise.
    // Requires p prime
    static boolean QR (BigInteger a, BigInteger p) {
	return false;
    }

    // Return a random quadratic residue mod pq
    static BigInteger bigRandQR (BigInteger p, BigInteger q) {
	return BigInteger.ONE;
    }


}