From 71fba5c6662d6bbe74366c03b531a5f86b25bbbb Mon Sep 17 00:00:00 2001 From: "Pavel V. Shatov (Meister)" Date: Mon, 26 Feb 2018 13:05:17 +0300 Subject: Initial commit of C reference model for ECDH cores. --- fpga_curve.cpp | 352 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 352 insertions(+) create mode 100644 fpga_curve.cpp (limited to 'fpga_curve.cpp') diff --git a/fpga_curve.cpp b/fpga_curve.cpp new file mode 100644 index 0000000..46f6f73 --- /dev/null +++ b/fpga_curve.cpp @@ -0,0 +1,352 @@ +//------------------------------------------------------------------------------ +// +// fpga_curve.cpp +// ------------------------------------ +// Elliptic curve arithmetic procedures +// +// 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 +#include "ecdh_fpga_model.h" +#include "fpga_lowlevel.h" +#include "fpga_modular.h" +#include "fpga_curve.h" +#include "fpga_util.h" + + +//------------------------------------------------------------------------------ +// Globals +//------------------------------------------------------------------------------ +FPGA_BUFFER ecdsa_n; +FPGA_BUFFER ecdsa_g_x, ecdsa_g_y; +FPGA_BUFFER ecdh_d_x, ecdh_d_y; +FPGA_BUFFER ecdh_da, ecdh_db; +FPGA_BUFFER ecdh_qa_x, ecdh_qa_y; +FPGA_BUFFER ecdh_qb_x, ecdh_qb_y; +FPGA_BUFFER ecdh_s_x, ecdh_s_y; + + +//------------------------------------------------------------------------------ +void fpga_curve_init() +//------------------------------------------------------------------------------ +{ + int w; // word counter + + FPGA_BUFFER tmp_n = ECDSA_N; + FPGA_BUFFER tmp_g_x = ECDSA_G_X, tmp_g_y = ECDSA_G_Y; + FPGA_BUFFER tmp_da = ECDH_DA, tmp_db = ECDH_DB; + FPGA_BUFFER tmp_qa_x = ECDH_QA_X, tmp_qa_y = ECDH_QA_Y; + FPGA_BUFFER tmp_qb_x = ECDH_QB_X, tmp_qb_y = ECDH_QB_Y; + FPGA_BUFFER tmp_s_x = ECDH_S_X, tmp_s_y = ECDH_S_Y; + + /* fill buffers for large multi-word integers */ + for (w=0; w R=2*G) : (P==-Q => R=O) + fpga_buffer_copy(t2_is_zero ? &ecdh_d_y : &ecdsa_one, ry); // | + fpga_buffer_copy(t2_is_zero ? &ecdsa_one : &ecdsa_zero, rz); // | + } + +} + + +//------------------------------------------------------------------------------ +// +// Conversion from projective Jacobian to affine coordinates. +// +// P(px,py,pz) -> Q(qx,qy) +// +// Note, that qx = px / Z^2 and qy = py / Z^3. Division in modular arithmetic +// is equivalent to multiplication by the inverse value of divisor, so +// qx = px * (pz^-1)^2 and qy = py * (pz^-1)^3. +// +// Note, that this procedure does *NOT* handle points at infinity correctly. It +// can only be called from the base point multiplication routine, that +// specifically makes sure that P is not at infinity, so pz will always be +// non-zero value. +// +//------------------------------------------------------------------------------ +void fpga_curve_point_to_affine(FPGA_BUFFER *px, FPGA_BUFFER *py, FPGA_BUFFER *pz, FPGA_BUFFER *qx, FPGA_BUFFER *qy) +//------------------------------------------------------------------------------ +{ + FPGA_BUFFER pz1; // inverse value of pz + FPGA_BUFFER t2, t3; // intermediate values + + fpga_modular_inv(pz, &pz1); // pz1 = pz^-1 (mod q) + + fpga_modular_mul(&pz1, &pz1, &t2); // t2 = pz1 ^ 2 (mod q) + fpga_modular_mul(&pz1, &t2, &t3); // t3 = tz1 ^ 3 (mod q) + + fpga_modular_mul(px, &t2, qx); // qx = px * (pz^-1)^2 (mod q) + fpga_modular_mul(py, &t3, qy); // qy = py * (pz^-1)^3 (mod q) +} + + +//------------------------------------------------------------------------------ +// +// Elliptic curve point scalar multiplication routine. +// +// Q(qx,qy) = k * P(px,py) +// +// Note, that Q is supposed to be in affine coordinates. Multiplication is done +// using the double-and-add algorithm 3.27 from "Guide to Elliptic Curve +// Cryptography". +// +// WARNING: Though this procedure always does the addition step, it only +// updates the result when current bit of k is set. It does not take any +// active measures to keep run-time constant. The main purpose of this model +// is to help debug Verilog code for FPGA, so *DO NOT* use it anywhere near +// production! +// +//------------------------------------------------------------------------------ +void fpga_curve_scalar_multiply(FPGA_BUFFER *px, FPGA_BUFFER *py, FPGA_BUFFER *k, FPGA_BUFFER *qx, FPGA_BUFFER *qy) +//------------------------------------------------------------------------------ +{ + int word_count, bit_count; // counters + + FPGA_BUFFER rx, ry, rz; // intermediate result + FPGA_BUFFER tx, ty, tz; // temporary variable + + /* obtain quantity 2 * P */ + fpga_curve_double_jacobian(px, py, &ecdsa_one, &tx, &ty, &tz); + fpga_curve_point_to_affine(&tx, &ty, &tz, &ecdh_d_x, &ecdh_d_y); + + /* set initial value of R to point at infinity */ + fpga_buffer_copy(&ecdsa_one, &rx); + fpga_buffer_copy(&ecdsa_one, &ry); + fpga_buffer_copy(&ecdsa_zero, &rz); + + /* process bits of k left-to-right */ + for (word_count=OPERAND_NUM_WORDS; word_count>0; word_count--) + for (bit_count=FPGA_WORD_WIDTH; bit_count>0; bit_count--) + { + /* calculate T = 2 * R */ + fpga_curve_double_jacobian(&rx, &ry, &rz, &tx, &ty, &tz); + + /* always calculate R = T + P for constant-time */ + fpga_curve_add_jacobian(&tx, &ty, &tz, px, py, &rx, &ry, &rz); + + /* revert to the value of T before addition if the current bit of k is not set */ + if (!((k->words[word_count-1] >> (bit_count-1)) & 1)) + { fpga_buffer_copy(&tx, &rx); + fpga_buffer_copy(&ty, &ry); + fpga_buffer_copy(&tz, &rz); + } + + } + + // convert result to affine coordinates anyway + fpga_curve_point_to_affine(&rx, &ry, &rz, qx, qy); + + // check, that rz is non-zero (not point at infinity) + bool rz_is_zero = fpga_buffer_is_zero(&rz); + + // handle special case (result is point at infinity) + if (rz_is_zero) + { fpga_buffer_copy(&ecdsa_zero, qx); + fpga_buffer_copy(&ecdsa_zero, qy); + } +} + + +//------------------------------------------------------------------------------ +// End-of-File +//------------------------------------------------------------------------------ -- cgit v1.2.3