Ashley Mills / tinydtls

Version 0.5.0 of tinydtls

Dependents:   tinydtls_test_cellular tinydtls_test_ethernet tiny-dtls

ecc/ecc.c@0:ff9ebe0cf0e9, 2013-10-18 (annotated)

Committer:
ashleymills
Date:
Fri Oct 18 13:18:30 2013 +0000
Revision:
0:ff9ebe0cf0e9
Upgraded to tinydtls 0.5.0

Who changed what in which revision?

UserRevisionLine numberNew contents of line
ashleymills 0:ff9ebe0cf0e9 1 /*
ashleymills 0:ff9ebe0cf0e9 2 * Copyright (c) 2009 Chris K Cockrum <ckc@cockrum.net>
ashleymills 0:ff9ebe0cf0e9 3 *
ashleymills 0:ff9ebe0cf0e9 4 * Copyright (c) 2013 Jens Trillmann <jtrillma@tzi.de>
ashleymills 0:ff9ebe0cf0e9 5 * Copyright (c) 2013 Marc Müller-Weinhardt <muewei@tzi.de>
ashleymills 0:ff9ebe0cf0e9 6 * Copyright (c) 2013 Lars Schmertmann <lars@tzi.de>
ashleymills 0:ff9ebe0cf0e9 7 * Copyright (c) 2013 Hauke Mehrtens <hauke@hauke-m.de>
ashleymills 0:ff9ebe0cf0e9 8 *
ashleymills 0:ff9ebe0cf0e9 9 * Permission is hereby granted, free of charge, to any person obtaining a copy
ashleymills 0:ff9ebe0cf0e9 10 * of this software and associated documentation files (the "Software"), to deal
ashleymills 0:ff9ebe0cf0e9 11 * in the Software without restriction, including without limitation the rights
ashleymills 0:ff9ebe0cf0e9 12 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
ashleymills 0:ff9ebe0cf0e9 13 * copies of the Software, and to permit persons to whom the Software is
ashleymills 0:ff9ebe0cf0e9 14 * furnished to do so, subject to the following conditions:
ashleymills 0:ff9ebe0cf0e9 15 *
ashleymills 0:ff9ebe0cf0e9 16 * The above copyright notice and this permission notice shall be included in
ashleymills 0:ff9ebe0cf0e9 17 * all copies or substantial portions of the Software.
ashleymills 0:ff9ebe0cf0e9 18 *
ashleymills 0:ff9ebe0cf0e9 19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
ashleymills 0:ff9ebe0cf0e9 20 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
ashleymills 0:ff9ebe0cf0e9 21 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
ashleymills 0:ff9ebe0cf0e9 22 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
ashleymills 0:ff9ebe0cf0e9 23 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
ashleymills 0:ff9ebe0cf0e9 24 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
ashleymills 0:ff9ebe0cf0e9 25 * THE SOFTWARE.
ashleymills 0:ff9ebe0cf0e9 26 *
ashleymills 0:ff9ebe0cf0e9 27 *
ashleymills 0:ff9ebe0cf0e9 28 * This implementation is based in part on the paper Implementation of an
ashleymills 0:ff9ebe0cf0e9 29 * Elliptic Curve Cryptosystem on an 8-bit Microcontroller [0] by
ashleymills 0:ff9ebe0cf0e9 30 * Chris K Cockrum <ckc@cockrum.net>.
ashleymills 0:ff9ebe0cf0e9 31 *
ashleymills 0:ff9ebe0cf0e9 32 * [0]: http://cockrum.net/Implementation_of_ECC_on_an_8-bit_microcontroller.pdf
ashleymills 0:ff9ebe0cf0e9 33 *
ashleymills 0:ff9ebe0cf0e9 34 * This is a efficient ECC implementation on the secp256r1 curve for 32 Bit CPU
ashleymills 0:ff9ebe0cf0e9 35 * architectures. It provides basic operations on the secp256r1 curve and support
ashleymills 0:ff9ebe0cf0e9 36 * for ECDH and ECDSA.
ashleymills 0:ff9ebe0cf0e9 37 */
ashleymills 0:ff9ebe0cf0e9 38
ashleymills 0:ff9ebe0cf0e9 39 //big number functions
ashleymills 0:ff9ebe0cf0e9 40 #include "ecc.h"
ashleymills 0:ff9ebe0cf0e9 41
ashleymills 0:ff9ebe0cf0e9 42 static uint32_t add( const uint32_t *x, const uint32_t *y, uint32_t *result, uint8_t length){
ashleymills 0:ff9ebe0cf0e9 43 uint64_t d = 0; //carry
ashleymills 0:ff9ebe0cf0e9 44 int v = 0;
ashleymills 0:ff9ebe0cf0e9 45 for(v = 0;v<length;v++){
ashleymills 0:ff9ebe0cf0e9 46 //printf("%02x + %02x + %01x = ", x[v], y[v], d);
ashleymills 0:ff9ebe0cf0e9 47 d += (uint64_t) x[v] + (uint64_t) y[v];
ashleymills 0:ff9ebe0cf0e9 48 //printf("%02x\n", d);
ashleymills 0:ff9ebe0cf0e9 49 result[v] = d;
ashleymills 0:ff9ebe0cf0e9 50 d = d>>32; //save carry
ashleymills 0:ff9ebe0cf0e9 51 }
ashleymills 0:ff9ebe0cf0e9 52
ashleymills 0:ff9ebe0cf0e9 53 return (uint32_t)d;
ashleymills 0:ff9ebe0cf0e9 54 }
ashleymills 0:ff9ebe0cf0e9 55
ashleymills 0:ff9ebe0cf0e9 56 static uint32_t sub( const uint32_t *x, const uint32_t *y, uint32_t *result, uint8_t length){
ashleymills 0:ff9ebe0cf0e9 57 uint64_t d = 0;
ashleymills 0:ff9ebe0cf0e9 58 int v;
ashleymills 0:ff9ebe0cf0e9 59 for(v = 0;v < length; v++){
ashleymills 0:ff9ebe0cf0e9 60 d = (uint64_t) x[v] - (uint64_t) y[v] - d;
ashleymills 0:ff9ebe0cf0e9 61 result[v] = d & 0xFFFFFFFF;
ashleymills 0:ff9ebe0cf0e9 62 d = d>>32;
ashleymills 0:ff9ebe0cf0e9 63 d &= 0x1;
ashleymills 0:ff9ebe0cf0e9 64 }
ashleymills 0:ff9ebe0cf0e9 65 return (uint32_t)d;
ashleymills 0:ff9ebe0cf0e9 66 }
ashleymills 0:ff9ebe0cf0e9 67
ashleymills 0:ff9ebe0cf0e9 68 static void rshiftby(const uint32_t *in, uint8_t in_size, uint32_t *out, uint8_t out_size, uint8_t shift) {
ashleymills 0:ff9ebe0cf0e9 69 int i;
ashleymills 0:ff9ebe0cf0e9 70
ashleymills 0:ff9ebe0cf0e9 71 for (i = 0; i < (in_size - shift) && i < out_size; i++)
ashleymills 0:ff9ebe0cf0e9 72 out[i] = in[i + shift];
ashleymills 0:ff9ebe0cf0e9 73 for (/* reuse i */; i < out_size; i++)
ashleymills 0:ff9ebe0cf0e9 74 out[i] = 0;
ashleymills 0:ff9ebe0cf0e9 75 }
ashleymills 0:ff9ebe0cf0e9 76
ashleymills 0:ff9ebe0cf0e9 77 //finite field functions
ashleymills 0:ff9ebe0cf0e9 78 //FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
ashleymills 0:ff9ebe0cf0e9 79 static const uint32_t ecc_prime_m[8] = {0xffffffff, 0xffffffff, 0xffffffff, 0x00000000,
ashleymills 0:ff9ebe0cf0e9 80 0x00000000, 0x00000000, 0x00000001, 0xffffffff};
ashleymills 0:ff9ebe0cf0e9 81
ashleymills 0:ff9ebe0cf0e9 82
ashleymills 0:ff9ebe0cf0e9 83 /* This is added after an static byte addition if the answer has a carry in MSB*/
ashleymills 0:ff9ebe0cf0e9 84 static const uint32_t ecc_prime_r[8] = {0x00000001, 0x00000000, 0x00000000, 0xffffffff,
ashleymills 0:ff9ebe0cf0e9 85 0xffffffff, 0xffffffff, 0xfffffffe, 0x00000000};
ashleymills 0:ff9ebe0cf0e9 86
ashleymills 0:ff9ebe0cf0e9 87 // ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
ashleymills 0:ff9ebe0cf0e9 88 static const uint32_t ecc_order_m[9] = {0xFC632551, 0xF3B9CAC2, 0xA7179E84, 0xBCE6FAAD,
ashleymills 0:ff9ebe0cf0e9 89 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0xFFFFFFFF,
ashleymills 0:ff9ebe0cf0e9 90 0x00000000};
ashleymills 0:ff9ebe0cf0e9 91
ashleymills 0:ff9ebe0cf0e9 92 static const uint32_t ecc_order_r[8] = {0x039CDAAF, 0x0C46353D, 0x58E8617B, 0x43190552,
ashleymills 0:ff9ebe0cf0e9 93 0x00000000, 0x00000000, 0xFFFFFFFF, 0x00000000};
ashleymills 0:ff9ebe0cf0e9 94
ashleymills 0:ff9ebe0cf0e9 95 static const uint32_t ecc_order_mu[9] = {0xEEDF9BFE, 0x012FFD85, 0xDF1A6C21, 0x43190552,
ashleymills 0:ff9ebe0cf0e9 96 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0x00000000,
ashleymills 0:ff9ebe0cf0e9 97 0x00000001};
ashleymills 0:ff9ebe0cf0e9 98
ashleymills 0:ff9ebe0cf0e9 99 static const uint8_t ecc_order_k = 8;
ashleymills 0:ff9ebe0cf0e9 100
ashleymills 0:ff9ebe0cf0e9 101 const uint32_t ecc_g_point_x[8] = { 0xD898C296, 0xF4A13945, 0x2DEB33A0, 0x77037D81,
ashleymills 0:ff9ebe0cf0e9 102 0x63A440F2, 0xF8BCE6E5, 0xE12C4247, 0x6B17D1F2};
ashleymills 0:ff9ebe0cf0e9 103 const uint32_t ecc_g_point_y[8] = { 0x37BF51F5, 0xCBB64068, 0x6B315ECE, 0x2BCE3357,
ashleymills 0:ff9ebe0cf0e9 104 0x7C0F9E16, 0x8EE7EB4A, 0xFE1A7F9B, 0x4FE342E2};
ashleymills 0:ff9ebe0cf0e9 105
ashleymills 0:ff9ebe0cf0e9 106
ashleymills 0:ff9ebe0cf0e9 107 static void setZero(uint32_t *A, const int length){
ashleymills 0:ff9ebe0cf0e9 108 int i;
ashleymills 0:ff9ebe0cf0e9 109
ashleymills 0:ff9ebe0cf0e9 110 for (i = 0; i < length; ++i)
ashleymills 0:ff9ebe0cf0e9 111 {
ashleymills 0:ff9ebe0cf0e9 112 A[i] = 0;
ashleymills 0:ff9ebe0cf0e9 113 }
ashleymills 0:ff9ebe0cf0e9 114 }
ashleymills 0:ff9ebe0cf0e9 115
ashleymills 0:ff9ebe0cf0e9 116 /*
ashleymills 0:ff9ebe0cf0e9 117 * copy one array to another
ashleymills 0:ff9ebe0cf0e9 118 */
ashleymills 0:ff9ebe0cf0e9 119 static void copy(const uint32_t *from, uint32_t *to, uint8_t length){
ashleymills 0:ff9ebe0cf0e9 120 int i;
ashleymills 0:ff9ebe0cf0e9 121 for (i = 0; i < length; ++i)
ashleymills 0:ff9ebe0cf0e9 122 {
ashleymills 0:ff9ebe0cf0e9 123 to[i] = from[i];
ashleymills 0:ff9ebe0cf0e9 124 }
ashleymills 0:ff9ebe0cf0e9 125 }
ashleymills 0:ff9ebe0cf0e9 126
ashleymills 0:ff9ebe0cf0e9 127 static int isSame(const uint32_t *A, const uint32_t *B, uint8_t length){
ashleymills 0:ff9ebe0cf0e9 128 int i;
ashleymills 0:ff9ebe0cf0e9 129
ashleymills 0:ff9ebe0cf0e9 130 for(i = 0; i < length; i++){
ashleymills 0:ff9ebe0cf0e9 131 if (A[i] != B[i])
ashleymills 0:ff9ebe0cf0e9 132 return 0;
ashleymills 0:ff9ebe0cf0e9 133 }
ashleymills 0:ff9ebe0cf0e9 134 return 1;
ashleymills 0:ff9ebe0cf0e9 135 }
ashleymills 0:ff9ebe0cf0e9 136
ashleymills 0:ff9ebe0cf0e9 137 //is A greater than B?
ashleymills 0:ff9ebe0cf0e9 138 static int isGreater(const uint32_t *A, const uint32_t *B, uint8_t length){
ashleymills 0:ff9ebe0cf0e9 139 int i;
ashleymills 0:ff9ebe0cf0e9 140 for (i = length-1; i >= 0; --i)
ashleymills 0:ff9ebe0cf0e9 141 {
ashleymills 0:ff9ebe0cf0e9 142 if(A[i] > B[i])
ashleymills 0:ff9ebe0cf0e9 143 return 1;
ashleymills 0:ff9ebe0cf0e9 144 if(A[i] < B[i])
ashleymills 0:ff9ebe0cf0e9 145 return -1;
ashleymills 0:ff9ebe0cf0e9 146 }
ashleymills 0:ff9ebe0cf0e9 147 return 0;
ashleymills 0:ff9ebe0cf0e9 148 }
ashleymills 0:ff9ebe0cf0e9 149
ashleymills 0:ff9ebe0cf0e9 150
ashleymills 0:ff9ebe0cf0e9 151 static int fieldAdd(const uint32_t *x, const uint32_t *y, const uint32_t *reducer, uint32_t *result){
ashleymills 0:ff9ebe0cf0e9 152 if(add(x, y, result, arrayLength)){ //add prime if carry is still set!
ashleymills 0:ff9ebe0cf0e9 153 uint32_t tempas[8];
ashleymills 0:ff9ebe0cf0e9 154 setZero(tempas, 8);
ashleymills 0:ff9ebe0cf0e9 155 add(result, reducer, tempas, arrayLength);
ashleymills 0:ff9ebe0cf0e9 156 copy(tempas, result, arrayLength);
ashleymills 0:ff9ebe0cf0e9 157 }
ashleymills 0:ff9ebe0cf0e9 158 return 0;
ashleymills 0:ff9ebe0cf0e9 159 }
ashleymills 0:ff9ebe0cf0e9 160
ashleymills 0:ff9ebe0cf0e9 161 static int fieldSub(const uint32_t *x, const uint32_t *y, const uint32_t *modulus, uint32_t *result){
ashleymills 0:ff9ebe0cf0e9 162 if(sub(x, y, result, arrayLength)){ //add modulus if carry is set
ashleymills 0:ff9ebe0cf0e9 163 uint32_t tempas[8];
ashleymills 0:ff9ebe0cf0e9 164 setZero(tempas, 8);
ashleymills 0:ff9ebe0cf0e9 165 add(result, modulus, tempas, arrayLength);
ashleymills 0:ff9ebe0cf0e9 166 copy(tempas, result, arrayLength);
ashleymills 0:ff9ebe0cf0e9 167 }
ashleymills 0:ff9ebe0cf0e9 168 return 0;
ashleymills 0:ff9ebe0cf0e9 169 }
ashleymills 0:ff9ebe0cf0e9 170
ashleymills 0:ff9ebe0cf0e9 171 //finite Field multiplication
ashleymills 0:ff9ebe0cf0e9 172 //32bit * 32bit = 64bit
ashleymills 0:ff9ebe0cf0e9 173 static int fieldMult(const uint32_t *x, const uint32_t *y, uint32_t *result, uint8_t length){
ashleymills 0:ff9ebe0cf0e9 174 uint32_t temp[length * 2];
ashleymills 0:ff9ebe0cf0e9 175 setZero(temp, length * 2);
ashleymills 0:ff9ebe0cf0e9 176 setZero(result, length * 2);
ashleymills 0:ff9ebe0cf0e9 177 uint8_t k, n;
ashleymills 0:ff9ebe0cf0e9 178 uint64_t l;
ashleymills 0:ff9ebe0cf0e9 179 for (k = 0; k < length; k++){
ashleymills 0:ff9ebe0cf0e9 180 for (n = 0; n < length; n++){
ashleymills 0:ff9ebe0cf0e9 181 l = (uint64_t)x[n]*(uint64_t)y[k];
ashleymills 0:ff9ebe0cf0e9 182 temp[n+k] = l&0xFFFFFFFF;
ashleymills 0:ff9ebe0cf0e9 183 temp[n+k+1] = l>>32;
ashleymills 0:ff9ebe0cf0e9 184 add(&temp[n+k], &result[n+k], &result[n+k], (length * 2) - (n + k));
ashleymills 0:ff9ebe0cf0e9 185
ashleymills 0:ff9ebe0cf0e9 186 setZero(temp, length * 2);
ashleymills 0:ff9ebe0cf0e9 187 }
ashleymills 0:ff9ebe0cf0e9 188 }
ashleymills 0:ff9ebe0cf0e9 189 return 0;
ashleymills 0:ff9ebe0cf0e9 190 }
ashleymills 0:ff9ebe0cf0e9 191
ashleymills 0:ff9ebe0cf0e9 192 //TODO: maximum:
ashleymills 0:ff9ebe0cf0e9 193 //fffffffe00000002fffffffe0000000100000001fffffffe00000001fffffffe00000001fffffffefffffffffffffffffffffffe000000000000000000000001_16
ashleymills 0:ff9ebe0cf0e9 194 static void fieldModP(uint32_t *A, const uint32_t *B)
ashleymills 0:ff9ebe0cf0e9 195 {
ashleymills 0:ff9ebe0cf0e9 196 uint32_t tempm[8];
ashleymills 0:ff9ebe0cf0e9 197 uint32_t tempm2[8];
ashleymills 0:ff9ebe0cf0e9 198 uint8_t n;
ashleymills 0:ff9ebe0cf0e9 199 setZero(tempm, 8);
ashleymills 0:ff9ebe0cf0e9 200 setZero(tempm2, 8);
ashleymills 0:ff9ebe0cf0e9 201 /* A = T */
ashleymills 0:ff9ebe0cf0e9 202 copy(B,A,arrayLength);
ashleymills 0:ff9ebe0cf0e9 203
ashleymills 0:ff9ebe0cf0e9 204 /* Form S1 */
ashleymills 0:ff9ebe0cf0e9 205 for(n=0;n<3;n++) tempm[n]=0;
ashleymills 0:ff9ebe0cf0e9 206 for(n=3;n<8;n++) tempm[n]=B[n+8];
ashleymills 0:ff9ebe0cf0e9 207
ashleymills 0:ff9ebe0cf0e9 208 /* tempm2=T+S1 */
ashleymills 0:ff9ebe0cf0e9 209 fieldAdd(A,tempm,ecc_prime_r,tempm2);
ashleymills 0:ff9ebe0cf0e9 210 /* A=T+S1+S1 */
ashleymills 0:ff9ebe0cf0e9 211 fieldAdd(tempm2,tempm,ecc_prime_r,A);
ashleymills 0:ff9ebe0cf0e9 212 /* Form S2 */
ashleymills 0:ff9ebe0cf0e9 213 for(n=0;n<3;n++) tempm[n]=0;
ashleymills 0:ff9ebe0cf0e9 214 for(n=3;n<7;n++) tempm[n]=B[n+9];
ashleymills 0:ff9ebe0cf0e9 215 for(n=7;n<8;n++) tempm[n]=0;
ashleymills 0:ff9ebe0cf0e9 216 /* tempm2=T+S1+S1+S2 */
ashleymills 0:ff9ebe0cf0e9 217 fieldAdd(A,tempm,ecc_prime_r,tempm2);
ashleymills 0:ff9ebe0cf0e9 218 /* A=T+S1+S1+S2+S2 */
ashleymills 0:ff9ebe0cf0e9 219 fieldAdd(tempm2,tempm,ecc_prime_r,A);
ashleymills 0:ff9ebe0cf0e9 220 /* Form S3 */
ashleymills 0:ff9ebe0cf0e9 221 for(n=0;n<3;n++) tempm[n]=B[n+8];
ashleymills 0:ff9ebe0cf0e9 222 for(n=3;n<6;n++) tempm[n]=0;
ashleymills 0:ff9ebe0cf0e9 223 for(n=6;n<8;n++) tempm[n]=B[n+8];
ashleymills 0:ff9ebe0cf0e9 224 /* tempm2=T+S1+S1+S2+S2+S3 */
ashleymills 0:ff9ebe0cf0e9 225 fieldAdd(A,tempm,ecc_prime_r,tempm2);
ashleymills 0:ff9ebe0cf0e9 226 /* Form S4 */
ashleymills 0:ff9ebe0cf0e9 227 for(n=0;n<3;n++) tempm[n]=B[n+9];
ashleymills 0:ff9ebe0cf0e9 228 for(n=3;n<6;n++) tempm[n]=B[n+10];
ashleymills 0:ff9ebe0cf0e9 229 for(n=6;n<7;n++) tempm[n]=B[n+7];
ashleymills 0:ff9ebe0cf0e9 230 for(n=7;n<8;n++) tempm[n]=B[n+1];
ashleymills 0:ff9ebe0cf0e9 231 /* A=T+S1+S1+S2+S2+S3+S4 */
ashleymills 0:ff9ebe0cf0e9 232 fieldAdd(tempm2,tempm,ecc_prime_r,A);
ashleymills 0:ff9ebe0cf0e9 233 /* Form D1 */
ashleymills 0:ff9ebe0cf0e9 234 for(n=0;n<3;n++) tempm[n]=B[n+11];
ashleymills 0:ff9ebe0cf0e9 235 for(n=3;n<6;n++) tempm[n]=0;
ashleymills 0:ff9ebe0cf0e9 236 for(n=6;n<7;n++) tempm[n]=B[n+2];
ashleymills 0:ff9ebe0cf0e9 237 for(n=7;n<8;n++) tempm[n]=B[n+3];
ashleymills 0:ff9ebe0cf0e9 238 /* tempm2=T+S1+S1+S2+S2+S3+S4-D1 */
ashleymills 0:ff9ebe0cf0e9 239 fieldSub(A,tempm,ecc_prime_m,tempm2);
ashleymills 0:ff9ebe0cf0e9 240 /* Form D2 */
ashleymills 0:ff9ebe0cf0e9 241 for(n=0;n<4;n++) tempm[n]=B[n+12];
ashleymills 0:ff9ebe0cf0e9 242 for(n=4;n<6;n++) tempm[n]=0;
ashleymills 0:ff9ebe0cf0e9 243 for(n=6;n<7;n++) tempm[n]=B[n+3];
ashleymills 0:ff9ebe0cf0e9 244 for(n=7;n<8;n++) tempm[n]=B[n+4];
ashleymills 0:ff9ebe0cf0e9 245 /* A=T+S1+S1+S2+S2+S3+S4-D1-D2 */
ashleymills 0:ff9ebe0cf0e9 246 fieldSub(tempm2,tempm,ecc_prime_m,A);
ashleymills 0:ff9ebe0cf0e9 247 /* Form D3 */
ashleymills 0:ff9ebe0cf0e9 248 for(n=0;n<3;n++) tempm[n]=B[n+13];
ashleymills 0:ff9ebe0cf0e9 249 for(n=3;n<6;n++) tempm[n]=B[n+5];
ashleymills 0:ff9ebe0cf0e9 250 for(n=6;n<7;n++) tempm[n]=0;
ashleymills 0:ff9ebe0cf0e9 251 for(n=7;n<8;n++) tempm[n]=B[n+5];
ashleymills 0:ff9ebe0cf0e9 252 /* tempm2=T+S1+S1+S2+S2+S3+S4-D1-D2-D3 */
ashleymills 0:ff9ebe0cf0e9 253 fieldSub(A,tempm,ecc_prime_m,tempm2);
ashleymills 0:ff9ebe0cf0e9 254 /* Form D4 */
ashleymills 0:ff9ebe0cf0e9 255 for(n=0;n<2;n++) tempm[n]=B[n+14];
ashleymills 0:ff9ebe0cf0e9 256 for(n=2;n<3;n++) tempm[n]=0;
ashleymills 0:ff9ebe0cf0e9 257 for(n=3;n<6;n++) tempm[n]=B[n+6];
ashleymills 0:ff9ebe0cf0e9 258 for(n=6;n<7;n++) tempm[n]=0;
ashleymills 0:ff9ebe0cf0e9 259 for(n=7;n<8;n++) tempm[n]=B[n+6];
ashleymills 0:ff9ebe0cf0e9 260 /* A=T+S1+S1+S2+S2+S3+S4-D1-D2-D3-D4 */
ashleymills 0:ff9ebe0cf0e9 261 fieldSub(tempm2,tempm,ecc_prime_m,A);
ashleymills 0:ff9ebe0cf0e9 262 if(isGreater(A, ecc_prime_m, arrayLength) >= 0){
ashleymills 0:ff9ebe0cf0e9 263 fieldSub(A, ecc_prime_m, ecc_prime_m, tempm);
ashleymills 0:ff9ebe0cf0e9 264 copy(tempm, A, arrayLength);
ashleymills 0:ff9ebe0cf0e9 265 }
ashleymills 0:ff9ebe0cf0e9 266 }
ashleymills 0:ff9ebe0cf0e9 267
ashleymills 0:ff9ebe0cf0e9 268 /**
ashleymills 0:ff9ebe0cf0e9 269 * calculate the result = A mod n.
ashleymills 0:ff9ebe0cf0e9 270 * n is the order of the eliptic curve.
ashleymills 0:ff9ebe0cf0e9 271 * A and result could point to the same value
ashleymills 0:ff9ebe0cf0e9 272 *
ashleymills 0:ff9ebe0cf0e9 273 * A: input value (max size * 4 bytes)
ashleymills 0:ff9ebe0cf0e9 274 * result: result of modulo calculation (max 36 bytes)
ashleymills 0:ff9ebe0cf0e9 275 * size: size of A
ashleymills 0:ff9ebe0cf0e9 276 *
ashleymills 0:ff9ebe0cf0e9 277 * This uses the Barrett modular reduction as described in the Handbook
ashleymills 0:ff9ebe0cf0e9 278 * of Applied Cryptography 14.42 Algorithm Barrett modular reduction,
ashleymills 0:ff9ebe0cf0e9 279 * see http://cacr.uwaterloo.ca/hac/about/chap14.pdf and
ashleymills 0:ff9ebe0cf0e9 280 * http://everything2.com/title/Barrett+Reduction
ashleymills 0:ff9ebe0cf0e9 281 *
ashleymills 0:ff9ebe0cf0e9 282 * b = 32 (bite size of the processor architecture)
ashleymills 0:ff9ebe0cf0e9 283 * mu (ecc_order_mu) was precomputed in a java program
ashleymills 0:ff9ebe0cf0e9 284 */
ashleymills 0:ff9ebe0cf0e9 285 static void fieldModO(const uint32_t *A, uint32_t *result, uint8_t length) {
ashleymills 0:ff9ebe0cf0e9 286 // This is used for value q1 and q3
ashleymills 0:ff9ebe0cf0e9 287 uint32_t q1_q3[9];
ashleymills 0:ff9ebe0cf0e9 288 // This is used for q2 and a temp var
ashleymills 0:ff9ebe0cf0e9 289 uint32_t q2_tmp[18];
ashleymills 0:ff9ebe0cf0e9 290
ashleymills 0:ff9ebe0cf0e9 291 // return if the given value is smaller than the modulus
ashleymills 0:ff9ebe0cf0e9 292 if (length == arrayLength && isGreater(A, ecc_order_m, arrayLength) <= 0) {
ashleymills 0:ff9ebe0cf0e9 293 if (A != result)
ashleymills 0:ff9ebe0cf0e9 294 copy(A, result, length);
ashleymills 0:ff9ebe0cf0e9 295 return;
ashleymills 0:ff9ebe0cf0e9 296 }
ashleymills 0:ff9ebe0cf0e9 297
ashleymills 0:ff9ebe0cf0e9 298 rshiftby(A, length, q1_q3, 9, ecc_order_k - 1);
ashleymills 0:ff9ebe0cf0e9 299
ashleymills 0:ff9ebe0cf0e9 300 fieldMult(ecc_order_mu, q1_q3, q2_tmp, 9);
ashleymills 0:ff9ebe0cf0e9 301
ashleymills 0:ff9ebe0cf0e9 302 rshiftby(q2_tmp, 18, q1_q3, 8, ecc_order_k + 1);
ashleymills 0:ff9ebe0cf0e9 303
ashleymills 0:ff9ebe0cf0e9 304 // r1 = first 9 blocks of A
ashleymills 0:ff9ebe0cf0e9 305
ashleymills 0:ff9ebe0cf0e9 306 fieldMult(q1_q3, ecc_order_m, q2_tmp, 8);
ashleymills 0:ff9ebe0cf0e9 307
ashleymills 0:ff9ebe0cf0e9 308 // r2 = first 9 blocks of q2_tmp
ashleymills 0:ff9ebe0cf0e9 309
ashleymills 0:ff9ebe0cf0e9 310 sub(A, q2_tmp, result, 9);
ashleymills 0:ff9ebe0cf0e9 311
ashleymills 0:ff9ebe0cf0e9 312 while (isGreater(result, ecc_order_m, 9) >= 0)
ashleymills 0:ff9ebe0cf0e9 313 sub(result, ecc_order_m, result, 9);
ashleymills 0:ff9ebe0cf0e9 314 }
ashleymills 0:ff9ebe0cf0e9 315
ashleymills 0:ff9ebe0cf0e9 316 static int isOne(const uint32_t* A){
ashleymills 0:ff9ebe0cf0e9 317 uint8_t n;
ashleymills 0:ff9ebe0cf0e9 318 for(n=1;n<8;n++)
ashleymills 0:ff9ebe0cf0e9 319 if (A[n]!=0)
ashleymills 0:ff9ebe0cf0e9 320 break;
ashleymills 0:ff9ebe0cf0e9 321
ashleymills 0:ff9ebe0cf0e9 322 if ((n==8)&&(A[0]==1))
ashleymills 0:ff9ebe0cf0e9 323 return 1;
ashleymills 0:ff9ebe0cf0e9 324 else
ashleymills 0:ff9ebe0cf0e9 325 return 0;
ashleymills 0:ff9ebe0cf0e9 326 }
ashleymills 0:ff9ebe0cf0e9 327
ashleymills 0:ff9ebe0cf0e9 328 static int isZero(const uint32_t* A){
ashleymills 0:ff9ebe0cf0e9 329 uint8_t n, r=0;
ashleymills 0:ff9ebe0cf0e9 330 for(n=0;n<8;n++){
ashleymills 0:ff9ebe0cf0e9 331 if (A[n] == 0) r++;
ashleymills 0:ff9ebe0cf0e9 332 }
ashleymills 0:ff9ebe0cf0e9 333 return r==8;
ashleymills 0:ff9ebe0cf0e9 334 }
ashleymills 0:ff9ebe0cf0e9 335
ashleymills 0:ff9ebe0cf0e9 336 static void rshift(uint32_t* A){
ashleymills 0:ff9ebe0cf0e9 337 int n, i, nOld=0;
ashleymills 0:ff9ebe0cf0e9 338 for (i = 8; i--;)
ashleymills 0:ff9ebe0cf0e9 339 {
ashleymills 0:ff9ebe0cf0e9 340 n = A[i]&0x1;
ashleymills 0:ff9ebe0cf0e9 341 A[i] = A[i]>>1 | nOld<<31;
ashleymills 0:ff9ebe0cf0e9 342 nOld = n;
ashleymills 0:ff9ebe0cf0e9 343 }
ashleymills 0:ff9ebe0cf0e9 344 }
ashleymills 0:ff9ebe0cf0e9 345
ashleymills 0:ff9ebe0cf0e9 346 static int fieldAddAndDivide(const uint32_t *x, const uint32_t *modulus, const uint32_t *reducer, uint32_t* result){
ashleymills 0:ff9ebe0cf0e9 347 uint32_t n = add(x, modulus, result, arrayLength);
ashleymills 0:ff9ebe0cf0e9 348 rshift(result);
ashleymills 0:ff9ebe0cf0e9 349 if(n){ //add prime if carry is still set!
ashleymills 0:ff9ebe0cf0e9 350 result[7] |= 0x80000000;//add the carry
ashleymills 0:ff9ebe0cf0e9 351 if (isGreater(result, modulus, arrayLength) == 1)
ashleymills 0:ff9ebe0cf0e9 352 {
ashleymills 0:ff9ebe0cf0e9 353 uint32_t tempas[8];
ashleymills 0:ff9ebe0cf0e9 354 setZero(tempas, 8);
ashleymills 0:ff9ebe0cf0e9 355 add(result, reducer, tempas, 8);
ashleymills 0:ff9ebe0cf0e9 356 copy(tempas, result, arrayLength);
ashleymills 0:ff9ebe0cf0e9 357 }
ashleymills 0:ff9ebe0cf0e9 358
ashleymills 0:ff9ebe0cf0e9 359 }
ashleymills 0:ff9ebe0cf0e9 360 return 0;
ashleymills 0:ff9ebe0cf0e9 361 }
ashleymills 0:ff9ebe0cf0e9 362
ashleymills 0:ff9ebe0cf0e9 363 /*
ashleymills 0:ff9ebe0cf0e9 364 * Inverse A and output to B
ashleymills 0:ff9ebe0cf0e9 365 */
ashleymills 0:ff9ebe0cf0e9 366 static void fieldInv(const uint32_t *A, const uint32_t *modulus, const uint32_t *reducer, uint32_t *B){
ashleymills 0:ff9ebe0cf0e9 367 uint32_t u[8],v[8],x1[8],x2[8];
ashleymills 0:ff9ebe0cf0e9 368 uint32_t tempm[8];
ashleymills 0:ff9ebe0cf0e9 369 uint32_t tempm2[8];
ashleymills 0:ff9ebe0cf0e9 370 setZero(tempm, 8);
ashleymills 0:ff9ebe0cf0e9 371 setZero(tempm2, 8);
ashleymills 0:ff9ebe0cf0e9 372 setZero(u, 8);
ashleymills 0:ff9ebe0cf0e9 373 setZero(v, 8);
ashleymills 0:ff9ebe0cf0e9 374
ashleymills 0:ff9ebe0cf0e9 375 uint8_t t;
ashleymills 0:ff9ebe0cf0e9 376 copy(A,u,arrayLength);
ashleymills 0:ff9ebe0cf0e9 377 copy(modulus,v,arrayLength);
ashleymills 0:ff9ebe0cf0e9 378 setZero(x1, 8);
ashleymills 0:ff9ebe0cf0e9 379 setZero(x2, 8);
ashleymills 0:ff9ebe0cf0e9 380 x1[0]=1;
ashleymills 0:ff9ebe0cf0e9 381 /* While u !=1 and v !=1 */
ashleymills 0:ff9ebe0cf0e9 382 while ((isOne(u) || isOne(v))==0) {
ashleymills 0:ff9ebe0cf0e9 383 while(!(u[0]&1)) { /* While u is even */
ashleymills 0:ff9ebe0cf0e9 384 rshift(u); /* divide by 2 */
ashleymills 0:ff9ebe0cf0e9 385 if (!(x1[0]&1)) /*ifx1iseven*/
ashleymills 0:ff9ebe0cf0e9 386 rshift(x1); /* Divide by 2 */
ashleymills 0:ff9ebe0cf0e9 387 else {
ashleymills 0:ff9ebe0cf0e9 388 fieldAddAndDivide(x1,modulus,reducer,tempm); /* tempm=x1+p */
ashleymills 0:ff9ebe0cf0e9 389 copy(tempm,x1,arrayLength); /* x1=tempm */
ashleymills 0:ff9ebe0cf0e9 390 //rshift(x1); /* Divide by 2 */
ashleymills 0:ff9ebe0cf0e9 391 }
ashleymills 0:ff9ebe0cf0e9 392 }
ashleymills 0:ff9ebe0cf0e9 393 while(!(v[0]&1)) { /* While v is even */
ashleymills 0:ff9ebe0cf0e9 394 rshift(v); /* divide by 2 */
ashleymills 0:ff9ebe0cf0e9 395 if (!(x2[0]&1)) /*ifx1iseven*/
ashleymills 0:ff9ebe0cf0e9 396 rshift(x2); /* Divide by 2 */
ashleymills 0:ff9ebe0cf0e9 397 else
ashleymills 0:ff9ebe0cf0e9 398 {
ashleymills 0:ff9ebe0cf0e9 399 fieldAddAndDivide(x2,modulus,reducer,tempm); /* tempm=x1+p */
ashleymills 0:ff9ebe0cf0e9 400 copy(tempm,x2,arrayLength); /* x1=tempm */
ashleymills 0:ff9ebe0cf0e9 401 //rshift(x2); /* Divide by 2 */
ashleymills 0:ff9ebe0cf0e9 402 }
ashleymills 0:ff9ebe0cf0e9 403
ashleymills 0:ff9ebe0cf0e9 404 }
ashleymills 0:ff9ebe0cf0e9 405 t=sub(u,v,tempm,arrayLength); /* tempm=u-v */
ashleymills 0:ff9ebe0cf0e9 406 if (t==0) { /* If u > 0 */
ashleymills 0:ff9ebe0cf0e9 407 copy(tempm,u,arrayLength); /* u=u-v */
ashleymills 0:ff9ebe0cf0e9 408 fieldSub(x1,x2,modulus,tempm); /* tempm=x1-x2 */
ashleymills 0:ff9ebe0cf0e9 409 copy(tempm,x1,arrayLength); /* x1=x1-x2 */
ashleymills 0:ff9ebe0cf0e9 410 } else {
ashleymills 0:ff9ebe0cf0e9 411 sub(v,u,tempm,arrayLength); /* tempm=v-u */
ashleymills 0:ff9ebe0cf0e9 412 copy(tempm,v,arrayLength); /* v=v-u */
ashleymills 0:ff9ebe0cf0e9 413 fieldSub(x2,x1,modulus,tempm); /* tempm=x2-x1 */
ashleymills 0:ff9ebe0cf0e9 414 copy(tempm,x2,arrayLength); /* x2=x2-x1 */
ashleymills 0:ff9ebe0cf0e9 415 }
ashleymills 0:ff9ebe0cf0e9 416 }
ashleymills 0:ff9ebe0cf0e9 417 if (isOne(u)) {
ashleymills 0:ff9ebe0cf0e9 418 copy(x1,B,arrayLength);
ashleymills 0:ff9ebe0cf0e9 419 } else {
ashleymills 0:ff9ebe0cf0e9 420 copy(x2,B,arrayLength);
ashleymills 0:ff9ebe0cf0e9 421 }
ashleymills 0:ff9ebe0cf0e9 422 }
ashleymills 0:ff9ebe0cf0e9 423
ashleymills 0:ff9ebe0cf0e9 424 void static ec_double(const uint32_t *px, const uint32_t *py, uint32_t *Dx, uint32_t *Dy){
ashleymills 0:ff9ebe0cf0e9 425 uint32_t tempA[8];
ashleymills 0:ff9ebe0cf0e9 426 uint32_t tempB[8];
ashleymills 0:ff9ebe0cf0e9 427 uint32_t tempC[8];
ashleymills 0:ff9ebe0cf0e9 428 uint32_t tempD[16];
ashleymills 0:ff9ebe0cf0e9 429
ashleymills 0:ff9ebe0cf0e9 430 if(isZero(px) && isZero(py)){
ashleymills 0:ff9ebe0cf0e9 431 copy(px, Dx,arrayLength);
ashleymills 0:ff9ebe0cf0e9 432 copy(py, Dy,arrayLength);
ashleymills 0:ff9ebe0cf0e9 433 return;
ashleymills 0:ff9ebe0cf0e9 434 }
ashleymills 0:ff9ebe0cf0e9 435
ashleymills 0:ff9ebe0cf0e9 436 fieldMult(px, px, tempD, arrayLength);
ashleymills 0:ff9ebe0cf0e9 437 fieldModP(tempA, tempD);
ashleymills 0:ff9ebe0cf0e9 438 setZero(tempB, 8);
ashleymills 0:ff9ebe0cf0e9 439 tempB[0] = 0x00000001;
ashleymills 0:ff9ebe0cf0e9 440 fieldSub(tempA, tempB, ecc_prime_m, tempC); //tempC = (qx^2-1)
ashleymills 0:ff9ebe0cf0e9 441 tempB[0] = 0x00000003;
ashleymills 0:ff9ebe0cf0e9 442 fieldMult(tempC, tempB, tempD, arrayLength);
ashleymills 0:ff9ebe0cf0e9 443 fieldModP(tempA, tempD);//tempA = 3*(qx^2-1)
ashleymills 0:ff9ebe0cf0e9 444 fieldAdd(py, py, ecc_prime_r, tempB); //tempB = 2*qy
ashleymills 0:ff9ebe0cf0e9 445 fieldInv(tempB, ecc_prime_m, ecc_prime_r, tempC); //tempC = 1/(2*qy)
ashleymills 0:ff9ebe0cf0e9 446 fieldMult(tempA, tempC, tempD, arrayLength); //tempB = lambda = (3*(qx^2-1))/(2*qy)
ashleymills 0:ff9ebe0cf0e9 447 fieldModP(tempB, tempD);
ashleymills 0:ff9ebe0cf0e9 448
ashleymills 0:ff9ebe0cf0e9 449 fieldMult(tempB, tempB, tempD, arrayLength); //tempC = lambda^2
ashleymills 0:ff9ebe0cf0e9 450 fieldModP(tempC, tempD);
ashleymills 0:ff9ebe0cf0e9 451 fieldSub(tempC, px, ecc_prime_m, tempA); //lambda^2 - Px
ashleymills 0:ff9ebe0cf0e9 452 fieldSub(tempA, px, ecc_prime_m, Dx); //lambda^2 - Px - Qx
ashleymills 0:ff9ebe0cf0e9 453
ashleymills 0:ff9ebe0cf0e9 454 fieldSub(px, Dx, ecc_prime_m, tempA); //tempA = qx-dx
ashleymills 0:ff9ebe0cf0e9 455 fieldMult(tempB, tempA, tempD, arrayLength); //tempC = lambda * (qx-dx)
ashleymills 0:ff9ebe0cf0e9 456 fieldModP(tempC, tempD);
ashleymills 0:ff9ebe0cf0e9 457 fieldSub(tempC, py, ecc_prime_m, Dy); //Dy = lambda * (qx-dx) - px
ashleymills 0:ff9ebe0cf0e9 458 }
ashleymills 0:ff9ebe0cf0e9 459
ashleymills 0:ff9ebe0cf0e9 460 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){
ashleymills 0:ff9ebe0cf0e9 461 uint32_t tempA[8];
ashleymills 0:ff9ebe0cf0e9 462 uint32_t tempB[8];
ashleymills 0:ff9ebe0cf0e9 463 uint32_t tempC[8];
ashleymills 0:ff9ebe0cf0e9 464 uint32_t tempD[16];
ashleymills 0:ff9ebe0cf0e9 465
ashleymills 0:ff9ebe0cf0e9 466 if(isZero(px) && isZero(py)){
ashleymills 0:ff9ebe0cf0e9 467 copy(qx, Sx,arrayLength);
ashleymills 0:ff9ebe0cf0e9 468 copy(qy, Sy,arrayLength);
ashleymills 0:ff9ebe0cf0e9 469 return;
ashleymills 0:ff9ebe0cf0e9 470 } else if(isZero(qx) && isZero(qy)) {
ashleymills 0:ff9ebe0cf0e9 471 copy(px, Sx,arrayLength);
ashleymills 0:ff9ebe0cf0e9 472 copy(py, Sy,arrayLength);
ashleymills 0:ff9ebe0cf0e9 473 return;
ashleymills 0:ff9ebe0cf0e9 474 }
ashleymills 0:ff9ebe0cf0e9 475
ashleymills 0:ff9ebe0cf0e9 476 if(isSame(px, qx, arrayLength)){
ashleymills 0:ff9ebe0cf0e9 477 if(!isSame(py, qy, arrayLength)){
ashleymills 0:ff9ebe0cf0e9 478 setZero(Sx, 8);
ashleymills 0:ff9ebe0cf0e9 479 setZero(Sy, 8);
ashleymills 0:ff9ebe0cf0e9 480 return;
ashleymills 0:ff9ebe0cf0e9 481 } else {
ashleymills 0:ff9ebe0cf0e9 482 ec_double(px, py, Sx, Sy);
ashleymills 0:ff9ebe0cf0e9 483 return;
ashleymills 0:ff9ebe0cf0e9 484 }
ashleymills 0:ff9ebe0cf0e9 485 }
ashleymills 0:ff9ebe0cf0e9 486
ashleymills 0:ff9ebe0cf0e9 487 fieldSub(py, qy, ecc_prime_m, tempA);
ashleymills 0:ff9ebe0cf0e9 488 fieldSub(px, qx, ecc_prime_m, tempB);
ashleymills 0:ff9ebe0cf0e9 489 fieldInv(tempB, ecc_prime_m, ecc_prime_r, tempB);
ashleymills 0:ff9ebe0cf0e9 490 fieldMult(tempA, tempB, tempD, arrayLength);
ashleymills 0:ff9ebe0cf0e9 491 fieldModP(tempC, tempD); //tempC = lambda
ashleymills 0:ff9ebe0cf0e9 492
ashleymills 0:ff9ebe0cf0e9 493 fieldMult(tempC, tempC, tempD, arrayLength); //tempA = lambda^2
ashleymills 0:ff9ebe0cf0e9 494 fieldModP(tempA, tempD);
ashleymills 0:ff9ebe0cf0e9 495 fieldSub(tempA, px, ecc_prime_m, tempB); //lambda^2 - Px
ashleymills 0:ff9ebe0cf0e9 496 fieldSub(tempB, qx, ecc_prime_m, Sx); //lambda^2 - Px - Qx
ashleymills 0:ff9ebe0cf0e9 497
ashleymills 0:ff9ebe0cf0e9 498 fieldSub(qx, Sx, ecc_prime_m, tempB);
ashleymills 0:ff9ebe0cf0e9 499 fieldMult(tempC, tempB, tempD, arrayLength);
ashleymills 0:ff9ebe0cf0e9 500 fieldModP(tempC, tempD);
ashleymills 0:ff9ebe0cf0e9 501 fieldSub(tempC, qy, ecc_prime_m, Sy);
ashleymills 0:ff9ebe0cf0e9 502 }
ashleymills 0:ff9ebe0cf0e9 503
ashleymills 0:ff9ebe0cf0e9 504 void ecc_ec_mult(const uint32_t *px, const uint32_t *py, const uint32_t *secret, uint32_t *resultx, uint32_t *resulty){
ashleymills 0:ff9ebe0cf0e9 505 uint32_t Qx[8];
ashleymills 0:ff9ebe0cf0e9 506 uint32_t Qy[8];
ashleymills 0:ff9ebe0cf0e9 507 setZero(Qx, 8);
ashleymills 0:ff9ebe0cf0e9 508 setZero(Qy, 8);
ashleymills 0:ff9ebe0cf0e9 509
ashleymills 0:ff9ebe0cf0e9 510 uint32_t tempx[8];
ashleymills 0:ff9ebe0cf0e9 511 uint32_t tempy[8];
ashleymills 0:ff9ebe0cf0e9 512
ashleymills 0:ff9ebe0cf0e9 513 int i;
ashleymills 0:ff9ebe0cf0e9 514 for (i = 256;i--;){
ashleymills 0:ff9ebe0cf0e9 515 ec_double(Qx, Qy, tempx, tempy);
ashleymills 0:ff9ebe0cf0e9 516 copy(tempx, Qx,arrayLength);
ashleymills 0:ff9ebe0cf0e9 517 copy(tempy, Qy,arrayLength);
ashleymills 0:ff9ebe0cf0e9 518 if ((((secret[i/32])>>(i%32)) & 0x01) == 1){ //<- TODO quark, muss anders gemacht werden
ashleymills 0:ff9ebe0cf0e9 519 ec_add(Qx, Qy, px, py, tempx, tempy); //eccAdd
ashleymills 0:ff9ebe0cf0e9 520 copy(tempx, Qx,arrayLength);
ashleymills 0:ff9ebe0cf0e9 521 copy(tempy, Qy,arrayLength);
ashleymills 0:ff9ebe0cf0e9 522 }
ashleymills 0:ff9ebe0cf0e9 523 }
ashleymills 0:ff9ebe0cf0e9 524 copy(Qx, resultx,arrayLength);
ashleymills 0:ff9ebe0cf0e9 525 copy(Qy, resulty,arrayLength);
ashleymills 0:ff9ebe0cf0e9 526 }
ashleymills 0:ff9ebe0cf0e9 527
ashleymills 0:ff9ebe0cf0e9 528 /**
ashleymills 0:ff9ebe0cf0e9 529 * Calculate the ecdsa signature.
ashleymills 0:ff9ebe0cf0e9 530 *
ashleymills 0:ff9ebe0cf0e9 531 * For a description of this algorithm see
ashleymills 0:ff9ebe0cf0e9 532 * https://en.wikipedia.org/wiki/Elliptic_Curve_DSA#Signature_generation_algorithm
ashleymills 0:ff9ebe0cf0e9 533 *
ashleymills 0:ff9ebe0cf0e9 534 * input:
ashleymills 0:ff9ebe0cf0e9 535 * d: private key on the curve secp256r1 (32 bytes)
ashleymills 0:ff9ebe0cf0e9 536 * e: hash to sign (32 bytes)
ashleymills 0:ff9ebe0cf0e9 537 * k: random data, this must be changed for every signature (32 bytes)
ashleymills 0:ff9ebe0cf0e9 538 *
ashleymills 0:ff9ebe0cf0e9 539 * output:
ashleymills 0:ff9ebe0cf0e9 540 * r: r value of the signature (36 bytes)
ashleymills 0:ff9ebe0cf0e9 541 * s: s value of the signature (36 bytes)
ashleymills 0:ff9ebe0cf0e9 542 *
ashleymills 0:ff9ebe0cf0e9 543 * return:
ashleymills 0:ff9ebe0cf0e9 544 * 0: everything is ok
ashleymills 0:ff9ebe0cf0e9 545 * -1: can not create signature, try again with different k.
ashleymills 0:ff9ebe0cf0e9 546 */
ashleymills 0:ff9ebe0cf0e9 547 int ecc_ecdsa_sign(const uint32_t *d, const uint32_t *e, const uint32_t *k, uint32_t *r, uint32_t *s)
ashleymills 0:ff9ebe0cf0e9 548 {
ashleymills 0:ff9ebe0cf0e9 549 uint32_t tmp1[16];
ashleymills 0:ff9ebe0cf0e9 550 uint32_t tmp2[9];
ashleymills 0:ff9ebe0cf0e9 551 uint32_t tmp3[9];
ashleymills 0:ff9ebe0cf0e9 552
ashleymills 0:ff9ebe0cf0e9 553 if (isZero(k))
ashleymills 0:ff9ebe0cf0e9 554 return -1;
ashleymills 0:ff9ebe0cf0e9 555
ashleymills 0:ff9ebe0cf0e9 556 // 4. Calculate the curve point (x_1, y_1) = k * G.
ashleymills 0:ff9ebe0cf0e9 557 ecc_ec_mult(ecc_g_point_x, ecc_g_point_y, k, r, tmp1);
ashleymills 0:ff9ebe0cf0e9 558
ashleymills 0:ff9ebe0cf0e9 559 // 5. Calculate r = x_1 \pmod{n}.
ashleymills 0:ff9ebe0cf0e9 560 fieldModO(r, r, 8);
ashleymills 0:ff9ebe0cf0e9 561
ashleymills 0:ff9ebe0cf0e9 562 // 5. If r = 0, go back to step 3.
ashleymills 0:ff9ebe0cf0e9 563 if (isZero(r))
ashleymills 0:ff9ebe0cf0e9 564 return -1;
ashleymills 0:ff9ebe0cf0e9 565
ashleymills 0:ff9ebe0cf0e9 566 // 6. Calculate s = k^{-1}(z + r d_A) \pmod{n}.
ashleymills 0:ff9ebe0cf0e9 567 // 6. r * d
ashleymills 0:ff9ebe0cf0e9 568 fieldMult(r, d, tmp1, arrayLength);
ashleymills 0:ff9ebe0cf0e9 569 fieldModO(tmp1, tmp2, 16);
ashleymills 0:ff9ebe0cf0e9 570
ashleymills 0:ff9ebe0cf0e9 571 // 6. z + (r d)
ashleymills 0:ff9ebe0cf0e9 572 tmp1[8] = add(e, tmp2, tmp1, 8);
ashleymills 0:ff9ebe0cf0e9 573 fieldModO(tmp1, tmp3, 9);
ashleymills 0:ff9ebe0cf0e9 574
ashleymills 0:ff9ebe0cf0e9 575 // 6. k^{-1}
ashleymills 0:ff9ebe0cf0e9 576 fieldInv(k, ecc_order_m, ecc_order_r, tmp2);
ashleymills 0:ff9ebe0cf0e9 577
ashleymills 0:ff9ebe0cf0e9 578 // 6. (k^{-1}) (z + (r d))
ashleymills 0:ff9ebe0cf0e9 579 fieldMult(tmp2, tmp3, tmp1, arrayLength);
ashleymills 0:ff9ebe0cf0e9 580 fieldModO(tmp1, s, 16);
ashleymills 0:ff9ebe0cf0e9 581
ashleymills 0:ff9ebe0cf0e9 582 // 6. If s = 0, go back to step 3.
ashleymills 0:ff9ebe0cf0e9 583 if (isZero(s))
ashleymills 0:ff9ebe0cf0e9 584 return -1;
ashleymills 0:ff9ebe0cf0e9 585
ashleymills 0:ff9ebe0cf0e9 586 return 0;
ashleymills 0:ff9ebe0cf0e9 587 }
ashleymills 0:ff9ebe0cf0e9 588
ashleymills 0:ff9ebe0cf0e9 589 /**
ashleymills 0:ff9ebe0cf0e9 590 * Verifies a ecdsa signature.
ashleymills 0:ff9ebe0cf0e9 591 *
ashleymills 0:ff9ebe0cf0e9 592 * For a description of this algorithm see
ashleymills 0:ff9ebe0cf0e9 593 * https://en.wikipedia.org/wiki/Elliptic_Curve_DSA#Signature_verification_algorithm
ashleymills 0:ff9ebe0cf0e9 594 *
ashleymills 0:ff9ebe0cf0e9 595 * input:
ashleymills 0:ff9ebe0cf0e9 596 * x: x coordinate of the public key (32 bytes)
ashleymills 0:ff9ebe0cf0e9 597 * y: y coordinate of the public key (32 bytes)
ashleymills 0:ff9ebe0cf0e9 598 * e: hash to verify the signature of (32 bytes)
ashleymills 0:ff9ebe0cf0e9 599 * r: r value of the signature (32 bytes)
ashleymills 0:ff9ebe0cf0e9 600 * s: s value of the signature (32 bytes)
ashleymills 0:ff9ebe0cf0e9 601 *
ashleymills 0:ff9ebe0cf0e9 602 * return:
ashleymills 0:ff9ebe0cf0e9 603 * 0: signature is ok
ashleymills 0:ff9ebe0cf0e9 604 * -1: signature check failed the signature is invalid
ashleymills 0:ff9ebe0cf0e9 605 */
ashleymills 0:ff9ebe0cf0e9 606 int ecc_ecdsa_validate(const uint32_t *x, const uint32_t *y, const uint32_t *e, const uint32_t *r, const uint32_t *s)
ashleymills 0:ff9ebe0cf0e9 607 {
ashleymills 0:ff9ebe0cf0e9 608 uint32_t w[8];
ashleymills 0:ff9ebe0cf0e9 609 uint32_t tmp[16];
ashleymills 0:ff9ebe0cf0e9 610 uint32_t u1[9];
ashleymills 0:ff9ebe0cf0e9 611 uint32_t u2[9];
ashleymills 0:ff9ebe0cf0e9 612 uint32_t tmp1_x[8];
ashleymills 0:ff9ebe0cf0e9 613 uint32_t tmp1_y[8];
ashleymills 0:ff9ebe0cf0e9 614 uint32_t tmp2_x[8];
ashleymills 0:ff9ebe0cf0e9 615 uint32_t tmp2_y[8];
ashleymills 0:ff9ebe0cf0e9 616 uint32_t tmp3_x[8];
ashleymills 0:ff9ebe0cf0e9 617 uint32_t tmp3_y[8];
ashleymills 0:ff9ebe0cf0e9 618
ashleymills 0:ff9ebe0cf0e9 619 // 3. Calculate w = s^{-1} \pmod{n}
ashleymills 0:ff9ebe0cf0e9 620 fieldInv(s, ecc_order_m, ecc_order_r, w);
ashleymills 0:ff9ebe0cf0e9 621
ashleymills 0:ff9ebe0cf0e9 622 // 4. Calculate u_1 = zw \pmod{n}
ashleymills 0:ff9ebe0cf0e9 623 fieldMult(e, w, tmp, arrayLength);
ashleymills 0:ff9ebe0cf0e9 624 fieldModO(tmp, u1, 16);
ashleymills 0:ff9ebe0cf0e9 625
ashleymills 0:ff9ebe0cf0e9 626 // 4. Calculate u_2 = rw \pmod{n}
ashleymills 0:ff9ebe0cf0e9 627 fieldMult(r, w, tmp, arrayLength);
ashleymills 0:ff9ebe0cf0e9 628 fieldModO(tmp, u2, 16);
ashleymills 0:ff9ebe0cf0e9 629
ashleymills 0:ff9ebe0cf0e9 630 // 5. Calculate the curve point (x_1, y_1) = u_1 * G + u_2 * Q_A.
ashleymills 0:ff9ebe0cf0e9 631 // tmp1 = u_1 * G
ashleymills 0:ff9ebe0cf0e9 632 ecc_ec_mult(ecc_g_point_x, ecc_g_point_y, u1, tmp1_x, tmp1_y);
ashleymills 0:ff9ebe0cf0e9 633
ashleymills 0:ff9ebe0cf0e9 634 // tmp2 = u_2 * Q_A
ashleymills 0:ff9ebe0cf0e9 635 ecc_ec_mult(x, y, u2, tmp2_x, tmp2_y);
ashleymills 0:ff9ebe0cf0e9 636
ashleymills 0:ff9ebe0cf0e9 637 // tmp3 = tmp1 + tmp2
ashleymills 0:ff9ebe0cf0e9 638 ec_add(tmp1_x, tmp1_y, tmp2_x, tmp2_y, tmp3_x, tmp3_y);
ashleymills 0:ff9ebe0cf0e9 639 // TODO: this u_1 * G + u_2 * Q_A could be optimiced with Straus's algorithm.
ashleymills 0:ff9ebe0cf0e9 640
ashleymills 0:ff9ebe0cf0e9 641 return isSame(tmp3_x, r, arrayLength) ? 0 : -1;
ashleymills 0:ff9ebe0cf0e9 642 }
ashleymills 0:ff9ebe0cf0e9 643
ashleymills 0:ff9ebe0cf0e9 644 int ecc_is_valid_key(const uint32_t * priv_key)
ashleymills 0:ff9ebe0cf0e9 645 {
ashleymills 0:ff9ebe0cf0e9 646 return isGreater(ecc_order_m, priv_key, arrayLength) == 1;
ashleymills 0:ff9ebe0cf0e9 647 }
ashleymills 0:ff9ebe0cf0e9 648
ashleymills 0:ff9ebe0cf0e9 649 /*
ashleymills 0:ff9ebe0cf0e9 650 * This exports the low level functions so the tests can use them.
ashleymills 0:ff9ebe0cf0e9 651 * In real use the compiler is now bale to optimice the code better.
ashleymills 0:ff9ebe0cf0e9 652 */
ashleymills 0:ff9ebe0cf0e9 653 #ifdef TEST_INCLUDE
ashleymills 0:ff9ebe0cf0e9 654 uint32_t ecc_add( const uint32_t *x, const uint32_t *y, uint32_t *result, uint8_t length)
ashleymills 0:ff9ebe0cf0e9 655 {
ashleymills 0:ff9ebe0cf0e9 656 return add(x, y, result, length);
ashleymills 0:ff9ebe0cf0e9 657 }
ashleymills 0:ff9ebe0cf0e9 658 uint32_t ecc_sub( const uint32_t *x, const uint32_t *y, uint32_t *result, uint8_t length)
ashleymills 0:ff9ebe0cf0e9 659 {
ashleymills 0:ff9ebe0cf0e9 660 return sub(x, y, result, length);
ashleymills 0:ff9ebe0cf0e9 661 }
ashleymills 0:ff9ebe0cf0e9 662 int ecc_fieldAdd(const uint32_t *x, const uint32_t *y, const uint32_t *reducer, uint32_t *result)
ashleymills 0:ff9ebe0cf0e9 663 {
ashleymills 0:ff9ebe0cf0e9 664 return fieldAdd(x, y, reducer, result);
ashleymills 0:ff9ebe0cf0e9 665 }
ashleymills 0:ff9ebe0cf0e9 666 int ecc_fieldSub(const uint32_t *x, const uint32_t *y, const uint32_t *modulus, uint32_t *result)
ashleymills 0:ff9ebe0cf0e9 667 {
ashleymills 0:ff9ebe0cf0e9 668 return fieldSub(x, y, modulus, result);
ashleymills 0:ff9ebe0cf0e9 669 }
ashleymills 0:ff9ebe0cf0e9 670 int ecc_fieldMult(const uint32_t *x, const uint32_t *y, uint32_t *result, uint8_t length)
ashleymills 0:ff9ebe0cf0e9 671 {
ashleymills 0:ff9ebe0cf0e9 672 return fieldMult(x, y, result, length);
ashleymills 0:ff9ebe0cf0e9 673 }
ashleymills 0:ff9ebe0cf0e9 674 void ecc_fieldModP(uint32_t *A, const uint32_t *B)
ashleymills 0:ff9ebe0cf0e9 675 {
ashleymills 0:ff9ebe0cf0e9 676 fieldModP(A, B);
ashleymills 0:ff9ebe0cf0e9 677 }
ashleymills 0:ff9ebe0cf0e9 678 void ecc_fieldModO(const uint32_t *A, uint32_t *result, uint8_t length)
ashleymills 0:ff9ebe0cf0e9 679 {
ashleymills 0:ff9ebe0cf0e9 680 fieldModO(A, result, length);
ashleymills 0:ff9ebe0cf0e9 681 }
ashleymills 0:ff9ebe0cf0e9 682 void ecc_fieldInv(const uint32_t *A, const uint32_t *modulus, const uint32_t *reducer, uint32_t *B)
ashleymills 0:ff9ebe0cf0e9 683 {
ashleymills 0:ff9ebe0cf0e9 684 fieldInv(A, modulus, reducer, B);
ashleymills 0:ff9ebe0cf0e9 685 }
ashleymills 0:ff9ebe0cf0e9 686 void ecc_copy(const uint32_t *from, uint32_t *to, uint8_t length)
ashleymills 0:ff9ebe0cf0e9 687 {
ashleymills 0:ff9ebe0cf0e9 688 copy(from, to, length);
ashleymills 0:ff9ebe0cf0e9 689 }
ashleymills 0:ff9ebe0cf0e9 690 int ecc_isSame(const uint32_t *A, const uint32_t *B, uint8_t length)
ashleymills 0:ff9ebe0cf0e9 691 {
ashleymills 0:ff9ebe0cf0e9 692 return isSame(A, B, length);
ashleymills 0:ff9ebe0cf0e9 693 }
ashleymills 0:ff9ebe0cf0e9 694 void ecc_setZero(uint32_t *A, const int length)
ashleymills 0:ff9ebe0cf0e9 695 {
ashleymills 0:ff9ebe0cf0e9 696 setZero(A, length);
ashleymills 0:ff9ebe0cf0e9 697 }
ashleymills 0:ff9ebe0cf0e9 698 int ecc_isOne(const uint32_t* A)
ashleymills 0:ff9ebe0cf0e9 699 {
ashleymills 0:ff9ebe0cf0e9 700 return isOne(A);
ashleymills 0:ff9ebe0cf0e9 701 }
ashleymills 0:ff9ebe0cf0e9 702 void ecc_rshift(uint32_t* A)
ashleymills 0:ff9ebe0cf0e9 703 {
ashleymills 0:ff9ebe0cf0e9 704 rshift(A);
ashleymills 0:ff9ebe0cf0e9 705 }
ashleymills 0:ff9ebe0cf0e9 706 int ecc_isGreater(const uint32_t *A, const uint32_t *B, uint8_t length)
ashleymills 0:ff9ebe0cf0e9 707 {
ashleymills 0:ff9ebe0cf0e9 708 return isGreater(A, B , length);
ashleymills 0:ff9ebe0cf0e9 709 }
ashleymills 0:ff9ebe0cf0e9 710
ashleymills 0:ff9ebe0cf0e9 711 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)
ashleymills 0:ff9ebe0cf0e9 712 {
ashleymills 0:ff9ebe0cf0e9 713 ec_add(px, py, qx, qy, Sx, Sy);
ashleymills 0:ff9ebe0cf0e9 714 }
ashleymills 0:ff9ebe0cf0e9 715 void ecc_ec_double(const uint32_t *px, const uint32_t *py, uint32_t *Dx, uint32_t *Dy)
ashleymills 0:ff9ebe0cf0e9 716 {
ashleymills 0:ff9ebe0cf0e9 717 ec_double(px, py, Dx, Dy);
ashleymills 0:ff9ebe0cf0e9 718 }
ashleymills 0:ff9ebe0cf0e9 719
ashleymills 0:ff9ebe0cf0e9 720 #endif /* TEST_INCLUDE */