16.4 RSA Classes in C

Team-Fly

16.4 RSA Classes in C++

In this section we develop a C++ class RSAkey that contains the functions

  • RSAkey::RSAkey() for RSA key generation;

  • RSAkey::export() for exporting public keys;

  • RSAkey::decrypt() for decryption;

  • RSAkey::sign() for digital signing using the hash function RIPEMD-160;

as well as a class RSApub for the storage and application of public keys only with the functions

  • RSApub::RSApub() for importing a public key from an object of the class RSAkey;

  • RSApub::crypt() for encrypting a text;

  • RSApub::authenticate() for authenticating a digital signature.

The idea is not merely to look at cryptographic keys as numbers with particular cryptographic properties, but to consider them as objects that bring with themselves the methods for their application and make them available to the outside world but that nonetheless restrictively prevent unmediated access to private key data. Objects of the class RSAkey thus contain, after the generation of a key, a public and a private RSA key component as private elements, as well as the public functions for encryption and signing. Alternatively, the constructor functions enable the generation of keys

  • with fixed length and internal initialization of the BBS random number generator;

  • with adjustable length and internal initialization of the BBS random number generator;

  • with adjustable length and passing of a LINT initialization value for the BBS random number generator via the calling program.

Objects of the class RSApub contain only the public key, which they must import from an RSAkey object, and the public functions for encryption and verification of a signature. To generate an object of the RSApub class, then, an initialized RSAkey object must already exist. In contrast to objects of type RSAkey, RSApub objects are considered unreliable and can be more freely handled than RSAkey objects, which in serious applications may be transmitted or stored in data media only in encrypted form or protected by special hardware measures.

Before we realize these example classes we would like to set ourselves some boundary conditions that will limit the implementation cost at something appropriate for what is merely an example: For the sake of simplicity, input values for RSA encryption will be accepted only if they are smaller than the modulus; a subdivision of longer texts into blocks will not occur. Furthermore, we shall leave aside the more costly functional and security-related features that would be necessary in a full-fledged implementation of the RSA classes (see in this regard the pointer on page 323).

However, we do not wish to do without an effective possibility of speeding up the calculations for decryption or signing. By application of the Chinese remainder theorem (see page 199) the RSA operations with the secret key d can be made about four times as fast as with the usual method of calculating a single power: Given a secret key <d, n> with n = pq we form dp := d mod (p 1) and dq := d mod (q 1) and employ the extended Euclidean algorithm to compute the representation 1 = rp + sq, from which we extract the value r as the multiplicative inverse of p modulo q (cf. Section 10.2). We then employ the components p, q, dp, dq, r to calculate c = md mod n as follows:

  1. Calculate a1 mod p and a2 mod q.

  2. Calculate c a1 + p ((a2 a1) r mod q).

After step 1 we have a1 md mod p and a2 md mod q. To see this, just use the little theorem of Fermat (cf. page 175), according to which mp1 1 mod p, respectively mq1 1 mod q. From d = (p 1) + dp with integral it follows that

(16.9) click to expand

