/**
  @title: rsa.cpp
  @date: 2004.11.25 - 21:55
  @author: vinnie
  @source for rsa.exe
*/

#include <conio.h>
#include <ctype.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string>

using namespace std;
///////////////////////////////////////////////////////////////////////////

int cal_mod( int data, int power, int mod_num)
{
  int result = 1;
  for( int i = 1; i <= power; i++)
  {
    result = ( result * data) % mod_num;
    if ( result < 0 )
      break;
  }
  return result;
}
///////////////////////////////////////////////////////////////////////////

int mod_exp( int base, int expon, int modu)
{
  int result = 1;

  while ( expon > 0 )
  {
    if ( expon & 1 > 0 )
      result = ( result * base ) % modu;
    expon >>= 1;
    base = (base * base) % modu;
  }
  return result;
}
///////////////////////////////////////////////////////////////////////////

void extended_Euclid( long a, long b, long *u, long *v, long *d)
{
  long q, t1, t3, v1, v3;

  *u = 1, *d = a;
  if (b == 0)
  {
    *v = 0;
    return;
  }

  v1 = 0, v3 = b;
  while (v3 != 0)
  {
    q = *d / v3;
    t3 = *d - q * v3;
    t1 = *u - q * v1;
    *u = v1, *d = v3;
    v1 = t1, v3 = t3;
  }
  *v = (*d - a * *u) / b;
}
///////////////////////////////////////////////////////////////////////////

long inverse( long a, long b)
{
  long d, u, v;
  extended_Euclid( a, b, &u, &v, &d);
  if (d == 1) return u;
  return 0;
}
///////////////////////////////////////////////////////////////////////////

void main()
{
  int   pP, qP, eXp;
  int   iPairItems, iStrLen;
  char  userStr[65];
  char  bump[5];
  char  c;
  bool  evenLenStr;

  //   code
  system( "color 1f" );

  // menu' label
  MYMENU: //  begin

  //  reset vars
  iStrLen  = iPairItems = 0;
  memset( userStr, '\0', 65 );

  //  print intro & menu
  system( "cls" );
  printf( "\t\t   SLCC - CS 2310-01 - Fall '04 - RSA Enc/Dec\n" );
  printf( "\n Encryption/Decryption of a string using the RSA method.\n" );
  printf( "\n Input the 1st prime number, p = ");
  gets( userStr );
  pP = atoi( userStr);

  printf( " Input the 2nd prime number, q = ");
  gets( userStr );
  qP = atoi( userStr);

  printf( " Input the exponent number, exp = ");
  gets( userStr );
  eXp = atoi( userStr);

  printf( " Now input your string [NO spaces]: " );
  gets( userStr );
///////////////////////////////////////////////////////////////////////////

  iStrLen = strlen( userStr );
  for ( int i = 0; i < iStrLen; i++ )
    userStr[i] = toupper( userStr[i] );

  //  determine if the string lenght is odd or even
  if ( iStrLen % 2 )
    evenLenStr = false;
  else
    evenLenStr = true;
  iPairItems = iStrLen / 2;
  if ( !evenLenStr ) ++iPairItems;
///////////////////////////////////////////////////////////////////////////

  //  couple the chars
  int iLimit;
  if ( evenLenStr )
    iLimit = iStrLen;
  else
    iLimit = iStrLen - 1;

  //  an array of integers to store the pairs
  int* iCouples = new int[iPairItems];

  int i, j;
  //  minus 65 ASCII positions
  for ( i = 0, j = 0; i < iLimit; i += 2, j++ )
    iCouples[j] = (*( userStr + i) - 65) * 100 + *(userStr + i + 1 ) - 65;
  if ( !evenLenStr )
    iCouples[j] = (*( userStr + i) - 65) * 100;
///////////////////////////////////////////////////////////////////////////

  //  encrypt
  int   prod1   = pP * qP;
  int*  iResult = new int[iPairItems];
  for ( i = 0; i < iPairItems; i++)
    iResult[i] = (int) mod_exp( iCouples[i], eXp, prod1);

///////////////////////////////////////////////////////////////////////////

  //  decrypt
  int      prod2 = (pP-1) * (qP-1);
  int*     iDest = new int[iPairItems];

  int  iInv = inverse( eXp, prod2 );

  for ( i = 0; i < iPairItems; i++)
    iDest[i] = cal_mod( iResult[i], iInv, prod1);
///////////////////////////////////////////////////////////////////////////

  printf( "\n The two prime numbers used are p = %d and q = %d, \
with exp = %d.\n", pP, qP, eXp );

  gotoxy( 1, 12);
  printf("Char.s  Integers  Encrypted  Inverse Decrypted  Char.s ");
  for ( int i = 0; i < iPairItems; i++)
  {
    int j = 0;
    if ( i ) j = i * 2;
    gotoxy(  2, 14 + i); printf( " %c%c", userStr[j], userStr[j+1] );
    gotoxy(  9, 14 + i); printf( "%d",   iCouples[i] );
    gotoxy( 19, 14 + i); printf( "%d",   iResult[i] );
    gotoxy( 30, 14 + i); printf( "%d",   iInv );
    gotoxy( 38, 14 + i); printf( "%d", iDest[i] );
    gotoxy( 49, 14 + i); printf( "%c%c\n", (iDest[i]-(iDest[i] % 100))/100 \
                                 + 65, (iDest[i] % 100) + 65 );
  }
///////////////////////////////////////////////////////////////////////////

  //  destructors
  delete [] iCouples;
  delete [] iResult;
  delete [] iDest;
///////////////////////////////////////////////////////////////////////////

  //  ask for an other trip
  printf( "\n Another one [Y/y/N/n]? " );
  while ( !kbhit() );
  c = getchar();
  if ( c == 'Y' || c == 'y' ) goto MYMENU;
///////////////////////////////////////////////////////////////////////////

  printf( "\n Thanks for using RSA\n" );
  printf( " Vincenzo Maggio Code - released under GPL\n" );
  system( "color 0f" );
}