path: root/ecdsa_fpga_model.cpp

//------------------------------------------------------------------------------
//
// ecdsa_fpga_model.cpp
// --------------------------------------------
// Base point scalar multiplier model for ECDSA
//
// Authors: Pavel Shatov
//
// Copyright (c) 2015-2016, 2018 NORDUnet A/S
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// - Redistributions of source code must retain the above copyright notice,
//   this list of conditions and the following disclaimer.
//
// - Redistributions in binary form must reproduce the above copyright notice,
//   this list of conditions and the following disclaimer in the documentation
//   and/or other materials provided with the distribution.
//
// - Neither the name of the NORDUnet nor the names of its contributors may be
//   used to endorse or promote products derived from this software without
//   specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.
//
//------------------------------------------------------------------------------


//------------------------------------------------------------------------------
// Headers
//------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>


//------------------------------------------------------------------------------
// Microcode Switch
//------------------------------------------------------------------------------
#define USE_MICROCODE


//------------------------------------------------------------------------------
// More Headers
//------------------------------------------------------------------------------
#include "ecdsa_fpga_model.h"


//------------------------------------------------------------------------------
// Prototypes
//------------------------------------------------------------------------------
void fpga_model_init ();

bool test_base_point_multiplier (const FPGA_BUFFER *k,
                                 const FPGA_BUFFER *qx,
                                 const FPGA_BUFFER *qy);

bool abuse_internal_point_adder   ();
bool abuse_internal_point_doubler ();


//------------------------------------------------------------------------------
// Locals
//------------------------------------------------------------------------------
static FPGA_BUFFER ecdsa_d_nsa;
static FPGA_BUFFER ecdsa_qx_nsa;
static FPGA_BUFFER ecdsa_qy_nsa;

static FPGA_BUFFER ecdsa_k_nsa;
static FPGA_BUFFER ecdsa_rx_nsa;
static FPGA_BUFFER ecdsa_ry_nsa;

static FPGA_BUFFER ecdsa_d_random;
static FPGA_BUFFER ecdsa_qx_random;
static FPGA_BUFFER ecdsa_qy_random;


//------------------------------------------------------------------------------
int main()
//------------------------------------------------------------------------------
{
    bool    ok;     // flag

        // initialize buffers
    fpga_multiword_init();
    fpga_modular_init();
    fpga_curve_init();
    fpga_model_init();

#ifdef USE_MICROCODE
	printf("ECDSA_UOP_OPERAND_COUNT == %d\n\n", ECDSA_UOP_OPERAND_COUNT);
#endif

		// test base point multiplier: Q = d * G
    printf("Trying to derive public key from private key (NSA test vector)...\n\n");
    ok = test_base_point_multiplier(&ecdsa_d_nsa, &ecdsa_qx_nsa, &ecdsa_qy_nsa);
    if (!ok) return EXIT_FAILURE;

        // test base point multiplier: R = k * G
    printf("Trying to sign something (NSA test vector)...\n\n");
    ok = test_base_point_multiplier(&ecdsa_k_nsa, &ecdsa_rx_nsa, &ecdsa_ry_nsa);
    if (!ok) return EXIT_FAILURE;

		// test base point multiplier: Q = d * G
    printf("Trying to derive public key from private key (random test vector)...\n\n");
    ok = test_base_point_multiplier(&ecdsa_d_random, &ecdsa_qx_random, &ecdsa_qy_random);
    if (!ok) return EXIT_FAILURE;

        // test base point multiplier: O = n * G
    printf("Trying to multiply the base point by its order...\n\n");
    ok = test_base_point_multiplier(&ECDSA_N, &ECDSA_ZERO, &ECDSA_ZERO);
    if (!ok) return EXIT_FAILURE;

        // now run some intricate tests...

        /* Excerpt from the commit message e718fdfae6443466e566ed6ce1515cdecc215ac0:

        The model does multiplication using the double-and-add algorithm. When adding
        two points P and Q on curves P-256 and P-384, four special cases must be
        considered. One of them is P = Q, in that situation the explicit addition
        formulae don't work and either 2*P or 2*Q must be returned from the addition
        routine. In this model Q is always the base point G, so when P = G, then 2*G
        must be returned. Since G is fixed, this model stores precomputed point H = 2*G
        and returns it when adding G + G for true constant-time operation.
    
        During multiplication the bits of k are scanned left-to-right, so doubling is
        done before addition. This way the only situation when both inputs to the
        addition routine are equal to G is when after doubling the result is G. This in
        its turn is only possible when k = n + 2 (where n is the order of the base
        point G). ECDSA requires integer k to be [1, n-1], one of the side effects
        is that the model has a code path that will never be used under normal
        operation. This code path can be verified by first multiplying by k = 2
        (special handling for P = G not triggered), then multiplying by k = n + 2
        (special handling for P = G triggered). Both multiplications should produce
        the same output. In the former case the output will be calculated on-the-fly,
        in the latter case the pre-computed coordinates of H will be used.
         */


		// test base point multiplier: H = 2 * G
    FPGA_BUFFER two;
    fpga_modular_add(&ECDSA_ONE, &ECDSA_ONE, &two);

    printf("Trying to double the base point...\n\n");
    ok = test_base_point_multiplier(&two, &ECDSA_HX, &ECDSA_HY);
    if (!ok) return EXIT_FAILURE;

		// test base point multiplier: G = (n + 1) * G
    FPGA_BUFFER n1;
    fpga_modular_add(&ECDSA_N, &ECDSA_ONE, &n1);	// n1 = n + 1

    printf("Trying to multiply the base point by its order plus one...\n\n");
    ok = test_base_point_multiplier(&n1, &ECDSA_GX, &ECDSA_GY);
    if (!ok) return EXIT_FAILURE;

        // test base point multiplier: H = (n + 2) * G
    FPGA_BUFFER n2;
    fpga_modular_add(&ECDSA_N, &two, &n2);	// n2 = n + two

    printf("Trying to multiply the base point by its order plus two...\n\n");
    ok = test_base_point_multiplier(&n2, &ECDSA_HX, &ECDSA_HY);
    if (!ok) return EXIT_FAILURE;

        // ..and some more tests

        // try to abuse internal point doubler
    ok = abuse_internal_point_doubler();
    if (!ok) return EXIT_FAILURE;
    
        // try to abuse internal point adder
    ok = abuse_internal_point_adder();
    if (!ok) return EXIT_FAILURE;

        // everything went just fine
    return EXIT_SUCCESS;
}


