Product Keys Based on Elliptic Curve Cryptography

Introduction

A popular method of product validation uses keys similar to VJJJBX-H2BBCC-68CF7F-2BXD4R-3XP7FB-JDVQBC. These compact keys can be derived by using Public Key Cryptosystems such as Elliptic Curve Cryptography.

Other Public Key Cryptosystems, such as RSA, are available. However, these systems generally produce larger keys (that the user will eventually have to enter into the program to unlock functionality). Smaller producing Cryptosystems exist, but it is the author's opinion that they are highly encumbered with patents. Quartz is one such example. It is a Public Key Encryption System that produces a smaller ciphertext based on Hidden Field Equations (HFEs). The Quartz website is littered with phrases such as "must license" and "pay royalties."

This article will use ECIES (specified in IEEE 1363 and ANSI X9.63) as the Cryptosystem, and Wei Dai's Crypto++ for Elliptic Curve operations. ECIES is based on the work of Abdalla, Bellare, add Rogaway. ECIES will produce slightly larger keys, but the cryptosystem is less burdened with patents. The reader also is encouraged to investigate Signature Schemes (with Recovery) as an alternative method to producing Product Keys. An example is PSS-R, a Message Recovery Signature Scheme based on RSA. PSS-R is proposed in ANSI X9.31 (reopened by the ANSI X9F working group) and IEEE 1363. The reader also should visit Product Keys Based on the Advanced Encryption Standard (AES) to familiarize themselves with basic concepts of Product Keys in the domain of Symmetric Key Cryptography.

This article will explain the following topics in detail:

  • Compiling and Integrating Crypto++ into the Visual C++ Environment
  • Elliptic Curve Cryptography Implementation in Crypto++
  • Using Elliptic Curves with User Defined Domain Parameters In Crypto++
  • Base Encoding a Ciphertext String in Crypto++
  • Working Demo which Exercises Product Keys based on ECC
  • Bulk Product Key Generation
  • Product Key Validation
  • Product Activation
  • Securely Saving Key or Activation State to the Registry

This article is based on the Visual C++ 6.0 environment in hopes that it reaches the largest audience.

Elliptic Curve Cryptography

This article assumes the reader has a basic understanding of Cryptography. For an overview, see Gary Kessler's An Overview of Cryptography. For an ECC Tutorial, see Ceticom's ECC Tutorial. For a casual Cryptography reader, Elliptic Curve Cryptography should prove to be interesting; it is not like RSA (based on Integer Factorization), Diffie-Hellman and ElGamal (based on Discrete Logarithms), or MQ (Multivariate Quadratics). However, ECC is related to DLP.

This article uses comparitively small EC key sizes. It is justified in that the Product Key liftetime is relatively short (based directly on Product Life Cycles). RSA Laboratories offers the following recommendations for key sizes:

Protection Lifetime of Data Present – 2010 Present – 2030 Present – Beyond 2031
Minimum Symmetric Security Level 80 bits 112 bits 128 bits
Minimum RSA
Key Size
1024 bits 2048 bits 3072 bits

Below is a comparison of equivalent Key sizes of ECC and RSA.

The following figure estimates the Security Level of ECC and RSA & DSA in MIPS Years.

The friendly folks at the US Government's NSA has put together some reading that also may be of interest. The article is titled The Case for Elliptic Curve Cryptography.

It is very noteworthy that Peter Shor of AT&T Research has a Quantum Factoring Algorithm that runs in O((log n)3) time. Additionally, Shor has proposed a Quantum Root Finding Algorithm that also is polynomial in time complexity (to solve the Discrete Logarithm problem). In 2001, IBM built a quantum computer capable of factoring the number 15 (using 7 qubits—the quantum equivalent of 27) using Shor's Algorithm. It is believed the future will produce quantum computers with over 1000 qubits.

Product Keys Based on Elliptic Curve Cryptography

Using Elliptic Curves with User-Defined Domain Parameters in Crypto++

Crypto++ supplies 31 predefined Elliptical Curves for use with ECIES (Elliptic Curve Integrated Encryption Scheme) as specified in ANSI X9.63. These curves range in size from 112 bits to 571 bits. Encrypting a 4-byte message with an 112-bit ECIES object produces a ciphertext length of 53 bytes. Encrypting the same message with an ECIES object of 34 bits will produce a 35-byte ciphertext.

The large ciphertext is due to the following: When using Crypto++, a CryptoPP::ECIES< CryptoPP::ECP > object is created. The CryptoPP::ECIES< CryptoPP::ECP >::Encryptor returns a ciphertext object that is a tuple (V, C, T) consisting of the following:

  • EC public key V
  • Encrypted message C
  • Authentication tag T is generated from a message M

The authentication tag T is derived from SHA-1. The SHA-1 block size is 160 bits. So, the authentication tag accounts for approximately 160/8, or approximately 20 bytes of the ciphertext object. (The astute reader should realize the benefits of a Signature Scheme (with Recovery) at this point). More will follow later in this article with respect to authentication tag T parring.

Ideally, the ciphertext will be about 20 bytes. This will produce a key of 30 to 35 characters in length after Base Encoding the ciphertext into a Product Key. (Again, further reductions will be achieved later in the article.)

