Elliptic Curve Digital Signature Algorithm

From Crypto++ Wiki
Jump to: navigation, search

Elliptic Curve Digital Signature Algorithm, or ECDSA, is one of three digital signature schemes specified in FIPS-186. The current revision is Change 3, dated June 2009. If interested in the non-elliptic curve variant, see Digital Signature Algorithm.

Before operations such as key generation, signing, and verification can occur, we must chose a field and suitable domain parameters. For demonstration purposes, this example will use Fp as the field. This means one template argument to ECDSA will include ECP. If we were using F2m, the template argument would be EC2N.

Crypto++ supplies a set of standard curves approved by ANSI, Brainpool, and NIST. Crypto++ does not provide curve generation functionality. If you need a custom curve, see Elliptic Curve Builder.

Crypto++ Validation

Crypto++'s performs ECDSA validation in ValidateECDSA from valdat2.cpp. Both Fp and F2m are demonstrated.

Choice of Fields

ECDSA is defined over both prime fields (Fp) and binary fields (F2m). To operate over a prime field, use ECP:

ECDSA<ECP, SHA1>::Signer signer;
ECDSA<ECP, SHA1>::Verifier verifier;

For binary fields, specify EC2N:

ECDSA<EC2N, SHA1>::Signer signer;
ECDSA<EC2N, SHA1>::Verifier verifier;

Key Generation

The following discusses public and private key generation.

Private Key

To generate a private key for signing, perform the following. Note that Initialize functions which take a RandomNumberGenerator will generate a private key.

AutoSeededRandomPool prng;
ECDSA<ECP, SHA1>::PrivateKey privateKey;

privateKey.Initialize( prng, ASN1::secp160r1() );
bool result = privateKey.Validate( prng, 3 );
if( !result ) { ... }

An alternative to using a random number generator and OID is shown below. In the code below, the OID is used to construct an object for domain parameters.

ECDSA<ECP, SHA1>::PrivateKey privateKey;
DL_GroupParameters_EC<ECP> params(ASN1::secp160r1());

privateKey.Initialize(prng, params);

Once the private key has been generated, the private exponent can be retrieved as follows.

const Integer& x = privateKey.GetPrivateExponent()

Calling GenerateRandom as shown below will not work as expected - it will cause a NotImplemented exception with the message, DL_GroupParameters_EC<EC>: curve generation is not implemented yet.

AutoSeededRandomPool prng;

ECDSA<ECP, SHA1>::PrivateKey privateKey;
privateKey.GenerateRandom(prng, g_nullNameValuePairs);

Be careful when working with ECDSA's parameterized arguments. The following will save and load properly, despite the difference between SHA1 and SHA256. When a key is saved or loaded, it is done so in PKCS #8 (private key) or X509 format (public key). The key formats are ignorant to the objects which use them (such as ECDSA).

ECDSA<ECP, SHA1>::PrivateKey k1;
k1.Initialize( prng, secp160r1() );

const Integer& x1 = k1.GetPrivateExponent();
cout << "K1: " << std::hex << x1 << endl;

ByteQueue queue;
k1.Save(queue);

ECDSA<ECP, SHA256>::PrivateKey k2;
k2.Load(queue);

const Integer& x2 = k2.GetPrivateExponent();
cout << "K2: " << std::hex << x2 << endl;
$ ./cryptopp-test.exe
K1: fb468a2d41678c92b5b41b25f4e48c96700278e2h
K2: fb468a2d41678c92b5b41b25f4e48c96700278e2h

Signer

To generate a private key for signing using a Signer, perform the following.

AutoSeededRandomPool prng;
ECDSA<ECP, SHA1>::Signer signer;

signer.AccessKey().Initialize( prng, ASN1::secp160r1() );
bool result = signer.AccessKey().Validate( prng, 3 );
if( !result ) { ... }

We can also use a PrivateKey to initialize a signer:

ECDSA<ECP, SHA1>::PrivateKey privateKey
...
ECDSA<ECP, SHA1>::Signer signer(privateKey);

bool result = signer.AccessKey().Validate( prng, 3 );
if( !result ) { ... }

Public Key

To derive a public key from the private key, perform the following.

privateKey.MakePublicKey( publicKey );

bool result = publicKey.Validate( prng, 3 );
if( !result ) { ... }

Once the public key has been derived, the public element can be retrieved as follows.

const ECP::Point& q = publicKey.GetPublicElement()

const Integer& qx = q.x;
const Integer& qy = q.y;

Verifier

To use a high level verifier, perform the following.

ECDSA<ECP, SHA1>::PublicKey verifier( publicKey );
signer.AccessKey().Verify( prng, 3 );

