rsakey.cpp

flint库 RSA算法

//*****************************************************************************/
//                                                                            */
// Software supplement to the book "Cryptography in C and C++"                */
// by Michael Welschenbach                                                    */
//                                                                            */
// Module rsakey.cpp       Revision: 19.04.2005                               */
//                                                                            */
//  Copyright (C) 1998-2005 by Michael Welschenbach                           */
//  Copyright (C) 1998-2005 by Springer-Verlag Berlin, Heidelberg             */
//  Copyright (C) 2001-2005 by Apress L.P., Berkeley, CA                      */
//  Copyright (C) 2002-2005 by Wydawnictwa MIKOM, Poland                      */
//  Copyright (C) 2002-2005 by PHEI, P.R.China                                */
//  Copyright (C) 2002-2005 by InfoBook, Korea                                */
//  Copyright (C) 2002-2005 by Triumph Publishing, Russia                     */
//                                                                            */
//  All Rights Reserved                                                       */
//                                                                            */
//  The software may be used for noncommercial purposes and may be altered,   */
//  as long as the following conditions are accepted without any              */
//  qualification:                                                            */
//                                                                            */
//  (1) All changes to the sources must be identified in such a way that the  */
//      changed software cannot be misinterpreted as the original software.   */
//                                                                            */
//  (2) The statements of copyright may not be removed or altered.            */
//                                                                            */
//  (3) The following DISCLAIMER is accepted:                                 */
//                                                                            */
//  DISCLAIMER:                                                               */
//                                                                            */
//  There is no warranty for the software contained in this distribution, to  */
//  the extent permitted by applicable law. The copyright holders provide the */
//  software `as is' without warranty of any kind, either expressed or        */
//  implied, including, but not limited to, the implied warranty of fitness   */
//  for a particular purpose. The entire risk as to the quality and           */
//  performance of the program is with you.                                   */
//                                                                            */
//  In no event unless required by applicable law or agreed to in writing     */
//  will the copyright holders, or any of the individual authors named in     */
//  the source files, be liable to you for damages, including any general,    */
//  special, incidental or consequential damages arising out of any use of    */
//  the software or out of inability to use the software (including but not   */
//  limited to any financial losses, loss of data or data being rendered      */
//  inaccurate or losses sustained by you or by third parties as a result of  */
//  a failure of the software to operate with any other programs), even if    */
//  such holder or other party has been advised of the possibility of such    */
//  damages.                                                                  */
//                                                                            */
//*****************************************************************************/

#include <stdlib.h>
#include <string.h>
#include "rsakey.h"

#ifdef FLINT_TEST
static void cout_mess (const char*, int, const char*);
#endif


// Member functions of class RSAkey

// Constructor 1
RSAkey::RSAkey (int bitlen)
{
  STATEPRNG xrstate;
  int done;
  InitRand (xrstate, "", 0, 200, FLINT_RNDRMDSHA1);

  do
    {
      done = RSAkey::makekey (bitlen, xrstate);
    }
  while (!done);

  PurgeRand (xrstate);
}


// Constructor 2 with optional public exponent PubExp.
// The constructor generates RSA keys of distinct binary length and optional
// given public exponent (must be odd). In case that PubExp == 1 or omitted, 
// a random exponent is created. If the given exponent is even, an error 
// condition is generated, that can be handled by try() and catch() if 
// exceptions are enabled.

RSAkey::RSAkey (int bitlen, STATEPRNG& xrstate, const LINT& PubExp)
{
  int done;

  do
    {
      done = RSAkey::makekey (bitlen, xrstate, PubExp);
    }
  while (!done);
}


// Export public key
PKEYSTRUCT RSAkey::export_public (void) const
{
  PKEYSTRUCT pktmp;

  pktmp.pubexp = key.pubexp;
  pktmp.mod = key.mod;
  pktmp.bitlen_mod = key.bitlen_mod;
  pktmp.bytelen_mod = key.bytelen_mod;

  return pktmp;
}


