//------------------------------------------------------------------------------ // // x25519_fpga_curve_abstract.cpp // ----------------------------------------------- // Elliptic curve arithmetic procedures for X25519 // // 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 "x25519_fpga_model.h" //------------------------------------------------------------------------------ // Globals //------------------------------------------------------------------------------ FPGA_BUFFER X25519_G_X; // x-coordinate of the base point FPGA_BUFFER X25519_A24; // coefficient (A + 2) / 4 //------------------------------------------------------------------------------ void fpga_curve_x25519_init() //------------------------------------------------------------------------------ { int w_src, w_dst; // word counters FPGA_WORD TMP_G_X[FPGA_OPERAND_NUM_WORDS] = X25519_G_X_INIT; FPGA_WORD TMP_A24[FPGA_OPERAND_NUM_WORDS] = X25519_A24_INIT; /* fill buffers for large multi-word integers */ for ( w_src = 0, w_dst = FPGA_OPERAND_NUM_WORDS - 1; w_src < FPGA_OPERAND_NUM_WORDS; w_src++, w_dst--) { X25519_G_X.words[w_dst] = TMP_G_X[w_src]; X25519_A24.words[w_dst] = TMP_A24[w_src]; } } //------------------------------------------------------------------------------ // // Elliptic curve point scalar multiplication routine. // // This uses the Montgomery ladder to do the multiplication and then // converts the result to affine coordinates. // // The algorithm is based on Algorithm 3 from "How to (pre-)compute a ladder" // https://eprint.iacr.org/2017/264.pdf // //------------------------------------------------------------------------------ void fpga_curve_x25519_scalar_multiply_abstract(const FPGA_BUFFER *PX, const FPGA_BUFFER *K, FPGA_BUFFER *QX) //------------------------------------------------------------------------------ { int word_count, bit_count; // counters // temporary buffers FPGA_BUFFER R0_X; FPGA_BUFFER R0_Z; FPGA_BUFFER R1_X; FPGA_BUFFER R1_Z; FPGA_BUFFER T0_X; FPGA_BUFFER T0_Z; FPGA_BUFFER T1_X; FPGA_BUFFER T1_Z; // initialization fpga_multiword_copy(&CURVE25519_ONE, &R0_X); fpga_multiword_copy(&CURVE25519_ZERO, &R0_Z); fpga_multiword_copy(PX, &R1_X); fpga_multiword_copy(&CURVE25519_ONE, &R1_Z); // handy vars FPGA_WORD k_word; bool k_bit, r_swap = false; // multiply for (word_count=FPGA_OPERAND_NUM_WORDS; word_count>0; word_count--) { for (bit_count=FPGA_WORD_WIDTH; bit_count>0; bit_count--) { // get current bit of K k_word = K->words[word_count - 1] >> (bit_count - 1); k_bit = (k_word & (FPGA_WORD)1) == 1; // we feed either R0, R1 or R1, R0 into the ladder fpga_multiword_copy(r_swap == k_bit ? &R0_X : &R1_X, &T0_X); fpga_multiword_copy(r_swap == k_bit ? &R0_Z : &R1_Z, &T0_Z); fpga_multiword_copy(r_swap == k_bit ? &R1_X : &R0_X, &T1_X); fpga_multiword_copy(r_swap == k_bit ? &R1_Z : &R0_Z, &T1_Z); // remember whether we did swapping r_swap = k_bit; // montgomery ladder step fpga_curve_x25519_ladder_step( PX, &T0_X, &T0_Z, &T1_X, &T1_Z, &R0_X, &R0_Z, &R1_X, &R1_Z); } } // since the lower three bits of the private key are always ...000, // the result is in R0_X, R0_Z and // now conversion to affine coordinates fpga_curve_x25519_to_affine(&R0_X, &R0_Z, &T0_X); // so far we've done everything modulo 2*P, we now need // to do final reduction modulo P, this can be done using // our modular adder this way: fpga_modular_add(&T0_X, &CURVE25519_ZERO, QX, &CURVE25519_1P); } //------------------------------------------------------------------------------ // // Montgomery Ladder Step // // There are many papers describing Montgomery ladder, this particular // implementation is based on Algorithm 2 from "Fast elliptic-curve // cryptography on the Cell Broadband Engine" by Neil Costigan and Peter // Schwabe // https://cryptojedi.org/papers/celldh-20090107.pdf // //------------------------------------------------------------------------------ void fpga_curve_x25519_ladder_step (const FPGA_BUFFER *PX, const FPGA_BUFFER *R0X_in, const FPGA_BUFFER *R0Z_in, const FPGA_BUFFER *R1X_in, const FPGA_BUFFER *R1Z_in, FPGA_BUFFER *R0X_out, FPGA_BUFFER *R0Z_out, FPGA_BUFFER *R1X_out, FPGA_BUFFER *R1Z_out) //------------------------------------------------------------------------------ { FPGA_BUFFER S0, S1; FPGA_BUFFER D0, D1; FPGA_BUFFER QS0, QD0; FPGA_BUFFER S0D1, S1D0; FPGA_BUFFER TS, TD; FPGA_BUFFER QTD; FPGA_BUFFER T0, TA, T1; fpga_modular_add(R0X_in, R0Z_in, &S0, &CURVE25519_2P); fpga_modular_add(R1X_in, R1Z_in, &S1, &CURVE25519_2P); fpga_modular_sub(R0X_in, R0Z_in, &D0, &CURVE25519_2P); fpga_modular_sub(R1X_in, R1Z_in, &D1, &CURVE25519_2P); // fpga_modular_mul(&S0, &S0, &QS0, &CURVE25519_2P); fpga_modular_mul(&D0, &D0, &QD0, &CURVE25519_2P); fpga_modular_mul(&S0, &D1, &S0D1, &CURVE25519_2P); fpga_modular_mul(&S1, &D0, &S1D0, &CURVE25519_2P); // fpga_modular_add(&S1D0, &S0D1, &TS, &CURVE25519_2P); fpga_modular_sub(&S1D0, &S0D1, &TD, &CURVE25519_2P); // fpga_modular_mul(&TD, &TD, &QTD, &CURVE25519_2P); // fpga_modular_sub(&QS0, &QD0, &T0, &CURVE25519_2P); fpga_modular_mul(&T0, &X25519_A24, &TA, &CURVE25519_2P); fpga_modular_add(&TA, &QD0, &T1, &CURVE25519_2P); // fpga_modular_mul(&QS0, &QD0, R0X_out, &CURVE25519_2P); fpga_modular_mul(&T0, &T1, R0Z_out, &CURVE25519_2P); fpga_modular_mul(&TS, &TS, R1X_out, &CURVE25519_2P); fpga_modular_mul(PX, &QTD, R1Z_out, &CURVE25519_2P); } //------------------------------------------------------------------------------ // // Conversion to affine coordinates. // // Q_X = P_X / P_Z = P_X * P_Z ^ -1 // //------------------------------------------------------------------------------ void fpga_curve_x25519_to_affine (const FPGA_BUFFER *P_X, const FPGA_BUFFER *P_Z, FPGA_BUFFER *Q_X) //------------------------------------------------------------------------------ { FPGA_BUFFER P_Z_1; fpga_modular_inv_abstract(P_Z, &P_Z_1, &CURVE25519_2P); fpga_modular_mul(P_X, &P_Z_1, Q_X, &CURVE25519_2P); } //------------------------------------------------------------------------------ // End-of-File //------------------------------------------------------------------------------