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.

More by Author

Must Read