Ashley Mills / cyassl-lib

This is a port of cyaSSL 2.7.0.

Dependents:   CyaSSL_DTLS_Cellular CyaSSL_DTLS_Ethernet

ctaocrypt/src/ecc.c@0:714293de3836, 2013-09-05 (annotated)

Committer:
ashleymills
Date:
Thu Sep 05 10:33:04 2013 +0000
Revision:
0:714293de3836
Initial commit

Who changed what in which revision?

UserRevisionLine numberNew contents of line
ashleymills 0:714293de3836 1 /* ecc.c
ashleymills 0:714293de3836 2 *
ashleymills 0:714293de3836 3 * Copyright (C) 2006-2013 wolfSSL Inc.
ashleymills 0:714293de3836 4 *
ashleymills 0:714293de3836 5 * This file is part of CyaSSL.
ashleymills 0:714293de3836 6 *
ashleymills 0:714293de3836 7 * CyaSSL is free software; you can redistribute it and/or modify
ashleymills 0:714293de3836 8 * it under the terms of the GNU General Public License as published by
ashleymills 0:714293de3836 9 * the Free Software Foundation; either version 2 of the License, or
ashleymills 0:714293de3836 10 * (at your option) any later version.
ashleymills 0:714293de3836 11 *
ashleymills 0:714293de3836 12 * CyaSSL is distributed in the hope that it will be useful,
ashleymills 0:714293de3836 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
ashleymills 0:714293de3836 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
ashleymills 0:714293de3836 15 * GNU General Public License for more details.
ashleymills 0:714293de3836 16 *
ashleymills 0:714293de3836 17 * You should have received a copy of the GNU General Public License
ashleymills 0:714293de3836 18 * along with this program; if not, write to the Free Software
ashleymills 0:714293de3836 19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
ashleymills 0:714293de3836 20 */
ashleymills 0:714293de3836 21
ashleymills 0:714293de3836 22
ashleymills 0:714293de3836 23 #ifdef HAVE_CONFIG_H
ashleymills 0:714293de3836 24 #include <config.h>
ashleymills 0:714293de3836 25 #endif
ashleymills 0:714293de3836 26
ashleymills 0:714293de3836 27 /* in case user set HAVE_ECC there */
ashleymills 0:714293de3836 28 #include <cyassl/ctaocrypt/settings.h>
ashleymills 0:714293de3836 29
ashleymills 0:714293de3836 30 #ifdef HAVE_ECC
ashleymills 0:714293de3836 31
ashleymills 0:714293de3836 32 #include <cyassl/ctaocrypt/ecc.h>
ashleymills 0:714293de3836 33 #include <cyassl/ctaocrypt/asn.h>
ashleymills 0:714293de3836 34 #include <cyassl/ctaocrypt/ctaoerror2.h>
ashleymills 0:714293de3836 35
ashleymills 0:714293de3836 36
ashleymills 0:714293de3836 37 /* map
ashleymills 0:714293de3836 38
ashleymills 0:714293de3836 39 ptmul -> mulmod
ashleymills 0:714293de3836 40
ashleymills 0:714293de3836 41 */
ashleymills 0:714293de3836 42
ashleymills 0:714293de3836 43 #define ECC112
ashleymills 0:714293de3836 44 #define ECC128
ashleymills 0:714293de3836 45 #define ECC160
ashleymills 0:714293de3836 46 #define ECC192
ashleymills 0:714293de3836 47 #define ECC224
ashleymills 0:714293de3836 48 #define ECC256
ashleymills 0:714293de3836 49 #define ECC384
ashleymills 0:714293de3836 50 #define ECC521
ashleymills 0:714293de3836 51
ashleymills 0:714293de3836 52
ashleymills 0:714293de3836 53
ashleymills 0:714293de3836 54 /* This holds the key settings. ***MUST*** be organized by size from
ashleymills 0:714293de3836 55 smallest to largest. */
ashleymills 0:714293de3836 56
ashleymills 0:714293de3836 57 const ecc_set_type ecc_sets[] = {
ashleymills 0:714293de3836 58 #ifdef ECC112
ashleymills 0:714293de3836 59 {
ashleymills 0:714293de3836 60 14,
ashleymills 0:714293de3836 61 "SECP112R1",
ashleymills 0:714293de3836 62 "DB7C2ABF62E35E668076BEAD208B",
ashleymills 0:714293de3836 63 "659EF8BA043916EEDE8911702B22",
ashleymills 0:714293de3836 64 "DB7C2ABF62E35E7628DFAC6561C5",
ashleymills 0:714293de3836 65 "09487239995A5EE76B55F9C2F098",
ashleymills 0:714293de3836 66 "A89CE5AF8724C0A23E0E0FF77500"
ashleymills 0:714293de3836 67 },
ashleymills 0:714293de3836 68 #endif
ashleymills 0:714293de3836 69 #ifdef ECC128
ashleymills 0:714293de3836 70 {
ashleymills 0:714293de3836 71 16,
ashleymills 0:714293de3836 72 "SECP128R1",
ashleymills 0:714293de3836 73 "FFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFF",
ashleymills 0:714293de3836 74 "E87579C11079F43DD824993C2CEE5ED3",
ashleymills 0:714293de3836 75 "FFFFFFFE0000000075A30D1B9038A115",
ashleymills 0:714293de3836 76 "161FF7528B899B2D0C28607CA52C5B86",
ashleymills 0:714293de3836 77 "CF5AC8395BAFEB13C02DA292DDED7A83",
ashleymills 0:714293de3836 78 },
ashleymills 0:714293de3836 79 #endif
ashleymills 0:714293de3836 80 #ifdef ECC160
ashleymills 0:714293de3836 81 {
ashleymills 0:714293de3836 82 20,
ashleymills 0:714293de3836 83 "SECP160R1",
ashleymills 0:714293de3836 84 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFF",
ashleymills 0:714293de3836 85 "1C97BEFC54BD7A8B65ACF89F81D4D4ADC565FA45",
ashleymills 0:714293de3836 86 "0100000000000000000001F4C8F927AED3CA752257",
ashleymills 0:714293de3836 87 "4A96B5688EF573284664698968C38BB913CBFC82",
ashleymills 0:714293de3836 88 "23A628553168947D59DCC912042351377AC5FB32",
ashleymills 0:714293de3836 89 },
ashleymills 0:714293de3836 90 #endif
ashleymills 0:714293de3836 91 #ifdef ECC192
ashleymills 0:714293de3836 92 {
ashleymills 0:714293de3836 93 24,
ashleymills 0:714293de3836 94 "ECC-192",
ashleymills 0:714293de3836 95 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF",
ashleymills 0:714293de3836 96 "64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1",
ashleymills 0:714293de3836 97 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831",
ashleymills 0:714293de3836 98 "188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012",
ashleymills 0:714293de3836 99 "7192B95FFC8DA78631011ED6B24CDD573F977A11E794811",
ashleymills 0:714293de3836 100 },
ashleymills 0:714293de3836 101 #endif
ashleymills 0:714293de3836 102 #ifdef ECC224
ashleymills 0:714293de3836 103 {
ashleymills 0:714293de3836 104 28,
ashleymills 0:714293de3836 105 "ECC-224",
ashleymills 0:714293de3836 106 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001",
ashleymills 0:714293de3836 107 "B4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4",
ashleymills 0:714293de3836 108 "FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D",
ashleymills 0:714293de3836 109 "B70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21",
ashleymills 0:714293de3836 110 "BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34",
ashleymills 0:714293de3836 111 },
ashleymills 0:714293de3836 112 #endif
ashleymills 0:714293de3836 113 #ifdef ECC256
ashleymills 0:714293de3836 114 {
ashleymills 0:714293de3836 115 32,
ashleymills 0:714293de3836 116 "ECC-256",
ashleymills 0:714293de3836 117 "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF",
ashleymills 0:714293de3836 118 "5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B",
ashleymills 0:714293de3836 119 "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551",
ashleymills 0:714293de3836 120 "6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296",
ashleymills 0:714293de3836 121 "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5",
ashleymills 0:714293de3836 122 },
ashleymills 0:714293de3836 123 #endif
ashleymills 0:714293de3836 124 #ifdef ECC384
ashleymills 0:714293de3836 125 {
ashleymills 0:714293de3836 126 48,
ashleymills 0:714293de3836 127 "ECC-384",
ashleymills 0:714293de3836 128 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF",
ashleymills 0:714293de3836 129 "B3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF",
ashleymills 0:714293de3836 130 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973",
ashleymills 0:714293de3836 131 "AA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B9859F741E082542A385502F25DBF55296C3A545E3872760AB7",
ashleymills 0:714293de3836 132 "3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F",
ashleymills 0:714293de3836 133 },
ashleymills 0:714293de3836 134 #endif
ashleymills 0:714293de3836 135 #ifdef ECC521
ashleymills 0:714293de3836 136 {
ashleymills 0:714293de3836 137 66,
ashleymills 0:714293de3836 138 "ECC-521",
ashleymills 0:714293de3836 139 "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
ashleymills 0:714293de3836 140 "51953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00",
ashleymills 0:714293de3836 141 "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409",
ashleymills 0:714293de3836 142 "C6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66",
ashleymills 0:714293de3836 143 "11839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650",
ashleymills 0:714293de3836 144 },
ashleymills 0:714293de3836 145 #endif
ashleymills 0:714293de3836 146 {
ashleymills 0:714293de3836 147 0,
ashleymills 0:714293de3836 148 NULL, NULL, NULL, NULL, NULL, NULL
ashleymills 0:714293de3836 149 }
ashleymills 0:714293de3836 150 };
ashleymills 0:714293de3836 151
ashleymills 0:714293de3836 152
ashleymills 0:714293de3836 153 ecc_point* ecc_new_point(void);
ashleymills 0:714293de3836 154 void ecc_del_point(ecc_point* p);
ashleymills 0:714293de3836 155 int ecc_map(ecc_point*, mp_int*, mp_digit*);
ashleymills 0:714293de3836 156 int ecc_projective_add_point(ecc_point* P, ecc_point* Q, ecc_point* R,
ashleymills 0:714293de3836 157 mp_int* modulus, mp_digit* mp);
ashleymills 0:714293de3836 158 int ecc_projective_dbl_point(ecc_point* P, ecc_point* R, mp_int* modulus,
ashleymills 0:714293de3836 159 mp_digit* mp);
ashleymills 0:714293de3836 160
ashleymills 0:714293de3836 161
ashleymills 0:714293de3836 162 /* helper for either lib */
ashleymills 0:714293de3836 163 static int get_digit_count(mp_int* a)
ashleymills 0:714293de3836 164 {
ashleymills 0:714293de3836 165 if (a == NULL)
ashleymills 0:714293de3836 166 return 0;
ashleymills 0:714293de3836 167
ashleymills 0:714293de3836 168 return a->used;
ashleymills 0:714293de3836 169 }
ashleymills 0:714293de3836 170
ashleymills 0:714293de3836 171 /* helper for either lib */
ashleymills 0:714293de3836 172 static unsigned long get_digit(mp_int* a, int n)
ashleymills 0:714293de3836 173 {
ashleymills 0:714293de3836 174 if (a == NULL)
ashleymills 0:714293de3836 175 return 0;
ashleymills 0:714293de3836 176
ashleymills 0:714293de3836 177 return (n >= a->used || n < 0) ? 0 : a->dp[n];
ashleymills 0:714293de3836 178 }
ashleymills 0:714293de3836 179
ashleymills 0:714293de3836 180
ashleymills 0:714293de3836 181 /**
ashleymills 0:714293de3836 182 Add two ECC points
ashleymills 0:714293de3836 183 P The point to add
ashleymills 0:714293de3836 184 Q The point to add
ashleymills 0:714293de3836 185 R [out] The destination of the double
ashleymills 0:714293de3836 186 modulus The modulus of the field the ECC curve is in
ashleymills 0:714293de3836 187 mp The "b" value from montgomery_setup()
ashleymills 0:714293de3836 188 return MP_OKAY on success
ashleymills 0:714293de3836 189 */
ashleymills 0:714293de3836 190 int ecc_projective_add_point(ecc_point* P, ecc_point* Q, ecc_point* R,
ashleymills 0:714293de3836 191 mp_int* modulus, mp_digit* mp)
ashleymills 0:714293de3836 192 {
ashleymills 0:714293de3836 193 mp_int t1;
ashleymills 0:714293de3836 194 mp_int t2;
ashleymills 0:714293de3836 195 mp_int x;
ashleymills 0:714293de3836 196 mp_int y;
ashleymills 0:714293de3836 197 mp_int z;
ashleymills 0:714293de3836 198 int err;
ashleymills 0:714293de3836 199
ashleymills 0:714293de3836 200 if (P == NULL || Q == NULL || R == NULL || modulus == NULL || mp == NULL)
ashleymills 0:714293de3836 201 return ECC_BAD_ARG_E;
ashleymills 0:714293de3836 202
ashleymills 0:714293de3836 203 if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, NULL)) != MP_OKAY) {
ashleymills 0:714293de3836 204 return err;
ashleymills 0:714293de3836 205 }
ashleymills 0:714293de3836 206
ashleymills 0:714293de3836 207 /* should we dbl instead? */
ashleymills 0:714293de3836 208 err = mp_sub(modulus, &Q->y, &t1);
ashleymills 0:714293de3836 209
ashleymills 0:714293de3836 210 if (err == MP_OKAY) {
ashleymills 0:714293de3836 211 if ( (mp_cmp(&P->x, &Q->x) == MP_EQ) &&
ashleymills 0:714293de3836 212 (get_digit_count(&Q->z) && mp_cmp(&P->z, &Q->z) == MP_EQ) &&
ashleymills 0:714293de3836 213 (mp_cmp(&P->y, &Q->y) == MP_EQ || mp_cmp(&P->y, &t1) == MP_EQ)) {
ashleymills 0:714293de3836 214 mp_clear(&t1);
ashleymills 0:714293de3836 215 mp_clear(&t2);
ashleymills 0:714293de3836 216 mp_clear(&x);
ashleymills 0:714293de3836 217 mp_clear(&y);
ashleymills 0:714293de3836 218 mp_clear(&z);
ashleymills 0:714293de3836 219
ashleymills 0:714293de3836 220 return ecc_projective_dbl_point(P, R, modulus, mp);
ashleymills 0:714293de3836 221 }
ashleymills 0:714293de3836 222 }
ashleymills 0:714293de3836 223
ashleymills 0:714293de3836 224 if (err == MP_OKAY)
ashleymills 0:714293de3836 225 err = mp_copy(&P->x, &x);
ashleymills 0:714293de3836 226 if (err == MP_OKAY)
ashleymills 0:714293de3836 227 err = mp_copy(&P->y, &y);
ashleymills 0:714293de3836 228 if (err == MP_OKAY)
ashleymills 0:714293de3836 229 err = mp_copy(&P->z, &z);
ashleymills 0:714293de3836 230
ashleymills 0:714293de3836 231 /* if Z is one then these are no-operations */
ashleymills 0:714293de3836 232 if (err == MP_OKAY) {
ashleymills 0:714293de3836 233 if (get_digit_count(&Q->z)) {
ashleymills 0:714293de3836 234 /* T1 = Z' * Z' */
ashleymills 0:714293de3836 235 err = mp_sqr(&Q->z, &t1);
ashleymills 0:714293de3836 236 if (err == MP_OKAY)
ashleymills 0:714293de3836 237 err = mp_montgomery_reduce(&t1, modulus, *mp);
ashleymills 0:714293de3836 238
ashleymills 0:714293de3836 239 /* X = X * T1 */
ashleymills 0:714293de3836 240 if (err == MP_OKAY)
ashleymills 0:714293de3836 241 err = mp_mul(&t1, &x, &x);
ashleymills 0:714293de3836 242 if (err == MP_OKAY)
ashleymills 0:714293de3836 243 err = mp_montgomery_reduce(&x, modulus, *mp);
ashleymills 0:714293de3836 244
ashleymills 0:714293de3836 245 /* T1 = Z' * T1 */
ashleymills 0:714293de3836 246 if (err == MP_OKAY)
ashleymills 0:714293de3836 247 err = mp_mul(&Q->z, &t1, &t1);
ashleymills 0:714293de3836 248 if (err == MP_OKAY)
ashleymills 0:714293de3836 249 err = mp_montgomery_reduce(&t1, modulus, *mp);
ashleymills 0:714293de3836 250
ashleymills 0:714293de3836 251 /* Y = Y * T1 */
ashleymills 0:714293de3836 252 if (err == MP_OKAY)
ashleymills 0:714293de3836 253 err = mp_mul(&t1, &y, &y);
ashleymills 0:714293de3836 254 if (err == MP_OKAY)
ashleymills 0:714293de3836 255 err = mp_montgomery_reduce(&y, modulus, *mp);
ashleymills 0:714293de3836 256 }
ashleymills 0:714293de3836 257 }
ashleymills 0:714293de3836 258
ashleymills 0:714293de3836 259 /* T1 = Z*Z */
ashleymills 0:714293de3836 260 if (err == MP_OKAY)
ashleymills 0:714293de3836 261 err = mp_sqr(&z, &t1);
ashleymills 0:714293de3836 262 if (err == MP_OKAY)
ashleymills 0:714293de3836 263 err = mp_montgomery_reduce(&t1, modulus, *mp);
ashleymills 0:714293de3836 264
ashleymills 0:714293de3836 265 /* T2 = X' * T1 */
ashleymills 0:714293de3836 266 if (err == MP_OKAY)
ashleymills 0:714293de3836 267 err = mp_mul(&Q->x, &t1, &t2);
ashleymills 0:714293de3836 268 if (err == MP_OKAY)
ashleymills 0:714293de3836 269 err = mp_montgomery_reduce(&t2, modulus, *mp);
ashleymills 0:714293de3836 270
ashleymills 0:714293de3836 271 /* T1 = Z * T1 */
ashleymills 0:714293de3836 272 if (err == MP_OKAY)
ashleymills 0:714293de3836 273 err = mp_mul(&z, &t1, &t1);
ashleymills 0:714293de3836 274 if (err == MP_OKAY)
ashleymills 0:714293de3836 275 err = mp_montgomery_reduce(&t1, modulus, *mp);
ashleymills 0:714293de3836 276
ashleymills 0:714293de3836 277 /* T1 = Y' * T1 */
ashleymills 0:714293de3836 278 if (err == MP_OKAY)
ashleymills 0:714293de3836 279 err = mp_mul(&Q->y, &t1, &t1);
ashleymills 0:714293de3836 280 if (err == MP_OKAY)
ashleymills 0:714293de3836 281 err = mp_montgomery_reduce(&t1, modulus, *mp);
ashleymills 0:714293de3836 282
ashleymills 0:714293de3836 283 /* Y = Y - T1 */
ashleymills 0:714293de3836 284 if (err == MP_OKAY)
ashleymills 0:714293de3836 285 err = mp_sub(&y, &t1, &y);
ashleymills 0:714293de3836 286 if (err == MP_OKAY) {
ashleymills 0:714293de3836 287 if (mp_cmp_d(&y, 0) == MP_LT)
ashleymills 0:714293de3836 288 err = mp_add(&y, modulus, &y);
ashleymills 0:714293de3836 289 }
ashleymills 0:714293de3836 290 /* T1 = 2T1 */
ashleymills 0:714293de3836 291 if (err == MP_OKAY)
ashleymills 0:714293de3836 292 err = mp_add(&t1, &t1, &t1);
ashleymills 0:714293de3836 293 if (err == MP_OKAY) {
ashleymills 0:714293de3836 294 if (mp_cmp(&t1, modulus) != MP_LT)
ashleymills 0:714293de3836 295 err = mp_sub(&t1, modulus, &t1);
ashleymills 0:714293de3836 296 }
ashleymills 0:714293de3836 297 /* T1 = Y + T1 */
ashleymills 0:714293de3836 298 if (err == MP_OKAY)
ashleymills 0:714293de3836 299 err = mp_add(&t1, &y, &t1);
ashleymills 0:714293de3836 300 if (err == MP_OKAY) {
ashleymills 0:714293de3836 301 if (mp_cmp(&t1, modulus) != MP_LT)
ashleymills 0:714293de3836 302 err = mp_sub(&t1, modulus, &t1);
ashleymills 0:714293de3836 303 }
ashleymills 0:714293de3836 304 /* X = X - T2 */
ashleymills 0:714293de3836 305 if (err == MP_OKAY)
ashleymills 0:714293de3836 306 err = mp_sub(&x, &t2, &x);
ashleymills 0:714293de3836 307 if (err == MP_OKAY) {
ashleymills 0:714293de3836 308 if (mp_cmp_d(&x, 0) == MP_LT)
ashleymills 0:714293de3836 309 err = mp_add(&x, modulus, &x);
ashleymills 0:714293de3836 310 }
ashleymills 0:714293de3836 311 /* T2 = 2T2 */
ashleymills 0:714293de3836 312 if (err == MP_OKAY)
ashleymills 0:714293de3836 313 err = mp_add(&t2, &t2, &t2);
ashleymills 0:714293de3836 314 if (err == MP_OKAY) {
ashleymills 0:714293de3836 315 if (mp_cmp(&t2, modulus) != MP_LT)
ashleymills 0:714293de3836 316 err = mp_sub(&t2, modulus, &t2);
ashleymills 0:714293de3836 317 }
ashleymills 0:714293de3836 318 /* T2 = X + T2 */
ashleymills 0:714293de3836 319 if (err == MP_OKAY)
ashleymills 0:714293de3836 320 err = mp_add(&t2, &x, &t2);
ashleymills 0:714293de3836 321 if (err == MP_OKAY) {
ashleymills 0:714293de3836 322 if (mp_cmp(&t2, modulus) != MP_LT)
ashleymills 0:714293de3836 323 err = mp_sub(&t2, modulus, &t2);
ashleymills 0:714293de3836 324 }
ashleymills 0:714293de3836 325
ashleymills 0:714293de3836 326 if (err == MP_OKAY) {
ashleymills 0:714293de3836 327 if (get_digit_count(&Q->z)) {
ashleymills 0:714293de3836 328 /* Z = Z * Z' */
ashleymills 0:714293de3836 329 err = mp_mul(&z, &Q->z, &z);
ashleymills 0:714293de3836 330 if (err == MP_OKAY)
ashleymills 0:714293de3836 331 err = mp_montgomery_reduce(&z, modulus, *mp);
ashleymills 0:714293de3836 332 }
ashleymills 0:714293de3836 333 }
ashleymills 0:714293de3836 334
ashleymills 0:714293de3836 335 /* Z = Z * X */
ashleymills 0:714293de3836 336 if (err == MP_OKAY)
ashleymills 0:714293de3836 337 err = mp_mul(&z, &x, &z);
ashleymills 0:714293de3836 338 if (err == MP_OKAY)
ashleymills 0:714293de3836 339 err = mp_montgomery_reduce(&z, modulus, *mp);
ashleymills 0:714293de3836 340
ashleymills 0:714293de3836 341 /* T1 = T1 * X */
ashleymills 0:714293de3836 342 if (err == MP_OKAY)
ashleymills 0:714293de3836 343 err = mp_mul(&t1, &x, &t1);
ashleymills 0:714293de3836 344 if (err == MP_OKAY)
ashleymills 0:714293de3836 345 err = mp_montgomery_reduce(&t1, modulus, *mp);
ashleymills 0:714293de3836 346
ashleymills 0:714293de3836 347 /* X = X * X */
ashleymills 0:714293de3836 348 if (err == MP_OKAY)
ashleymills 0:714293de3836 349 err = mp_sqr(&x, &x);
ashleymills 0:714293de3836 350 if (err == MP_OKAY)
ashleymills 0:714293de3836 351 err = mp_montgomery_reduce(&x, modulus, *mp);
ashleymills 0:714293de3836 352
ashleymills 0:714293de3836 353 /* T2 = T2 * x */
ashleymills 0:714293de3836 354 if (err == MP_OKAY)
ashleymills 0:714293de3836 355 err = mp_mul(&t2, &x, &t2);
ashleymills 0:714293de3836 356 if (err == MP_OKAY)
ashleymills 0:714293de3836 357 err = mp_montgomery_reduce(&t2, modulus, *mp);
ashleymills 0:714293de3836 358
ashleymills 0:714293de3836 359 /* T1 = T1 * X */
ashleymills 0:714293de3836 360 if (err == MP_OKAY)
ashleymills 0:714293de3836 361 err = mp_mul(&t1, &x, &t1);
ashleymills 0:714293de3836 362 if (err == MP_OKAY)
ashleymills 0:714293de3836 363 err = mp_montgomery_reduce(&t1, modulus, *mp);
ashleymills 0:714293de3836 364
ashleymills 0:714293de3836 365 /* X = Y*Y */
ashleymills 0:714293de3836 366 if (err == MP_OKAY)
ashleymills 0:714293de3836 367 err = mp_sqr(&y, &x);
ashleymills 0:714293de3836 368 if (err == MP_OKAY)
ashleymills 0:714293de3836 369 err = mp_montgomery_reduce(&x, modulus, *mp);
ashleymills 0:714293de3836 370
ashleymills 0:714293de3836 371 /* X = X - T2 */
ashleymills 0:714293de3836 372 if (err == MP_OKAY)
ashleymills 0:714293de3836 373 err = mp_sub(&x, &t2, &x);
ashleymills 0:714293de3836 374 if (err == MP_OKAY) {
ashleymills 0:714293de3836 375 if (mp_cmp_d(&x, 0) == MP_LT)
ashleymills 0:714293de3836 376 err = mp_add(&x, modulus, &x);
ashleymills 0:714293de3836 377 }
ashleymills 0:714293de3836 378 /* T2 = T2 - X */
ashleymills 0:714293de3836 379 if (err == MP_OKAY)
ashleymills 0:714293de3836 380 err = mp_sub(&t2, &x, &t2);
ashleymills 0:714293de3836 381 if (err == MP_OKAY) {
ashleymills 0:714293de3836 382 if (mp_cmp_d(&t2, 0) == MP_LT)
ashleymills 0:714293de3836 383 err = mp_add(&t2, modulus, &t2);
ashleymills 0:714293de3836 384 }
ashleymills 0:714293de3836 385 /* T2 = T2 - X */
ashleymills 0:714293de3836 386 if (err == MP_OKAY)
ashleymills 0:714293de3836 387 err = mp_sub(&t2, &x, &t2);
ashleymills 0:714293de3836 388 if (err == MP_OKAY) {
ashleymills 0:714293de3836 389 if (mp_cmp_d(&t2, 0) == MP_LT)
ashleymills 0:714293de3836 390 err = mp_add(&t2, modulus, &t2);
ashleymills 0:714293de3836 391 }
ashleymills 0:714293de3836 392 /* T2 = T2 * Y */
ashleymills 0:714293de3836 393 if (err == MP_OKAY)
ashleymills 0:714293de3836 394 err = mp_mul(&t2, &y, &t2);
ashleymills 0:714293de3836 395 if (err == MP_OKAY)
ashleymills 0:714293de3836 396 err = mp_montgomery_reduce(&t2, modulus, *mp);
ashleymills 0:714293de3836 397
ashleymills 0:714293de3836 398 /* Y = T2 - T1 */
ashleymills 0:714293de3836 399 if (err == MP_OKAY)
ashleymills 0:714293de3836 400 err = mp_sub(&t2, &t1, &y);
ashleymills 0:714293de3836 401 if (err == MP_OKAY) {
ashleymills 0:714293de3836 402 if (mp_cmp_d(&y, 0) == MP_LT)
ashleymills 0:714293de3836 403 err = mp_add(&y, modulus, &y);
ashleymills 0:714293de3836 404 }
ashleymills 0:714293de3836 405 /* Y = Y/2 */
ashleymills 0:714293de3836 406 if (err == MP_OKAY) {
ashleymills 0:714293de3836 407 if (mp_isodd(&y))
ashleymills 0:714293de3836 408 err = mp_add(&y, modulus, &y);
ashleymills 0:714293de3836 409 }
ashleymills 0:714293de3836 410 if (err == MP_OKAY)
ashleymills 0:714293de3836 411 err = mp_div_2(&y, &y);
ashleymills 0:714293de3836 412
ashleymills 0:714293de3836 413 if (err == MP_OKAY)
ashleymills 0:714293de3836 414 err = mp_copy(&x, &R->x);
ashleymills 0:714293de3836 415 if (err == MP_OKAY)
ashleymills 0:714293de3836 416 err = mp_copy(&y, &R->y);
ashleymills 0:714293de3836 417 if (err == MP_OKAY)
ashleymills 0:714293de3836 418 err = mp_copy(&z, &R->z);
ashleymills 0:714293de3836 419
ashleymills 0:714293de3836 420 /* clean up */
ashleymills 0:714293de3836 421 mp_clear(&t1);
ashleymills 0:714293de3836 422 mp_clear(&t2);
ashleymills 0:714293de3836 423 mp_clear(&x);
ashleymills 0:714293de3836 424 mp_clear(&y);
ashleymills 0:714293de3836 425 mp_clear(&z);
ashleymills 0:714293de3836 426
ashleymills 0:714293de3836 427 return err;
ashleymills 0:714293de3836 428 }
ashleymills 0:714293de3836 429
ashleymills 0:714293de3836 430
ashleymills 0:714293de3836 431 /**
ashleymills 0:714293de3836 432 Double an ECC point
ashleymills 0:714293de3836 433 P The point to double
ashleymills 0:714293de3836 434 R [out] The destination of the double
ashleymills 0:714293de3836 435 modulus The modulus of the field the ECC curve is in
ashleymills 0:714293de3836 436 mp The "b" value from montgomery_setup()
ashleymills 0:714293de3836 437 return MP_OKAY on success
ashleymills 0:714293de3836 438 */
ashleymills 0:714293de3836 439 int ecc_projective_dbl_point(ecc_point *P, ecc_point *R, mp_int* modulus,
ashleymills 0:714293de3836 440 mp_digit* mp)
ashleymills 0:714293de3836 441 {
ashleymills 0:714293de3836 442 mp_int t1;
ashleymills 0:714293de3836 443 mp_int t2;
ashleymills 0:714293de3836 444 int err;
ashleymills 0:714293de3836 445
ashleymills 0:714293de3836 446 if (P == NULL || R == NULL || modulus == NULL || mp == NULL)
ashleymills 0:714293de3836 447 return ECC_BAD_ARG_E;
ashleymills 0:714293de3836 448
ashleymills 0:714293de3836 449 if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) {
ashleymills 0:714293de3836 450 return err;
ashleymills 0:714293de3836 451 }
ashleymills 0:714293de3836 452
ashleymills 0:714293de3836 453 if (P != R) {
ashleymills 0:714293de3836 454 err = mp_copy(&P->x, &R->x);
ashleymills 0:714293de3836 455 if (err == MP_OKAY)
ashleymills 0:714293de3836 456 err = mp_copy(&P->y, &R->y);
ashleymills 0:714293de3836 457 if (err == MP_OKAY)
ashleymills 0:714293de3836 458 err = mp_copy(&P->z, &R->z);
ashleymills 0:714293de3836 459 }
ashleymills 0:714293de3836 460
ashleymills 0:714293de3836 461 /* t1 = Z * Z */
ashleymills 0:714293de3836 462 if (err == MP_OKAY)
ashleymills 0:714293de3836 463 err = mp_sqr(&R->z, &t1);
ashleymills 0:714293de3836 464 if (err == MP_OKAY)
ashleymills 0:714293de3836 465 err = mp_montgomery_reduce(&t1, modulus, *mp);
ashleymills 0:714293de3836 466
ashleymills 0:714293de3836 467 /* Z = Y * Z */
ashleymills 0:714293de3836 468 if (err == MP_OKAY)
ashleymills 0:714293de3836 469 err = mp_mul(&R->z, &R->y, &R->z);
ashleymills 0:714293de3836 470 if (err == MP_OKAY)
ashleymills 0:714293de3836 471 err = mp_montgomery_reduce(&R->z, modulus, *mp);
ashleymills 0:714293de3836 472
ashleymills 0:714293de3836 473 /* Z = 2Z */
ashleymills 0:714293de3836 474 if (err == MP_OKAY)
ashleymills 0:714293de3836 475 err = mp_add(&R->z, &R->z, &R->z);
ashleymills 0:714293de3836 476 if (err == MP_OKAY) {
ashleymills 0:714293de3836 477 if (mp_cmp(&R->z, modulus) != MP_LT)
ashleymills 0:714293de3836 478 err = mp_sub(&R->z, modulus, &R->z);
ashleymills 0:714293de3836 479 }
ashleymills 0:714293de3836 480
ashleymills 0:714293de3836 481 /* T2 = X - T1 */
ashleymills 0:714293de3836 482 if (err == MP_OKAY)
ashleymills 0:714293de3836 483 err = mp_sub(&R->x, &t1, &t2);
ashleymills 0:714293de3836 484 if (err == MP_OKAY) {
ashleymills 0:714293de3836 485 if (mp_cmp_d(&t2, 0) == MP_LT)
ashleymills 0:714293de3836 486 err = mp_add(&t2, modulus, &t2);
ashleymills 0:714293de3836 487 }
ashleymills 0:714293de3836 488 /* T1 = X + T1 */
ashleymills 0:714293de3836 489 if (err == MP_OKAY)
ashleymills 0:714293de3836 490 err = mp_add(&t1, &R->x, &t1);
ashleymills 0:714293de3836 491 if (err == MP_OKAY) {
ashleymills 0:714293de3836 492 if (mp_cmp(&t1, modulus) != MP_LT)
ashleymills 0:714293de3836 493 err = mp_sub(&t1, modulus, &t1);
ashleymills 0:714293de3836 494 }
ashleymills 0:714293de3836 495 /* T2 = T1 * T2 */
ashleymills 0:714293de3836 496 if (err == MP_OKAY)
ashleymills 0:714293de3836 497 err = mp_mul(&t1, &t2, &t2);
ashleymills 0:714293de3836 498 if (err == MP_OKAY)
ashleymills 0:714293de3836 499 err = mp_montgomery_reduce(&t2, modulus, *mp);
ashleymills 0:714293de3836 500
ashleymills 0:714293de3836 501 /* T1 = 2T2 */
ashleymills 0:714293de3836 502 if (err == MP_OKAY)
ashleymills 0:714293de3836 503 err = mp_add(&t2, &t2, &t1);
ashleymills 0:714293de3836 504 if (err == MP_OKAY) {
ashleymills 0:714293de3836 505 if (mp_cmp(&t1, modulus) != MP_LT)
ashleymills 0:714293de3836 506 err = mp_sub(&t1, modulus, &t1);
ashleymills 0:714293de3836 507 }
ashleymills 0:714293de3836 508 /* T1 = T1 + T2 */
ashleymills 0:714293de3836 509 if (err == MP_OKAY)
ashleymills 0:714293de3836 510 err = mp_add(&t1, &t2, &t1);
ashleymills 0:714293de3836 511 if (err == MP_OKAY) {
ashleymills 0:714293de3836 512 if (mp_cmp(&t1, modulus) != MP_LT)
ashleymills 0:714293de3836 513 err = mp_sub(&t1, modulus, &t1);
ashleymills 0:714293de3836 514 }
ashleymills 0:714293de3836 515 /* Y = 2Y */
ashleymills 0:714293de3836 516 if (err == MP_OKAY)
ashleymills 0:714293de3836 517 err = mp_add(&R->y, &R->y, &R->y);
ashleymills 0:714293de3836 518 if (err == MP_OKAY) {
ashleymills 0:714293de3836 519 if (mp_cmp(&R->y, modulus) != MP_LT)
ashleymills 0:714293de3836 520 err = mp_sub(&R->y, modulus, &R->y);
ashleymills 0:714293de3836 521 }
ashleymills 0:714293de3836 522 /* Y = Y * Y */
ashleymills 0:714293de3836 523 if (err == MP_OKAY)
ashleymills 0:714293de3836 524 err = mp_sqr(&R->y, &R->y);
ashleymills 0:714293de3836 525 if (err == MP_OKAY)
ashleymills 0:714293de3836 526 err = mp_montgomery_reduce(&R->y, modulus, *mp);
ashleymills 0:714293de3836 527
ashleymills 0:714293de3836 528 /* T2 = Y * Y */
ashleymills 0:714293de3836 529 if (err == MP_OKAY)
ashleymills 0:714293de3836 530 err = mp_sqr(&R->y, &t2);
ashleymills 0:714293de3836 531 if (err == MP_OKAY)
ashleymills 0:714293de3836 532 err = mp_montgomery_reduce(&t2, modulus, *mp);
ashleymills 0:714293de3836 533
ashleymills 0:714293de3836 534 /* T2 = T2/2 */
ashleymills 0:714293de3836 535 if (err == MP_OKAY) {
ashleymills 0:714293de3836 536 if (mp_isodd(&t2))
ashleymills 0:714293de3836 537 err = mp_add(&t2, modulus, &t2);
ashleymills 0:714293de3836 538 }
ashleymills 0:714293de3836 539 if (err == MP_OKAY)
ashleymills 0:714293de3836 540 err = mp_div_2(&t2, &t2);
ashleymills 0:714293de3836 541
ashleymills 0:714293de3836 542 /* Y = Y * X */
ashleymills 0:714293de3836 543 if (err == MP_OKAY)
ashleymills 0:714293de3836 544 err = mp_mul(&R->y, &R->x, &R->y);
ashleymills 0:714293de3836 545 if (err == MP_OKAY)
ashleymills 0:714293de3836 546 err = mp_montgomery_reduce(&R->y, modulus, *mp);
ashleymills 0:714293de3836 547
ashleymills 0:714293de3836 548 /* X = T1 * T1 */
ashleymills 0:714293de3836 549 if (err == MP_OKAY)
ashleymills 0:714293de3836 550 err = mp_sqr(&t1, &R->x);
ashleymills 0:714293de3836 551 if (err == MP_OKAY)
ashleymills 0:714293de3836 552 err = mp_montgomery_reduce(&R->x, modulus, *mp);
ashleymills 0:714293de3836 553
ashleymills 0:714293de3836 554 /* X = X - Y */
ashleymills 0:714293de3836 555 if (err == MP_OKAY)
ashleymills 0:714293de3836 556 err = mp_sub(&R->x, &R->y, &R->x);
ashleymills 0:714293de3836 557 if (err == MP_OKAY) {
ashleymills 0:714293de3836 558 if (mp_cmp_d(&R->x, 0) == MP_LT)
ashleymills 0:714293de3836 559 err = mp_add(&R->x, modulus, &R->x);
ashleymills 0:714293de3836 560 }
ashleymills 0:714293de3836 561 /* X = X - Y */
ashleymills 0:714293de3836 562 if (err == MP_OKAY)
ashleymills 0:714293de3836 563 err = mp_sub(&R->x, &R->y, &R->x);
ashleymills 0:714293de3836 564 if (err == MP_OKAY) {
ashleymills 0:714293de3836 565 if (mp_cmp_d(&R->x, 0) == MP_LT)
ashleymills 0:714293de3836 566 err = mp_add(&R->x, modulus, &R->x);
ashleymills 0:714293de3836 567 }
ashleymills 0:714293de3836 568 /* Y = Y - X */
ashleymills 0:714293de3836 569 if (err == MP_OKAY)
ashleymills 0:714293de3836 570 err = mp_sub(&R->y, &R->x, &R->y);
ashleymills 0:714293de3836 571 if (err == MP_OKAY) {
ashleymills 0:714293de3836 572 if (mp_cmp_d(&R->y, 0) == MP_LT)
ashleymills 0:714293de3836 573 err = mp_add(&R->y, modulus, &R->y);
ashleymills 0:714293de3836 574 }
ashleymills 0:714293de3836 575 /* Y = Y * T1 */
ashleymills 0:714293de3836 576 if (err == MP_OKAY)
ashleymills 0:714293de3836 577 err = mp_mul(&R->y, &t1, &R->y);
ashleymills 0:714293de3836 578 if (err == MP_OKAY)
ashleymills 0:714293de3836 579 err = mp_montgomery_reduce(&R->y, modulus, *mp);
ashleymills 0:714293de3836 580
ashleymills 0:714293de3836 581 /* Y = Y - T2 */
ashleymills 0:714293de3836 582 if (err == MP_OKAY)
ashleymills 0:714293de3836 583 err = mp_sub(&R->y, &t2, &R->y);
ashleymills 0:714293de3836 584 if (err == MP_OKAY) {
ashleymills 0:714293de3836 585 if (mp_cmp_d(&R->y, 0) == MP_LT)
ashleymills 0:714293de3836 586 err = mp_add(&R->y, modulus, &R->y);
ashleymills 0:714293de3836 587 }
ashleymills 0:714293de3836 588
ashleymills 0:714293de3836 589 /* clean up */
ashleymills 0:714293de3836 590 mp_clear(&t1);
ashleymills 0:714293de3836 591 mp_clear(&t2);
ashleymills 0:714293de3836 592
ashleymills 0:714293de3836 593 return err;
ashleymills 0:714293de3836 594 }
ashleymills 0:714293de3836 595
ashleymills 0:714293de3836 596
ashleymills 0:714293de3836 597 /**
ashleymills 0:714293de3836 598 Map a projective jacbobian point back to affine space
ashleymills 0:714293de3836 599 P [in/out] The point to map
ashleymills 0:714293de3836 600 modulus The modulus of the field the ECC curve is in
ashleymills 0:714293de3836 601 mp The "b" value from montgomery_setup()
ashleymills 0:714293de3836 602 return MP_OKAY on success
ashleymills 0:714293de3836 603 */
ashleymills 0:714293de3836 604 int ecc_map(ecc_point* P, mp_int* modulus, mp_digit* mp)
ashleymills 0:714293de3836 605 {
ashleymills 0:714293de3836 606 mp_int t1;
ashleymills 0:714293de3836 607 mp_int t2;
ashleymills 0:714293de3836 608 int err;
ashleymills 0:714293de3836 609
ashleymills 0:714293de3836 610 if (P == NULL || mp == NULL || modulus == NULL)
ashleymills 0:714293de3836 611 return ECC_BAD_ARG_E;
ashleymills 0:714293de3836 612
ashleymills 0:714293de3836 613 if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) {
ashleymills 0:714293de3836 614 return MEMORY_E;
ashleymills 0:714293de3836 615 }
ashleymills 0:714293de3836 616
ashleymills 0:714293de3836 617 /* first map z back to normal */
ashleymills 0:714293de3836 618 err = mp_montgomery_reduce(&P->z, modulus, *mp);
ashleymills 0:714293de3836 619
ashleymills 0:714293de3836 620 /* get 1/z */
ashleymills 0:714293de3836 621 if (err == MP_OKAY)
ashleymills 0:714293de3836 622 err = mp_invmod(&P->z, modulus, &t1);
ashleymills 0:714293de3836 623
ashleymills 0:714293de3836 624 /* get 1/z^2 and 1/z^3 */
ashleymills 0:714293de3836 625 if (err == MP_OKAY)
ashleymills 0:714293de3836 626 err = mp_sqr(&t1, &t2);
ashleymills 0:714293de3836 627 if (err == MP_OKAY)
ashleymills 0:714293de3836 628 err = mp_mod(&t2, modulus, &t2);
ashleymills 0:714293de3836 629 if (err == MP_OKAY)
ashleymills 0:714293de3836 630 err = mp_mul(&t1, &t2, &t1);
ashleymills 0:714293de3836 631 if (err == MP_OKAY)
ashleymills 0:714293de3836 632 err = mp_mod(&t1, modulus, &t1);
ashleymills 0:714293de3836 633
ashleymills 0:714293de3836 634 /* multiply against x/y */
ashleymills 0:714293de3836 635 if (err == MP_OKAY)
ashleymills 0:714293de3836 636 err = mp_mul(&P->x, &t2, &P->x);
ashleymills 0:714293de3836 637 if (err == MP_OKAY)
ashleymills 0:714293de3836 638 err = mp_montgomery_reduce(&P->x, modulus, *mp);
ashleymills 0:714293de3836 639 if (err == MP_OKAY)
ashleymills 0:714293de3836 640 err = mp_mul(&P->y, &t1, &P->y);
ashleymills 0:714293de3836 641 if (err == MP_OKAY)
ashleymills 0:714293de3836 642 err = mp_montgomery_reduce(&P->y, modulus, *mp);
ashleymills 0:714293de3836 643
ashleymills 0:714293de3836 644 if (err == MP_OKAY)
ashleymills 0:714293de3836 645 mp_set(&P->z, 1);
ashleymills 0:714293de3836 646
ashleymills 0:714293de3836 647 /* clean up */
ashleymills 0:714293de3836 648 mp_clear(&t1);
ashleymills 0:714293de3836 649 mp_clear(&t2);
ashleymills 0:714293de3836 650
ashleymills 0:714293de3836 651 return err;
ashleymills 0:714293de3836 652 }
ashleymills 0:714293de3836 653
ashleymills 0:714293de3836 654
ashleymills 0:714293de3836 655 #ifndef ECC_TIMING_RESISTANT
ashleymills 0:714293de3836 656
ashleymills 0:714293de3836 657 /* size of sliding window, don't change this! */
ashleymills 0:714293de3836 658 #define WINSIZE 4
ashleymills 0:714293de3836 659
ashleymills 0:714293de3836 660 /**
ashleymills 0:714293de3836 661 Perform a point multiplication
ashleymills 0:714293de3836 662 k The scalar to multiply by
ashleymills 0:714293de3836 663 G The base point
ashleymills 0:714293de3836 664 R [out] Destination for kG
ashleymills 0:714293de3836 665 modulus The modulus of the field the ECC curve is in
ashleymills 0:714293de3836 666 map Boolean whether to map back to affine or not
ashleymills 0:714293de3836 667 (1==map, 0 == leave in projective)
ashleymills 0:714293de3836 668 return MP_OKAY on success
ashleymills 0:714293de3836 669 */
ashleymills 0:714293de3836 670 static int ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, mp_int* modulus,
ashleymills 0:714293de3836 671 int map)
ashleymills 0:714293de3836 672 {
ashleymills 0:714293de3836 673 ecc_point *tG, *M[8];
ashleymills 0:714293de3836 674 int i, j, err;
ashleymills 0:714293de3836 675 mp_int mu;
ashleymills 0:714293de3836 676 mp_digit mp;
ashleymills 0:714293de3836 677 unsigned long buf;
ashleymills 0:714293de3836 678 int first, bitbuf, bitcpy, bitcnt, mode, digidx;
ashleymills 0:714293de3836 679
ashleymills 0:714293de3836 680 if (k == NULL || G == NULL || R == NULL || modulus == NULL)
ashleymills 0:714293de3836 681 return ECC_BAD_ARG_E;
ashleymills 0:714293de3836 682
ashleymills 0:714293de3836 683 /* init montgomery reduction */
ashleymills 0:714293de3836 684 if ((err = mp_montgomery_setup(modulus, &mp)) != MP_OKAY) {
ashleymills 0:714293de3836 685 return err;
ashleymills 0:714293de3836 686 }
ashleymills 0:714293de3836 687 if ((err = mp_init(&mu)) != MP_OKAY) {
ashleymills 0:714293de3836 688 return err;
ashleymills 0:714293de3836 689 }
ashleymills 0:714293de3836 690 if ((err = mp_montgomery_calc_normalization(&mu, modulus)) != MP_OKAY) {
ashleymills 0:714293de3836 691 mp_clear(&mu);
ashleymills 0:714293de3836 692 return err;
ashleymills 0:714293de3836 693 }
ashleymills 0:714293de3836 694
ashleymills 0:714293de3836 695 /* alloc ram for window temps */
ashleymills 0:714293de3836 696 for (i = 0; i < 8; i++) {
ashleymills 0:714293de3836 697 M[i] = ecc_new_point();
ashleymills 0:714293de3836 698 if (M[i] == NULL) {
ashleymills 0:714293de3836 699 for (j = 0; j < i; j++) {
ashleymills 0:714293de3836 700 ecc_del_point(M[j]);
ashleymills 0:714293de3836 701 }
ashleymills 0:714293de3836 702 mp_clear(&mu);
ashleymills 0:714293de3836 703 return MEMORY_E;
ashleymills 0:714293de3836 704 }
ashleymills 0:714293de3836 705 }
ashleymills 0:714293de3836 706
ashleymills 0:714293de3836 707 /* make a copy of G incase R==G */
ashleymills 0:714293de3836 708 tG = ecc_new_point();
ashleymills 0:714293de3836 709 if (tG == NULL)
ashleymills 0:714293de3836 710 err = MEMORY_E;
ashleymills 0:714293de3836 711
ashleymills 0:714293de3836 712 /* tG = G and convert to montgomery */
ashleymills 0:714293de3836 713 if (err == MP_OKAY) {
ashleymills 0:714293de3836 714 if (mp_cmp_d(&mu, 1) == MP_EQ) {
ashleymills 0:714293de3836 715 err = mp_copy(&G->x, &tG->x);
ashleymills 0:714293de3836 716 if (err == MP_OKAY)
ashleymills 0:714293de3836 717 err = mp_copy(&G->y, &tG->y);
ashleymills 0:714293de3836 718 if (err == MP_OKAY)
ashleymills 0:714293de3836 719 err = mp_copy(&G->z, &tG->z);
ashleymills 0:714293de3836 720 } else {
ashleymills 0:714293de3836 721 err = mp_mulmod(&G->x, &mu, modulus, &tG->x);
ashleymills 0:714293de3836 722 if (err == MP_OKAY)
ashleymills 0:714293de3836 723 err = mp_mulmod(&G->y, &mu, modulus, &tG->y);
ashleymills 0:714293de3836 724 if (err == MP_OKAY)
ashleymills 0:714293de3836 725 err = mp_mulmod(&G->z, &mu, modulus, &tG->z);
ashleymills 0:714293de3836 726 }
ashleymills 0:714293de3836 727 }
ashleymills 0:714293de3836 728 mp_clear(&mu);
ashleymills 0:714293de3836 729
ashleymills 0:714293de3836 730 /* calc the M tab, which holds kG for k==8..15 */
ashleymills 0:714293de3836 731 /* M[0] == 8G */
ashleymills 0:714293de3836 732 if (err == MP_OKAY)
ashleymills 0:714293de3836 733 err = ecc_projective_dbl_point(tG, M[0], modulus, &mp);
ashleymills 0:714293de3836 734 if (err == MP_OKAY)
ashleymills 0:714293de3836 735 err = ecc_projective_dbl_point(M[0], M[0], modulus, &mp);
ashleymills 0:714293de3836 736 if (err == MP_OKAY)
ashleymills 0:714293de3836 737 err = ecc_projective_dbl_point(M[0], M[0], modulus, &mp);
ashleymills 0:714293de3836 738
ashleymills 0:714293de3836 739 /* now find (8+k)G for k=1..7 */
ashleymills 0:714293de3836 740 if (err == MP_OKAY)
ashleymills 0:714293de3836 741 for (j = 9; j < 16; j++) {
ashleymills 0:714293de3836 742 err = ecc_projective_add_point(M[j-9], tG, M[j-8], modulus, &mp);
ashleymills 0:714293de3836 743 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 744 }
ashleymills 0:714293de3836 745
ashleymills 0:714293de3836 746 /* setup sliding window */
ashleymills 0:714293de3836 747 if (err == MP_OKAY) {
ashleymills 0:714293de3836 748 mode = 0;
ashleymills 0:714293de3836 749 bitcnt = 1;
ashleymills 0:714293de3836 750 buf = 0;
ashleymills 0:714293de3836 751 digidx = get_digit_count(k) - 1;
ashleymills 0:714293de3836 752 bitcpy = bitbuf = 0;
ashleymills 0:714293de3836 753 first = 1;
ashleymills 0:714293de3836 754
ashleymills 0:714293de3836 755 /* perform ops */
ashleymills 0:714293de3836 756 for (;;) {
ashleymills 0:714293de3836 757 /* grab next digit as required */
ashleymills 0:714293de3836 758 if (--bitcnt == 0) {
ashleymills 0:714293de3836 759 if (digidx == -1) {
ashleymills 0:714293de3836 760 break;
ashleymills 0:714293de3836 761 }
ashleymills 0:714293de3836 762 buf = get_digit(k, digidx);
ashleymills 0:714293de3836 763 bitcnt = (int) DIGIT_BIT;
ashleymills 0:714293de3836 764 --digidx;
ashleymills 0:714293de3836 765 }
ashleymills 0:714293de3836 766
ashleymills 0:714293de3836 767 /* grab the next msb from the ltiplicand */
ashleymills 0:714293de3836 768 i = (int)(buf >> (DIGIT_BIT - 1)) & 1;
ashleymills 0:714293de3836 769 buf <<= 1;
ashleymills 0:714293de3836 770
ashleymills 0:714293de3836 771 /* skip leading zero bits */
ashleymills 0:714293de3836 772 if (mode == 0 && i == 0)
ashleymills 0:714293de3836 773 continue;
ashleymills 0:714293de3836 774
ashleymills 0:714293de3836 775 /* if the bit is zero and mode == 1 then we double */
ashleymills 0:714293de3836 776 if (mode == 1 && i == 0) {
ashleymills 0:714293de3836 777 err = ecc_projective_dbl_point(R, R, modulus, &mp);
ashleymills 0:714293de3836 778 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 779 continue;
ashleymills 0:714293de3836 780 }
ashleymills 0:714293de3836 781
ashleymills 0:714293de3836 782 /* else we add it to the window */
ashleymills 0:714293de3836 783 bitbuf |= (i << (WINSIZE - ++bitcpy));
ashleymills 0:714293de3836 784 mode = 2;
ashleymills 0:714293de3836 785
ashleymills 0:714293de3836 786 if (bitcpy == WINSIZE) {
ashleymills 0:714293de3836 787 /* if this is the first window we do a simple copy */
ashleymills 0:714293de3836 788 if (first == 1) {
ashleymills 0:714293de3836 789 /* R = kG [k = first window] */
ashleymills 0:714293de3836 790 err = mp_copy(&M[bitbuf-8]->x, &R->x);
ashleymills 0:714293de3836 791 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 792
ashleymills 0:714293de3836 793 err = mp_copy(&M[bitbuf-8]->y, &R->y);
ashleymills 0:714293de3836 794 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 795
ashleymills 0:714293de3836 796 err = mp_copy(&M[bitbuf-8]->z, &R->z);
ashleymills 0:714293de3836 797 first = 0;
ashleymills 0:714293de3836 798 } else {
ashleymills 0:714293de3836 799 /* normal window */
ashleymills 0:714293de3836 800 /* ok window is filled so double as required and add */
ashleymills 0:714293de3836 801 /* double first */
ashleymills 0:714293de3836 802 for (j = 0; j < WINSIZE; j++) {
ashleymills 0:714293de3836 803 err = ecc_projective_dbl_point(R, R, modulus, &mp);
ashleymills 0:714293de3836 804 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 805 }
ashleymills 0:714293de3836 806 if (err != MP_OKAY) break; /* out of first for(;;) */
ashleymills 0:714293de3836 807
ashleymills 0:714293de3836 808 /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranted */
ashleymills 0:714293de3836 809 err = ecc_projective_add_point(R,M[bitbuf-8],R,modulus,&mp);
ashleymills 0:714293de3836 810 }
ashleymills 0:714293de3836 811 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 812 /* empty window and reset */
ashleymills 0:714293de3836 813 bitcpy = bitbuf = 0;
ashleymills 0:714293de3836 814 mode = 1;
ashleymills 0:714293de3836 815 }
ashleymills 0:714293de3836 816 }
ashleymills 0:714293de3836 817 }
ashleymills 0:714293de3836 818
ashleymills 0:714293de3836 819 /* if bits remain then double/add */
ashleymills 0:714293de3836 820 if (err == MP_OKAY) {
ashleymills 0:714293de3836 821 if (mode == 2 && bitcpy > 0) {
ashleymills 0:714293de3836 822 /* double then add */
ashleymills 0:714293de3836 823 for (j = 0; j < bitcpy; j++) {
ashleymills 0:714293de3836 824 /* only double if we have had at least one add first */
ashleymills 0:714293de3836 825 if (first == 0) {
ashleymills 0:714293de3836 826 err = ecc_projective_dbl_point(R, R, modulus, &mp);
ashleymills 0:714293de3836 827 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 828 }
ashleymills 0:714293de3836 829
ashleymills 0:714293de3836 830 bitbuf <<= 1;
ashleymills 0:714293de3836 831 if ((bitbuf & (1 << WINSIZE)) != 0) {
ashleymills 0:714293de3836 832 if (first == 1) {
ashleymills 0:714293de3836 833 /* first add, so copy */
ashleymills 0:714293de3836 834 err = mp_copy(&tG->x, &R->x);
ashleymills 0:714293de3836 835 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 836
ashleymills 0:714293de3836 837 err = mp_copy(&tG->y, &R->y);
ashleymills 0:714293de3836 838 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 839
ashleymills 0:714293de3836 840 err = mp_copy(&tG->z, &R->z);
ashleymills 0:714293de3836 841 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 842 first = 0;
ashleymills 0:714293de3836 843 } else {
ashleymills 0:714293de3836 844 /* then add */
ashleymills 0:714293de3836 845 err = ecc_projective_add_point(R, tG, R, modulus, &mp);
ashleymills 0:714293de3836 846 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 847 }
ashleymills 0:714293de3836 848 }
ashleymills 0:714293de3836 849 }
ashleymills 0:714293de3836 850 }
ashleymills 0:714293de3836 851 }
ashleymills 0:714293de3836 852
ashleymills 0:714293de3836 853 /* map R back from projective space */
ashleymills 0:714293de3836 854 if (err == MP_OKAY && map)
ashleymills 0:714293de3836 855 err = ecc_map(R, modulus, &mp);
ashleymills 0:714293de3836 856
ashleymills 0:714293de3836 857 mp_clear(&mu);
ashleymills 0:714293de3836 858 ecc_del_point(tG);
ashleymills 0:714293de3836 859 for (i = 0; i < 8; i++) {
ashleymills 0:714293de3836 860 ecc_del_point(M[i]);
ashleymills 0:714293de3836 861 }
ashleymills 0:714293de3836 862 return err;
ashleymills 0:714293de3836 863 }
ashleymills 0:714293de3836 864
ashleymills 0:714293de3836 865 #undef WINSIZE
ashleymills 0:714293de3836 866 #endif /* ECC_TIMING_RESISTANT */
ashleymills 0:714293de3836 867
ashleymills 0:714293de3836 868
ashleymills 0:714293de3836 869 /**
ashleymills 0:714293de3836 870 Allocate a new ECC point
ashleymills 0:714293de3836 871 return A newly allocated point or NULL on error
ashleymills 0:714293de3836 872 */
ashleymills 0:714293de3836 873 ecc_point* ecc_new_point(void)
ashleymills 0:714293de3836 874 {
ashleymills 0:714293de3836 875 ecc_point* p;
ashleymills 0:714293de3836 876 p = (ecc_point*)XMALLOC(sizeof(ecc_point), 0, DYNAMIC_TYPE_BIGINT);
ashleymills 0:714293de3836 877 if (p == NULL) {
ashleymills 0:714293de3836 878 return NULL;
ashleymills 0:714293de3836 879 }
ashleymills 0:714293de3836 880 XMEMSET(p, 0, sizeof(ecc_point));
ashleymills 0:714293de3836 881 if (mp_init_multi(&p->x, &p->y, &p->z, NULL, NULL, NULL) != MP_OKAY) {
ashleymills 0:714293de3836 882 XFREE(p, 0, DYNAMIC_TYPE_BIGINT);
ashleymills 0:714293de3836 883 return NULL;
ashleymills 0:714293de3836 884 }
ashleymills 0:714293de3836 885 return p;
ashleymills 0:714293de3836 886 }
ashleymills 0:714293de3836 887
ashleymills 0:714293de3836 888 /** Free an ECC point from memory
ashleymills 0:714293de3836 889 p The point to free
ashleymills 0:714293de3836 890 */
ashleymills 0:714293de3836 891 void ecc_del_point(ecc_point* p)
ashleymills 0:714293de3836 892 {
ashleymills 0:714293de3836 893 /* prevents free'ing null arguments */
ashleymills 0:714293de3836 894 if (p != NULL) {
ashleymills 0:714293de3836 895 mp_clear(&p->x);
ashleymills 0:714293de3836 896 mp_clear(&p->y);
ashleymills 0:714293de3836 897 mp_clear(&p->z);
ashleymills 0:714293de3836 898 XFREE(p, 0, DYNAMIC_TYPE_BIGINT);
ashleymills 0:714293de3836 899 }
ashleymills 0:714293de3836 900 }
ashleymills 0:714293de3836 901
ashleymills 0:714293de3836 902
ashleymills 0:714293de3836 903 /** Returns whether an ECC idx is valid or not
ashleymills 0:714293de3836 904 n The idx number to check
ashleymills 0:714293de3836 905 return 1 if valid, 0 if not
ashleymills 0:714293de3836 906 */
ashleymills 0:714293de3836 907 static int ecc_is_valid_idx(int n)
ashleymills 0:714293de3836 908 {
ashleymills 0:714293de3836 909 int x;
ashleymills 0:714293de3836 910
ashleymills 0:714293de3836 911 for (x = 0; ecc_sets[x].size != 0; x++)
ashleymills 0:714293de3836 912 ;
ashleymills 0:714293de3836 913 /* -1 is a valid index --- indicating that the domain params
ashleymills 0:714293de3836 914 were supplied by the user */
ashleymills 0:714293de3836 915 if ((n >= -1) && (n < x)) {
ashleymills 0:714293de3836 916 return 1;
ashleymills 0:714293de3836 917 }
ashleymills 0:714293de3836 918 return 0;
ashleymills 0:714293de3836 919 }
ashleymills 0:714293de3836 920
ashleymills 0:714293de3836 921
ashleymills 0:714293de3836 922 /**
ashleymills 0:714293de3836 923 Create an ECC shared secret between two keys
ashleymills 0:714293de3836 924 private_key The private ECC key
ashleymills 0:714293de3836 925 public_key The public key
ashleymills 0:714293de3836 926 out [out] Destination of the shared secret
ashleymills 0:714293de3836 927 Conforms to EC-DH from ANSI X9.63
ashleymills 0:714293de3836 928 outlen [in/out] The max size and resulting size of the shared secret
ashleymills 0:714293de3836 929 return MP_OKAY if successful
ashleymills 0:714293de3836 930 */
ashleymills 0:714293de3836 931 int ecc_shared_secret(ecc_key* private_key, ecc_key* public_key, byte* out,
ashleymills 0:714293de3836 932 word32* outlen)
ashleymills 0:714293de3836 933 {
ashleymills 0:714293de3836 934 word32 x = 0;
ashleymills 0:714293de3836 935 ecc_point* result;
ashleymills 0:714293de3836 936 mp_int prime;
ashleymills 0:714293de3836 937 int err;
ashleymills 0:714293de3836 938
ashleymills 0:714293de3836 939 if (private_key == NULL || public_key == NULL || out == NULL ||
ashleymills 0:714293de3836 940 outlen == NULL)
ashleymills 0:714293de3836 941 return BAD_FUNC_ARG;
ashleymills 0:714293de3836 942
ashleymills 0:714293de3836 943 /* type valid? */
ashleymills 0:714293de3836 944 if (private_key->type != ECC_PRIVATEKEY) {
ashleymills 0:714293de3836 945 return ECC_BAD_ARG_E;
ashleymills 0:714293de3836 946 }
ashleymills 0:714293de3836 947
ashleymills 0:714293de3836 948 if (ecc_is_valid_idx(private_key->idx) == 0 ||
ashleymills 0:714293de3836 949 ecc_is_valid_idx(public_key->idx) == 0)
ashleymills 0:714293de3836 950 return ECC_BAD_ARG_E;
ashleymills 0:714293de3836 951
ashleymills 0:714293de3836 952 if (XSTRNCMP(private_key->dp->name, public_key->dp->name, ECC_MAXNAME) != 0)
ashleymills 0:714293de3836 953 return ECC_BAD_ARG_E;
ashleymills 0:714293de3836 954
ashleymills 0:714293de3836 955 /* make new point */
ashleymills 0:714293de3836 956 result = ecc_new_point();
ashleymills 0:714293de3836 957 if (result == NULL) {
ashleymills 0:714293de3836 958 return MEMORY_E;
ashleymills 0:714293de3836 959 }
ashleymills 0:714293de3836 960
ashleymills 0:714293de3836 961 if ((err = mp_init(&prime)) != MP_OKAY) {
ashleymills 0:714293de3836 962 ecc_del_point(result);
ashleymills 0:714293de3836 963 return err;
ashleymills 0:714293de3836 964 }
ashleymills 0:714293de3836 965
ashleymills 0:714293de3836 966 err = mp_read_radix(&prime, (char *)private_key->dp->prime, 16);
ashleymills 0:714293de3836 967
ashleymills 0:714293de3836 968 if (err == MP_OKAY)
ashleymills 0:714293de3836 969 err = ecc_mulmod(&private_key->k, &public_key->pubkey, result, &prime,1);
ashleymills 0:714293de3836 970
ashleymills 0:714293de3836 971 if (err == MP_OKAY) {
ashleymills 0:714293de3836 972 x = mp_unsigned_bin_size(&prime);
ashleymills 0:714293de3836 973 if (*outlen < x)
ashleymills 0:714293de3836 974 err = BUFFER_E;
ashleymills 0:714293de3836 975 }
ashleymills 0:714293de3836 976
ashleymills 0:714293de3836 977 if (err == MP_OKAY) {
ashleymills 0:714293de3836 978 XMEMSET(out, 0, x);
ashleymills 0:714293de3836 979 err = mp_to_unsigned_bin(&result->x,out + (x -
ashleymills 0:714293de3836 980 mp_unsigned_bin_size(&result->x)));
ashleymills 0:714293de3836 981 *outlen = x;
ashleymills 0:714293de3836 982 }
ashleymills 0:714293de3836 983
ashleymills 0:714293de3836 984 mp_clear(&prime);
ashleymills 0:714293de3836 985 ecc_del_point(result);
ashleymills 0:714293de3836 986
ashleymills 0:714293de3836 987 return err;
ashleymills 0:714293de3836 988 }
ashleymills 0:714293de3836 989
ashleymills 0:714293de3836 990
ashleymills 0:714293de3836 991 int ecc_make_key_ex(RNG* rng, ecc_key* key, const ecc_set_type* dp);
ashleymills 0:714293de3836 992
ashleymills 0:714293de3836 993 /**
ashleymills 0:714293de3836 994 Make a new ECC key
ashleymills 0:714293de3836 995 rng An active RNG state
ashleymills 0:714293de3836 996 keysize The keysize for the new key (in octets from 20 to 65 bytes)
ashleymills 0:714293de3836 997 key [out] Destination of the newly created key
ashleymills 0:714293de3836 998 return MP_OKAY if successful,
ashleymills 0:714293de3836 999 upon error all allocated memory will be freed
ashleymills 0:714293de3836 1000 */
ashleymills 0:714293de3836 1001 int ecc_make_key(RNG* rng, int keysize, ecc_key* key)
ashleymills 0:714293de3836 1002 {
ashleymills 0:714293de3836 1003 int x, err;
ashleymills 0:714293de3836 1004
ashleymills 0:714293de3836 1005 /* find key size */
ashleymills 0:714293de3836 1006 for (x = 0; (keysize > ecc_sets[x].size) && (ecc_sets[x].size != 0); x++)
ashleymills 0:714293de3836 1007 ;
ashleymills 0:714293de3836 1008 keysize = ecc_sets[x].size;
ashleymills 0:714293de3836 1009
ashleymills 0:714293de3836 1010 if (keysize > ECC_MAXSIZE || ecc_sets[x].size == 0) {
ashleymills 0:714293de3836 1011 return BAD_FUNC_ARG;
ashleymills 0:714293de3836 1012 }
ashleymills 0:714293de3836 1013 err = ecc_make_key_ex(rng, key, &ecc_sets[x]);
ashleymills 0:714293de3836 1014 key->idx = x;
ashleymills 0:714293de3836 1015
ashleymills 0:714293de3836 1016 return err;
ashleymills 0:714293de3836 1017 }
ashleymills 0:714293de3836 1018
ashleymills 0:714293de3836 1019 int ecc_make_key_ex(RNG* rng, ecc_key* key, const ecc_set_type* dp)
ashleymills 0:714293de3836 1020 {
ashleymills 0:714293de3836 1021 int err;
ashleymills 0:714293de3836 1022 ecc_point* base;
ashleymills 0:714293de3836 1023 mp_int prime;
ashleymills 0:714293de3836 1024 mp_int order;
ashleymills 0:714293de3836 1025 byte buf[ECC_MAXSIZE];
ashleymills 0:714293de3836 1026 int keysize;
ashleymills 0:714293de3836 1027
ashleymills 0:714293de3836 1028 if (key == NULL || rng == NULL || dp == NULL)
ashleymills 0:714293de3836 1029 return ECC_BAD_ARG_E;
ashleymills 0:714293de3836 1030
ashleymills 0:714293de3836 1031 key->idx = -1;
ashleymills 0:714293de3836 1032 key->dp = dp;
ashleymills 0:714293de3836 1033 keysize = dp->size;
ashleymills 0:714293de3836 1034
ashleymills 0:714293de3836 1035 /* allocate ram */
ashleymills 0:714293de3836 1036 base = NULL;
ashleymills 0:714293de3836 1037
ashleymills 0:714293de3836 1038 /* make up random string */
ashleymills 0:714293de3836 1039 RNG_GenerateBlock(rng, buf, keysize);
ashleymills 0:714293de3836 1040 buf[0] |= 0x0c;
ashleymills 0:714293de3836 1041
ashleymills 0:714293de3836 1042 /* setup the key variables */
ashleymills 0:714293de3836 1043 if ((err = mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z,
ashleymills 0:714293de3836 1044 &key->k, &prime, &order)) != MP_OKAY)
ashleymills 0:714293de3836 1045 return MEMORY_E;
ashleymills 0:714293de3836 1046
ashleymills 0:714293de3836 1047 base = ecc_new_point();
ashleymills 0:714293de3836 1048 if (base == NULL)
ashleymills 0:714293de3836 1049 err = MEMORY_E;
ashleymills 0:714293de3836 1050
ashleymills 0:714293de3836 1051 /* read in the specs for this key */
ashleymills 0:714293de3836 1052 if (err == MP_OKAY)
ashleymills 0:714293de3836 1053 err = mp_read_radix(&prime, (char *)key->dp->prime, 16);
ashleymills 0:714293de3836 1054 if (err == MP_OKAY)
ashleymills 0:714293de3836 1055 err = mp_read_radix(&order, (char *)key->dp->order, 16);
ashleymills 0:714293de3836 1056 if (err == MP_OKAY)
ashleymills 0:714293de3836 1057 err = mp_read_radix(&base->x, (char *)key->dp->Gx, 16);
ashleymills 0:714293de3836 1058 if (err == MP_OKAY)
ashleymills 0:714293de3836 1059 err = mp_read_radix(&base->y, (char *)key->dp->Gy, 16);
ashleymills 0:714293de3836 1060
ashleymills 0:714293de3836 1061 if (err == MP_OKAY)
ashleymills 0:714293de3836 1062 mp_set(&base->z, 1);
ashleymills 0:714293de3836 1063 if (err == MP_OKAY)
ashleymills 0:714293de3836 1064 err = mp_read_unsigned_bin(&key->k, (byte*)buf, keysize);
ashleymills 0:714293de3836 1065
ashleymills 0:714293de3836 1066 /* the key should be smaller than the order of base point */
ashleymills 0:714293de3836 1067 if (err == MP_OKAY) {
ashleymills 0:714293de3836 1068 if (mp_cmp(&key->k, &order) != MP_LT)
ashleymills 0:714293de3836 1069 err = mp_mod(&key->k, &order, &key->k);
ashleymills 0:714293de3836 1070 }
ashleymills 0:714293de3836 1071 /* make the public key */
ashleymills 0:714293de3836 1072 if (err == MP_OKAY)
ashleymills 0:714293de3836 1073 err = ecc_mulmod(&key->k, base, &key->pubkey, &prime, 1);
ashleymills 0:714293de3836 1074 if (err == MP_OKAY)
ashleymills 0:714293de3836 1075 key->type = ECC_PRIVATEKEY;
ashleymills 0:714293de3836 1076
ashleymills 0:714293de3836 1077 if (err != MP_OKAY) {
ashleymills 0:714293de3836 1078 /* clean up */
ashleymills 0:714293de3836 1079 mp_clear(&key->pubkey.x);
ashleymills 0:714293de3836 1080 mp_clear(&key->pubkey.y);
ashleymills 0:714293de3836 1081 mp_clear(&key->pubkey.z);
ashleymills 0:714293de3836 1082 mp_clear(&key->k);
ashleymills 0:714293de3836 1083 }
ashleymills 0:714293de3836 1084 ecc_del_point(base);
ashleymills 0:714293de3836 1085 mp_clear(&prime);
ashleymills 0:714293de3836 1086 mp_clear(&order);
ashleymills 0:714293de3836 1087 #ifdef ECC_CLEAN_STACK
ashleymills 0:714293de3836 1088 XMEMSET(buff, 0, ECC_MAXSIZE);
ashleymills 0:714293de3836 1089 #endif
ashleymills 0:714293de3836 1090 return err;
ashleymills 0:714293de3836 1091 }
ashleymills 0:714293de3836 1092
ashleymills 0:714293de3836 1093
ashleymills 0:714293de3836 1094 /* Setup dynamic pointers is using normal math for proper freeing */
ashleymills 0:714293de3836 1095 void ecc_init(ecc_key* key)
ashleymills 0:714293de3836 1096 {
ashleymills 0:714293de3836 1097 (void)key;
ashleymills 0:714293de3836 1098 #ifndef USE_FAST_MATH
ashleymills 0:714293de3836 1099 key->pubkey.x.dp = NULL;
ashleymills 0:714293de3836 1100 key->pubkey.y.dp = NULL;
ashleymills 0:714293de3836 1101 key->pubkey.z.dp = NULL;
ashleymills 0:714293de3836 1102
ashleymills 0:714293de3836 1103 key->k.dp = NULL;
ashleymills 0:714293de3836 1104 #endif
ashleymills 0:714293de3836 1105 }
ashleymills 0:714293de3836 1106
ashleymills 0:714293de3836 1107
ashleymills 0:714293de3836 1108 /**
ashleymills 0:714293de3836 1109 Sign a message digest
ashleymills 0:714293de3836 1110 in The message digest to sign
ashleymills 0:714293de3836 1111 inlen The length of the digest
ashleymills 0:714293de3836 1112 out [out] The destination for the signature
ashleymills 0:714293de3836 1113 outlen [in/out] The max size and resulting size of the signature
ashleymills 0:714293de3836 1114 key A private ECC key
ashleymills 0:714293de3836 1115 return MP_OKAY if successful
ashleymills 0:714293de3836 1116 */
ashleymills 0:714293de3836 1117 int ecc_sign_hash(const byte* in, word32 inlen, byte* out, word32 *outlen,
ashleymills 0:714293de3836 1118 RNG* rng, ecc_key* key)
ashleymills 0:714293de3836 1119 {
ashleymills 0:714293de3836 1120 mp_int r;
ashleymills 0:714293de3836 1121 mp_int s;
ashleymills 0:714293de3836 1122 mp_int e;
ashleymills 0:714293de3836 1123 mp_int p;
ashleymills 0:714293de3836 1124 int err;
ashleymills 0:714293de3836 1125
ashleymills 0:714293de3836 1126 if (in == NULL || out == NULL || outlen == NULL || key == NULL || rng ==NULL)
ashleymills 0:714293de3836 1127 return ECC_BAD_ARG_E;
ashleymills 0:714293de3836 1128
ashleymills 0:714293de3836 1129 /* is this a private key? */
ashleymills 0:714293de3836 1130 if (key->type != ECC_PRIVATEKEY) {
ashleymills 0:714293de3836 1131 return ECC_BAD_ARG_E;
ashleymills 0:714293de3836 1132 }
ashleymills 0:714293de3836 1133
ashleymills 0:714293de3836 1134 /* is the IDX valid ? */
ashleymills 0:714293de3836 1135 if (ecc_is_valid_idx(key->idx) != 1) {
ashleymills 0:714293de3836 1136 return ECC_BAD_ARG_E;
ashleymills 0:714293de3836 1137 }
ashleymills 0:714293de3836 1138
ashleymills 0:714293de3836 1139 /* get the hash and load it as a bignum into 'e' */
ashleymills 0:714293de3836 1140 /* init the bignums */
ashleymills 0:714293de3836 1141 if ((err = mp_init_multi(&r, &s, &p, &e, NULL, NULL)) != MP_OKAY) {
ashleymills 0:714293de3836 1142 return err;
ashleymills 0:714293de3836 1143 }
ashleymills 0:714293de3836 1144 err = mp_read_radix(&p, (char *)key->dp->order, 16);
ashleymills 0:714293de3836 1145
ashleymills 0:714293de3836 1146 if (err == MP_OKAY) {
ashleymills 0:714293de3836 1147 int truncLen = (int)inlen;
ashleymills 0:714293de3836 1148 if (truncLen > ecc_size(key))
ashleymills 0:714293de3836 1149 truncLen = ecc_size(key);
ashleymills 0:714293de3836 1150 err = mp_read_unsigned_bin(&e, (byte*)in, truncLen);
ashleymills 0:714293de3836 1151 }
ashleymills 0:714293de3836 1152
ashleymills 0:714293de3836 1153 /* make up a key and export the public copy */
ashleymills 0:714293de3836 1154 if (err == MP_OKAY) {
ashleymills 0:714293de3836 1155 ecc_key pubkey;
ashleymills 0:714293de3836 1156 ecc_init(&pubkey);
ashleymills 0:714293de3836 1157 for (;;) {
ashleymills 0:714293de3836 1158 err = ecc_make_key_ex(rng, &pubkey, key->dp);
ashleymills 0:714293de3836 1159 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 1160
ashleymills 0:714293de3836 1161 /* find r = x1 mod n */
ashleymills 0:714293de3836 1162 err = mp_mod(&pubkey.pubkey.x, &p, &r);
ashleymills 0:714293de3836 1163 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 1164
ashleymills 0:714293de3836 1165 if (mp_iszero(&r) == MP_YES)
ashleymills 0:714293de3836 1166 ecc_free(&pubkey);
ashleymills 0:714293de3836 1167 else {
ashleymills 0:714293de3836 1168 /* find s = (e + xr)/k */
ashleymills 0:714293de3836 1169 err = mp_invmod(&pubkey.k, &p, &pubkey.k);
ashleymills 0:714293de3836 1170 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 1171
ashleymills 0:714293de3836 1172 err = mp_mulmod(&key->k, &r, &p, &s); /* s = xr */
ashleymills 0:714293de3836 1173 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 1174
ashleymills 0:714293de3836 1175 err = mp_add(&e, &s, &s); /* s = e + xr */
ashleymills 0:714293de3836 1176 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 1177
ashleymills 0:714293de3836 1178 err = mp_mod(&s, &p, &s); /* s = e + xr */
ashleymills 0:714293de3836 1179 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 1180
ashleymills 0:714293de3836 1181 err = mp_mulmod(&s, &pubkey.k, &p, &s); /* s = (e + xr)/k */
ashleymills 0:714293de3836 1182 if (err != MP_OKAY) break;
ashleymills 0:714293de3836 1183
ashleymills 0:714293de3836 1184 ecc_free(&pubkey);
ashleymills 0:714293de3836 1185 if (mp_iszero(&s) == MP_NO)
ashleymills 0:714293de3836 1186 break;
ashleymills 0:714293de3836 1187 }
ashleymills 0:714293de3836 1188 }
ashleymills 0:714293de3836 1189 ecc_free(&pubkey);
ashleymills 0:714293de3836 1190 }
ashleymills 0:714293de3836 1191
ashleymills 0:714293de3836 1192 /* store as SEQUENCE { r, s -- integer } */
ashleymills 0:714293de3836 1193 if (err == MP_OKAY)
ashleymills 0:714293de3836 1194 err = StoreECC_DSA_Sig(out, outlen, &r, &s);
ashleymills 0:714293de3836 1195
ashleymills 0:714293de3836 1196 mp_clear(&r);
ashleymills 0:714293de3836 1197 mp_clear(&s);
ashleymills 0:714293de3836 1198 mp_clear(&p);
ashleymills 0:714293de3836 1199 mp_clear(&e);
ashleymills 0:714293de3836 1200
ashleymills 0:714293de3836 1201 return err;
ashleymills 0:714293de3836 1202 }
ashleymills 0:714293de3836 1203
ashleymills 0:714293de3836 1204
ashleymills 0:714293de3836 1205 /**
ashleymills 0:714293de3836 1206 Free an ECC key from memory
ashleymills 0:714293de3836 1207 key The key you wish to free
ashleymills 0:714293de3836 1208 */
ashleymills 0:714293de3836 1209 void ecc_free(ecc_key* key)
ashleymills 0:714293de3836 1210 {
ashleymills 0:714293de3836 1211 if (key == NULL)
ashleymills 0:714293de3836 1212 return;
ashleymills 0:714293de3836 1213
ashleymills 0:714293de3836 1214 mp_clear(&key->pubkey.x);
ashleymills 0:714293de3836 1215 mp_clear(&key->pubkey.y);
ashleymills 0:714293de3836 1216 mp_clear(&key->pubkey.z);
ashleymills 0:714293de3836 1217 mp_clear(&key->k);
ashleymills 0:714293de3836 1218 }
ashleymills 0:714293de3836 1219
ashleymills 0:714293de3836 1220
ashleymills 0:714293de3836 1221 /* verify
ashleymills 0:714293de3836 1222 *
ashleymills 0:714293de3836 1223 * w = s^-1 mod n
ashleymills 0:714293de3836 1224 * u1 = xw
ashleymills 0:714293de3836 1225 * u2 = rw
ashleymills 0:714293de3836 1226 * X = u1*G + u2*Q
ashleymills 0:714293de3836 1227 * v = X_x1 mod n
ashleymills 0:714293de3836 1228 * accept if v == r
ashleymills 0:714293de3836 1229 */
ashleymills 0:714293de3836 1230
ashleymills 0:714293de3836 1231 /**
ashleymills 0:714293de3836 1232 Verify an ECC signature
ashleymills 0:714293de3836 1233 sig The signature to verify
ashleymills 0:714293de3836 1234 siglen The length of the signature (octets)
ashleymills 0:714293de3836 1235 hash The hash (message digest) that was signed
ashleymills 0:714293de3836 1236 hashlen The length of the hash (octets)
ashleymills 0:714293de3836 1237 stat Result of signature, 1==valid, 0==invalid
ashleymills 0:714293de3836 1238 key The corresponding public ECC key
ashleymills 0:714293de3836 1239 return MP_OKAY if successful (even if the signature is not valid)
ashleymills 0:714293de3836 1240 */
ashleymills 0:714293de3836 1241 int ecc_verify_hash(const byte* sig, word32 siglen, byte* hash, word32 hashlen,
ashleymills 0:714293de3836 1242 int* stat, ecc_key* key)
ashleymills 0:714293de3836 1243 {
ashleymills 0:714293de3836 1244 ecc_point *mG, *mQ;
ashleymills 0:714293de3836 1245 mp_int r;
ashleymills 0:714293de3836 1246 mp_int s;
ashleymills 0:714293de3836 1247 mp_int v;
ashleymills 0:714293de3836 1248 mp_int w;
ashleymills 0:714293de3836 1249 mp_int u1;
ashleymills 0:714293de3836 1250 mp_int u2;
ashleymills 0:714293de3836 1251 mp_int e;
ashleymills 0:714293de3836 1252 mp_int p;
ashleymills 0:714293de3836 1253 mp_int m;
ashleymills 0:714293de3836 1254 mp_digit mp;
ashleymills 0:714293de3836 1255 int err;
ashleymills 0:714293de3836 1256
ashleymills 0:714293de3836 1257 if (sig == NULL || hash == NULL || stat == NULL || key == NULL)
ashleymills 0:714293de3836 1258 return ECC_BAD_ARG_E;
ashleymills 0:714293de3836 1259
ashleymills 0:714293de3836 1260 /* default to invalid signature */
ashleymills 0:714293de3836 1261 *stat = 0;
ashleymills 0:714293de3836 1262
ashleymills 0:714293de3836 1263 /* is the IDX valid ? */
ashleymills 0:714293de3836 1264 if (ecc_is_valid_idx(key->idx) != 1) {
ashleymills 0:714293de3836 1265 return ECC_BAD_ARG_E;
ashleymills 0:714293de3836 1266 }
ashleymills 0:714293de3836 1267
ashleymills 0:714293de3836 1268 /* allocate ints */
ashleymills 0:714293de3836 1269 if ((err = mp_init_multi(&v, &w, &u1, &u2, &p, &e)) != MP_OKAY) {
ashleymills 0:714293de3836 1270 return MEMORY_E;
ashleymills 0:714293de3836 1271 }
ashleymills 0:714293de3836 1272
ashleymills 0:714293de3836 1273 if ((err = mp_init(&m)) != MP_OKAY) {
ashleymills 0:714293de3836 1274 mp_clear(&v);
ashleymills 0:714293de3836 1275 mp_clear(&w);
ashleymills 0:714293de3836 1276 mp_clear(&u1);
ashleymills 0:714293de3836 1277 mp_clear(&u2);
ashleymills 0:714293de3836 1278 mp_clear(&p);
ashleymills 0:714293de3836 1279 mp_clear(&e);
ashleymills 0:714293de3836 1280 return MEMORY_E;
ashleymills 0:714293de3836 1281 }
ashleymills 0:714293de3836 1282
ashleymills 0:714293de3836 1283 /* allocate points */
ashleymills 0:714293de3836 1284 mG = ecc_new_point();
ashleymills 0:714293de3836 1285 mQ = ecc_new_point();
ashleymills 0:714293de3836 1286 if (mQ == NULL || mG == NULL)
ashleymills 0:714293de3836 1287 err = MEMORY_E;
ashleymills 0:714293de3836 1288
ashleymills 0:714293de3836 1289 /* Note, DecodeECC_DSA_Sig() calls mp_init() on r and s.
ashleymills 0:714293de3836 1290 * If either of those don't allocate correctly, none of
ashleymills 0:714293de3836 1291 * the rest of this function will execute, and everything
ashleymills 0:714293de3836 1292 * gets cleaned up at the end. */
ashleymills 0:714293de3836 1293 XMEMSET(&r, 0, sizeof(r));
ashleymills 0:714293de3836 1294 XMEMSET(&s, 0, sizeof(s));
ashleymills 0:714293de3836 1295 if (err == MP_OKAY)
ashleymills 0:714293de3836 1296 err = DecodeECC_DSA_Sig(sig, siglen, &r, &s);
ashleymills 0:714293de3836 1297
ashleymills 0:714293de3836 1298 /* get the order */
ashleymills 0:714293de3836 1299 if (err == MP_OKAY)
ashleymills 0:714293de3836 1300 err = mp_read_radix(&p, (char *)key->dp->order, 16);
ashleymills 0:714293de3836 1301
ashleymills 0:714293de3836 1302 /* get the modulus */
ashleymills 0:714293de3836 1303 if (err == MP_OKAY)
ashleymills 0:714293de3836 1304 err = mp_read_radix(&m, (char *)key->dp->prime, 16);
ashleymills 0:714293de3836 1305
ashleymills 0:714293de3836 1306 /* check for zero */
ashleymills 0:714293de3836 1307 if (err == MP_OKAY) {
ashleymills 0:714293de3836 1308 if (mp_iszero(&r) || mp_iszero(&s) || mp_cmp(&r, &p) != MP_LT ||
ashleymills 0:714293de3836 1309 mp_cmp(&s, &p) != MP_LT)
ashleymills 0:714293de3836 1310 err = MP_ZERO_E;
ashleymills 0:714293de3836 1311 }
ashleymills 0:714293de3836 1312 /* read hash */
ashleymills 0:714293de3836 1313 if (err == MP_OKAY) {
ashleymills 0:714293de3836 1314 int truncLen = (int)hashlen;
ashleymills 0:714293de3836 1315 if (truncLen > ecc_size(key))
ashleymills 0:714293de3836 1316 truncLen = ecc_size(key);
ashleymills 0:714293de3836 1317 err = mp_read_unsigned_bin(&e, (byte*)hash, truncLen);
ashleymills 0:714293de3836 1318 }
ashleymills 0:714293de3836 1319
ashleymills 0:714293de3836 1320 /* w = s^-1 mod n */
ashleymills 0:714293de3836 1321 if (err == MP_OKAY)
ashleymills 0:714293de3836 1322 err = mp_invmod(&s, &p, &w);
ashleymills 0:714293de3836 1323
ashleymills 0:714293de3836 1324 /* u1 = ew */
ashleymills 0:714293de3836 1325 if (err == MP_OKAY)
ashleymills 0:714293de3836 1326 err = mp_mulmod(&e, &w, &p, &u1);
ashleymills 0:714293de3836 1327
ashleymills 0:714293de3836 1328 /* u2 = rw */
ashleymills 0:714293de3836 1329 if (err == MP_OKAY)
ashleymills 0:714293de3836 1330 err = mp_mulmod(&r, &w, &p, &u2);
ashleymills 0:714293de3836 1331
ashleymills 0:714293de3836 1332 /* find mG and mQ */
ashleymills 0:714293de3836 1333 if (err == MP_OKAY)
ashleymills 0:714293de3836 1334 err = mp_read_radix(&mG->x, (char *)key->dp->Gx, 16);
ashleymills 0:714293de3836 1335
ashleymills 0:714293de3836 1336 if (err == MP_OKAY)
ashleymills 0:714293de3836 1337 err = mp_read_radix(&mG->y, (char *)key->dp->Gy, 16);
ashleymills 0:714293de3836 1338 if (err == MP_OKAY)
ashleymills 0:714293de3836 1339 mp_set(&mG->z, 1);
ashleymills 0:714293de3836 1340
ashleymills 0:714293de3836 1341 if (err == MP_OKAY)
ashleymills 0:714293de3836 1342 err = mp_copy(&key->pubkey.x, &mQ->x);
ashleymills 0:714293de3836 1343 if (err == MP_OKAY)
ashleymills 0:714293de3836 1344 err = mp_copy(&key->pubkey.y, &mQ->y);
ashleymills 0:714293de3836 1345 if (err == MP_OKAY)
ashleymills 0:714293de3836 1346 err = mp_copy(&key->pubkey.z, &mQ->z);
ashleymills 0:714293de3836 1347
ashleymills 0:714293de3836 1348 #ifndef ECC_SHAMIR
ashleymills 0:714293de3836 1349 /* compute u1*mG + u2*mQ = mG */
ashleymills 0:714293de3836 1350 if (err == MP_OKAY)
ashleymills 0:714293de3836 1351 err = ecc_mulmod(&u1, mG, mG, &m, 0);
ashleymills 0:714293de3836 1352 if (err == MP_OKAY)
ashleymills 0:714293de3836 1353 err = ecc_mulmod(&u2, mQ, mQ, &m, 0);
ashleymills 0:714293de3836 1354
ashleymills 0:714293de3836 1355 /* find the montgomery mp */
ashleymills 0:714293de3836 1356 if (err == MP_OKAY)
ashleymills 0:714293de3836 1357 err = mp_montgomery_setup(&m, &mp);
ashleymills 0:714293de3836 1358
ashleymills 0:714293de3836 1359 /* add them */
ashleymills 0:714293de3836 1360 if (err == MP_OKAY)
ashleymills 0:714293de3836 1361 err = ecc_projective_add_point(mQ, mG, mG, &m, &mp);
ashleymills 0:714293de3836 1362
ashleymills 0:714293de3836 1363 /* reduce */
ashleymills 0:714293de3836 1364 if (err == MP_OKAY)
ashleymills 0:714293de3836 1365 err = ecc_map(mG, &m, &mp);
ashleymills 0:714293de3836 1366 #else
ashleymills 0:714293de3836 1367 /* use Shamir's trick to compute u1*mG + u2*mQ using half the doubles */
ashleymills 0:714293de3836 1368 if (err == MP_OKAY)
ashleymills 0:714293de3836 1369 err = ecc_mul2add(mG, &u1, mQ, &u2, mG, &m);
ashleymills 0:714293de3836 1370 #endif /* ECC_SHAMIR */
ashleymills 0:714293de3836 1371
ashleymills 0:714293de3836 1372 /* v = X_x1 mod n */
ashleymills 0:714293de3836 1373 if (err == MP_OKAY)
ashleymills 0:714293de3836 1374 err = mp_mod(&mG->x, &p, &v);
ashleymills 0:714293de3836 1375
ashleymills 0:714293de3836 1376 /* does v == r */
ashleymills 0:714293de3836 1377 if (err == MP_OKAY) {
ashleymills 0:714293de3836 1378 if (mp_cmp(&v, &r) == MP_EQ)
ashleymills 0:714293de3836 1379 *stat = 1;
ashleymills 0:714293de3836 1380 }
ashleymills 0:714293de3836 1381
ashleymills 0:714293de3836 1382 ecc_del_point(mG);
ashleymills 0:714293de3836 1383 ecc_del_point(mQ);
ashleymills 0:714293de3836 1384
ashleymills 0:714293de3836 1385 mp_clear(&r);
ashleymills 0:714293de3836 1386 mp_clear(&s);
ashleymills 0:714293de3836 1387 mp_clear(&v);
ashleymills 0:714293de3836 1388 mp_clear(&w);
ashleymills 0:714293de3836 1389 mp_clear(&u1);
ashleymills 0:714293de3836 1390 mp_clear(&u2);
ashleymills 0:714293de3836 1391 mp_clear(&p);
ashleymills 0:714293de3836 1392 mp_clear(&e);
ashleymills 0:714293de3836 1393 mp_clear(&m);
ashleymills 0:714293de3836 1394
ashleymills 0:714293de3836 1395 return err;
ashleymills 0:714293de3836 1396 }
ashleymills 0:714293de3836 1397
ashleymills 0:714293de3836 1398
ashleymills 0:714293de3836 1399 /* export public ECC key in ANSI X9.63 format */
ashleymills 0:714293de3836 1400 int ecc_export_x963(ecc_key* key, byte* out, word32* outLen)
ashleymills 0:714293de3836 1401 {
ashleymills 0:714293de3836 1402 byte buf[ECC_BUFSIZE];
ashleymills 0:714293de3836 1403 word32 numlen;
ashleymills 0:714293de3836 1404
ashleymills 0:714293de3836 1405 if (key == NULL || out == NULL || outLen == NULL)
ashleymills 0:714293de3836 1406 return ECC_BAD_ARG_E;
ashleymills 0:714293de3836 1407
ashleymills 0:714293de3836 1408 if (ecc_is_valid_idx(key->idx) == 0) {
ashleymills 0:714293de3836 1409 return ECC_BAD_ARG_E;
ashleymills 0:714293de3836 1410 }
ashleymills 0:714293de3836 1411 numlen = key->dp->size;
ashleymills 0:714293de3836 1412
ashleymills 0:714293de3836 1413 if (*outLen < (1 + 2*numlen)) {
ashleymills 0:714293de3836 1414 *outLen = 1 + 2*numlen;
ashleymills 0:714293de3836 1415 return BUFFER_E;
ashleymills 0:714293de3836 1416 }
ashleymills 0:714293de3836 1417
ashleymills 0:714293de3836 1418 /* store byte 0x04 */
ashleymills 0:714293de3836 1419 out[0] = 0x04;
ashleymills 0:714293de3836 1420
ashleymills 0:714293de3836 1421 /* pad and store x */
ashleymills 0:714293de3836 1422 XMEMSET(buf, 0, sizeof(buf));
ashleymills 0:714293de3836 1423 mp_to_unsigned_bin(&key->pubkey.x,
ashleymills 0:714293de3836 1424 buf + (numlen - mp_unsigned_bin_size(&key->pubkey.x)));
ashleymills 0:714293de3836 1425 XMEMCPY(out+1, buf, numlen);
ashleymills 0:714293de3836 1426
ashleymills 0:714293de3836 1427 /* pad and store y */
ashleymills 0:714293de3836 1428 XMEMSET(buf, 0, sizeof(buf));
ashleymills 0:714293de3836 1429 mp_to_unsigned_bin(&key->pubkey.y,
ashleymills 0:714293de3836 1430 buf + (numlen - mp_unsigned_bin_size(&key->pubkey.y)));
ashleymills 0:714293de3836 1431 XMEMCPY(out+1+numlen, buf, numlen);
ashleymills 0:714293de3836 1432
ashleymills 0:714293de3836 1433 *outLen = 1 + 2*numlen;
ashleymills 0:714293de3836 1434
ashleymills 0:714293de3836 1435 return 0;
ashleymills 0:714293de3836 1436 }
ashleymills 0:714293de3836 1437
ashleymills 0:714293de3836 1438
ashleymills 0:714293de3836 1439 /* import public ECC key in ANSI X9.63 format */
ashleymills 0:714293de3836 1440 int ecc_import_x963(const byte* in, word32 inLen, ecc_key* key)
ashleymills 0:714293de3836 1441 {
ashleymills 0:714293de3836 1442 int x, err;
ashleymills 0:714293de3836 1443
ashleymills 0:714293de3836 1444
ashleymills 0:714293de3836 1445 if (in == NULL || key == NULL)
ashleymills 0:714293de3836 1446 return ECC_BAD_ARG_E;
ashleymills 0:714293de3836 1447
ashleymills 0:714293de3836 1448 /* must be odd */
ashleymills 0:714293de3836 1449 if ((inLen & 1) == 0) {
ashleymills 0:714293de3836 1450 return ECC_BAD_ARG_E;
ashleymills 0:714293de3836 1451 }
ashleymills 0:714293de3836 1452
ashleymills 0:714293de3836 1453 /* init key */
ashleymills 0:714293de3836 1454 if (mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k,
ashleymills 0:714293de3836 1455 NULL, NULL) != MP_OKAY) {
ashleymills 0:714293de3836 1456 return MEMORY_E;
ashleymills 0:714293de3836 1457 }
ashleymills 0:714293de3836 1458 err = MP_OKAY;
ashleymills 0:714293de3836 1459
ashleymills 0:714293de3836 1460 /* check for 4, 6 or 7 */
ashleymills 0:714293de3836 1461 if (in[0] != 4 && in[0] != 6 && in[0] != 7) {
ashleymills 0:714293de3836 1462 err = ASN_PARSE_E;
ashleymills 0:714293de3836 1463 }
ashleymills 0:714293de3836 1464
ashleymills 0:714293de3836 1465 /* read data */
ashleymills 0:714293de3836 1466 if (err == MP_OKAY)
ashleymills 0:714293de3836 1467 err = mp_read_unsigned_bin(&key->pubkey.x, (byte*)in+1, (inLen-1)>>1);
ashleymills 0:714293de3836 1468
ashleymills 0:714293de3836 1469 if (err == MP_OKAY)
ashleymills 0:714293de3836 1470 err = mp_read_unsigned_bin(&key->pubkey.y, (byte*)in+1+((inLen-1)>>1),
ashleymills 0:714293de3836 1471 (inLen-1)>>1);
ashleymills 0:714293de3836 1472
ashleymills 0:714293de3836 1473 if (err == MP_OKAY)
ashleymills 0:714293de3836 1474 mp_set(&key->pubkey.z, 1);
ashleymills 0:714293de3836 1475
ashleymills 0:714293de3836 1476 if (err == MP_OKAY) {
ashleymills 0:714293de3836 1477 /* determine the idx */
ashleymills 0:714293de3836 1478 for (x = 0; ecc_sets[x].size != 0; x++) {
ashleymills 0:714293de3836 1479 if ((unsigned)ecc_sets[x].size >= ((inLen-1)>>1)) {
ashleymills 0:714293de3836 1480 break;
ashleymills 0:714293de3836 1481 }
ashleymills 0:714293de3836 1482 }
ashleymills 0:714293de3836 1483 if (ecc_sets[x].size == 0) {
ashleymills 0:714293de3836 1484 err = ASN_PARSE_E;
ashleymills 0:714293de3836 1485 } else {
ashleymills 0:714293de3836 1486 /* set the idx */
ashleymills 0:714293de3836 1487 key->idx = x;
ashleymills 0:714293de3836 1488 key->dp = &ecc_sets[x];
ashleymills 0:714293de3836 1489 key->type = ECC_PUBLICKEY;
ashleymills 0:714293de3836 1490 }
ashleymills 0:714293de3836 1491 }
ashleymills 0:714293de3836 1492
ashleymills 0:714293de3836 1493 if (err != MP_OKAY) {
ashleymills 0:714293de3836 1494 mp_clear(&key->pubkey.x);
ashleymills 0:714293de3836 1495 mp_clear(&key->pubkey.y);
ashleymills 0:714293de3836 1496 mp_clear(&key->pubkey.z);
ashleymills 0:714293de3836 1497 mp_clear(&key->k);
ashleymills 0:714293de3836 1498 }
ashleymills 0:714293de3836 1499
ashleymills 0:714293de3836 1500 return err;
ashleymills 0:714293de3836 1501 }
ashleymills 0:714293de3836 1502
ashleymills 0:714293de3836 1503
ashleymills 0:714293de3836 1504 /* ecc private key import, public key in ANSI X9.63 format, private raw */
ashleymills 0:714293de3836 1505 int ecc_import_private_key(const byte* priv, word32 privSz, const byte* pub,
ashleymills 0:714293de3836 1506 word32 pubSz, ecc_key* key)
ashleymills 0:714293de3836 1507 {
ashleymills 0:714293de3836 1508 int ret = ecc_import_x963(pub, pubSz, key);
ashleymills 0:714293de3836 1509 if (ret != 0)
ashleymills 0:714293de3836 1510 return ret;
ashleymills 0:714293de3836 1511
ashleymills 0:714293de3836 1512 key->type = ECC_PRIVATEKEY;
ashleymills 0:714293de3836 1513
ashleymills 0:714293de3836 1514 return mp_read_unsigned_bin(&key->k, priv, privSz);
ashleymills 0:714293de3836 1515 }
ashleymills 0:714293de3836 1516
ashleymills 0:714293de3836 1517
ashleymills 0:714293de3836 1518 /* key size in octets */
ashleymills 0:714293de3836 1519 int ecc_size(ecc_key* key)
ashleymills 0:714293de3836 1520 {
ashleymills 0:714293de3836 1521 if (key == NULL) return 0;
ashleymills 0:714293de3836 1522
ashleymills 0:714293de3836 1523 return key->dp->size;
ashleymills 0:714293de3836 1524 }
ashleymills 0:714293de3836 1525
ashleymills 0:714293de3836 1526
ashleymills 0:714293de3836 1527 /* signature size in octets */
ashleymills 0:714293de3836 1528 int ecc_sig_size(ecc_key* key)
ashleymills 0:714293de3836 1529 {
ashleymills 0:714293de3836 1530 int sz = ecc_size(key);
ashleymills 0:714293de3836 1531 if (sz < 0)
ashleymills 0:714293de3836 1532 return sz;
ashleymills 0:714293de3836 1533
ashleymills 0:714293de3836 1534 return sz * 2 + SIG_HEADER_SZ;
ashleymills 0:714293de3836 1535 }
ashleymills 0:714293de3836 1536
ashleymills 0:714293de3836 1537 #endif /* HAVE_ECC */