For this portion of the article, Elliptic Curve Builder (ECB) will be used to generate curves for use with the Product Keys. Many thanks to Marcel Martin for modifying his original Object Pascal code to accommodate this article. ECB can be downloaded from http://www.ellipsa.net/. A copy of the ECB version 1.0.0.6 is not included with the article. However, it is obtainable from Marcel's Ellipsa page.

Using Elliptic Curve Builder to Generate Domain Parameters

Open ECB, and click the leftmost blue thunderbolt. This will generate new curve parameters over Fp.

In the New Curve Over... Dialog Box, enter the following:

  • Suitable Curve Size (minimum is 33 bits)
  • Cofactor S max binary size of 2

A note on EC Domain Parameters and ECB. Although the ECB editor displays Discriminant is 0, ECB begins its search at Discriminant + 1, so the parameter does not require modification. The ECB Discriminant value is for Complex Multiplication. This is a different Discriminant than that of Weierstrass' equation of y2 ≡ x3 + ax + b (mod p). A non 0 Discriminant is required for the later case in this Cryptosystem. Eventually, Crypto++ will check the condition 4a3 + 27b2 !≡  0 (mod p). For a complete list of required checks, see Certicom's accompanying document, SEC 1: Elliptic Curve Cryptography. Section 3.1.1.1, Elliptic Curve Domain Parameters over Fp Generation Primitive, is the appropriate area of the document.

Cofactor S max binary size is set to 2 because 22 = 4. According to the Certicom document, h ≤ 4 (S in ECB, h in EC literature). If the reader is inclined, a larger S can be selected. Marcel recommends at least 3, so a cofactor of 4 is available. If the user encounters cofactor S of 5, 6, or 7, he or she should regenerate the parameters.

Next, select the tab entitled, "Curve and Point." Click the yellow thunderbolt. The presented parameters are acceptable. Note that NIST curves use A = -3 to speed underlying mathematical operations.

Finally, click the green thunderbolt in the editor. This will produce G(x, y) points of Order R over the Curve E(Fp). Note that negative values are acceptable for either a, b, x or y. However, SEC1, Section 3.1.1.2.1 Elliptic Curve Domain Parameters over Fp Validation Primitive (check 2) states:

Check that a, b, xG, and yG are integers in the interval [0, p-1].

To facilitate the requirement, issue the following:

// parameters are in the interval [0, p-1]
a %= p; b %= p; x %= p; y %= p;

Copy and Paste the parameters into Visual C++ to avoid transcription errors.

Product Keys Based on Elliptic Curve Cryptography

Using Elliptic Curves with User Defined Domain Parameters In Crypto++ (continued)

ecctest2 exercises Crypto++ and the User Defined Domain Parameters. The essence of ecctest2 is below. Some notes on the following code:

  • p, a, and b define the curve
  • Base Point G is specified as a (x, y) coordinate
// From ecctest 2

// Crypto++ Includes
#include "cryptlib.h"
#include "osrng.h"      // Random Number Generator
#include "eccrypto.h"   // Elliptic Curve
#include "ecp.h"        // F(p) EC
#include "integer.h"    // Integer Operations

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

   CryptoPP::AutoSeededRandomPool rng;

   // User Defined Domain Parameters
   CryptoPP::Integer p("11069481119");
   CryptoPP::Integer a("9891419326");
   CryptoPP::Integer b("3785846764");
   CryptoPP::Integer n("5534832397");    // R from ECB
   CryptoPP::Integer h("2");             // S from ECB, must be <= 4
   CryptoPP::Integer x("53467489");
   CryptoPP::Integer y("1485849126");

   CryptoPP::ECP ec( p, a, b );
   CryptoPP::ECP::Point G( x, y );

   CryptoPP::ECIES< CryptoPP::ECP >::PrivateKey    PrivateKey;
   CryptoPP::ECIES< CryptoPP::ECP >::PublicKey     PublicKey;

   // Curve Initialization and Key Generation
   PrivateKey.Initialize( ec, G, n, h );
   PrivateKey.MakePublicKey( PublicKey );
        
   // Encryptor and Decryptor
   CryptoPP::ECIES< CryptoPP::ECP >::Encryptor
      Encryptor( PublicKey );
   CryptoPP::ECIES< CryptoPP::ECP >::Decryptor
      Decryptor( PrivateKey );

   // Message
   std::string PlainText = " ECC ";

   // Runtime Sizes...
   unsigned int PlainTextLength = PlainText.length() + 1;
   unsigned int CipherTextLength =
      Encryptor.CiphertextLength( PlainTextLength );
   if( 0 == CipherTextLength )
      { throw std::string("plaintextLength is not valid (too long)"); }
       
   // Scratch for Encryption
   byte* CipherText = new byte[ CipherTextLength ];

   // Encryption
   Encryptor.Encrypt( rng, reinterpret_cast<const byte*>
      ( PlainText.c_str() ), PlainTextLength,
        CipherText );

   // Scratch for Decryption
   unsigned int RecoveredTextLength =
      Decryptor.MaxPlaintextLength( CipherTextLength );
   if( 0 == RecoveredTextLength )
      { throw std::string("ciphertextLength is not valid (too long
           or too short)"); }

   // Decryption Buffer
   char* RecoveredText = new char[ RecoveredTextLength ];

   // Decryption        
   Decryptor.Decrypt( rng, CipherText, CipherTextLength,
                      reinterpret_cast<byte*>( RecoveredText ) );

   // Diagnostics
   std::cout << "Recovered text (" << RecoveredTextLength <<
                                 " bytes):" << std::endl;
   std::cout << "'" << RecoveredText << "'" << std::endl;

   return 0;
}

