/********* CryptoHill.java ********
 *
 *  APCS Labs 2011-2020
 *  Cryptology
 *  Dr. John Pais
 *  pais.john@gmail.com
 *  Copyright (c) 2011 to present John Pais. All rights reserved.
 *
 *  A Hill cryptosystem uses a matrix affine cipher: Ax + B.
 *
 */

package CryptoHill;
import java.util.*;
import CryptoAffine.Ntuple;
import CryptoAffine.CryptoAffine;

public class CryptoHill
{
   protected List<Character> alphabet;
   protected int alphaSize;
   private String dirPath;
   private List<Ntuple> lexicon = new ArrayList<Ntuple>();
   private List<String> plaintextWords = new ArrayList<String>();
   private List<Integer> units = new ArrayList<Integer>();

   private CryptoAffine ca;

   public CryptoHill(List<Character> alphabet, String dirPath, String lexicon)
   {
		this.alphabet = alphabet;
		this.alphaSize = alphabet.size();
		this.dirPath = dirPath;
		ca = new CryptoAffine(alphabet, dirPath, lexicon);
		plaintextWords = ca.getPlaintextWords();
		units = ca.groupOfUnits(alphaSize);
   }

   // Problem 1.
   public CryptoAffine getCA()
   {
	   return ca;
   }

   // Problem 2. transpose matrix
   public long[][] transpose(long[][] a)
	{
		int m = a.length;
		int n = a[0].length;
		long[][] b = new long [n][m];
		for (int i = 0 ; i < m; i++)
			for (int j = 0; j < n; j++)
			b[j][i] = a[i][j];
			return b;
	}

   // Problem 3. sum of two vectors
   public static long[] sum(long[] x, long[] y)
   {
		if (x.length != y.length) throw new RuntimeException("illegal vector dimensions");
		long[] z = new long[x.length];
		for (int i=0; i<x.length; i++)
			z[i] = x[i] + y[i];
		return z;
	}

   // Problem 4. matrix multiplication: c = a * b
   public long[][] multiply(long[][] a, long[][] b)
   {
		int m1 = a.length;
		int n1 = a[0].length;
		int m2 = b.length;
		int n2 = b[0].length;
		if (n1 != m2) throw new RuntimeException("Illegal matrix dimensions.");
		long[] [] c = new long[m1][n2];
		for (int i = 0; i < m1; i++)
			for (int j = 0; j < n2; j++)
				for (int k = 0; k < n1; k++)
					c[i][j] += a[i][k] * b[k][j];
		return c;
	}

   // Problem 5. matrix-vector multiplication: a * x
   public long[] multiply(long[][] a, long[] x)
   {
		int m = a.length;
		int n = a[0].length;
		if (x.length != n) throw new RuntimeException("Illegal matrix dimensions.");
		long[] y = new long[n];
		for (int j = 0; j < n; j++)
			for (int i = 0; i < m; i++)
				y[j] += a[i][j] * x[i];
		return y;
	}

   // Problem 6. vector-matrix multiplication: x^T * a
   public long[] multiply(long[] x, long[][] a)
   {
		int m = a.length;
		int n = a[0].length;
		if (x.length != m) throw new RuntimeException("Illegal matrix dimensions.");
		long[] y = new long[m];
		for (int j = 0; j < n; j++)
			for (int i = 0; i < m; i++)
				y[i] += a[i][j] * x[i];
		return y;
	}

	// Problem 7. method to create submatrix of mat (w.r.t. row p and col q)
    // written into temp
	public void submatrix(long[][] mat, long[][] temp, int p, int q)
	{
		int n = mat.length;
		int i = 0, j = 0;
		for (int row = 0; row < n; row++)
		{
			for (int col = 0; col < n; col++)
			{
				if (row != p && col != q)
				{
					temp[i][j++] = mat[row][col];
					if (j == n - 1)
					{
						j = 0;
						i++;
					}
				}
			}
		}

	}

