diff options
Diffstat (limited to 'x25519/x25519_fpga_curve_abstract.cpp')
| -rw-r--r-- | x25519/x25519_fpga_curve_abstract.cpp | 222 |
1 files changed, 222 insertions, 0 deletions
diff --git a/x25519/x25519_fpga_curve_abstract.cpp b/x25519/x25519_fpga_curve_abstract.cpp new file mode 100644 index 0000000..bb551df --- /dev/null +++ b/x25519/x25519_fpga_curve_abstract.cpp @@ -0,0 +1,222 @@ +//------------------------------------------------------------------------------ +// +// 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 +//------------------------------------------------------------------------------ |