//------------------------------------------------------------------------------
//
// 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
//------------------------------------------------------------------------------
