dpval.cpp

用来验证椭圆曲线的Parameters 是否正确

// DPVal.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"

// 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, ModularRoot,
                        //   and ModularExponentiation

// 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
        //    This is Curve P-112 from NIST
        CryptoPP::Integer p("6277101735386680763835789423207666416083908700390324961279");

        // a: fixed to speed underlying operations
        CryptoPP::Integer a("-3");
        // b: satisfies b^2 * c === -27 (mod p)
        CryptoPP::Integer b("0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1");

        // Cofactor (f) and Order (r)
        CryptoPP::Integer f = 1;
        CryptoPP::Integer r("6277101735386680763835789423176059013767194773182842284081");

        // n: n = f * r
        CryptoPP::Integer n = f * r;

        // s: Input seed to SHA-1 algorithm
        //    Not used (included for completeness)
        CryptoPP::Integer s("0x3045ae6fc8422f64ed579528d38120eae12196d5");
        // c: Output of SHA-1 Algorithm
        //    Not used (included for completeness)
        CryptoPP::Integer c("0x3099d2bbbfcb2538542dcd5fb078b6ef5f3d6fe2c745de65");

        // x, y: Base Point G
        CryptoPP::Integer x("0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012");
        CryptoPP::Integer y("0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811");

        //Interval [0, p-1]
        a %= p;     b %= p;     x %= p;     y %= p;

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

        //   From cryptlib.h, Validate(...):
        //
        //   0 - using this object won't cause a crash or exception (rng is ignored)
        //   1 - this object will probably function (encrypt, sign, etc.) correctly
        //       (but may not check for weak keys and such)
        //   2 - make sure this object will function correctly, and do reasonable
        //       security checks
        //   3 - do checks that may take a long time
        if( false == ec.ValidateParameters( rng, 3 ) )
            { throw std::string( "EC Parameter Validation Failure" ); }

        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 );

        // Key Validation
        //   0 - using this object won't cause a crash or exception (rng is ignored)
        //   1 - this object will probably function (encrypt, sign, etc.) correctly
        //       (but may not check for weak keys and such)
        //   2 - make sure this object will function correctly, and do reasonable
        //       security checks
        //   3 - do checks that may take a long time
        if( false == PrivateKey.Validate( rng, 3 ) )
        {
            DumpPublicKey( PublicKey );      std::cout << std::endl;

            DumpPrivateKey( PrivateKey );    std::cout << std::endl;

            Validate( p, a, b, x, y, n, f ); std::cout << std::endl;
            
            throw std::string( "Private Key Validation Failure" );        
        }
        if( false == PublicKey.Validate( rng, 3 ) )
        {
            DumpPublicKey( PublicKey );      std::cout << std::endl;

            Validate( p, a, b, x, y, n, f ); std::cout << std::endl;
            
            throw std::string( "Public Key Validation Failure" );
        }

        std::cout << "NIST P192 Curve Parameters:" << std::endl;
        std::cout << std::hex << "  p: " << p << std::endl;
        std::cout << std::hex << "  a: " << a%p << std::endl;
        std::cout << std::hex << "  b: " << b%p << std::endl;

        std::cout << std::dec << "  x: " << x%p << std::endl;
        std::cout << std::dec << "  y: " << y%p << std::endl;

        std::cout << std::dec << "  n: " << n%p << std::endl;
        std::cout << std::dec << "  f: " << f%p << std::endl;

        std::cout << std::endl;

        // a%p in case a<0.
        Validate( p, a%p, b, x, y, n, f );
    }

    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;

    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;
}

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;    // scratch
    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( y % p == t % 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;
    }

    // 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;
    }

    // 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;
    }

    // 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;
}