Below is a sample output with satisfactory parameters. The litmus test is definitive—the message decrypts.

Finally, a sample output with unsatisfactory parameters. Should a reader encounter similar, perform the following:

  • Verify ECB parameters were correctly transcribed
  • Generate new parameters with ECB.

Product Keys Based on Elliptic Curve Cryptography

Encoding a Ciphertext String in Crypto++

For encoding and decoding of the ciphertext, this article uses both the Crypto++ base 64 encoder and base 32 encode. Better alphabet choices exist for Product Keys. For example, the following is a short list of alphabet constraints for Product Keys

  • Keys are formed over the alphabet A-Z and 0-9
  • Keys are not case sensitive
  • Do not use letters l (lowercase "L") or O (capital "o") (they appear as numbers in some fonts)
  • Do not use letters u and v (they appear similar in some fonts)
  • Do not use numbers 0 or 1 (they appear as letters in some fonts)
  • Print keys using a font created for text scanning (it is easier to distinguish characters)

Base Encoding expansion for Base64 encoding is approximately 35%, whereas expansion for Base32 encoding is approximately 60% (based on a psuedo randomly generated block of 16 * 1024 (16384) bytes). See the accompanying BaseExp for the program used to generate the sample block and calculate the expansions.

// From ecctest3

// Crypto++ Includes
#include "cryptlib.h"
#include "osrng.h"      // Random Number Generator
#include "eccrypto.h"   // Elliptic Curve
#include "ecp.h"        // F(p) EC
#include "integer.h"    // Integer Operations
#include "base64.h"     // Base 64 Encode/Decoder

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

   // User Defined Domain Parameters Omitted
   // ec, G, n, h

   CryptoPP::ECIES< CryptoPP::ECP >::PrivateKey    PrivateKey;
   CryptoPP::ECIES< CryptoPP::ECP >::PublicKey     PublicKey;

   PrivateKey.Initialize( ec, G, n, h );
   PrivateKey.MakePublicKey( PublicKey );
     
   // Encryptor and Decryptor
   CryptoPP::ECIES< CryptoPP::ECP >::Encryptor Encryptor( PublicKey );
   CryptoPP::ECIES< CryptoPP::ECP >::Decryptor Decryptor( PrivateKey );

   // Message
   std::string PlainText = " ECC ";

   // Runtime Sizes...
   unsigned int PlainTextLength  = PlainText.length() + 1;
   unsigned int CipherTextLength = Encryptor.CiphertextLength
      ( PlainTextLength );
   if( 0 == CipherTextLength )
      { throw std::string("plaintextLength is not valid (too long)"); }
   
   // Scratch for Encryption
   byte* CipherText = new byte[ CipherTextLength ];

   // Encryption        
   Encryptor.Encrypt( rng, reinterpret_cast<const byte*>
                     ( PlainText.c_str() ),
                      PlainTextLength, CipherText );

   // Base 64 Encoding
   CryptoPP::Base64Encoder Encoder;
   Encoder.Put( CipherText, CipherTextLength );
   Encoder.MessageEnd();
        
   // Scratch for Base 64 Encoded Ciphertext
   unsigned int EncodedTextLength = Encoder.MaxRetrievable();
   // + 1 for NULL termination
   byte* EncodedText = new byte[ EncodedTextLength + 1 ];
   EncodedText[ EncodedTextLength ] = '\0';    // NULL Terminate

   // Base 64 Encoded Ciphertext
   Encoder.Get( EncodedText, EncodedTextLength );

   // Base 64 Decoding
   CryptoPP::Base64Decoder Decoder;
   Decoder.Put( EncodedText, EncodedTextLength );
   Decoder.MessageEnd();

   // Scratch for Base 64 Decoded Ciphertext
   unsigned int DecodedTextLength =
                Decoder.MaxRetrievable();
   byte* DecodedText = new byte[ DecodedTextLength ];

   // Ciphertext is no longer Encoded
   Decoder.Get( DecodedText, DecodedTextLength );

   //
   // At this point, DecodedText = CipherText
   //
   assert( DecodedTextLength == CipherTextLength );
   assert( 0 == ::memcmp( DecodedText, CipherText, CipherTextLength ) );

   // Scratch for Decryption
   unsigned int RecoveredTextLength =
      Decryptor.MaxPlaintextLength( CipherTextLength );
   if( 0 == RecoveredTextLength )
      { throw std::string("ciphertextLength is not valid (too long
        or too short)"); }

   // Decryption Buffer
   char* RecoveredText = new char[ RecoveredTextLength ];

   // Decryption        
   Decryptor.Decrypt( rng, CipherText, CipherTextLength,
                      reinterpret_cast( RecoveredText ) );

   // Diagnostics
   std::cout << "Recovered text (" << RecoveredTextLength << " bytes):"
      << std::endl;
   std::cout << "'" << RecoveredText << "'" << std::endl;
}

