//This is the program, as demo'd, with only cosmetic changes.  The
//initialization button has been moved, additional space is provided for
//showing the suspected key, and a help utility (which uses the other two
//files I sent to you) which provides a standalone, scrollable help text
//file, have been added.  Tried adding some additional processing ("Friedman"
//processing, searching for tri-graphs, etc) but each one failed at solving
//the two ciphers we were given and provided very marginal performance on
//other self-generated "difficult" ciphers.  Very, very marginal return for
//modifying a fairly fast polynomial time algorithm with an exponential time
//one.  Soooo, I canned further enhancements.

//On with the code....
//Vig2.java
//
//Created: March, 1997; David Kreiner
//
//This class provides tools necessary for decrypting
//a cipher that was created using a Vigenere method.
//
//To compile into Java byte code:
//    javac Vig2.java
//To run the program
//    java Vig2
//
//Minimal operating instructions:
//	1. load in cipher text
//	2. hit initialize
//	3. hit automatic
//	4. adjust controls and repeat from 3
//	5. save plaintext
//
//In order to compile, the HelpFrame class must also exist in 
//the current directory.
import java.awt.*;
import java.io.*;
import java.util.*;


public class Vig2 extends Frame 
{
	//Global primitive variables
	int colcount[];				 //char count per column
	double vigfreq[][];			 //letter frequency per column
	int vigcount[][];			 //letter count per column
	BitSet solved;				 //boolean array for solving offsets
	boolean counted=false;		 //initialization boolean
	boolean found=false;		 //answer found boolean
	int key[], tempkey[];		 //hold suspected keywords
	int offset[][];				 //offset twn 2 key chars, based on
								 //largest MIC value twn them
	double strength_offset[][];	 //larget MIC value twn 2 columns
	int letcount[];				 //letter count per letter for whole text
	double offsens = .056;		 //default MIC sensitivity
	double klsens = .057;		 //default IC sensitivity
	double ts = 0;				 //default text sensitivity
	int totalcount;				 //total number of valid chars in text

	//GUI component declarations
	Panel textpanel,buttonpanel,supportpanel, selectpanel, userpanel;
	TextArea texttotest,answerarea, computations;
	TextField kasiski, kayone, suspect;
	TextField offsensf, klsensf;
	Button test_kas, test_kayone, pushbutton;
	Button clr, new_suspect, automat;
	Scrollbar keylength, offsetsel;
	Choice textmatch;
	StringBuffer theData, answer, s1;
	MenuBar m;
	Menu filemenu, helpmenu;
	MenuItem load, save, savelog, clearit, quitit, howto;
	File inf, outf;

	//Constructor function
	public Vig2()
	{
		super("Vigenere Tool");
	}