	// Problem 8. recursive method for determinant of square matrix
	public long det(long[][] mat, int n)
	{
		int detVal = 0;
		if (n==1)
		{
			return mat[0][0];
		}
		else
		{
			//initialize temp to store submatrix
			long[][] temp = new long[n-1][n-1];
			int sign = 1;
			for (int k=0; k < n; k++)
			{
				submatrix(mat, temp, 0, k); //create submatrix in temp
				detVal += sign * mat[0][k] * det(temp, n - 1); //recursive call
				sign = -sign; // alternate signs

			}
		}
		return detVal;
	}

   // Problem 9. matrix adjugate of a square matrix
   public long[][] adjugate(long[][] a)
   {
		int n = a.length;
		long[][] temp = new long[n-1][n-1];
		long [][] adj = new long[n][n];
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				submatrix(a,temp,i,j);
				adj[i][j] = ((int)Math.pow(-1, i+j))*det(temp, n-1);
				temp = new long[n-1][n-1];
			}
		}
		adj = transpose(adj);
		return adj;
	}

   // Problem 10. scalar times matrix
   public long[][] scalarMult(long r, long[][] a)
   {
		int n = a.length;
		int m = a[0].length;
		long[][] b = new long[n][n];
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				b[i][j] = r * a[i][j];
			}
		}
		return b;
	}
	// Problem 11. display matrix
	public void display(long[][] mat, int row, int col)
	{
		for(int i=0; i < row; i++)
			{
				for (int j = 0; j < col; j++)
					{
						System.out.print(mat[i][j] + " ");
					}
			System.out.print("\n");
		}
	}

   // Vector & Matrix Methods mod k (alphaSize)
   // Needed for Hill Encryption/Decryption

   // Problem 12. scalar times matrix mod k
   public long[][] scalarMultMod(long r, long[][] a, long k)
   {
	  int n = a.length;
	  int m = a[0].length;
	  long[][] b = new long[n][n];
	  for (int i=0; i < n; i++)
	  {
		  for (int j=0; j < m; j++)
		  {
			  b[i][j] = (r*a[i][j]) % k;
			  if (b[i][j] < 0)
			  {
				  b[i][j] += k;
			  }
		  }
	  }
	  return b;
   }

   // Problem 13. scalar times vector mod k
   public long[] scalarMultMod(long r, long[] v, long k)
   {
       int temp = v.length;
       for (int i = 0; i < temp; i++ )
       {
           v[i] = (r * v[i]) % k;
           if (v[i] < 0)
           {
               v[i] += k;
           }
       }
       return v;
   }

   // Problem 14. matrix mod k
   public long[][] matrixMod(long[][] a, long k)
   {
	   int n = a.length;
	   int m = a[0].length;
	   long [][] b = new long [n][m];
	   for (int i = 0; i < n; i++)
	   {
		   for (int j = 0; j < n; j++)
		   {
			   b[n][m] = a[n][m] % k;
			   if (b[n][m] < 0)
			   {
				   b[n][m] += k;
			   }
		   }
	   }
	   return b;
   }

   // Problem 15. vector mod k
   public long[] vectorMod(long[] v, long k)
   {
	  int tmp = v.length;
	  for (int i = 0; i < tmp; i++)
	  {
		  v[i] %= k;
		  if (v[i] < 0)
		  {
			  v[i] += k;
		  }
	  }
	  return v;
   }

   // Problem 16. matrix inverse mod k when it exists
   // note that we use two methods from our CryptoAffine object
   public long[][] matMultInvMod(long[][] a, long k)
   {
	   	long det = (det(a,a.length) % k + k) % k;
		if (det == 0 || ca.gcd((int)det,(int)k) != 1) throw new RuntimeException("matrix is not invertible.");
		return scalarMultMod(ca.inverse((int)det), adjugate(a),k);
   }

   // Problem 17. vector additive inverse mod k
   public long[] vecAddInvMod(long[] v, long k)
   {
	   int tmp = v.length;
	   long[] b = new long[tmp];
	   for (int i = 0; i < tmp; i++)
		  {
			  b[i] = k-v[i];
		  }
		  return b;
   }

   // Problem 18. matrix multiplication mod k: c = a * b
   public long[][] multiplyMod(long[][] a, long[][] b, long k)
   {
	   int m1 = a.length;
	   int n1 = a[0].length;
	   int m2 = b.length;
	   int n2 = b[0].length;
	   if (n1 != m2) throw new RuntimeException("Illegal matrix dimensions.");
	   long[] [] c = new long[m1][n2];
	   for (int i = 0; i < m1; i++)
	   {
		   for (int j = 0; j < n2; j++)
		   {
			   for (int x = 0; x < n1; x++)
			   {
				   c[i][j] += (a[i][x] * b[x][j]) % k;
				   if (c[i][j] < 0)
				   {
					   c[i][j] += k;
				   }
			   }
		   }
	   }
	   return c;
   }

   // Problem 19. matrix-vector multiplication mod k: a * x
   public long[] multiplyMod(long[][] a, long[] x, long k)
   {
	   	int m = a.length;
		int n = a[0].length;
		if (x.length != n) throw new RuntimeException("Illegal matrix dimensions.");
		long[] y = new long[n];
		for (int j = 0; j < n; j++)
		{
			for (int i = 0; i < m; i++)
			{
				y[j] += (a[i][j] * x[i]) % k;
				if (y[j] < 0)
				{
					y[j] += k;
				}
			}
		}
		return y;
   }

    // Problem 20. generate random n by n matrix invertible mod k
	public long[][] genRndMatrixMod(int n, int k)
	{
		long[][] a = new long[n][n];
		Random rnd = new Random();
		long det = 0;
		while (det == 0 || ca.gcd((int)det,(int)k) != 1)
		{
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					a[i][j] = rnd.nextInt(k);
				}
			}
			det = det(a,a.length) % k;
			if (det < 0)
			{
				det += k;
			}
		}
		return a;
	}

    // Problem 21. generate random n vector mod k
	public long[] genRndVectorMod(int n, int k)
	{
		long[] a = new long[n];
		Random rnd = new Random();
		for (int j = 0; j < n; j++)
		{
			a[j] = rnd.nextInt(k);
		}
		return a;
	}

	// Problem 22. precondition: matKey[n][n], vecKey[n], blocksize = n
	// = str.length(), all characters in str are in the alphabet
	public String hillEncryptBlock(long[][] matKey, long[] vecKey, String block)
	{
		int n = block.length();
		long k = alphaSize;
		char[] plainChars = block.toCharArray();
		long[] plainIndexes = new long[n];
		long[] cipherIndexes = new long[n];
		char[] cipherChars = new char[n];

		// create plainIndexes vector of plainChars
		for(int i = 0; i < n; i++)
		{
				plainIndexes[i] = alphabet.indexOf(plainChars[i]);
		}

		// encrypt plainIndexes vector
		cipherIndexes = vectorMod(sum(multiply(matKey,plainIndexes), vecKey),k);

		// create cipherChars array of characters
		for(int i = 0; i < n; i++)
		{
			cipherChars[i] = alphabet.get((int)cipherIndexes[i]);
		}

		// return ciphertext string block
		return String.valueOf(cipherChars);

		// insert your code here
	}

	// Problem 23. precondition: matKey[n][n], vecKey[n], blocksize = n
	// = str.length(), all characters in str are in the alphabet
	public String hillDecryptBlock(long[][] matKey, long[] vecKey, String block)
	{
		int n = block.length();
		long k = alphaSize;
		char[] cipherChars = block.toCharArray();
		long[] cipherIndexes = new long[n];
		long[] plainIndexes = new long[n];
		char[] plainChars = new char[n];

		// create cipherIndexes vector of cipherChars
		for(int i = 0; i < n; i++)
		{
			cipherIndexes[i] = alphabet.indexOf(cipherChars[i]);
		}

		// decrypt cipherIndexes vector

		plainIndexes = vectorMod(multiply(matMultInvMod(matKey,k), sum(cipherIndexes, vecAddInvMod(vecKey,k))),k);

		// create plainChars array of characters
		for(int i = 0; i < n; i++)
		{
			plainChars[i] = alphabet.get((int)plainIndexes[i]);
		}

		// return plaintext string block

		return String.valueOf(plainChars);
	}
}