aboutsummaryrefslogtreecommitdiff
path: root/ecdsa_fpga_model.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'ecdsa_fpga_model.cpp')
-rw-r--r--ecdsa_fpga_model.cpp539
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
+//------------------------------------------------------------------------------