diff options
Diffstat (limited to 'ecdsa_fpga_model.cpp')
| -rw-r--r-- | ecdsa_fpga_model.cpp | 539 |
1 files changed, 539 insertions, 0 deletions
diff --git a/ecdsa_fpga_model.cpp b/ecdsa_fpga_model.cpp new file mode 100644 index 0000000..182c2ab --- /dev/null +++ b/ecdsa_fpga_model.cpp @@ -0,0 +1,539 @@ +//------------------------------------------------------------------------------ +// +// 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(); + + printf("ECDSA_UOP_OPERAND_COUNT == %d\n\n", ECDSA_UOP_OPERAND_COUNT); + + // 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 +//------------------------------------------------------------------------------ |