bmrsa.cpp

rsa realisation in c++ language

// bmrsa.cpp : Defines the entry point for the console application.
//

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <time.h>
#include "bignum.h"

#define MAXPRIMECOUNT 1000

unsigned int nSmallPrimes[MAXPRIMECOUNT][2];
unsigned int nPrimeCount = 0;

void MakeSmallPrimes()
{
   unsigned int n;
   unsigned int j;

   nPrimeCount = 3;
   nSmallPrimes[0][0] = 2;
   nSmallPrimes[1][0] = 3;
   nSmallPrimes[2][0] = 5;
   nSmallPrimes[0][1] = 4;
   nSmallPrimes[1][1] = 9;
   nSmallPrimes[2][1] = 25;

   for (n=7; nPrimeCount < MAXPRIMECOUNT; n+=2)
   {
      for (j=0; nSmallPrimes[j][1] < n; j++)
      {
         if (j>= nPrimeCount)
         {
            puts("error");
            return;
         }
         if (n % nSmallPrimes[j][0]==0)
         {
            break;
         }
      }
      if (nSmallPrimes[j][1] > n)
      {
         nSmallPrimes[nPrimeCount][0] = n;
         nSmallPrimes[nPrimeCount++][1] = n*n;
      }
   }
}

CBigNum GenerateBigRandomNumber(unsigned short nBytes)
{
   CBigNum Result=0U;
   int i;
   clock_t ctStart;
   unsigned long ctr=0;
   clock_t ctInterval = CLOCKS_PER_SEC / 50 + 1;

   puts("Generating random number:");

   for (i=0; i<nBytes*2; i++)
   {
      ctStart = clock();
      while (clock() - ctStart < ctInterval)
         ctr++;

      ctr = (ctr % 33) & 0xF;
      printf("%X", ctr);
      Result <<= 4U;
      Result |= ctr;
   }
   putchar('\n');
   return Result;
}

CBigNum FindABigPrime(unsigned short nBytes)
{
   CBigNum nBig, nBig2;
   DWORD j;
   //nBig = "294409"; // Carmichael number
   //nBig = "63973"; // Carmichael number
   DWORD nTestCount = 0;
   DWORD nLehmanCount = 0;
   clock_t ctStartTime = clock();
   DWORD nOffset=0;

   bool bPrime=false;

   for (nBig = GenerateBigRandomNumber(nBytes) | 1U; !bPrime; nBig+=2U, nOffset+=2)
   {
      nTestCount++;
      puts("Testing for prime:");
      if (nOffset==0)
      {
         puts(nBig);
      }
      else
      {
         printf("+%d\n", nOffset);
      }

      for (j=0; j<nPrimeCount; j++)
      {
         if (nBig <= nSmallPrimes[j][0])
            break;

         if (nBig % nSmallPrimes[j][0] == 0)
         {
            printf("It's evenly divisible by %d\n", nSmallPrimes[j][0]);
            break;
         }
      }
      
      if ((j<nPrimeCount) && (nBig > nSmallPrimes[j][0]))
         continue;

      puts("No small prime factors; trying Lehman method");

      nLehmanCount++;

      nBig2 = (nBig - 1U) / 2U;

      DWORD arnLehmanPrimes[] = { 89, 5179, 25981, 25439, 25013, 25667, 27397 }; // some random prime numbers
      CBigNum LehmanResults[sizeof(arnLehmanPrimes) / sizeof(arnLehmanPrimes[0])];

      nBig2 = nBig - 1U;

      bPrime = true;
      for (j=0; j<sizeof(arnLehmanPrimes) / sizeof(arnLehmanPrimes[0]); j++)
      {
         LehmanResults[j] = CBigNum(arnLehmanPrimes[j]).PowMod(nBig2, nBig, CLOCKS_PER_SEC);
         if (LehmanResults[j] == nBig2)
         {
            printf("Lehman result %d suggests prime (-1)\n", j);
         }
         else if (LehmanResults[j] == 1U)
         {
            printf("Lehman result %d suggests prime (1)\n", j);
         }
         else
         {
            printf("Lehman result %d indicates composite\n", j);
            bPrime = false;
            break;
         }
      }

      if (bPrime)
      {
         puts(nBig);
         puts("Appears prime");
         break;
      }
   }
   printf("Tested %d numbers before finding a prime. Resorted to Lehman method %d times.\n", nTestCount, nLehmanCount);
   printf("Process took %6.1f seconds.\n", (clock()-ctStartTime)/(float)(CLOCKS_PER_SEC));
   
   return nBig;
}

void GenKeyPair(CBigNum &PublicMod, CBigNum &PublicKey, CBigNum &PrivateKey, CBigNum &P, CBigNum &Q, unsigned int nByteCount = 32)
{
   if (0U==(P | Q))
   {
      P=FindABigPrime(nByteCount);
      Q=FindABigPrime(nByteCount);
      PublicKey=GenerateBigRandomNumber(nByteCount) | 1U;
   } else {
      PublicKey |= 1U;
   }
   PrivateKey = (P-1U) * (Q-1U);
   while (PublicKey > PrivateKey)
      PublicKey=GenerateBigRandomNumber(nByteCount-1) | 1U;
   while(CBigNum::gcd(PublicKey,PrivateKey) != 1U)
      PublicKey+=2;
   PrivateKey = PublicKey.Inverse(PrivateKey);

   PublicMod = P*Q;
}

