Assignment for Discrete Math class, short for Discrete Structures.
This has been the toughest program I ever wrote.
Assignment was to implement the RSA algorithm, that deals with large prime numbers. However we were told to test with small primes like 37 or 41 to be raised at small power like 13, 17 or 19.
So first problem has been a buffer overflow. Consequence was to write the cal_mod() function.
Second problem is that some time the algorithm doesn't work, when we decrypt back and the encrypted number doesn't have a inverse, or the inverse is negative.
However the code needs some cleaning.
Download the executable: rsa.exe

---

November 25, 2004

RSA Encryption / Decryption

/**
  @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" );
}

---

2004.11.25

Vincenzo Maggio