1 /* 2 * Copyright 2017-2023 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[SER_BYTES], 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)((i < NLIMBS - 1) ? buffer & LIMB_MASK(LIMBPERM(i)) : buffer); 88 fill -= LIMB_PLACE_VALUE(LIMBPERM(i)); 89 buffer >>= LIMB_PLACE_VALUE(LIMBPERM(i)); 90 scarry = (scarry + x->limb[LIMBPERM(i)] - MODULUS->limb[LIMBPERM(i)]) >> (8 * sizeof(word_t)); 91 } 92 succ = with_hibit ? 0 - (mask_t)1 : ~gf_hibit(x); 93 return succ & word_is_zero((word_t)buffer) & ~word_is_zero((word_t)scarry); 94 } 95 96 /* Reduce to canonical form. */ 97 void gf_strong_reduce(gf a) 98 { 99 dsword_t scarry; 100 word_t scarry_0; 101 dword_t carry = 0; 102 unsigned int i; 103 104 /* first, clear high */ 105 gf_weak_reduce(a); /* Determined to have negligible perf impact. */ 106 107 /* now the total is less than 2p */ 108 109 /* compute total_value - p. No need to reduce mod p. */ 110 scarry = 0; 111 for (i = 0; i < NLIMBS; i++) { 112 scarry = scarry + a->limb[LIMBPERM(i)] - MODULUS->limb[LIMBPERM(i)]; 113 a->limb[LIMBPERM(i)] = scarry & LIMB_MASK(LIMBPERM(i)); 114 scarry >>= LIMB_PLACE_VALUE(LIMBPERM(i)); 115 } 116 117 /* 118 * uncommon case: it was >= p, so now scarry = 0 and this = x common case: 119 * it was < p, so now scarry = -1 and this = x - p + 2^255 so let's add 120 * back in p. will carry back off the top for 2^255. 121 */ 122 assert(scarry == 0 || scarry == -1); 123 124 scarry_0 = (word_t)scarry; 125 126 /* add it back */ 127 for (i = 0; i < NLIMBS; i++) { 128 carry = carry + a->limb[LIMBPERM(i)] + (scarry_0 & MODULUS->limb[LIMBPERM(i)]); 129 a->limb[LIMBPERM(i)] = carry & LIMB_MASK(LIMBPERM(i)); 130 carry >>= LIMB_PLACE_VALUE(LIMBPERM(i)); 131 } 132 133 assert(carry < 2 && ((word_t)carry + scarry_0) == 0); 134 } 135 136 /* Subtract two gf elements d=a-b */ 137 void gf_sub(gf d, const gf a, const gf b) 138 { 139 gf_sub_RAW(d, a, b); 140 gf_bias(d, 2); 141 gf_weak_reduce(d); 142 } 143 144 /* Add two field elements d = a+b */ 145 void gf_add(gf d, const gf a, const gf b) 146 { 147 gf_add_RAW(d, a, b); 148 gf_weak_reduce(d); 149 } 150 151 /* Compare a==b */ 152 mask_t gf_eq(const gf a, const gf b) 153 { 154 gf c; 155 mask_t ret = 0; 156 unsigned int i; 157 158 gf_sub(c, a, b); 159 gf_strong_reduce(c); 160 161 for (i = 0; i < NLIMBS; i++) 162 ret |= c->limb[LIMBPERM(i)]; 163 164 return word_is_zero(ret); 165 } 166 167 mask_t gf_isr(gf a, const gf x) 168 { 169 gf L0, L1, L2; 170 171 ossl_gf_sqr(L1, x); 172 ossl_gf_mul(L2, x, L1); 173 ossl_gf_sqr(L1, L2); 174 ossl_gf_mul(L2, x, L1); 175 gf_sqrn(L1, L2, 3); 176 ossl_gf_mul(L0, L2, L1); 177 gf_sqrn(L1, L0, 3); 178 ossl_gf_mul(L0, L2, L1); 179 gf_sqrn(L2, L0, 9); 180 ossl_gf_mul(L1, L0, L2); 181 ossl_gf_sqr(L0, L1); 182 ossl_gf_mul(L2, x, L0); 183 gf_sqrn(L0, L2, 18); 184 ossl_gf_mul(L2, L1, L0); 185 gf_sqrn(L0, L2, 37); 186 ossl_gf_mul(L1, L2, L0); 187 gf_sqrn(L0, L1, 37); 188 ossl_gf_mul(L1, L2, L0); 189 gf_sqrn(L0, L1, 111); 190 ossl_gf_mul(L2, L1, L0); 191 ossl_gf_sqr(L0, L2); 192 ossl_gf_mul(L1, x, L0); 193 gf_sqrn(L0, L1, 223); 194 ossl_gf_mul(L1, L2, L0); 195 ossl_gf_sqr(L2, L1); 196 ossl_gf_mul(L0, L2, x); 197 gf_copy(a, L1); 198 return gf_eq(L0, ONE); 199 } 200
Indexes created Sat Feb 28 05:31:39 UTC 2026