[Cryptech-Commits] [user/shatov/curve25519_fpga_model] 09/14: Ed25519-specific code (curve base point multiplication)
git at cryptech.is
git at cryptech.is
Mon Sep 24 18:52:53 UTC 2018
This is an automated email from the git hooks/post-receive script.
meisterpaul1 at yandex.ru pushed a commit to branch master
in repository user/shatov/curve25519_fpga_model.
commit 250716dfed0da0bdcf8f975293fbf72c2b56c247
Author: Pavel V. Shatov (Meister) <meisterpaul1 at yandex.ru>
AuthorDate: Mon Sep 24 21:38:37 2018 +0300
Ed25519-specific code (curve base point multiplication)
---
ed25519/ed25519_fpga_curve.h | 118 ++++++++++++
ed25519/ed25519_fpga_curve_abstract.cpp | 295 ++++++++++++++++++++++++++++++
ed25519/ed25519_fpga_curve_microcode.cpp | 299 +++++++++++++++++++++++++++++++
3 files changed, 712 insertions(+)
diff --git a/ed25519/ed25519_fpga_curve.h b/ed25519/ed25519_fpga_curve.h
new file mode 100644
index 0000000..3a16bb6
--- /dev/null
+++ b/ed25519/ed25519_fpga_curve.h
@@ -0,0 +1,118 @@
+//------------------------------------------------------------------------------
+//
+// ed25519_fpga_curve.h
+// ------------------------------------------------
+// Elliptic curve arithmetic procedures for Ed25519
+//
+// Authors: Pavel Shatov
+//
+// Copyright (c) 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.
+//
+//------------------------------------------------------------------------------
+
+
+//------------------------------------------------------------------------------
+// Ed25519 Parameters
+//------------------------------------------------------------------------------
+
+/* x-coordinate of the base point */
+#define ED25519_G_X_INIT {0x216936d3, 0xcd6e53fe, 0xc0a4e231, 0xfdd6dc5c, \
+ 0x692cc760, 0x9525a7b2, 0xc9562d60, 0x8f25d51a}
+
+/* y-coordinate of the base point */
+#define ED25519_G_Y_INIT {0x66666666, 0x66666666, 0x66666666, 0x66666666, \
+ 0x66666666, 0x66666666, 0x66666666, 0x66666658}
+
+/* z-coordinate of the base point */
+#define ED25519_G_Z_INIT {0x00000000, 0x00000000, 0x00000000, 0x00000000, \
+ 0x00000000, 0x00000000, 0x00000000, 0x00000001}
+
+/* t-coordinate of the base point */
+#define ED25519_G_T_INIT {0x67875f0f, 0xd78b7665, 0x66ea4e8e, 0x64abe37d, \
+ 0x20f09f80, 0x775152f5, 0x6dde8ab3, 0xa5b7dda3}
+
+
+//------------------------------------------------------------------------------
+// Globals
+//------------------------------------------------------------------------------
+extern FPGA_BUFFER ED25519_G_X; // the base point
+extern FPGA_BUFFER ED25519_G_Y; //
+extern FPGA_BUFFER ED25519_G_Z; //
+extern FPGA_BUFFER ED25519_G_T; //
+
+
+
+//------------------------------------------------------------------------------
+// Implementation switch
+//------------------------------------------------------------------------------
+#ifdef USE_MICROCODE
+#define fpga_curve_ed25519_base_scalar_multiply fpga_curve_ed25519_base_scalar_multiply_microcode
+#else
+#define fpga_curve_ed25519_base_scalar_multiply fpga_curve_ed25519_base_scalar_multiply_abstract
+#endif
+
+
+//------------------------------------------------------------------------------
+// Prototypes
+//------------------------------------------------------------------------------
+void fpga_curve_ed25519_init ();
+
+void fpga_curve_ed25519_base_scalar_multiply_abstract (const FPGA_BUFFER *K, FPGA_BUFFER *Q_Y);
+void fpga_curve_ed25519_base_scalar_multiply_microcode (const FPGA_BUFFER *K, FPGA_BUFFER *Q_Y);
+
+void fpga_curve_ed25519_double (const FPGA_BUFFER *P_X,
+ const FPGA_BUFFER *P_Y,
+ const FPGA_BUFFER *P_Z,
+ const FPGA_BUFFER *P_T,
+ FPGA_BUFFER *Q_X,
+ FPGA_BUFFER *Q_Y,
+ FPGA_BUFFER *Q_Z,
+ FPGA_BUFFER *Q_T);
+
+void fpga_curve_ed25519_add (const FPGA_BUFFER *P_X,
+ const FPGA_BUFFER *P_Y,
+ const FPGA_BUFFER *P_Z,
+ const FPGA_BUFFER *P_T,
+ const FPGA_BUFFER *Q_X,
+ const FPGA_BUFFER *Q_Y,
+ const FPGA_BUFFER *Q_Z,
+ const FPGA_BUFFER *Q_T,
+ FPGA_BUFFER *R_X,
+ FPGA_BUFFER *R_Y,
+ FPGA_BUFFER *R_Z,
+ FPGA_BUFFER *R_T);
+
+void fpga_curve_ed25519_to_affine (const FPGA_BUFFER *P_X, const FPGA_BUFFER *P_Y,
+ const FPGA_BUFFER *P_Z,
+ FPGA_BUFFER *Q_X, FPGA_BUFFER *Q_Y);
+
+
+//------------------------------------------------------------------------------
+// End-of-File
+//------------------------------------------------------------------------------
diff --git a/ed25519/ed25519_fpga_curve_abstract.cpp b/ed25519/ed25519_fpga_curve_abstract.cpp
new file mode 100644
index 0000000..e5b1dd0
--- /dev/null
+++ b/ed25519/ed25519_fpga_curve_abstract.cpp
@@ -0,0 +1,295 @@
+//------------------------------------------------------------------------------
+//
+// ed25519_fpga_curve_abstract.cpp
+// ------------------------------------------------
+// Elliptic curve arithmetic procedures for Ed25519
+//
+// Authors: Pavel Shatov
+//
+// Copyright (c) 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.
+//
+//------------------------------------------------------------------------------
+
+
+#include <stdio.h>
+
+
+//------------------------------------------------------------------------------
+// Headers
+//------------------------------------------------------------------------------
+#include "ed25519_fpga_model.h"
+
+
+//------------------------------------------------------------------------------
+// Globals
+//------------------------------------------------------------------------------
+FPGA_BUFFER ED25519_G_X; // x-coordinate of the base point
+FPGA_BUFFER ED25519_G_Y; // y-coordinate of the base point
+FPGA_BUFFER ED25519_G_Z; // z-coordinate of the base point
+FPGA_BUFFER ED25519_G_T; // y-coordinate of the base point
+
+
+//------------------------------------------------------------------------------
+void fpga_curve_ed25519_init()
+//------------------------------------------------------------------------------
+{
+ int w_src, w_dst; // word counters
+
+ FPGA_WORD TMP_G_X[FPGA_OPERAND_NUM_WORDS] = ED25519_G_X_INIT;
+ FPGA_WORD TMP_G_Y[FPGA_OPERAND_NUM_WORDS] = ED25519_G_Y_INIT;
+ FPGA_WORD TMP_G_Z[FPGA_OPERAND_NUM_WORDS] = ED25519_G_Z_INIT;
+ FPGA_WORD TMP_G_T[FPGA_OPERAND_NUM_WORDS] = ED25519_G_T_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--)
+ {
+ ED25519_G_X.words[w_dst] = TMP_G_X[w_src];
+ ED25519_G_Y.words[w_dst] = TMP_G_Y[w_src];
+ ED25519_G_Z.words[w_dst] = TMP_G_Z[w_src];
+ ED25519_G_T.words[w_dst] = TMP_G_T[w_src];
+ }
+}
+
+
+//------------------------------------------------------------------------------
+//
+// Elliptic curve base point scalar multiplication routine.
+//
+// This uses Algorithm 4 ("Joye double-and-add") from "Fast and Regular
+// Algorithms for Scalar Multiplication over Elliptic Curves"
+// https://eprint.iacr.org/2011/338.pdf
+//
+//------------------------------------------------------------------------------
+void fpga_curve_ed25519_base_scalar_multiply_abstract(const FPGA_BUFFER *K, FPGA_BUFFER *Q_Y)
+//------------------------------------------------------------------------------
+{
+ int word_count, bit_count; // counters
+
+ // temporary buffers
+ FPGA_BUFFER R0_X;
+ FPGA_BUFFER R0_Y;
+ FPGA_BUFFER R0_Z;
+ FPGA_BUFFER R0_T;
+
+ FPGA_BUFFER R1_X;
+ FPGA_BUFFER R1_Y;
+ FPGA_BUFFER R1_Z;
+ FPGA_BUFFER R1_T;
+
+ FPGA_BUFFER T_X;
+ FPGA_BUFFER T_Y;
+ FPGA_BUFFER T_Z;
+ FPGA_BUFFER T_T;
+
+ // initialization
+ fpga_multiword_copy(&CURVE25519_ZERO, &R0_X);
+ fpga_multiword_copy(&CURVE25519_ONE, &R0_Y);
+ fpga_multiword_copy(&CURVE25519_ONE, &R0_Z);
+ fpga_multiword_copy(&CURVE25519_ZERO, &R0_T);
+
+ fpga_multiword_copy(&ED25519_G_X, &R1_X);
+ fpga_multiword_copy(&ED25519_G_Y, &R1_Y);
+ fpga_multiword_copy(&ED25519_G_Z, &R1_Z);
+ fpga_multiword_copy(&ED25519_G_T, &R1_T);
+
+ // force zero bits
+ FPGA_BUFFER K_INT;
+ fpga_multiword_copy(K, &K_INT);
+
+ K_INT.words[0] &= 0xFFFFFFF8;
+ K_INT.words[FPGA_OPERAND_NUM_WORDS-1] &= 0x3FFFFFFF;
+ K_INT.words[FPGA_OPERAND_NUM_WORDS-1] |= 0x40000000;
+
+
+ // handy vars
+ FPGA_WORD k_word;
+ bool k_bit = false;
+
+ // multiply
+ for (word_count=0; word_count<FPGA_OPERAND_NUM_WORDS; word_count++)
+ {
+ for (bit_count=0; bit_count<FPGA_WORD_WIDTH; bit_count++)
+ {
+ // get current bit of K
+ k_word = K_INT.words[word_count] >> bit_count;
+ k_bit = (k_word & (FPGA_WORD)1) == 1;
+
+ // symmetric processing scheme regardless of the current private bit value
+ if (k_bit)
+ {
+ // T = double(R0)
+ fpga_curve_ed25519_double( &R0_X, &R0_Y, &R0_Z, &R0_T,
+ &T_X, &T_Y, &T_Z, &T_T);
+
+ // R0 = add(T, R1)
+ fpga_curve_ed25519_add( &T_X, &T_Y, &T_Z, &T_T,
+ &R1_X, &R1_Y, &R1_Z, &R1_T,
+ &R0_X, &R0_Y, &R0_Z, &R0_T);
+ }
+ else
+ {
+ // T = double(R1)
+ fpga_curve_ed25519_double( &R1_X, &R1_Y, &R1_Z, &R1_T,
+ &T_X, &T_Y, &T_Z, &T_T);
+
+ // R1 = add(T, R0)
+ fpga_curve_ed25519_add( &T_X, &T_Y, &T_Z, &T_T,
+ &R0_X, &R0_Y, &R0_Z, &R0_T,
+ &R1_X, &R1_Y, &R1_Z, &R1_T);
+ }
+ }
+ }
+
+ // now conversion to affine coordinates
+ fpga_curve_ed25519_to_affine(&R0_X, &R0_Y, &R0_Z, &R1_X, &R1_Y);
+
+ // 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(&R1_X, &CURVE25519_ZERO, &R0_X, &CURVE25519_1P);
+ fpga_modular_add(&R1_Y, &CURVE25519_ZERO, &R0_Y, &CURVE25519_1P);
+
+ // process "sign" of x, see this Cryptography Stack Exchange
+ // answer for more details:
+ //
+ // https://crypto.stackexchange.com/questions/58921/decoding-a-ed25519-key-per-rfc8032
+ //
+ // the short story is that odd values of x are negative, so we
+ // just copy the lsb of x into msb of y
+ R0_Y.words[FPGA_OPERAND_NUM_WORDS-1] |= (R0_X.words[0] & (FPGA_WORD)1) << 31;
+
+ // store result
+ fpga_multiword_copy(&R0_Y, Q_Y);
+}
+
+
+//------------------------------------------------------------------------------
+//
+// Elliptic curve point doubling routine.
+//
+// This implements the "dbl-2008-hwcd" formulae set from
+// https://hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html
+//
+// The only difference is that E, F, G and H have opposite signs, this is
+// equivalent to the original algorithm, because the end result depends on
+// (E * F) and (G * H). If both variables have opposite signs, then the
+// sign of the product doesn't change.
+//
+//------------------------------------------------------------------------------
+void fpga_curve_ed25519_double( const FPGA_BUFFER *P_X, const FPGA_BUFFER *P_Y, const FPGA_BUFFER *P_Z, const FPGA_BUFFER *P_T,
+ FPGA_BUFFER *Q_X, FPGA_BUFFER *Q_Y, FPGA_BUFFER *Q_Z, FPGA_BUFFER *Q_T)
+{
+ FPGA_BUFFER A, B, C, D, E, F, G, H, I;
+
+ fpga_modular_mul(P_X, P_X, &A, &CURVE25519_2P); // A = (qx * qx) % mod
+ fpga_modular_mul(P_Y, P_Y, &B, &CURVE25519_2P); // B = (qy * qy) % mod
+
+ fpga_modular_mul(P_Z, P_Z, &I, &CURVE25519_2P); // I = (qz * qz) % mod
+ fpga_modular_add( &I, &I, &C, &CURVE25519_2P); // C = ( I + I) % mod
+ fpga_modular_add(P_X, P_Y, &I, &CURVE25519_2P); // I = (qx + qy) % mod
+ fpga_modular_mul( &I, &I, &D, &CURVE25519_2P); // D = ( I * I) % mod
+
+ fpga_modular_add( &A, &B, &H, &CURVE25519_2P); // H = ( A + B) % mod
+ fpga_modular_sub( &H, &D, &E, &CURVE25519_2P); // E = ( H - D) % mod
+ fpga_modular_sub( &A, &B, &G, &CURVE25519_2P); // G = ( A - B) % mod
+ fpga_modular_add( &C, &G, &F, &CURVE25519_2P); // F = ( C + G) % mod
+
+ fpga_modular_mul( &E, &F, Q_X, &CURVE25519_2P); // rx = ( E * F) % mod
+ fpga_modular_mul( &G, &H, Q_Y, &CURVE25519_2P); // ry = ( G * H) % mod
+ fpga_modular_mul( &E, &H, Q_T, &CURVE25519_2P); // rt = ( E * H) % mod
+ fpga_modular_mul( &F, &G, Q_Z, &CURVE25519_2P); // rz = ( F * G) % mod
+}
+
+
+//------------------------------------------------------------------------------
+//
+// Elliptic curve point addition routine.
+//
+// This implements the "add-2008-hwcd-4" formulae set from
+// https://hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html
+//
+//------------------------------------------------------------------------------
+void fpga_curve_ed25519_add( const FPGA_BUFFER *P_X, const FPGA_BUFFER *P_Y, const FPGA_BUFFER *P_Z, const FPGA_BUFFER *P_T,
+ const FPGA_BUFFER *Q_X, const FPGA_BUFFER *Q_Y, const FPGA_BUFFER *Q_Z, const FPGA_BUFFER *Q_T,
+ FPGA_BUFFER *R_X, FPGA_BUFFER *R_Y, FPGA_BUFFER *R_Z, FPGA_BUFFER *R_T)
+{
+ FPGA_BUFFER A, B, C, D, E, F, G, H, I, J;
+
+ fpga_modular_sub(P_Y, P_X, &I, &CURVE25519_2P); // I = (qy - qx) % mod
+ fpga_modular_add(Q_Y, Q_X, &J, &CURVE25519_2P); // J = (py + px) % mod
+ fpga_modular_mul( &I, &J, &A, &CURVE25519_2P); // A = ( I * J) % mod
+
+ fpga_modular_add(P_Y, P_X, &I, &CURVE25519_2P); // I = (qy + qx) % mod
+ fpga_modular_sub(Q_Y, Q_X, &J, &CURVE25519_2P); // J = (py - px) % mod
+ fpga_modular_mul( &I, &J, &B, &CURVE25519_2P); // B = ( I * J) % mod
+
+ fpga_modular_mul(P_Z, Q_T, &I, &CURVE25519_2P); // I = (qz * pt) % mod
+ fpga_modular_add( &I, &I, &C, &CURVE25519_2P); // C = ( I + I) % mod
+ fpga_modular_mul(P_T, Q_Z, &I, &CURVE25519_2P); // I = (qt * pz) % mod
+ fpga_modular_add( &I, &I, &D, &CURVE25519_2P); // D = ( I + I) % mod
+
+ fpga_modular_add( &D, &C, &E, &CURVE25519_2P); // E = (D + C) % mod
+ fpga_modular_sub( &B, &A, &F, &CURVE25519_2P); // F = (B - A) % mod
+ fpga_modular_add( &B, &A, &G, &CURVE25519_2P); // G = (B + A) % mod
+ fpga_modular_sub( &D, &C, &H, &CURVE25519_2P); // H = (D - C) % mod
+
+ fpga_modular_mul( &E, &F, R_X, &CURVE25519_2P); // rx = (E * F) % mod
+ fpga_modular_mul( &G, &H, R_Y, &CURVE25519_2P); // ry = (G * H) % mod
+ fpga_modular_mul( &E, &H, R_T, &CURVE25519_2P); // rt = (E * H) % mod
+ fpga_modular_mul( &F, &G, R_Z, &CURVE25519_2P); // rz = (F * G) % mod
+}
+
+
+//------------------------------------------------------------------------------
+//
+// Conversion to affine coordinates.
+//
+// Q_X = P_X / P_Z = P_X * P_Z ^ -1
+// Q_Y = P_Y / P_Z = P_Y * P_Z ^ -1
+//
+//------------------------------------------------------------------------------
+void fpga_curve_ed25519_to_affine (const FPGA_BUFFER *P_X, const FPGA_BUFFER *P_Y,
+ const FPGA_BUFFER *P_Z,
+ FPGA_BUFFER *Q_X, FPGA_BUFFER *Q_Y)
+//------------------------------------------------------------------------------
+{
+ 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);
+ fpga_modular_mul(P_Y, &P_Z_1, Q_Y, &CURVE25519_2P);
+}
+
+
+//------------------------------------------------------------------------------
+// End-of-File
+//------------------------------------------------------------------------------
diff --git a/ed25519/ed25519_fpga_curve_microcode.cpp b/ed25519/ed25519_fpga_curve_microcode.cpp
new file mode 100644
index 0000000..25826c5
--- /dev/null
+++ b/ed25519/ed25519_fpga_curve_microcode.cpp
@@ -0,0 +1,299 @@
+//------------------------------------------------------------------------------
+//
+// ed25519_fpga_curve_microcode.cpp
+// -----------------------------------------------
+// Elliptic curve arithmetic procedures for Ed25519
+//
+// Authors: Pavel Shatov
+//
+// Copyright (c) 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 "ed25519_fpga_model.h"
+
+
+//------------------------------------------------------------------------------
+enum ED25519_UOP_OPERAND
+//------------------------------------------------------------------------------
+{
+ CONST_G_X = CURVE25519_UOP_OPERAND_COUNT + 1,
+ CONST_G_Y,
+ CONST_G_T,
+
+ CYCLE_R0_X,
+ CYCLE_R0_Y,
+ CYCLE_R0_Z,
+ CYCLE_R0_T,
+
+ CYCLE_R1_X,
+ CYCLE_R1_Y,
+ CYCLE_R1_Z,
+ CYCLE_R1_T,
+
+ CYCLE_S_X,
+ CYCLE_S_Y,
+ CYCLE_S_Z,
+ CYCLE_S_T,
+
+ CYCLE_T_X,
+ CYCLE_T_Y,
+ CYCLE_T_Z,
+ CYCLE_T_T,
+
+ CYCLE_U_X,
+ CYCLE_U_Y,
+ CYCLE_U_Z,
+ CYCLE_U_T,
+
+ CYCLE_V_X,
+ CYCLE_V_Y,
+ CYCLE_V_Z,
+ CYCLE_V_T,
+
+ PROC_A,
+ PROC_B,
+ PROC_C,
+ PROC_D,
+ PROC_E,
+ PROC_F,
+ PROC_G,
+ PROC_H,
+ PROC_I,
+ PROC_J,
+
+ ED25519_UOP_OPERAND_COUNT
+};
+
+
+//------------------------------------------------------------------------------
+// Storage Buffers
+//------------------------------------------------------------------------------
+static FPGA_BUFFER BUF_LO[ED25519_UOP_OPERAND_COUNT];
+static FPGA_BUFFER BUF_HI[ED25519_UOP_OPERAND_COUNT];
+
+
+//------------------------------------------------------------------------------
+//
+// Elliptic curve point scalar multiplication routine.
+//
+//------------------------------------------------------------------------------
+void fpga_curve_ed25519_base_scalar_multiply_microcode(const FPGA_BUFFER *K, FPGA_BUFFER *QY)
+//------------------------------------------------------------------------------
+{
+ bool k_bit; // 1-bit values
+ FPGA_WORD k_word; // current word of multiplier
+ int word_count, bit_count; // counters
+
+ // initialize internal banks
+ fpga_multiword_copy(&CURVE25519_ZERO, &BUF_LO[CONST_ZERO]);
+ fpga_multiword_copy(&CURVE25519_ZERO, &BUF_HI[CONST_ZERO]);
+
+ fpga_multiword_copy(&CURVE25519_ONE, &BUF_LO[CONST_ONE]);
+ fpga_multiword_copy(&CURVE25519_ONE, &BUF_HI[CONST_ONE]);
+
+ fpga_multiword_copy(&ED25519_G_X, &BUF_LO[CONST_G_X]);
+ fpga_multiword_copy(&ED25519_G_X, &BUF_HI[CONST_G_X]);
+
+ fpga_multiword_copy(&ED25519_G_Y, &BUF_LO[CONST_G_Y]);
+ fpga_multiword_copy(&ED25519_G_Y, &BUF_HI[CONST_G_Y]);
+
+ fpga_multiword_copy(&ED25519_G_T, &BUF_LO[CONST_G_T]);
+ fpga_multiword_copy(&ED25519_G_T, &BUF_HI[CONST_G_T]);
+
+ // force certain bit values
+ FPGA_BUFFER K_INT;
+ fpga_multiword_copy(K, &K_INT);
+
+ K_INT.words[0] &= 0xFFFFFFF8;
+ K_INT.words[FPGA_OPERAND_NUM_WORDS-1] &= 0x3FFFFFFF;
+ K_INT.words[FPGA_OPERAND_NUM_WORDS-1] |= 0x40000000;
+
+ // initialization
+ uop_move(BANK_HI, CONST_ZERO, BANK_LO, CYCLE_R0_X, BUF_LO, BUF_HI);
+ uop_move(BANK_HI, CONST_ONE, BANK_LO, CYCLE_R0_Y, BUF_LO, BUF_HI);
+ uop_move(BANK_HI, CONST_ONE, BANK_LO, CYCLE_R0_Z, BUF_LO, BUF_HI);
+ uop_move(BANK_HI, CONST_ZERO, BANK_LO, CYCLE_R0_T, BUF_LO, BUF_HI);
+
+ uop_move(BANK_HI, CONST_G_X, BANK_LO, CYCLE_R1_X, BUF_LO, BUF_HI);
+ uop_move(BANK_HI, CONST_G_Y, BANK_LO, CYCLE_R1_Y, BUF_LO, BUF_HI);
+ uop_move(BANK_HI, CONST_ONE, BANK_LO, CYCLE_R1_Z, BUF_LO, BUF_HI);
+ uop_move(BANK_HI, CONST_G_T, BANK_LO, CYCLE_R1_T, BUF_LO, BUF_HI);
+
+ // multiply
+ for (word_count=0; word_count<FPGA_OPERAND_NUM_WORDS; word_count++)
+ {
+ for (bit_count=0; bit_count<FPGA_WORD_WIDTH; bit_count++)
+ {
+ // get current bit of K
+ k_word = K_INT.words[word_count] >> bit_count;
+ k_bit = (k_word & (FPGA_WORD)1) == 1;
+
+ if (k_bit)
+ {
+ // U = R0
+ // V = R1
+
+ uop_move(BANK_LO, CYCLE_R0_X, BANK_HI, CYCLE_U_X, BUF_LO, BUF_HI);
+ uop_move(BANK_LO, CYCLE_R0_Y, BANK_HI, CYCLE_U_Y, BUF_LO, BUF_HI);
+ uop_move(BANK_LO, CYCLE_R0_Z, BANK_HI, CYCLE_U_Z, BUF_LO, BUF_HI);
+ uop_move(BANK_LO, CYCLE_R0_T, BANK_HI, CYCLE_U_T, BUF_LO, BUF_HI);
+ uop_move(BANK_LO, CYCLE_R1_X, BANK_HI, CYCLE_V_X, BUF_LO, BUF_HI);
+ uop_move(BANK_LO, CYCLE_R1_Y, BANK_HI, CYCLE_V_Y, BUF_LO, BUF_HI);
+ uop_move(BANK_LO, CYCLE_R1_Z, BANK_HI, CYCLE_V_Z, BUF_LO, BUF_HI);
+ uop_move(BANK_LO, CYCLE_R1_T, BANK_HI, CYCLE_V_T, BUF_LO, BUF_HI);
+ }
+ else
+ {
+ // U = R1
+ // V = R0
+
+ uop_move(BANK_LO, CYCLE_R0_X, BANK_HI, CYCLE_V_X, BUF_LO, BUF_HI);
+ uop_move(BANK_LO, CYCLE_R0_Y, BANK_HI, CYCLE_V_Y, BUF_LO, BUF_HI);
+ uop_move(BANK_LO, CYCLE_R0_Z, BANK_HI, CYCLE_V_Z, BUF_LO, BUF_HI);
+ uop_move(BANK_LO, CYCLE_R0_T, BANK_HI, CYCLE_V_T, BUF_LO, BUF_HI);
+ uop_move(BANK_LO, CYCLE_R1_X, BANK_HI, CYCLE_U_X, BUF_LO, BUF_HI);
+ uop_move(BANK_LO, CYCLE_R1_Y, BANK_HI, CYCLE_U_Y, BUF_LO, BUF_HI);
+ uop_move(BANK_LO, CYCLE_R1_Z, BANK_HI, CYCLE_U_Z, BUF_LO, BUF_HI);
+ uop_move(BANK_LO, CYCLE_R1_T, BANK_HI, CYCLE_U_T, BUF_LO, BUF_HI);
+ }
+
+ // S = double(U)
+ uop_calc(MUL, BANK_HI, CYCLE_U_X, CYCLE_U_X, BANK_LO, PROC_A, BUF_LO, BUF_HI, MOD_2P); // fpga_modular_mul(P_X, P_X, &A, &CURVE25519_2P);
+ uop_calc(MUL, BANK_HI, CYCLE_U_Y, CYCLE_U_Y, BANK_LO, PROC_B, BUF_LO, BUF_HI, MOD_2P); // fpga_modular_mul(P_Y, P_Y, &B, &CURVE25519_2P);
+
+ uop_calc(MUL, BANK_HI, CYCLE_U_Z, CYCLE_U_Z, BANK_LO, PROC_I, BUF_LO, BUF_HI, MOD_2P); // fpga_modular_mul(P_Z, P_Z, &I, &CURVE25519_2P);
+ uop_calc(ADD, BANK_LO, PROC_I, PROC_I, BANK_HI, PROC_C, BUF_LO, BUF_HI, MOD_2P); // fpga_modular_add( &I, &I, &C, &CURVE25519_2P);
+ uop_calc(ADD, BANK_HI, CYCLE_U_X, CYCLE_U_Y, BANK_LO, PROC_I, BUF_LO, BUF_HI, MOD_2P); // fpga_modular_add(P_X, P_Y, &I, &CURVE25519_2P);
+ uop_calc(MUL, BANK_LO, PROC_I, PROC_I, BANK_HI, PROC_D, BUF_LO, BUF_HI, MOD_2P); // fpga_modular_mul( &I, &I, &D, &CURVE25519_2P);
+
+ uop_calc(ADD, BANK_LO, PROC_A, PROC_B, BANK_HI, PROC_H, BUF_LO, BUF_HI, MOD_2P); // fpga_modular_add( &A, &B, &H, &CURVE25519_2P);
+ uop_calc(SUB, BANK_HI, PROC_H, PROC_D, BANK_LO, PROC_E, BUF_LO, BUF_HI, MOD_2P); // fpga_modular_sub( &H, &D, &E, &CURVE25519_2P);
+ uop_calc(SUB, BANK_LO, PROC_A, PROC_B, BANK_HI, PROC_G, BUF_LO, BUF_HI, MOD_2P); // fpga_modular_sub( &A, &B, &G, &CURVE25519_2P);
+ uop_calc(ADD, BANK_HI, PROC_C, PROC_G, BANK_LO, PROC_F, BUF_LO, BUF_HI, MOD_2P); // fpga_modular_add( &C, &G, &F, &CURVE25519_2P);
+
+ uop_move2(BANK_HI, PROC_G, PROC_H, BANK_LO, PROC_G, PROC_H, BUF_LO, BUF_HI);
+
+ uop_calc(MUL, BANK_LO, PROC_E, PROC_F, BANK_HI, CYCLE_S_X, BUF_LO, BUF_HI, MOD_2P); // fpga_modular_mul( &E, &F, Q_X, &CURVE25519_2P);
+ uop_calc(MUL, BANK_LO, PROC_G, PROC_H, BANK_HI, CYCLE_S_Y, BUF_LO, BUF_HI, MOD_2P); // fpga_modular_mul( &G, &H, Q_Y, &CURVE25519_2P);
+
+ uop_calc(MUL, BANK_LO, PROC_E, PROC_H, BANK_HI, CYCLE_S_T, BUF_LO, BUF_HI, MOD_2P); // fpga_modular_mul( &E, &H, Q_T, &CURVE25519_2P);
+ uop_calc(MUL, BANK_LO, PROC_F, PROC_G, BANK_HI, CYCLE_S_Z, BUF_LO, BUF_HI, MOD_2P); // fpga_modular_mul( &F, &G, Q_Z, &CURVE25519_2P);
+
+ // T = add(S, V)
+ uop_calc(SUB, BANK_HI, CYCLE_S_Y, CYCLE_S_X, BANK_LO, PROC_I, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_sub(S_Y, S_X, &I, &CURVE25519_2P); // I = (qy - qx) % mod
+ uop_calc(ADD, BANK_HI, CYCLE_V_Y, CYCLE_V_X, BANK_LO, PROC_J, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_add(V_Y, V_X, &J, &CURVE25519_2P); // J = (py + px) % mod
+ uop_calc(MUL, BANK_LO, PROC_I, PROC_J, BANK_HI, PROC_A, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_mul( &I, &J, &A, &CURVE25519_2P); // A = ( I * J) % mod
+
+ uop_calc(ADD, BANK_HI, CYCLE_S_Y, CYCLE_S_X, BANK_LO, PROC_I, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_add(S_Y, S_X, &I, &CURVE25519_2P); // I = (qy + qx) % mod
+ uop_calc(SUB, BANK_HI, CYCLE_V_Y, CYCLE_V_X, BANK_LO, PROC_J, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_sub(V_Y, V_X, &J, &CURVE25519_2P); // J = (py - px) % mod
+ uop_calc(MUL, BANK_LO, PROC_I, PROC_J, BANK_HI, PROC_B, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_mul( &I, &J, &B, &CURVE25519_2P); // B = ( I * J) % mod
+
+ uop_calc(MUL, BANK_HI, CYCLE_S_Z, CYCLE_V_T, BANK_LO, PROC_I, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_mul(S_Z, V_T, &I, &CURVE25519_2P); // I = (qz * pt) % mod
+ uop_calc(ADD, BANK_LO, PROC_I, PROC_I, BANK_HI, PROC_C, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_add( &I, &I, &C, &CURVE25519_2P); // C = ( I + I) % mod
+ uop_calc(MUL, BANK_HI, CYCLE_S_T, CYCLE_V_Z, BANK_LO, PROC_I, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_mul(S_T, V_Z, &I, &CURVE25519_2P); // I = (qt * pz) % mod
+ uop_calc(ADD, BANK_LO, PROC_I, PROC_I, BANK_HI, PROC_D, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_add( &I, &I, &D, &CURVE25519_2P); // D = ( I + I) % mod
+
+ uop_calc(ADD, BANK_HI, PROC_C, PROC_D, BANK_LO, PROC_E, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_add( &D, &C, &E, &CURVE25519_2P); // E = (D + C) % mod
+ uop_calc(SUB, BANK_HI, PROC_B, PROC_A, BANK_LO, PROC_F, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_sub( &B, &A, &F, &CURVE25519_2P); // F = (B - A) % mod
+ uop_calc(ADD, BANK_HI, PROC_B, PROC_A, BANK_LO, PROC_G, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_add( &B, &A, &G, &CURVE25519_2P); // G = (B + A) % mod
+ uop_calc(SUB, BANK_HI, PROC_D, PROC_C, BANK_LO, PROC_H, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_sub( &D, &C, &H, &CURVE25519_2P); // H = (D - C) % mod
+
+ uop_calc(MUL, BANK_LO, PROC_E, PROC_F, BANK_HI, CYCLE_T_X, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_mul( &E, &F, R_X, &CURVE25519_2P); // rx = (E * F) % mod
+ uop_calc(MUL, BANK_LO, PROC_G, PROC_H, BANK_HI, CYCLE_T_Y, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_mul( &G, &H, R_Y, &CURVE25519_2P); // ry = (G * H) % mod
+ uop_calc(MUL, BANK_LO, PROC_E, PROC_H, BANK_HI, CYCLE_T_T, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_mul( &E, &H, R_T, &CURVE25519_2P); // rt = (E * H) % mod
+ uop_calc(MUL, BANK_LO, PROC_F, PROC_G, BANK_HI, CYCLE_T_Z, BUF_LO, BUF_HI, MOD_2P); //fpga_modular_mul( &F, &G, R_Z, &CURVE25519_2P); // rz = (F * G) % mod
+
+ if (k_bit)
+ {
+ // R0 = T
+
+ uop_move2(BANK_HI, CYCLE_T_X, CYCLE_T_Y, BANK_LO, CYCLE_R0_X, CYCLE_R0_Y, BUF_LO, BUF_HI);
+ uop_move2(BANK_HI, CYCLE_T_Z, CYCLE_T_T, BANK_LO, CYCLE_R0_Z, CYCLE_R0_T, BUF_LO, BUF_HI);
+ }
+ else
+ {
+ // R1 = T
+
+ uop_move2(BANK_HI, CYCLE_T_X, CYCLE_T_Y, BANK_LO, CYCLE_R1_X, CYCLE_R1_Y, BUF_LO, BUF_HI);
+ uop_move2(BANK_HI, CYCLE_T_Z, CYCLE_T_T, BANK_LO, CYCLE_R1_Z, CYCLE_R1_T, BUF_LO, BUF_HI);
+ }
+ }
+ }
+
+ // inversion expects result to be in LO: T1
+ uop_move2(BANK_LO, CYCLE_R0_Z, CYCLE_R0_Z, BANK_HI, CYCLE_R0_Z, CYCLE_R0_Z, BUF_LO, BUF_HI);
+ uop_move2(BANK_HI, CYCLE_R0_Z, CYCLE_R0_Z, BANK_LO, INVERT_T_1, INVERT_T_1, BUF_LO, BUF_HI);
+
+ // just call piece of microcode
+ fpga_modular_inv_microcode(BUF_LO, BUF_HI);
+
+ // inversion places result in HI: R1
+ // coordinates are in HI: R0_X, R0_Y
+
+ uop_move2(BANK_HI, INVERT_R1, INVERT_R1, BANK_LO, INVERT_R1, INVERT_R1, BUF_LO, BUF_HI);
+ uop_calc(MUL, BANK_LO, INVERT_R1, CYCLE_R0_X, BANK_HI, CYCLE_R0_X, BUF_LO, BUF_HI, MOD_2P);
+ uop_calc(MUL, BANK_LO, INVERT_R1, CYCLE_R0_Y, BANK_HI, CYCLE_R0_Y, BUF_LO, BUF_HI, MOD_2P);
+
+ // finally reduce to just 1*P
+ uop_calc(ADD, BANK_HI, CYCLE_R0_X, CONST_ZERO, BANK_LO, CYCLE_R0_X, BUF_LO, BUF_HI, MOD_1P); // !!!
+ uop_calc(ADD, BANK_HI, CYCLE_R0_Y, CONST_ZERO, BANK_LO, CYCLE_R0_Y, BUF_LO, BUF_HI, MOD_1P); // !!!
+
+ // poke sign bit
+ BUF_LO[CYCLE_R0_Y].words[FPGA_OPERAND_NUM_WORDS-1] |=
+ (FPGA_WORD)((BUF_LO[CYCLE_R0_X].words[0] & (FPGA_WORD)1) << 31);
+
+ // store result
+ uop_stor(BUF_LO, BUF_HI, BANK_LO, CYCLE_R0_Y, QY);
+
+
+
+ /*
+ // process "sign" of x, see this Cryptography Stack Exchange
+ // answer for more details:
+ //
+ // https://crypto.stackexchange.com/questions/58921/decoding-a-ed25519-key-per-rfc8032
+ //
+ // the short story is that odd values of x are negative, so we
+ // just copy the lsb of x into msb of y
+ R0_Y.words[FPGA_OPERAND_NUM_WORDS-1] |= (R0_X.words[0] & (FPGA_WORD)1) << 31;
+
+ // store result
+ fpga_multiword_copy(&R0_Y, QY);
+ */
+}
+
+
+//------------------------------------------------------------------------------
+// End-of-File
+//------------------------------------------------------------------------------
More information about the Commits
mailing list