	//Startup method called when initiating the program.
	//Responsible for instantiating and placing all the 
	//GUI components.
	public void startup()
	{
		setLayout(new BorderLayout());

		//Set up the menubar
		m = new MenuBar();
		filemenu = new Menu("File");
		load = new MenuItem("Load Cipher");
		save = new MenuItem("Save Plaintext");
		savelog = new MenuItem("Save Log");
		clearit = new MenuItem("New");
		quitit = new MenuItem("Quit");
		helpmenu = new Menu("Help");
		howto = new MenuItem("How to...");
		filemenu.add(load);
		filemenu.add(save);
		filemenu.addSeparator();
		filemenu.add(savelog);
		filemenu.addSeparator();
		filemenu.add(clearit);
		filemenu.addSeparator();
		filemenu.add(quitit);
		helpmenu.add(howto);
		m.add(filemenu);
		m.add(helpmenu);
		m.setHelpMenu(helpmenu);
		this.setMenuBar(m);

		//Set up the Selectivity panel
		selectpanel = new Panel();
		selectpanel.setLayout( new GridLayout(2, 3, 5, 5) );
		klsensf = new TextField("IC Sensitivity: "+klsens+" (def)");
		offsensf = new TextField("MIC Sensitivity: "+offsens+" (def)");
		keylength = new Scrollbar(Scrollbar.HORIZONTAL,57,0,45,70);
		offsetsel = new Scrollbar(Scrollbar.HORIZONTAL,56,0,45,70);
		automat = new Button("Try Automatic");
		textmatch = new Choice();
		textmatch.addItem("Text Match: Standard");
		textmatch.addItem("Text Match: Looser");
		textmatch.addItem("Text Match: Loosest");
		selectpanel.add(klsensf);
		selectpanel.add(offsensf);
		selectpanel.add(textmatch);
		selectpanel.add(keylength);
		selectpanel.add(offsetsel);
		selectpanel.add(automat);
		
		//Set up the text panel (cipher and plaintext)
		pushbutton = new Button("Init");
		texttotest = new TextArea(8,30);
		answerarea = new TextArea(8,30);
		answerarea.setEditable(false);
		textpanel = new Panel();
		textpanel.add(pushbutton);
		textpanel.add(new Label("CipherText:"));
		textpanel.add(texttotest);
		textpanel.add(new Label("PlainText:"));
		textpanel.add(answerarea);
		textpanel.setBackground(Color.lightGray);
		this.add("North", textpanel);

		//Set up the support panel (where logging goes)
		computations = new TextArea(6,45);
		clr = new Button("Clear Computations");
		supportpanel = new Panel();
		supportpanel.add(new Label("Computations"));
		supportpanel.add(computations);
		supportpanel.add(clr);
		this.add("Center", supportpanel);
		
		//Set up the user interface panel for manual 
		//interventions
		kasiski = new TextField(2);
		kayone = new TextField(2);
		suspect = new TextField(20);
		test_kas = new Button("Try Kasiski");
		test_kayone = new Button("Try K1");
		new_suspect = new Button("Try Key");
		buttonpanel = new Panel();
		buttonpanel.add(test_kas);
		buttonpanel.add(new Label("Kasiski "));
		buttonpanel.add(kasiski);
		buttonpanel.add(test_kayone);
		buttonpanel.add(new Label("K1: "));
		buttonpanel.add(kayone);
		buttonpanel.add(test_kayone);
		buttonpanel.add(new Label("Suspected Key"));
		buttonpanel.add(suspect);
		buttonpanel.add(new_suspect);
		
		userpanel = new Panel();
		userpanel.setLayout( new BorderLayout());
		userpanel.add("North", selectpanel);
		userpanel.add("South", buttonpanel);
		this.add("South",userpanel);
		
		//Resize, then pack the frame to make things look good
		this.setSize(600,450);
		this.pack();
		this.setVisible(true);
	}

	//Handle such events as closing the frame and adjusting the 
	//scrollbars by overriding handleEvents functions
	public boolean handleEvent(Event e)
	{
		
		//User chooses to kill frame, exit gracefully
		if (e.id == Event.WINDOW_DESTROY)
		{
			setVisible(false);
			dispose();
			System.exit(0);
			return true;
		}
		
		//User modifies the IC Sensitivity
		else if (e.target == keylength)
		{
			klsens = (double)keylength.getValue() / 1000;
			//Show user the change
			if (keylength.getValue() == 57)
			{
				klsensf.setText("IC Sensitivity: "+klsens+" (def)");
			}
			else
			{
				klsensf.setText("IC Sensitivity: "+klsens);
			}
			return true;
		}
		
		//User modifies the MIC Sensitivity
		else if (e.target == offsetsel)
		{
			offsens = (double)offsetsel.getValue() / 1000;
			//show user the change
			if (offsetsel.getValue() == 56)
			{
				offsensf.setText("MIC Sensitivity: "+offsens+" (def)");
			}
			else
			{
				offsensf.setText("MIC Sensitivity: "+offsens);
			}
			return true;
		}
		return super.handleEvent(e);
	}

