1 /* Microsoft Reference Implementation for TPM 2.0 2 * 3 * The copyright in this software is being made available under the BSD License, 4 * included below. This software may be subject to other third party and 5 * contributor rights, including patent rights, and no such rights are granted 6 * under this license. 7 * 8 * Copyright (c) Microsoft Corporation 9 * 10 * All rights reserved. 11 * 12 * BSD License 13 * 14 * Redistribution and use in source and binary forms, with or without modification, 15 * are permitted provided that the following conditions are met: 16 * 17 * Redistributions of source code must retain the above copyright notice, this list 18 * of conditions and the following disclaimer. 19 * 20 * Redistributions in binary form must reproduce the above copyright notice, this 21 * list of conditions and the following disclaimer in the documentation and/or 22 * other materials provided with the distribution. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ""AS IS"" 25 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 27 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR 28 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 29 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 30 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 31 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 32 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34 */ 35 //** Introduction 36 37 // This file contains the definitions needed for defining the internal BIGNUM 38 // structure. 39 40 // A BIGNUM is a pointer to a structure. The structure has three fields. The 41 // last field is and array (d) of crypt_uword_t. Each word is in machine format 42 // (big- or little-endian) with the words in ascending significance (i.e. words 43 // in little-endian order). This is the order that seems to be used in every 44 // big number library in the worlds, so... 45 // 46 // The first field in the structure (allocated) is the number of words in 'd'. 47 // This is the upper limit on the size of the number that can be held in the 48 // structure. This differs from libraries like OpenSSL as this is not intended 49 // to deal with numbers of arbitrary size; just numbers that are needed to deal 50 // with the algorithms that are defined in the TPM implementation. 51 // 52 // The second field in the structure (size) is the number of significant words 53 // in 'n'. When this number is zero, the number is zero. The word at used-1 should 54 // never be zero. All words between d[size] and d[allocated-1] should be zero. 55 56 //** Defines 57 58 #ifndef _BN_NUMBERS_H 59 #define _BN_NUMBERS_H 60 61 #if RADIX_BITS == 64 62 # define RADIX_LOG2 6 63 #elif RADIX_BITS == 32 64 #define RADIX_LOG2 5 65 #else 66 # error "Unsupported radix" 67 #endif 68 69 #define RADIX_MOD(x) ((x) & ((1 << RADIX_LOG2) - 1)) 70 #define RADIX_DIV(x) ((x) >> RADIX_LOG2) 71 #define RADIX_MASK ((((crypt_uword_t)1) << RADIX_LOG2) - 1) 72 73 #define BITS_TO_CRYPT_WORDS(bits) RADIX_DIV((bits) + (RADIX_BITS - 1)) 74 #define BYTES_TO_CRYPT_WORDS(bytes) BITS_TO_CRYPT_WORDS(bytes * 8) 75 #define SIZE_IN_CRYPT_WORDS(thing) BYTES_TO_CRYPT_WORDS(sizeof(thing)) 76 77 #if RADIX_BITS == 64 78 #define SWAP_CRYPT_WORD(x) REVERSE_ENDIAN_64(x) 79 typedef uint64_t crypt_uword_t; 80 typedef int64_t crypt_word_t; 81 # define TO_CRYPT_WORD_64 BIG_ENDIAN_BYTES_TO_UINT64 82 # define TO_CRYPT_WORD_32(a, b, c, d) TO_CRYPT_WORD_64(0, 0, 0, 0, a, b, c, d) 83 #elif RADIX_BITS == 32 84 # define SWAP_CRYPT_WORD(x) REVERSE_ENDIAN_32((x)) 85 typedef uint32_t crypt_uword_t; 86 typedef int32_t crypt_word_t; 87 # define TO_CRYPT_WORD_64(a, b, c, d, e, f, g, h) \ 88 BIG_ENDIAN_BYTES_TO_UINT32(e, f, g, h), \ 89 BIG_ENDIAN_BYTES_TO_UINT32(a, b, c, d) 90 #endif 91 92 #define MAX_CRYPT_UWORD (~((crypt_uword_t)0)) 93 #define MAX_CRYPT_WORD ((crypt_word_t)(MAX_CRYPT_UWORD >> 1)) 94 #define MIN_CRYPT_WORD (~MAX_CRYPT_WORD) 95 96 #define LARGEST_NUMBER (MAX((ALG_RSA * MAX_RSA_KEY_BYTES), \ 97 MAX((ALG_ECC * MAX_ECC_KEY_BYTES), MAX_DIGEST_SIZE))) 98 #define LARGEST_NUMBER_BITS (LARGEST_NUMBER * 8) 99 100 #define MAX_ECC_PARAMETER_BYTES (MAX_ECC_KEY_BYTES * ALG_ECC) 101 102 // These are the basic big number formats. This is convertible to the library- 103 // specific format without too much difficulty. For the math performed using 104 // these numbers, the value is always positive. 105 #define BN_STRUCT_DEF(count) struct { \ 106 crypt_uword_t allocated; \ 107 crypt_uword_t size; \ 108 crypt_uword_t d[count]; \ 109 } 110 111 typedef BN_STRUCT_DEF(1) bignum_t; 112 #ifndef bigNum 113 typedef bignum_t *bigNum; 114 typedef const bignum_t *bigConst; 115 #endif 116 117 extern const bignum_t BnConstZero; 118 119 // The Functions to access the properties of a big number. 120 // Get number of allocated words 121 #define BnGetAllocated(x) (unsigned)((x)->allocated) 122 123 // Get number of words used 124 #define BnGetSize(x) ((x)->size) 125 126 // Get a pointer to the data array 127 #define BnGetArray(x) ((crypt_uword_t *)&((x)->d[0])) 128 129 // Get the nth word of a BIGNUM (zero-based) 130 #define BnGetWord(x, i) (crypt_uword_t)((x)->d[i]) 131 132 // Some things that are done often. 133 134 // Test to see if a bignum_t is equal to zero 135 #define BnEqualZero(bn) (BnGetSize(bn) == 0) 136 137 // Test to see if a bignum_t is equal to a word type 138 #define BnEqualWord(bn, word) \ 139 ((BnGetSize(bn) == 1) && (BnGetWord(bn, 0) == (crypt_uword_t)word)) 140 141 // Determine if a BIGNUM is even. A zero is even. Although the 142 // indication that a number is zero is that its size is zero, 143 // all words of the number are 0 so this test works on zero. 144 #define BnIsEven(n) ((BnGetWord(n, 0) & 1) == 0) 145 146 // The macros below are used to define BIGNUM values of the required 147 // size. The values are allocated on the stack so they can be 148 // treated like simple local values. 149 150 // This will call the initialization function for a defined bignum_t. 151 // This sets the allocated and used fields and clears the words of 'n'. 152 #define BN_INIT(name) \ 153 (bigNum)BnInit((bigNum)&(name), \ 154 BYTES_TO_CRYPT_WORDS(sizeof(name.d))) 155 156 // In some cases, a function will need the address of the structure 157 // associated with a variable. The structure for a BIGNUM variable 158 // of 'name' is 'name_'. Generally, when the structure is created, it 159 // is initialized and a parameter is created with a pointer to the 160 // structure. The pointer has the 'name' and the structure it points 161 // to is 'name_' 162 #define BN_ADDRESS(name) (bigNum)&name##_ 163 164 #define BN_CONST(name, words, initializer) \ 165 typedef const struct name##_type { \ 166 crypt_uword_t allocated; \ 167 crypt_uword_t size; \ 168 crypt_uword_t d[words < 1 ? 1 : words]; \ 169 } name##_type; \ 170 name##_type name = {(words < 1 ? 1 : words), words, {initializer}}; 171 172 #define BN_STRUCT_ALLOCATION(bits) (BITS_TO_CRYPT_WORDS(bits) + 1) 173 174 // Create a structure of the correct size. 175 #define BN_STRUCT(bits) \ 176 BN_STRUCT_DEF(BN_STRUCT_ALLOCATION(bits)) 177 178 // Define a BIGNUM type with a specific allocation 179 #define BN_TYPE(name, bits) \ 180 typedef BN_STRUCT(bits) bn_##name##_t 181 182 // This creates a local BIGNUM variable of a specific size and 183 // initializes it from a TPM2B input parameter. 184 #define BN_INITIALIZED(name, bits, initializer) \ 185 BN_STRUCT(bits) name##_; \ 186 bigNum name = BnFrom2B(BN_INIT(name##_), \ 187 (const TPM2B *)initializer) 188 189 // Create a local variable that can hold a number with 'bits' 190 #define BN_VAR(name, bits) \ 191 BN_STRUCT(bits) _##name; \ 192 bigNum name = BN_INIT(_##name) 193 194 // Create a type that can hold the largest number defined by the 195 // implementation. 196 #define BN_MAX(name) BN_VAR(name, LARGEST_NUMBER_BITS) 197 #define BN_MAX_INITIALIZED(name, initializer) \ 198 BN_INITIALIZED(name, LARGEST_NUMBER_BITS, initializer) 199 200 // A word size value is useful 201 #define BN_WORD(name) BN_VAR(name, RADIX_BITS) 202 203 // This is used to create a word-size BIGNUM and initialize it with 204 // an input parameter to a function. 205 #define BN_WORD_INITIALIZED(name, initial) \ 206 BN_STRUCT(RADIX_BITS) name##_; \ 207 bigNum name = BnInitializeWord((bigNum)&name##_, \ 208 BN_STRUCT_ALLOCATION(RADIX_BITS), initial) 209 210 // ECC-Specific Values 211 212 // This is the format for a point. It is always in affine format. The Z value is 213 // carried as part of the point, primarily to simplify the interface to the support 214 // library. Rather than have the interface layer have to create space for the 215 // point each time it is used... 216 // The x, y, and z values are pointers to bigNum values and not in-line versions of 217 // the numbers. This is a relic of the days when there was no standard TPM format 218 // for the numbers 219 typedef struct _bn_point_t 220 { 221 bigNum x; 222 bigNum y; 223 bigNum z; 224 } bn_point_t; 225 226 typedef bn_point_t *bigPoint; 227 typedef const bn_point_t *pointConst; 228 229 typedef struct constant_point_t 230 { 231 bigConst x; 232 bigConst y; 233 bigConst z; 234 } constant_point_t; 235 236 #define ECC_BITS (MAX_ECC_KEY_BYTES * 8) 237 BN_TYPE(ecc, ECC_BITS); 238 #define ECC_NUM(name) BN_VAR(name, ECC_BITS) 239 #define ECC_INITIALIZED(name, initializer) \ 240 BN_INITIALIZED(name, ECC_BITS, initializer) 241 242 #define POINT_INSTANCE(name, bits) \ 243 BN_STRUCT (bits) name##_x = \ 244 {BITS_TO_CRYPT_WORDS ( bits ), 0,{0}}; \ 245 BN_STRUCT ( bits ) name##_y = \ 246 {BITS_TO_CRYPT_WORDS ( bits ), 0,{0}}; \ 247 BN_STRUCT ( bits ) name##_z = \ 248 {BITS_TO_CRYPT_WORDS ( bits ), 0,{0}}; \ 249 bn_point_t name##_ 250 251 #define POINT_INITIALIZER(name) \ 252 BnInitializePoint(&name##_, (bigNum)&name##_x, \ 253 (bigNum)&name##_y, (bigNum)&name##_z) 254 255 #define POINT_INITIALIZED(name, initValue) \ 256 POINT_INSTANCE(name, MAX_ECC_KEY_BITS); \ 257 bigPoint name = BnPointFrom2B( \ 258 POINT_INITIALIZER(name), \ 259 initValue) 260 261 #define POINT_VAR(name, bits) \ 262 POINT_INSTANCE (name, bits); \ 263 bigPoint name = POINT_INITIALIZER(name) 264 265 #define POINT(name) POINT_VAR(name, MAX_ECC_KEY_BITS) 266 267 // Structure for the curve parameters. This is an analog to the 268 // TPMS_ALGORITHM_DETAIL_ECC 269 typedef struct 270 { 271 bigConst prime; // a prime number 272 bigConst order; // the order of the curve 273 bigConst h; // cofactor 274 bigConst a; // linear coefficient 275 bigConst b; // constant term 276 constant_point_t base; // base point 277 } ECC_CURVE_DATA; 278 279 // Access macros for the ECC_CURVE structure. The parameter 'C' is a pointer 280 // to an ECC_CURVE_DATA structure. In some libraries, the curve structure contains 281 // a pointer to an ECC_CURVE_DATA structure as well as some other bits. For those 282 // cases, the AccessCurveData macro is used in the code to first get the pointer 283 // to the ECC_CURVE_DATA for access. In some cases, the macro does nothing. 284 #define CurveGetPrime(C) ((C)->prime) 285 #define CurveGetOrder(C) ((C)->order) 286 #define CurveGetCofactor(C) ((C)->h) 287 #define CurveGet_a(C) ((C)->a) 288 #define CurveGet_b(C) ((C)->b) 289 #define CurveGetG(C) ((pointConst)&((C)->base)) 290 #define CurveGetGx(C) ((C)->base.x) 291 #define CurveGetGy(C) ((C)->base.y) 292 293 294 // Convert bytes in initializers 295 // This is used for CryptEccData.c. 296 #define BIG_ENDIAN_BYTES_TO_UINT32(a, b, c, d) \ 297 ( ((UINT32)(a) << 24) \ 298 + ((UINT32)(b) << 16) \ 299 + ((UINT32)(c) << 8) \ 300 + ((UINT32)(d)) \ 301 ) 302 303 #define BIG_ENDIAN_BYTES_TO_UINT64(a, b, c, d, e, f, g, h) \ 304 ( ((UINT64)(a) << 56) \ 305 + ((UINT64)(b) << 48) \ 306 + ((UINT64)(c) << 40) \ 307 + ((UINT64)(d) << 32) \ 308 + ((UINT64)(e) << 24) \ 309 + ((UINT64)(f) << 16) \ 310 + ((UINT64)(g) << 8) \ 311 + ((UINT64)(h)) \ 312 ) 313 314 #ifndef RADIX_BYTES 315 # if RADIX_BITS == 32 316 # define RADIX_BYTES 4 317 # elif RADIX_BITS == 64 318 # define RADIX_BYTES 8 319 # else 320 # error "RADIX_BITS must either be 32 or 64" 321 # endif 322 #endif 323 324 // These macros are used for data initialization of big number ECC constants 325 // These two macros combine a macro for data definition with a macro for 326 // structure initilization. The 'a' parameter is a macro that gives numbers to 327 // each of the bytes of the initializer and defines where each of the numberd 328 // bytes will show up in the final structure. The 'b' value is a structure that 329 // contains the requisite number of bytes in big endian order. S, the MJOIN 330 // and JOIND macros will combine a macro defining a data layout with a macro defining 331 // the data to be places. Generally, these macros will only need expansion when 332 // CryptEccData.c gets compiled. 333 #define JOINED(a,b) a b 334 #define MJOIN(a,b) a b 335 336 #define B4_TO_BN(a, b, c, d) (((((a << 8) + b) << 8) + c) + d) 337 #if RADIX_BYTES == 64 338 #define B8_TO_BN(a, b, c, d, e, f, g, h) \ 339 (UINT64)(((((((((((((((a) << 8) | b) << 8) | c) << 8) | d) << 8) \ 340 e) << 8) | f) << 8) | g) << 8) | h) 341 #define B1_TO_BN(a) B8_TO_BN(0, 0, 0, 0, 0, 0, 0, a) 342 #define B2_TO_BN(a, b) B8_TO_BN(0, 0, 0, 0, 0, 0, a, b) 343 #define B3_TO_BN(a, b, c) B8_TO_BN(0, 0, 0, 0, 0, a, b, c) 344 #define B4_TO_BN(a, b, c, d) B8_TO_BN(0, 0, 0, 0, a, b, c, d) 345 #define B5_TO_BN(a, b, c, d, e) B8_TO_BN(0, 0, 0, a, b, c, d, e) 346 #define B6_TO_BN(a, b, c, d, e, f) B8_TO_BN(0, 0, a, b, c, d, e, f) 347 #define B7_TO_BN(a, b, c, d, e, f, g) B8_TO_BN(0, a, b, c, d, e, f, g) 348 #else 349 #define B1_TO_BN(a) B4_TO_BN(0, 0, 0, a) 350 #define B2_TO_BN(a, b) B4_TO_BN(0, 0, a, b) 351 #define B3_TO_BN(a, b, c) B4_TO_BN(0, a, b, c) 352 #define B4_TO_BN(a, b, c, d) (((((a << 8) + b) << 8) + c) + d) 353 #define B5_TO_BN(a, b, c, d, e) B4_TO_BN(b, c, d, e), B1_TO_BN(a) 354 #define B6_TO_BN(a, b, c, d, e, f) B4_TO_BN(c, d, e, f), B2_TO_BN(a, b) 355 #define B7_TO_BN(a, b, c, d, e, f, g) B4_TO_BN(d, e, f, g), B3_TO_BN(a, b, c) 356 #define B8_TO_BN(a, b, c, d, e, f, g, h) B4_TO_BN(e, f, g, h), B4_TO_BN(a, b, c, d) 357 358 #endif 359 360 // Add implementation dependent definitions for other ECC Values and for linkages. 361 #include LIB_INCLUDE(MATH_LIB, Math) 362 363 364 #endif // _BN_NUMBERS_H