Sorry for the late reply. In case you haven't already figured it out, there are
two problems with your code. The subgroup order you pass in to
DL_PrivateKey_EC::Initialize() is supposed to be prime (i.e. r instead of n),
and you should be using a random integer instead of 2 as the private exponent.
You can use the fourth overloaded Initialize() function of DL_PrivateKey_EC to
have it create a random exponent for you.
----- Original Message -----
From: Jeffrey Walton
To: Crypto
Sent: Sunday, November 19, 2006 5:35 AM
Subject: EC Key Validation Failure at Level 1
Hi All,
I've generated Domain Parameters T as shown below. They pass the Certicom
Validation Primitive (Section 3.1.1.2.1), but Crypto++ Validate fails even at
level 1 ('weaks keys and such' are not tested). Any ideas? The curve does
Validate at Level 3.
What I see:
Generated Cofactor f = 2. When passed into Crypto++ (through parameter k):
Sub Group Order n: 5186044226273133563273371929482314
Cofactor k: 1
Max Exponent m: 5186044226273133563273371929482313
Private Exp e: 2
I _ASSUMED_ k is the cofactor because m_k is returned through GetCofactor().
CryptoPP::ECP ec( p, a, b );
CryptoPP::ECIES< CryptoPP::ECP >::PrivateKey PrivateKey;
CryptoPP::ECIES< CryptoPP::ECP >::PublicKey PublicKey;
// Curve Initialization and Key Generation
PrivateKey.Initialize( ec, CryptoPP::ECP::Point( x, y ), n, f );
PrivateKey.MakePublicKey( PublicKey );
Jeff
p appears to be prime... OK
a is in the interval [0, p-1]... OK
b is in the interval [0, p-1]... OK
x is in the interval [0, p-1]... OK
y is in the interval [0, p-1]... OK
Discriminant != 0 (mod p)... OK
Base Point G(x,y) is on E(GF(p))... OK
n appears to be prime... OK
h <= 4... OK
h = FLOOR((SQRT(p)+1)^2 / n)... OK
nG = O... OK
p^B != 1 (mod n) for any 1 <= B < 20... OK
n*h != p... OK
Public Key:
EC Parameter p: 5186044226273133699992338255370617
112 bits
EC Parameter a: 2757214153910325245522685003043920
EC Parameter b: 1175514487796170316401010612487484
Base Point x: 4052281606118159132919127812645338
Base Point y: 1465818003156267745766136355594228
Private Key:
Base Point x: 4052281606118159132919127812645338
Base Point y: 1465818003156267745766136355594228
Group Order r: 5186044226273133563273371929482314
Sub Group Order n: 5186044226273133563273371929482314
Cofactor k: 1
Max Exponent m: 5186044226273133563273371929482313
Private Exp e: 2
Error: Private Key Validation Failure
===================================
Source File
===================================
// Runtime Includes
#include <iostream>
// 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 "nbtheory.h" // VerifyPrime and ModularRoot
// Solves y^2 === x^3 + a*x + b (mod p)
CryptoPP::Integer Y(CryptoPP::Integer x, CryptoPP::Integer a,
CryptoPP::Integer b, CryptoPP::Integer p);
// Returns 4*a^3 + 27*b^2 (mod p) (Discriminant)
CryptoPP::Integer D( CryptoPP::Integer a, CryptoPP::Integer b,
CryptoPP::Integer p );
void Validate( CryptoPP::Integer p, CryptoPP::Integer a, CryptoPP::Integer b,
CryptoPP::Integer x, CryptoPP::Integer y,
CryptoPP::Integer n, CryptoPP::Integer k );
// Debug
void DumpPublicKey( const CryptoPP::ECIES< CryptoPP::ECP >::PublicKey&
PublicKey );
void DumpPrivateKey( const CryptoPP::ECIES< CryptoPP::ECP >::PrivateKey&
PrivateKey );
int main(int argc, char* argv[]) {
CryptoPP::AutoSeededRandomPool rng;
try {
// User Defined Domain Parameters
CryptoPP::Integer p("5186044226273133699992338255370617");
// a
CryptoPP::Integer a("2757214153910325245522685003043920");
// b
CryptoPP::Integer b("1175514487796170316401010612487484");
// Cofactor (f) and Order (r)
CryptoPP::Integer f = 2;
CryptoPP::Integer r("2593022113136566781636685964741157");
// n: n = f * r
CryptoPP::Integer n = f * r;
// x, y: Base Point G
CryptoPP::Integer x("-1133762620154974567073210442725279");
CryptoPP::Integer y("1465818003156267745766136355594228");
// bring back to the interval [0, p-1]
a %= p; b %= p; x %= p; y %= p;
CryptoPP::ECP ec( p, a, b );
CryptoPP::ECIES< CryptoPP::ECP >::PrivateKey PrivateKey;
CryptoPP::ECIES< CryptoPP::ECP >::PublicKey PublicKey;
// Curve Initialization and Key Generation
PrivateKey.Initialize( ec, CryptoPP::ECP::Point( x, y ), n, f );
PrivateKey.MakePublicKey( PublicKey );
Validate( p, a, b, x, y, r, f ); std::cout << std::endl;
DumpPublicKey( PublicKey ); std::cout << std::endl;
DumpPrivateKey( PrivateKey ); std::cout << std::endl;
if( false == ec.ValidateParameters( rng, 3 ) )
{ throw std::string("EC Parameter Validation Failure"); }
if( false == PrivateKey.Validate( rng, 1 ) )
{ throw std::string("Private Key Validation Failure"); }
if( false == PublicKey.Validate( rng, 1 ) )
{ throw std::string("Public Key Validation Failure"); }
}
catch( CryptoPP::Exception& e )
{ std::cerr << "Error: " << e.what() << std::endl; }
catch( std::string& s )
{ std::cerr << "Error: " << s << std::endl; }
catch (...)
{ std::cerr << "Unknown Error" << std::endl; }
return 0;
}
void DumpPublicKey( const CryptoPP::ECIES< CryptoPP::ECP >::PublicKey&
PublicKey )
{
std::cout << "Public Key:" << std::endl;
CryptoPP::Integer p =
PublicKey.GetGroupParameters().GetCurve().FieldSize();
std::cout << " EC Parameter p: " << p << std::endl;
std::cout << " " << p.BitCount() << " bits" << std::endl;
CryptoPP::Integer a = PublicKey.GetGroupParameters().GetCurve().GetA();
std::cout << " EC Parameter a: " << a << std::endl;
CryptoPP::Integer b = PublicKey.GetGroupParameters ().GetCurve().GetB();
std::cout << " EC Parameter b: " << b << std::endl;
CryptoPP::Integer x =
PublicKey.GetGroupParameters().GetSubgroupGenerator().x;
std::cout << " Base Point x: " << x << std::endl;
CryptoPP::Integer y = PublicKey.GetGroupParameters
().GetSubgroupGenerator().y;
std::cout << " Base Point y: " << y << std::endl;
// CryptoPP::Integer e =
PublicKey.GetGroupParameters().GetPublicExponent();
// std::cout << " Public Exp e: " << e << std::endl;
}
void DumpPrivateKey( const CryptoPP::ECIES< CryptoPP::ECP >::PrivateKey&
PrivateKey )
{
std::cout << "Private Key:" << std::endl;
CryptoPP::Integer x =
PrivateKey.GetGroupParameters().GetSubgroupGenerator().x;
std::cout << " Base Point x: " << x << std::endl;
CryptoPP::Integer y = PrivateKey.GetGroupParameters
().GetSubgroupGenerator().y;
std::cout << " Base Point y: " << y << std::endl;
CryptoPP::Integer r = PrivateKey.GetGroupParameters().GetGroupOrder();
std::cout << " Group Order r: " << r << std::endl;
CryptoPP::Integer n = PrivateKey.GetGroupParameters().GetSubgroupOrder();
std::cout << " Sub Group Order n: " << n << std::endl;
CryptoPP::Integer k = PrivateKey.GetGroupParameters().GetCofactor();
std::cout << " Cofactor k: " << k << std::endl;
CryptoPP::Integer m =
PrivateKey.GetAbstractGroupParameters().GetMaxExponent();
std::cout << " Max Exponent m: " << m << std::endl;
CryptoPP::Integer e = PrivateKey.GetPrivateExponent();
std::cout << " Private Exp e: " << e << std::endl;
}
// Standards for Efficient Cryptography
// SEC 1: Elliptic Curve Cryptography
// Elliptic Curve Domain Parameters over GF(p) Validation, pp 17-18
void Validate( CryptoPP::Integer p, CryptoPP::Integer a, CryptoPP::Integer b,
CryptoPP::Integer x, CryptoPP::Integer y,
CryptoPP::Integer n, CryptoPP::Integer h )
{
CryptoPP::Integer t;
CryptoPP::AutoSeededRandomPool rng;
// SEC1, Section 3.1.1.2.1, page 18
// Check 1: p is an odd prime...
if( true == CryptoPP::VerifyPrime( rng, p, 6 ) )
{
std::cout << " p appears to be prime... OK" << std::endl;
}
else
{
std::cout << " ** p is composite **" << std::endl;
}
// SEC1, Section 3.1.1.2.1, page 18
// Check 1: [p] ... such that t = { 56, 64, ..., 192, 256 }
// This needs to be tightened...
if( p.BitCount() / 2 >= 56 )
{
// { std::cout << " t = { 56, 64, 80, 96, 112, 128, 192, 256}... OK"
<< std::endl; }
}
else
{
{ std::cout << " ** Security Level t may be too small **" <<
std::endl; }
}
// SEC1, Section 3.1.1.2.1, page 18
// Check 2: a, b, g_x, g_y = [0, p-1]
t = p - 1;
if( a >= 0 && a <= t )
{ std::cout << " a is in the interval [0, p-1]... OK" << std::endl;
}
else
{
std::cout << " ** a is not in the interval [0, p-1] **" << std::endl;
std::cout << " a: " << a << std::endl;
}
if( b >= 0 && b <= t )
{ std::cout << " b is in the interval [0, p-1]... OK" << std::endl; }
else
{
std::cout << " ** b is not in the interval [0, p-1] **" <<
std::endl;
std::cout << " b: " << b << std::endl;
}
if( x >= 0 && x <= t )
{ std::cout << " x is in the interval [0, p-1]... OK" << std::endl; }
else
{
std::cout << " ** x is not in the interval [0, p-1] **" <<
std::endl;
std::cout << " x: " << x << std::endl;
}
if( y >= 0 && y <= t )
{ std::cout << " y is in the interval [0, p-1]... OK" << std::endl; }
else
{
std::cout << " ** y is not in the interval [0, p-1] **" <<
std::endl;
std::cout << " y: " << y << std::endl;
}
// SEC1, Section 3.1.1.2.1, page 18
// Check 3: 4*a^3 + 27*b^2 != 0 (mod p)
t = D( a, b, p );
if( 0 != t )
{
std::cout << " Discriminant != 0 (mod p)... OK" << std::endl;
}
else
{
std::cout << " ** Discriminant == 0 (mod p) **" << std::endl;
}
// SEC1, Section 3.1.1.2.1, page 18
// Check 4: y^2 == x^3 + a*x + b (mod p)
t = Y( x, a, b, p );
if( t % p != y % p )
{
std::cout << " Base Point G(x,y) is on E(GF(p))... OK" << std::endl;
}
else
{
std::cout << " ** Base Point G(x,y) is not on E(GF(p)) **" <<
std::endl;
std::cout << " y^2: " << y.Squared () % p << std::endl;
std::cout << " f(y^2): " << (x*(x.Squared()+1)+b)%p << std::endl;
}
// SEC1, Section 3.1.1.2.1, page 18
// Check 5: n is an odd prime...
if( true == CryptoPP::VerifyPrime( rng, n, 6 ) )
{
std::cout << " n appears to be prime... OK" << std::endl;
}
else
{
std::cout << " ** n is composite **" << std::endl;
}
// SEC1, Section 3.1.1.2.1, page 18
// Check 6: h <= 4 ...
if( h <= 4 )
{
std::cout << " h <= 4... OK" << std::endl;
}
else
{
std::cout << " ** h is too large **" << std::endl;
std::cout << " h: " << h << std::endl;
}
// SEC1, Section 3.1.1.2.1, page 18
// Check 6: ... h = FLOOR( (SQRT(P)+1)^2 / n )
t = p.SquareRoot() + 1;
t = t.Squared() / n;
if( h == t )
{
std::cout << " h = FLOOR((SQRT(p)+1)^2 / n)... OK" << std::endl;
}
else
{
std::cout << " ** h != FLOOR( (SQRT(p)+1)^2 / n ) **" << std::endl;
std::cout << " f(h): " << t << std::endl;
}
// SEC1, Section 3.1.1.2.1, page 18
// Check 7: n*G = O (O is Point of Infinity)
CryptoPP::ECP ec( p, a, b );
if( ec.Identity() == ec.ScalarMultiply( CryptoPP::ECPPoint(x, y), n ) )
{
std::cout << " nG = O... OK" << std::endl;
}
else
{
std::cout << " ** nG != O **" << std::endl;
}
// SEC1, Section 3.1.1.2.1, page 18
// Check 8: q^B != 1 (mod n) for any 1 <= B < 20 ...
bool bResult = true;
for( unsigned int B = 1; B < 20 && true == bResult; B++ )
{
bResult |= ( 1 != CryptoPP::a_exp_b_mod_c( p, B, p ) );
}
if( true == bResult )
{
std::cout << " p^B != 1 (mod n) for any 1 <= B < 20... OK" <<
std::endl;
}
else
{
std::cout << " ** p^B = 1 (mod n) for B = " << B << " **" <<
std::endl;
}
// SEC1, Section 3.1.1.2.1, page 18
// Check 8: ... n*h != p
if( p != n * h )
{
std::cout << " n*h != p... OK" << std::endl;
}
else
{
std::cout << " ** n*h = p **" << std::endl;
}
}
CryptoPP::Integer Y( CryptoPP::Integer x, CryptoPP::Integer a,
CryptoPP::Integer b, CryptoPP::Integer p )
{
x %= p; a %= p; b %= p;
CryptoPP::Integer y = CryptoPP::a_exp_b_mod_c( x, 3, p );
y += a * x + b;
return CryptoPP::ModularSquareRoot( y % p, p );
}
CryptoPP::Integer D( CryptoPP::Integer a, CryptoPP::Integer b,
CryptoPP::Integer p )
{
CryptoPP::Integer d = 4 * CryptoPP::a_exp_b_mod_c( a, 3, p );
d += 27 * b.Squared();
return d % p;
}