ecctest3 is the driver for this portion of the article. The results of running ecctest3 should be similar to the following.

Product Keys Based on Elliptic Curve Cryptography

Product Keys Based on ECC

This (near anticlimactic) portion of the article discusses Feature Encoding. ecctest4.zip is the sample archive. Feature Encoding requires very few bytes—in the author's sample it is 4 bytes—one unsigned int is used. Other notes on the code are:

  • Message is now an unsigned int rather than a std::string
  • Features is a bit mask values
  • Magic is the final check to verify the Product Key is Valid
// Form ecctest4

// The Features Available...
const unsigned int FEATURE_EVALUATION  = 0x01;    // 0000 0001
const unsigned int FEATURE_USE_SQUARES = 0x02;    // 0000 0010
const unsigned int FEATURE_USE_CIRCLES = 0x04;    // 0000 0100
const unsigned int FEATURE_USE_WIDGETS = 0x08;    // 0000 1000

// 1010 1010 1010 1010 0000 0000 0000 0000
const unsigned int FEATURE_MAGIC = 0xAAAA << 16;

// 1111 1111 1111 1111 0000 0000 0000 0000
const unsigned int FEATURE_MAGIC_MASK = 0xFFFF << 16;


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

   // User Defined Domain Parameters Omitted
   // ec, G, n, h

   CryptoPP::ECIES< CryptoPP::ECP >::PrivateKey    PrivateKey;
   CryptoPP::ECIES< CryptoPP::ECP >::PublicKey     PublicKey;

   PrivateKey.Initialize( ec, G, n, h );
   PrivateKey.MakePublicKey( PublicKey );

   // Encryptor and Decryptor
   CryptoPP::ECIES< CryptoPP::ECP >::Encryptor
      Encryptor( PublicKey );
   CryptoPP::ECIES< CryptoPP::ECP >::Decryptor
      Decryptor( PrivateKey );

   // Message
   unsigned int Features = 0;

   Features |= FEATURE_MAGIC;
   Features |= FEATURE_USE_WIDGETS;
   Features |= FEATURE_USE_SQUARES;

   // Runtime Sizes...
   unsigned int PlainTextLength = sizeof( Features );
   unsigned int CipherTextLength = Encryptor.CiphertextLength
      ( PlainTextLength );
   if( 0 == CipherTextLength )
      { throw std::string("plaintextLength is not valid (too long)"); }

   // Scratch for Encryption
   CipherText = new byte[ CipherTextLength ];

   // Encryption
   Encryptor.Encrypt( rng, reinterpret_cast<const byte*>( &Features ),
            PlainTextLength, CipherText );

   // Base 64 Encoding
   CryptoPP::Base64Encoder Encoder;
   Encoder.Put( CipherText, CipherTextLength );
   Encoder.MessageEnd();

   // Scratch for Base 64 Encoded Ciphertext
   unsigned int EncodedTextLength = Encoder.MaxRetrievable();
   EncodedText = new byte[ EncodedTextLength + 1 ];
   EncodedText[ EncodedTextLength ] = '\0';

   // Fetch Base 64 Encoded Ciphertext
   Encoder.Get( EncodedText, EncodedTextLength );

   // Diagnostics...
   std::cout << "Encoded Text Before Tampering:"
             << std::endl << EncodedText << std::endl;

   // Output
   if( FEATURE_EVALUATION  == (Features & FEATURE_EVALUATION ) )
       { std::cout << "Evaluation Edition." << std::endl; }
   if( FEATURE_USE_SQUARES == (Features & FEATURE_USE_SQUARES) )
       { std::cout << "Operations are permitted on Squares."
         << std::endl; }
   if( FEATURE_USE_CIRCLES == (Features & FEATURE_USE_CIRCLES) )
       { std::cout << "Operations are permitted on Circles."
         << std::endl; }
   if( FEATURE_USE_WIDGETS == (Features & FEATURE_USE_WIDGETS) )
       { std::cout << "Operations are permitted on Widgets."
         << std::endl; }
   std::cout << std::endl << "********************"
             << std::endl << std::endl;

   // The folllowing introduces 1 random error
   // EncodedText[ EncodedTextLength - 2 ] = 'W';


   // The folllowing introduces multiple random errors
   //   Guessing at a Product Key
   char ch = 'A';
   for( unsigned int i = 0; i < EncodedTextLength - 1; i += 3 )
   {
       EncodedText[ i ] = ch++;
   }

   // Diagnostics...
   std::cout << "Encoded Text After Tampering:" << std::endl
             << EncodedText << std::endl;

   // Base 64 Decoding
   CryptoPP::Base64Decoder Decoder;
   Decoder.Put( EncodedText, EncodedTextLength );
   Decoder.MessageEnd();

   // Scratch for Base 64 Decoded Ciphertext
   unsigned int DecodedTextLength = Decoder.MaxRetrievable();
   DecodedText = new byte[ DecodedTextLength ];

   // Fetch Base 64 Decoded Ciphertext
   Decoder.Get( DecodedText, DecodedTextLength );

   // Scratch for Decryption
   unsigned int RecoveredTextLength = Decryptor.MaxPlaintextLength
      ( DecodedTextLength );
   if( 0 == RecoveredTextLength )
       { throw std::string("ciphertextLength is not valid (too long
         or too short)"); }

   // Decryption Buffer
   // 1111 ... 1111
   unsigned int RecoveredText = static_cast<int>( -1 );

   // Decryption
   Decryptor.Decrypt( rng, DecodedText, DecodedTextLength,
                      reinterpret_cast<byte *>( &RecoveredText ) );

   // Output
   if( FEATURE_MAGIC != (RecoveredText & FEATURE_MAGIC_MASK ) )
   {
      throw std::string("Invalid Product Key");
   }
   else
   {
      if( FEATURE_EVALUATION  == (RecoveredText & FEATURE_EVALUATION ) )
         { std::cout << "Evaluation Edition." << std::endl; }
      if( FEATURE_USE_SQUARES == (RecoveredText & FEATURE_USE_SQUARES) )
         { std::cout << "Operations are permitted on Squares."
           << std::endl; }
      if( FEATURE_USE_CIRCLES == (RecoveredText & FEATURE_USE_CIRCLES) )
         { std::cout << "Operations are permitted on Circles."
           << std::endl; }
      if( FEATURE_USE_WIDGETS == (RecoveredText & FEATURE_USE_WIDGETS) )
         { std::cout << "Operations are permitted on Widgets."
           << std::endl; }
   }

   return 0;
}