and analogously, we have the same for md mod q. An application of the Garner algorithm (see page 203) with m1 := p, m2 := q, and r := 2 shows us at once that c in step 2 represents the desired solution. Rapid decryption is implemented in the auxiliary function RSAkey::fastdecrypt(). All exponents modulo p, q, or n are calculated via Montgomery exponentiation with the LINT function LINT::mexpkm () (cf. page 282).

   // Selection from the include file rsakey.h    ...   #include "flintpp.h"   #include "ripemd.h"   #define BLOCKTYPE_SIGN 01   #define BLOCKTYPE_ENCR 02   // The RSA key structure with all key components   typedef struct   {       LINT kpub, kpriv, mod, p, q, ep, eq, r;       USHORT bitlen_mod;// binary length of modulus       USHORT bytelen_mod; // length of modulus in bytes   } KEYSTRUCT;   // the structure with the public key components   typedef struct   {       LINT kpub, mod;       USHORT bitlen_mod;// binary length of the modulus       USHORT bytelen_mod; // length of modulus in bytes   } PKEYSTRUCT;   class RSAkey   {     public:       inline RSAkey (void) {};       RSAkey (const int);       RSAkey (const int, const LINT&);       PKEYSTRUCT export_public (void) const;       UCHAR* decrypt (const LINT&, int*);       LINT sign (const UCHAR* const, const int);     private:       KEYSTRUCT key;       // auxiliary functions       int makekey (const int);       int testkey (void);       LINT fastdecrypt (const LINT&);   };   class RSApub   {     public:       inline RSApub (void) {};       RSApub (const RSAkey&);       LINT crypt (const UCHAR* const, const int);       int authenticate (const UCHAR* const, const int, const LINT&);     private:       PKEYSTRUCT pkey;   };   // selection from module rsakey.cpp    ...   #include "rsakey.h"   ////////////////////////////////////////////////////////////////////////   // member functions of the class RSAkey   // constructor generates RSA keys of specified binary length   RSAkey::RSAkey (const int bitlen)   {     int done;     seedBBS ((unsigned long)time (NULL));     do       {          done = RSAkey::makekey (bitlen);       }     while (!done);   }   // constructor generates RSA keys of specified binary length,   // initialization of random number generator randBBS() with   // specified LINT argument   RSAkey::RSAkey (const int bitlen, const LINT& rand)   {     int done;     seedBBS (rand);     do       {          done = RSAkey::makekey (bitlen);       }     while (!done);   }   // export function for public key components   PKEYSTRUCT RSAkey::export_public (void) const   {     PKEYSTRUCT pktmp;     pktmp.kpub = key.kpub;     pktmp.mod = key.mod;     pktmp.bitlen_mod = key.bitlen_mod;     pktmp.bytelen_mod = key.bytelen_mod;     return pktmp;   }   // RSA decryption   UCHAR* RSAkey::decrypt (const LINT& Ciph, int* LenMess)   {     // decryption and transformation of plain text into byte vector     UCHAR* Mess = lint2byte (fastdecrypt (Ciph), LenMess);     // take decrypted data from PKCS #1 Encryption Block     return parse_pkcs1 (Mess, LenMess);   }   // RSA signing   LINT RSAkey::sign (const UCHAR* const Mess, const int LenMess)   {     int LenEncryptionBlock = key.bytelen_mod - 1;     UCHAR* EncryptionBlock = new UCHAR[LenEncryptionBlock];     if (NULL == format_pkcs1 (EncryptionBlock,                     LenEncryptionBLock,                     BLOCKTYPE_SIGN,                     ripemd160 ((UCHAR*)Mess, (ULONG)LenMess),                     RMDVER >> 3))       {          delete [] EncryptionBlock;          return LINT (0);// error in formatting: message too long       }     // change encryption block into LINT number (constructor 3)     LINT m = LINT (EncryptionBlock, LenEncryptionBlock);     delete [] EncryptionBlock;     return fastdecrypt (m);   }   ////////////////////////////////////////////////////////////////////////   // private auxiliary functions of the class RSAkey   // ... among other things: RSA key generation according to IEEE P1363, Annex A   int RSAkey::makekey (const int length)   {     // generate prime p with length 2 ^ (m - r - 1) <= p < 2 ^ (m - r), where     // m = (length + 1)/2 and r random in interval 2 <= r < 13     USHORT m = (length + 1) >> 1 - 2 - usrandBBS_l () % 11;     key.p = findprime (m, 1);     // determine interval bounds qmin and qmax for prime q     // set qmin = (2 ^ (length - 1))/p + 1     LINT qmin = LINT(0).setbit (length - 1)/key.p + 1;     // set qmax = (2 ^ length)/p)     LINT qmax = LINT(0).setbit (length)/key.p;     // generate prime q > p with length qmin <= q <= qmax     key.q = findprime (qmin, qmax, 1);     // generate modulus p*q with length 2 ^ (length - 1) <= p*q < 2 ^ length     key.mod = key.p * key.q;     // calculate Euler phi function     LINT phi_n = key.mod - key.p - key.q + 1;     ...     // generate public key of length 64 bits     key.kpub = randBBS (64) | 1;     while (gcd (key.kpub, phi_n) != 1)       {          ++key.kpub;          ++key.kpub;       }     // generate secret key     key.kpriv = key.kpub.inv (phi_n);     // generate secret components for rapid decryption     key.ep = key.kpriv % (key.p - 1);     key.eq = key.kpriv % (key.q - 1);     key.r = inv (key.p, key.q);     return testkey();   }   // test function for RSA-key   int RSAkey::testkey (void)   {     LINT mess = randBBS (ld (key.mod) >> 1);     return (mess == fastdecrypt (mexpkm (mess, key.kpub, key.mod)));   }   // rapid RSA decryption   LINT RSAkey::fastdecrypt (const LINT& mess)   {     LINT m, w;     m = mexpkm (mess, key.ep, key.p);     w = mexpkm (mess, key.eq, key.q);     w = w.msub (m, key.q);     w = w.mmul (key.r, key.q) * key.p;     return (w + m);   }   ////////////////////////////////////////////////////////////////////////    // member functions of the class RSApub   // constructor RSApub()   RSApub::RSApub (const RSAkey& k)   {     // import public key from k     pkey = k.export();   }   // RSA encryption   LINT RSApub::crypt (const UCHAR* const Mess, const int LenMess)   {     int LenEncryptionBlock = key.bytelen_mod - 1;     UCHAR* EncryptionBlock = new UCHAR[LenEncryptionBlock];     // format encryption block according to PKCS #1     if (NULL == format_pkcs1 (EncryptionBlock,                     LenEncryptionBlock,                     BLOCKTYPE_ENCR,                     Mess,                     (ULONG)LenMess))       {          delete [] EncryptionBlock;          return LINT (0); // formatting error: message too long       }     // transform encryption block into LINT number (constructor 3)     LINT m = LINT (EncryptionBlock, LenEncryptionBlock);     delete [] EncryptionBlock;     return (mexpkm (m, pkey.kpub, pkey.mod));   }   // authentication of RSA signature   int RSApub::authenticate (const UCHAR* const Mess, const int LenMess, const LINT& Signature)   {     int l, verification = 0;     UCHAR* m = lint2byte (mexpkm (Signature, pkey.kpub, pkey.mod), &l);     UCHAR* h = ripemd160 ((UCHAR*)Mess, (ULONG)LenMess);     // take data from decrypted PKCS #1 encryption block     m = parse_pkcs1 (m, &l);     // compare length and value of decrypted data with hash value     if (l == (RMDVER >> 3))       {          verification = !memcmp ((char*)h, (char*)m, RMDVER >> 3);       }     return verification;  } 

