Spring 2008                                                                            
95-804 Applied Cryptography
Homework 1 Part A
Due: Tuesday, April 1

Simulating a secure voting protocol in Java
=============================================

  Write a stand alone Java program that implements the secure 
voting protocol described on pages 126 and 127 of Schneier's "Applied
Cryptography". This protocol uses blind signatures and details can 
be found on the course slides. 

  You will write four classes. Each of these will be outlined below.

(1) Keys.java will encapsulate RSA key data and provide several public methods. 
The Keys.java code will contain the RSA algorithms for key generation, encryption
and signing.

Outline of Keys.java

// The following imports will be sufficient
import java.math.*;
import java.util.*;
import java.io.*;

/* Class Keys holds RSA key data. A Keys object is constructed with
   no arguments. The key material is placed in the object in one
   of two ways. The user can call generateKeySet to generate the 
   n, e, and d. Or, if the keys were generated from some other source, 
   they can be set individually. 

   A Keys object is meant to be a "write-once" object with respect 
   to n, e, and d. Either use the generateBasicKeySet method or use
   individual setters but not both. After one of the basic keys is 
   determined it cannot be changed.
*/   

 public class Keys {

     private BigInteger n, e, d; 
     private BigInteger k, kInverse;
           :
           :
     
     public Keys() 
     // constructor assigns null to all key data    
	    
     
     public void generateBasicKeySet (Random r1, Random r2)
     // generateBasicKeySet
     // a basic key set consists of e,d,n
     // use this method when using the class to generate new keys
     // use the set methods when the key data is provided
     // pre: none of the private data has yet been set.
     // post: d,e, and n are RSA keys. 

                        
     public void setD(BigInteger d)
     // set d with existing key data 
     //  pre: d not yet set 
                
     public void setE(BigInteger e) 
     // set e with existing key data 
     // pre: e not yet set
                       
     public void setN(BigInteger n) 
     // set n with existing key data 
     // pre: n not yet set


     public void setK(BigInteger k)
     // set k with existing key data 
     // k may be set many times with different values
     // setK calls computeKInverse                       


     //  getter method to read key data                                        
     public BigInteger getD() 
     public BigInteger getE() 
     public BigInteger getN()
     public BigInteger getK() 
     public BigInteger getKInverse() 

                      
     public void generateANewBlindingFactor() 
     //computes a new blinding factor each time it's called.
     // pre: n is an RSA modulus
     // post: object has a new blinding factor          
            
           	   
     public void computeKInverse() 
     //pre: generateANewBlindingFactor has been called so k is not null.
     // n is not null
     // post: the object holds the inverse of k modulo n               


     public BigInteger sign(BigInteger t) 
     //Takes a BigInteger producing a signed BigInteger 
     // pre: d and n must be valid RSA keys
     // post: t^d mod n is returned

     public BigInteger unSign(BigInteger t)
     // Takes a signed BigInteger and produces an unsigned BigInteger 
     // pre: e and n must be valid RSA keys and the BigInteger was signed
     // with d.
     // post: t^e mod n is returned

     private BigInteger findfirstnocommon(BigInteger n) 
     // find a small int that has no common divisor with n
     // used as a utility method when computing RSA keys


(2) CTF.java represents the Central Tabulating Facility.
The CTF class provides three public methods that will be called 
by a voter. There are two registration methods and one method
that takes a vote. In a later assignment, the voter's initial
request will be accompanied by a digital signature. In this 
assignment, you may assume that the voter has provided 
appropriate credentials. 


Outline of CTF.java

// The following imports will be sufficient
import java.math.*;
import java.util.*;

	public class CTF {

      public void setKeys(Keys keys) 
      // set the key data for this CTF object        

       	
      public boolean votesInProperForm()
      // Check if the voter has submitted votes in the proper format.
      // If any vote is not correctly formed then the voter may be attempting
      // to cheat. In that case we would not blindly sign the remaining data.
      // In this code you will simply unblind each vote and display
      // it on the screen. This will demonstrate that you know how
      // to unblind messages. Checking for proper formatting 
      // will be treated as optional. In a real protocol this would 
      // be essential.

      public int registrationStep1(String[] blindedMessages) 
      // The first registration step gathers the blinded messages and returns
      // an integer that represents the voting set whose blinding factor should
      // not be submitted by the voter. All other blinding factors will be passed
      // by the voter to the regsitrationStep2 method.

                     
      public String[] registrationStep2(String[] blindingFactors) 
      // The method registrationStep2 takes an array of blinding factors
      // and returns a set of messages each holding a blind signature.

      public boolean vote(String v)
      // The vote method takes one of the messages that was blindly
      // signed (also salted and encrypted) and returns true if the 
      // vote was accepted and false otherwise. This method decrypts 
      // the vote, discards the salt and checks the signatures, it 
      // checks its database for a duplicate identification 
      // number, saves the identification number, and tabulates the
      // votes. Your solution will demonstrate the counting of votes
      // from different clients. You may use a hash table rather than
      // a database.
       
      
 (3) The VotingUtility.java class holds several utility methods needed
by the voter and/or the CTF.

Outline of VotingUtility.java
             
     public static BigInteger normalStringToBigInteger(String s)
     // Convert a normal string to a BigInteger
     // The input may be an arbitrary string like "Hello".
     // The output is a BigInteger.

     
     public static String bigIntegerToNormalString(BigInteger x) 
     // Convert a BigInteger into a normal String
        
     public static BigInteger blind(BigInteger m, Keys keys) 
     // Pre: Keys has n, e, and a blinding factor k.
     // Post: returns a BigInteger that represents the BigInteger input
     // blinded by n, e, and k in Keys   

              
     public static String unBlindBigIntToString(BigInteger base, Keys keys) 
     //Remove the blinding from a big int and return a normal String. Keys
     //must contain e, d, k and n.
     //This method can be used to unblind data to check its format. It assumes
     //that the caller knows the blinding factor as well as the public and
     //private keys. 

     public static BigInteger unBlindSignedBigInteger(BigInteger blinded, Keys keys)
     // Keys must contain kInverse and n. The input is a signed blinded BigInteger
     // and the output is an unblinded BigInteger. This method can be used
     // by a recipient of signed blinded data. This method will compute 
     // s = (t^d) * ( 1/k) mod n as described in Schneier page 550.              


(4) The class Voter.java represents a voter in this simulation.

Outline of Voter.java

    public String[] getTenSets(String[] ballot, Keys ctfKeys)

    // pre: The ballot array is an array of strings holding a list of the three options
    // in an election. For example, ballot may contain the three strings "Bush",
    // "Kerry" and "Nader".
    // post: An array of 3 * 10 = 30 strings is returned. The array may be thought
    // of as holding 10 sets of three strings each. Each set has a randomly generated
    // integer identifier. Each string within a set has that identifier appended to the
    // candidate's name.  Each set also has a randomly generated blinding
    // factor used to blind each message in that set.


    public String[] produceRequestedFactors(int exclude) 
    // This is a convenience method. It takes an int that represents an
    // index into a blinding factor array. There were ten blinding
    // factors generated but since each is used three times
    // the array being indexed is of size thirty. The array returned
    // is of size 27. The three that were skipped were pointed
    // to by the input parameter exclude.  

    public static void main(String args[]) 
    // The main method carries out the secure voting protocol. It should
    // make three calls on a CTF object. The third call should represent
    // a randomly selected vote. Display messages should be included that
    // demonstrate that the simulation is working.
 
    The only keys used in this simulation are the CTF's keys. You will need to
copy the CTF's n and e over to the voter's code. You may do this by hand, 
i.e., copy and paste the CTF's public key data directly into the client code. 
Needless to say, the CTF key data should not change between runs of the
simulator.

Submission requirements:

    Submit all of your documented Java source code. Turn in several 
screen shots showing your simulator at work. You may also need to 
demonstrate your solution to the TA. 

A small percentage of the grade (10%) will be for readability and 
understandability of code. Use understandable variable and function 
names. Comment the code and explain important actions and conform to 
basic JAVA coding standards.

The breakup for the project evaluation will look like this:
     
     10% Code Readability
     40% Documentation
     50% Correctness of implementation