aboutsummaryrefslogblamecommitdiff
path: root/ecdsa_fpga_model.cpp
blob: 13ba3f9f7cefd4e864477eb21bce68aa1d0febd3 (plain) (tree)


































































































                                                                                
                    
                                                                             
      





                                                                                    




                                                                       
















                                                                                         














                                                                             
        












                                                                             
 




























































































































































































































































                                                                                             
                                                                  


















                                                                                
                                              






                                                                                
                                            






                                                                       
                                                  




                                                                


                                                     


                                                                               
                                                                                    









                                                                                   

                                                                                 

      


                                                                                 

                            
                                                                                   





                                      



                                    
 
 






                                                                                     
 









                                                                                               
 


                                    
 















                                                                                





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

        // bail out right after the first test, if debugging is enabled
#if defined(DUMP_CYCLE_STATES) || defined(DUMP_UOP_OUTPUTS)
    return -1;
#endif

        // 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...

		// 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_shim(&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 through all the possible "corner cases".
//
//------------------------------------------------------------------------------
{
    int w;      // word counter 
    bool ok;    // flag

    FPGA_BUFFER px, py, pz;     // input
	FPGA_BUFFER qx, qy, qz;     // 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
			// set Q to the base point
        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);
		fpga_multiword_copy(&ECDSA_GX, &qx);
		fpga_multiword_copy(&ECDSA_GY, &qy);
		fpga_multiword_copy(&ECDSA_ONE, &qz);

            // run addition proceduce
        printf("Trying to add something at infinity to the base point...\n\n");
        fpga_curve_add_jacobian_2_shim(&px, &py, &pz, &qx, &qy, &qz, &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 point at infinity (different order of points)
    //
    {
            // in fact we only need to swap P and Q
        printf("Trying to add the base point to something at infinity...\n\n");
        //fpga_curve_add_jacobian_2(&qx, &qy, &qz, &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");
    }
	
        // everything went just fine
    return true;
}


//------------------------------------------------------------------------------
void dump_cycle_header(int word_count, int bit_count, bool k_bit)
//------------------------------------------------------------------------------
{
    (void)printf("wc = %d, bc = %d, k_bit = %d\n", word_count-1, bit_count-1, k_bit);
}


//------------------------------------------------------------------------------
void dump_cycle_state(  const FPGA_BUFFER *r0x, const FPGA_BUFFER *r0y, const FPGA_BUFFER *r0z,
                        const FPGA_BUFFER *r1x, const FPGA_BUFFER *r1y, const FPGA_BUFFER *r1z,
                        const FPGA_BUFFER *sx,  const FPGA_BUFFER *sy,  const FPGA_BUFFER *sz,
                        const FPGA_BUFFER *tx,  const FPGA_BUFFER *ty,  const FPGA_BUFFER *tz)
//------------------------------------------------------------------------------
{
    print_fpga_buffer("R0X: ", r0x);
    print_fpga_buffer("R0Y: ", r0y);
    print_fpga_buffer("R0Z: ", r0z);

    print_fpga_buffer("R1X: ", r1x);
    print_fpga_buffer("R1Y: ", r1y);
    print_fpga_buffer("R1Z: ", r1z);

    print_fpga_buffer("SX: ", sx);
    print_fpga_buffer("SY: ", sy);
    print_fpga_buffer("SZ: ", sz);

    print_fpga_buffer("TX: ", tx);
    print_fpga_buffer("TY: ", ty);
    print_fpga_buffer("TZ: ", tz);
}


//------------------------------------------------------------------------------
void dump_uop_output(const char *uop, const FPGA_BUFFER *buf)
//------------------------------------------------------------------------------
{
    (void)printf("UOP: %s: ", uop);
    print_fpga_buffer("", buf);
}


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