Results from running ecctest4 are shown below:

 

Product Keys Based on Elliptic Curve Cryptography

Product Keys Based on ECC (continued)

The output above displays the execution of ecctest5. ecctest5 adds the following (shown in the code example below):

  • Base 32 Encoding
  • 'Pretty Printing' of the Base 32-Encoded ciphertext
  • Use of CryptoPP::DecodingResult to detect altered Product Keys:
// From ecctest5

// Base 32 Encoding
CryptoPP::Base32Encoder Encoder;
Encoder.Put( CipherText, CipherTextLength );
Encoder.MessageEnd();

...

const unsigned int BREAK = 7;
std::cout << "Pretty Print:" << std::endl;
for(unsigned int i = 0; i < EncodedTextLength - 1; i++)
{
   if( 0 != i && 0 == i % BREAK )
      { std::cout << "-"; }
   std::cout << EncodedText[ i ];
};
std::cout << std::endl;

...

// Decryption
CryptoPP::DecodingResult Result =
    Decryptor.Decrypt( rng, DecodedText, DecodedTextLength,
                       reinterpret_cast<byte *>( &RecoveredText ) );

// Crypto++ Test
if( false == Result.isValidCoding )
   { throw std::string("Crypto++: Invalid Coding"); }

Product Keys Based on Elliptic Curve Cryptography

Product Keys Based on ECC (continued)

To further reduce the size of the Product Key, this article creates a spurious authentication tag T for the ciphertext object (C,V,T). Ideally, a 0 byte HMAC function would have been added to CryptoPP::DL_EncryptionAlgorithm_Xor(...)—however, Microsoft's environment could not properly generate code with arrays of size 0. SecByteBlock< > caused too many C2229 compilation errors.

As a compromise, TRUEHash was created. The hash returns the same value regardless of the message—0x01. TRUEHash adds aprroximately 4 bytes of authentication tagging (T in the Ciphertext Object (C, V, T)). Template specialization for TRUEHash is below. 58 bits was chosen because it can be partitioned into an aesthetically pleasing groups of 5.

// From ecctest6

// Crypto++ Includes
//   Expedient Implementation of a NULL Hash
#include "cryptlib.h"
#include "iterhash.h"
// TRUEHash
//   A hash that always returns 0x01
//     This is a Visual C++ workaround (possibly others)
//     due to not being being able to create a NULL HMAC class
//   The NULL HMAC cannot compile due to a digest size of 0
//     because of array sizing of 0 (major problems in SecByteBlock())
class TRUEHash : public CryptoPP::IteratedHashWithStaticTransform
      <CryptoPP::word32,
      CryptoPP::BigEndian, 32, 4, TRUEHash>
{
public:
   static void InitState(HashWordType *state)
      { state[0] = 0x01; return; }
   static void Transform(CryptoPP::word32 *digest,
                         const CryptoPP::word32 *data)
      { return; }
   static const char *StaticAlgorithmName() {return "TRUE HASH";}
};

With the shim class in place, a new Specialized ECIESNullT class < > was created. Notice the introduction of TRUEHash to DL_EncryptionAlgorithm_Xor.

// Crypto++ Includes
//   Template Specialization modification of
//   struct ECIES in ecccrypto.h
#include "pubkey.h"
#include "dh.h"
#include "sha.h"
#include "eccrypto.h"
#include "ecp.h"

