//------------------------------------------------------------------------------ // // ecdsa_fpga_curve_abstract.cpp // ---------------------------------------------- // Elliptic curve arithmetic procedures 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 "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--) { /* calculate T = 2 * R */ fpga_curve_double_jacobian_abstract(&rx, &ry, &rz, &tx, &ty, &tz); /* always calculate R = T + P for constant-time */ fpga_curve_add_jacobian_abstract(&tx, &ty, &tz, &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_multiword_copy(&tx, &rx); fpga_multiword_copy(&ty, &ry); fpga_multiword_copy(&tz, &rz); } } FPGA_BUFFER a2, a3; fpga_modular_inv23(&rz, &a2, &a3); fpga_modular_mul(&rx, &a2, qx); // qx = px * (pz^-1)^2 (mod q) fpga_modular_mul(&ry, &a3, qy); // qy = py * (pz^-1)^3 (mod q) // check, that rz is non-zero (not point at infinity) bool rz_is_zero = fpga_multiword_is_zero(&rz); // 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. // // Instead of actual modular division, multiplication by pre-computed constant // (2^-1 mod q) is done. // // Note, that FPGA modular multiplier can't multiply a given buffer by itself, // this way it's impossible to do eg. fpga_modular_mul(pz, pz, &t1). To overcome // the problem the algorithm was modified to do fpga_buffer_copy(pz, &t1) and // then fpga_modular_mul(pz, &t1, &t1) instead. // // WARNING: Though this procedure always does doubling steps, 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 is anywhere // near production! // //------------------------------------------------------------------------------ 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; // temporary variables // check, whether P is at infinity bool pz_is_zero = fpga_multiword_is_zero(pz); /* 2. */ fpga_multiword_copy(pz, &t1); fpga_modular_mul(pz, &t1, &t1); /* 3. */ fpga_modular_sub(px, &t1, &t2); /* 4. */ fpga_modular_add(px, &t1, &t1); /* 5. */ fpga_modular_mul(&t1, &t2, &t2); /* 6. */ fpga_modular_add(&t2, &t2, &t1); /* */ fpga_modular_add(&t1, &t2, &t2); /* 7. */ fpga_modular_add(py, py, ry); /* 8. */ fpga_modular_mul(pz, ry, rz); /* 9. */ fpga_multiword_copy(ry, &t1); fpga_multiword_copy(ry, &t3); fpga_modular_mul(&t1, &t3, ry); /* 10. */ fpga_modular_mul(px, ry, &t3); /* 11. */ fpga_multiword_copy(ry, &t1); fpga_modular_mul(ry, &t1, &t1); /* 12. */ fpga_modular_mul(&t1, &ECDSA_DELTA, ry); /* 13. */ fpga_multiword_copy(&t2, &t1); fpga_modular_mul(&t1, &t2, rx); /* 14. */ fpga_modular_add(&t3, &t3, &t1); /* 15. */ fpga_modular_sub(rx, &t1, rx); /* 16. */ fpga_modular_sub(&t3, rx, &t1); /* 17. */ fpga_modular_mul(&t1, &t2, &t1); /* 18. */ fpga_modular_sub(&t1, ry, ry); // handle special case (input point is at infinity) if (pz_is_zero) { fpga_multiword_copy(&ECDSA_ONE, rx); fpga_multiword_copy(&ECDSA_ONE, ry); fpga_multiword_copy(&ECDSA_ZERO, rz); } } //------------------------------------------------------------------------------ // // Elliptic curve point addition routine. // // R(rx,ry,rz) = P(px,py,pz) + Q(qx,qy) // // Note, that P(px, py, pz) is supposed to be in projective Jacobian // coordinates, while Q(qx,qy) is supposed to be in affine coordinates, // R(rx, ry, rz) will be in projective Jacobian coordinates. Moreover, in this // particular implementation Q is always the base point G. // // This routine implements algorithm 3.22 from "Guide to Elliptic Curve // Cryptography". Differences from the original algorithm: // // 1) Step 1. is omitted, because point Q is always the base point, which is // not at infinity by definition. // // 2) Step 9.1 just returns the pre-computed double of the base point instead // of actually doubling it. // // Note, that this routine also handles three special cases: // // 1) P is at infinity // 2) P == Q // 3) P == -Q // // Note, that FPGA modular multiplier can't multiply a given buffer by itself, // this way it's impossible to do eg. fpga_modular_mul(pz, pz, &t1). To overcome // the problem the algorithm was modified to do fpga_buffer_copy(pz, &t1) and // then fpga_modular_mul(pz, &t1, &t1) instead. // // 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(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; // temporary variables bool pz_is_zero = fpga_multiword_is_zero(pz); // Step 2. /* 3. */ fpga_multiword_copy(pz, &t1); fpga_modular_mul(pz, &t1, &t1); /* 4. */ fpga_modular_mul(pz, &t1, &t2); /* 5. */ fpga_modular_mul(&t1, &ECDSA_GX, &t1); /* 6. */ fpga_modular_mul(&t2, &ECDSA_GY, &t2); /* 7. */ fpga_modular_sub(&t1, px, &t1); /* 8. */ fpga_modular_sub(&t2, py, &t2); bool t1_is_zero = fpga_multiword_is_zero(&t1); // | Step 9. bool t2_is_zero = fpga_multiword_is_zero(&t2); // | /* 10. */ fpga_modular_mul(pz, &t1, rz); /* 11. */ fpga_multiword_copy(&t1, &t3); fpga_modular_mul(&t1, &t3, &t3); /* 12. */ fpga_modular_mul(&t1, &t3, &t4); /* 13. */ fpga_modular_mul(px, &t3, &t3); /* 14. */ fpga_modular_add(&t3, &t3, &t1); /* 15. */ fpga_multiword_copy(&t2, rx); fpga_modular_mul(rx, &t2, rx); /* 16. */ fpga_modular_sub(rx, &t1, rx); /* 17. */ fpga_modular_sub(rx, &t4, rx); /* 18. */ fpga_modular_sub(&t3, rx, &t3); /* 19. */ fpga_modular_mul(&t2, &t3, &t3); /* 20. */ fpga_modular_mul(py, &t4, &t4); /* 21. */ fpga_modular_sub(&t3, &t4, ry); // // final selection // if (pz_is_zero) // P at infinity ? { fpga_multiword_copy(&ECDSA_GX, rx); fpga_multiword_copy(&ECDSA_GY, ry); fpga_multiword_copy(&ECDSA_ONE, rz); } else if (t1_is_zero) // same x for P and Q ? { fpga_multiword_copy(t2_is_zero ? &ECDSA_HX : &ECDSA_ONE, rx); // | same y ? (P==Q => R=2*G) : (P==-Q => R=O) fpga_multiword_copy(t2_is_zero ? &ECDSA_HY : &ECDSA_ONE, ry); // | fpga_multiword_copy(t2_is_zero ? &ECDSA_ONE : &ECDSA_ZERO, rz); // | } } //------------------------------------------------------------------------------ // End-of-File //------------------------------------------------------------------------------