	//Where the bulk of the actions will be handled
	public boolean action(Event e, Object o)
	{
		
		//Handle the first INIT for this ciphertext
		if ( e.target == pushbutton && !counted)
		{
			answer = new StringBuffer(texttotest.getText() );
			theData = new StringBuffer();
			//count the number of lower case characters and report
			//store stripped data to theData for Kasiski test
			for (int i = 0; i<answer.length(); i++ )
			{
				if (Character.isLowerCase(answer.charAt(i)))
				{
					theData.append(answer.charAt(i));
					totalcount++;
				}
			}
			s1 = new StringBuffer("Init done, char count: "+totalcount);
			computations.setText(s1.toString() );
			//Perform kasinski test for trigraphs in text
			compute_kas();
			answerarea.setText("Initialization Done" );
			counted = true;				 //Initialization done
			return true;
		}
		
		//Handle actions required to test a given keylength
		if ( e.target == test_kas && counted )
		{
			//get keylength user has specified and run validity check
			int col_size = Integer.parseInt(kasiski.getText());
			computations.append("\nTesting keylength of "+col_size);
			boolean valid = convert_to_columns(col_size);
			//if validity check passes, try to solve for this keylength
			if (valid)
			{
				//Reset and zeroize the global key variable
				key = new int[col_size + 1];
				for (int i=1;i<=col_size;i++) {key[i] = 0; }
				computations.append("\nComputing relative offsets");
				compute_offsets(col_size);
				computations.append("\nSelecting relative offsets");
				select_offsets(col_size);
				computations.append("\nDone offsets");
				//Check the base keystream's 26 possible shifts
				for (int i = 0; i<26;i++)
				{
					computations.append("\nTesting shift: "+(char)(i+65));
					found = runtest(col_size, i);
					if (found)
					{
						printkey(col_size, i);
						return true;
					}
				}
			}
			return true;
		}

		//This event triggers a test of all keylengths from 
		//2 to 15.
		if ( e.target == automat && counted)
		{
			for(int col_size =2;col_size < 16; col_size++)
			{
				computations.append("\nTesting keylength of "+col_size);
				boolean valid = convert_to_columns(col_size);
				if (valid)
				{
					key = new int[col_size + 1];
					for (int i=1;i<=col_size;i++) {key[i] = 0; }
					computations.append("\nComputing relative offsets");
					compute_offsets(col_size);
					computations.append("\nSelecting relative offsets");
					select_offsets(col_size);
					computations.append("\nDone offsets");
					for (int i = 0; i<26;i++)
					{
						computations.append("\nTesting shift: "+i);
						found = runtest(col_size, i);
						if (found)
						{
							printkey(col_size, i);
							return true;
						}
					}
				}
			}
			return true;
		}

		//Handle button for trying a new key; simply apply keystream
		//to the text.
		else if (e.target == new_suspect)
		{
			String keystream = new String(suspect.getText() );
			int col_size = keystream.length();
			int temkey[];
			int counter = 0;
			temkey = new int[col_size+1];
			for (int i=1;i<=col_size;i++)
			{
				temkey[i] = (int)(keystream.charAt(i-1)) - 65;
			}
			answer = new StringBuffer(texttotest.getText() );
			for (int i = 0; i<answer.length(); i++ )
			{
				if (Character.isLowerCase(answer.charAt(i)))
				{
					//determine column
					int keyindex = (counter%col_size)+1;
					counter++;
					//determine new character
					int index2 = ((int)answer.charAt(i) - 97);
					index2 = (index2 - temkey[keyindex] +26)%26;
					//set new character
					answer.setCharAt(i,(char)(index2+65));
				}
			}
			answerarea.setText(answer.toString());
			return true;
		}
				
		//Handle event to try a new K1 value...this option allows		
		//user to see result of shifting keystream an integral number
		//of places
		else if (e.target == test_kayone && counted)
		{
			answer = new StringBuffer(texttotest.getText() );
			int counter = 0;
			//convert user supplied shift to number form
			int shift = (int)(kayone.getText().charAt(0)) - 65;
			int col_size = Integer.parseInt(kasiski.getText());
			computations.append("Getting new key\n");
			tempkey = new int[col_size + 1];
			StringBuffer q= new StringBuffer();
			try 
			{
				//print out the keystream being tested
				for (int k = 1;k<=col_size;k++)
				{
					tempkey[k]=(key[k]+shift)%26;
					q.append((char)(tempkey[k]+65));
				}
			} catch (Exception e2) { computations.append("e:"+e2);}
			computations.append("\nnew key: "+q+"\n");
			//Apply new key to text
			for (int i = 0; i<answer.length(); i++ )
			{
				if (Character.isLowerCase(answer.charAt(i)))
				{
					
					int keyindex = (counter%col_size)+1;
					counter++;
					int index2 = ((int)answer.charAt(i) - 97);
					index2 = (index2 - tempkey[keyindex] +26)%26;
					answer.setCharAt(i,(char)(index2+65));
				}
			}
			answerarea.setText(answer.toString());
			return true;
		}

		//Handle event from File menu to load in a new cipher.  Meat of
		//processing handled by FileDialog object (Java provided).
		else if (e.target == load && !counted)
		{
			try {
				FileDialog fd = new FileDialog(this,"Open",FileDialog.LOAD);
				fd.setVisible(true);
				String s = fd.getFile();
				super.setTitle("Vigenere Tool - "+s);
				inf = new File(s);
				BufferedReader in = 
					new BufferedReader(new InputStreamReader(new FileInputStream(inf)));
				String l = new String(in.readLine());
				while (l != null)
				{
					texttotest.append(l.toLowerCase() + "\n");
					l = new String(in.readLine());
				}

			} catch (IOException b) {System.err.println("Caught: "+b);}
			return true;
		}

		//Handle event from File menu to save plaintext. Meat of the 
		//process contained within FileDialog object (Java provided).
		else if (e.target == save)
		{
			try
			{
			FileDialog fd = new FileDialog(this,"Save",FileDialog.SAVE);
			fd.setVisible(true);
			String s = fd.getFile();
			outf = new File(s);
			PrintStream out = 
				new PrintStream(new FileOutputStream(outf));
			String st = answerarea.getText();
			out.print(st);
			out.flush();
			out.close();
			} catch (IOException se) {System.err.println("Caught"+se);}
			return true;
		}

		//Handle event from File menu to save log...uses same code
		//as saving plaintext, just a different text area as source.
		else if (e.target == savelog)
		{
			try
			{
			FileDialog fd = new FileDialog(this,"Save",FileDialog.SAVE);
			fd.setVisible(true);
			String s = fd.getFile();
			outf = new File(s);
			PrintStream out = 
				new PrintStream(new FileOutputStream(outf));
			String st = computations.getText();
			out.print(st);
			out.flush();
			out.close();
			} catch (IOException se) {System.err.println("Caught"+se);}
			return true;
		}

		//Handle a clear command from the menu.
		else if (e.target == clearit)
		{
			texttotest.setText("");
			answerarea.setText("");
			answer = new StringBuffer();
			theData = new StringBuffer();
			totalcount = 0;
			counted = false;
			return true;
		}

		//Ever so slightly ambiguous, this clear command clears only
		//the computation text box.
		else if (e.target == clr)
		{
			computations.setText("");
			return true;
		}

		//Call to build the HelpFrame for this application
		else if (e.target == howto)
		{
			HelpFrame h = new HelpFrame("vigenere");
			h.startup();
			return true;
		}

		//Handle the choice for sensitivity of the text matching
		else if (e.target == textmatch)
		{
			if (o.equals("Text Match: Standard"))ts = 0;
			else if (o.equals("Text Match: Looser"))	ts = .6;
			else if (o.equals("Text Match: Loosest")) ts = 1.2;
			return true;
		}

		//Handle a quit command from the menu. Hide the frame,
		//dispose of its resources, and exit gracefully.
		if (e.target == quitit )
		{
			setVisible(false);
			dispose();
			System.exit(0);
			return true;
		}

	return true;
	}

