//------------------------------------------------------------------------------ // // ecdsa_fpga_curve_abstract.cpp // ---------------------------------------------- // Elliptic curve arithmetic procedures for ECDSA // // Authors: Pavel Shatov // // Copyright 2015-2016, 2018 NORDUnet A/S // Copyright 2021 The Commons Conservancy Cryptech Project // SPDX-License-Identifier: BSD-3-Clause // // 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 copyright holder 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 "ecdsa_fpga_model.h" //------------------------------------------------------------------------------ // Globals //------------------------------------------------------------------------------ FPGA_BUFFER ECDSA_GX, ECDSA_GY; FPGA_BUFFER ECDSA_HX, ECDSA_HY; FPGA_BUFFER ECDSA_N; //------------------------------------------------------------------------------ void fpga_curve_init() //------------------------------------------------------------------------------ { int w; // word counter FPGA_BUFFER tmp_gx = ECDSA_GX_INIT, tmp_gy = ECDSA_GY_INIT; FPGA_BUFFER tmp_hx = ECDSA_HX_INIT, tmp_hy = ECDSA_HY_INIT; FPGA_BUFFER tmp_n = ECDSA_N_INIT; /* fill buffers for large multi-word integers */ for (w=0; w0; word_count--) for (bit_count=FPGA_WORD_WIDTH; bit_count>0; bit_count--) { k_word_shifted = k->words[word_count-1] >> (bit_count-1); k_bit = (k_word_shifted & 1) == 1; #ifdef DUMP_CYCLE_STATES dump_cycle_header(word_count, bit_count, k_bit); #endif /* calculate S = R0 + R */ fpga_curve_add_jacobian_abstract_2(&r0x, &r0y, &r0z, &r1x, &r1y, &r1z, &sx, &sy, &sz); /* calculate T = 2 * (R0 | R1) */ if (!k_bit) fpga_curve_double_jacobian_abstract(&r0x, &r0y, &r0z, &tx, &ty, &tz); else fpga_curve_double_jacobian_abstract(&r1x, &r1y, &r1z, &tx, &ty, &tz); // // dump cycle state // #ifdef DUMP_CYCLE_STATES dump_cycle_state(&r0x, &r0y, &r0z, &r1x, &r1y, &r1z, &sx, &sy, &sz, &tx, &ty, &tz); #endif /* now update working variables */ if (!k_bit) { fpga_multiword_copy(&tx, &r0x); fpga_multiword_copy(&ty, &r0y); fpga_multiword_copy(&tz, &r0z); fpga_multiword_copy(&sx, &r1x); fpga_multiword_copy(&sy, &r1y); fpga_multiword_copy(&sz, &r1z); } else { fpga_multiword_copy(&tx, &r1x); fpga_multiword_copy(&ty, &r1y); fpga_multiword_copy(&tz, &r1z); fpga_multiword_copy(&sx, &r0x); fpga_multiword_copy(&sy, &r0y); fpga_multiword_copy(&sz, &r0z); } } // // we now need to convert the point to affine coordinates // FPGA_BUFFER a2, a3; #ifdef DUMP_UOP_OUTPUTS _DUMP_MODULAR_RESULTS = true; #endif fpga_modular_inv23(&r0z, &a2, &a3); fpga_modular_mul(&r0x, &a2, qx); // qx = px * (pz^-1)^2 (mod q) fpga_modular_mul(&r0y, &a3, qy); // qy = py * (pz^-1)^3 (mod q) _DUMP_MODULAR_RESULTS = false; // check, that rz is non-zero (not point at infinity) bool rz_is_zero = fpga_multiword_is_zero(&r0z); // handle special case (result is point at infinity) if (rz_is_zero) { fpga_multiword_copy(&ECDSA_ZERO, qx); fpga_multiword_copy(&ECDSA_ZERO, qy); } } //------------------------------------------------------------------------------ // // Elliptic curve point doubling routine. // // R(rx,ry,rz) = 2 * P(px,py,pz) // // Note, that P(px,py,pz) is supposed to be in projective Jacobian coordinates, // R will be in projective Jacobian coordinates. // // This routine implements algorithm 3.21 from "Guide to Elliptic Curve // Cryptography", the only difference is that step 6. does T1 = T2 + T2 and // then T2 = T2 + T1 instead of T2 = 3 * T2, because our addition is much // faster, than multiplication. // // Note, that this routine also handles one special case, namely when P is at // infinity. No actual extra "handling" is necessary, since when pz is zero, // rz will also be zero (and that's what the "at infinity" check takes into // account). // // Instead of actual modular division, multiplication by pre-computed constant // (2^-1 mod q) is done. // //------------------------------------------------------------------------------ void fpga_curve_double_jacobian_abstract(const FPGA_BUFFER *px, const FPGA_BUFFER *py, const FPGA_BUFFER *pz, FPGA_BUFFER *rx, FPGA_BUFFER *ry, FPGA_BUFFER *rz) //------------------------------------------------------------------------------ { FPGA_BUFFER t1, t2, t3, t4, t5; // temporary variables #ifdef DUMP_UOP_OUTPUTS _DUMP_MODULAR_RESULTS = true; #endif fpga_modular_mul(pz, pz, &t1); fpga_modular_sub(px, &t1, &t2); fpga_modular_add(px, &t1, &t3); fpga_modular_mul(&t3, &t2, &t4); fpga_modular_add(&t4, &t4, &t1); fpga_modular_add(&t1, &t4, &t2); fpga_modular_add(py, py, ry); fpga_modular_mul(pz, ry, rz); fpga_modular_mul(ry, ry, &t1); fpga_modular_mul(px, &t1, &t3); fpga_modular_mul(&t1, &t1, &t4); fpga_modular_mul(&t4, &ECDSA_DELTA, &t5); fpga_modular_mul(&t2, &t2, &t4); fpga_modular_add(&t3, &t3, &t1); fpga_modular_sub(&t4, &t1, rx); fpga_modular_sub(&t3, rx, &t1); fpga_modular_mul(&t1, &t2, &t3); fpga_modular_sub(&t3, &t5, ry); _DUMP_MODULAR_RESULTS = false; } //------------------------------------------------------------------------------ // // Elliptic curve point addition routine. // // R(rx,ry,rz) = P(px,py,pz) + Q(qx,qy,qz) // // Note, that P(px, py, pz) and Q(qx, qy, qz) are supposed to be in projective // Jacobian coordinates, R(rx, ry, rz) will be in projective Jacobian // coordinates too. // // This routine implements the Point Addition algorithm from // https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates // // Since the routine is means to be used with Montgomery ladder, the invariant // R1 - R0 = G means, that the two special cases P == Q and P == -Q can never // happen and the checks are redundant. The checks for P === O and Q == O are // necessary, however. Note, that P and Q can't be at infinity at the same time // though. // // WARNING: This procedure 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 is anywhere near production! // //------------------------------------------------------------------------------ void fpga_curve_add_jacobian_abstract_2(const FPGA_BUFFER *px, const FPGA_BUFFER *py, const FPGA_BUFFER *pz, const FPGA_BUFFER *qx, const FPGA_BUFFER *qy, const FPGA_BUFFER *qz, FPGA_BUFFER *rx, FPGA_BUFFER *ry, FPGA_BUFFER *rz) //------------------------------------------------------------------------------ { bool pz_is_zero = fpga_multiword_is_zero(pz); bool qz_is_zero = fpga_multiword_is_zero(qz); FPGA_BUFFER t1, t2, t3, t4, t5, t6, t7, t8; #ifdef DUMP_UOP_OUTPUTS _DUMP_MODULAR_RESULTS = true; #endif fpga_modular_mul(pz, pz, &t1); // pz2 = pz * pz (pz squared) fpga_modular_mul(qz, qz, &t2); // qz2 = qz * qz (qz squared) fpga_modular_mul(pz, &t1, &t3); // pz3 = pz * pz2 (pz cubed) fpga_modular_mul(qz, &t2, &t4); // qz3 = qz * qz2 (qz cubed) fpga_modular_mul(px, &t2, &t5); // pxz = px * qz2 (px z-adjusted) fpga_modular_mul(qx, &t1, &t2); // qxz = qx * pz2 (qx z-adjusted) fpga_modular_mul(py, &t4, &t6); // pyz = py * qz3 (py z-adjusted) fpga_modular_mul(qy, &t3, &t4); // qyz = qy * pz3 (qy z-adjusted) fpga_modular_sub(&t2, &t5, &t7); // dqpx = qxz - pxz (x-coordinate delta) fpga_modular_sub(&t4, &t6, &t8); // dqpy = qyz - pyz (y-coordinate delta) fpga_modular_mul(pz, qz, &t1); // pqz = pz * qz fpga_modular_mul(&t7, &t1, rz); // rz = pqz * qdpx fpga_modular_mul(&t8, &t8, &t2); // dqpy2 = dqpy * dqpy fpga_modular_mul(&t7, &t7, &t3); // dqpx2 = dqpx * dqpx fpga_modular_mul(&t7, &t3, &t4); // dqpx3 = dqpx * dqpx2 fpga_modular_sub(&t2, &t4, &t1); // t1 = dqpy2 - dqpx3 fpga_modular_mul(&t5, &t3, &t2); // t2 = pxz * dqpx2 fpga_modular_add(&t2, &t2, &t3); // t3 = 2 * t2 (= t2 + t2, which is faster) fpga_modular_sub(&t1, &t3, rx); // rx = t1 - t3 fpga_modular_sub(&t2, rx, &t1); // t1 = t2 - rx fpga_modular_mul(&t1, &t8, &t2); // t2 = t1 * dqpy fpga_modular_mul(&t6, &t4, &t3); // t3 = pyz * dqpx3 fpga_modular_sub(&t2, &t3, ry); // ry = t2 - t3 _DUMP_MODULAR_RESULTS = false; // P == O if (pz_is_zero) { fpga_multiword_copy(qx, rx); fpga_multiword_copy(qy, ry); fpga_multiword_copy(qz, rz); return; } // Q == O if (qz_is_zero) { fpga_multiword_copy(px, rx); fpga_multiword_copy(py, ry); fpga_multiword_copy(pz, rz); return; } } //------------------------------------------------------------------------------ // End-of-File //------------------------------------------------------------------------------