// Decryption
UCHAR* RSAkey::decrypt (const LINT& Ciph, int* LenEB)
{
  UCHAR* EB = lint2byte (fastdecrypt (Ciph), LenEB);
  UCHAR* Mess = NULL;

#ifdef FLINT_TEST
  cout_mess ((const char*)EB, key.bytelen_mod - 1, "Encryption Block after decryption");
#endif

  // Parsing decrypted Encryption Block, PKCS#1-formatted
  if (2 != parse_pkcs1 (Mess, LenEB, EB, key.bytelen_mod)) 
    {
      return (UCHAR*)NULL; // False block type or format of encryption block    
    }
  else
    {
      return Mess; // Return pointer to decrypted message
    }
}


// Sign
// Returns 0 if message too long
LINT RSAkey::sign (const UCHAR* Mess, int LenMess)
{

  STATEPRNG junk;

#ifdef FLINT_TEST
  cout << "Length of modulus = " << key.bytelen_mod << " byte." << endl;
#endif
  int LenEncryptionBlock = key.bytelen_mod;
  UCHAR HashRes[RMDVER>>3];
  UCHAR* EncryptionBlock = new UCHAR[LenEncryptionBlock];

  sha1_l (HashRes, (UCHAR*)Mess, (ULONG)LenMess);
  if (NULL == format_pkcs1 (EncryptionBlock, LenEncryptionBlock,
                            BLOCKTYPE_SIGN, HashRes, RMDVER >> 3, junk))
    {
      delete [] EncryptionBlock;
      return LINT (0);             // Error: Message too long
    }

#ifdef FLINT_TEST
  cout_mess ((const char*)EncryptionBlock, LenEncryptionBlock, "Encryption Block");
#endif

  // Convert Encryption Block into LINT value (Constructor 3)
  LINT m = LINT (EncryptionBlock, LenEncryptionBlock);
  delete [] EncryptionBlock;

  return fastdecrypt (m);
}


// Key deletion
void RSAkey::purge (void)
{
  key.pubexp.purge ();
  key.prvexp.purge ();
  key.mod.purge ();
  key.p.purge ();
  key.q.purge ();
  key.ep.purge ();
  key.eq.purge ();
  key.r.purge ();
  key.bitlen_mod = 0;
  key.bytelen_mod = 0;
}



// RSAkey auxiliary functions


// Generation of RSA keys acc. to IEEE P1363, Annex A.
// A public exponent may be given in PubExp. If PubExp is omitted or
// PubExp == 1 a public exponent of half the modulus length
// is choosen at random.

int RSAkey::makekey (int length, STATEPRNG& xrstate, const LINT& PubExp)
{
  // Generate prime p
  // 2^(m - r - 1) <= p < 2^(m - r), with
  // m = floor((length + 1)/2) and r randomly chosen from intervall 2 <= r < 15
  const USHORT m = (((const USHORT)length + 1) >> 1) - 2 - sRand_l (&xrstate) % 13;

  key.p = FindPrime (m, PubExp, xrstate);

  // Determine intervall qmin and qmax for prime q
  // Set qmin = floor ((2^(length - 1))/p + 1)
  LINT qmin = LINT(0).setbit (length - 1)/key.p + 1;
  // Set qmax = floor ((2^length - 1)/p)
  LINT qmax = (((LINT(0).setbit (length - 1) - 1) << 1) + 1)/key.p; 

  // Generate prime q > p
  // qmin <= q <= qmax
  key.q = FindPrime (qmin, qmax, PubExp, xrstate);

  // Generate modulus p*q
  // 2^(length - 1) <= p*q < 2^length
  key.mod = key.p * key.q;

  // Calculate Euler's Phi-function
  LINT phi_n = key.mod - key.p - key.q + 1;

  // Generate public key, if not defined in PubExp, of half the number of 
  // the modulus digits
  if (1 == PubExp)
    {
      key.pubexp = RandLINT (length/2, xrstate) | 1; 
      while (gcd (key.pubexp, phi_n) != 1)
        {
          ++key.pubexp;
          ++key.pubexp;
        }
    }
  else
    {
      key.pubexp = PubExp;
    }

  // Generate secret key
  key.prvexp = key.pubexp.inv (phi_n);

  // Generate secret key components for fast decryption
  // acc. to Chinese Remainder Theorem
  key.ep = key.prvexp % (key.p - 1);
  key.eq = key.prvexp % (key.q - 1);
  key.r = inv (key.p, key.q);     // r = p^(-1) mod q, as an alternative 
                                  // r = q^(-1) mod p is possible

  // Store keylength
  key.bitlen_mod = ld (key.mod);
  key.bytelen_mod = key.bitlen_mod >> 3;
  if ((key.bitlen_mod % 8) > 0)
    {
      ++key.bytelen_mod;
    }

#ifdef FLINT_TEST
  cout << "Modulus = " << key.mod << endl;
  cout << "Public exponent e = " << key.pubexp << endl;
  cout << "Private exponent d = " << key.prvexp << endl;
  cout << "p = " << key.p << endl;
  cout << "q = " << key.q << endl;
  cout << "d mod p-1 = " << key.ep << endl;
  cout << "d mod q-1 = " << key.eq << endl;
  cout << "Inverse of p mod q = " << key.r << endl;
#endif // FLINT_TEST

  return testkey (xrstate);
}