template <class EC, class COFACTOR_OPTION =
   CryptoPP::NoCofactorMultiplication,
   bool DHAES_MODE = false>
struct ECIESNullT
   : public CryptoPP::DL_ES<
      CryptoPP::DL_Keys_EC<EC>,
      CryptoPP::DL_KeyAgreementAlgorithm_DH<typename EC::Point,
         COFACTOR_OPTION>,
      CryptoPP::DL_KeyDerivationAlgorithm_P1363<typename EC::Point,
         DHAES_MODE, CryptoPP::P1363_KDF2<CryptoPP::SHA1> >,
      CryptoPP::DL_EncryptionAlgorithm_Xor<
         CryptoPP::HMAC<TRUEHash>, DHAES_MODE>,
      CryptoPP::ECIES<EC> >
{
   static std::string StaticAlgorithmName() {return "ECIES with NULL T";}
};

Running ecctest6 produces the following output:

And the corresponding results with a false key:

Product Keys Based on Elliptic Curve Cryptography

Bulk Product Key Generation

ecctest7 exercises the ability to generate multiple Ciphertext Objects based on common curve parameters (recall that ECIES parameters are the sextuple (p, a, b, Point G, n, h). Point G is simply (x, y)). This sample serves as proof of concept for the Key Generator and Key Validator.

KeyGen (as with ecctest7) exercises ECIES's property that a new, Temporary Key V is generated for each Messsage M, producing a unique Ciphertext object (C,V,T) for each encryption operation. Note that the Decryptor has been dropped—it will exist in the validating software.

The perceptive reader should notice ECIES Ciphertext redundancy. The reader can further reduce the size of the generated Product Key by removing the redundant bytes after Base32 encoding (before PrettyPrint); and prepending and/or appending before the Base32 decoding, saving an additional 7 bytes of Base32 encoding. As a concrete example, a 56 bit curve produces a 31 byte key. 31 - 7 = 24, which groups aesthetically—six groups of four (xxxx-xxxx-xxxx-xxxx-xxxx-xxxx). Note that the additional bytes are required for decoding, but do not necessarily need to be keyed by the user.

The following is the Product Key generating program.

// From ecctest7

// The Features Available...
const unsigned int FEATURE_EVALUATION  = 0x01;    // 0000 0001
const unsigned int FEATURE_USE_SQUARES = 0x02;    // 0000 0010
const unsigned int FEATURE_USE_CIRCLES = 0x04;    // 0000 0100
const unsigned int FEATURE_USE_WIDGETS = 0x08;    // 0000 1000

const unsigned int FEATURE_MAGIC      = 0xAAAA << 16;
const unsigned int FEATURE_MAGIC_MASK = 0xFFFF << 16;

// Crypto++ Includes
//   Expedient Implementation of a NULL Hash
#include "cryptlib.h"
#include "iterhash.h"
// TRUEHash
//   A hash that always returns 0x01
class TRUEHash : public CryptoPP::IteratedHashWithStaticTransform
   <CryptoPP::word32, CryptoPP::BigEndian, 32, 4, TRUEHash>
{
public:
    static void InitState(HashWordType *state)
        { state[0] = 0x01; return; }
    static void Transform(CryptoPP::word32 *digest,
                          const CryptoPP::word32 *data)
        { return; }
   static const char *StaticAlgorithmName() {return "TRUE HASH";}
};

// Crypto++ Includes
//   Template Specialization modification of
//   struct ECIES in ecccrypto.h
#include "pubkey.h"
#include "dh.h"
#include "sha.h"
#include "eccrypto.h"
#include "ecp.h"

template <class EC, class COFACTOR_OPTION =
   CryptoPP::NoCofactorMultiplication,
         bool DHAES_MODE = false>
struct ECIESNullT
   : public CryptoPP::DL_ES<
      CryptoPP::DL_Keys_EC<EC>,
      CryptoPP::DL_KeyAgreementAlgorithm_DH<typename EC::Point,
                COFACTOR_OPTION>,
      CryptoPP::DL_KeyDerivationAlgorithm_P1363<typename EC::Point,
                DHAES_MODE, CryptoPP::P1363_KDF2<CryptoPP::SHA1> >,
      CryptoPP::DL_EncryptionAlgorithm_Xor<CryptoPP::HMAC<TRUEHash>,
                DHAES_MODE>,
      CryptoPP::ECIES<EC> >
{
   static std::string StaticAlgorithmName() {return "ECIES with NULL T";}
};

