Click here to download p4/rsa.cpp.

/* SI 335 Spring 2012
 * Project 4, RSA program
 * YOUR NAME HERE
 */

#include <iostream>
#include <string>
#include <sstream>
#include <cstdlib>

#include "posint.hpp"

using namespace std;

// Prints a message on proper usage and exits with the given code
void usage (const char* progname, int ret);

// Function prototype. You have to fill in the implementation below.
void powmod (PosInt& result, const PosInt& a, const PosInt& b, const PosInt& n);

int main (int argc, char** argv) {
  // Seed the random number generator
  srand (time(NULL));

  // Pick the base to use in the PosInt class
  PosInt::setBase (10);

  if (argc < 2 || argv[1][0] != '-') usage(argv[0],1);
  if (argv[1][1] == 'k') {
    ////////////////////////////////////////////////////////////////////
    //                 KEY GENERATION                                 //
    ////////////////////////////////////////////////////////////////////
    if (argc != 2) usage(argv[0],3);
    
    // These are just "dummy" values! Replace with your actual code
    PosInt n (11);
    PosInt e (5);
    PosInt d (9);

    // Print out the public key and private key
    cout << e << ' ' << n << endl;
    cout << d << ' ' << n << endl;
  }
  else if (argv[1][1] == 'e') {
    ////////////////////////////////////////////////////////////////////
    //                  ENCRYPTION WITH PUBLIC KEY                    //
    ////////////////////////////////////////////////////////////////////
    if (argc != 4) usage(argv[0],3);

    // Get public key from command-line arguments
    PosInt e (argv[2]);
    PosInt n (argv[3]);

    // Read characters from standard in and encrypt them
    int c;
    PosInt M (0); // Initialize M to zero
    int twoFiftySixCubed = 256 << 16; // = 256^3
    PosInt twoFiftySix (256);
    PosInt power (twoFiftySixCubed);
    
    bool keepGoing = true;
    while (keepGoing) {
      c = cin.get();

      if (c == '\n') keepGoing = false;
      else {
        PosInt next (c); // next character, converted to a PosInt
        next.mul(power); // next *= power
        M.add(next);     // M = M + next
        power.div(twoFiftySix);
      }

      if (power.isZero() || !keepGoing) {
        // HERE'S WHERE YOU HAVE TO DO THE ENCRYPTION!
        PosInt C (M); // THIS IS JUST A "DUMMY" VALUE
        cout << C << ' ';

        // Now reset power and M and keep going
        power.set(twoFiftySixCubed);
        M.set(0);
      }
    }
    cout << endl;
  }
  else if (argv[1][1] == 'd') {
    ////////////////////////////////////////////////////////////////////
    //                 DECRYPTION WITH PRIVATE KEY                    //
    ////////////////////////////////////////////////////////////////////
    if (argc != 4) usage(argv[0],3);

    // Get private key from command-line arguments
    PosInt d (argv[2]);
    PosInt n (argv[3]);
    PosInt C;

    // Put the line of encoded numbers into a stringstream for reading
    string line;
    getline (cin, line);
    istringstream iss (line);

    while (iss >> C) {
      // You have to decrypt C and print out the four characters
      // Note: use the "convert" function to turn a PosInt into
      // a regular "int".
      cout << "abcd"; // THIS IS JUST A DUMMY!
    }
    cout << endl;
  }
  else if (argv[1][1] == 'h') usage(argv[0], 0);
  else usage(argv[0],2);
  return 0;
}

////////////////////////////////////////////////////////////
//              MODULAR EXPONENTIATION                    //
////////////////////////////////////////////////////////////

// Computes a^b mod n, and stores the answer in "result".
void powmod (PosInt& result, const PosInt& a, const PosInt& b, const PosInt& n) {
  // YOU HAVE TO FILL THIS IN!
}


////////////////////////////////////////////////////////////
//              KARATSUBA MULTIPLICATION                  //
////////////////////////////////////////////////////////////

// Computes x * y, and stores the result in "this" PosInt object.
PosInt& PosInt::fasterMul (const PosInt& x, const PosInt& y) {
  // This is a suggestion of how to do this one:

  // First figure out the larger of the two input sizes
  int n = x.digits.size();
  if (n < y.digits.size()) n = y.digits.size();
  
  // Now copy the inputs into arrays of that size, with zero-padding
  int* xcopy = new int[n];
  int* ycopy = new int[n];
  for (int i=0; i<n; ++i) {
    xcopy[i] = 0;
    ycopy[i] = 0;
  }
  for (int i=0; i<x.digits.size(); ++i)
    xcopy[i] = x.digits[i];
  for (int i=0; i<y.digits.size(); ++i)
    ycopy[i] = y.digits[i];

  // Set "this" digit vector to a zeroed-vector of size 2n
  digits.assign (2*n, 0);

  // Now call the array version to do the actual multiplication
  fastMulArray (&digits[0], xcopy, ycopy, n);

  // We have to call normalize in case there are leading zeros
  normalize();

  // And we don't want memory leaks do we?
  delete [] xcopy;
  delete [] ycopy;

  // Finally return a reference to "this" PosInt
  return *this;
}

// This does the real work of Karatsuba's algorithm
// (or whatever multiplication algorithm you might write).
// The input is two arrays of digits, x and y, which both have length len.
// The output is stored in the array dest, which is already allocated
// to the proper length.
void PosInt::fastMulArray (int* dest, const int* x, const int* y, int len) {
  // Again, this is just a suggested general outline...
  if (len == 1) {
    // base case
    // YOU FILL THIS IN
  }
  else {
    // recursive case
    // YOU FILL THIS IN TOO.
    // Hint: you will have to allocate some memory for U, V, P0, P1, and P2
    // Another hint: use the addArray and subArray helper methods from the
    // PosInt class!
  }
}


// Prints a message on proper usage and exits with the given code
void usage (const char* progname, int ret) {
  cout
    << "Generate a public-private key pair:" << endl
    << "\t" << progname << " -k" << endl
    << "Encrypt a message with public key:" << endl
    << "\t" << progname << " -e <e> <n>" << endl
    << "Decrypt a message with private key:" << endl
    << "\t" << progname << " -d <d> <n>" << endl;
  exit(ret);
}