// Test keys
int RSAkey::testkey (STATEPRNG& xrstate)
{
  LINT mess = RandLINT (ld (key.mod) >> 1, xrstate);
  return (mess == fastdecrypt (mexpkm (mess, key.pubexp, key.mod)));
}


// Fast RSA-decryption acc. to Chinese Remainder Theorem (CRT)
LINT RSAkey::fastdecrypt (const LINT& mess)
{
  LINT m, w;                           // If alternative CRT key component
  m = mexpkm (mess, key.ep, key.p);    // r = q^(-1) mod p 
  w = mexpkm (mess, key.eq, key.q);    // is in use:
  w.msub (m, key.q);                   // m.msub (w, key.p);
  w = w.mmul (key.r, key.q) * key.p;   // m = m.mmul (key.r, key.p) * key.q;
  return (w + m);
}


// Operators =, ==, != in class RSAkey

RSAkey& RSAkey::operator= (const RSAkey &k)
{
  if ((&k != this)) // Don't copy object into itself
    {
      key.pubexp      = k.key.pubexp;
      key.prvexp      = k.key.prvexp;
      key.mod         = k.key.mod;
      key.p           = k.key.p;
      key.q           = k.key.q;
      key.ep          = k.key.ep;
      key.eq          = k.key.eq;
      key.r           = k.key.r;
      key.bitlen_mod  = k.key.bitlen_mod;
      key.bytelen_mod = k.key.bytelen_mod;
    }
  return *this;
}


int operator== (const RSAkey& k1, const RSAkey& k2)
{
  if (&k1 == &k2)       //lint !e506
    {
      return 1;
    }

  return (k1.key.pubexp      == k2.key.pubexp      &&
          k1.key.prvexp      == k2.key.prvexp      &&
          k1.key.mod         == k2.key.mod         &&
          k1.key.p           == k2.key.p           &&
          k1.key.q           == k2.key.q           &&
          k1.key.ep          == k2.key.ep          &&
          k1.key.eq          == k2.key.eq          &&
          k1.key.r           == k2.key.r           &&
          k1.key.bitlen_mod  == k2.key.bitlen_mod  &&
          k1.key.bytelen_mod == k2.key.bytelen_mod);

  // Operator == returns 1 if k1 == k2, 0 else
}


int operator!= (const RSAkey& k1, const RSAkey& k2)
{
  if (&k1 == &k2)       //lint !e506
    {
      return 0;
    }

  return (k1.key.pubexp      != k2.key.pubexp      ||
          k1.key.prvexp      != k2.key.prvexp      ||
          k1.key.mod         != k2.key.mod         ||
          k1.key.p           != k2.key.p           ||
          k1.key.q           != k2.key.q           ||