801 lines
23 KiB
C
801 lines
23 KiB
C
/*
|
|
* Copyright (c) 2009 Chris K Cockrum <ckc@cockrum.net>
|
|
*
|
|
* Copyright (c) 2013 Jens Trillmann <jtrillma@tzi.de>
|
|
* Copyright (c) 2013 Marc Müller-Weinhardt <muewei@tzi.de>
|
|
* Copyright (c) 2013 Lars Schmertmann <lars@tzi.de>
|
|
* Copyright (c) 2013 Hauke Mehrtens <hauke@hauke-m.de>
|
|
*
|
|
* Permission is hereby granted, free of charge, to any person obtaining a copy
|
|
* of this software and associated documentation files (the "Software"), to deal
|
|
* in the Software without restriction, including without limitation the rights
|
|
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
|
|
* copies of the Software, and to permit persons to whom the Software is
|
|
* furnished to do so, subject to the following conditions:
|
|
*
|
|
* The above copyright notice and this permission notice shall be included in
|
|
* all copies or substantial portions of the Software.
|
|
*
|
|
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
|
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
|
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
|
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
|
|
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
|
|
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
|
|
* THE SOFTWARE.
|
|
*
|
|
*
|
|
* This implementation is based in part on the paper Implementation of an
|
|
* Elliptic Curve Cryptosystem on an 8-bit Microcontroller [0] by
|
|
* Chris K Cockrum <ckc@cockrum.net>.
|
|
*
|
|
* [0]: http://cockrum.net/Implementation_of_ECC_on_an_8-bit_microcontroller.pdf
|
|
*
|
|
* This is a efficient ECC implementation on the secp256r1 curve for 32 Bit CPU
|
|
* architectures. It provides basic operations on the secp256r1 curve and support
|
|
* for ECDH and ECDSA.
|
|
*/
|
|
|
|
//big number functions
|
|
#include "ecc.h"
|
|
#include <string.h>
|
|
|
|
static uint32_t add(const uint32_t *x, const uint32_t *y, uint32_t *result, uint8_t length)
|
|
{
|
|
uint64_t d = 0; //carry
|
|
int v = 0;
|
|
for (v = 0; v < length; v++) {
|
|
//printf("%02x + %02x + %01x = ", x[v], y[v], d);
|
|
d += (uint64_t) x[v] + (uint64_t) y[v];
|
|
//printf("%02x\n", d);
|
|
result[v] = d;
|
|
d = d >> 32; //save carry
|
|
}
|
|
|
|
return (uint32_t)d;
|
|
}
|
|
|
|
static uint32_t sub(const uint32_t *x, const uint32_t *y, uint32_t *result, uint8_t length)
|
|
{
|
|
uint64_t d = 0;
|
|
int v;
|
|
for (v = 0; v < length; v++) {
|
|
d = (uint64_t) x[v] - (uint64_t) y[v] - d;
|
|
result[v] = d & 0xFFFFFFFF;
|
|
d = d >> 32;
|
|
d &= 0x1;
|
|
}
|
|
return (uint32_t)d;
|
|
}
|
|
|
|
static void rshiftby(const uint32_t *in, uint8_t in_size, uint32_t *out, uint8_t out_size, uint8_t shift)
|
|
{
|
|
int i;
|
|
|
|
for (i = 0; i < (in_size - shift) && i < out_size; i++) {
|
|
out[i] = in[i + shift];
|
|
}
|
|
for (/* reuse i */; i < out_size; i++) {
|
|
out[i] = 0;
|
|
}
|
|
}
|
|
|
|
//finite field functions
|
|
//FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
|
|
static const uint32_t ecc_prime_m[8] = {0xffffffff, 0xffffffff, 0xffffffff, 0x00000000,
|
|
0x00000000, 0x00000000, 0x00000001, 0xffffffff
|
|
};
|
|
|
|
|
|
/* This is added after an static byte addition if the answer has a carry in MSB*/
|
|
static const uint32_t ecc_prime_r[8] = {0x00000001, 0x00000000, 0x00000000, 0xffffffff,
|
|
0xffffffff, 0xffffffff, 0xfffffffe, 0x00000000
|
|
};
|
|
|
|
// ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
|
|
static const uint32_t ecc_order_m[9] = {0xFC632551, 0xF3B9CAC2, 0xA7179E84, 0xBCE6FAAD,
|
|
0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0xFFFFFFFF,
|
|
0x00000000
|
|
};
|
|
|
|
static const uint32_t ecc_order_r[8] = {0x039CDAAF, 0x0C46353D, 0x58E8617B, 0x43190552,
|
|
0x00000000, 0x00000000, 0xFFFFFFFF, 0x00000000
|
|
};
|
|
|
|
static const uint32_t ecc_order_mu[9] = {0xEEDF9BFE, 0x012FFD85, 0xDF1A6C21, 0x43190552,
|
|
0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0x00000000,
|
|
0x00000001
|
|
};
|
|
|
|
static const uint8_t ecc_order_k = 8;
|
|
|
|
const uint32_t ecc_g_point_x[8] = { 0xD898C296, 0xF4A13945, 0x2DEB33A0, 0x77037D81,
|
|
0x63A440F2, 0xF8BCE6E5, 0xE12C4247, 0x6B17D1F2
|
|
};
|
|
const uint32_t ecc_g_point_y[8] = { 0x37BF51F5, 0xCBB64068, 0x6B315ECE, 0x2BCE3357,
|
|
0x7C0F9E16, 0x8EE7EB4A, 0xFE1A7F9B, 0x4FE342E2
|
|
};
|
|
|
|
|
|
static void setZero(uint32_t *A, const int length)
|
|
{
|
|
memset(A, 0x0, length * sizeof(uint32_t));
|
|
}
|
|
|
|
/*
|
|
* copy one array to another
|
|
*/
|
|
static void copy(const uint32_t *from, uint32_t *to, uint8_t length)
|
|
{
|
|
memcpy(to, from, length * sizeof(uint32_t));
|
|
}
|
|
|
|
static int isSame(const uint32_t *A, const uint32_t *B, uint8_t length)
|
|
{
|
|
return !memcmp(A, B, length * sizeof(uint32_t));
|
|
}
|
|
|
|
//is A greater than B?
|
|
static int isGreater(const uint32_t *A, const uint32_t *B, uint8_t length)
|
|
{
|
|
int i;
|
|
for (i = length - 1; i >= 0; --i) {
|
|
if (A[i] > B[i]) {
|
|
return 1;
|
|
}
|
|
if (A[i] < B[i]) {
|
|
return -1;
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
|
|
static int fieldAdd(const uint32_t *x, const uint32_t *y, const uint32_t *reducer, uint32_t *result)
|
|
{
|
|
if (add(x, y, result, arrayLength)) { //add prime if carry is still set!
|
|
uint32_t tempas[8];
|
|
setZero(tempas, 8);
|
|
add(result, reducer, tempas, arrayLength);
|
|
copy(tempas, result, arrayLength);
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
static int fieldSub(const uint32_t *x, const uint32_t *y, const uint32_t *modulus, uint32_t *result)
|
|
{
|
|
if (sub(x, y, result, arrayLength)) { //add modulus if carry is set
|
|
uint32_t tempas[8];
|
|
setZero(tempas, 8);
|
|
add(result, modulus, tempas, arrayLength);
|
|
copy(tempas, result, arrayLength);
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
//finite Field multiplication
|
|
//32bit * 32bit = 64bit
|
|
static int fieldMult(const uint32_t *x, const uint32_t *y, uint32_t *result, uint8_t length)
|
|
{
|
|
uint32_t temp[length * 2];
|
|
setZero(temp, length * 2);
|
|
setZero(result, length * 2);
|
|
uint8_t k, n;
|
|
uint64_t l;
|
|
for (k = 0; k < length; k++) {
|
|
for (n = 0; n < length; n++) {
|
|
l = (uint64_t)x[n] * (uint64_t)y[k];
|
|
temp[n + k] = l & 0xFFFFFFFF;
|
|
temp[n + k + 1] = l >> 32;
|
|
add(&temp[n + k], &result[n + k], &result[n + k], (length * 2) - (n + k));
|
|
|
|
setZero(temp, length * 2);
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
//TODO: maximum:
|
|
//fffffffe00000002fffffffe0000000100000001fffffffe00000001fffffffe00000001fffffffefffffffffffffffffffffffe000000000000000000000001_16
|
|
static void fieldModP(uint32_t *A, const uint32_t *B)
|
|
{
|
|
uint32_t tempm[8];
|
|
uint32_t tempm2[8];
|
|
uint8_t n;
|
|
setZero(tempm, 8);
|
|
setZero(tempm2, 8);
|
|
/* A = T */
|
|
copy(B, A, arrayLength);
|
|
|
|
/* Form S1 */
|
|
for (n = 0; n < 3; n++) {
|
|
tempm[n] = 0;
|
|
}
|
|
for (n = 3; n < 8; n++) {
|
|
tempm[n] = B[n + 8];
|
|
}
|
|
|
|
/* tempm2=T+S1 */
|
|
fieldAdd(A, tempm, ecc_prime_r, tempm2);
|
|
/* A=T+S1+S1 */
|
|
fieldAdd(tempm2, tempm, ecc_prime_r, A);
|
|
/* Form S2 */
|
|
for (n = 0; n < 3; n++) {
|
|
tempm[n] = 0;
|
|
}
|
|
for (n = 3; n < 7; n++) {
|
|
tempm[n] = B[n + 9];
|
|
}
|
|
for (n = 7; n < 8; n++) {
|
|
tempm[n] = 0;
|
|
}
|
|
/* tempm2=T+S1+S1+S2 */
|
|
fieldAdd(A, tempm, ecc_prime_r, tempm2);
|
|
/* A=T+S1+S1+S2+S2 */
|
|
fieldAdd(tempm2, tempm, ecc_prime_r, A);
|
|
/* Form S3 */
|
|
for (n = 0; n < 3; n++) {
|
|
tempm[n] = B[n + 8];
|
|
}
|
|
for (n = 3; n < 6; n++) {
|
|
tempm[n] = 0;
|
|
}
|
|
for (n = 6; n < 8; n++) {
|
|
tempm[n] = B[n + 8];
|
|
}
|
|
/* tempm2=T+S1+S1+S2+S2+S3 */
|
|
fieldAdd(A, tempm, ecc_prime_r, tempm2);
|
|
/* Form S4 */
|
|
for (n = 0; n < 3; n++) {
|
|
tempm[n] = B[n + 9];
|
|
}
|
|
for (n = 3; n < 6; n++) {
|
|
tempm[n] = B[n + 10];
|
|
}
|
|
for (n = 6; n < 7; n++) {
|
|
tempm[n] = B[n + 7];
|
|
}
|
|
for (n = 7; n < 8; n++) {
|
|
tempm[n] = B[n + 1];
|
|
}
|
|
/* A=T+S1+S1+S2+S2+S3+S4 */
|
|
fieldAdd(tempm2, tempm, ecc_prime_r, A);
|
|
/* Form D1 */
|
|
for (n = 0; n < 3; n++) {
|
|
tempm[n] = B[n + 11];
|
|
}
|
|
for (n = 3; n < 6; n++) {
|
|
tempm[n] = 0;
|
|
}
|
|
for (n = 6; n < 7; n++) {
|
|
tempm[n] = B[n + 2];
|
|
}
|
|
for (n = 7; n < 8; n++) {
|
|
tempm[n] = B[n + 3];
|
|
}
|
|
/* tempm2=T+S1+S1+S2+S2+S3+S4-D1 */
|
|
fieldSub(A, tempm, ecc_prime_m, tempm2);
|
|
/* Form D2 */
|
|
for (n = 0; n < 4; n++) {
|
|
tempm[n] = B[n + 12];
|
|
}
|
|
for (n = 4; n < 6; n++) {
|
|
tempm[n] = 0;
|
|
}
|
|
for (n = 6; n < 7; n++) {
|
|
tempm[n] = B[n + 3];
|
|
}
|
|
for (n = 7; n < 8; n++) {
|
|
tempm[n] = B[n + 4];
|
|
}
|
|
/* A=T+S1+S1+S2+S2+S3+S4-D1-D2 */
|
|
fieldSub(tempm2, tempm, ecc_prime_m, A);
|
|
/* Form D3 */
|
|
for (n = 0; n < 3; n++) {
|
|
tempm[n] = B[n + 13];
|
|
}
|
|
for (n = 3; n < 6; n++) {
|
|
tempm[n] = B[n + 5];
|
|
}
|
|
for (n = 6; n < 7; n++) {
|
|
tempm[n] = 0;
|
|
}
|
|
for (n = 7; n < 8; n++) {
|
|
tempm[n] = B[n + 5];
|
|
}
|
|
/* tempm2=T+S1+S1+S2+S2+S3+S4-D1-D2-D3 */
|
|
fieldSub(A, tempm, ecc_prime_m, tempm2);
|
|
/* Form D4 */
|
|
for (n = 0; n < 2; n++) {
|
|
tempm[n] = B[n + 14];
|
|
}
|
|
for (n = 2; n < 3; n++) {
|
|
tempm[n] = 0;
|
|
}
|
|
for (n = 3; n < 6; n++) {
|
|
tempm[n] = B[n + 6];
|
|
}
|
|
for (n = 6; n < 7; n++) {
|
|
tempm[n] = 0;
|
|
}
|
|
for (n = 7; n < 8; n++) {
|
|
tempm[n] = B[n + 6];
|
|
}
|
|
/* A=T+S1+S1+S2+S2+S3+S4-D1-D2-D3-D4 */
|
|
fieldSub(tempm2, tempm, ecc_prime_m, A);
|
|
if (isGreater(A, ecc_prime_m, arrayLength) >= 0) {
|
|
fieldSub(A, ecc_prime_m, ecc_prime_m, tempm);
|
|
copy(tempm, A, arrayLength);
|
|
}
|
|
}
|
|
|
|
/**
|
|
* calculate the result = A mod n.
|
|
* n is the order of the eliptic curve.
|
|
* A and result could point to the same value
|
|
*
|
|
* A: input value (max size * 4 bytes)
|
|
* result: result of modulo calculation (max 36 bytes)
|
|
* size: size of A
|
|
*
|
|
* This uses the Barrett modular reduction as described in the Handbook
|
|
* of Applied Cryptography 14.42 Algorithm Barrett modular reduction,
|
|
* see http://cacr.uwaterloo.ca/hac/about/chap14.pdf and
|
|
* http://everything2.com/title/Barrett+Reduction
|
|
*
|
|
* b = 32 (bite size of the processor architecture)
|
|
* mu (ecc_order_mu) was precomputed in a java program
|
|
*/
|
|
static void fieldModO(const uint32_t *A, uint32_t *result, uint8_t length)
|
|
{
|
|
// This is used for value q1 and q3
|
|
uint32_t q1_q3[9];
|
|
// This is used for q2 and a temp var
|
|
uint32_t q2_tmp[18];
|
|
|
|
// return if the given value is smaller than the modulus
|
|
if (length == arrayLength && isGreater(A, ecc_order_m, arrayLength) <= 0) {
|
|
if (A != result) {
|
|
copy(A, result, length);
|
|
}
|
|
return;
|
|
}
|
|
|
|
rshiftby(A, length, q1_q3, 9, ecc_order_k - 1);
|
|
|
|
fieldMult(ecc_order_mu, q1_q3, q2_tmp, 9);
|
|
|
|
rshiftby(q2_tmp, 18, q1_q3, 8, ecc_order_k + 1);
|
|
|
|
// r1 = first 9 blocks of A
|
|
|
|
fieldMult(q1_q3, ecc_order_m, q2_tmp, 8);
|
|
|
|
// r2 = first 9 blocks of q2_tmp
|
|
|
|
sub(A, q2_tmp, result, 9);
|
|
|
|
while (isGreater(result, ecc_order_m, 9) >= 0) {
|
|
sub(result, ecc_order_m, result, 9);
|
|
}
|
|
}
|
|
|
|
static int isOne(const uint32_t *A)
|
|
{
|
|
uint8_t n;
|
|
for (n = 1; n < 8; n++)
|
|
if (A[n] != 0) {
|
|
break;
|
|
}
|
|
|
|
if ((n == 8) && (A[0] == 1)) {
|
|
return 1;
|
|
} else {
|
|
return 0;
|
|
}
|
|
}
|
|
|
|
static int isZero(const uint32_t *A)
|
|
{
|
|
uint8_t n, r = 0;
|
|
for (n = 0; n < 8; n++) {
|
|
if (A[n] == 0) {
|
|
r++;
|
|
}
|
|
}
|
|
return r == 8;
|
|
}
|
|
|
|
static void rshift(uint32_t *A)
|
|
{
|
|
int n, i;
|
|
uint32_t nOld = 0;
|
|
for (i = 8; i--;) {
|
|
n = A[i] & 0x1;
|
|
A[i] = A[i] >> 1 | nOld << 31;
|
|
nOld = n;
|
|
}
|
|
}
|
|
|
|
static int fieldAddAndDivide(const uint32_t *x, const uint32_t *modulus, const uint32_t *reducer, uint32_t *result)
|
|
{
|
|
uint32_t n = add(x, modulus, result, arrayLength);
|
|
rshift(result);
|
|
if (n) { //add prime if carry is still set!
|
|
result[7] |= 0x80000000;//add the carry
|
|
if (isGreater(result, modulus, arrayLength) == 1) {
|
|
uint32_t tempas[8];
|
|
setZero(tempas, 8);
|
|
add(result, reducer, tempas, 8);
|
|
copy(tempas, result, arrayLength);
|
|
}
|
|
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
/*
|
|
* Inverse A and output to B
|
|
*/
|
|
static void fieldInv(const uint32_t *A, const uint32_t *modulus, const uint32_t *reducer, uint32_t *B)
|
|
{
|
|
uint32_t u[8], v[8], x1[8], x2[8];
|
|
uint32_t tempm[8];
|
|
uint32_t tempm2[8];
|
|
setZero(tempm, 8);
|
|
setZero(tempm2, 8);
|
|
setZero(u, 8);
|
|
setZero(v, 8);
|
|
|
|
uint8_t t;
|
|
copy(A, u, arrayLength);
|
|
copy(modulus, v, arrayLength);
|
|
setZero(x1, 8);
|
|
setZero(x2, 8);
|
|
x1[0] = 1;
|
|
/* While u !=1 and v !=1 */
|
|
while ((isOne(u) || isOne(v)) == 0) {
|
|
while (!(u[0] & 1)) { /* While u is even */
|
|
rshift(u); /* divide by 2 */
|
|
if (!(x1[0] & 1)) { /*ifx1iseven*/
|
|
rshift(x1); /* Divide by 2 */
|
|
} else {
|
|
fieldAddAndDivide(x1, modulus, reducer, tempm); /* tempm=x1+p */
|
|
copy(tempm, x1, arrayLength); /* x1=tempm */
|
|
//rshift(x1); /* Divide by 2 */
|
|
}
|
|
}
|
|
while (!(v[0] & 1)) { /* While v is even */
|
|
rshift(v); /* divide by 2 */
|
|
if (!(x2[0] & 1)) { /*ifx1iseven*/
|
|
rshift(x2); /* Divide by 2 */
|
|
} else {
|
|
fieldAddAndDivide(x2, modulus, reducer, tempm); /* tempm=x1+p */
|
|
copy(tempm, x2, arrayLength); /* x1=tempm */
|
|
//rshift(x2); /* Divide by 2 */
|
|
}
|
|
|
|
}
|
|
t = sub(u, v, tempm, arrayLength); /* tempm=u-v */
|
|
if (t == 0) { /* If u > 0 */
|
|
copy(tempm, u, arrayLength); /* u=u-v */
|
|
fieldSub(x1, x2, modulus, tempm); /* tempm=x1-x2 */
|
|
copy(tempm, x1, arrayLength); /* x1=x1-x2 */
|
|
} else {
|
|
sub(v, u, tempm, arrayLength); /* tempm=v-u */
|
|
copy(tempm, v, arrayLength); /* v=v-u */
|
|
fieldSub(x2, x1, modulus, tempm); /* tempm=x2-x1 */
|
|
copy(tempm, x2, arrayLength); /* x2=x2-x1 */
|
|
}
|
|
}
|
|
if (isOne(u)) {
|
|
copy(x1, B, arrayLength);
|
|
} else {
|
|
copy(x2, B, arrayLength);
|
|
}
|
|
}
|
|
|
|
void static ec_double(const uint32_t *px, const uint32_t *py, uint32_t *Dx, uint32_t *Dy)
|
|
{
|
|
uint32_t tempA[8];
|
|
uint32_t tempB[8];
|
|
uint32_t tempC[8];
|
|
uint32_t tempD[16];
|
|
|
|
if (isZero(px) && isZero(py)) {
|
|
copy(px, Dx, arrayLength);
|
|
copy(py, Dy, arrayLength);
|
|
return;
|
|
}
|
|
|
|
fieldMult(px, px, tempD, arrayLength);
|
|
fieldModP(tempA, tempD);
|
|
setZero(tempB, 8);
|
|
tempB[0] = 0x00000001;
|
|
fieldSub(tempA, tempB, ecc_prime_m, tempC); //tempC = (qx^2-1)
|
|
tempB[0] = 0x00000003;
|
|
fieldMult(tempC, tempB, tempD, arrayLength);
|
|
fieldModP(tempA, tempD);//tempA = 3*(qx^2-1)
|
|
fieldAdd(py, py, ecc_prime_r, tempB); //tempB = 2*qy
|
|
fieldInv(tempB, ecc_prime_m, ecc_prime_r, tempC); //tempC = 1/(2*qy)
|
|
fieldMult(tempA, tempC, tempD, arrayLength); //tempB = lambda = (3*(qx^2-1))/(2*qy)
|
|
fieldModP(tempB, tempD);
|
|
|
|
fieldMult(tempB, tempB, tempD, arrayLength); //tempC = lambda^2
|
|
fieldModP(tempC, tempD);
|
|
fieldSub(tempC, px, ecc_prime_m, tempA); //lambda^2 - Px
|
|
fieldSub(tempA, px, ecc_prime_m, Dx); //lambda^2 - Px - Qx
|
|
|
|
fieldSub(px, Dx, ecc_prime_m, tempA); //tempA = qx-dx
|
|
fieldMult(tempB, tempA, tempD, arrayLength); //tempC = lambda * (qx-dx)
|
|
fieldModP(tempC, tempD);
|
|
fieldSub(tempC, py, ecc_prime_m, Dy); //Dy = lambda * (qx-dx) - px
|
|
}
|
|
|
|
void static ec_add(const uint32_t *px, const uint32_t *py, const uint32_t *qx, const uint32_t *qy, uint32_t *Sx, uint32_t *Sy)
|
|
{
|
|
uint32_t tempA[8];
|
|
uint32_t tempB[8];
|
|
uint32_t tempC[8];
|
|
uint32_t tempD[16];
|
|
|
|
if (isZero(px) && isZero(py)) {
|
|
copy(qx, Sx, arrayLength);
|
|
copy(qy, Sy, arrayLength);
|
|
return;
|
|
} else if (isZero(qx) && isZero(qy)) {
|
|
copy(px, Sx, arrayLength);
|
|
copy(py, Sy, arrayLength);
|
|
return;
|
|
}
|
|
|
|
if (isSame(px, qx, arrayLength)) {
|
|
if (!isSame(py, qy, arrayLength)) {
|
|
setZero(Sx, 8);
|
|
setZero(Sy, 8);
|
|
return;
|
|
} else {
|
|
ec_double(px, py, Sx, Sy);
|
|
return;
|
|
}
|
|
}
|
|
|
|
fieldSub(py, qy, ecc_prime_m, tempA);
|
|
fieldSub(px, qx, ecc_prime_m, tempB);
|
|
fieldInv(tempB, ecc_prime_m, ecc_prime_r, tempB);
|
|
fieldMult(tempA, tempB, tempD, arrayLength);
|
|
fieldModP(tempC, tempD); //tempC = lambda
|
|
|
|
fieldMult(tempC, tempC, tempD, arrayLength); //tempA = lambda^2
|
|
fieldModP(tempA, tempD);
|
|
fieldSub(tempA, px, ecc_prime_m, tempB); //lambda^2 - Px
|
|
fieldSub(tempB, qx, ecc_prime_m, Sx); //lambda^2 - Px - Qx
|
|
|
|
fieldSub(qx, Sx, ecc_prime_m, tempB);
|
|
fieldMult(tempC, tempB, tempD, arrayLength);
|
|
fieldModP(tempC, tempD);
|
|
fieldSub(tempC, qy, ecc_prime_m, Sy);
|
|
}
|
|
|
|
void ecc_ec_mult(const uint32_t *px, const uint32_t *py, const uint32_t *secret, uint32_t *resultx, uint32_t *resulty)
|
|
{
|
|
uint32_t Qx[8];
|
|
uint32_t Qy[8];
|
|
setZero(Qx, 8);
|
|
setZero(Qy, 8);
|
|
|
|
uint32_t tempx[8];
|
|
uint32_t tempy[8];
|
|
|
|
int i;
|
|
for (i = 256; i--;) {
|
|
ec_double(Qx, Qy, tempx, tempy);
|
|
copy(tempx, Qx, arrayLength);
|
|
copy(tempy, Qy, arrayLength);
|
|
if (((secret[i / 32]) & ((uint32_t)1 << (i % 32)))) {
|
|
ec_add(Qx, Qy, px, py, tempx, tempy); //eccAdd
|
|
copy(tempx, Qx, arrayLength);
|
|
copy(tempy, Qy, arrayLength);
|
|
}
|
|
}
|
|
copy(Qx, resultx, arrayLength);
|
|
copy(Qy, resulty, arrayLength);
|
|
}
|
|
|
|
/**
|
|
* Calculate the ecdsa signature.
|
|
*
|
|
* For a description of this algorithm see
|
|
* https://en.wikipedia.org/wiki/Elliptic_Curve_DSA#Signature_generation_algorithm
|
|
*
|
|
* input:
|
|
* d: private key on the curve secp256r1 (32 bytes)
|
|
* e: hash to sign (32 bytes)
|
|
* k: random data, this must be changed for every signature (32 bytes)
|
|
*
|
|
* output:
|
|
* r: r value of the signature (36 bytes)
|
|
* s: s value of the signature (36 bytes)
|
|
*
|
|
* return:
|
|
* 0: everything is ok
|
|
* -1: can not create signature, try again with different k.
|
|
*/
|
|
int ecc_ecdsa_sign(const uint32_t *d, const uint32_t *e, const uint32_t *k, uint32_t *r, uint32_t *s)
|
|
{
|
|
uint32_t tmp1[16];
|
|
uint32_t tmp2[9];
|
|
uint32_t tmp3[9];
|
|
|
|
if (isZero(k)) {
|
|
return -1;
|
|
}
|
|
|
|
// 4. Calculate the curve point (x_1, y_1) = k * G.
|
|
ecc_ec_mult(ecc_g_point_x, ecc_g_point_y, k, r, tmp1);
|
|
|
|
// 5. Calculate r = x_1 \pmod{n}.
|
|
fieldModO(r, r, 8);
|
|
|
|
// 5. If r = 0, go back to step 3.
|
|
if (isZero(r)) {
|
|
return -1;
|
|
}
|
|
|
|
// 6. Calculate s = k^{-1}(z + r d_A) \pmod{n}.
|
|
// 6. r * d
|
|
fieldMult(r, d, tmp1, arrayLength);
|
|
fieldModO(tmp1, tmp2, 16);
|
|
|
|
// 6. z + (r d)
|
|
tmp1[8] = add(e, tmp2, tmp1, 8);
|
|
fieldModO(tmp1, tmp3, 9);
|
|
|
|
// 6. k^{-1}
|
|
fieldInv(k, ecc_order_m, ecc_order_r, tmp2);
|
|
|
|
// 6. (k^{-1}) (z + (r d))
|
|
fieldMult(tmp2, tmp3, tmp1, arrayLength);
|
|
fieldModO(tmp1, s, 16);
|
|
|
|
// 6. If s = 0, go back to step 3.
|
|
if (isZero(s)) {
|
|
return -1;
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* Verifies a ecdsa signature.
|
|
*
|
|
* For a description of this algorithm see
|
|
* https://en.wikipedia.org/wiki/Elliptic_Curve_DSA#Signature_verification_algorithm
|
|
*
|
|
* input:
|
|
* x: x coordinate of the public key (32 bytes)
|
|
* y: y coordinate of the public key (32 bytes)
|
|
* e: hash to verify the signature of (32 bytes)
|
|
* r: r value of the signature (32 bytes)
|
|
* s: s value of the signature (32 bytes)
|
|
*
|
|
* return:
|
|
* 0: signature is ok
|
|
* -1: signature check failed the signature is invalid
|
|
*/
|
|
int ecc_ecdsa_validate(const uint32_t *x, const uint32_t *y, const uint32_t *e, const uint32_t *r, const uint32_t *s)
|
|
{
|
|
uint32_t w[8];
|
|
uint32_t tmp[16];
|
|
uint32_t u1[9];
|
|
uint32_t u2[9];
|
|
uint32_t tmp1_x[8];
|
|
uint32_t tmp1_y[8];
|
|
uint32_t tmp2_x[8];
|
|
uint32_t tmp2_y[8];
|
|
uint32_t tmp3_x[8];
|
|
uint32_t tmp3_y[8];
|
|
|
|
// 3. Calculate w = s^{-1} \pmod{n}
|
|
fieldInv(s, ecc_order_m, ecc_order_r, w);
|
|
|
|
// 4. Calculate u_1 = zw \pmod{n}
|
|
fieldMult(e, w, tmp, arrayLength);
|
|
fieldModO(tmp, u1, 16);
|
|
|
|
// 4. Calculate u_2 = rw \pmod{n}
|
|
fieldMult(r, w, tmp, arrayLength);
|
|
fieldModO(tmp, u2, 16);
|
|
|
|
// 5. Calculate the curve point (x_1, y_1) = u_1 * G + u_2 * Q_A.
|
|
// tmp1 = u_1 * G
|
|
ecc_ec_mult(ecc_g_point_x, ecc_g_point_y, u1, tmp1_x, tmp1_y);
|
|
|
|
// tmp2 = u_2 * Q_A
|
|
ecc_ec_mult(x, y, u2, tmp2_x, tmp2_y);
|
|
|
|
// tmp3 = tmp1 + tmp2
|
|
ec_add(tmp1_x, tmp1_y, tmp2_x, tmp2_y, tmp3_x, tmp3_y);
|
|
// TODO: this u_1 * G + u_2 * Q_A could be optimiced with Straus's algorithm.
|
|
|
|
return isSame(tmp3_x, r, arrayLength) ? 0 : -1;
|
|
}
|
|
|
|
int ecc_is_valid_key(const uint32_t *priv_key)
|
|
{
|
|
return isGreater(ecc_order_m, priv_key, arrayLength) == 1;
|
|
}
|
|
|
|
/*
|
|
* This exports the low level functions so the tests can use them.
|
|
* In real use the compiler is now bale to optimice the code better.
|
|
*/
|
|
#ifdef TEST_INCLUDE
|
|
uint32_t ecc_add(const uint32_t *x, const uint32_t *y, uint32_t *result, uint8_t length)
|
|
{
|
|
return add(x, y, result, length);
|
|
}
|
|
uint32_t ecc_sub(const uint32_t *x, const uint32_t *y, uint32_t *result, uint8_t length)
|
|
{
|
|
return sub(x, y, result, length);
|
|
}
|
|
int ecc_fieldAdd(const uint32_t *x, const uint32_t *y, const uint32_t *reducer, uint32_t *result)
|
|
{
|
|
return fieldAdd(x, y, reducer, result);
|
|
}
|
|
int ecc_fieldSub(const uint32_t *x, const uint32_t *y, const uint32_t *modulus, uint32_t *result)
|
|
{
|
|
return fieldSub(x, y, modulus, result);
|
|
}
|
|
int ecc_fieldMult(const uint32_t *x, const uint32_t *y, uint32_t *result, uint8_t length)
|
|
{
|
|
return fieldMult(x, y, result, length);
|
|
}
|
|
void ecc_fieldModP(uint32_t *A, const uint32_t *B)
|
|
{
|
|
fieldModP(A, B);
|
|
}
|
|
void ecc_fieldModO(const uint32_t *A, uint32_t *result, uint8_t length)
|
|
{
|
|
fieldModO(A, result, length);
|
|
}
|
|
void ecc_fieldInv(const uint32_t *A, const uint32_t *modulus, const uint32_t *reducer, uint32_t *B)
|
|
{
|
|
fieldInv(A, modulus, reducer, B);
|
|
}
|
|
void ecc_copy(const uint32_t *from, uint32_t *to, uint8_t length)
|
|
{
|
|
copy(from, to, length);
|
|
}
|
|
int ecc_isSame(const uint32_t *A, const uint32_t *B, uint8_t length)
|
|
{
|
|
return isSame(A, B, length);
|
|
}
|
|
void ecc_setZero(uint32_t *A, const int length)
|
|
{
|
|
setZero(A, length);
|
|
}
|
|
int ecc_isOne(const uint32_t *A)
|
|
{
|
|
return isOne(A);
|
|
}
|
|
void ecc_rshift(uint32_t *A)
|
|
{
|
|
rshift(A);
|
|
}
|
|
int ecc_isGreater(const uint32_t *A, const uint32_t *B, uint8_t length)
|
|
{
|
|
return isGreater(A, B, length);
|
|
}
|
|
|
|
void ecc_ec_add(const uint32_t *px, const uint32_t *py, const uint32_t *qx, const uint32_t *qy, uint32_t *Sx, uint32_t *Sy)
|
|
{
|
|
ec_add(px, py, qx, qy, Sx, Sy);
|
|
}
|
|
void ecc_ec_double(const uint32_t *px, const uint32_t *py, uint32_t *Dx, uint32_t *Dy)
|
|
{
|
|
ec_double(px, py, Dx, Dy);
|
|
}
|
|
|
|
#endif /* TEST_INCLUDE */
|