Though unlikely, we could perform the following if the signer object were handy (the same signer and verifier usually do not exist in the same program).

ECDSA<ECP, SHA1>::PrivateKey privateKey = ...;
ECDSA<ECP, SHA1>::Signer signer( privateKey );
...

ECDSA<ECP, SHA1>::PublicKey verifier( signer );
bool result = verifier.AccessKey().Verify( prng, 3 );
if(!result) { ... }

Key Initialization

The following demonstrates public and private key initialization using previously generated parameters.

Private Key

Given a curve and the private exponent, perform the following to initialize the private key.

ECDSA<ECP, SHA1>::PrivateKey privateKey;
const Integer x = ...;       // private exponent

privateKey.Initialize( ASN1::secp160r1(), x );

bool result = privateKey.Validate( prng, 3 );
if( !result ) { ... }

Public Key

Similar to a private key, a public key is initialized as follows using the public element.

ECDSA<ECP, SHA1>::PublicKey publicKey;
const ECP::Point q = ...;    // public element

publicKey.Initialize( ASN1::secp160r1(), q );

bool result = publicKey.Validate( prng, 3 );
if( !result ) { ... }

Key Persistence

The following uses Load and Save to read and write a PKCS #8 private or X509 public keys. For a complete discussion of PKCS #8 private keys and X509 public keys, see Keys and Formats.

Private Key

Given a public key and private key, we perform the following to save a private key to disk.

// Save private key in PKCS #8 format
FileSink fs( "private.ec.der", true /*binary*/ );
privateKey.Save( fs );

To load the private key from disk, perform the following:

// Load private key in PKCS #8 format
FileSource( "private.ec.der", true /*pump all*/ );
privateKey.Load( fs );

bool result = privateKey.Validate( prng, 3 );
if( !result ) { ... }

Signer

If working with a higher level ECDSA<ECP, SHA1>::Signer, use AccessKey to access the private key and call Load or Save on the returned object.

ECDSA<ECP, SHA1>::Signer signer( privateKey );

ByteQueue queue;
signer.AccessKey().Save( queue );

A ByteQueue is convenient for transferring a private key in memory. To save to disk, we can use a FileSink.

FileSink fs( "private.ec.der", true /*binary*/ );
signer.AccessKey().Save( fs );

Saving the key to disk using an ASCII encoding is shown below.

HexEncoder encoder( new FileSink( "private.ec.der", false /*binary*/ ));
signer.AccessKey().Save( encoder );

Public Key

Public keys are persisted similar to private keys.

// Save public key in X.509 format
FileSink fs( "public.ec.der", true /*binary*/ );
publiceKey.Save( fs );
// Load public key in X.509 format
FileSource fs( "public.ec.der", true /*pump all*/ );
publiceKey.Load( fs );

bool result = publicKey.Validate( prng, 3 );
if( !result ) { ... }

Verifier

If working with a higher level ECDSA<ECP, SHA1>::Verfier, use AccessKey to access the public key and call Load or Save on the returned object.

ECDSA<ECP, SHA1>::Verifier verifier( publicKey );

ByteQueue queue;
verifier.AccessKey().Save( queue );

A ByteQueue is convenient for transferring a public key in memory. To save to disk, we can use a FileSink.

FileSink fs( "public.ec.der", true /*binary*/ );
verifier.AccessKey().Save( fs );

Saving the key to disk using an ASCII encoding is shown below.

HexEncoder encoder( new FileSink( "public.ec.der", false /*binary*/ ));
verifier.AccessKey().Save( encoder );

Message Signing

Signing a string is as follows. Note that a PRNG is required because the Digital Signature Standard specifies a per-message random value.

ECDSA<ECP, SHA1>::PrivateKey privateKey;
privateKey.Load(...);

AutoSeededRandomPool prng;
string message = "Yoda said, Do or do not. There is no try.";
string signature;

StringSource s( message, true /*pump all*/,
    new SignerFilter( prng,
        ECDSA<ECP,SHA1>::Signer( privateKey ),
        new StringSink( signature )
    ) // SignerFilter
); // StringSource

The previous signing example used filters, while the example below uses traditional C-style function calls. After completion, signature will hold a properly sized binary string with the signature of the message.

ECDSA<ECP, SHA1>::Signer signer;
signer.AccessKey().Initialize( prng, secp160r1() );

string message = "Do or do not. There is no try.";

// Determine maximum size, allocate a string with the maximum size
size_t siglen = signer.MaxSignatureLength();
string signature(siglen, 0x00);

// Sign, and trim signature to actual size
siglen = signer.SignMessage( prng, (const byte*)message.data(), message.size(), (byte*)signature.data() );
signature.resize(siglen);

Message Verification

ECDSA is a Signature Scheme with Appendix. This means that the original message must be presented to the verifier function. Verification is performed as follows.

By default, the filter uses flags equal to SIGNATURE_AT_BEGIN | PUT_RESULT, so a boolean value is placed in result. See the SignatureVerificationFilter page for details on the filter and the flags.

ECDSA<ECP, SHA1>::PublicKey publicKey;
publicKey.Load(...);

// Result of the verification process
bool result = false;

// Exactly what was signed in the previous step
string message = ...;
// Output from the signing operation in the previous step
string signature = ...;

StringSource ss( signature+message, true /*pump all*/,
    new SignatureVerificationFilter(
        ECDSA<ECP,SHA1>::Verifier(publicKey),
        new ArraySink( (byte*)&result, sizeof(result) )
    ) // SignatureVerificationFilter
);

// Verification failure?
if( !result ) {...}

If we wanted the SignatureVerificationFilter to throw on verification failure, the code is shown below. Note we should be prepared to catch a SignatureVerificationFailed exception.

static const int VERIFICATION_FLAGS = SIGNATURE_AT_BEGIN | THROW_EXCEPTION;
StringSource ss( signature+message, true /*pump all*/,
    new SignatureVerificationFilter(
        ECDSA<ECP,SHA1>::Verifier(publicKey),
        NULL, /* No need for attached filter */
        VERIFICATION_FLAGS
    ) // SignatureVerificationFilter
);

The previous verification example used filters, while the example below uses traditional C-style function calls. It builds upon the signing example above.

// Sign, and trim signature to actual size
siglen = signer.SignMessage( prng, (const byte*)message.data(), message.size(), (byte*)signature.data() );
signature.resize(siglen);

ECDSA<ECP, SHA1>::PublicKey publicKey;
publicKey.Load(...);
ECDSA<ECP, SHA1>::Verifier verifier(publicKey);

bool result = verifier.VerifyMessage( (const byte*)message.data(), message.size(), (const byte*)signature.data(), signature.size() );
if(result)
  cout << "Verified signature on message" << endl;
else
  cerr << "Failed to verify signature on message" << endl;

Domain Parameters

At times, it may be useful to dump domain parameters. We can use a single function to print both the public key and private key by accepting DL_GroupParameters_EC<ECP> as a parameter to the function since (not suprisingly) it is common to both objects.

ECDSA<ECP, SHA1>::PublicKey publicKey;
publicKey.Load(...);

PrintDomainParameters( publicKey );
void PrintDomainParameters( const DL_GroupParameters_EC<ECP>& params )
{
    cout << "Modulus:" << endl;
    cout << " " << params.GetCurve().GetField().GetModulus() << endl;
    
    cout << "Coefficient A:" << endl;
    cout << " " << params.GetCurve().GetA() << endl;
    
    cout << "Coefficient B:" << endl;
    cout << " " << params.GetCurve().GetB() << endl;
    
    cout << "Base Point:" << endl;
    cout << " X: " << params.GetSubgroupGenerator().x << endl; 
    cout << " Y: " << params.GetSubgroupGenerator().y << endl;
    
    cout << "Subgroup Order:" << endl;
    cout << " " << params.GetSubgroupOrder() << endl;
    
    cout << "Cofactor:" << endl;
    cout << " " << params.GetCofactor() << endl;    
}

A typical output from a 160 bit curve is shown below.

Modulus:
 1461501637330902918203684832716283019653785059327
Coefficient A:
 1461501637330902918203684832716283019653785059324
Coefficient B:
 163235791306168110546604919403271579530548345413
Base Point
 X: 425826231723888350446541592701409065913635568770
 Y: 203520114162904107873991457957346892027982641970
Subgroup Order:
 1461501637330902918203687197606826779884643492439
Cofactor:
 1

Private Exponent:
 542053241409584231606641348297804563147909139481

Public Element:
 X: 1330662819286567003101256740359821157367793328918
 Y: 294709699265533759639226491877167235372762906422

Signature Sizes

The following table was compiled to offer a comparison of domain parameters and relative signature sizes. Crypto++ Curve specifies the programmatic name for the approved curve. The signature sizes are displayed in bytes.

Crypto++ Curve Signature Size
secp112r1 28
secp128r1 32
secp160r1 42
secp192r1 48
secp224r1 56
secp256r1 64
secp384r1 96
secp521r1 132

Downloads

ECDSA-Test.zip - Crypto++ ECDSA sample program using filters

ECDSA-Test-C.zip - Crypto++ ECDSA sample program using C Style API