Diff: ecc/ecc.c

Revision:

0:ff9ebe0cf0e9

diff -r 000000000000 -r ff9ebe0cf0e9 ecc/ecc.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ecc/ecc.c	Fri Oct 18 13:18:30 2013 +0000
@@ -0,0 +1,720 @@
+/*
+ * 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"
+
+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){
+	int i;
+
+	for (i = 0; i < length; ++i)
+	{
+		A[i] = 0;
+	}
+}
+
+/*
+ * copy one array to another
+ */
+static void copy(const uint32_t *from, uint32_t *to, uint8_t length){
+	int i;
+	for (i = 0; i < length; ++i)
+	{
+		to[i] = from[i];
+	}
+}
+
+static int isSame(const uint32_t *A, const uint32_t *B, uint8_t length){
+	int i;
+
+	for(i = 0; i < length; i++){
+		if (A[i] != B[i])
+			return 0;
+	}
+	return 1;
+}
+
+//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, 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])>>(i%32)) & 0x01) == 1){ //<- TODO quark, muss anders gemacht werden
+			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 */