	//Figure_mic
	//Function to determine the mutual incidence of coincidence
	//between two columns, given a specific shift of the second.
	public double figure_mic (int first, int second, int shift_2)
	{
		double answer = 0.0;
		for (int i=0; i<26;i++) 
		{
			answer += vigfreq[first][i] * vigfreq[second][(i+26-shift_2)%26];
		}
		return answer;
	}

	//Initialize_globals
	//Used to reset all the global variables for a new keylength.
	public void initialize_globals(int no_columns)
	{
		int max_len = totalcount/no_columns +1;
		vigfreq= new double[no_columns+1][27];
		vigcount= new int[no_columns+1][27];
		colcount= new int[no_columns+1];
		key= new int[no_columns+1];
		for (int i=0;i<no_columns+1;i++)
		{
			colcount[i]=0;
			key[i]=0;
			for (int j=0;j<26;j++)
			{
				vigfreq[i][j]=0.0;
				vigcount[i][j]=0;
			}
		}
	}

	//Convert_to_columns
	//Perform the necessary counts and partitioning of data based
	//on given number of columns.  Then check each columns IC to
	//see if this keylength meets the minimum validation check.
	public boolean convert_to_columns(int no_columns)
	{
		initialize_globals(no_columns);
		int validint = 0;
		//divide it up
		for (int i=0;i<theData.length();i++)
		{
			int col = (i%no_columns)+1;
			int row = (i/no_columns);
			colcount[col]++;
			int index = (int)(theData.toString().charAt(i)-97);
			vigcount[col][index]++;
		}
		computations.append("\nIndices filled...determining validity.");
		//
		//Check validity vs. IC sensitivity (variable klsens).
		for (int j=1; j<=no_columns;j++)
		{
			double test_case = 0.0;
			int cumul = 0;
			for (int k=0;k<26;k++)
			{
				vigfreq[j][k]=(double)vigcount[j][k]/colcount[j];
				test_case += (vigfreq[j][k]*vigfreq[j][k]);

			}

			computations.append("\nIC for column "+j+" is "+test_case);
			if (test_case >= klsens)
			{
				validint++;
			}
		}
		//If all columns are valid, return true
		if (validint == no_columns)
		{
			return true;
		}
		return false;
	}

