1 /* 2 * Copyright 2017-2021 The OpenSSL Project Authors. All Rights Reserved. 3 * Copyright 2015-2016 Cryptography Research, Inc. 4 * 5 * Licensed under the Apache License 2.0 (the "License"). You may not use 6 * this file except in compliance with the License. You can obtain a copy 7 * in the file LICENSE in the source distribution or at 8 * https://www.openssl.org/source/license.html 9 * 10 * Originally written by Mike Hamburg 11 */ 12 #include "field.h" 13 14 static const gf MODULUS = { 15 FIELD_LITERAL(0xffffffffffffffULL, 0xffffffffffffffULL, 0xffffffffffffffULL, 16 0xffffffffffffffULL, 0xfffffffffffffeULL, 0xffffffffffffffULL, 17 0xffffffffffffffULL, 0xffffffffffffffULL) 18 }; 19 20 /* Serialize to wire format. */ 21 void gf_serialize(uint8_t *serial, const gf x, int with_hibit) 22 { 23 unsigned int j = 0, fill = 0; 24 dword_t buffer = 0; 25 int i; 26 gf red; 27 28 gf_copy(red, x); 29 gf_strong_reduce(red); 30 if (!with_hibit) 31 assert(gf_hibit(red) == 0); 32 33 for (i = 0; i < (with_hibit ? X_SER_BYTES : SER_BYTES); i++) { 34 if (fill < 8 && j < NLIMBS) { 35 buffer |= ((dword_t) red->limb[LIMBPERM(j)]) << fill; 36 fill += LIMB_PLACE_VALUE(LIMBPERM(j)); 37 j++; 38 } 39 serial[i] = (uint8_t)buffer; 40 fill -= 8; 41 buffer >>= 8; 42 } 43 } 44 45 /* Return high bit of x = low bit of 2x mod p */ 46 mask_t gf_hibit(const gf x) 47 { 48 gf y; 49 50 gf_add(y, x, x); 51 gf_strong_reduce(y); 52 return 0 - (y->limb[0] & 1); 53 } 54 55 /* Return high bit of x = low bit of 2x mod p */ 56 mask_t gf_lobit(const gf x) 57 { 58 gf y; 59 60 gf_copy(y, x); 61 gf_strong_reduce(y); 62 return 0 - (y->limb[0] & 1); 63 } 64 65 /* Deserialize from wire format; return -1 on success and 0 on failure. */ 66 mask_t gf_deserialize(gf x, const uint8_t serial[SER_BYTES], int with_hibit, 67 uint8_t hi_nmask) 68 { 69 unsigned int j = 0, fill = 0; 70 dword_t buffer = 0; 71 dsword_t scarry = 0; 72 const unsigned nbytes = with_hibit ? X_SER_BYTES : SER_BYTES; 73 unsigned int i; 74 mask_t succ; 75 76 for (i = 0; i < NLIMBS; i++) { 77 while (fill < LIMB_PLACE_VALUE(LIMBPERM(i)) && j < nbytes) { 78 uint8_t sj; 79 80 sj = serial[j]; 81 if (j == nbytes - 1) 82 sj &= ~hi_nmask; 83 buffer |= ((dword_t) sj) << fill; 84 fill += 8; 85 j++; 86 } 87 x->limb[LIMBPERM(i)] = (word_t) 88 ((i < NLIMBS - 1) ? buffer & LIMB_MASK(LIMBPERM(i)) : buffer); 89 fill -= LIMB_PLACE_VALUE(LIMBPERM(i)); 90 buffer >>= LIMB_PLACE_VALUE(LIMBPERM(i)); 91 scarry = 92 (scarry + x->limb[LIMBPERM(i)] - 93 MODULUS->limb[LIMBPERM(i)]) >> (8 * sizeof(word_t)); 94 } 95 succ = with_hibit ? 0 - (mask_t) 1 : ~gf_hibit(x); 96 return succ & word_is_zero((word_t)buffer) & ~word_is_zero((word_t)scarry); 97 } 98 99 /* Reduce to canonical form. */ 100 void gf_strong_reduce(gf a) 101 { 102 dsword_t scarry; 103 word_t scarry_0; 104 dword_t carry = 0; 105 unsigned int i; 106 107 /* first, clear high */ 108 gf_weak_reduce(a); /* Determined to have negligible perf impact. */ 109 110 /* now the total is less than 2p */ 111 112 /* compute total_value - p. No need to reduce mod p. */ 113 scarry = 0; 114 for (i = 0; i < NLIMBS; i++) { 115 scarry = scarry + a->limb[LIMBPERM(i)] - MODULUS->limb[LIMBPERM(i)]; 116 a->limb[LIMBPERM(i)] = scarry & LIMB_MASK(LIMBPERM(i)); 117 scarry >>= LIMB_PLACE_VALUE(LIMBPERM(i)); 118 } 119 120 /* 121 * uncommon case: it was >= p, so now scarry = 0 and this = x common case: 122 * it was < p, so now scarry = -1 and this = x - p + 2^255 so let's add 123 * back in p. will carry back off the top for 2^255. 124 */ 125 assert(scarry == 0 || scarry == -1); 126 127 scarry_0 = (word_t)scarry; 128 129 /* add it back */ 130 for (i = 0; i < NLIMBS; i++) { 131 carry = 132 carry + a->limb[LIMBPERM(i)] + 133 (scarry_0 & MODULUS->limb[LIMBPERM(i)]); 134 a->limb[LIMBPERM(i)] = carry & LIMB_MASK(LIMBPERM(i)); 135 carry >>= LIMB_PLACE_VALUE(LIMBPERM(i)); 136 } 137 138 assert(carry < 2 && ((word_t)carry + scarry_0) == 0); 139 } 140 141 /* Subtract two gf elements d=a-b */ 142 void gf_sub(gf d, const gf a, const gf b) 143 { 144 gf_sub_RAW(d, a, b); 145 gf_bias(d, 2); 146 gf_weak_reduce(d); 147 } 148 149 /* Add two field elements d = a+b */ 150 void gf_add(gf d, const gf a, const gf b) 151 { 152 gf_add_RAW(d, a, b); 153 gf_weak_reduce(d); 154 } 155 156 /* Compare a==b */ 157 mask_t gf_eq(const gf a, const gf b) 158 { 159 gf c; 160 mask_t ret = 0; 161 unsigned int i; 162 163 gf_sub(c, a, b); 164 gf_strong_reduce(c); 165 166 for (i = 0; i < NLIMBS; i++) 167 ret |= c->limb[LIMBPERM(i)]; 168 169 return word_is_zero(ret); 170 } 171 172 mask_t gf_isr(gf a, const gf x) 173 { 174 gf L0, L1, L2; 175 176 gf_sqr(L1, x); 177 gf_mul(L2, x, L1); 178 gf_sqr(L1, L2); 179 gf_mul(L2, x, L1); 180 gf_sqrn(L1, L2, 3); 181 gf_mul(L0, L2, L1); 182 gf_sqrn(L1, L0, 3); 183 gf_mul(L0, L2, L1); 184 gf_sqrn(L2, L0, 9); 185 gf_mul(L1, L0, L2); 186 gf_sqr(L0, L1); 187 gf_mul(L2, x, L0); 188 gf_sqrn(L0, L2, 18); 189 gf_mul(L2, L1, L0); 190 gf_sqrn(L0, L2, 37); 191 gf_mul(L1, L2, L0); 192 gf_sqrn(L0, L1, 37); 193 gf_mul(L1, L2, L0); 194 gf_sqrn(L0, L1, 111); 195 gf_mul(L2, L1, L0); 196 gf_sqr(L0, L2); 197 gf_mul(L1, x, L0); 198 gf_sqrn(L0, L1, 223); 199 gf_mul(L1, L2, L0); 200 gf_sqr(L2, L1); 201 gf_mul(L0, L2, x); 202 gf_copy(a, L1); 203 return gf_eq(L0, ONE); 204 } 205