//------------------------------------------------------------------------------
void fpga_model_init()
//------------------------------------------------------------------------------
{
    int w;  // word counter

    FPGA_BUFFER tmp_d_nsa  = ECDSA_D_NSA_INIT, tmp_k_nsa = ECDSA_K_NSA_INIT;
    FPGA_BUFFER tmp_qx_nsa = ECDSA_QX_NSA_INIT, tmp_rx_nsa = ECDSA_RX_NSA_INIT;
    FPGA_BUFFER tmp_qy_nsa = ECDSA_QY_NSA_INIT, tmp_ry_nsa = ECDSA_RY_NSA_INIT;

	FPGA_BUFFER tmp_d_random  = ECDSA_D_RANDOM_INIT;
    FPGA_BUFFER tmp_qx_random = ECDSA_QX_RANDOM_INIT;
    FPGA_BUFFER tmp_qy_random = ECDSA_QY_RANDOM_INIT;

        // fill buffers for large multi-word integers
    for (w=0; w<FPGA_OPERAND_NUM_WORDS; w++)
    {
        ecdsa_d_nsa.words[w] = tmp_d_nsa.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
        ecdsa_qx_nsa.words[w] = tmp_qx_nsa.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
        ecdsa_qy_nsa.words[w] = tmp_qy_nsa.words[FPGA_OPERAND_NUM_WORDS - (w+1)];

        ecdsa_k_nsa.words[w] = tmp_k_nsa.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
        ecdsa_rx_nsa.words[w] = tmp_rx_nsa.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
        ecdsa_ry_nsa.words[w] = tmp_ry_nsa.words[FPGA_OPERAND_NUM_WORDS - (w+1)];

		ecdsa_d_random.words[w] = tmp_d_random.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
        ecdsa_qx_random.words[w] = tmp_qx_random.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
        ecdsa_qy_random.words[w] = tmp_qy_random.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
    }
}


//------------------------------------------------------------------------------
bool test_base_point_multiplier (const FPGA_BUFFER *k,
                                 const FPGA_BUFFER *qx,
                                 const FPGA_BUFFER *qy)
//------------------------------------------------------------------------------
//
// k - multiplier
//
// qx, qy - expected coordinates of product
//
// Returns true when point (rx,ry) = k * G matches the point (qx,qy).
//
//------------------------------------------------------------------------------
{
    bool ok;                // flag
    FPGA_BUFFER rx, ry;     // result

        // run the model
    fpga_curve_base_scalar_multiply(k, &rx, &ry);

        // handle result
    ok = compare_fpga_buffers(qx, qy, &rx, &ry);

    if (!ok)
    {   printf("\n    ERROR\n\n");
        return false;
    }
    else printf("\n    OK\n\n");

        // everything went just fine
    return true;
}


