| /* |
| * Copyright 2017-2021 The OpenSSL Project Authors. All Rights Reserved. |
| * Copyright 2015-2016 Cryptography Research, Inc. |
| * |
| * Licensed under the Apache License 2.0 (the "License"). You may not use |
| * this file except in compliance with the License. You can obtain a copy |
| * in the file LICENSE in the source distribution or at |
| * https://www.openssl.org/source/license.html |
| * |
| * Originally written by Mike Hamburg |
| */ |
| #include "field.h" |
| |
| static const gf MODULUS = { |
| FIELD_LITERAL(0xffffffffffffffULL, 0xffffffffffffffULL, 0xffffffffffffffULL, |
| 0xffffffffffffffULL, 0xfffffffffffffeULL, 0xffffffffffffffULL, |
| 0xffffffffffffffULL, 0xffffffffffffffULL) |
| }; |
| |
| /* Serialize to wire format. */ |
| void gf_serialize(uint8_t serial[SER_BYTES], const gf x, int with_hibit) |
| { |
| unsigned int j = 0, fill = 0; |
| dword_t buffer = 0; |
| int i; |
| gf red; |
| |
| gf_copy(red, x); |
| gf_strong_reduce(red); |
| if (!with_hibit) |
| assert(gf_hibit(red) == 0); |
| |
| for (i = 0; i < (with_hibit ? X_SER_BYTES : SER_BYTES); i++) { |
| if (fill < 8 && j < NLIMBS) { |
| buffer |= ((dword_t) red->limb[LIMBPERM(j)]) << fill; |
| fill += LIMB_PLACE_VALUE(LIMBPERM(j)); |
| j++; |
| } |
| serial[i] = (uint8_t)buffer; |
| fill -= 8; |
| buffer >>= 8; |
| } |
| } |
| |
| /* Return high bit of x = low bit of 2x mod p */ |
| mask_t gf_hibit(const gf x) |
| { |
| gf y; |
| |
| gf_add(y, x, x); |
| gf_strong_reduce(y); |
| return 0 - (y->limb[0] & 1); |
| } |
| |
| /* Return high bit of x = low bit of 2x mod p */ |
| mask_t gf_lobit(const gf x) |
| { |
| gf y; |
| |
| gf_copy(y, x); |
| gf_strong_reduce(y); |
| return 0 - (y->limb[0] & 1); |
| } |
| |
| /* Deserialize from wire format; return -1 on success and 0 on failure. */ |
| mask_t gf_deserialize(gf x, const uint8_t serial[SER_BYTES], int with_hibit, |
| uint8_t hi_nmask) |
| { |
| unsigned int j = 0, fill = 0; |
| dword_t buffer = 0; |
| dsword_t scarry = 0; |
| const unsigned nbytes = with_hibit ? X_SER_BYTES : SER_BYTES; |
| unsigned int i; |
| mask_t succ; |
| |
| for (i = 0; i < NLIMBS; i++) { |
| while (fill < LIMB_PLACE_VALUE(LIMBPERM(i)) && j < nbytes) { |
| uint8_t sj; |
| |
| sj = serial[j]; |
| if (j == nbytes - 1) |
| sj &= ~hi_nmask; |
| buffer |= ((dword_t) sj) << fill; |
| fill += 8; |
| j++; |
| } |
| x->limb[LIMBPERM(i)] = (word_t) |
| ((i < NLIMBS - 1) ? buffer & LIMB_MASK(LIMBPERM(i)) : buffer); |
| fill -= LIMB_PLACE_VALUE(LIMBPERM(i)); |
| buffer >>= LIMB_PLACE_VALUE(LIMBPERM(i)); |
| scarry = |
| (scarry + x->limb[LIMBPERM(i)] - |
| MODULUS->limb[LIMBPERM(i)]) >> (8 * sizeof(word_t)); |
| } |
| succ = with_hibit ? 0 - (mask_t) 1 : ~gf_hibit(x); |
| return succ & word_is_zero((word_t)buffer) & ~word_is_zero((word_t)scarry); |
| } |
| |
| /* Reduce to canonical form. */ |
| void gf_strong_reduce(gf a) |
| { |
| dsword_t scarry; |
| word_t scarry_0; |
| dword_t carry = 0; |
| unsigned int i; |
| |
| /* first, clear high */ |
| gf_weak_reduce(a); /* Determined to have negligible perf impact. */ |
| |
| /* now the total is less than 2p */ |
| |
| /* compute total_value - p. No need to reduce mod p. */ |
| scarry = 0; |
| for (i = 0; i < NLIMBS; i++) { |
| scarry = scarry + a->limb[LIMBPERM(i)] - MODULUS->limb[LIMBPERM(i)]; |
| a->limb[LIMBPERM(i)] = scarry & LIMB_MASK(LIMBPERM(i)); |
| scarry >>= LIMB_PLACE_VALUE(LIMBPERM(i)); |
| } |
| |
| /* |
| * uncommon case: it was >= p, so now scarry = 0 and this = x common case: |
| * it was < p, so now scarry = -1 and this = x - p + 2^255 so let's add |
| * back in p. will carry back off the top for 2^255. |
| */ |
| assert(scarry == 0 || scarry == -1); |
| |
| scarry_0 = (word_t)scarry; |
| |
| /* add it back */ |
| for (i = 0; i < NLIMBS; i++) { |
| carry = |
| carry + a->limb[LIMBPERM(i)] + |
| (scarry_0 & MODULUS->limb[LIMBPERM(i)]); |
| a->limb[LIMBPERM(i)] = carry & LIMB_MASK(LIMBPERM(i)); |
| carry >>= LIMB_PLACE_VALUE(LIMBPERM(i)); |
| } |
| |
| assert(carry < 2 && ((word_t)carry + scarry_0) == 0); |
| } |
| |
| /* Subtract two gf elements d=a-b */ |
| void gf_sub(gf d, const gf a, const gf b) |
| { |
| gf_sub_RAW(d, a, b); |
| gf_bias(d, 2); |
| gf_weak_reduce(d); |
| } |
| |
| /* Add two field elements d = a+b */ |
| void gf_add(gf d, const gf a, const gf b) |
| { |
| gf_add_RAW(d, a, b); |
| gf_weak_reduce(d); |
| } |
| |
| /* Compare a==b */ |
| mask_t gf_eq(const gf a, const gf b) |
| { |
| gf c; |
| mask_t ret = 0; |
| unsigned int i; |
| |
| gf_sub(c, a, b); |
| gf_strong_reduce(c); |
| |
| for (i = 0; i < NLIMBS; i++) |
| ret |= c->limb[LIMBPERM(i)]; |
| |
| return word_is_zero(ret); |
| } |
| |
| mask_t gf_isr(gf a, const gf x) |
| { |
| gf L0, L1, L2; |
| |
| gf_sqr(L1, x); |
| gf_mul(L2, x, L1); |
| gf_sqr(L1, L2); |
| gf_mul(L2, x, L1); |
| gf_sqrn(L1, L2, 3); |
| gf_mul(L0, L2, L1); |
| gf_sqrn(L1, L0, 3); |
| gf_mul(L0, L2, L1); |
| gf_sqrn(L2, L0, 9); |
| gf_mul(L1, L0, L2); |
| gf_sqr(L0, L1); |
| gf_mul(L2, x, L0); |
| gf_sqrn(L0, L2, 18); |
| gf_mul(L2, L1, L0); |
| gf_sqrn(L0, L2, 37); |
| gf_mul(L1, L2, L0); |
| gf_sqrn(L0, L1, 37); |
| gf_mul(L1, L2, L0); |
| gf_sqrn(L0, L1, 111); |
| gf_mul(L2, L1, L0); |
| gf_sqr(L0, L2); |
| gf_mul(L1, x, L0); |
| gf_sqrn(L0, L1, 223); |
| gf_mul(L1, L2, L0); |
| gf_sqr(L2, L1); |
| gf_mul(L0, L2, x); |
| gf_copy(a, L1); |
| return gf_eq(L0, ONE); |
| } |