Re-added ECC implementation
Covered by CQ 10516:
http://dev.eclipse.org/ipzilla/show_bug.cgi?id=10516
diff --git a/ecc/ecc.c b/ecc/ecc.c
new file mode 100644
index 0000000..c6c8497
--- /dev/null
+++ b/ecc/ecc.c
@@ -0,0 +1,707 @@
+/*
+ * 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 */
diff --git a/ecc/ecc.h b/ecc/ecc.h
new file mode 100644
index 0000000..3c0d9b1
--- /dev/null
+++ b/ecc/ecc.h
@@ -0,0 +1,86 @@
+/*
+ * 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.
+ */
+#include <inttypes.h>
+
+#define keyLengthInBytes 32
+#define arrayLength 8
+
+extern const uint32_t ecc_g_point_x[8];
+extern const uint32_t ecc_g_point_y[8];
+
+//ec Functions
+void ecc_ec_mult(const uint32_t *px, const uint32_t *py, const uint32_t *secret, uint32_t *resultx, uint32_t *resulty);
+
+static inline void ecc_ecdh(const uint32_t *px, const uint32_t *py, const uint32_t *secret, uint32_t *resultx, uint32_t *resulty) {
+ ecc_ec_mult(px, py, secret, resultx, resulty);
+}
+int ecc_ecdsa_validate(const uint32_t *x, const uint32_t *y, const uint32_t *e, const uint32_t *r, const uint32_t *s);
+int ecc_ecdsa_sign(const uint32_t *d, const uint32_t *e, const uint32_t *k, uint32_t *r, uint32_t *s);
+
+int ecc_is_valid_key(const uint32_t * priv_key);
+static inline void ecc_gen_pub_key(const uint32_t *priv_key, uint32_t *pub_x, uint32_t *pub_y)
+{
+ ecc_ec_mult(ecc_g_point_x, ecc_g_point_y, priv_key, pub_x, pub_y);
+}
+
+#ifdef TEST_INCLUDE
+//ec Functions
+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);
+void ecc_ec_double(const uint32_t *px, const uint32_t *py, uint32_t *Dx, uint32_t *Dy);
+
+//simple Functions for addition and substraction of big numbers
+uint32_t ecc_add( const uint32_t *x, const uint32_t *y, uint32_t *result, uint8_t length);
+uint32_t ecc_sub( const uint32_t *x, const uint32_t *y, uint32_t *result, uint8_t length);
+
+//field functions for big numbers
+int ecc_fieldAdd(const uint32_t *x, const uint32_t *y, const uint32_t *reducer, uint32_t *result);
+int ecc_fieldSub(const uint32_t *x, const uint32_t *y, const uint32_t *modulus, uint32_t *result);
+int ecc_fieldMult(const uint32_t *x, const uint32_t *y, uint32_t *result, uint8_t length);
+void ecc_fieldModP(uint32_t *A, const uint32_t *B);
+void ecc_fieldModO(const uint32_t *A, uint32_t *result, uint8_t length);
+void ecc_fieldInv(const uint32_t *A, const uint32_t *modulus, const uint32_t *reducer, uint32_t *B);
+
+//simple functions to work with the big numbers
+void ecc_copy(const uint32_t *from, uint32_t *to, uint8_t length);
+int ecc_isSame(const uint32_t *A, const uint32_t *B, uint8_t length);
+void ecc_setZero(uint32_t *A, const int length);
+int ecc_isOne(const uint32_t* A);
+void ecc_rshift(uint32_t* A);
+int ecc_isGreater(const uint32_t *A, const uint32_t *B, uint8_t length);
+
+#endif /* TEST_INCLUDE */
diff --git a/ecc/test_helper.c b/ecc/test_helper.c
new file mode 100644
index 0000000..bda44ba
--- /dev/null
+++ b/ecc/test_helper.c
@@ -0,0 +1,79 @@
+/*
+ * 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.
+ */
+#include "test_helper.h"
+#include "ecc.h"
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+void ecc_printNumber(const uint32_t *x, int numberLength){ //here the values are turned to MSB!
+ int n;
+
+ for(n = numberLength - 1; n >= 0; n--){
+ printf("%08x", x[n]);
+ }
+ printf("\n");
+}
+
+void ecc_setRandom(uint32_t *secret){
+ int i;
+
+ for (i = 0; i < arrayLength; ++i)
+ {
+ secret[i] = rand();
+ }
+}
+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*/
+const uint32_t ecc_prime_r[8] = {0x00000001, 0x00000000, 0x00000000, 0xffffffff,
+ 0xffffffff, 0xffffffff, 0xfffffffe, 0x00000000};
+
+#ifdef CONTIKI
+void
+test_assert(const char *file, int lineno)
+{
+ printf("Assertion failed: file %s, line %d.\n", file, lineno);
+ /*
+ * loop for a while;
+ * call _reset_vector__();
+ */
+}
+#endif
diff --git a/ecc/test_helper.h b/ecc/test_helper.h
new file mode 100644
index 0000000..38a194e
--- /dev/null
+++ b/ecc/test_helper.h
@@ -0,0 +1,51 @@
+/*
+ * 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.
+ */
+#include <inttypes.h>
+
+extern const uint32_t ecc_prime_m[8];
+extern const uint32_t ecc_prime_r[8];
+
+//debug function to print long numbers
+void ecc_printNumber(const uint32_t *x, int numberLength);
+void ecc_setRandom(uint32_t *secret);
+
+#ifdef CONTIKI
+#undef assert
+#define assert(e) ((e) ? (void)0 : test_assert(__FILE__, __LINE__))
+void test_assert(const char *, int);
+#endif
diff --git a/ecc/testecc.c b/ecc/testecc.c
new file mode 100644
index 0000000..b36d46b
--- /dev/null
+++ b/ecc/testecc.c
@@ -0,0 +1,226 @@
+/*
+ * 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.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+#include "ecc.h"
+#include "test_helper.h"
+
+#ifdef CONTIKI
+#include "contiki.h"
+#else
+#include <time.h>
+#endif /* CONTIKI */
+
+//These are testvalues taken from the NIST P-256 definition
+//6b17d1f2 e12c4247 f8bce6e5 63a440f2 77037d81 2deb33a0 f4a13945 d898c296
+uint32_t BasePointx[8] = { 0xd898c296, 0xf4a13945, 0x2deb33a0, 0x77037d81,
+ 0x63a440f2, 0xf8bce6e5, 0xe12c4247, 0x6b17d1f2};
+
+//4fe342e2 fe1a7f9b 8ee7eb4a 7c0f9e16 2bce3357 6b315ece cbb64068 37bf51f5
+uint32_t BasePointy[8] = { 0x37bf51f5, 0xcbb64068, 0x6b315ece, 0x2bce3357,
+ 0x7c0f9e16, 0x8ee7eb4a, 0xfe1a7f9b, 0x4fe342e2};
+
+//de2444be bc8d36e6 82edd27e 0f271508 617519b3 221a8fa0 b77cab39 89da97c9
+uint32_t Sx[8] = { 0x89da97c9, 0xb77cab39, 0x221a8fa0, 0x617519b3,
+ 0x0f271508, 0x82edd27e, 0xbc8d36e6, 0xde2444be};
+
+//c093ae7f f36e5380 fc01a5aa d1e66659 702de80f 53cec576 b6350b24 3042a256
+uint32_t Sy[8] = { 0x3042a256, 0xb6350b24, 0x53cec576, 0x702de80f,
+ 0xd1e66659, 0xfc01a5aa, 0xf36e5380, 0xc093ae7f};
+
+//55a8b00f 8da1d44e 62f6b3b2 5316212e 39540dc8 61c89575 bb8cf92e 35e0986b
+uint32_t Tx[8] = { 0x35e0986b, 0xbb8cf92e, 0x61c89575, 0x39540dc8,
+ 0x5316212e, 0x62f6b3b2, 0x8da1d44e, 0x55a8b00f};
+
+//5421c320 9c2d6c70 4835d82a c4c3dd90 f61a8a52 598b9e7a b656e9d8 c8b24316
+uint32_t Ty[8] = { 0xc8b24316, 0xb656e9d8, 0x598b9e7a, 0xf61a8a52,
+ 0xc4c3dd90, 0x4835d82a, 0x9c2d6c70, 0x5421c320};
+
+//c51e4753 afdec1e6 b6c6a5b9 92f43f8d d0c7a893 3072708b 6522468b 2ffb06fd
+uint32_t secret[8] = { 0x2ffb06fd, 0x6522468b, 0x3072708b, 0xd0c7a893,
+ 0x92f43f8d, 0xb6c6a5b9, 0xafdec1e6, 0xc51e4753};
+
+//72b13dd4 354b6b81 745195e9 8cc5ba69 70349191 ac476bd4 553cf35a 545a067e
+uint32_t resultAddx[8] = { 0x545a067e, 0x553cf35a, 0xac476bd4, 0x70349191,
+ 0x8cc5ba69, 0x745195e9, 0x354b6b81, 0x72b13dd4};
+
+//8d585cbb 2e1327d7 5241a8a1 22d7620d c33b1331 5aa5c9d4 6d013011 744ac264
+uint32_t resultAddy[8] = { 0x744ac264, 0x6d013011, 0x5aa5c9d4, 0xc33b1331,
+ 0x22d7620d, 0x5241a8a1, 0x2e1327d7, 0x8d585cbb};
+
+//7669e690 1606ee3b a1a8eef1 e0024c33 df6c22f3 b17481b8 2a860ffc db6127b0
+uint32_t resultDoublex[8] = { 0xdb6127b0, 0x2a860ffc, 0xb17481b8, 0xdf6c22f3,
+ 0xe0024c33, 0xa1a8eef1, 0x1606ee3b, 0x7669e690};
+
+//fa878162 187a54f6 c39f6ee0 072f33de 389ef3ee cd03023d e10ca2c1 db61d0c7
+uint32_t resultDoubley[8] = { 0xdb61d0c7, 0xe10ca2c1, 0xcd03023d, 0x389ef3ee,
+ 0x072f33de, 0xc39f6ee0, 0x187a54f6, 0xfa878162};
+
+//51d08d5f 2d427888 2946d88d 83c97d11 e62becc3 cfc18bed acc89ba3 4eeca03f
+uint32_t resultMultx[8] = { 0x4eeca03f, 0xacc89ba3, 0xcfc18bed, 0xe62becc3,
+ 0x83c97d11, 0x2946d88d, 0x2d427888, 0x51d08d5f};
+
+//75ee68eb 8bf626aa 5b673ab5 1f6e744e 06f8fcf8 a6c0cf30 35beca95 6a7b41d5
+uint32_t resultMulty[8] = { 0x6a7b41d5, 0x35beca95, 0xa6c0cf30, 0x06f8fcf8,
+ 0x1f6e744e, 0x5b673ab5, 0x8bf626aa, 0x75ee68eb};
+
+static const uint32_t ecdsaTestMessage[] = { 0x65637572, 0x20612073, 0x68206F66, 0x20686173, 0x69732061, 0x68697320, 0x6F2C2054, 0x48616C6C};
+
+static const uint32_t ecdsaTestSecret[] = {0x94A949FA, 0x401455A1, 0xAD7294CA, 0x896A33BB, 0x7A80E714, 0x4321435B, 0x51247A14, 0x41C1CB6B};
+
+static const uint32_t ecdsaTestRand1[] = { 0x1D1E1F20, 0x191A1B1C, 0x15161718, 0x11121314, 0x0D0E0F10, 0x090A0B0C, 0x05060708, 0x01020304};
+static const uint32_t ecdsaTestresultR1[] = { 0xC3B4035F, 0x515AD0A6, 0xBF375DCA, 0x0CC1E997, 0x7F54FDCD, 0x04D3FECA, 0xB9E396B9, 0x515C3D6E};
+static const uint32_t ecdsaTestresultS1[] = { 0x5366B1AB, 0x0F1DBF46, 0xB0C8D3C4, 0xDB755B6F, 0xB9BF9243, 0xE644A8BE, 0x55159A59, 0x6F9E52A6};
+
+static const uint32_t ecdsaTestRand2[] = { 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x01FFFFFF};
+static const uint32_t ecdsaTestresultR2[] = { 0x14146C91, 0xE878724D, 0xCD4FF928, 0xCC24BC04, 0xAC403390, 0x650C0060, 0x4A30B3F1, 0x9C69B726};
+static const uint32_t ecdsaTestresultS2[] = { 0x433AAB6F, 0x808250B1, 0xE46F90F4, 0xB342E972, 0x18B2F7E4, 0x2DB981A2, 0x6A288FA4, 0x41CF59DB};
+
+void addTest(){
+ uint32_t tempx[8];
+ uint32_t tempy[8];
+
+ ecc_ec_add(Tx, Ty, Sx, Sy, tempx, tempy);
+ assert(ecc_isSame(tempx, resultAddx, arrayLength));
+ assert(ecc_isSame(tempy, resultAddy, arrayLength));
+}
+
+void doubleTest(){
+ uint32_t tempx[8];
+ uint32_t tempy[8];
+
+ ecc_ec_double(Sx, Sy, tempx, tempy);
+ assert(ecc_isSame(tempx, resultDoublex, arrayLength));
+ assert(ecc_isSame(tempy, resultDoubley, arrayLength));
+}
+
+void multTest(){
+ uint32_t tempx[8];
+ uint32_t tempy[8];
+
+ ecc_ec_mult(Sx, Sy, secret, tempx, tempy);
+ assert(ecc_isSame(tempx, resultMultx, arrayLength));
+ assert(ecc_isSame(tempy, resultMulty, arrayLength));
+}
+
+void eccdhTest(){
+ uint32_t tempx[8];
+ uint32_t tempy[8];
+ uint32_t tempAx2[8];
+ uint32_t tempAy2[8];
+ uint32_t tempBx1[8];
+ uint32_t tempBy1[8];
+ uint32_t tempBx2[8];
+ uint32_t tempBy2[8];
+ uint32_t secretA[8];
+ uint32_t secretB[8];
+ ecc_setRandom(secretA);
+ ecc_printNumber(secretA, 8);
+ ecc_setRandom(secretB);
+ ecc_printNumber(secretB, 8);
+ ecc_ec_mult(BasePointx, BasePointy, secretA, tempx, tempy);
+ ecc_ec_mult(BasePointx, BasePointy, secretB, tempBx1, tempBy1);
+ //public key exchange
+ ecc_ec_mult(tempBx1, tempBy1, secretA, tempAx2, tempAy2);
+ ecc_ec_mult(tempx, tempy, secretB, tempBx2, tempBy2);
+ assert(ecc_isSame(tempAx2, tempBx2, arrayLength));
+ assert(ecc_isSame(tempAy2, tempBy2, arrayLength));
+
+}
+
+void ecdsaTest() {
+ int ret __attribute__((unused));
+ uint32_t tempx[9];
+ uint32_t tempy[9];
+ uint32_t pub_x[8];
+ uint32_t pub_y[8];
+
+ ecc_ec_mult(BasePointx, BasePointy, ecdsaTestSecret, pub_x, pub_y);
+
+ ret = ecc_ecdsa_sign(ecdsaTestSecret, ecdsaTestMessage, ecdsaTestRand1, tempx, tempy);
+ assert(ecc_isSame(tempx, ecdsaTestresultR1, arrayLength));
+ assert(ecc_isSame(tempy, ecdsaTestresultS1, arrayLength));
+ assert(ret == 0);
+
+ ret = ecc_ecdsa_validate(pub_x, pub_y, ecdsaTestMessage, tempx, tempy);
+ assert(!ret);
+
+
+ ret = ecc_ecdsa_sign(ecdsaTestSecret, ecdsaTestMessage, ecdsaTestRand2, tempx, tempy);
+ assert(ecc_isSame(tempx, ecdsaTestresultR2, arrayLength));
+ assert(ecc_isSame(tempy, ecdsaTestresultS2, arrayLength));
+ assert(ret == 0);
+
+ ret = ecc_ecdsa_validate(pub_x, pub_y, ecdsaTestMessage, tempx, tempy);
+ assert(!ret);
+}
+
+#ifdef CONTIKI
+PROCESS(ecc_filed_test, "ECC test");
+AUTOSTART_PROCESSES(&ecc_filed_test);
+PROCESS_THREAD(ecc_filed_test, ev, d)
+{
+ PROCESS_BEGIN();
+
+ srand(1234);
+ addTest();
+ doubleTest();
+ multTest();
+ eccdhTest();
+ ecdsaTest();
+ printf("%s\n", "All Tests successful.");
+
+ PROCESS_END();
+}
+#else /* CONTIKI */
+int main(int argc, char const *argv[])
+{
+ srand(time(NULL));
+ addTest();
+ doubleTest();
+ multTest();
+ eccdhTest();
+ ecdsaTest();
+ printf("%s\n", "All Tests successful.");
+ return 0;
+}
+#endif /* CONTIKI */
diff --git a/ecc/testfield.c b/ecc/testfield.c
new file mode 100644
index 0000000..30a690e
--- /dev/null
+++ b/ecc/testfield.c
@@ -0,0 +1,290 @@
+/*
+ * 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.
+ */
+#include <assert.h>
+#include <string.h>
+#include <stdio.h>
+#include "ecc.h"
+#include "test_helper.h"
+
+#ifdef CONTIKI
+#include "contiki.h"
+#endif /* CONTIKI */
+
+//arbitrary test values and results
+uint32_t null[8] = { 0x00000000,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000};
+uint32_t null64[16] = { 0x00000000,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000};
+uint32_t one[8] = { 0x00000001,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000};
+uint32_t one64[16] = { 0x00000001,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000};
+uint32_t two[8] = { 0x00000002,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000};
+uint32_t two64[16] = { 0x00000002,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000};
+uint32_t three[8] = { 0x00000003,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000};
+uint32_t four[8] = {0x00000004,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000};
+uint32_t four64[16] = { 0x00000004,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000};
+uint32_t six[8] = { 0x00000006,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000};
+uint32_t eight[8] = { 0x00000008,0x00000000,0x00000000,0x00000000,
+ 0x00000000,0x00000000,0x00000000,0x00000000};
+uint32_t full[8] = { 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,
+ 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF};
+//00000000fffffffeffffffffffffffffffffffff000000000000000000000001_16
+uint32_t resultFullAdd[8] = { 0x00000001,0x00000000,0x00000000,0xFFFFFFFF,
+ 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFE,0x00000000};
+uint32_t primeMinusOne[8]= { 0xfffffffe,0xffffffff,0xffffffff,0x00000000,
+ 0x00000000,0x00000000,0x00000001,0xffffffff};
+uint32_t resultDoubleMod[8] = { 0xfffffffd,0xffffffff,0xffffffff,0x00000000,
+ 0x00000000,0x00000000,0x00000001,0xffffffff};
+//fffffffe00000002fffffffe0000000100000001fffffffe00000001fffffffc00000003fffffffcfffffffffffffffffffffffc000000000000000000000004_16
+uint32_t resultQuadMod[16] = { 0x00000004,0x00000000,0x00000000,0xFFFFFFFC,
+ 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFC,0x00000003,
+ 0xFFFFFFFC,0x00000001,0xFFFFFFFE,0x00000001,
+ 0x00000001,0xFFFFFFFE,0x00000002,0xFFFFFFFE};
+//00000002fffffffffffffffffffffffefffffffdffffffff0000000000000002_16
+uint32_t resultFullMod[8] = { 0x00000002,0x00000000,0xFFFFFFFF,0xFFFFFFFD,
+ 0xFFFFFFFE,0xFFFFFFFF,0xFFFFFFFF,0x00000002};
+
+static const uint32_t orderMinusOne[8] = {0xFC632550, 0xF3B9CAC2, 0xA7179E84, 0xBCE6FAAD,
+ 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0xFFFFFFFF};
+static const uint32_t orderResultDoubleMod[8] = {0xFC63254F, 0xF3B9CAC2, 0xA7179E84, 0xBCE6FAAD, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0xFFFFFFFF};
+
+uint32_t temp[8];
+uint32_t temp2[16];
+
+void nullEverything(){
+ memset(temp, 0, sizeof(temp));
+ memset(temp2, 0, sizeof(temp));
+}
+
+void fieldAddTest(){
+ assert(ecc_isSame(one, one, arrayLength));
+ ecc_fieldAdd(one, null, ecc_prime_r, temp);
+ assert(ecc_isSame(temp, one, arrayLength));
+ nullEverything();
+ ecc_fieldAdd(one, one, ecc_prime_r, temp);
+ assert(ecc_isSame(temp, two, arrayLength));
+ nullEverything();
+ ecc_add(full, one, temp, 32);
+ assert(ecc_isSame(null, temp, arrayLength));
+ nullEverything();
+ ecc_fieldAdd(full, one, ecc_prime_r, temp);
+ assert(ecc_isSame(temp, resultFullAdd, arrayLength));
+}
+
+void fieldSubTest(){
+ assert(ecc_isSame(one, one, arrayLength));
+ ecc_fieldSub(one, null, ecc_prime_m, temp);
+ assert(ecc_isSame(one, temp, arrayLength));
+ nullEverything();
+ ecc_fieldSub(one, one, ecc_prime_m, temp);
+ assert(ecc_isSame(null, temp, arrayLength));
+ nullEverything();
+ ecc_fieldSub(null, one, ecc_prime_m, temp);
+ assert(ecc_isSame(primeMinusOne, temp, arrayLength));
+}
+
+void fieldMultTest(){
+ ecc_fieldMult(one, null, temp2, arrayLength);
+ assert(ecc_isSame(temp2, null64, arrayLength * 2));
+ nullEverything();
+ ecc_fieldMult(one, two, temp2, arrayLength);
+ assert(ecc_isSame(temp2, two64, arrayLength * 2));
+ nullEverything();
+ ecc_fieldMult(two, two, temp2, arrayLength);
+ assert(ecc_isSame(temp2, four64, arrayLength * 2));
+ nullEverything();
+ ecc_fieldMult(primeMinusOne, primeMinusOne, temp2, arrayLength);
+ assert(ecc_isSame(temp2, resultQuadMod, arrayLength * 2));
+ nullEverything();
+ ecc_fieldInv(two, ecc_prime_m, ecc_prime_r, temp);
+ ecc_fieldMult(temp, two, temp2, arrayLength);
+ ecc_fieldModP(temp, temp2);
+ assert(ecc_isSame(temp, one, arrayLength));
+}
+
+void fieldModPTest(){
+ ecc_fieldMult(primeMinusOne, primeMinusOne, temp2, arrayLength);
+ ecc_fieldModP(temp, temp2);
+ assert(ecc_isSame(temp, one, arrayLength));
+ nullEverything();
+ ecc_fieldModP(temp, one64);
+ assert(ecc_isSame(temp, one, arrayLength));
+ nullEverything();
+ ecc_fieldMult(two, primeMinusOne, temp2, arrayLength);
+ ecc_fieldModP(temp, temp2);
+ assert(ecc_isSame(temp, resultDoubleMod, arrayLength));
+ nullEverything();
+ /*fieldMult(full, full, temp2, arrayLength); //not working, maybe because of the number bigger than p^2?
+ fieldModP(temp, temp2);
+ assert(ecc_isSame(temp, resultFullMod, arrayLength));*/
+}
+
+void fieldModOTest(){
+ ecc_fieldMult(orderMinusOne, orderMinusOne, temp2, arrayLength);
+ ecc_fieldModO(temp2, temp, arrayLength * 2);
+ assert(ecc_isSame(temp, one, arrayLength));
+ nullEverything();
+ ecc_fieldModO(one64, temp, arrayLength * 2);
+ assert(ecc_isSame(temp, one, arrayLength));
+ nullEverything();
+ ecc_fieldMult(two, orderMinusOne, temp2, arrayLength);
+ ecc_fieldModO(temp2, temp, arrayLength * 2);
+ assert(ecc_isSame(temp, orderResultDoubleMod, arrayLength));
+ nullEverything();
+}
+
+
+// void rShiftTest(){
+// printNumber(full, 32);
+// rshift(full);
+// printNumber(full, 32);
+// printNumber(two, 32);
+// rshift(two);
+// printNumber(two, 32);
+// printNumber(four, 32);
+// rshift(four);
+// printNumber(four, 32);
+// }
+
+// void isOneTest(){
+// printf("%d\n", isone(one));
+// printf("%d\n", isone(two));
+// printf("%d\n", isone(four));
+// printf("%d\n", isone(full));
+// printf("%d\n", isone(null));
+// }
+
+void fieldInvTest(){
+ nullEverything();
+ ecc_fieldInv(two, ecc_prime_m, ecc_prime_r, temp);
+ ecc_fieldMult(temp, two, temp2, arrayLength);
+ ecc_fieldModP(temp, temp2);
+ assert(ecc_isSame(one, temp, arrayLength));
+ nullEverything();
+ ecc_fieldInv(eight, ecc_prime_m, ecc_prime_r, temp);
+ ecc_fieldMult(temp, eight, temp2, arrayLength);
+ ecc_fieldModP(temp, temp2);
+ assert(ecc_isSame(one, temp, arrayLength));
+ nullEverything();
+ ecc_fieldInv(three, ecc_prime_m, ecc_prime_r, temp);
+ ecc_fieldMult(temp, three, temp2, arrayLength);
+ ecc_fieldModP(temp, temp2);
+ assert(ecc_isSame(one, temp, arrayLength));
+ nullEverything();
+ ecc_fieldInv(six, ecc_prime_m, ecc_prime_r, temp);
+ ecc_fieldMult(temp, six, temp2, arrayLength);
+ ecc_fieldModP(temp, temp2);
+ assert(ecc_isSame(one, temp, arrayLength));
+ nullEverything();
+ ecc_fieldInv(primeMinusOne, ecc_prime_m, ecc_prime_r, temp);
+ ecc_fieldMult(temp, primeMinusOne, temp2, arrayLength);
+ ecc_fieldModP(temp, temp2);
+ assert(ecc_isSame(one, temp, arrayLength));
+}
+
+// void randomStuff(){
+
+// }
+
+#ifdef CONTIKI
+PROCESS(ecc_filed_test, "ECC field test");
+AUTOSTART_PROCESSES(&ecc_filed_test);
+PROCESS_THREAD(ecc_filed_test, ev, d)
+{
+ PROCESS_BEGIN();
+
+ nullEverything();
+ //randomStuff();
+ nullEverything();
+ fieldAddTest();
+ nullEverything();
+ fieldSubTest();
+ nullEverything();
+ fieldMultTest();
+ nullEverything();
+ fieldModPTest();
+ nullEverything();
+ fieldModOTest();
+ nullEverything();
+ fieldInvTest();
+ nullEverything();
+ //rShiftTest();
+ //isOneTest();
+ printf("%s\n", "All Tests succesfull!");
+
+ PROCESS_END();
+}
+#else /* CONTIKI */
+int main(int argc, char const *argv[])
+{
+ nullEverything();
+ //randomStuff();
+ nullEverything();
+ fieldAddTest();
+ nullEverything();
+ fieldSubTest();
+ nullEverything();
+ fieldMultTest();
+ nullEverything();
+ fieldModPTest();
+ nullEverything();
+ fieldModOTest();
+ nullEverything();
+ fieldInvTest();
+ nullEverything();
+ //rShiftTest();
+ //isOneTest();
+ printf("%s\n", "All Tests succesfull!");
+ return 0;
+}
+#endif /* CONTIKI */