//------------------------------------------------------------------------------
bool compare_fpga_buffers(  const FPGA_BUFFER *az,
                            const FPGA_BUFFER *bz)
//------------------------------------------------------------------------------
//
// Compare z-coordinates of two points and return true when they match.
//
//------------------------------------------------------------------------------
{
    int w;  // word counter

        // print all the values
    print_fpga_buffer("  Expected:   Z = ", az);
    print_fpga_buffer("  Calculated: Z = ", bz);

        // compare values
    for (w=0; w<FPGA_OPERAND_NUM_WORDS; w++)
    {
            // compare x
        if (az->words[w] != bz->words[w]) return false;
    }

        // values are the same
    return true;
}


//------------------------------------------------------------------------------
bool compare_fpga_buffers(  const FPGA_BUFFER *ax,
                            const FPGA_BUFFER *ay,
                            const FPGA_BUFFER *bx,
                            const FPGA_BUFFER *by)
//------------------------------------------------------------------------------
//
// Compare affine coordinates of two points and return true when they match.
//
//------------------------------------------------------------------------------
{
    int w;  // word counter

        // print all the values
    print_fpga_buffer("  Expected:   X = ", ax);
    print_fpga_buffer("  Calculated: X = ", bx);
    printf("\n");
    print_fpga_buffer("  Expected:   Y = ", ay);
    print_fpga_buffer("  Calculated: Y = ", by);

        // compare values
    for (w=0; w<FPGA_OPERAND_NUM_WORDS; w++)
    {
            // compare x
        if (ax->words[w] != bx->words[w]) return false;

            // compare y
        if (ay->words[w] != by->words[w]) return false;
    }

        // values are the same
    return true;
}


//------------------------------------------------------------------------------
bool compare_fpga_buffers(  const FPGA_BUFFER *ax,
                            const FPGA_BUFFER *ay,
                            const FPGA_BUFFER *az,
                            const FPGA_BUFFER *bx,
                            const FPGA_BUFFER *by,
                            const FPGA_BUFFER *bz)
//------------------------------------------------------------------------------
//
// Compare projective coordinates of two points and return true when they match.
//
//------------------------------------------------------------------------------
{
    int w;  // word counter

        // print all the values
    print_fpga_buffer("  Expected:   X = ", ax);
    print_fpga_buffer("  Calculated: X = ", bx);
    printf("\n");
    print_fpga_buffer("  Expected:   Y = ", ay);
    print_fpga_buffer("  Calculated: Y = ", by);
    printf("\n");
    print_fpga_buffer("  Expected:   Z = ", az);
    print_fpga_buffer("  Calculated: Z = ", bz);

        // compare values
    for (w=0; w<FPGA_OPERAND_NUM_WORDS; w++)
    {
            // compare x
        if (ax->words[w] != bx->words[w]) return false;

            // compare y
        if (ay->words[w] != by->words[w]) return false;

            // compare z
        if (az->words[w] != bz->words[w]) return false;
    }

        // values are the same
    return true;
}


//------------------------------------------------------------------------------
void print_fpga_buffer(const char *s, const FPGA_BUFFER *buf)
//------------------------------------------------------------------------------
//
// Pretty print large multi-word integer.
//
//------------------------------------------------------------------------------
{
    int w;  // word counter

        // print header
    printf("%s", s);

        // print all bytes
    for (w=FPGA_OPERAND_NUM_WORDS; w>0; w--)
    {   
        printf("%08x", buf->words[w-1]);

            // insert space after every group of 4 bytes
        if (w > 1) printf(" ");
    }

        // print footer
    printf("\n");
}


//------------------------------------------------------------------------------
void print_fpga_buffer_nodelim(const char *s, const FPGA_BUFFER *buf)
//------------------------------------------------------------------------------
//
// Pretty print large multi-word integer.
//
//------------------------------------------------------------------------------
{
    int w;  // word counter

        // print header
    printf("%s", s);

        // print all bytes
    for (w=FPGA_OPERAND_NUM_WORDS; w>0; w--)
        printf("%08x", buf->words[w-1]);

        // print footer
    printf("\n");
}