	//Compute_offsets
	//For each pairing of columns, compute and store the maximum
	//Mutual Incidence of Coincidence, accounting for all possible
	//shifts
	public void compute_offsets(int no_columns)
	{
		double curr_val;
		strength_offset = new double[no_columns+1][no_columns+1];
		offset = new int[no_columns+1][no_columns+1];
		for (int i=1;i<no_columns;i++)
		{
			for (int j=i+1;j<=no_columns;j++)
			{
				computations.append("\nStrength 'twn "+i+" and "+j);
				strength_offset[i][j] = 0.0;
				curr_val = 0.0;
				//test all 26 shifts and save largest value, offset
				for (int k=0;k<26;k++)
				{
					curr_val = figure_mic(i,j,k);
					if (curr_val > strength_offset[i][j])
					{
						strength_offset[i][j]=curr_val;
						offset[i][j]=k;
					}
				}
				computations.append(":"+strength_offset[i][j]);
			}
		}
	}

	//Select_offsets
	//Go through the MIC offsets defined by Compute_offsets to solve
	//the offsets of the key from position 2 to n (reference to 
	//position 1).  MIC strengths must be greater than user defined
	//threshhold to be considered valid for the computation.
	public void select_offsets(int no_columns)
	{
		//use a BitSet as an array of booleans to determine whether
		//each position in the keystream has been solved yet.
		solved = new BitSet(no_columns +1);
		solved.set(1);
		for (int n=2;n<=no_columns;n++)
		{
			solved.clear(n);
		}
		//for each pairing...
		for (int i=1;i<no_columns;i++)
		{
			for (int j=i+1;j<=no_columns;j++)
			{
				//If only one of the two is solved...
				if (solved.get(i) ^ solved.get(j))
				{
					//and the strength is greater than threshhold
					if (strength_offset[i][j] > offsens)
					{
						if (solved.get(i))
						{
							key[j]=(26+key[i]-offset[i][j])%26;
							solved.set(j);
						} else {
							key[i]=(key[j]+offset[i][j])%26;
							solved.set(i);
						}
					}
				}
			}
		}
		StringBuffer s=new StringBuffer("A");
		for (int i=2;i<=no_columns;i++)
		{
			s.append((char)(key[i]+65));
		}
		//show suspected key in Suspect Key field and put in log
		suspect.setText(s.toString());
		computations.append("\nSuspected key: "+s.toString() );
	}