int main(int argc, char* argv[])
{

   bool bAbort = false;
   unsigned short nBytes=0; // Key byte-length
   int nCommand=0;   // 1 = Generate key
                     // 2 = Transform input with public key
                     // 3 = Transform input with private key
                     // 4 = Convert input to another text format
                     // 5 = Regenerate private key
   int nMode=0;      // 0 = Expect switch
                     // 1 = Expect key byte-length
                     // 2 = Expect key file name
   char szKeyFile[512];
   int nTextModeI=3; // Encrypted Text Mode  0 = Decimal, 1 = Hex, 2 = Printable text, 3=base64
   int nTextModeO=3; // Decrypted Text Mode  0 = Decimal, 1 = Hex, 2 = Printable text, 3=base64
   int nTextModeK=3; // Key text mode  0 = Decimal, 1 = Hex, 2 = Printable text, 3 = base64
   unsigned int nWid=5;

   szKeyFile[0] = '\0';

   if (argc < 2)
   {
      bAbort = true;
   }
   else
   {
      int nArg;

      for (nArg=1; nArg<argc; nArg++)
      {
         switch (argv[nArg][0])
         {
         case '-':
         case '/':
            switch(argv[nArg][1])
            {
            case 'g':
            case 'G': // Generate key of length <arg>
               nCommand = 1;
               if (argv[nArg][2])
               {
                  nBytes = atoi(argv[nArg]+2);
                  nCommand = 1;
               }
               else
                  nMode = 1;
               break;
            case 'f':
            case 'F': // key filename
               if (argv[nArg][2])
                  strcpy(szKeyFile, argv[nArg]+2);
               else
                  nMode = 2;
               break;
            case 'p':
            case 'P':
               switch(argv[nArg][2])
               {
               case 'u': // Transform through [Pu]blic key
               case 'U':
                  nCommand = 2;
                  break;
               case 'r': // Transform through [Pr]ivate key
               case 'R':
                  nCommand = 3;
                  break;
               }
               break;
            case 'c':
            case 'C':
               nCommand = 4;
               break;
            case 'r':
            case 'R':
               nCommand = 5;
               break;
            case 'm':
            case 'M': // Mode switch
               switch(argv[nArg][2])
               {
               case 'i':
               case 'I':
                  switch(argv[nArg][3])
                  {
                  case 'd':
                  case 'D':
                     nTextModeI = 0;
                     break;
                  case 'h':
                  case 'H':
                     nTextModeI = 1;
                     break;
                  case 't':
                  case 'T':
                     nTextModeI = 2;
                     break;
                  case '6':
                     nTextModeI = 3;
                     break;
                  }
                  break;
               case 'k':
               case 'K':
                  switch(argv[nArg][3])
                  {
                  case 'd':
                  case 'D':
                     nTextModeK = 0;
                     break;
                  case 'h':
                  case 'H':
                     nTextModeK = 1;
                     break;
                  case 't':
                  case 'T':
                     nTextModeK = 2;
                     break;
                  case '6':
                     nTextModeK = 3;
                     break;
                  }
                  break;
               case 'o':
               case 'O':
               case '0':
                  switch(argv[nArg][3])
                  {
                  case 'd':
                  case 'D':
                     nTextModeO = 0;
                     break;
                  case 'h':
                  case 'H':
                     nTextModeO = 1;
                     break;
                  case 't':
                  case 'T':
                     nTextModeO = 2;
                     break;
                  case '6':
                     nTextModeO = 3;
                     break;
                  }
                  break;
               }
               break;
            default:
               bAbort=true;
               break;
            }
            break;
         default:
            switch(nMode)
            {
            case 1:
               nBytes = atoi(argv[nArg]);
               nMode = 0;
               break;
            case 2:
               strcpy(szKeyFile, argv[nArg]);
               nMode = 0;
               break;
            default:
               bAbort = true;
               break;
            }
         }
      }
   }

   if (nCommand == 0)
   {
      bAbort = true;
   }

   if (((nCommand == 2) || (nCommand == 3) || (nCommand == 5)) && (szKeyFile[0] == '\0'))
   {
      puts("Key file name required.");
      bAbort = true;
   }

   if (bAbort)
   {
      puts  ("RSA Encryption, Decryption, Signing and Key Generation Tool\nWritten by Benjamin Marty ([e-mail])\n"
             "Syntax 1 (generate a key file):\n"
             "   bmrsa [<mode switches>] -g [<byte count>] [-f <key file>]\n"
             "Syntax 2 (tranform text or regenerate private key):\n"
             "   bmrsa [<mode switches>] -f <key file> <command>\n"
             "Syntax 3 (convert text):\n"
             "   bmrsa [<mode switches>] -c\n"
             " <mode switches>: -m<text spec><text mode>\n"
             "     <text spec>: k|i|o\n"
             "                  where k = text of keys in <key file>\n"
             "                        i = text in input stream\n"
             "                        o = text in output stream\n"
             "     <text mode>: d|h|t|6\n"
             "                  where d = decimal\n"
             "                        h = hexadecimal\n"
             "                        t = bytes as printable text (careful here!)\n"
             "              (default) 6 = base64 encoding (no line breaks)\n"
             "     Printable text mode replaces non-printable characters with\n"
             "     periods, so it should only be used on data that is expected\n"
             "     to be printable, and definitely not on a key, which would\n"
             "     almost certainly be corrupted as plain text.\n"
             " <byte count>   : (A decimal number from 4 to 128)\n"
             "                  The byte count determines the number of bytes\n"
             "                  in each prime number that compose the public mod.\n"
             "                  A value of 8 will generate 2 64-bit primes and\n"
             "                  result in a 128-bit public mod and private key.\n"
             "                  (default=32 which gives 512-bit mod)\n"
             " <command>      : -pu[blic] | -pr[ivate] | -r[egen]\n"
             "                  -pu: Transforms the input stream using the\n"
             "                       specified input text mode and the public key\n"
             "                       in the key file, then outputs it to the\n"
             "                       output stream according to the output mode\n"