//------------------------------------------------------------------------------
bool abuse_internal_point_doubler()
//------------------------------------------------------------------------------
//
// This routine tries to abuse the internal curve point doubler by forcing it
// to double point at infinity.
//
//------------------------------------------------------------------------------
{
    int w;      // word counter
    bool ok;    // flag
    
    FPGA_BUFFER px, py, pz;     // input
    FPGA_BUFFER qx, qy, qz;     // output

        // set P.X and P.Y to some "random" garbage and P.Z to zero
    for (w=0; w<FPGA_OPERAND_NUM_WORDS; w++)
    {   px.words[w] = ECDSA_GX.words[w] ^ ECDSA_HX.words[w];
        py.words[w] = ECDSA_GY.words[w] ^ ECDSA_HY.words[w];
    }
    fpga_multiword_copy(&ECDSA_ZERO, &pz);

        // try to double point at infinity (should produce point at infinity)
    printf("Trying to double something at infinity...\n\n");
    fpga_curve_double_jacobian(&px, &py, &pz, &qx, &qy, &qz);

        // handle result
    ok = compare_fpga_buffers(&ECDSA_ZERO, &qz);
    if (! ok)
    {   printf("\n    ERROR\n\n");
        return false;
    }
    else printf("\n    OK\n\n");

        // everything went just fine
    return true;
}


//------------------------------------------------------------------------------
bool abuse_internal_point_adder()
//------------------------------------------------------------------------------
//
// This routine tries to abuse the internal curve point adder by forcing it to
// go throgh all the possible "corner cases".
//
//------------------------------------------------------------------------------
{
    int w;      // word counter 
    bool ok;    // flag

    FPGA_BUFFER px, py, pz;     // input
    FPGA_BUFFER rx, ry, rz;     // output

    //
    // try to add point at infinity to the base point
    //
    {
            // set P.X and P.Y to some "random" garbage and P.Z to zero
        for (w=0; w<FPGA_OPERAND_NUM_WORDS; w++)
        {   px.words[w] = ECDSA_GX.words[w] ^ ECDSA_HX.words[w];
            py.words[w] = ECDSA_GY.words[w] ^ ECDSA_HY.words[w];
        }
        fpga_multiword_copy(&ECDSA_ZERO, &pz);

            // run addition proceduce
        printf("Trying to add something at infinity to the base point...\n\n");
        fpga_curve_add_jacobian(&px, &py, &pz, &rx, &ry, &rz);

            // handle result
        ok = compare_fpga_buffers(&ECDSA_GX, &ECDSA_GY, &ECDSA_ONE, &rx, &ry, &rz);
        if (! ok)
        {   printf("\n    ERROR\n\n");
            return false;
        }
        else printf("\n    OK\n\n");
    }

    //
    // try to add the base point to itself
    //
    {
            // set P to G
        fpga_multiword_copy(&ECDSA_GX, &px);
        fpga_multiword_copy(&ECDSA_GY, &py);
        fpga_multiword_copy(&ECDSA_ONE, &pz);

            // run addition proceduce
        printf("Trying to add the base point to itself...\n\n");
        fpga_curve_add_jacobian(&px, &py, &pz, &rx, &ry, &rz);

            // handle result
        ok = compare_fpga_buffers(&ECDSA_HX, &ECDSA_HY, &ECDSA_ONE, &rx, &ry, &rz);
        if (! ok)
        {   printf("\n    ERROR\n\n");
            return false;
        }
        else printf("\n    OK\n\n");
    }

    //
    // try to add the base point to its opposite
    //
    {
            // set P to (G.X, -G.Y, 1)
        fpga_multiword_copy(&ECDSA_ZERO, &px);
        fpga_multiword_copy(&ECDSA_ZERO, &py);
        fpga_multiword_copy(&ECDSA_ONE,  &pz);

        fpga_modular_add(&ECDSA_ZERO, &ECDSA_GX, &px);
        fpga_modular_sub(&ECDSA_ZERO, &ECDSA_GY, &py);

            // run addition proceduce
        printf("Trying to add the base point to its opposite...\n\n");
        fpga_curve_add_jacobian(&px, &py, &pz, &rx, &ry, &rz);

            // handle result
        ok = compare_fpga_buffers(&ECDSA_ONE, &ECDSA_ONE, &ECDSA_ZERO, &rx, &ry, &rz);
        if (! ok)
        {   printf("\n    ERROR\n\n");
            return false;
        }
        else printf("\n    OK\n\n");
    }

        // everything went just fine
    return true;
}


//------------------------------------------------------------------------------
// End-of-File
//------------------------------------------------------------------------------