// Crypto++ Includes
//   Required for main(...)
#include "cryptlib.h"
#include "osrng.h"       // Random Numbeer Generator
#include "eccrypto.h"    // Elliptic Curve
#include "ecp.h"         // F(p) EC
#include "integer.h"     // Integer Operations
#include "base32.h"      // Encodeing-Decoding
#include "nbtheory.h"    // ModularSquareRoot(...)

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

    byte* CipherText  = NULL;
    byte* EncodedText = NULL;
    CryptoPP::AutoSeededRandomPool rng;

    try {

        // PlainText (Message M)
        unsigned int Features = 0;

        Features |= FEATURE_MAGIC;
        Features |= FEATURE_USE_WIDGETS;
        Features |= FEATURE_USE_SQUARES;

        // Runtime Sizes...
        unsigned int PlainTextLength = sizeof( Features );

        // User Defined Domain Parameters
        CryptoPP::Integer p("214644128745822931");
        CryptoPP::Integer a("0");
        CryptoPP::Integer b("-23719602096934623");
        CryptoPP::Integer n("71548043092139563");
        CryptoPP::Integer h("3");
        CryptoPP::Integer x("-35255913743814615");
        CryptoPP::Integer y("-71911853159754273");

        PrintCurveParameters( p, a, b, x, y, n, h ); std::cout
           << std::endl;

        CryptoPP::ECP ec( p, a, b );

        ECIESNullT< CryptoPP::ECP >::PrivateKey    PrivateKey;
        ECIESNullT< CryptoPP::ECP >::PublicKey     PublicKey;
     
        // Curve Initialization
        PrivateKey.Initialize(  ec, CryptoPP::ECP::Point( x, y ), n , h);
        PrivateKey.MakePublicKey( PublicKey );

        ECIESNullT< CryptoPP::ECP >::Encryptor Encryptor( PublicKey );
        // No Need for ECIESNullT< CryptoPP::ECP >::Decryptor
        //   in the Key Generator. The software will employ it.

        const unsigned int ITERATIONS = 128;
        for(int i = 0; i < ITERATIONS; i++ ) {
            
            unsigned int CipherTextLength =
               Encryptor.CiphertextLength( PlainTextLength );
            if( 0 == CipherTextLength )
                { throw std::string("plaintextLength is not valid
                  (too long)"); }

            // Scratch for Encryption
            CipherText = new byte[ CipherTextLength ];
            if( NULL == CipherText )
                { throw std::string( "CipherText Allocation Failure" ); }

            // Encryption
            Encryptor.Encrypt( rng, reinterpret_cast<const byte*>
                              ( &Features ),
                              PlainTextLength, CipherText );

            // Base 32 Encoding
            CryptoPP::Base32Encoder Encoder;
            Encoder.Put( CipherText, CipherTextLength );
            Encoder.MessageEnd();

            // Scratch for Base 32 Encoded Ciphertext
            unsigned int EncodedTextLength = Encoder.MaxRetrievable();
            EncodedText = new byte[ EncodedTextLength + 1 ];
            EncodedText[ EncodedTextLength ] = '\0';

            // Fetch Base 32 Encoded Ciphertext
            Encoder.Get( EncodedText, EncodedTextLength );

            // Pretty Print
            const unsigned int BREAK = 5;
            for(unsigned int i = 0; i < EncodedTextLength; i++)
            {
                if( 0 != i && 0 == i % BREAK ) { std::cout << "-"; }
                std::cout << EncodedText[ i ];
            }; std::cout << std::endl;

            // Cleanup
            delete[] CipherText;
            delete[] EncodedText;
        }
    }

    catch( CryptoPP::Exception& e ) {
        std::cerr << "Crypto++ Error: " << e.what()
           << std::endl;
    }

    catch( std::string& s ) {
        std::cerr << "Error: " << s << std::endl;
    }

    catch (...) {
        std::cerr << "Unknown Error" << std::endl;
    }

   return 0;
}

Product Keys Based on Elliptic Curve Cryptography

Product Key Validation

KeyVal is the driver program that validates Product Keys. The reader should chose a Product Key from this article and use it as a parameter to Decryptor.Decrypt(...) after removing the Base32 encoding.

The reader should be aware of the side effects casting a byte[] to an unsigned int*, as in excerpts from ecctest7 below. It is a C++ side effect, not a Crypto++ effect.

// User Defined Domain Parameters
// p, a, b, G, n, h omitted

// Setup Curve and Keys
// ...

// PlainText (Message M)
unsigned int Features = 0;
unsigned int PlainTextLength = sizeof( Features );

Features |= FEATURE_MAGIC;
Features |= FEATURE_USE_WIDGETS;
Features |= FEATURE_USE_SQUARES;

// Encrypt, Encode, Decode
// ...

// Decryption Buffer
byte* RecoveredText = new byte[ RecoveredTextLength ];
if( NULL == RecoveredText )
   { throw std::string( "RecoveredText CipherText
                         Allocation Failure" ); }

// Decryption
CryptoPP::DecodingResult Result =
   Decryptor.Decrypt( rng, DecodedText, DecodedTextLength,
                      RecoveredText );

...

// Conversion for Convenience
// Don't be fooled:
//   RecoveredFeatures = static_cast<unsigned int>
//   ( *RecoveredText );
//   only converts byte[ 0 ], not bytes[ 0 - 4 ]
unsigned int RecoveredFeatures =
   *(reinterpret_cast<unsigned int*>( RecoveredText ) );

// Output
if( FEATURE_MAGIC != (RecoveredFeatures & FEATURE_MAGIC_MASK ) )
  { throw std::string("RecoveredFeatures: Magic:
                       Invalid Product Key"); }

Securely Saving Key or Activation State to the Registry

Program Activation state can be securely saved to the Windows Registry. Visit CodeGuru's article, "An AES Encrypting Registry Class," for a discussion and implementation.

Product Keys Based on Elliptic Curve Cryptography

Product Key Validation

KeyVal is the driver program that validates Product Keys. The reader should chose a Product Key from this article and use it as a parameter to Decryptor.Decrypt(...) after removing the Base32 encoding.

The reader should be aware of the side effects of casting a byte[] to an unsigned int*, as in excerpts from ecctest7 below. It is a C++ side effect, not a Crypto++ effect.

// User Defined Domain Parameters
// p, a, b, G, n, h omitted

// Setup Curve and Keys
// ...

// PlainText (Message M)
unsigned int Features = 0;
unsigned int PlainTextLength = sizeof( Features );

Features |= FEATURE_MAGIC;
Features |= FEATURE_USE_WIDGETS;
Features |= FEATURE_USE_SQUARES;

// Encrypt, Encode, Decode
// ...

// Decryption Buffer
byte* RecoveredText = new byte[ RecoveredTextLength ];
if( NULL == RecoveredText )
   { throw std::string( "RecoveredText CipherText
                         Allocation Failure" ); }

// Decryption
CryptoPP::DecodingResult Result =
   Decryptor.Decrypt( rng, DecodedText, DecodedTextLength,
                      RecoveredText );

...

// Conversion for Convenience
// Don't be fooled:
//   RecoveredFeatures = static_cast<unsigned int>
//   ( *RecoveredText );
//   only converts byte[ 0 ], not bytes[ 0 - 4 ]
unsigned int RecoveredFeatures =
   *(reinterpret_cast<unsigned int*>( RecoveredText ) );

// Output
if( FEATURE_MAGIC != (RecoveredFeatures & FEATURE_MAGIC_MASK ) )
  { throw std::string("RecoveredFeatures: Magic:
                       Invalid Product Key"); }

Securely Saving Key or Activation State to the Registry

Program Activation state can be securely saved to the Windows Registry. Visit CodeGuru's article, "An AES Encrypting Registry Class," for a discussion and implementation.

Product Keys Based on Elliptic Curve Cryptography

A Note on User Interface Design

Thomas Holte provides an article for entering Product Keys. See MFC Extension Class CProductKey.

The reader is highly encouraged to employ techniques of quality User Interface design. For example, Sybex's CCNA Virtual Lab, Platinum Edition displays the following ("Unknown Error -52" is simply not acceptable). The author is relieved he purchased the Platinum Edition, and not the Aluminum, Brass, or Silver Edition.

And an example from ACDSee 6.0. ACDSee presumably moved the script location of the validation and update routines on its servers over time.

Summary

Although this article does not present a concrete implementation of an Optimal Compact Product Key System, the groundwork for such a system has been presented. By using ECIES as specified in IEEE 1363 and ANSI X9.63, and implemented in Crypto++, one can side step most patent issues involved with Elliptic Curve Cryptography. However, there may be other implications in the application of ECC to the realm of Product Keys and Product Activations.

A to-do list would include the following:

  • Create a Class ProductKeyEncoder (to use in place of the Base32 or Base64 Encoder)
  • Remove redundant byte structure from a Base32-encoded Ciphertext object; add the before structure with Base32 decoding
  • Use of Signatures with Recovery versus PKI

Acknowledgments

  • Wei Dai for Crypto++ and his invaluable help on the Crypto++ mailing list
  • Dr. A. Brooke Stephens, who laid my Cryptographic foundations
  • Marcel Martin for his work on ECB to facilitate this article; and critiques of the article's EC description correctness
  • Jason Smethers for his Elliptic Curve Sample, which served as an early basis for this article

Revisions

  • 11.10.2006 Original Release


About the Author

Jeffrey Walton

In the past, I have worked as an IT consultant for County Government (Anne Arundel County), the Nuclear Energy Institute, the Treasury Department, and Social Security Administration as a Network Engineer and System Administrator. Primary Administration experience includes Microsoft Windows and Novell Netware, with additional exposure and familiarity with Mac and Linux OSes. Previous to the US government, I was a programmer for a small business using Microsoft Visual Languages (Basic 5.0, 6.0, and C++ 5.0, 6.0) and Scripting Languages. An undergraduate degree (BS in Computer Science) was obtained from University of Maryland, Baltimore County. Graduate work includes a Masters of Science (Computer Science) from Johns Hopkins University (expected before 2009). Training and Certifications include Microsoft, Checkpoint, and Cisco.

Downloads

Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Live Event Date: October 29, 2014 @ 11:00 a.m. ET / 8:00 a.m. PT Are you interested in building a cognitive application using the power of IBM Watson? Need a platform that provides speed and ease for rapidly deploying this application? Join Chris Madison, Watson Solution Architect, as he walks through the process of building a Watson powered application on IBM Bluemix. Chris will talk about the new Watson Services just released on IBM bluemix, but more importantly he will do a step by step cognitive …

  • QA teams don't have time to test everything yet they can't afford to ship buggy code. Learn how Coverity can help organizations shrink their testing cycles and reduce regression risk by focusing their manual and automated testing based on the impact of change.

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds