Initialising ECC private key with external random number generator

[Patrick]

Hello all,

I need to be able to initialise an ECC private key with entropy coming
from a source which doesn't support the
CryptoPP::RandomNumberGenerator interface. All the ECC examples I have
found use:

#define ECC_CURVE CryptoPP::ASN1::secp256k1()
CryptoPP::ECIES< ECC_ALGORITHM >::PrivateKey PrivateKey;
CryptoPP::AutoSeededRandomPool rng;
PrivateKey.Initialize( rng, ECC_CURVE );

or something similar to create the private key. I've traced through
the code this calls and tried to generate a way of doing this without
passing an rng, as shown below. The code seems to work but I'm a
little nervous and was hoping for a free code review from those more
familiar with the library. Apologies for the cheek but if someone can
confirm the following is not fatally flawed I would be very grateful?

Thanks for looking,
Patrick

PS : thank you, Jeffrey Walton, for your codeProject examples (if you
happen to read this)

//following code butchered from CryptoPP functions:
// DL_PrivateKeyImpl -> void GenerateRandom(RandomNumberGenerator
&rng, const NameValuePairs &params)
// void Integer::Randomize(RandomNumberGenerator &rng, const Integer
&min, const Integer &max)
// void Integer::Randomize(RandomNumberGenerator &rng, size_t nbits)

#define ECC_ALGORITHM CryptoPP::ECP
#define ECC_CURVE CryptoPP::ASN1::secp256k1()

//get the range of the ECC exponent
CryptoPP::Integer themin = CryptoPP::Integer::One();
CryptoPP::Integer themax =
CryptoPP::DL_GroupParameters_EC<CryptoPP::ECP>(ECC_CURVE).GetMaxExponent();
CryptoPP::Integer Range = themax - themin;
//calc the number of bits of randomness required
const unsigned int nbits = Range.BitCount();
const size_t nbytes = nbits/8 + 1;
//generate random value within the range and assign to x
CryptoPP::Integer x;
do
{
//will use other source of randomness here
CryptoPP::AutoSeededRandomPool rng;
CryptoPP::SecByteBlock buf(nbytes);
rng.GenerateBlock( buf, buf.SizeInBytes() );

if (nbytes)
buf[0] = (byte)CryptoPP::Crop(buf[0], nbits % 8);
x = CryptoPP::Integer(buf, nbytes,
CryptoPP::Integer::UNSIGNED);
}while (x > Range);
x += themin;
//set up the private key
CryptoPP::ECIES< ECC_ALGORITHM >::PrivateKey PrivateKey;
PrivateKey.Initialize( ECC_CURVE, x );

[zooko]

Hi there Patrick. I needed to do the same thing in my pycryptopp
project [1] -- to generate an ECDSA key pair deterministically from a
seed. Here is the ticket for this feature request: [2].

Here's the relevant source code from what I did. It has not yet been
committed to pycryptopp trunk. I intend at some point to publicize
this, request comments from other experts, submit patches to get such
a thing included in Crypto++ itself, and write unit tests with test
vectors.

Regards,

Zooko

[1] http://allmydata.org/trac/pycryptopp
[2] http://allmydata.org/trac/pycryptopp/ticket/2
---
http://allmydata.org -- Tahoe, the Least-Authority Filesystem
http://allmydata.com -- back up all your files for $5/month

------- begin appended C++ source code
OID curve;
Integer grouporder;
byte privexpbytes[24] = {0};
Integer privexponent;
privexponent.Decode(privexpbytes, sizeof(privexpbytes)); assert
(priveexponent == 0); // just checking..

curve = ASN1::secp192r1();
grouporder = DL_GroupParameters_EC<ECP>(curve).GetGroupOrder();
Tiger t;

static const byte* TAG_AND_SALT = reinterpret_cast<const byte*>( \
"102:pycryptopp v0.5.3 key derivation algorithm using Tiger
hash to generate ECDSA 192-bit secret exponents," \
"16:H1yGNvUONoc0FD1d," \
);

t.Update(TAG_AND_SALT, sizeof(TAG_AND_SALT));
t.Update(reinterpret_cast<const byte*>(seed), seedlen);
t.TruncatedFinal(privexpbytes, Tiger::DIGESTSIZE);
privexponent.Decode(privexpbytes, sizeof(privexpbytes));

while ((privexponent >= grouporder) || (privexponent == 0)) {
Tiger t2;
t2.Update(TAG_AND_SALT, sizeof(TAG_AND_SALT));
t2.Update(privexpbytes, sizeof(privexpbytes));
t2.TruncatedFinal(privexpbytes, Tiger::DIGESTSIZE);
privexponent.Decode(privexpbytes, sizeof(privexpbytes));
}

SigningKey* signer = new SigningKey;
signer->k = ECDSA<ECP, Tiger>::Signer(curve, privexponent);

[Jeffrey Walton]

Hi Patrick,

> entropy coming from a source which doesn't support the

> CryptoPP::RandomNumberGenerator...
I'm not sure what exactly you're trying to accomplish, but here goes...

* the library offers a NullRNG object if you need to satisfy an API,
but don't have a pseudo random source. It is located in cryptlib
classes.

* given a seed, you can use IncorporateEntropy (const byte *input,
size_t length) of RandomNumberGenerator to try and keep objects in
lock step. I suppose you would use this case if you are trying to
create the same key given the same inputs in different libraries
(similar to validation parameters?). See
http://cryptopp.com/docs/ref/class_random_number_generator.html

Jeff

[zooko]

On Sep 1, 2008, at 11:42 AM, Jeffrey Walton wrote:

> I'm not sure what exactly you're trying to accomplish, but here
> goes...

The goal is to generate a 192-bit ECC private key from a 96-bit
secret value, such that

a) anyone who starts with the same 96-bit secret value can regenerate
the same 192-bit ECC private key, and

b) anyone who doesn't start with the same 96-bit secret value
can't. ;-)

> * the library offers a NullRNG object if you need to satisfy an API,
> but don't have a pseudo random source. It is located in cryptlib
> classes.

This would fail criterion b, of course.

> * given a seed, you can use IncorporateEntropy (const byte *input,
> size_t length) of RandomNumberGenerator to try and keep objects in
> lock step. I suppose you would use this case if you are trying to
> create the same key given the same inputs in different libraries
> (similar to validation parameters?). See
> http://cryptopp.com/docs/ref/class_random_number_generator.html

If I recall correctly, I tried this first, and was surprised to learn
that it actually went ahead and incorporated other entropy in
addition to the seed I had given it, thus failing criterion a.

Also, I looked at the source code of the built-in RNG, and it seemed
like it would be potentially more complicated to document (e.g. to
facilitate independent, compatible re-implementation) than the
simpler algorithm that I posted in my previous note.

The fact that Patrick came up with a very similar algorithm
independently to solve a similar problem is encouraging in that way.

By the way, we're having a contest in which anyone who finds a
significant security flaw in our decentralized file-sharing system
gets a customized t-shirt with their exploit printed on it and a big
thank-you from us:

http://hacktahoe.org

Regards,

Zooko