micro-ECC for mbed, ported from GCC version from Github,
Dependents: mbed_microECC Wallet_v1
uECC.cpp@0:b6fdeddc0bc9, 2017-09-07 (annotated)
- Committer:
- allankliu
- Date:
- Thu Sep 07 12:10:11 2017 +0000
- Revision:
- 0:b6fdeddc0bc9
Init version, ported from GCC version of uECC of Github. Assembly optimization for thumb2 is disabled.
Who changed what in which revision?
User | Revision | Line number | New contents of line |
---|---|---|---|
allankliu | 0:b6fdeddc0bc9 | 1 | /* Copyright 2014, Kenneth MacKay. Licensed under the BSD 2-clause license. */ |
allankliu | 0:b6fdeddc0bc9 | 2 | |
allankliu | 0:b6fdeddc0bc9 | 3 | #include "uECC.h" |
allankliu | 0:b6fdeddc0bc9 | 4 | #include "uECC_vli.h" |
allankliu | 0:b6fdeddc0bc9 | 5 | |
allankliu | 0:b6fdeddc0bc9 | 6 | #ifndef uECC_RNG_MAX_TRIES |
allankliu | 0:b6fdeddc0bc9 | 7 | #define uECC_RNG_MAX_TRIES 64 |
allankliu | 0:b6fdeddc0bc9 | 8 | #endif |
allankliu | 0:b6fdeddc0bc9 | 9 | |
allankliu | 0:b6fdeddc0bc9 | 10 | #if uECC_ENABLE_VLI_API |
allankliu | 0:b6fdeddc0bc9 | 11 | #define uECC_VLI_API |
allankliu | 0:b6fdeddc0bc9 | 12 | #else |
allankliu | 0:b6fdeddc0bc9 | 13 | #define uECC_VLI_API static |
allankliu | 0:b6fdeddc0bc9 | 14 | #endif |
allankliu | 0:b6fdeddc0bc9 | 15 | |
allankliu | 0:b6fdeddc0bc9 | 16 | #define CONCATX(a, ...) a ## __VA_ARGS__ |
allankliu | 0:b6fdeddc0bc9 | 17 | #define CONCAT(a, ...) CONCATX(a, __VA_ARGS__) |
allankliu | 0:b6fdeddc0bc9 | 18 | |
allankliu | 0:b6fdeddc0bc9 | 19 | #define STRX(a) #a |
allankliu | 0:b6fdeddc0bc9 | 20 | #define STR(a) STRX(a) |
allankliu | 0:b6fdeddc0bc9 | 21 | |
allankliu | 0:b6fdeddc0bc9 | 22 | #define EVAL(...) EVAL1(EVAL1(EVAL1(EVAL1(__VA_ARGS__)))) |
allankliu | 0:b6fdeddc0bc9 | 23 | #define EVAL1(...) EVAL2(EVAL2(EVAL2(EVAL2(__VA_ARGS__)))) |
allankliu | 0:b6fdeddc0bc9 | 24 | #define EVAL2(...) EVAL3(EVAL3(EVAL3(EVAL3(__VA_ARGS__)))) |
allankliu | 0:b6fdeddc0bc9 | 25 | #define EVAL3(...) EVAL4(EVAL4(EVAL4(EVAL4(__VA_ARGS__)))) |
allankliu | 0:b6fdeddc0bc9 | 26 | #define EVAL4(...) __VA_ARGS__ |
allankliu | 0:b6fdeddc0bc9 | 27 | |
allankliu | 0:b6fdeddc0bc9 | 28 | #define DEC_1 0 |
allankliu | 0:b6fdeddc0bc9 | 29 | #define DEC_2 1 |
allankliu | 0:b6fdeddc0bc9 | 30 | #define DEC_3 2 |
allankliu | 0:b6fdeddc0bc9 | 31 | #define DEC_4 3 |
allankliu | 0:b6fdeddc0bc9 | 32 | #define DEC_5 4 |
allankliu | 0:b6fdeddc0bc9 | 33 | #define DEC_6 5 |
allankliu | 0:b6fdeddc0bc9 | 34 | #define DEC_7 6 |
allankliu | 0:b6fdeddc0bc9 | 35 | #define DEC_8 7 |
allankliu | 0:b6fdeddc0bc9 | 36 | #define DEC_9 8 |
allankliu | 0:b6fdeddc0bc9 | 37 | #define DEC_10 9 |
allankliu | 0:b6fdeddc0bc9 | 38 | #define DEC_11 10 |
allankliu | 0:b6fdeddc0bc9 | 39 | #define DEC_12 11 |
allankliu | 0:b6fdeddc0bc9 | 40 | #define DEC_13 12 |
allankliu | 0:b6fdeddc0bc9 | 41 | #define DEC_14 13 |
allankliu | 0:b6fdeddc0bc9 | 42 | #define DEC_15 14 |
allankliu | 0:b6fdeddc0bc9 | 43 | #define DEC_16 15 |
allankliu | 0:b6fdeddc0bc9 | 44 | #define DEC_17 16 |
allankliu | 0:b6fdeddc0bc9 | 45 | #define DEC_18 17 |
allankliu | 0:b6fdeddc0bc9 | 46 | #define DEC_19 18 |
allankliu | 0:b6fdeddc0bc9 | 47 | #define DEC_20 19 |
allankliu | 0:b6fdeddc0bc9 | 48 | #define DEC_21 20 |
allankliu | 0:b6fdeddc0bc9 | 49 | #define DEC_22 21 |
allankliu | 0:b6fdeddc0bc9 | 50 | #define DEC_23 22 |
allankliu | 0:b6fdeddc0bc9 | 51 | #define DEC_24 23 |
allankliu | 0:b6fdeddc0bc9 | 52 | #define DEC_25 24 |
allankliu | 0:b6fdeddc0bc9 | 53 | #define DEC_26 25 |
allankliu | 0:b6fdeddc0bc9 | 54 | #define DEC_27 26 |
allankliu | 0:b6fdeddc0bc9 | 55 | #define DEC_28 27 |
allankliu | 0:b6fdeddc0bc9 | 56 | #define DEC_29 28 |
allankliu | 0:b6fdeddc0bc9 | 57 | #define DEC_30 29 |
allankliu | 0:b6fdeddc0bc9 | 58 | #define DEC_31 30 |
allankliu | 0:b6fdeddc0bc9 | 59 | #define DEC_32 31 |
allankliu | 0:b6fdeddc0bc9 | 60 | |
allankliu | 0:b6fdeddc0bc9 | 61 | #define DEC(N) CONCAT(DEC_, N) |
allankliu | 0:b6fdeddc0bc9 | 62 | |
allankliu | 0:b6fdeddc0bc9 | 63 | #define SECOND_ARG(_, val, ...) val |
allankliu | 0:b6fdeddc0bc9 | 64 | #define SOME_CHECK_0 ~, 0 |
allankliu | 0:b6fdeddc0bc9 | 65 | #define GET_SECOND_ARG(...) SECOND_ARG(__VA_ARGS__, SOME,) |
allankliu | 0:b6fdeddc0bc9 | 66 | #define SOME_OR_0(N) GET_SECOND_ARG(CONCAT(SOME_CHECK_, N)) |
allankliu | 0:b6fdeddc0bc9 | 67 | |
allankliu | 0:b6fdeddc0bc9 | 68 | #define EMPTY(...) |
allankliu | 0:b6fdeddc0bc9 | 69 | #define DEFER(...) __VA_ARGS__ EMPTY() |
allankliu | 0:b6fdeddc0bc9 | 70 | |
allankliu | 0:b6fdeddc0bc9 | 71 | #define REPEAT_NAME_0() REPEAT_0 |
allankliu | 0:b6fdeddc0bc9 | 72 | #define REPEAT_NAME_SOME() REPEAT_SOME |
allankliu | 0:b6fdeddc0bc9 | 73 | #define REPEAT_0(...) |
allankliu | 0:b6fdeddc0bc9 | 74 | #define REPEAT_SOME(N, stuff) DEFER(CONCAT(REPEAT_NAME_, SOME_OR_0(DEC(N))))()(DEC(N), stuff) stuff |
allankliu | 0:b6fdeddc0bc9 | 75 | #define REPEAT(N, stuff) EVAL(REPEAT_SOME(N, stuff)) |
allankliu | 0:b6fdeddc0bc9 | 76 | |
allankliu | 0:b6fdeddc0bc9 | 77 | #define REPEATM_NAME_0() REPEATM_0 |
allankliu | 0:b6fdeddc0bc9 | 78 | #define REPEATM_NAME_SOME() REPEATM_SOME |
allankliu | 0:b6fdeddc0bc9 | 79 | #define REPEATM_0(...) |
allankliu | 0:b6fdeddc0bc9 | 80 | #define REPEATM_SOME(N, macro) macro(N) \ |
allankliu | 0:b6fdeddc0bc9 | 81 | DEFER(CONCAT(REPEATM_NAME_, SOME_OR_0(DEC(N))))()(DEC(N), macro) |
allankliu | 0:b6fdeddc0bc9 | 82 | #define REPEATM(N, macro) EVAL(REPEATM_SOME(N, macro)) |
allankliu | 0:b6fdeddc0bc9 | 83 | |
allankliu | 0:b6fdeddc0bc9 | 84 | //#include "platform-specific.inc" |
allankliu | 0:b6fdeddc0bc9 | 85 | #include "platform-specific.h" |
allankliu | 0:b6fdeddc0bc9 | 86 | |
allankliu | 0:b6fdeddc0bc9 | 87 | #if (uECC_WORD_SIZE == 1) |
allankliu | 0:b6fdeddc0bc9 | 88 | #if uECC_SUPPORTS_secp160r1 |
allankliu | 0:b6fdeddc0bc9 | 89 | #define uECC_MAX_WORDS 21 /* Due to the size of curve_n. */ |
allankliu | 0:b6fdeddc0bc9 | 90 | #endif |
allankliu | 0:b6fdeddc0bc9 | 91 | #if uECC_SUPPORTS_secp192r1 |
allankliu | 0:b6fdeddc0bc9 | 92 | #undef uECC_MAX_WORDS |
allankliu | 0:b6fdeddc0bc9 | 93 | #define uECC_MAX_WORDS 24 |
allankliu | 0:b6fdeddc0bc9 | 94 | #endif |
allankliu | 0:b6fdeddc0bc9 | 95 | #if uECC_SUPPORTS_secp224r1 |
allankliu | 0:b6fdeddc0bc9 | 96 | #undef uECC_MAX_WORDS |
allankliu | 0:b6fdeddc0bc9 | 97 | #define uECC_MAX_WORDS 28 |
allankliu | 0:b6fdeddc0bc9 | 98 | #endif |
allankliu | 0:b6fdeddc0bc9 | 99 | #if (uECC_SUPPORTS_secp256r1 || uECC_SUPPORTS_secp256k1) |
allankliu | 0:b6fdeddc0bc9 | 100 | #undef uECC_MAX_WORDS |
allankliu | 0:b6fdeddc0bc9 | 101 | #define uECC_MAX_WORDS 32 |
allankliu | 0:b6fdeddc0bc9 | 102 | #endif |
allankliu | 0:b6fdeddc0bc9 | 103 | #elif (uECC_WORD_SIZE == 4) |
allankliu | 0:b6fdeddc0bc9 | 104 | #if uECC_SUPPORTS_secp160r1 |
allankliu | 0:b6fdeddc0bc9 | 105 | #define uECC_MAX_WORDS 6 /* Due to the size of curve_n. */ |
allankliu | 0:b6fdeddc0bc9 | 106 | #endif |
allankliu | 0:b6fdeddc0bc9 | 107 | #if uECC_SUPPORTS_secp192r1 |
allankliu | 0:b6fdeddc0bc9 | 108 | #undef uECC_MAX_WORDS |
allankliu | 0:b6fdeddc0bc9 | 109 | #define uECC_MAX_WORDS 6 |
allankliu | 0:b6fdeddc0bc9 | 110 | #endif |
allankliu | 0:b6fdeddc0bc9 | 111 | #if uECC_SUPPORTS_secp224r1 |
allankliu | 0:b6fdeddc0bc9 | 112 | #undef uECC_MAX_WORDS |
allankliu | 0:b6fdeddc0bc9 | 113 | #define uECC_MAX_WORDS 7 |
allankliu | 0:b6fdeddc0bc9 | 114 | #endif |
allankliu | 0:b6fdeddc0bc9 | 115 | #if (uECC_SUPPORTS_secp256r1 || uECC_SUPPORTS_secp256k1) |
allankliu | 0:b6fdeddc0bc9 | 116 | #undef uECC_MAX_WORDS |
allankliu | 0:b6fdeddc0bc9 | 117 | #define uECC_MAX_WORDS 8 |
allankliu | 0:b6fdeddc0bc9 | 118 | #endif |
allankliu | 0:b6fdeddc0bc9 | 119 | #elif (uECC_WORD_SIZE == 8) |
allankliu | 0:b6fdeddc0bc9 | 120 | #if uECC_SUPPORTS_secp160r1 |
allankliu | 0:b6fdeddc0bc9 | 121 | #define uECC_MAX_WORDS 3 |
allankliu | 0:b6fdeddc0bc9 | 122 | #endif |
allankliu | 0:b6fdeddc0bc9 | 123 | #if uECC_SUPPORTS_secp192r1 |
allankliu | 0:b6fdeddc0bc9 | 124 | #undef uECC_MAX_WORDS |
allankliu | 0:b6fdeddc0bc9 | 125 | #define uECC_MAX_WORDS 3 |
allankliu | 0:b6fdeddc0bc9 | 126 | #endif |
allankliu | 0:b6fdeddc0bc9 | 127 | #if uECC_SUPPORTS_secp224r1 |
allankliu | 0:b6fdeddc0bc9 | 128 | #undef uECC_MAX_WORDS |
allankliu | 0:b6fdeddc0bc9 | 129 | #define uECC_MAX_WORDS 4 |
allankliu | 0:b6fdeddc0bc9 | 130 | #endif |
allankliu | 0:b6fdeddc0bc9 | 131 | #if (uECC_SUPPORTS_secp256r1 || uECC_SUPPORTS_secp256k1) |
allankliu | 0:b6fdeddc0bc9 | 132 | #undef uECC_MAX_WORDS |
allankliu | 0:b6fdeddc0bc9 | 133 | #define uECC_MAX_WORDS 4 |
allankliu | 0:b6fdeddc0bc9 | 134 | #endif |
allankliu | 0:b6fdeddc0bc9 | 135 | #endif /* uECC_WORD_SIZE */ |
allankliu | 0:b6fdeddc0bc9 | 136 | |
allankliu | 0:b6fdeddc0bc9 | 137 | #define BITS_TO_WORDS(num_bits) ((num_bits + ((uECC_WORD_SIZE * 8) - 1)) / (uECC_WORD_SIZE * 8)) |
allankliu | 0:b6fdeddc0bc9 | 138 | #define BITS_TO_BYTES(num_bits) ((num_bits + 7) / 8) |
allankliu | 0:b6fdeddc0bc9 | 139 | |
allankliu | 0:b6fdeddc0bc9 | 140 | struct uECC_Curve_t { |
allankliu | 0:b6fdeddc0bc9 | 141 | wordcount_t num_words; |
allankliu | 0:b6fdeddc0bc9 | 142 | wordcount_t num_bytes; |
allankliu | 0:b6fdeddc0bc9 | 143 | bitcount_t num_n_bits; |
allankliu | 0:b6fdeddc0bc9 | 144 | uECC_word_t p[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 145 | uECC_word_t n[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 146 | uECC_word_t G[uECC_MAX_WORDS * 2]; |
allankliu | 0:b6fdeddc0bc9 | 147 | uECC_word_t b[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 148 | void (*double_jacobian)(uECC_word_t * X1, |
allankliu | 0:b6fdeddc0bc9 | 149 | uECC_word_t * Y1, |
allankliu | 0:b6fdeddc0bc9 | 150 | uECC_word_t * Z1, |
allankliu | 0:b6fdeddc0bc9 | 151 | uECC_Curve curve); |
allankliu | 0:b6fdeddc0bc9 | 152 | #if uECC_SUPPORT_COMPRESSED_POINT |
allankliu | 0:b6fdeddc0bc9 | 153 | void (*mod_sqrt)(uECC_word_t *a, uECC_Curve curve); |
allankliu | 0:b6fdeddc0bc9 | 154 | #endif |
allankliu | 0:b6fdeddc0bc9 | 155 | void (*x_side)(uECC_word_t *result, const uECC_word_t *x, uECC_Curve curve); |
allankliu | 0:b6fdeddc0bc9 | 156 | #if (uECC_OPTIMIZATION_LEVEL > 0) |
allankliu | 0:b6fdeddc0bc9 | 157 | void (*mmod_fast)(uECC_word_t *result, uECC_word_t *product); |
allankliu | 0:b6fdeddc0bc9 | 158 | #endif |
allankliu | 0:b6fdeddc0bc9 | 159 | }; |
allankliu | 0:b6fdeddc0bc9 | 160 | |
allankliu | 0:b6fdeddc0bc9 | 161 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN |
allankliu | 0:b6fdeddc0bc9 | 162 | static void bcopy(uint8_t *dst, |
allankliu | 0:b6fdeddc0bc9 | 163 | const uint8_t *src, |
allankliu | 0:b6fdeddc0bc9 | 164 | unsigned num_bytes) { |
allankliu | 0:b6fdeddc0bc9 | 165 | while (0 != num_bytes) { |
allankliu | 0:b6fdeddc0bc9 | 166 | num_bytes--; |
allankliu | 0:b6fdeddc0bc9 | 167 | dst[num_bytes] = src[num_bytes]; |
allankliu | 0:b6fdeddc0bc9 | 168 | } |
allankliu | 0:b6fdeddc0bc9 | 169 | } |
allankliu | 0:b6fdeddc0bc9 | 170 | #endif |
allankliu | 0:b6fdeddc0bc9 | 171 | |
allankliu | 0:b6fdeddc0bc9 | 172 | static cmpresult_t uECC_vli_cmp_unsafe(const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 173 | const uECC_word_t *right, |
allankliu | 0:b6fdeddc0bc9 | 174 | wordcount_t num_words); |
allankliu | 0:b6fdeddc0bc9 | 175 | |
allankliu | 0:b6fdeddc0bc9 | 176 | #if (uECC_PLATFORM == uECC_arm || uECC_PLATFORM == uECC_arm_thumb || \ |
allankliu | 0:b6fdeddc0bc9 | 177 | uECC_PLATFORM == uECC_arm_thumb2) |
allankliu | 0:b6fdeddc0bc9 | 178 | //#include "asm_arm.inc" |
allankliu | 0:b6fdeddc0bc9 | 179 | #include "asm_arm.h" |
allankliu | 0:b6fdeddc0bc9 | 180 | #if (uECC_PLATFORM == uECC_arm) |
allankliu | 0:b6fdeddc0bc9 | 181 | #warning uECC_arm |
allankliu | 0:b6fdeddc0bc9 | 182 | #elif (uECC_PLATFORM == uECC_arm_thumb) |
allankliu | 0:b6fdeddc0bc9 | 183 | #warning uECC_arm_thumb |
allankliu | 0:b6fdeddc0bc9 | 184 | #elif (uECC_PLATFORM == uECC_arm_thumb2) |
allankliu | 0:b6fdeddc0bc9 | 185 | #warning uECC_arm_thumb2 |
allankliu | 0:b6fdeddc0bc9 | 186 | #endif |
allankliu | 0:b6fdeddc0bc9 | 187 | #endif |
allankliu | 0:b6fdeddc0bc9 | 188 | |
allankliu | 0:b6fdeddc0bc9 | 189 | #if (uECC_PLATFORM == uECC_avr) |
allankliu | 0:b6fdeddc0bc9 | 190 | #include "asm_avr.inc" |
allankliu | 0:b6fdeddc0bc9 | 191 | #endif |
allankliu | 0:b6fdeddc0bc9 | 192 | |
allankliu | 0:b6fdeddc0bc9 | 193 | #if default_RNG_defined |
allankliu | 0:b6fdeddc0bc9 | 194 | static uECC_RNG_Function g_rng_function = &default_RNG; |
allankliu | 0:b6fdeddc0bc9 | 195 | #else |
allankliu | 0:b6fdeddc0bc9 | 196 | static uECC_RNG_Function g_rng_function = 0; |
allankliu | 0:b6fdeddc0bc9 | 197 | #endif |
allankliu | 0:b6fdeddc0bc9 | 198 | |
allankliu | 0:b6fdeddc0bc9 | 199 | void uECC_set_rng(uECC_RNG_Function rng_function) { |
allankliu | 0:b6fdeddc0bc9 | 200 | g_rng_function = rng_function; |
allankliu | 0:b6fdeddc0bc9 | 201 | } |
allankliu | 0:b6fdeddc0bc9 | 202 | |
allankliu | 0:b6fdeddc0bc9 | 203 | uECC_RNG_Function uECC_get_rng(void) { |
allankliu | 0:b6fdeddc0bc9 | 204 | return g_rng_function; |
allankliu | 0:b6fdeddc0bc9 | 205 | } |
allankliu | 0:b6fdeddc0bc9 | 206 | |
allankliu | 0:b6fdeddc0bc9 | 207 | int uECC_curve_private_key_size(uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 208 | return BITS_TO_BYTES(curve->num_n_bits); |
allankliu | 0:b6fdeddc0bc9 | 209 | } |
allankliu | 0:b6fdeddc0bc9 | 210 | |
allankliu | 0:b6fdeddc0bc9 | 211 | int uECC_curve_public_key_size(uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 212 | return 2 * curve->num_bytes; |
allankliu | 0:b6fdeddc0bc9 | 213 | } |
allankliu | 0:b6fdeddc0bc9 | 214 | |
allankliu | 0:b6fdeddc0bc9 | 215 | #if !asm_clear |
allankliu | 0:b6fdeddc0bc9 | 216 | uECC_VLI_API void uECC_vli_clear(uECC_word_t *vli, wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 217 | wordcount_t i; |
allankliu | 0:b6fdeddc0bc9 | 218 | for (i = 0; i < num_words; ++i) { |
allankliu | 0:b6fdeddc0bc9 | 219 | vli[i] = 0; |
allankliu | 0:b6fdeddc0bc9 | 220 | } |
allankliu | 0:b6fdeddc0bc9 | 221 | } |
allankliu | 0:b6fdeddc0bc9 | 222 | #endif /* !asm_clear */ |
allankliu | 0:b6fdeddc0bc9 | 223 | |
allankliu | 0:b6fdeddc0bc9 | 224 | /* Constant-time comparison to zero - secure way to compare long integers */ |
allankliu | 0:b6fdeddc0bc9 | 225 | /* Returns 1 if vli == 0, 0 otherwise. */ |
allankliu | 0:b6fdeddc0bc9 | 226 | uECC_VLI_API uECC_word_t uECC_vli_isZero(const uECC_word_t *vli, wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 227 | uECC_word_t bits = 0; |
allankliu | 0:b6fdeddc0bc9 | 228 | wordcount_t i; |
allankliu | 0:b6fdeddc0bc9 | 229 | for (i = 0; i < num_words; ++i) { |
allankliu | 0:b6fdeddc0bc9 | 230 | bits |= vli[i]; |
allankliu | 0:b6fdeddc0bc9 | 231 | } |
allankliu | 0:b6fdeddc0bc9 | 232 | return (bits == 0); |
allankliu | 0:b6fdeddc0bc9 | 233 | } |
allankliu | 0:b6fdeddc0bc9 | 234 | |
allankliu | 0:b6fdeddc0bc9 | 235 | /* Returns nonzero if bit 'bit' of vli is set. */ |
allankliu | 0:b6fdeddc0bc9 | 236 | uECC_VLI_API uECC_word_t uECC_vli_testBit(const uECC_word_t *vli, bitcount_t bit) { |
allankliu | 0:b6fdeddc0bc9 | 237 | return (vli[bit >> uECC_WORD_BITS_SHIFT] & ((uECC_word_t)1 << (bit & uECC_WORD_BITS_MASK))); |
allankliu | 0:b6fdeddc0bc9 | 238 | } |
allankliu | 0:b6fdeddc0bc9 | 239 | |
allankliu | 0:b6fdeddc0bc9 | 240 | /* Counts the number of words in vli. */ |
allankliu | 0:b6fdeddc0bc9 | 241 | static wordcount_t vli_numDigits(const uECC_word_t *vli, const wordcount_t max_words) { |
allankliu | 0:b6fdeddc0bc9 | 242 | wordcount_t i; |
allankliu | 0:b6fdeddc0bc9 | 243 | /* Search from the end until we find a non-zero digit. |
allankliu | 0:b6fdeddc0bc9 | 244 | We do it in reverse because we expect that most digits will be nonzero. */ |
allankliu | 0:b6fdeddc0bc9 | 245 | for (i = max_words - 1; i >= 0 && vli[i] == 0; --i) { |
allankliu | 0:b6fdeddc0bc9 | 246 | } |
allankliu | 0:b6fdeddc0bc9 | 247 | |
allankliu | 0:b6fdeddc0bc9 | 248 | return (i + 1); |
allankliu | 0:b6fdeddc0bc9 | 249 | } |
allankliu | 0:b6fdeddc0bc9 | 250 | |
allankliu | 0:b6fdeddc0bc9 | 251 | /* Counts the number of bits required to represent vli. */ |
allankliu | 0:b6fdeddc0bc9 | 252 | uECC_VLI_API bitcount_t uECC_vli_numBits(const uECC_word_t *vli, const wordcount_t max_words) { |
allankliu | 0:b6fdeddc0bc9 | 253 | uECC_word_t i; |
allankliu | 0:b6fdeddc0bc9 | 254 | uECC_word_t digit; |
allankliu | 0:b6fdeddc0bc9 | 255 | |
allankliu | 0:b6fdeddc0bc9 | 256 | wordcount_t num_digits = vli_numDigits(vli, max_words); |
allankliu | 0:b6fdeddc0bc9 | 257 | if (num_digits == 0) { |
allankliu | 0:b6fdeddc0bc9 | 258 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 259 | } |
allankliu | 0:b6fdeddc0bc9 | 260 | |
allankliu | 0:b6fdeddc0bc9 | 261 | digit = vli[num_digits - 1]; |
allankliu | 0:b6fdeddc0bc9 | 262 | for (i = 0; digit; ++i) { |
allankliu | 0:b6fdeddc0bc9 | 263 | digit >>= 1; |
allankliu | 0:b6fdeddc0bc9 | 264 | } |
allankliu | 0:b6fdeddc0bc9 | 265 | |
allankliu | 0:b6fdeddc0bc9 | 266 | return (((bitcount_t)(num_digits - 1) << uECC_WORD_BITS_SHIFT) + i); |
allankliu | 0:b6fdeddc0bc9 | 267 | } |
allankliu | 0:b6fdeddc0bc9 | 268 | |
allankliu | 0:b6fdeddc0bc9 | 269 | /* Sets dest = src. */ |
allankliu | 0:b6fdeddc0bc9 | 270 | #if !asm_set |
allankliu | 0:b6fdeddc0bc9 | 271 | uECC_VLI_API void uECC_vli_set(uECC_word_t *dest, const uECC_word_t *src, wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 272 | wordcount_t i; |
allankliu | 0:b6fdeddc0bc9 | 273 | for (i = 0; i < num_words; ++i) { |
allankliu | 0:b6fdeddc0bc9 | 274 | dest[i] = src[i]; |
allankliu | 0:b6fdeddc0bc9 | 275 | } |
allankliu | 0:b6fdeddc0bc9 | 276 | } |
allankliu | 0:b6fdeddc0bc9 | 277 | #endif /* !asm_set */ |
allankliu | 0:b6fdeddc0bc9 | 278 | |
allankliu | 0:b6fdeddc0bc9 | 279 | /* Returns sign of left - right. */ |
allankliu | 0:b6fdeddc0bc9 | 280 | static cmpresult_t uECC_vli_cmp_unsafe(const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 281 | const uECC_word_t *right, |
allankliu | 0:b6fdeddc0bc9 | 282 | wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 283 | wordcount_t i; |
allankliu | 0:b6fdeddc0bc9 | 284 | for (i = num_words - 1; i >= 0; --i) { |
allankliu | 0:b6fdeddc0bc9 | 285 | if (left[i] > right[i]) { |
allankliu | 0:b6fdeddc0bc9 | 286 | return 1; |
allankliu | 0:b6fdeddc0bc9 | 287 | } else if (left[i] < right[i]) { |
allankliu | 0:b6fdeddc0bc9 | 288 | return -1; |
allankliu | 0:b6fdeddc0bc9 | 289 | } |
allankliu | 0:b6fdeddc0bc9 | 290 | } |
allankliu | 0:b6fdeddc0bc9 | 291 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 292 | } |
allankliu | 0:b6fdeddc0bc9 | 293 | |
allankliu | 0:b6fdeddc0bc9 | 294 | /* Constant-time comparison function - secure way to compare long integers */ |
allankliu | 0:b6fdeddc0bc9 | 295 | /* Returns one if left == right, zero otherwise. */ |
allankliu | 0:b6fdeddc0bc9 | 296 | uECC_VLI_API uECC_word_t uECC_vli_equal(const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 297 | const uECC_word_t *right, |
allankliu | 0:b6fdeddc0bc9 | 298 | wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 299 | uECC_word_t diff = 0; |
allankliu | 0:b6fdeddc0bc9 | 300 | wordcount_t i; |
allankliu | 0:b6fdeddc0bc9 | 301 | for (i = num_words - 1; i >= 0; --i) { |
allankliu | 0:b6fdeddc0bc9 | 302 | diff |= (left[i] ^ right[i]); |
allankliu | 0:b6fdeddc0bc9 | 303 | } |
allankliu | 0:b6fdeddc0bc9 | 304 | return (diff == 0); |
allankliu | 0:b6fdeddc0bc9 | 305 | } |
allankliu | 0:b6fdeddc0bc9 | 306 | |
allankliu | 0:b6fdeddc0bc9 | 307 | uECC_VLI_API uECC_word_t uECC_vli_sub(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 308 | const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 309 | const uECC_word_t *right, |
allankliu | 0:b6fdeddc0bc9 | 310 | wordcount_t num_words); |
allankliu | 0:b6fdeddc0bc9 | 311 | |
allankliu | 0:b6fdeddc0bc9 | 312 | /* Returns sign of left - right, in constant time. */ |
allankliu | 0:b6fdeddc0bc9 | 313 | uECC_VLI_API cmpresult_t uECC_vli_cmp(const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 314 | const uECC_word_t *right, |
allankliu | 0:b6fdeddc0bc9 | 315 | wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 316 | uECC_word_t tmp[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 317 | uECC_word_t neg = !!uECC_vli_sub(tmp, left, right, num_words); |
allankliu | 0:b6fdeddc0bc9 | 318 | uECC_word_t equal = uECC_vli_isZero(tmp, num_words); |
allankliu | 0:b6fdeddc0bc9 | 319 | return (!equal - 2 * neg); |
allankliu | 0:b6fdeddc0bc9 | 320 | } |
allankliu | 0:b6fdeddc0bc9 | 321 | |
allankliu | 0:b6fdeddc0bc9 | 322 | /* Computes vli = vli >> 1. */ |
allankliu | 0:b6fdeddc0bc9 | 323 | #if !asm_rshift1 |
allankliu | 0:b6fdeddc0bc9 | 324 | uECC_VLI_API void uECC_vli_rshift1(uECC_word_t *vli, wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 325 | uECC_word_t *end = vli; |
allankliu | 0:b6fdeddc0bc9 | 326 | uECC_word_t carry = 0; |
allankliu | 0:b6fdeddc0bc9 | 327 | |
allankliu | 0:b6fdeddc0bc9 | 328 | vli += num_words; |
allankliu | 0:b6fdeddc0bc9 | 329 | while (vli-- > end) { |
allankliu | 0:b6fdeddc0bc9 | 330 | uECC_word_t temp = *vli; |
allankliu | 0:b6fdeddc0bc9 | 331 | *vli = (temp >> 1) | carry; |
allankliu | 0:b6fdeddc0bc9 | 332 | carry = temp << (uECC_WORD_BITS - 1); |
allankliu | 0:b6fdeddc0bc9 | 333 | } |
allankliu | 0:b6fdeddc0bc9 | 334 | } |
allankliu | 0:b6fdeddc0bc9 | 335 | #endif /* !asm_rshift1 */ |
allankliu | 0:b6fdeddc0bc9 | 336 | |
allankliu | 0:b6fdeddc0bc9 | 337 | /* Computes result = left + right, returning carry. Can modify in place. */ |
allankliu | 0:b6fdeddc0bc9 | 338 | #if !asm_add |
allankliu | 0:b6fdeddc0bc9 | 339 | uECC_VLI_API uECC_word_t uECC_vli_add(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 340 | const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 341 | const uECC_word_t *right, |
allankliu | 0:b6fdeddc0bc9 | 342 | wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 343 | uECC_word_t carry = 0; |
allankliu | 0:b6fdeddc0bc9 | 344 | wordcount_t i; |
allankliu | 0:b6fdeddc0bc9 | 345 | for (i = 0; i < num_words; ++i) { |
allankliu | 0:b6fdeddc0bc9 | 346 | uECC_word_t sum = left[i] + right[i] + carry; |
allankliu | 0:b6fdeddc0bc9 | 347 | if (sum != left[i]) { |
allankliu | 0:b6fdeddc0bc9 | 348 | carry = (sum < left[i]); |
allankliu | 0:b6fdeddc0bc9 | 349 | } |
allankliu | 0:b6fdeddc0bc9 | 350 | result[i] = sum; |
allankliu | 0:b6fdeddc0bc9 | 351 | } |
allankliu | 0:b6fdeddc0bc9 | 352 | return carry; |
allankliu | 0:b6fdeddc0bc9 | 353 | } |
allankliu | 0:b6fdeddc0bc9 | 354 | #endif /* !asm_add */ |
allankliu | 0:b6fdeddc0bc9 | 355 | |
allankliu | 0:b6fdeddc0bc9 | 356 | /* Computes result = left - right, returning borrow. Can modify in place. */ |
allankliu | 0:b6fdeddc0bc9 | 357 | #if !asm_sub |
allankliu | 0:b6fdeddc0bc9 | 358 | uECC_VLI_API uECC_word_t uECC_vli_sub(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 359 | const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 360 | const uECC_word_t *right, |
allankliu | 0:b6fdeddc0bc9 | 361 | wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 362 | uECC_word_t borrow = 0; |
allankliu | 0:b6fdeddc0bc9 | 363 | wordcount_t i; |
allankliu | 0:b6fdeddc0bc9 | 364 | for (i = 0; i < num_words; ++i) { |
allankliu | 0:b6fdeddc0bc9 | 365 | uECC_word_t diff = left[i] - right[i] - borrow; |
allankliu | 0:b6fdeddc0bc9 | 366 | if (diff != left[i]) { |
allankliu | 0:b6fdeddc0bc9 | 367 | borrow = (diff > left[i]); |
allankliu | 0:b6fdeddc0bc9 | 368 | } |
allankliu | 0:b6fdeddc0bc9 | 369 | result[i] = diff; |
allankliu | 0:b6fdeddc0bc9 | 370 | } |
allankliu | 0:b6fdeddc0bc9 | 371 | return borrow; |
allankliu | 0:b6fdeddc0bc9 | 372 | } |
allankliu | 0:b6fdeddc0bc9 | 373 | #endif /* !asm_sub */ |
allankliu | 0:b6fdeddc0bc9 | 374 | |
allankliu | 0:b6fdeddc0bc9 | 375 | #if !asm_mult || (uECC_SQUARE_FUNC && !asm_square) || \ |
allankliu | 0:b6fdeddc0bc9 | 376 | (uECC_SUPPORTS_secp256k1 && (uECC_OPTIMIZATION_LEVEL > 0) && \ |
allankliu | 0:b6fdeddc0bc9 | 377 | ((uECC_WORD_SIZE == 1) || (uECC_WORD_SIZE == 8))) |
allankliu | 0:b6fdeddc0bc9 | 378 | static void muladd(uECC_word_t a, |
allankliu | 0:b6fdeddc0bc9 | 379 | uECC_word_t b, |
allankliu | 0:b6fdeddc0bc9 | 380 | uECC_word_t *r0, |
allankliu | 0:b6fdeddc0bc9 | 381 | uECC_word_t *r1, |
allankliu | 0:b6fdeddc0bc9 | 382 | uECC_word_t *r2) { |
allankliu | 0:b6fdeddc0bc9 | 383 | #if uECC_WORD_SIZE == 8 && !SUPPORTS_INT128 |
allankliu | 0:b6fdeddc0bc9 | 384 | uint64_t a0 = a & 0xffffffffull; |
allankliu | 0:b6fdeddc0bc9 | 385 | uint64_t a1 = a >> 32; |
allankliu | 0:b6fdeddc0bc9 | 386 | uint64_t b0 = b & 0xffffffffull; |
allankliu | 0:b6fdeddc0bc9 | 387 | uint64_t b1 = b >> 32; |
allankliu | 0:b6fdeddc0bc9 | 388 | |
allankliu | 0:b6fdeddc0bc9 | 389 | uint64_t i0 = a0 * b0; |
allankliu | 0:b6fdeddc0bc9 | 390 | uint64_t i1 = a0 * b1; |
allankliu | 0:b6fdeddc0bc9 | 391 | uint64_t i2 = a1 * b0; |
allankliu | 0:b6fdeddc0bc9 | 392 | uint64_t i3 = a1 * b1; |
allankliu | 0:b6fdeddc0bc9 | 393 | |
allankliu | 0:b6fdeddc0bc9 | 394 | uint64_t p0, p1; |
allankliu | 0:b6fdeddc0bc9 | 395 | |
allankliu | 0:b6fdeddc0bc9 | 396 | i2 += (i0 >> 32); |
allankliu | 0:b6fdeddc0bc9 | 397 | i2 += i1; |
allankliu | 0:b6fdeddc0bc9 | 398 | if (i2 < i1) { /* overflow */ |
allankliu | 0:b6fdeddc0bc9 | 399 | i3 += 0x100000000ull; |
allankliu | 0:b6fdeddc0bc9 | 400 | } |
allankliu | 0:b6fdeddc0bc9 | 401 | |
allankliu | 0:b6fdeddc0bc9 | 402 | p0 = (i0 & 0xffffffffull) | (i2 << 32); |
allankliu | 0:b6fdeddc0bc9 | 403 | p1 = i3 + (i2 >> 32); |
allankliu | 0:b6fdeddc0bc9 | 404 | |
allankliu | 0:b6fdeddc0bc9 | 405 | *r0 += p0; |
allankliu | 0:b6fdeddc0bc9 | 406 | *r1 += (p1 + (*r0 < p0)); |
allankliu | 0:b6fdeddc0bc9 | 407 | *r2 += ((*r1 < p1) || (*r1 == p1 && *r0 < p0)); |
allankliu | 0:b6fdeddc0bc9 | 408 | #else |
allankliu | 0:b6fdeddc0bc9 | 409 | uECC_dword_t p = (uECC_dword_t)a * b; |
allankliu | 0:b6fdeddc0bc9 | 410 | uECC_dword_t r01 = ((uECC_dword_t)(*r1) << uECC_WORD_BITS) | *r0; |
allankliu | 0:b6fdeddc0bc9 | 411 | r01 += p; |
allankliu | 0:b6fdeddc0bc9 | 412 | *r2 += (r01 < p); |
allankliu | 0:b6fdeddc0bc9 | 413 | *r1 = r01 >> uECC_WORD_BITS; |
allankliu | 0:b6fdeddc0bc9 | 414 | *r0 = (uECC_word_t)r01; |
allankliu | 0:b6fdeddc0bc9 | 415 | #endif |
allankliu | 0:b6fdeddc0bc9 | 416 | } |
allankliu | 0:b6fdeddc0bc9 | 417 | #endif /* muladd needed */ |
allankliu | 0:b6fdeddc0bc9 | 418 | |
allankliu | 0:b6fdeddc0bc9 | 419 | #if !asm_mult |
allankliu | 0:b6fdeddc0bc9 | 420 | uECC_VLI_API void uECC_vli_mult(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 421 | const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 422 | const uECC_word_t *right, |
allankliu | 0:b6fdeddc0bc9 | 423 | wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 424 | uECC_word_t r0 = 0; |
allankliu | 0:b6fdeddc0bc9 | 425 | uECC_word_t r1 = 0; |
allankliu | 0:b6fdeddc0bc9 | 426 | uECC_word_t r2 = 0; |
allankliu | 0:b6fdeddc0bc9 | 427 | wordcount_t i, k; |
allankliu | 0:b6fdeddc0bc9 | 428 | |
allankliu | 0:b6fdeddc0bc9 | 429 | /* Compute each digit of result in sequence, maintaining the carries. */ |
allankliu | 0:b6fdeddc0bc9 | 430 | for (k = 0; k < num_words; ++k) { |
allankliu | 0:b6fdeddc0bc9 | 431 | for (i = 0; i <= k; ++i) { |
allankliu | 0:b6fdeddc0bc9 | 432 | muladd(left[i], right[k - i], &r0, &r1, &r2); |
allankliu | 0:b6fdeddc0bc9 | 433 | } |
allankliu | 0:b6fdeddc0bc9 | 434 | result[k] = r0; |
allankliu | 0:b6fdeddc0bc9 | 435 | r0 = r1; |
allankliu | 0:b6fdeddc0bc9 | 436 | r1 = r2; |
allankliu | 0:b6fdeddc0bc9 | 437 | r2 = 0; |
allankliu | 0:b6fdeddc0bc9 | 438 | } |
allankliu | 0:b6fdeddc0bc9 | 439 | for (k = num_words; k < num_words * 2 - 1; ++k) { |
allankliu | 0:b6fdeddc0bc9 | 440 | for (i = (k + 1) - num_words; i < num_words; ++i) { |
allankliu | 0:b6fdeddc0bc9 | 441 | muladd(left[i], right[k - i], &r0, &r1, &r2); |
allankliu | 0:b6fdeddc0bc9 | 442 | } |
allankliu | 0:b6fdeddc0bc9 | 443 | result[k] = r0; |
allankliu | 0:b6fdeddc0bc9 | 444 | r0 = r1; |
allankliu | 0:b6fdeddc0bc9 | 445 | r1 = r2; |
allankliu | 0:b6fdeddc0bc9 | 446 | r2 = 0; |
allankliu | 0:b6fdeddc0bc9 | 447 | } |
allankliu | 0:b6fdeddc0bc9 | 448 | result[num_words * 2 - 1] = r0; |
allankliu | 0:b6fdeddc0bc9 | 449 | } |
allankliu | 0:b6fdeddc0bc9 | 450 | #endif /* !asm_mult */ |
allankliu | 0:b6fdeddc0bc9 | 451 | |
allankliu | 0:b6fdeddc0bc9 | 452 | #if uECC_SQUARE_FUNC |
allankliu | 0:b6fdeddc0bc9 | 453 | |
allankliu | 0:b6fdeddc0bc9 | 454 | #if !asm_square |
allankliu | 0:b6fdeddc0bc9 | 455 | static void mul2add(uECC_word_t a, |
allankliu | 0:b6fdeddc0bc9 | 456 | uECC_word_t b, |
allankliu | 0:b6fdeddc0bc9 | 457 | uECC_word_t *r0, |
allankliu | 0:b6fdeddc0bc9 | 458 | uECC_word_t *r1, |
allankliu | 0:b6fdeddc0bc9 | 459 | uECC_word_t *r2) { |
allankliu | 0:b6fdeddc0bc9 | 460 | #if uECC_WORD_SIZE == 8 && !SUPPORTS_INT128 |
allankliu | 0:b6fdeddc0bc9 | 461 | uint64_t a0 = a & 0xffffffffull; |
allankliu | 0:b6fdeddc0bc9 | 462 | uint64_t a1 = a >> 32; |
allankliu | 0:b6fdeddc0bc9 | 463 | uint64_t b0 = b & 0xffffffffull; |
allankliu | 0:b6fdeddc0bc9 | 464 | uint64_t b1 = b >> 32; |
allankliu | 0:b6fdeddc0bc9 | 465 | |
allankliu | 0:b6fdeddc0bc9 | 466 | uint64_t i0 = a0 * b0; |
allankliu | 0:b6fdeddc0bc9 | 467 | uint64_t i1 = a0 * b1; |
allankliu | 0:b6fdeddc0bc9 | 468 | uint64_t i2 = a1 * b0; |
allankliu | 0:b6fdeddc0bc9 | 469 | uint64_t i3 = a1 * b1; |
allankliu | 0:b6fdeddc0bc9 | 470 | |
allankliu | 0:b6fdeddc0bc9 | 471 | uint64_t p0, p1; |
allankliu | 0:b6fdeddc0bc9 | 472 | |
allankliu | 0:b6fdeddc0bc9 | 473 | i2 += (i0 >> 32); |
allankliu | 0:b6fdeddc0bc9 | 474 | i2 += i1; |
allankliu | 0:b6fdeddc0bc9 | 475 | if (i2 < i1) |
allankliu | 0:b6fdeddc0bc9 | 476 | { /* overflow */ |
allankliu | 0:b6fdeddc0bc9 | 477 | i3 += 0x100000000ull; |
allankliu | 0:b6fdeddc0bc9 | 478 | } |
allankliu | 0:b6fdeddc0bc9 | 479 | |
allankliu | 0:b6fdeddc0bc9 | 480 | p0 = (i0 & 0xffffffffull) | (i2 << 32); |
allankliu | 0:b6fdeddc0bc9 | 481 | p1 = i3 + (i2 >> 32); |
allankliu | 0:b6fdeddc0bc9 | 482 | |
allankliu | 0:b6fdeddc0bc9 | 483 | *r2 += (p1 >> 63); |
allankliu | 0:b6fdeddc0bc9 | 484 | p1 = (p1 << 1) | (p0 >> 63); |
allankliu | 0:b6fdeddc0bc9 | 485 | p0 <<= 1; |
allankliu | 0:b6fdeddc0bc9 | 486 | |
allankliu | 0:b6fdeddc0bc9 | 487 | *r0 += p0; |
allankliu | 0:b6fdeddc0bc9 | 488 | *r1 += (p1 + (*r0 < p0)); |
allankliu | 0:b6fdeddc0bc9 | 489 | *r2 += ((*r1 < p1) || (*r1 == p1 && *r0 < p0)); |
allankliu | 0:b6fdeddc0bc9 | 490 | #else |
allankliu | 0:b6fdeddc0bc9 | 491 | uECC_dword_t p = (uECC_dword_t)a * b; |
allankliu | 0:b6fdeddc0bc9 | 492 | uECC_dword_t r01 = ((uECC_dword_t)(*r1) << uECC_WORD_BITS) | *r0; |
allankliu | 0:b6fdeddc0bc9 | 493 | *r2 += (p >> (uECC_WORD_BITS * 2 - 1)); |
allankliu | 0:b6fdeddc0bc9 | 494 | p *= 2; |
allankliu | 0:b6fdeddc0bc9 | 495 | r01 += p; |
allankliu | 0:b6fdeddc0bc9 | 496 | *r2 += (r01 < p); |
allankliu | 0:b6fdeddc0bc9 | 497 | *r1 = r01 >> uECC_WORD_BITS; |
allankliu | 0:b6fdeddc0bc9 | 498 | *r0 = (uECC_word_t)r01; |
allankliu | 0:b6fdeddc0bc9 | 499 | #endif |
allankliu | 0:b6fdeddc0bc9 | 500 | } |
allankliu | 0:b6fdeddc0bc9 | 501 | |
allankliu | 0:b6fdeddc0bc9 | 502 | uECC_VLI_API void uECC_vli_square(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 503 | const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 504 | wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 505 | uECC_word_t r0 = 0; |
allankliu | 0:b6fdeddc0bc9 | 506 | uECC_word_t r1 = 0; |
allankliu | 0:b6fdeddc0bc9 | 507 | uECC_word_t r2 = 0; |
allankliu | 0:b6fdeddc0bc9 | 508 | |
allankliu | 0:b6fdeddc0bc9 | 509 | wordcount_t i, k; |
allankliu | 0:b6fdeddc0bc9 | 510 | |
allankliu | 0:b6fdeddc0bc9 | 511 | for (k = 0; k < num_words * 2 - 1; ++k) { |
allankliu | 0:b6fdeddc0bc9 | 512 | uECC_word_t min = (k < num_words ? 0 : (k + 1) - num_words); |
allankliu | 0:b6fdeddc0bc9 | 513 | for (i = min; i <= k && i <= k - i; ++i) { |
allankliu | 0:b6fdeddc0bc9 | 514 | if (i < k-i) { |
allankliu | 0:b6fdeddc0bc9 | 515 | mul2add(left[i], left[k - i], &r0, &r1, &r2); |
allankliu | 0:b6fdeddc0bc9 | 516 | } else { |
allankliu | 0:b6fdeddc0bc9 | 517 | muladd(left[i], left[k - i], &r0, &r1, &r2); |
allankliu | 0:b6fdeddc0bc9 | 518 | } |
allankliu | 0:b6fdeddc0bc9 | 519 | } |
allankliu | 0:b6fdeddc0bc9 | 520 | result[k] = r0; |
allankliu | 0:b6fdeddc0bc9 | 521 | r0 = r1; |
allankliu | 0:b6fdeddc0bc9 | 522 | r1 = r2; |
allankliu | 0:b6fdeddc0bc9 | 523 | r2 = 0; |
allankliu | 0:b6fdeddc0bc9 | 524 | } |
allankliu | 0:b6fdeddc0bc9 | 525 | |
allankliu | 0:b6fdeddc0bc9 | 526 | result[num_words * 2 - 1] = r0; |
allankliu | 0:b6fdeddc0bc9 | 527 | } |
allankliu | 0:b6fdeddc0bc9 | 528 | #endif /* !asm_square */ |
allankliu | 0:b6fdeddc0bc9 | 529 | |
allankliu | 0:b6fdeddc0bc9 | 530 | #else /* uECC_SQUARE_FUNC */ |
allankliu | 0:b6fdeddc0bc9 | 531 | |
allankliu | 0:b6fdeddc0bc9 | 532 | #if uECC_ENABLE_VLI_API |
allankliu | 0:b6fdeddc0bc9 | 533 | uECC_VLI_API void uECC_vli_square(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 534 | const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 535 | wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 536 | uECC_vli_mult(result, left, left, num_words); |
allankliu | 0:b6fdeddc0bc9 | 537 | } |
allankliu | 0:b6fdeddc0bc9 | 538 | #endif /* uECC_ENABLE_VLI_API */ |
allankliu | 0:b6fdeddc0bc9 | 539 | |
allankliu | 0:b6fdeddc0bc9 | 540 | #endif /* uECC_SQUARE_FUNC */ |
allankliu | 0:b6fdeddc0bc9 | 541 | |
allankliu | 0:b6fdeddc0bc9 | 542 | /* Computes result = (left + right) % mod. |
allankliu | 0:b6fdeddc0bc9 | 543 | Assumes that left < mod and right < mod, and that result does not overlap mod. */ |
allankliu | 0:b6fdeddc0bc9 | 544 | uECC_VLI_API void uECC_vli_modAdd(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 545 | const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 546 | const uECC_word_t *right, |
allankliu | 0:b6fdeddc0bc9 | 547 | const uECC_word_t *mod, |
allankliu | 0:b6fdeddc0bc9 | 548 | wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 549 | uECC_word_t carry = uECC_vli_add(result, left, right, num_words); |
allankliu | 0:b6fdeddc0bc9 | 550 | if (carry || uECC_vli_cmp_unsafe(mod, result, num_words) != 1) { |
allankliu | 0:b6fdeddc0bc9 | 551 | /* result > mod (result = mod + remainder), so subtract mod to get remainder. */ |
allankliu | 0:b6fdeddc0bc9 | 552 | uECC_vli_sub(result, result, mod, num_words); |
allankliu | 0:b6fdeddc0bc9 | 553 | } |
allankliu | 0:b6fdeddc0bc9 | 554 | } |
allankliu | 0:b6fdeddc0bc9 | 555 | |
allankliu | 0:b6fdeddc0bc9 | 556 | /* Computes result = (left - right) % mod. |
allankliu | 0:b6fdeddc0bc9 | 557 | Assumes that left < mod and right < mod, and that result does not overlap mod. */ |
allankliu | 0:b6fdeddc0bc9 | 558 | uECC_VLI_API void uECC_vli_modSub(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 559 | const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 560 | const uECC_word_t *right, |
allankliu | 0:b6fdeddc0bc9 | 561 | const uECC_word_t *mod, |
allankliu | 0:b6fdeddc0bc9 | 562 | wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 563 | uECC_word_t l_borrow = uECC_vli_sub(result, left, right, num_words); |
allankliu | 0:b6fdeddc0bc9 | 564 | if (l_borrow) { |
allankliu | 0:b6fdeddc0bc9 | 565 | /* In this case, result == -diff == (max int) - diff. Since -x % d == d - x, |
allankliu | 0:b6fdeddc0bc9 | 566 | we can get the correct result from result + mod (with overflow). */ |
allankliu | 0:b6fdeddc0bc9 | 567 | uECC_vli_add(result, result, mod, num_words); |
allankliu | 0:b6fdeddc0bc9 | 568 | } |
allankliu | 0:b6fdeddc0bc9 | 569 | } |
allankliu | 0:b6fdeddc0bc9 | 570 | |
allankliu | 0:b6fdeddc0bc9 | 571 | /* Computes result = product % mod, where product is 2N words long. */ |
allankliu | 0:b6fdeddc0bc9 | 572 | /* Currently only designed to work for curve_p or curve_n. */ |
allankliu | 0:b6fdeddc0bc9 | 573 | uECC_VLI_API void uECC_vli_mmod(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 574 | uECC_word_t *product, |
allankliu | 0:b6fdeddc0bc9 | 575 | const uECC_word_t *mod, |
allankliu | 0:b6fdeddc0bc9 | 576 | wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 577 | uECC_word_t mod_multiple[2 * uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 578 | uECC_word_t tmp[2 * uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 579 | uECC_word_t *v[2] = {tmp, product}; |
allankliu | 0:b6fdeddc0bc9 | 580 | uECC_word_t index; |
allankliu | 0:b6fdeddc0bc9 | 581 | |
allankliu | 0:b6fdeddc0bc9 | 582 | /* Shift mod so its highest set bit is at the maximum position. */ |
allankliu | 0:b6fdeddc0bc9 | 583 | bitcount_t shift = (num_words * 2 * uECC_WORD_BITS) - uECC_vli_numBits(mod, num_words); |
allankliu | 0:b6fdeddc0bc9 | 584 | wordcount_t word_shift = shift / uECC_WORD_BITS; |
allankliu | 0:b6fdeddc0bc9 | 585 | wordcount_t bit_shift = shift % uECC_WORD_BITS; |
allankliu | 0:b6fdeddc0bc9 | 586 | uECC_word_t carry = 0; |
allankliu | 0:b6fdeddc0bc9 | 587 | uECC_vli_clear(mod_multiple, word_shift); |
allankliu | 0:b6fdeddc0bc9 | 588 | if (bit_shift > 0) { |
allankliu | 0:b6fdeddc0bc9 | 589 | for(index = 0; index < (uECC_word_t)num_words; ++index) { |
allankliu | 0:b6fdeddc0bc9 | 590 | mod_multiple[word_shift + index] = (mod[index] << bit_shift) | carry; |
allankliu | 0:b6fdeddc0bc9 | 591 | carry = mod[index] >> (uECC_WORD_BITS - bit_shift); |
allankliu | 0:b6fdeddc0bc9 | 592 | } |
allankliu | 0:b6fdeddc0bc9 | 593 | } else { |
allankliu | 0:b6fdeddc0bc9 | 594 | uECC_vli_set(mod_multiple + word_shift, mod, num_words); |
allankliu | 0:b6fdeddc0bc9 | 595 | } |
allankliu | 0:b6fdeddc0bc9 | 596 | |
allankliu | 0:b6fdeddc0bc9 | 597 | for (index = 1; shift >= 0; --shift) { |
allankliu | 0:b6fdeddc0bc9 | 598 | uECC_word_t borrow = 0; |
allankliu | 0:b6fdeddc0bc9 | 599 | wordcount_t i; |
allankliu | 0:b6fdeddc0bc9 | 600 | for (i = 0; i < num_words * 2; ++i) { |
allankliu | 0:b6fdeddc0bc9 | 601 | uECC_word_t diff = v[index][i] - mod_multiple[i] - borrow; |
allankliu | 0:b6fdeddc0bc9 | 602 | if (diff != v[index][i]) { |
allankliu | 0:b6fdeddc0bc9 | 603 | borrow = (diff > v[index][i]); |
allankliu | 0:b6fdeddc0bc9 | 604 | } |
allankliu | 0:b6fdeddc0bc9 | 605 | v[1 - index][i] = diff; |
allankliu | 0:b6fdeddc0bc9 | 606 | } |
allankliu | 0:b6fdeddc0bc9 | 607 | index = !(index ^ borrow); /* Swap the index if there was no borrow */ |
allankliu | 0:b6fdeddc0bc9 | 608 | uECC_vli_rshift1(mod_multiple, num_words); |
allankliu | 0:b6fdeddc0bc9 | 609 | mod_multiple[num_words - 1] |= mod_multiple[num_words] << (uECC_WORD_BITS - 1); |
allankliu | 0:b6fdeddc0bc9 | 610 | uECC_vli_rshift1(mod_multiple + num_words, num_words); |
allankliu | 0:b6fdeddc0bc9 | 611 | } |
allankliu | 0:b6fdeddc0bc9 | 612 | uECC_vli_set(result, v[index], num_words); |
allankliu | 0:b6fdeddc0bc9 | 613 | } |
allankliu | 0:b6fdeddc0bc9 | 614 | |
allankliu | 0:b6fdeddc0bc9 | 615 | /* Computes result = (left * right) % mod. */ |
allankliu | 0:b6fdeddc0bc9 | 616 | uECC_VLI_API void uECC_vli_modMult(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 617 | const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 618 | const uECC_word_t *right, |
allankliu | 0:b6fdeddc0bc9 | 619 | const uECC_word_t *mod, |
allankliu | 0:b6fdeddc0bc9 | 620 | wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 621 | uECC_word_t product[2 * uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 622 | uECC_vli_mult(product, left, right, num_words); |
allankliu | 0:b6fdeddc0bc9 | 623 | uECC_vli_mmod(result, product, mod, num_words); |
allankliu | 0:b6fdeddc0bc9 | 624 | } |
allankliu | 0:b6fdeddc0bc9 | 625 | |
allankliu | 0:b6fdeddc0bc9 | 626 | uECC_VLI_API void uECC_vli_modMult_fast(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 627 | const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 628 | const uECC_word_t *right, |
allankliu | 0:b6fdeddc0bc9 | 629 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 630 | uECC_word_t product[2 * uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 631 | uECC_vli_mult(product, left, right, curve->num_words); |
allankliu | 0:b6fdeddc0bc9 | 632 | #if (uECC_OPTIMIZATION_LEVEL > 0) |
allankliu | 0:b6fdeddc0bc9 | 633 | curve->mmod_fast(result, product); |
allankliu | 0:b6fdeddc0bc9 | 634 | #else |
allankliu | 0:b6fdeddc0bc9 | 635 | uECC_vli_mmod(result, product, curve->p, curve->num_words); |
allankliu | 0:b6fdeddc0bc9 | 636 | #endif |
allankliu | 0:b6fdeddc0bc9 | 637 | } |
allankliu | 0:b6fdeddc0bc9 | 638 | |
allankliu | 0:b6fdeddc0bc9 | 639 | #if uECC_SQUARE_FUNC |
allankliu | 0:b6fdeddc0bc9 | 640 | |
allankliu | 0:b6fdeddc0bc9 | 641 | #if uECC_ENABLE_VLI_API |
allankliu | 0:b6fdeddc0bc9 | 642 | /* Computes result = left^2 % mod. */ |
allankliu | 0:b6fdeddc0bc9 | 643 | uECC_VLI_API void uECC_vli_modSquare(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 644 | const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 645 | const uECC_word_t *mod, |
allankliu | 0:b6fdeddc0bc9 | 646 | wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 647 | uECC_word_t product[2 * uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 648 | uECC_vli_square(product, left, num_words); |
allankliu | 0:b6fdeddc0bc9 | 649 | uECC_vli_mmod(result, product, mod, num_words); |
allankliu | 0:b6fdeddc0bc9 | 650 | } |
allankliu | 0:b6fdeddc0bc9 | 651 | #endif /* uECC_ENABLE_VLI_API */ |
allankliu | 0:b6fdeddc0bc9 | 652 | |
allankliu | 0:b6fdeddc0bc9 | 653 | uECC_VLI_API void uECC_vli_modSquare_fast(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 654 | const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 655 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 656 | uECC_word_t product[2 * uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 657 | uECC_vli_square(product, left, curve->num_words); |
allankliu | 0:b6fdeddc0bc9 | 658 | #if (uECC_OPTIMIZATION_LEVEL > 0) |
allankliu | 0:b6fdeddc0bc9 | 659 | curve->mmod_fast(result, product); |
allankliu | 0:b6fdeddc0bc9 | 660 | #else |
allankliu | 0:b6fdeddc0bc9 | 661 | uECC_vli_mmod(result, product, curve->p, curve->num_words); |
allankliu | 0:b6fdeddc0bc9 | 662 | #endif |
allankliu | 0:b6fdeddc0bc9 | 663 | } |
allankliu | 0:b6fdeddc0bc9 | 664 | |
allankliu | 0:b6fdeddc0bc9 | 665 | #else /* uECC_SQUARE_FUNC */ |
allankliu | 0:b6fdeddc0bc9 | 666 | |
allankliu | 0:b6fdeddc0bc9 | 667 | #if uECC_ENABLE_VLI_API |
allankliu | 0:b6fdeddc0bc9 | 668 | uECC_VLI_API void uECC_vli_modSquare(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 669 | const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 670 | const uECC_word_t *mod, |
allankliu | 0:b6fdeddc0bc9 | 671 | wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 672 | uECC_vli_modMult(result, left, left, mod, num_words); |
allankliu | 0:b6fdeddc0bc9 | 673 | } |
allankliu | 0:b6fdeddc0bc9 | 674 | #endif /* uECC_ENABLE_VLI_API */ |
allankliu | 0:b6fdeddc0bc9 | 675 | |
allankliu | 0:b6fdeddc0bc9 | 676 | uECC_VLI_API void uECC_vli_modSquare_fast(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 677 | const uECC_word_t *left, |
allankliu | 0:b6fdeddc0bc9 | 678 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 679 | uECC_vli_modMult_fast(result, left, left, curve); |
allankliu | 0:b6fdeddc0bc9 | 680 | } |
allankliu | 0:b6fdeddc0bc9 | 681 | |
allankliu | 0:b6fdeddc0bc9 | 682 | #endif /* uECC_SQUARE_FUNC */ |
allankliu | 0:b6fdeddc0bc9 | 683 | |
allankliu | 0:b6fdeddc0bc9 | 684 | #define EVEN(vli) (!(vli[0] & 1)) |
allankliu | 0:b6fdeddc0bc9 | 685 | static void vli_modInv_update(uECC_word_t *uv, |
allankliu | 0:b6fdeddc0bc9 | 686 | const uECC_word_t *mod, |
allankliu | 0:b6fdeddc0bc9 | 687 | wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 688 | uECC_word_t carry = 0; |
allankliu | 0:b6fdeddc0bc9 | 689 | if (!EVEN(uv)) { |
allankliu | 0:b6fdeddc0bc9 | 690 | carry = uECC_vli_add(uv, uv, mod, num_words); |
allankliu | 0:b6fdeddc0bc9 | 691 | } |
allankliu | 0:b6fdeddc0bc9 | 692 | uECC_vli_rshift1(uv, num_words); |
allankliu | 0:b6fdeddc0bc9 | 693 | if (carry) { |
allankliu | 0:b6fdeddc0bc9 | 694 | uv[num_words - 1] |= HIGH_BIT_SET; |
allankliu | 0:b6fdeddc0bc9 | 695 | } |
allankliu | 0:b6fdeddc0bc9 | 696 | } |
allankliu | 0:b6fdeddc0bc9 | 697 | |
allankliu | 0:b6fdeddc0bc9 | 698 | /* Computes result = (1 / input) % mod. All VLIs are the same size. |
allankliu | 0:b6fdeddc0bc9 | 699 | See "From Euclid's GCD to Montgomery Multiplication to the Great Divide" */ |
allankliu | 0:b6fdeddc0bc9 | 700 | uECC_VLI_API void uECC_vli_modInv(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 701 | const uECC_word_t *input, |
allankliu | 0:b6fdeddc0bc9 | 702 | const uECC_word_t *mod, |
allankliu | 0:b6fdeddc0bc9 | 703 | wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 704 | uECC_word_t a[uECC_MAX_WORDS], b[uECC_MAX_WORDS], u[uECC_MAX_WORDS], v[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 705 | cmpresult_t cmpResult; |
allankliu | 0:b6fdeddc0bc9 | 706 | |
allankliu | 0:b6fdeddc0bc9 | 707 | if (uECC_vli_isZero(input, num_words)) { |
allankliu | 0:b6fdeddc0bc9 | 708 | uECC_vli_clear(result, num_words); |
allankliu | 0:b6fdeddc0bc9 | 709 | return; |
allankliu | 0:b6fdeddc0bc9 | 710 | } |
allankliu | 0:b6fdeddc0bc9 | 711 | |
allankliu | 0:b6fdeddc0bc9 | 712 | uECC_vli_set(a, input, num_words); |
allankliu | 0:b6fdeddc0bc9 | 713 | uECC_vli_set(b, mod, num_words); |
allankliu | 0:b6fdeddc0bc9 | 714 | uECC_vli_clear(u, num_words); |
allankliu | 0:b6fdeddc0bc9 | 715 | u[0] = 1; |
allankliu | 0:b6fdeddc0bc9 | 716 | uECC_vli_clear(v, num_words); |
allankliu | 0:b6fdeddc0bc9 | 717 | while ((cmpResult = uECC_vli_cmp_unsafe(a, b, num_words)) != 0) { |
allankliu | 0:b6fdeddc0bc9 | 718 | if (EVEN(a)) { |
allankliu | 0:b6fdeddc0bc9 | 719 | uECC_vli_rshift1(a, num_words); |
allankliu | 0:b6fdeddc0bc9 | 720 | vli_modInv_update(u, mod, num_words); |
allankliu | 0:b6fdeddc0bc9 | 721 | } else if (EVEN(b)) { |
allankliu | 0:b6fdeddc0bc9 | 722 | uECC_vli_rshift1(b, num_words); |
allankliu | 0:b6fdeddc0bc9 | 723 | vli_modInv_update(v, mod, num_words); |
allankliu | 0:b6fdeddc0bc9 | 724 | } else if (cmpResult > 0) { |
allankliu | 0:b6fdeddc0bc9 | 725 | uECC_vli_sub(a, a, b, num_words); |
allankliu | 0:b6fdeddc0bc9 | 726 | uECC_vli_rshift1(a, num_words); |
allankliu | 0:b6fdeddc0bc9 | 727 | if (uECC_vli_cmp_unsafe(u, v, num_words) < 0) { |
allankliu | 0:b6fdeddc0bc9 | 728 | uECC_vli_add(u, u, mod, num_words); |
allankliu | 0:b6fdeddc0bc9 | 729 | } |
allankliu | 0:b6fdeddc0bc9 | 730 | uECC_vli_sub(u, u, v, num_words); |
allankliu | 0:b6fdeddc0bc9 | 731 | vli_modInv_update(u, mod, num_words); |
allankliu | 0:b6fdeddc0bc9 | 732 | } else { |
allankliu | 0:b6fdeddc0bc9 | 733 | uECC_vli_sub(b, b, a, num_words); |
allankliu | 0:b6fdeddc0bc9 | 734 | uECC_vli_rshift1(b, num_words); |
allankliu | 0:b6fdeddc0bc9 | 735 | if (uECC_vli_cmp_unsafe(v, u, num_words) < 0) { |
allankliu | 0:b6fdeddc0bc9 | 736 | uECC_vli_add(v, v, mod, num_words); |
allankliu | 0:b6fdeddc0bc9 | 737 | } |
allankliu | 0:b6fdeddc0bc9 | 738 | uECC_vli_sub(v, v, u, num_words); |
allankliu | 0:b6fdeddc0bc9 | 739 | vli_modInv_update(v, mod, num_words); |
allankliu | 0:b6fdeddc0bc9 | 740 | } |
allankliu | 0:b6fdeddc0bc9 | 741 | } |
allankliu | 0:b6fdeddc0bc9 | 742 | uECC_vli_set(result, u, num_words); |
allankliu | 0:b6fdeddc0bc9 | 743 | } |
allankliu | 0:b6fdeddc0bc9 | 744 | |
allankliu | 0:b6fdeddc0bc9 | 745 | /* ------ Point operations ------ */ |
allankliu | 0:b6fdeddc0bc9 | 746 | |
allankliu | 0:b6fdeddc0bc9 | 747 | //#include "curve-specific.inc" |
allankliu | 0:b6fdeddc0bc9 | 748 | #include "curve-specific.h" |
allankliu | 0:b6fdeddc0bc9 | 749 | |
allankliu | 0:b6fdeddc0bc9 | 750 | /* Returns 1 if 'point' is the point at infinity, 0 otherwise. */ |
allankliu | 0:b6fdeddc0bc9 | 751 | #define EccPoint_isZero(point, curve) uECC_vli_isZero((point), (curve)->num_words * 2) |
allankliu | 0:b6fdeddc0bc9 | 752 | |
allankliu | 0:b6fdeddc0bc9 | 753 | /* Point multiplication algorithm using Montgomery's ladder with co-Z coordinates. |
allankliu | 0:b6fdeddc0bc9 | 754 | From http://eprint.iacr.org/2011/338.pdf |
allankliu | 0:b6fdeddc0bc9 | 755 | */ |
allankliu | 0:b6fdeddc0bc9 | 756 | |
allankliu | 0:b6fdeddc0bc9 | 757 | /* Modify (x1, y1) => (x1 * z^2, y1 * z^3) */ |
allankliu | 0:b6fdeddc0bc9 | 758 | static void apply_z(uECC_word_t * X1, |
allankliu | 0:b6fdeddc0bc9 | 759 | uECC_word_t * Y1, |
allankliu | 0:b6fdeddc0bc9 | 760 | const uECC_word_t * const Z, |
allankliu | 0:b6fdeddc0bc9 | 761 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 762 | uECC_word_t t1[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 763 | |
allankliu | 0:b6fdeddc0bc9 | 764 | uECC_vli_modSquare_fast(t1, Z, curve); /* z^2 */ |
allankliu | 0:b6fdeddc0bc9 | 765 | uECC_vli_modMult_fast(X1, X1, t1, curve); /* x1 * z^2 */ |
allankliu | 0:b6fdeddc0bc9 | 766 | uECC_vli_modMult_fast(t1, t1, Z, curve); /* z^3 */ |
allankliu | 0:b6fdeddc0bc9 | 767 | uECC_vli_modMult_fast(Y1, Y1, t1, curve); /* y1 * z^3 */ |
allankliu | 0:b6fdeddc0bc9 | 768 | } |
allankliu | 0:b6fdeddc0bc9 | 769 | |
allankliu | 0:b6fdeddc0bc9 | 770 | /* P = (x1, y1) => 2P, (x2, y2) => P' */ |
allankliu | 0:b6fdeddc0bc9 | 771 | static void XYcZ_initial_double(uECC_word_t * X1, |
allankliu | 0:b6fdeddc0bc9 | 772 | uECC_word_t * Y1, |
allankliu | 0:b6fdeddc0bc9 | 773 | uECC_word_t * X2, |
allankliu | 0:b6fdeddc0bc9 | 774 | uECC_word_t * Y2, |
allankliu | 0:b6fdeddc0bc9 | 775 | const uECC_word_t * const initial_Z, |
allankliu | 0:b6fdeddc0bc9 | 776 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 777 | uECC_word_t z[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 778 | wordcount_t num_words = curve->num_words; |
allankliu | 0:b6fdeddc0bc9 | 779 | if (initial_Z) { |
allankliu | 0:b6fdeddc0bc9 | 780 | uECC_vli_set(z, initial_Z, num_words); |
allankliu | 0:b6fdeddc0bc9 | 781 | } else { |
allankliu | 0:b6fdeddc0bc9 | 782 | uECC_vli_clear(z, num_words); |
allankliu | 0:b6fdeddc0bc9 | 783 | z[0] = 1; |
allankliu | 0:b6fdeddc0bc9 | 784 | } |
allankliu | 0:b6fdeddc0bc9 | 785 | |
allankliu | 0:b6fdeddc0bc9 | 786 | uECC_vli_set(X2, X1, num_words); |
allankliu | 0:b6fdeddc0bc9 | 787 | uECC_vli_set(Y2, Y1, num_words); |
allankliu | 0:b6fdeddc0bc9 | 788 | |
allankliu | 0:b6fdeddc0bc9 | 789 | apply_z(X1, Y1, z, curve); |
allankliu | 0:b6fdeddc0bc9 | 790 | curve->double_jacobian(X1, Y1, z, curve); |
allankliu | 0:b6fdeddc0bc9 | 791 | apply_z(X2, Y2, z, curve); |
allankliu | 0:b6fdeddc0bc9 | 792 | } |
allankliu | 0:b6fdeddc0bc9 | 793 | |
allankliu | 0:b6fdeddc0bc9 | 794 | /* Input P = (x1, y1, Z), Q = (x2, y2, Z) |
allankliu | 0:b6fdeddc0bc9 | 795 | Output P' = (x1', y1', Z3), P + Q = (x3, y3, Z3) |
allankliu | 0:b6fdeddc0bc9 | 796 | or P => P', Q => P + Q |
allankliu | 0:b6fdeddc0bc9 | 797 | */ |
allankliu | 0:b6fdeddc0bc9 | 798 | static void XYcZ_add(uECC_word_t * X1, |
allankliu | 0:b6fdeddc0bc9 | 799 | uECC_word_t * Y1, |
allankliu | 0:b6fdeddc0bc9 | 800 | uECC_word_t * X2, |
allankliu | 0:b6fdeddc0bc9 | 801 | uECC_word_t * Y2, |
allankliu | 0:b6fdeddc0bc9 | 802 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 803 | /* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */ |
allankliu | 0:b6fdeddc0bc9 | 804 | uECC_word_t t5[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 805 | wordcount_t num_words = curve->num_words; |
allankliu | 0:b6fdeddc0bc9 | 806 | |
allankliu | 0:b6fdeddc0bc9 | 807 | uECC_vli_modSub(t5, X2, X1, curve->p, num_words); /* t5 = x2 - x1 */ |
allankliu | 0:b6fdeddc0bc9 | 808 | uECC_vli_modSquare_fast(t5, t5, curve); /* t5 = (x2 - x1)^2 = A */ |
allankliu | 0:b6fdeddc0bc9 | 809 | uECC_vli_modMult_fast(X1, X1, t5, curve); /* t1 = x1*A = B */ |
allankliu | 0:b6fdeddc0bc9 | 810 | uECC_vli_modMult_fast(X2, X2, t5, curve); /* t3 = x2*A = C */ |
allankliu | 0:b6fdeddc0bc9 | 811 | uECC_vli_modSub(Y2, Y2, Y1, curve->p, num_words); /* t4 = y2 - y1 */ |
allankliu | 0:b6fdeddc0bc9 | 812 | uECC_vli_modSquare_fast(t5, Y2, curve); /* t5 = (y2 - y1)^2 = D */ |
allankliu | 0:b6fdeddc0bc9 | 813 | |
allankliu | 0:b6fdeddc0bc9 | 814 | uECC_vli_modSub(t5, t5, X1, curve->p, num_words); /* t5 = D - B */ |
allankliu | 0:b6fdeddc0bc9 | 815 | uECC_vli_modSub(t5, t5, X2, curve->p, num_words); /* t5 = D - B - C = x3 */ |
allankliu | 0:b6fdeddc0bc9 | 816 | uECC_vli_modSub(X2, X2, X1, curve->p, num_words); /* t3 = C - B */ |
allankliu | 0:b6fdeddc0bc9 | 817 | uECC_vli_modMult_fast(Y1, Y1, X2, curve); /* t2 = y1*(C - B) */ |
allankliu | 0:b6fdeddc0bc9 | 818 | uECC_vli_modSub(X2, X1, t5, curve->p, num_words); /* t3 = B - x3 */ |
allankliu | 0:b6fdeddc0bc9 | 819 | uECC_vli_modMult_fast(Y2, Y2, X2, curve); /* t4 = (y2 - y1)*(B - x3) */ |
allankliu | 0:b6fdeddc0bc9 | 820 | uECC_vli_modSub(Y2, Y2, Y1, curve->p, num_words); /* t4 = y3 */ |
allankliu | 0:b6fdeddc0bc9 | 821 | |
allankliu | 0:b6fdeddc0bc9 | 822 | uECC_vli_set(X2, t5, num_words); |
allankliu | 0:b6fdeddc0bc9 | 823 | } |
allankliu | 0:b6fdeddc0bc9 | 824 | |
allankliu | 0:b6fdeddc0bc9 | 825 | /* Input P = (x1, y1, Z), Q = (x2, y2, Z) |
allankliu | 0:b6fdeddc0bc9 | 826 | Output P + Q = (x3, y3, Z3), P - Q = (x3', y3', Z3) |
allankliu | 0:b6fdeddc0bc9 | 827 | or P => P - Q, Q => P + Q |
allankliu | 0:b6fdeddc0bc9 | 828 | */ |
allankliu | 0:b6fdeddc0bc9 | 829 | static void XYcZ_addC(uECC_word_t * X1, |
allankliu | 0:b6fdeddc0bc9 | 830 | uECC_word_t * Y1, |
allankliu | 0:b6fdeddc0bc9 | 831 | uECC_word_t * X2, |
allankliu | 0:b6fdeddc0bc9 | 832 | uECC_word_t * Y2, |
allankliu | 0:b6fdeddc0bc9 | 833 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 834 | /* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */ |
allankliu | 0:b6fdeddc0bc9 | 835 | uECC_word_t t5[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 836 | uECC_word_t t6[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 837 | uECC_word_t t7[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 838 | wordcount_t num_words = curve->num_words; |
allankliu | 0:b6fdeddc0bc9 | 839 | |
allankliu | 0:b6fdeddc0bc9 | 840 | uECC_vli_modSub(t5, X2, X1, curve->p, num_words); /* t5 = x2 - x1 */ |
allankliu | 0:b6fdeddc0bc9 | 841 | uECC_vli_modSquare_fast(t5, t5, curve); /* t5 = (x2 - x1)^2 = A */ |
allankliu | 0:b6fdeddc0bc9 | 842 | uECC_vli_modMult_fast(X1, X1, t5, curve); /* t1 = x1*A = B */ |
allankliu | 0:b6fdeddc0bc9 | 843 | uECC_vli_modMult_fast(X2, X2, t5, curve); /* t3 = x2*A = C */ |
allankliu | 0:b6fdeddc0bc9 | 844 | uECC_vli_modAdd(t5, Y2, Y1, curve->p, num_words); /* t5 = y2 + y1 */ |
allankliu | 0:b6fdeddc0bc9 | 845 | uECC_vli_modSub(Y2, Y2, Y1, curve->p, num_words); /* t4 = y2 - y1 */ |
allankliu | 0:b6fdeddc0bc9 | 846 | |
allankliu | 0:b6fdeddc0bc9 | 847 | uECC_vli_modSub(t6, X2, X1, curve->p, num_words); /* t6 = C - B */ |
allankliu | 0:b6fdeddc0bc9 | 848 | uECC_vli_modMult_fast(Y1, Y1, t6, curve); /* t2 = y1 * (C - B) = E */ |
allankliu | 0:b6fdeddc0bc9 | 849 | uECC_vli_modAdd(t6, X1, X2, curve->p, num_words); /* t6 = B + C */ |
allankliu | 0:b6fdeddc0bc9 | 850 | uECC_vli_modSquare_fast(X2, Y2, curve); /* t3 = (y2 - y1)^2 = D */ |
allankliu | 0:b6fdeddc0bc9 | 851 | uECC_vli_modSub(X2, X2, t6, curve->p, num_words); /* t3 = D - (B + C) = x3 */ |
allankliu | 0:b6fdeddc0bc9 | 852 | |
allankliu | 0:b6fdeddc0bc9 | 853 | uECC_vli_modSub(t7, X1, X2, curve->p, num_words); /* t7 = B - x3 */ |
allankliu | 0:b6fdeddc0bc9 | 854 | uECC_vli_modMult_fast(Y2, Y2, t7, curve); /* t4 = (y2 - y1)*(B - x3) */ |
allankliu | 0:b6fdeddc0bc9 | 855 | uECC_vli_modSub(Y2, Y2, Y1, curve->p, num_words); /* t4 = (y2 - y1)*(B - x3) - E = y3 */ |
allankliu | 0:b6fdeddc0bc9 | 856 | |
allankliu | 0:b6fdeddc0bc9 | 857 | uECC_vli_modSquare_fast(t7, t5, curve); /* t7 = (y2 + y1)^2 = F */ |
allankliu | 0:b6fdeddc0bc9 | 858 | uECC_vli_modSub(t7, t7, t6, curve->p, num_words); /* t7 = F - (B + C) = x3' */ |
allankliu | 0:b6fdeddc0bc9 | 859 | uECC_vli_modSub(t6, t7, X1, curve->p, num_words); /* t6 = x3' - B */ |
allankliu | 0:b6fdeddc0bc9 | 860 | uECC_vli_modMult_fast(t6, t6, t5, curve); /* t6 = (y2+y1)*(x3' - B) */ |
allankliu | 0:b6fdeddc0bc9 | 861 | uECC_vli_modSub(Y1, t6, Y1, curve->p, num_words); /* t2 = (y2+y1)*(x3' - B) - E = y3' */ |
allankliu | 0:b6fdeddc0bc9 | 862 | |
allankliu | 0:b6fdeddc0bc9 | 863 | uECC_vli_set(X1, t7, num_words); |
allankliu | 0:b6fdeddc0bc9 | 864 | } |
allankliu | 0:b6fdeddc0bc9 | 865 | |
allankliu | 0:b6fdeddc0bc9 | 866 | /* result may overlap point. */ |
allankliu | 0:b6fdeddc0bc9 | 867 | static void EccPoint_mult(uECC_word_t * result, |
allankliu | 0:b6fdeddc0bc9 | 868 | const uECC_word_t * point, |
allankliu | 0:b6fdeddc0bc9 | 869 | const uECC_word_t * scalar, |
allankliu | 0:b6fdeddc0bc9 | 870 | const uECC_word_t * initial_Z, |
allankliu | 0:b6fdeddc0bc9 | 871 | bitcount_t num_bits, |
allankliu | 0:b6fdeddc0bc9 | 872 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 873 | /* R0 and R1 */ |
allankliu | 0:b6fdeddc0bc9 | 874 | uECC_word_t Rx[2][uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 875 | uECC_word_t Ry[2][uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 876 | uECC_word_t z[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 877 | bitcount_t i; |
allankliu | 0:b6fdeddc0bc9 | 878 | uECC_word_t nb; |
allankliu | 0:b6fdeddc0bc9 | 879 | wordcount_t num_words = curve->num_words; |
allankliu | 0:b6fdeddc0bc9 | 880 | |
allankliu | 0:b6fdeddc0bc9 | 881 | uECC_vli_set(Rx[1], point, num_words); |
allankliu | 0:b6fdeddc0bc9 | 882 | uECC_vli_set(Ry[1], point + num_words, num_words); |
allankliu | 0:b6fdeddc0bc9 | 883 | |
allankliu | 0:b6fdeddc0bc9 | 884 | XYcZ_initial_double(Rx[1], Ry[1], Rx[0], Ry[0], initial_Z, curve); |
allankliu | 0:b6fdeddc0bc9 | 885 | |
allankliu | 0:b6fdeddc0bc9 | 886 | for (i = num_bits - 2; i > 0; --i) { |
allankliu | 0:b6fdeddc0bc9 | 887 | nb = !uECC_vli_testBit(scalar, i); |
allankliu | 0:b6fdeddc0bc9 | 888 | XYcZ_addC(Rx[1 - nb], Ry[1 - nb], Rx[nb], Ry[nb], curve); |
allankliu | 0:b6fdeddc0bc9 | 889 | XYcZ_add(Rx[nb], Ry[nb], Rx[1 - nb], Ry[1 - nb], curve); |
allankliu | 0:b6fdeddc0bc9 | 890 | } |
allankliu | 0:b6fdeddc0bc9 | 891 | |
allankliu | 0:b6fdeddc0bc9 | 892 | nb = !uECC_vli_testBit(scalar, 0); |
allankliu | 0:b6fdeddc0bc9 | 893 | XYcZ_addC(Rx[1 - nb], Ry[1 - nb], Rx[nb], Ry[nb], curve); |
allankliu | 0:b6fdeddc0bc9 | 894 | |
allankliu | 0:b6fdeddc0bc9 | 895 | /* Find final 1/Z value. */ |
allankliu | 0:b6fdeddc0bc9 | 896 | uECC_vli_modSub(z, Rx[1], Rx[0], curve->p, num_words); /* X1 - X0 */ |
allankliu | 0:b6fdeddc0bc9 | 897 | uECC_vli_modMult_fast(z, z, Ry[1 - nb], curve); /* Yb * (X1 - X0) */ |
allankliu | 0:b6fdeddc0bc9 | 898 | uECC_vli_modMult_fast(z, z, point, curve); /* xP * Yb * (X1 - X0) */ |
allankliu | 0:b6fdeddc0bc9 | 899 | uECC_vli_modInv(z, z, curve->p, num_words); /* 1 / (xP * Yb * (X1 - X0)) */ |
allankliu | 0:b6fdeddc0bc9 | 900 | /* yP / (xP * Yb * (X1 - X0)) */ |
allankliu | 0:b6fdeddc0bc9 | 901 | uECC_vli_modMult_fast(z, z, point + num_words, curve); |
allankliu | 0:b6fdeddc0bc9 | 902 | uECC_vli_modMult_fast(z, z, Rx[1 - nb], curve); /* Xb * yP / (xP * Yb * (X1 - X0)) */ |
allankliu | 0:b6fdeddc0bc9 | 903 | /* End 1/Z calculation */ |
allankliu | 0:b6fdeddc0bc9 | 904 | |
allankliu | 0:b6fdeddc0bc9 | 905 | XYcZ_add(Rx[nb], Ry[nb], Rx[1 - nb], Ry[1 - nb], curve); |
allankliu | 0:b6fdeddc0bc9 | 906 | apply_z(Rx[0], Ry[0], z, curve); |
allankliu | 0:b6fdeddc0bc9 | 907 | |
allankliu | 0:b6fdeddc0bc9 | 908 | uECC_vli_set(result, Rx[0], num_words); |
allankliu | 0:b6fdeddc0bc9 | 909 | uECC_vli_set(result + num_words, Ry[0], num_words); |
allankliu | 0:b6fdeddc0bc9 | 910 | } |
allankliu | 0:b6fdeddc0bc9 | 911 | |
allankliu | 0:b6fdeddc0bc9 | 912 | static uECC_word_t regularize_k(const uECC_word_t * const k, |
allankliu | 0:b6fdeddc0bc9 | 913 | uECC_word_t *k0, |
allankliu | 0:b6fdeddc0bc9 | 914 | uECC_word_t *k1, |
allankliu | 0:b6fdeddc0bc9 | 915 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 916 | wordcount_t num_n_words = BITS_TO_WORDS(curve->num_n_bits); |
allankliu | 0:b6fdeddc0bc9 | 917 | bitcount_t num_n_bits = curve->num_n_bits; |
allankliu | 0:b6fdeddc0bc9 | 918 | uECC_word_t carry = uECC_vli_add(k0, k, curve->n, num_n_words) || |
allankliu | 0:b6fdeddc0bc9 | 919 | (num_n_bits < ((bitcount_t)num_n_words * uECC_WORD_SIZE * 8) && |
allankliu | 0:b6fdeddc0bc9 | 920 | uECC_vli_testBit(k0, num_n_bits)); |
allankliu | 0:b6fdeddc0bc9 | 921 | uECC_vli_add(k1, k0, curve->n, num_n_words); |
allankliu | 0:b6fdeddc0bc9 | 922 | return carry; |
allankliu | 0:b6fdeddc0bc9 | 923 | } |
allankliu | 0:b6fdeddc0bc9 | 924 | |
allankliu | 0:b6fdeddc0bc9 | 925 | static uECC_word_t EccPoint_compute_public_key(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 926 | uECC_word_t *private_key, |
allankliu | 0:b6fdeddc0bc9 | 927 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 928 | uECC_word_t tmp1[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 929 | uECC_word_t tmp2[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 930 | uECC_word_t *p2[2] = {tmp1, tmp2}; |
allankliu | 0:b6fdeddc0bc9 | 931 | uECC_word_t carry; |
allankliu | 0:b6fdeddc0bc9 | 932 | |
allankliu | 0:b6fdeddc0bc9 | 933 | /* Regularize the bitcount for the private key so that attackers cannot use a side channel |
allankliu | 0:b6fdeddc0bc9 | 934 | attack to learn the number of leading zeros. */ |
allankliu | 0:b6fdeddc0bc9 | 935 | carry = regularize_k(private_key, tmp1, tmp2, curve); |
allankliu | 0:b6fdeddc0bc9 | 936 | |
allankliu | 0:b6fdeddc0bc9 | 937 | EccPoint_mult(result, curve->G, p2[!carry], 0, curve->num_n_bits + 1, curve); |
allankliu | 0:b6fdeddc0bc9 | 938 | |
allankliu | 0:b6fdeddc0bc9 | 939 | if (EccPoint_isZero(result, curve)) { |
allankliu | 0:b6fdeddc0bc9 | 940 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 941 | } |
allankliu | 0:b6fdeddc0bc9 | 942 | return 1; |
allankliu | 0:b6fdeddc0bc9 | 943 | } |
allankliu | 0:b6fdeddc0bc9 | 944 | |
allankliu | 0:b6fdeddc0bc9 | 945 | #if uECC_WORD_SIZE == 1 |
allankliu | 0:b6fdeddc0bc9 | 946 | |
allankliu | 0:b6fdeddc0bc9 | 947 | uECC_VLI_API void uECC_vli_nativeToBytes(uint8_t *bytes, |
allankliu | 0:b6fdeddc0bc9 | 948 | int num_bytes, |
allankliu | 0:b6fdeddc0bc9 | 949 | const uint8_t *native) { |
allankliu | 0:b6fdeddc0bc9 | 950 | wordcount_t i; |
allankliu | 0:b6fdeddc0bc9 | 951 | for (i = 0; i < num_bytes; ++i) { |
allankliu | 0:b6fdeddc0bc9 | 952 | bytes[i] = native[(num_bytes - 1) - i]; |
allankliu | 0:b6fdeddc0bc9 | 953 | } |
allankliu | 0:b6fdeddc0bc9 | 954 | } |
allankliu | 0:b6fdeddc0bc9 | 955 | |
allankliu | 0:b6fdeddc0bc9 | 956 | uECC_VLI_API void uECC_vli_bytesToNative(uint8_t *native, |
allankliu | 0:b6fdeddc0bc9 | 957 | const uint8_t *bytes, |
allankliu | 0:b6fdeddc0bc9 | 958 | int num_bytes) { |
allankliu | 0:b6fdeddc0bc9 | 959 | uECC_vli_nativeToBytes(native, num_bytes, bytes); |
allankliu | 0:b6fdeddc0bc9 | 960 | } |
allankliu | 0:b6fdeddc0bc9 | 961 | |
allankliu | 0:b6fdeddc0bc9 | 962 | #else |
allankliu | 0:b6fdeddc0bc9 | 963 | |
allankliu | 0:b6fdeddc0bc9 | 964 | uECC_VLI_API void uECC_vli_nativeToBytes(uint8_t *bytes, |
allankliu | 0:b6fdeddc0bc9 | 965 | int num_bytes, |
allankliu | 0:b6fdeddc0bc9 | 966 | const uECC_word_t *native) { |
allankliu | 0:b6fdeddc0bc9 | 967 | wordcount_t i; |
allankliu | 0:b6fdeddc0bc9 | 968 | for (i = 0; i < num_bytes; ++i) { |
allankliu | 0:b6fdeddc0bc9 | 969 | unsigned b = num_bytes - 1 - i; |
allankliu | 0:b6fdeddc0bc9 | 970 | bytes[i] = native[b / uECC_WORD_SIZE] >> (8 * (b % uECC_WORD_SIZE)); |
allankliu | 0:b6fdeddc0bc9 | 971 | } |
allankliu | 0:b6fdeddc0bc9 | 972 | } |
allankliu | 0:b6fdeddc0bc9 | 973 | |
allankliu | 0:b6fdeddc0bc9 | 974 | uECC_VLI_API void uECC_vli_bytesToNative(uECC_word_t *native, |
allankliu | 0:b6fdeddc0bc9 | 975 | const uint8_t *bytes, |
allankliu | 0:b6fdeddc0bc9 | 976 | int num_bytes) { |
allankliu | 0:b6fdeddc0bc9 | 977 | wordcount_t i; |
allankliu | 0:b6fdeddc0bc9 | 978 | uECC_vli_clear(native, (num_bytes + (uECC_WORD_SIZE - 1)) / uECC_WORD_SIZE); |
allankliu | 0:b6fdeddc0bc9 | 979 | for (i = 0; i < num_bytes; ++i) { |
allankliu | 0:b6fdeddc0bc9 | 980 | unsigned b = num_bytes - 1 - i; |
allankliu | 0:b6fdeddc0bc9 | 981 | native[b / uECC_WORD_SIZE] |= |
allankliu | 0:b6fdeddc0bc9 | 982 | (uECC_word_t)bytes[i] << (8 * (b % uECC_WORD_SIZE)); |
allankliu | 0:b6fdeddc0bc9 | 983 | } |
allankliu | 0:b6fdeddc0bc9 | 984 | } |
allankliu | 0:b6fdeddc0bc9 | 985 | |
allankliu | 0:b6fdeddc0bc9 | 986 | #endif /* uECC_WORD_SIZE */ |
allankliu | 0:b6fdeddc0bc9 | 987 | |
allankliu | 0:b6fdeddc0bc9 | 988 | /* Generates a random integer in the range 0 < random < top. |
allankliu | 0:b6fdeddc0bc9 | 989 | Both random and top have num_words words. */ |
allankliu | 0:b6fdeddc0bc9 | 990 | uECC_VLI_API int uECC_generate_random_int(uECC_word_t *random, |
allankliu | 0:b6fdeddc0bc9 | 991 | const uECC_word_t *top, |
allankliu | 0:b6fdeddc0bc9 | 992 | wordcount_t num_words) { |
allankliu | 0:b6fdeddc0bc9 | 993 | uECC_word_t mask = (uECC_word_t)-1; |
allankliu | 0:b6fdeddc0bc9 | 994 | uECC_word_t tries; |
allankliu | 0:b6fdeddc0bc9 | 995 | bitcount_t num_bits = uECC_vli_numBits(top, num_words); |
allankliu | 0:b6fdeddc0bc9 | 996 | |
allankliu | 0:b6fdeddc0bc9 | 997 | if (!g_rng_function) { |
allankliu | 0:b6fdeddc0bc9 | 998 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 999 | } |
allankliu | 0:b6fdeddc0bc9 | 1000 | |
allankliu | 0:b6fdeddc0bc9 | 1001 | for (tries = 0; tries < uECC_RNG_MAX_TRIES; ++tries) { |
allankliu | 0:b6fdeddc0bc9 | 1002 | if (!g_rng_function((uint8_t *)random, num_words * uECC_WORD_SIZE)) { |
allankliu | 0:b6fdeddc0bc9 | 1003 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1004 | } |
allankliu | 0:b6fdeddc0bc9 | 1005 | random[num_words - 1] &= mask >> ((bitcount_t)(num_words * uECC_WORD_SIZE * 8 - num_bits)); |
allankliu | 0:b6fdeddc0bc9 | 1006 | if (!uECC_vli_isZero(random, num_words) && |
allankliu | 0:b6fdeddc0bc9 | 1007 | uECC_vli_cmp(top, random, num_words) == 1) { |
allankliu | 0:b6fdeddc0bc9 | 1008 | return 1; |
allankliu | 0:b6fdeddc0bc9 | 1009 | } |
allankliu | 0:b6fdeddc0bc9 | 1010 | } |
allankliu | 0:b6fdeddc0bc9 | 1011 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1012 | } |
allankliu | 0:b6fdeddc0bc9 | 1013 | |
allankliu | 0:b6fdeddc0bc9 | 1014 | int uECC_make_key(uint8_t *public_key, |
allankliu | 0:b6fdeddc0bc9 | 1015 | uint8_t *private_key, |
allankliu | 0:b6fdeddc0bc9 | 1016 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1017 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN |
allankliu | 0:b6fdeddc0bc9 | 1018 | uECC_word_t *_private = (uECC_word_t *)private_key; |
allankliu | 0:b6fdeddc0bc9 | 1019 | uECC_word_t *_public = (uECC_word_t *)public_key; |
allankliu | 0:b6fdeddc0bc9 | 1020 | #else |
allankliu | 0:b6fdeddc0bc9 | 1021 | uECC_word_t _private[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1022 | uECC_word_t _public[uECC_MAX_WORDS * 2]; |
allankliu | 0:b6fdeddc0bc9 | 1023 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1024 | uECC_word_t tries; |
allankliu | 0:b6fdeddc0bc9 | 1025 | |
allankliu | 0:b6fdeddc0bc9 | 1026 | for (tries = 0; tries < uECC_RNG_MAX_TRIES; ++tries) { |
allankliu | 0:b6fdeddc0bc9 | 1027 | if (!uECC_generate_random_int(_private, curve->n, BITS_TO_WORDS(curve->num_n_bits))) { |
allankliu | 0:b6fdeddc0bc9 | 1028 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1029 | } |
allankliu | 0:b6fdeddc0bc9 | 1030 | |
allankliu | 0:b6fdeddc0bc9 | 1031 | if (EccPoint_compute_public_key(_public, _private, curve)) { |
allankliu | 0:b6fdeddc0bc9 | 1032 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN == 0 |
allankliu | 0:b6fdeddc0bc9 | 1033 | uECC_vli_nativeToBytes(private_key, BITS_TO_BYTES(curve->num_n_bits), _private); |
allankliu | 0:b6fdeddc0bc9 | 1034 | uECC_vli_nativeToBytes(public_key, curve->num_bytes, _public); |
allankliu | 0:b6fdeddc0bc9 | 1035 | uECC_vli_nativeToBytes( |
allankliu | 0:b6fdeddc0bc9 | 1036 | public_key + curve->num_bytes, curve->num_bytes, _public + curve->num_words); |
allankliu | 0:b6fdeddc0bc9 | 1037 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1038 | return 1; |
allankliu | 0:b6fdeddc0bc9 | 1039 | } |
allankliu | 0:b6fdeddc0bc9 | 1040 | } |
allankliu | 0:b6fdeddc0bc9 | 1041 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1042 | } |
allankliu | 0:b6fdeddc0bc9 | 1043 | |
allankliu | 0:b6fdeddc0bc9 | 1044 | int uECC_shared_secret(const uint8_t *public_key, |
allankliu | 0:b6fdeddc0bc9 | 1045 | const uint8_t *private_key, |
allankliu | 0:b6fdeddc0bc9 | 1046 | uint8_t *secret, |
allankliu | 0:b6fdeddc0bc9 | 1047 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1048 | uECC_word_t _public[uECC_MAX_WORDS * 2]; |
allankliu | 0:b6fdeddc0bc9 | 1049 | uECC_word_t _private[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1050 | |
allankliu | 0:b6fdeddc0bc9 | 1051 | uECC_word_t tmp[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1052 | uECC_word_t *p2[2] = {_private, tmp}; |
allankliu | 0:b6fdeddc0bc9 | 1053 | uECC_word_t *initial_Z = 0; |
allankliu | 0:b6fdeddc0bc9 | 1054 | uECC_word_t carry; |
allankliu | 0:b6fdeddc0bc9 | 1055 | wordcount_t num_words = curve->num_words; |
allankliu | 0:b6fdeddc0bc9 | 1056 | wordcount_t num_bytes = curve->num_bytes; |
allankliu | 0:b6fdeddc0bc9 | 1057 | |
allankliu | 0:b6fdeddc0bc9 | 1058 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN |
allankliu | 0:b6fdeddc0bc9 | 1059 | bcopy((uint8_t *) _private, private_key, num_bytes); |
allankliu | 0:b6fdeddc0bc9 | 1060 | bcopy((uint8_t *) _public, public_key, num_bytes*2); |
allankliu | 0:b6fdeddc0bc9 | 1061 | #else |
allankliu | 0:b6fdeddc0bc9 | 1062 | uECC_vli_bytesToNative(_private, private_key, BITS_TO_BYTES(curve->num_n_bits)); |
allankliu | 0:b6fdeddc0bc9 | 1063 | uECC_vli_bytesToNative(_public, public_key, num_bytes); |
allankliu | 0:b6fdeddc0bc9 | 1064 | uECC_vli_bytesToNative(_public + num_words, public_key + num_bytes, num_bytes); |
allankliu | 0:b6fdeddc0bc9 | 1065 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1066 | |
allankliu | 0:b6fdeddc0bc9 | 1067 | /* Regularize the bitcount for the private key so that attackers cannot use a side channel |
allankliu | 0:b6fdeddc0bc9 | 1068 | attack to learn the number of leading zeros. */ |
allankliu | 0:b6fdeddc0bc9 | 1069 | carry = regularize_k(_private, _private, tmp, curve); |
allankliu | 0:b6fdeddc0bc9 | 1070 | |
allankliu | 0:b6fdeddc0bc9 | 1071 | /* If an RNG function was specified, try to get a random initial Z value to improve |
allankliu | 0:b6fdeddc0bc9 | 1072 | protection against side-channel attacks. */ |
allankliu | 0:b6fdeddc0bc9 | 1073 | if (g_rng_function) { |
allankliu | 0:b6fdeddc0bc9 | 1074 | if (!uECC_generate_random_int(p2[carry], curve->p, num_words)) { |
allankliu | 0:b6fdeddc0bc9 | 1075 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1076 | } |
allankliu | 0:b6fdeddc0bc9 | 1077 | initial_Z = p2[carry]; |
allankliu | 0:b6fdeddc0bc9 | 1078 | } |
allankliu | 0:b6fdeddc0bc9 | 1079 | |
allankliu | 0:b6fdeddc0bc9 | 1080 | EccPoint_mult(_public, _public, p2[!carry], initial_Z, curve->num_n_bits + 1, curve); |
allankliu | 0:b6fdeddc0bc9 | 1081 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN |
allankliu | 0:b6fdeddc0bc9 | 1082 | bcopy((uint8_t *) secret, (uint8_t *) _public, num_bytes); |
allankliu | 0:b6fdeddc0bc9 | 1083 | #else |
allankliu | 0:b6fdeddc0bc9 | 1084 | uECC_vli_nativeToBytes(secret, num_bytes, _public); |
allankliu | 0:b6fdeddc0bc9 | 1085 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1086 | return !EccPoint_isZero(_public, curve); |
allankliu | 0:b6fdeddc0bc9 | 1087 | } |
allankliu | 0:b6fdeddc0bc9 | 1088 | |
allankliu | 0:b6fdeddc0bc9 | 1089 | #if uECC_SUPPORT_COMPRESSED_POINT |
allankliu | 0:b6fdeddc0bc9 | 1090 | void uECC_compress(const uint8_t *public_key, uint8_t *compressed, uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1091 | wordcount_t i; |
allankliu | 0:b6fdeddc0bc9 | 1092 | for (i = 0; i < curve->num_bytes; ++i) { |
allankliu | 0:b6fdeddc0bc9 | 1093 | compressed[i+1] = public_key[i]; |
allankliu | 0:b6fdeddc0bc9 | 1094 | } |
allankliu | 0:b6fdeddc0bc9 | 1095 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN |
allankliu | 0:b6fdeddc0bc9 | 1096 | compressed[0] = 2 + (public_key[curve->num_bytes] & 0x01); |
allankliu | 0:b6fdeddc0bc9 | 1097 | #else |
allankliu | 0:b6fdeddc0bc9 | 1098 | compressed[0] = 2 + (public_key[curve->num_bytes * 2 - 1] & 0x01); |
allankliu | 0:b6fdeddc0bc9 | 1099 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1100 | } |
allankliu | 0:b6fdeddc0bc9 | 1101 | |
allankliu | 0:b6fdeddc0bc9 | 1102 | void uECC_decompress(const uint8_t *compressed, uint8_t *public_key, uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1103 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN |
allankliu | 0:b6fdeddc0bc9 | 1104 | uECC_word_t *point = (uECC_word_t *)public_key; |
allankliu | 0:b6fdeddc0bc9 | 1105 | #else |
allankliu | 0:b6fdeddc0bc9 | 1106 | uECC_word_t point[uECC_MAX_WORDS * 2]; |
allankliu | 0:b6fdeddc0bc9 | 1107 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1108 | uECC_word_t *y = point + curve->num_words; |
allankliu | 0:b6fdeddc0bc9 | 1109 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN |
allankliu | 0:b6fdeddc0bc9 | 1110 | bcopy(public_key, compressed+1, curve->num_bytes); |
allankliu | 0:b6fdeddc0bc9 | 1111 | #else |
allankliu | 0:b6fdeddc0bc9 | 1112 | uECC_vli_bytesToNative(point, compressed + 1, curve->num_bytes); |
allankliu | 0:b6fdeddc0bc9 | 1113 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1114 | curve->x_side(y, point, curve); |
allankliu | 0:b6fdeddc0bc9 | 1115 | curve->mod_sqrt(y, curve); |
allankliu | 0:b6fdeddc0bc9 | 1116 | |
allankliu | 0:b6fdeddc0bc9 | 1117 | if ((y[0] & 0x01) != (compressed[0] & 0x01)) { |
allankliu | 0:b6fdeddc0bc9 | 1118 | uECC_vli_sub(y, curve->p, y, curve->num_words); |
allankliu | 0:b6fdeddc0bc9 | 1119 | } |
allankliu | 0:b6fdeddc0bc9 | 1120 | |
allankliu | 0:b6fdeddc0bc9 | 1121 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN == 0 |
allankliu | 0:b6fdeddc0bc9 | 1122 | uECC_vli_nativeToBytes(public_key, curve->num_bytes, point); |
allankliu | 0:b6fdeddc0bc9 | 1123 | uECC_vli_nativeToBytes(public_key + curve->num_bytes, curve->num_bytes, y); |
allankliu | 0:b6fdeddc0bc9 | 1124 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1125 | } |
allankliu | 0:b6fdeddc0bc9 | 1126 | #endif /* uECC_SUPPORT_COMPRESSED_POINT */ |
allankliu | 0:b6fdeddc0bc9 | 1127 | |
allankliu | 0:b6fdeddc0bc9 | 1128 | int uECC_valid_point(const uECC_word_t *point, uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1129 | uECC_word_t tmp1[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1130 | uECC_word_t tmp2[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1131 | wordcount_t num_words = curve->num_words; |
allankliu | 0:b6fdeddc0bc9 | 1132 | |
allankliu | 0:b6fdeddc0bc9 | 1133 | /* The point at infinity is invalid. */ |
allankliu | 0:b6fdeddc0bc9 | 1134 | if (EccPoint_isZero(point, curve)) { |
allankliu | 0:b6fdeddc0bc9 | 1135 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1136 | } |
allankliu | 0:b6fdeddc0bc9 | 1137 | |
allankliu | 0:b6fdeddc0bc9 | 1138 | /* x and y must be smaller than p. */ |
allankliu | 0:b6fdeddc0bc9 | 1139 | if (uECC_vli_cmp_unsafe(curve->p, point, num_words) != 1 || |
allankliu | 0:b6fdeddc0bc9 | 1140 | uECC_vli_cmp_unsafe(curve->p, point + num_words, num_words) != 1) { |
allankliu | 0:b6fdeddc0bc9 | 1141 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1142 | } |
allankliu | 0:b6fdeddc0bc9 | 1143 | |
allankliu | 0:b6fdeddc0bc9 | 1144 | uECC_vli_modSquare_fast(tmp1, point + num_words, curve); |
allankliu | 0:b6fdeddc0bc9 | 1145 | curve->x_side(tmp2, point, curve); /* tmp2 = x^3 + ax + b */ |
allankliu | 0:b6fdeddc0bc9 | 1146 | |
allankliu | 0:b6fdeddc0bc9 | 1147 | /* Make sure that y^2 == x^3 + ax + b */ |
allankliu | 0:b6fdeddc0bc9 | 1148 | return (int)(uECC_vli_equal(tmp1, tmp2, num_words)); |
allankliu | 0:b6fdeddc0bc9 | 1149 | } |
allankliu | 0:b6fdeddc0bc9 | 1150 | |
allankliu | 0:b6fdeddc0bc9 | 1151 | int uECC_valid_public_key(const uint8_t *public_key, uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1152 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN |
allankliu | 0:b6fdeddc0bc9 | 1153 | uECC_word_t *_public = (uECC_word_t *)public_key; |
allankliu | 0:b6fdeddc0bc9 | 1154 | #else |
allankliu | 0:b6fdeddc0bc9 | 1155 | uECC_word_t _public[uECC_MAX_WORDS * 2]; |
allankliu | 0:b6fdeddc0bc9 | 1156 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1157 | |
allankliu | 0:b6fdeddc0bc9 | 1158 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN == 0 |
allankliu | 0:b6fdeddc0bc9 | 1159 | uECC_vli_bytesToNative(_public, public_key, curve->num_bytes); |
allankliu | 0:b6fdeddc0bc9 | 1160 | uECC_vli_bytesToNative( |
allankliu | 0:b6fdeddc0bc9 | 1161 | _public + curve->num_words, public_key + curve->num_bytes, curve->num_bytes); |
allankliu | 0:b6fdeddc0bc9 | 1162 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1163 | return uECC_valid_point(_public, curve); |
allankliu | 0:b6fdeddc0bc9 | 1164 | } |
allankliu | 0:b6fdeddc0bc9 | 1165 | |
allankliu | 0:b6fdeddc0bc9 | 1166 | int uECC_compute_public_key(const uint8_t *private_key, uint8_t *public_key, uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1167 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN |
allankliu | 0:b6fdeddc0bc9 | 1168 | uECC_word_t *_private = (uECC_word_t *)private_key; |
allankliu | 0:b6fdeddc0bc9 | 1169 | uECC_word_t *_public = (uECC_word_t *)public_key; |
allankliu | 0:b6fdeddc0bc9 | 1170 | #else |
allankliu | 0:b6fdeddc0bc9 | 1171 | uECC_word_t _private[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1172 | uECC_word_t _public[uECC_MAX_WORDS * 2]; |
allankliu | 0:b6fdeddc0bc9 | 1173 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1174 | |
allankliu | 0:b6fdeddc0bc9 | 1175 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN == 0 |
allankliu | 0:b6fdeddc0bc9 | 1176 | uECC_vli_bytesToNative(_private, private_key, BITS_TO_BYTES(curve->num_n_bits)); |
allankliu | 0:b6fdeddc0bc9 | 1177 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1178 | |
allankliu | 0:b6fdeddc0bc9 | 1179 | /* Make sure the private key is in the range [1, n-1]. */ |
allankliu | 0:b6fdeddc0bc9 | 1180 | if (uECC_vli_isZero(_private, BITS_TO_WORDS(curve->num_n_bits))) { |
allankliu | 0:b6fdeddc0bc9 | 1181 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1182 | } |
allankliu | 0:b6fdeddc0bc9 | 1183 | |
allankliu | 0:b6fdeddc0bc9 | 1184 | if (uECC_vli_cmp(curve->n, _private, BITS_TO_WORDS(curve->num_n_bits)) != 1) { |
allankliu | 0:b6fdeddc0bc9 | 1185 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1186 | } |
allankliu | 0:b6fdeddc0bc9 | 1187 | |
allankliu | 0:b6fdeddc0bc9 | 1188 | /* Compute public key. */ |
allankliu | 0:b6fdeddc0bc9 | 1189 | if (!EccPoint_compute_public_key(_public, _private, curve)) { |
allankliu | 0:b6fdeddc0bc9 | 1190 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1191 | } |
allankliu | 0:b6fdeddc0bc9 | 1192 | |
allankliu | 0:b6fdeddc0bc9 | 1193 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN == 0 |
allankliu | 0:b6fdeddc0bc9 | 1194 | uECC_vli_nativeToBytes(public_key, curve->num_bytes, _public); |
allankliu | 0:b6fdeddc0bc9 | 1195 | uECC_vli_nativeToBytes( |
allankliu | 0:b6fdeddc0bc9 | 1196 | public_key + curve->num_bytes, curve->num_bytes, _public + curve->num_words); |
allankliu | 0:b6fdeddc0bc9 | 1197 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1198 | return 1; |
allankliu | 0:b6fdeddc0bc9 | 1199 | } |
allankliu | 0:b6fdeddc0bc9 | 1200 | |
allankliu | 0:b6fdeddc0bc9 | 1201 | |
allankliu | 0:b6fdeddc0bc9 | 1202 | /* -------- ECDSA code -------- */ |
allankliu | 0:b6fdeddc0bc9 | 1203 | |
allankliu | 0:b6fdeddc0bc9 | 1204 | static void bits2int(uECC_word_t *native, |
allankliu | 0:b6fdeddc0bc9 | 1205 | const uint8_t *bits, |
allankliu | 0:b6fdeddc0bc9 | 1206 | unsigned bits_size, |
allankliu | 0:b6fdeddc0bc9 | 1207 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1208 | unsigned num_n_bytes = BITS_TO_BYTES(curve->num_n_bits); |
allankliu | 0:b6fdeddc0bc9 | 1209 | unsigned num_n_words = BITS_TO_WORDS(curve->num_n_bits); |
allankliu | 0:b6fdeddc0bc9 | 1210 | int shift; |
allankliu | 0:b6fdeddc0bc9 | 1211 | uECC_word_t carry; |
allankliu | 0:b6fdeddc0bc9 | 1212 | uECC_word_t *ptr; |
allankliu | 0:b6fdeddc0bc9 | 1213 | |
allankliu | 0:b6fdeddc0bc9 | 1214 | if (bits_size > num_n_bytes) { |
allankliu | 0:b6fdeddc0bc9 | 1215 | bits_size = num_n_bytes; |
allankliu | 0:b6fdeddc0bc9 | 1216 | } |
allankliu | 0:b6fdeddc0bc9 | 1217 | |
allankliu | 0:b6fdeddc0bc9 | 1218 | uECC_vli_clear(native, num_n_words); |
allankliu | 0:b6fdeddc0bc9 | 1219 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN |
allankliu | 0:b6fdeddc0bc9 | 1220 | bcopy((uint8_t *) native, bits, bits_size); |
allankliu | 0:b6fdeddc0bc9 | 1221 | #else |
allankliu | 0:b6fdeddc0bc9 | 1222 | uECC_vli_bytesToNative(native, bits, bits_size); |
allankliu | 0:b6fdeddc0bc9 | 1223 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1224 | if (bits_size * 8 <= (unsigned)curve->num_n_bits) { |
allankliu | 0:b6fdeddc0bc9 | 1225 | return; |
allankliu | 0:b6fdeddc0bc9 | 1226 | } |
allankliu | 0:b6fdeddc0bc9 | 1227 | shift = bits_size * 8 - curve->num_n_bits; |
allankliu | 0:b6fdeddc0bc9 | 1228 | carry = 0; |
allankliu | 0:b6fdeddc0bc9 | 1229 | ptr = native + num_n_words; |
allankliu | 0:b6fdeddc0bc9 | 1230 | while (ptr-- > native) { |
allankliu | 0:b6fdeddc0bc9 | 1231 | uECC_word_t temp = *ptr; |
allankliu | 0:b6fdeddc0bc9 | 1232 | *ptr = (temp >> shift) | carry; |
allankliu | 0:b6fdeddc0bc9 | 1233 | carry = temp << (uECC_WORD_BITS - shift); |
allankliu | 0:b6fdeddc0bc9 | 1234 | } |
allankliu | 0:b6fdeddc0bc9 | 1235 | |
allankliu | 0:b6fdeddc0bc9 | 1236 | /* Reduce mod curve_n */ |
allankliu | 0:b6fdeddc0bc9 | 1237 | if (uECC_vli_cmp_unsafe(curve->n, native, num_n_words) != 1) { |
allankliu | 0:b6fdeddc0bc9 | 1238 | uECC_vli_sub(native, native, curve->n, num_n_words); |
allankliu | 0:b6fdeddc0bc9 | 1239 | } |
allankliu | 0:b6fdeddc0bc9 | 1240 | } |
allankliu | 0:b6fdeddc0bc9 | 1241 | |
allankliu | 0:b6fdeddc0bc9 | 1242 | static int uECC_sign_with_k(const uint8_t *private_key, |
allankliu | 0:b6fdeddc0bc9 | 1243 | const uint8_t *message_hash, |
allankliu | 0:b6fdeddc0bc9 | 1244 | unsigned hash_size, |
allankliu | 0:b6fdeddc0bc9 | 1245 | uECC_word_t *k, |
allankliu | 0:b6fdeddc0bc9 | 1246 | uint8_t *signature, |
allankliu | 0:b6fdeddc0bc9 | 1247 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1248 | |
allankliu | 0:b6fdeddc0bc9 | 1249 | uECC_word_t tmp[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1250 | uECC_word_t s[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1251 | uECC_word_t *k2[2] = {tmp, s}; |
allankliu | 0:b6fdeddc0bc9 | 1252 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN |
allankliu | 0:b6fdeddc0bc9 | 1253 | uECC_word_t *p = (uECC_word_t *)signature; |
allankliu | 0:b6fdeddc0bc9 | 1254 | #else |
allankliu | 0:b6fdeddc0bc9 | 1255 | uECC_word_t p[uECC_MAX_WORDS * 2]; |
allankliu | 0:b6fdeddc0bc9 | 1256 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1257 | uECC_word_t carry; |
allankliu | 0:b6fdeddc0bc9 | 1258 | wordcount_t num_words = curve->num_words; |
allankliu | 0:b6fdeddc0bc9 | 1259 | wordcount_t num_n_words = BITS_TO_WORDS(curve->num_n_bits); |
allankliu | 0:b6fdeddc0bc9 | 1260 | bitcount_t num_n_bits = curve->num_n_bits; |
allankliu | 0:b6fdeddc0bc9 | 1261 | |
allankliu | 0:b6fdeddc0bc9 | 1262 | /* Make sure 0 < k < curve_n */ |
allankliu | 0:b6fdeddc0bc9 | 1263 | if (uECC_vli_isZero(k, num_words) || uECC_vli_cmp(curve->n, k, num_n_words) != 1) { |
allankliu | 0:b6fdeddc0bc9 | 1264 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1265 | } |
allankliu | 0:b6fdeddc0bc9 | 1266 | |
allankliu | 0:b6fdeddc0bc9 | 1267 | carry = regularize_k(k, tmp, s, curve); |
allankliu | 0:b6fdeddc0bc9 | 1268 | EccPoint_mult(p, curve->G, k2[!carry], 0, num_n_bits + 1, curve); |
allankliu | 0:b6fdeddc0bc9 | 1269 | if (uECC_vli_isZero(p, num_words)) { |
allankliu | 0:b6fdeddc0bc9 | 1270 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1271 | } |
allankliu | 0:b6fdeddc0bc9 | 1272 | |
allankliu | 0:b6fdeddc0bc9 | 1273 | /* If an RNG function was specified, get a random number |
allankliu | 0:b6fdeddc0bc9 | 1274 | to prevent side channel analysis of k. */ |
allankliu | 0:b6fdeddc0bc9 | 1275 | if (!g_rng_function) { |
allankliu | 0:b6fdeddc0bc9 | 1276 | uECC_vli_clear(tmp, num_n_words); |
allankliu | 0:b6fdeddc0bc9 | 1277 | tmp[0] = 1; |
allankliu | 0:b6fdeddc0bc9 | 1278 | } else if (!uECC_generate_random_int(tmp, curve->n, num_n_words)) { |
allankliu | 0:b6fdeddc0bc9 | 1279 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1280 | } |
allankliu | 0:b6fdeddc0bc9 | 1281 | |
allankliu | 0:b6fdeddc0bc9 | 1282 | /* Prevent side channel analysis of uECC_vli_modInv() to determine |
allankliu | 0:b6fdeddc0bc9 | 1283 | bits of k / the private key by premultiplying by a random number */ |
allankliu | 0:b6fdeddc0bc9 | 1284 | uECC_vli_modMult(k, k, tmp, curve->n, num_n_words); /* k' = rand * k */ |
allankliu | 0:b6fdeddc0bc9 | 1285 | uECC_vli_modInv(k, k, curve->n, num_n_words); /* k = 1 / k' */ |
allankliu | 0:b6fdeddc0bc9 | 1286 | uECC_vli_modMult(k, k, tmp, curve->n, num_n_words); /* k = 1 / k */ |
allankliu | 0:b6fdeddc0bc9 | 1287 | |
allankliu | 0:b6fdeddc0bc9 | 1288 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN == 0 |
allankliu | 0:b6fdeddc0bc9 | 1289 | uECC_vli_nativeToBytes(signature, curve->num_bytes, p); /* store r */ |
allankliu | 0:b6fdeddc0bc9 | 1290 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1291 | |
allankliu | 0:b6fdeddc0bc9 | 1292 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN |
allankliu | 0:b6fdeddc0bc9 | 1293 | bcopy((uint8_t *) tmp, private_key, BITS_TO_BYTES(curve->num_n_bits)); |
allankliu | 0:b6fdeddc0bc9 | 1294 | #else |
allankliu | 0:b6fdeddc0bc9 | 1295 | uECC_vli_bytesToNative(tmp, private_key, BITS_TO_BYTES(curve->num_n_bits)); /* tmp = d */ |
allankliu | 0:b6fdeddc0bc9 | 1296 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1297 | |
allankliu | 0:b6fdeddc0bc9 | 1298 | s[num_n_words - 1] = 0; |
allankliu | 0:b6fdeddc0bc9 | 1299 | uECC_vli_set(s, p, num_words); |
allankliu | 0:b6fdeddc0bc9 | 1300 | uECC_vli_modMult(s, tmp, s, curve->n, num_n_words); /* s = r*d */ |
allankliu | 0:b6fdeddc0bc9 | 1301 | |
allankliu | 0:b6fdeddc0bc9 | 1302 | bits2int(tmp, message_hash, hash_size, curve); |
allankliu | 0:b6fdeddc0bc9 | 1303 | uECC_vli_modAdd(s, tmp, s, curve->n, num_n_words); /* s = e + r*d */ |
allankliu | 0:b6fdeddc0bc9 | 1304 | uECC_vli_modMult(s, s, k, curve->n, num_n_words); /* s = (e + r*d) / k */ |
allankliu | 0:b6fdeddc0bc9 | 1305 | if (uECC_vli_numBits(s, num_n_words) > (bitcount_t)curve->num_bytes * 8) { |
allankliu | 0:b6fdeddc0bc9 | 1306 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1307 | } |
allankliu | 0:b6fdeddc0bc9 | 1308 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN |
allankliu | 0:b6fdeddc0bc9 | 1309 | bcopy((uint8_t *) signature + curve->num_bytes, (uint8_t *) s, curve->num_bytes); |
allankliu | 0:b6fdeddc0bc9 | 1310 | #else |
allankliu | 0:b6fdeddc0bc9 | 1311 | uECC_vli_nativeToBytes(signature + curve->num_bytes, curve->num_bytes, s); |
allankliu | 0:b6fdeddc0bc9 | 1312 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1313 | return 1; |
allankliu | 0:b6fdeddc0bc9 | 1314 | } |
allankliu | 0:b6fdeddc0bc9 | 1315 | |
allankliu | 0:b6fdeddc0bc9 | 1316 | int uECC_sign(const uint8_t *private_key, |
allankliu | 0:b6fdeddc0bc9 | 1317 | const uint8_t *message_hash, |
allankliu | 0:b6fdeddc0bc9 | 1318 | unsigned hash_size, |
allankliu | 0:b6fdeddc0bc9 | 1319 | uint8_t *signature, |
allankliu | 0:b6fdeddc0bc9 | 1320 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1321 | uECC_word_t k[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1322 | uECC_word_t tries; |
allankliu | 0:b6fdeddc0bc9 | 1323 | |
allankliu | 0:b6fdeddc0bc9 | 1324 | for (tries = 0; tries < uECC_RNG_MAX_TRIES; ++tries) { |
allankliu | 0:b6fdeddc0bc9 | 1325 | if (!uECC_generate_random_int(k, curve->n, BITS_TO_WORDS(curve->num_n_bits))) { |
allankliu | 0:b6fdeddc0bc9 | 1326 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1327 | } |
allankliu | 0:b6fdeddc0bc9 | 1328 | |
allankliu | 0:b6fdeddc0bc9 | 1329 | if (uECC_sign_with_k(private_key, message_hash, hash_size, k, signature, curve)) { |
allankliu | 0:b6fdeddc0bc9 | 1330 | return 1; |
allankliu | 0:b6fdeddc0bc9 | 1331 | } |
allankliu | 0:b6fdeddc0bc9 | 1332 | } |
allankliu | 0:b6fdeddc0bc9 | 1333 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1334 | } |
allankliu | 0:b6fdeddc0bc9 | 1335 | |
allankliu | 0:b6fdeddc0bc9 | 1336 | /* Compute an HMAC using K as a key (as in RFC 6979). Note that K is always |
allankliu | 0:b6fdeddc0bc9 | 1337 | the same size as the hash result size. */ |
allankliu | 0:b6fdeddc0bc9 | 1338 | static void HMAC_init(const uECC_HashContext *hash_context, const uint8_t *K) { |
allankliu | 0:b6fdeddc0bc9 | 1339 | uint8_t *pad = hash_context->tmp + 2 * hash_context->result_size; |
allankliu | 0:b6fdeddc0bc9 | 1340 | unsigned i; |
allankliu | 0:b6fdeddc0bc9 | 1341 | for (i = 0; i < hash_context->result_size; ++i) |
allankliu | 0:b6fdeddc0bc9 | 1342 | pad[i] = K[i] ^ 0x36; |
allankliu | 0:b6fdeddc0bc9 | 1343 | for (; i < hash_context->block_size; ++i) |
allankliu | 0:b6fdeddc0bc9 | 1344 | pad[i] = 0x36; |
allankliu | 0:b6fdeddc0bc9 | 1345 | |
allankliu | 0:b6fdeddc0bc9 | 1346 | hash_context->init_hash(hash_context); |
allankliu | 0:b6fdeddc0bc9 | 1347 | hash_context->update_hash(hash_context, pad, hash_context->block_size); |
allankliu | 0:b6fdeddc0bc9 | 1348 | } |
allankliu | 0:b6fdeddc0bc9 | 1349 | |
allankliu | 0:b6fdeddc0bc9 | 1350 | static void HMAC_update(const uECC_HashContext *hash_context, |
allankliu | 0:b6fdeddc0bc9 | 1351 | const uint8_t *message, |
allankliu | 0:b6fdeddc0bc9 | 1352 | unsigned message_size) { |
allankliu | 0:b6fdeddc0bc9 | 1353 | hash_context->update_hash(hash_context, message, message_size); |
allankliu | 0:b6fdeddc0bc9 | 1354 | } |
allankliu | 0:b6fdeddc0bc9 | 1355 | |
allankliu | 0:b6fdeddc0bc9 | 1356 | static void HMAC_finish(const uECC_HashContext *hash_context, |
allankliu | 0:b6fdeddc0bc9 | 1357 | const uint8_t *K, |
allankliu | 0:b6fdeddc0bc9 | 1358 | uint8_t *result) { |
allankliu | 0:b6fdeddc0bc9 | 1359 | uint8_t *pad = hash_context->tmp + 2 * hash_context->result_size; |
allankliu | 0:b6fdeddc0bc9 | 1360 | unsigned i; |
allankliu | 0:b6fdeddc0bc9 | 1361 | for (i = 0; i < hash_context->result_size; ++i) |
allankliu | 0:b6fdeddc0bc9 | 1362 | pad[i] = K[i] ^ 0x5c; |
allankliu | 0:b6fdeddc0bc9 | 1363 | for (; i < hash_context->block_size; ++i) |
allankliu | 0:b6fdeddc0bc9 | 1364 | pad[i] = 0x5c; |
allankliu | 0:b6fdeddc0bc9 | 1365 | |
allankliu | 0:b6fdeddc0bc9 | 1366 | hash_context->finish_hash(hash_context, result); |
allankliu | 0:b6fdeddc0bc9 | 1367 | |
allankliu | 0:b6fdeddc0bc9 | 1368 | hash_context->init_hash(hash_context); |
allankliu | 0:b6fdeddc0bc9 | 1369 | hash_context->update_hash(hash_context, pad, hash_context->block_size); |
allankliu | 0:b6fdeddc0bc9 | 1370 | hash_context->update_hash(hash_context, result, hash_context->result_size); |
allankliu | 0:b6fdeddc0bc9 | 1371 | hash_context->finish_hash(hash_context, result); |
allankliu | 0:b6fdeddc0bc9 | 1372 | } |
allankliu | 0:b6fdeddc0bc9 | 1373 | |
allankliu | 0:b6fdeddc0bc9 | 1374 | /* V = HMAC_K(V) */ |
allankliu | 0:b6fdeddc0bc9 | 1375 | static void update_V(const uECC_HashContext *hash_context, uint8_t *K, uint8_t *V) { |
allankliu | 0:b6fdeddc0bc9 | 1376 | HMAC_init(hash_context, K); |
allankliu | 0:b6fdeddc0bc9 | 1377 | HMAC_update(hash_context, V, hash_context->result_size); |
allankliu | 0:b6fdeddc0bc9 | 1378 | HMAC_finish(hash_context, K, V); |
allankliu | 0:b6fdeddc0bc9 | 1379 | } |
allankliu | 0:b6fdeddc0bc9 | 1380 | |
allankliu | 0:b6fdeddc0bc9 | 1381 | /* Deterministic signing, similar to RFC 6979. Differences are: |
allankliu | 0:b6fdeddc0bc9 | 1382 | * We just use H(m) directly rather than bits2octets(H(m)) |
allankliu | 0:b6fdeddc0bc9 | 1383 | (it is not reduced modulo curve_n). |
allankliu | 0:b6fdeddc0bc9 | 1384 | * We generate a value for k (aka T) directly rather than converting endianness. |
allankliu | 0:b6fdeddc0bc9 | 1385 | |
allankliu | 0:b6fdeddc0bc9 | 1386 | Layout of hash_context->tmp: <K> | <V> | (1 byte overlapped 0x00 or 0x01) / <HMAC pad> */ |
allankliu | 0:b6fdeddc0bc9 | 1387 | int uECC_sign_deterministic(const uint8_t *private_key, |
allankliu | 0:b6fdeddc0bc9 | 1388 | const uint8_t *message_hash, |
allankliu | 0:b6fdeddc0bc9 | 1389 | unsigned hash_size, |
allankliu | 0:b6fdeddc0bc9 | 1390 | const uECC_HashContext *hash_context, |
allankliu | 0:b6fdeddc0bc9 | 1391 | uint8_t *signature, |
allankliu | 0:b6fdeddc0bc9 | 1392 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1393 | uint8_t *K = hash_context->tmp; |
allankliu | 0:b6fdeddc0bc9 | 1394 | uint8_t *V = K + hash_context->result_size; |
allankliu | 0:b6fdeddc0bc9 | 1395 | wordcount_t num_bytes = curve->num_bytes; |
allankliu | 0:b6fdeddc0bc9 | 1396 | wordcount_t num_n_words = BITS_TO_WORDS(curve->num_n_bits); |
allankliu | 0:b6fdeddc0bc9 | 1397 | bitcount_t num_n_bits = curve->num_n_bits; |
allankliu | 0:b6fdeddc0bc9 | 1398 | uECC_word_t tries; |
allankliu | 0:b6fdeddc0bc9 | 1399 | unsigned i; |
allankliu | 0:b6fdeddc0bc9 | 1400 | for (i = 0; i < hash_context->result_size; ++i) { |
allankliu | 0:b6fdeddc0bc9 | 1401 | V[i] = 0x01; |
allankliu | 0:b6fdeddc0bc9 | 1402 | K[i] = 0; |
allankliu | 0:b6fdeddc0bc9 | 1403 | } |
allankliu | 0:b6fdeddc0bc9 | 1404 | |
allankliu | 0:b6fdeddc0bc9 | 1405 | /* K = HMAC_K(V || 0x00 || int2octets(x) || h(m)) */ |
allankliu | 0:b6fdeddc0bc9 | 1406 | HMAC_init(hash_context, K); |
allankliu | 0:b6fdeddc0bc9 | 1407 | V[hash_context->result_size] = 0x00; |
allankliu | 0:b6fdeddc0bc9 | 1408 | HMAC_update(hash_context, V, hash_context->result_size + 1); |
allankliu | 0:b6fdeddc0bc9 | 1409 | HMAC_update(hash_context, private_key, num_bytes); |
allankliu | 0:b6fdeddc0bc9 | 1410 | HMAC_update(hash_context, message_hash, hash_size); |
allankliu | 0:b6fdeddc0bc9 | 1411 | HMAC_finish(hash_context, K, K); |
allankliu | 0:b6fdeddc0bc9 | 1412 | |
allankliu | 0:b6fdeddc0bc9 | 1413 | update_V(hash_context, K, V); |
allankliu | 0:b6fdeddc0bc9 | 1414 | |
allankliu | 0:b6fdeddc0bc9 | 1415 | /* K = HMAC_K(V || 0x01 || int2octets(x) || h(m)) */ |
allankliu | 0:b6fdeddc0bc9 | 1416 | HMAC_init(hash_context, K); |
allankliu | 0:b6fdeddc0bc9 | 1417 | V[hash_context->result_size] = 0x01; |
allankliu | 0:b6fdeddc0bc9 | 1418 | HMAC_update(hash_context, V, hash_context->result_size + 1); |
allankliu | 0:b6fdeddc0bc9 | 1419 | HMAC_update(hash_context, private_key, num_bytes); |
allankliu | 0:b6fdeddc0bc9 | 1420 | HMAC_update(hash_context, message_hash, hash_size); |
allankliu | 0:b6fdeddc0bc9 | 1421 | HMAC_finish(hash_context, K, K); |
allankliu | 0:b6fdeddc0bc9 | 1422 | |
allankliu | 0:b6fdeddc0bc9 | 1423 | update_V(hash_context, K, V); |
allankliu | 0:b6fdeddc0bc9 | 1424 | |
allankliu | 0:b6fdeddc0bc9 | 1425 | for (tries = 0; tries < uECC_RNG_MAX_TRIES; ++tries) { |
allankliu | 0:b6fdeddc0bc9 | 1426 | uECC_word_t T[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1427 | uint8_t *T_ptr = (uint8_t *)T; |
allankliu | 0:b6fdeddc0bc9 | 1428 | wordcount_t T_bytes = 0; |
allankliu | 0:b6fdeddc0bc9 | 1429 | for (;;) { |
allankliu | 0:b6fdeddc0bc9 | 1430 | update_V(hash_context, K, V); |
allankliu | 0:b6fdeddc0bc9 | 1431 | for (i = 0; i < hash_context->result_size; ++i) { |
allankliu | 0:b6fdeddc0bc9 | 1432 | T_ptr[T_bytes++] = V[i]; |
allankliu | 0:b6fdeddc0bc9 | 1433 | if (T_bytes >= num_n_words * uECC_WORD_SIZE) { |
allankliu | 0:b6fdeddc0bc9 | 1434 | goto filled; |
allankliu | 0:b6fdeddc0bc9 | 1435 | } |
allankliu | 0:b6fdeddc0bc9 | 1436 | } |
allankliu | 0:b6fdeddc0bc9 | 1437 | } |
allankliu | 0:b6fdeddc0bc9 | 1438 | filled: |
allankliu | 0:b6fdeddc0bc9 | 1439 | if ((bitcount_t)num_n_words * uECC_WORD_SIZE * 8 > num_n_bits) { |
allankliu | 0:b6fdeddc0bc9 | 1440 | uECC_word_t mask = (uECC_word_t)-1; |
allankliu | 0:b6fdeddc0bc9 | 1441 | T[num_n_words - 1] &= |
allankliu | 0:b6fdeddc0bc9 | 1442 | mask >> ((bitcount_t)(num_n_words * uECC_WORD_SIZE * 8 - num_n_bits)); |
allankliu | 0:b6fdeddc0bc9 | 1443 | } |
allankliu | 0:b6fdeddc0bc9 | 1444 | |
allankliu | 0:b6fdeddc0bc9 | 1445 | if (uECC_sign_with_k(private_key, message_hash, hash_size, T, signature, curve)) { |
allankliu | 0:b6fdeddc0bc9 | 1446 | return 1; |
allankliu | 0:b6fdeddc0bc9 | 1447 | } |
allankliu | 0:b6fdeddc0bc9 | 1448 | |
allankliu | 0:b6fdeddc0bc9 | 1449 | /* K = HMAC_K(V || 0x00) */ |
allankliu | 0:b6fdeddc0bc9 | 1450 | HMAC_init(hash_context, K); |
allankliu | 0:b6fdeddc0bc9 | 1451 | V[hash_context->result_size] = 0x00; |
allankliu | 0:b6fdeddc0bc9 | 1452 | HMAC_update(hash_context, V, hash_context->result_size + 1); |
allankliu | 0:b6fdeddc0bc9 | 1453 | HMAC_finish(hash_context, K, K); |
allankliu | 0:b6fdeddc0bc9 | 1454 | |
allankliu | 0:b6fdeddc0bc9 | 1455 | update_V(hash_context, K, V); |
allankliu | 0:b6fdeddc0bc9 | 1456 | } |
allankliu | 0:b6fdeddc0bc9 | 1457 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1458 | } |
allankliu | 0:b6fdeddc0bc9 | 1459 | |
allankliu | 0:b6fdeddc0bc9 | 1460 | static bitcount_t smax(bitcount_t a, bitcount_t b) { |
allankliu | 0:b6fdeddc0bc9 | 1461 | return (a > b ? a : b); |
allankliu | 0:b6fdeddc0bc9 | 1462 | } |
allankliu | 0:b6fdeddc0bc9 | 1463 | |
allankliu | 0:b6fdeddc0bc9 | 1464 | int uECC_verify(const uint8_t *public_key, |
allankliu | 0:b6fdeddc0bc9 | 1465 | const uint8_t *message_hash, |
allankliu | 0:b6fdeddc0bc9 | 1466 | unsigned hash_size, |
allankliu | 0:b6fdeddc0bc9 | 1467 | const uint8_t *signature, |
allankliu | 0:b6fdeddc0bc9 | 1468 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1469 | uECC_word_t u1[uECC_MAX_WORDS], u2[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1470 | uECC_word_t z[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1471 | uECC_word_t sum[uECC_MAX_WORDS * 2]; |
allankliu | 0:b6fdeddc0bc9 | 1472 | uECC_word_t rx[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1473 | uECC_word_t ry[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1474 | uECC_word_t tx[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1475 | uECC_word_t ty[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1476 | uECC_word_t tz[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1477 | const uECC_word_t *points[4]; |
allankliu | 0:b6fdeddc0bc9 | 1478 | const uECC_word_t *point; |
allankliu | 0:b6fdeddc0bc9 | 1479 | bitcount_t num_bits; |
allankliu | 0:b6fdeddc0bc9 | 1480 | bitcount_t i; |
allankliu | 0:b6fdeddc0bc9 | 1481 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN |
allankliu | 0:b6fdeddc0bc9 | 1482 | uECC_word_t *_public = (uECC_word_t *)public_key; |
allankliu | 0:b6fdeddc0bc9 | 1483 | #else |
allankliu | 0:b6fdeddc0bc9 | 1484 | uECC_word_t _public[uECC_MAX_WORDS * 2]; |
allankliu | 0:b6fdeddc0bc9 | 1485 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1486 | uECC_word_t r[uECC_MAX_WORDS], s[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1487 | wordcount_t num_words = curve->num_words; |
allankliu | 0:b6fdeddc0bc9 | 1488 | wordcount_t num_n_words = BITS_TO_WORDS(curve->num_n_bits); |
allankliu | 0:b6fdeddc0bc9 | 1489 | |
allankliu | 0:b6fdeddc0bc9 | 1490 | rx[num_n_words - 1] = 0; |
allankliu | 0:b6fdeddc0bc9 | 1491 | r[num_n_words - 1] = 0; |
allankliu | 0:b6fdeddc0bc9 | 1492 | s[num_n_words - 1] = 0; |
allankliu | 0:b6fdeddc0bc9 | 1493 | |
allankliu | 0:b6fdeddc0bc9 | 1494 | #if uECC_VLI_NATIVE_LITTLE_ENDIAN |
allankliu | 0:b6fdeddc0bc9 | 1495 | bcopy((uint8_t *) r, signature, curve->num_bytes); |
allankliu | 0:b6fdeddc0bc9 | 1496 | bcopy((uint8_t *) s, signature + curve->num_bytes, curve->num_bytes); |
allankliu | 0:b6fdeddc0bc9 | 1497 | #else |
allankliu | 0:b6fdeddc0bc9 | 1498 | uECC_vli_bytesToNative(_public, public_key, curve->num_bytes); |
allankliu | 0:b6fdeddc0bc9 | 1499 | uECC_vli_bytesToNative( |
allankliu | 0:b6fdeddc0bc9 | 1500 | _public + num_words, public_key + curve->num_bytes, curve->num_bytes); |
allankliu | 0:b6fdeddc0bc9 | 1501 | uECC_vli_bytesToNative(r, signature, curve->num_bytes); |
allankliu | 0:b6fdeddc0bc9 | 1502 | uECC_vli_bytesToNative(s, signature + curve->num_bytes, curve->num_bytes); |
allankliu | 0:b6fdeddc0bc9 | 1503 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1504 | |
allankliu | 0:b6fdeddc0bc9 | 1505 | /* r, s must not be 0. */ |
allankliu | 0:b6fdeddc0bc9 | 1506 | if (uECC_vli_isZero(r, num_words) || uECC_vli_isZero(s, num_words)) { |
allankliu | 0:b6fdeddc0bc9 | 1507 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1508 | } |
allankliu | 0:b6fdeddc0bc9 | 1509 | |
allankliu | 0:b6fdeddc0bc9 | 1510 | /* r, s must be < n. */ |
allankliu | 0:b6fdeddc0bc9 | 1511 | if (uECC_vli_cmp_unsafe(curve->n, r, num_n_words) != 1 || |
allankliu | 0:b6fdeddc0bc9 | 1512 | uECC_vli_cmp_unsafe(curve->n, s, num_n_words) != 1) { |
allankliu | 0:b6fdeddc0bc9 | 1513 | return 0; |
allankliu | 0:b6fdeddc0bc9 | 1514 | } |
allankliu | 0:b6fdeddc0bc9 | 1515 | |
allankliu | 0:b6fdeddc0bc9 | 1516 | /* Calculate u1 and u2. */ |
allankliu | 0:b6fdeddc0bc9 | 1517 | uECC_vli_modInv(z, s, curve->n, num_n_words); /* z = 1/s */ |
allankliu | 0:b6fdeddc0bc9 | 1518 | u1[num_n_words - 1] = 0; |
allankliu | 0:b6fdeddc0bc9 | 1519 | bits2int(u1, message_hash, hash_size, curve); |
allankliu | 0:b6fdeddc0bc9 | 1520 | uECC_vli_modMult(u1, u1, z, curve->n, num_n_words); /* u1 = e/s */ |
allankliu | 0:b6fdeddc0bc9 | 1521 | uECC_vli_modMult(u2, r, z, curve->n, num_n_words); /* u2 = r/s */ |
allankliu | 0:b6fdeddc0bc9 | 1522 | |
allankliu | 0:b6fdeddc0bc9 | 1523 | /* Calculate sum = G + Q. */ |
allankliu | 0:b6fdeddc0bc9 | 1524 | uECC_vli_set(sum, _public, num_words); |
allankliu | 0:b6fdeddc0bc9 | 1525 | uECC_vli_set(sum + num_words, _public + num_words, num_words); |
allankliu | 0:b6fdeddc0bc9 | 1526 | uECC_vli_set(tx, curve->G, num_words); |
allankliu | 0:b6fdeddc0bc9 | 1527 | uECC_vli_set(ty, curve->G + num_words, num_words); |
allankliu | 0:b6fdeddc0bc9 | 1528 | uECC_vli_modSub(z, sum, tx, curve->p, num_words); /* z = x2 - x1 */ |
allankliu | 0:b6fdeddc0bc9 | 1529 | XYcZ_add(tx, ty, sum, sum + num_words, curve); |
allankliu | 0:b6fdeddc0bc9 | 1530 | uECC_vli_modInv(z, z, curve->p, num_words); /* z = 1/z */ |
allankliu | 0:b6fdeddc0bc9 | 1531 | apply_z(sum, sum + num_words, z, curve); |
allankliu | 0:b6fdeddc0bc9 | 1532 | |
allankliu | 0:b6fdeddc0bc9 | 1533 | /* Use Shamir's trick to calculate u1*G + u2*Q */ |
allankliu | 0:b6fdeddc0bc9 | 1534 | points[0] = 0; |
allankliu | 0:b6fdeddc0bc9 | 1535 | points[1] = curve->G; |
allankliu | 0:b6fdeddc0bc9 | 1536 | points[2] = _public; |
allankliu | 0:b6fdeddc0bc9 | 1537 | points[3] = sum; |
allankliu | 0:b6fdeddc0bc9 | 1538 | num_bits = smax(uECC_vli_numBits(u1, num_n_words), |
allankliu | 0:b6fdeddc0bc9 | 1539 | uECC_vli_numBits(u2, num_n_words)); |
allankliu | 0:b6fdeddc0bc9 | 1540 | |
allankliu | 0:b6fdeddc0bc9 | 1541 | point = points[(!!uECC_vli_testBit(u1, num_bits - 1)) | |
allankliu | 0:b6fdeddc0bc9 | 1542 | ((!!uECC_vli_testBit(u2, num_bits - 1)) << 1)]; |
allankliu | 0:b6fdeddc0bc9 | 1543 | uECC_vli_set(rx, point, num_words); |
allankliu | 0:b6fdeddc0bc9 | 1544 | uECC_vli_set(ry, point + num_words, num_words); |
allankliu | 0:b6fdeddc0bc9 | 1545 | uECC_vli_clear(z, num_words); |
allankliu | 0:b6fdeddc0bc9 | 1546 | z[0] = 1; |
allankliu | 0:b6fdeddc0bc9 | 1547 | |
allankliu | 0:b6fdeddc0bc9 | 1548 | for (i = num_bits - 2; i >= 0; --i) { |
allankliu | 0:b6fdeddc0bc9 | 1549 | uECC_word_t index; |
allankliu | 0:b6fdeddc0bc9 | 1550 | curve->double_jacobian(rx, ry, z, curve); |
allankliu | 0:b6fdeddc0bc9 | 1551 | |
allankliu | 0:b6fdeddc0bc9 | 1552 | index = (!!uECC_vli_testBit(u1, i)) | ((!!uECC_vli_testBit(u2, i)) << 1); |
allankliu | 0:b6fdeddc0bc9 | 1553 | point = points[index]; |
allankliu | 0:b6fdeddc0bc9 | 1554 | if (point) { |
allankliu | 0:b6fdeddc0bc9 | 1555 | uECC_vli_set(tx, point, num_words); |
allankliu | 0:b6fdeddc0bc9 | 1556 | uECC_vli_set(ty, point + num_words, num_words); |
allankliu | 0:b6fdeddc0bc9 | 1557 | apply_z(tx, ty, z, curve); |
allankliu | 0:b6fdeddc0bc9 | 1558 | uECC_vli_modSub(tz, rx, tx, curve->p, num_words); /* Z = x2 - x1 */ |
allankliu | 0:b6fdeddc0bc9 | 1559 | XYcZ_add(tx, ty, rx, ry, curve); |
allankliu | 0:b6fdeddc0bc9 | 1560 | uECC_vli_modMult_fast(z, z, tz, curve); |
allankliu | 0:b6fdeddc0bc9 | 1561 | } |
allankliu | 0:b6fdeddc0bc9 | 1562 | } |
allankliu | 0:b6fdeddc0bc9 | 1563 | |
allankliu | 0:b6fdeddc0bc9 | 1564 | uECC_vli_modInv(z, z, curve->p, num_words); /* Z = 1/Z */ |
allankliu | 0:b6fdeddc0bc9 | 1565 | apply_z(rx, ry, z, curve); |
allankliu | 0:b6fdeddc0bc9 | 1566 | |
allankliu | 0:b6fdeddc0bc9 | 1567 | /* v = x1 (mod n) */ |
allankliu | 0:b6fdeddc0bc9 | 1568 | if (uECC_vli_cmp_unsafe(curve->n, rx, num_n_words) != 1) { |
allankliu | 0:b6fdeddc0bc9 | 1569 | uECC_vli_sub(rx, rx, curve->n, num_n_words); |
allankliu | 0:b6fdeddc0bc9 | 1570 | } |
allankliu | 0:b6fdeddc0bc9 | 1571 | |
allankliu | 0:b6fdeddc0bc9 | 1572 | /* Accept only if v == r. */ |
allankliu | 0:b6fdeddc0bc9 | 1573 | return (int)(uECC_vli_equal(rx, r, num_words)); |
allankliu | 0:b6fdeddc0bc9 | 1574 | } |
allankliu | 0:b6fdeddc0bc9 | 1575 | |
allankliu | 0:b6fdeddc0bc9 | 1576 | #if uECC_ENABLE_VLI_API |
allankliu | 0:b6fdeddc0bc9 | 1577 | |
allankliu | 0:b6fdeddc0bc9 | 1578 | unsigned uECC_curve_num_words(uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1579 | return curve->num_words; |
allankliu | 0:b6fdeddc0bc9 | 1580 | } |
allankliu | 0:b6fdeddc0bc9 | 1581 | |
allankliu | 0:b6fdeddc0bc9 | 1582 | unsigned uECC_curve_num_bytes(uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1583 | return curve->num_bytes; |
allankliu | 0:b6fdeddc0bc9 | 1584 | } |
allankliu | 0:b6fdeddc0bc9 | 1585 | |
allankliu | 0:b6fdeddc0bc9 | 1586 | unsigned uECC_curve_num_bits(uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1587 | return curve->num_bytes * 8; |
allankliu | 0:b6fdeddc0bc9 | 1588 | } |
allankliu | 0:b6fdeddc0bc9 | 1589 | |
allankliu | 0:b6fdeddc0bc9 | 1590 | unsigned uECC_curve_num_n_words(uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1591 | return BITS_TO_WORDS(curve->num_n_bits); |
allankliu | 0:b6fdeddc0bc9 | 1592 | } |
allankliu | 0:b6fdeddc0bc9 | 1593 | |
allankliu | 0:b6fdeddc0bc9 | 1594 | unsigned uECC_curve_num_n_bytes(uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1595 | return BITS_TO_BYTES(curve->num_n_bits); |
allankliu | 0:b6fdeddc0bc9 | 1596 | } |
allankliu | 0:b6fdeddc0bc9 | 1597 | |
allankliu | 0:b6fdeddc0bc9 | 1598 | unsigned uECC_curve_num_n_bits(uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1599 | return curve->num_n_bits; |
allankliu | 0:b6fdeddc0bc9 | 1600 | } |
allankliu | 0:b6fdeddc0bc9 | 1601 | |
allankliu | 0:b6fdeddc0bc9 | 1602 | const uECC_word_t *uECC_curve_p(uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1603 | return curve->p; |
allankliu | 0:b6fdeddc0bc9 | 1604 | } |
allankliu | 0:b6fdeddc0bc9 | 1605 | |
allankliu | 0:b6fdeddc0bc9 | 1606 | const uECC_word_t *uECC_curve_n(uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1607 | return curve->n; |
allankliu | 0:b6fdeddc0bc9 | 1608 | } |
allankliu | 0:b6fdeddc0bc9 | 1609 | |
allankliu | 0:b6fdeddc0bc9 | 1610 | const uECC_word_t *uECC_curve_G(uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1611 | return curve->G; |
allankliu | 0:b6fdeddc0bc9 | 1612 | } |
allankliu | 0:b6fdeddc0bc9 | 1613 | |
allankliu | 0:b6fdeddc0bc9 | 1614 | const uECC_word_t *uECC_curve_b(uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1615 | return curve->b; |
allankliu | 0:b6fdeddc0bc9 | 1616 | } |
allankliu | 0:b6fdeddc0bc9 | 1617 | |
allankliu | 0:b6fdeddc0bc9 | 1618 | #if uECC_SUPPORT_COMPRESSED_POINT |
allankliu | 0:b6fdeddc0bc9 | 1619 | void uECC_vli_mod_sqrt(uECC_word_t *a, uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1620 | curve->mod_sqrt(a, curve); |
allankliu | 0:b6fdeddc0bc9 | 1621 | } |
allankliu | 0:b6fdeddc0bc9 | 1622 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1623 | |
allankliu | 0:b6fdeddc0bc9 | 1624 | void uECC_vli_mmod_fast(uECC_word_t *result, uECC_word_t *product, uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1625 | #if (uECC_OPTIMIZATION_LEVEL > 0) |
allankliu | 0:b6fdeddc0bc9 | 1626 | curve->mmod_fast(result, product); |
allankliu | 0:b6fdeddc0bc9 | 1627 | #else |
allankliu | 0:b6fdeddc0bc9 | 1628 | uECC_vli_mmod(result, product, curve->p, curve->num_words); |
allankliu | 0:b6fdeddc0bc9 | 1629 | #endif |
allankliu | 0:b6fdeddc0bc9 | 1630 | } |
allankliu | 0:b6fdeddc0bc9 | 1631 | |
allankliu | 0:b6fdeddc0bc9 | 1632 | void uECC_point_mult(uECC_word_t *result, |
allankliu | 0:b6fdeddc0bc9 | 1633 | const uECC_word_t *point, |
allankliu | 0:b6fdeddc0bc9 | 1634 | const uECC_word_t *scalar, |
allankliu | 0:b6fdeddc0bc9 | 1635 | uECC_Curve curve) { |
allankliu | 0:b6fdeddc0bc9 | 1636 | uECC_word_t tmp1[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1637 | uECC_word_t tmp2[uECC_MAX_WORDS]; |
allankliu | 0:b6fdeddc0bc9 | 1638 | uECC_word_t *p2[2] = {tmp1, tmp2}; |
allankliu | 0:b6fdeddc0bc9 | 1639 | uECC_word_t carry = regularize_k(scalar, tmp1, tmp2, curve); |
allankliu | 0:b6fdeddc0bc9 | 1640 | |
allankliu | 0:b6fdeddc0bc9 | 1641 | EccPoint_mult(result, point, p2[!carry], 0, curve->num_n_bits + 1, curve); |
allankliu | 0:b6fdeddc0bc9 | 1642 | } |
allankliu | 0:b6fdeddc0bc9 | 1643 | |
allankliu | 0:b6fdeddc0bc9 | 1644 | #endif /* uECC_ENABLE_VLI_API */ |