// Arup Guha
// 6/6/01
// COT 5937 Homework 1 : Affine Cipher functions
// Program Description : Two functions pertaining to the affine cipher
//                       are included. One function takes an input file,
//                       and encryptions keys a and b, and produces the
//                       ciphertext in a file designated by a parameter.
//                       The other function takes in four parameters, a
//                       and b by value and c and d by reference. If a
//                       and b are valid encryption keys for the affine 
//                       cipher, c and d are set to the corresponding
//                       decrypting keys. Otherwise they are both set to 0.
//                       A driver program allows the user to test each of
//                       the functions separately.

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include <time.h>

int menu(); // Prints the menu
int euclid(int, int); // Performs the extended euclid's algorithm
void doaffine(char[],char[], int, int); // encrypts a file using the given keys
void affine(int a, int b, ifstream&, ofstream&); // helps the function doaffine
bool get_decrypt(int a, int b, int& c, int& d); // computes decryption keys c
                                                // and d from given a and b.

main() {

  // Main menu of driver program
  int ans = menu();
  while (ans != 3) {

    // Allows user to test encryption function
    if (ans == 1) {

      // Get pertinent info from the user.
      char inputfile[100];
      char outputfile[100];
      cout << "Enter input file name." << endl;
      cin >> inputfile;
      cout << "Enter output file name." << endl;
      cin >> outputfile;

      int a,b;
      cout << "Enter Affine cipher values of a and b." << endl;
      cin >> a >> b;

      // Make the function call with this info.
      doaffine(inputfile, outputfile, a, b);

    }

    // Allows user to test decryption key function
    else if (ans == 2) {
      
      // Gets necessary info from the user.
      int a,b;
      cout << "Enter Affine cipher values of a and b." << endl;
      cin >> a >> b;

      // Calls the function and writes the output to the screen.
      int c,d;
      if (get_decrypt(a,b,c,d))
	cout << "Decrypting keys are " << c << " and " << d << endl;
      else
	cout << "Sorry, those are not valid keys."

    }
    else if (ans != 3)
      cout << "Sorry, not a valid menu choice. Try again." << endl;

    ans = menu();
  }
    
}

// Prints out user's choices.
int menu() {
  int pick;
  cout << "Pick your menu choice :" << endl;
  cout << "1. Apply affine cipher to a file\n";
  cout << "2. Find corresponding decrypting keys for the affine cipher\n";
  cout << "3. Quit.\n";
  cin >> pick;
  return pick;
}

// Opens appropriate streams and calls affine to do actual encryption.
void doaffine(char inputfile[], char outputfile[], int a, int b) {
     
  // Checks to see if the key is valid.
  if (euclid(a,26)<0) 
    cout << "Sorry that is not a valid affine shift key.";
  else {

    // Opens appropriate streams 
    ifstream input(inputfile);
    ofstream output(outputfile);

    affine(a,b,input, output);

    // Closes the streams
    input.close();
    output.close();
  }
  
}

// This function does the actual translation.
void affine(int a, int b, ifstream& input, ofstream& output) {
  
  // Loop until everything from the input file has been read.
  while (!input.eof()) {

    // Read in the next character and encrypt it.
    char c;
    input.get(c);

    // Only encrypt if it's an upper or lowercase letter.
    if (c >= 65 && c <= 90) 
      c = char( ( ( a*((int)c-65)+b)%26) + 65);
    else if (c >= 97 && c <= 122)
      c = char( ( ( a*((int)c-97)+b)%26) + 97);
    
    // Output the character to the output file.
    output.put(c);
  }

}

// Determines decryption keys c and d for the given encryption keys a and b.
bool get_decrypt(int a, int b, int& c, int& d) {

  // Find the inverse of a mod 26, if it exists.
  int inverse = euclid(a, 26);

  // A negative value for inverse indicates no inverse, and an invalid key.
  if (inverse < 0) {
    c = 0;
    d = 0;
    return false;
  }
  else {
    c = inverse; // From class.
    d = (-1*b*c)%26; // Look at math below to explain this.
    
    // Accounts for the case where d ends up negative. 
    if (d < 0) 
      d += 26;
  }
  return true;
}

/*
Derivation of above result:

e(x) = ax + b
d(x) = cx + d
     = c(ax + b) + d
     = cax + bc + d
     = x, as required by all cryptosystems.

Equating coefficients, we have ca = 1, and (bc + d) = 0
This means that c = a^(-1) mod 26, and d = -bc mod 26.
*/


// Precondition: n > x, and n and x are positive integers, 
// Post condition: Returns x' the inverse of x (mod n), if gcd(x,n)=1 else
// returns -1*gcd(x,n)
int euclid(int x, int n) {
  int t0=0, t1=1, t2;
  int r0,r1,r2,q;

  // Sets up the first three remainders and the quotient in Euclid's algorithm.
  r0 = n;
  r1 = x;
  r2 = n%x;
  q = n/x;

  // Set's up doing the equation backwards for the inverse solution.
  // The 100*26 is to ensure that t2 stays positive.
  t2 = (t0 - q*t1 + 100*26) % 26;
  if (r1 == 1)
    t2 = 1;

  // Stops when repeated division finally yields no remainder, as in Euclid's.
  while (r2!=0) {
    
    // Carries out division
    int temp = r2;
    q = r1/r2;
    r2 = r1 - q*r2;
    r1 = temp;

    // Carries out next step working the equations "backwards"
    if (r2!= 0) {
      int temp2 = t2;
      t2 = (t1 - q*t2 + 100*26) % 26;
      t1 = temp2;
    }
  }
  
  // Based on whether an inverse exists, either a positive value (the inverse)
  // is returned or the -gcd(x,n) is returned.
  if (r1 == 1)
    return t2;
  else
    return -r1;
  
}