The class implementations RSAkey and RSApub contain in addition the following operators, which are not discussed further here:

    RSAkey& operator= (const RSAkey&);    friend int operator== (const RSAkey&, const RSAkey&);    friend int operator!= (const RSAkey&, const RSAkey&);    friend fstream& operator<< (fstream&, const RSAkey&);    friend fstream& operator>> (fstream&, RSAkey&); 

and

    RSApub& operator= (const RSApub&);    friend int operator== (const RSApub&, const RSApub&);    friend int operator!= (const RSApub&, const RSApub&);    friend fstream& operator<< (fstream&, const RSApub&);    friend fstream& operator>> (fstream&, RSApub&); 

These are for elementwise allocation, tests for equality and inequality, as well as reading and writing of keys to and from mass storage. However, one must note that the private key is stored in plain text, just as the public key is. For a real application the secret keys must be stored in encrypted form.

There are also the member functions

      RSAkey::purge (void),      RSApub::purge (void), 

which overwrite keys and set their LINT components to 0. The formatting of message blocks for encryption or signing corresponding to the PKCS #1 specification is taken over by the function

     UCHAR* format_pkcs1 (const UCHAR* EB, const int LenEB,     const UCHAR BlockType, const UCHAR* Data, const int LenData); 

The analysis of decrypted message blocks for verifying the format and for the extraction of useful data is handled by the function

      UCHAR* parse_pkcs1 (const UCHAR* EB, int* LenData); 

The classes RSAkey and RSApub are extendable in a number of ways. For example, one could imagine a constructor that accepts a public key as parameter and generates a suitable modulus and secret key. For a practical implementation the inclusion of additional hash functions may be necessary. Message blocking is also required. The list of worthwhile extensions is long, and a full discussion would break the bounds and the binding of this book.

An example test application of the classes RSAkey and RSApub is to be found in the module rsademo.cpp contained in the FLINT/C package. The program is translated with

    gcc -O2 -DFLINT_ASM -o rsademo rsademo.cpp rsakey.cpp      flintpp.cpp flint.c ripemd.c -lflint -lstdc++ 

if one implements, for example, the GNU C/C++ compiler gcc under Linux and uses the assembler functions in libflint.a.


Team-Fly


Cryptography in C and C++
Cryptography in C and C++
ISBN: 189311595X
EAN: 2147483647
Year: 2001
Pages: 127

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net