* New hardware architecture

 * Randomized test vector

1 files changed, 313 insertions, 0 deletions

diff --git a/ecdsa_fpga_curve_abstract.cpp b/ecdsa_fpga_curve_abstract.cpp
new file mode 100644
index 0000000..5510ac1
--- /dev/null
+++ b/ecdsa_fpga_curve_abstract.cpp
@@ -0,0 +1,313 @@
+//------------------------------------------------------------------------------
+//
+// 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; w<FPGA_OPERAND_NUM_WORDS; w++)
+    {   ECDSA_GX.words[w] = tmp_gx.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
+        ECDSA_GY.words[w] = tmp_gy.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
+        ECDSA_HX.words[w] = tmp_hx.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
+        ECDSA_HY.words[w] = tmp_hy.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
+        ECDSA_N.words[w] = tmp_n.words[FPGA_OPERAND_NUM_WORDS - (w+1)];
+    }
+}
+
+
+//------------------------------------------------------------------------------
+//
+// Elliptic curve base point scalar multiplication routine.
+//
+// Q(qx,qy) = k * G(px,py)
+//
+// Note, that Q is supposed to be in affine coordinates. Multiplication is done
+// using the double-and-add algorithm 3.27 from "Guide to Elliptic Curve
+// Cryptography".
+//
+// WARNING: Though this procedure always does the addition step, it only
+// updates the result when current bit of k is set. 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 it anywhere near
+// production!
+//
+//------------------------------------------------------------------------------
+void fpga_curve_base_scalar_multiply_abstract(const FPGA_BUFFER *k, FPGA_BUFFER *qx, FPGA_BUFFER *qy)
+//------------------------------------------------------------------------------
+{
+    int word_count, bit_count;  // counters
+
+    FPGA_BUFFER rx, ry, rz;     // intermediate result
+    FPGA_BUFFER tx, ty, tz;     // temporary variable
+
+        /* set initial value of R to point at infinity */
+    fpga_multiword_copy(&ECDSA_ONE,  &rx);
+    fpga_multiword_copy(&ECDSA_ONE,  &ry);
+    fpga_multiword_copy(&ECDSA_ZERO, &rz);
+
+        /* process bits of k left-to-right */
+    for (word_count=FPGA_OPERAND_NUM_WORDS; word_count>0; 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
+//------------------------------------------------------------------------------