	//Runtest
	//This is the utility which tests whether the current base key,
	//plus the provided shift, is indeed valid English text.
	//If it is true, print the solved plaintext to the answerarea,
	//and return true to calling routine.
	public boolean runtest (int no_columns, int shift)
	{
		//Declare and initialize variables for this function.
		letcount = new int[27];
		tempkey = new int[no_columns + 1];
		double la=0.0, le=0.0, lt= 0.0, lz =0.0;
		int counter = 0;
		int keyindex = 0;
		//Clear letter counting array
		for (int j = 0; j<26; j++)
		{
			letcount[j] = 0;
		}
		//Set temporary key for this shift
		for (int k = 1; k <=no_columns;k++)
		{
			tempkey[k] = (shift + key[k])%26;
		}
		answer = new StringBuffer(texttotest.getText() );
		//Convert text counts accordiing to new key
		//and determine frequency of characters a,e,t,z.
		for (int i = 1; i<=no_columns; i++ )
		{
			letcount[0]+=vigcount[i][(0+tempkey[i])%26];
			letcount[4]+=vigcount[i][(4+tempkey[i])%26];
			letcount[19]+=vigcount[i][(19+tempkey[i])%26];
			letcount[25]+=vigcount[i][(25+tempkey[i])%26];
		}
		//Compute and report computations for frequency of a,e,t,z
		if (totalcount != 0) //protect against division by zero 
		{
			la = 100*(double)letcount[0]/totalcount;
			computations.append("a:"+la);
			le = 100*(double)letcount[4]/totalcount;
			computations.append("e:"+le);
			lt = 100*(double)letcount[19]/totalcount;
			computations.append("t:"+lt);
			lz = 100*(double)letcount[25]/totalcount;
			computations.append("z:"+lz);
		}
		//Test a,e,t, and z frequencies against threshholds...if valid
		//text, print out the solved plaintext and return true.
		if (le > (6.0-ts) && lt > (6.0-ts) && la > (5.0-ts) && lz < (0.5+ts) )
		{
			counter = 0;
			for (int i = 0; i<answer.length(); i++ )
			{
				if (Character.isLowerCase(answer.charAt(i)))
				{
					keyindex = (counter%no_columns)+1;
					counter++;
					int index2 = ((int)answer.charAt(i) - 97);
					index2 = (index2 - tempkey[keyindex] +26)%26;
					answer.setCharAt(i,(char)(index2+65));
				}
			}
			answerarea.setText(answer.toString());
			return true;
		}
		return false;
	}
	
	//Printkey
	//Prints the key in the suspect key field
	public void printkey(int no_columns, int shift)
	{
		StringBuffer s=new StringBuffer();
		for (int i=1;i<=no_columns;i++)
		{
			s.append((char)((26+key[i]+shift)%26+65));
		}
		suspect.setText(s.toString());
   	}

	//Compute_kas
	//This function performs a rudimentory Kasiski test, checking
	//distances between common tri-graphs in text.  This function 
	//uses the global stringbuffer theData, which is stripped of non-
	//characters.
	public void compute_kas()
	{
		//declare local variables
		ArrayList<String> used_tris;
		ArrayList<Integer> distances;
		String token, tempdata;
		int divfreq[];

		used_tris = new ArrayList<String>();
		distances = new ArrayList<Integer>();
		divfreq = new int[16];
		tempdata = theData.toString();
		for (int i = 0; i< (theData.length()-6); i++)
		{
			int start = i;
			token = tempdata.substring(i, i+2);
			//check the used trigraph list to see if this one
			//is already accounted for; if not look for matches.
			if (used_tris.contains(token)) break;
			while (start != -1)
			{
				//relies on fact that indexOf returns -1 if not found
				start = tempdata.indexOf(token, start + 3);
				//if match found, add this to list, add distance to 
				//distance list, and continue from where found.
				if (start > 0)
				{
					used_tris.add(token);
					distances.add(new Integer(start - i));
				}
			}
		}
		//Run through the collected distances and identify which values
		//between 2 and 15 divide the distances evenly.  Update the counts
		//associated with those that do divide them evenly.
		for( int x = 0; x < distances.size(); x++ )
		{
			Integer dist = new Integer(distances.get(x).toString() );
			for (int j=2;j<16;j++)
			{
				if (dist.intValue() %j == 0)
				{
					divfreq[j]++;
				}
			}
		}
		computations.append("\nKasiski Strengths from 2-15");
		computations.append("\n(try largest \"spikes\" first)\n");
		for (int k=2;k<16;k++)
		{
			computations.append("\nFor "+k+" --> "+divfreq[k]);
		}
	}

	//The main function that starts it all!!
	public static void main(String args[])
	{
		Vig2 v = new Vig2();
		v.startup();
	}
}