1 /**
2 * @file p25519/f_generic.c
3 * @author Mike Hamburg
4 *
5 * @copyright
6 * Copyright (c) 2015-2016 Cryptography Research, Inc. \n
7 * Released under the MIT License. See LICENSE.txt for license information.
8 *
9 * @brief Generic arithmetic which has to be compiled per field.
10 *
11 * @warning This file was automatically generated in Python.
12 * Please do not edit it.
13 */
14 #include "field.h"
15
16 static const gf MODULUS = {FIELD_LITERAL(
17 0x7ffffffffffed, 0x7ffffffffffff, 0x7ffffffffffff, 0x7ffffffffffff, 0x7ffffffffffff
18 )};
19
20 #if P_MOD_8 == 5
21 const gf SQRT_MINUS_ONE = {FIELD_LITERAL(
22 0x61b274a0ea0b0, 0x0d5a5fc8f189d, 0x7ef5e9cbd0c60, 0x78595a6804c9e, 0x2b8324804fc1d
23 )};
24 #endif
25
26 /** Serialize to wire format. */
gf_serialize(uint8_t serial[SER_BYTES],const gf x,int with_hibit)27 void gf_serialize (uint8_t serial[SER_BYTES], const gf x, int with_hibit) {
28 gf red;
29 gf_copy(red, x);
30 gf_strong_reduce(red);
31 if (!with_hibit) { assert(gf_hibit(red) == 0); }
32
33 unsigned int j=0, fill=0;
34 dword_t buffer = 0;
35 UNROLL for (unsigned int i=0; i<(with_hibit ? X_SER_BYTES : SER_BYTES); i++) {
36 if (fill < 8 && j < NLIMBS) {
37 buffer |= ((dword_t)red->limb[LIMBPERM(j)]) << fill;
38 fill += LIMB_PLACE_VALUE(LIMBPERM(j));
39 j++;
40 }
41 serial[i] = buffer;
42 fill -= 8;
43 buffer >>= 8;
44 }
45 }
46
47 /** Return high bit of x = low bit of 2x mod p */
gf_hibit(const gf x)48 mask_t gf_hibit(const gf x) {
49 gf y;
50 gf_add(y,x,x);
51 gf_strong_reduce(y);
52 return -(y->limb[0]&1);
53 }
54
55 /** Return high bit of x = low bit of 2x mod p */
gf_lobit(const gf x)56 mask_t gf_lobit(const gf x) {
57 gf y;
58 gf_copy(y,x);
59 gf_strong_reduce(y);
60 return -(y->limb[0]&1);
61 }
62
63 /** Deserialize from wire format; return -1 on success and 0 on failure. */
gf_deserialize(gf x,const uint8_t serial[SER_BYTES],int with_hibit,uint8_t hi_nmask)64 mask_t gf_deserialize (gf x, const uint8_t serial[SER_BYTES], int with_hibit, uint8_t hi_nmask) {
65 unsigned int j=0, fill=0;
66 dword_t buffer = 0;
67 dsword_t scarry = 0;
68 const unsigned nbytes = with_hibit ? X_SER_BYTES : SER_BYTES;
69 UNROLL for (unsigned int i=0; i<NLIMBS; i++) {
70 UNROLL while (fill < LIMB_PLACE_VALUE(LIMBPERM(i)) && j < nbytes) {
71 uint8_t sj = serial[j];
72 if (j==nbytes-1) sj &= ~hi_nmask;
73 buffer |= ((dword_t)sj) << fill;
74 fill += 8;
75 j++;
76 }
77 x->limb[LIMBPERM(i)] = (i<NLIMBS-1) ? buffer & LIMB_MASK(LIMBPERM(i)) : buffer;
78 fill -= LIMB_PLACE_VALUE(LIMBPERM(i));
79 buffer >>= LIMB_PLACE_VALUE(LIMBPERM(i));
80 scarry = (scarry + x->limb[LIMBPERM(i)] - MODULUS->limb[LIMBPERM(i)]) >> (8*sizeof(word_t));
81 }
82 mask_t succ = with_hibit ? -(mask_t)1 : ~gf_hibit(x);
83 return succ & word_is_zero(buffer) & ~word_is_zero(scarry);
84 }
85
86 /** Reduce to canonical form. */
gf_strong_reduce(gf a)87 void gf_strong_reduce (gf a) {
88 /* first, clear high */
89 gf_weak_reduce(a); /* Determined to have negligible perf impact. */
90
91 /* now the total is less than 2p */
92
93 /* compute total_value - p. No need to reduce mod p. */
94 dsword_t scarry = 0;
95 for (unsigned int i=0; i<NLIMBS; i++) {
96 scarry = scarry + a->limb[LIMBPERM(i)] - MODULUS->limb[LIMBPERM(i)];
97 a->limb[LIMBPERM(i)] = scarry & LIMB_MASK(LIMBPERM(i));
98 scarry >>= LIMB_PLACE_VALUE(LIMBPERM(i));
99 }
100
101 /* uncommon case: it was >= p, so now scarry = 0 and this = x
102 * common case: it was < p, so now scarry = -1 and this = x - p + 2^255
103 * so let's add back in p. will carry back off the top for 2^255.
104 */
105 assert(word_is_zero(scarry) | word_is_zero(scarry+1));
106
107 word_t scarry_0 = scarry;
108 dword_t carry = 0;
109
110 /* add it back */
111 for (unsigned int i=0; i<NLIMBS; i++) {
112 carry = carry + a->limb[LIMBPERM(i)] + (scarry_0 & MODULUS->limb[LIMBPERM(i)]);
113 a->limb[LIMBPERM(i)] = carry & LIMB_MASK(LIMBPERM(i));
114 carry >>= LIMB_PLACE_VALUE(LIMBPERM(i));
115 }
116
117 assert(word_is_zero(carry + scarry_0));
118 }
119
120 /** Subtract two gf elements d=a-b */
gf_sub(gf d,const gf a,const gf b)121 void gf_sub (gf d, const gf a, const gf b) {
122 gf_sub_RAW ( d, a, b );
123 gf_bias( d, 2 );
124 gf_weak_reduce ( d );
125 }
126
127 /** Add two field elements d = a+b */
gf_add(gf d,const gf a,const gf b)128 void gf_add (gf d, const gf a, const gf b) {
129 gf_add_RAW ( d, a, b );
130 gf_weak_reduce ( d );
131 }
132
133 /** Compare a==b */
gf_eq(const gf a,const gf b)134 mask_t gf_eq(const gf a, const gf b) {
135 gf c;
136 gf_sub(c,a,b);
137 gf_strong_reduce(c);
138 mask_t ret=0;
139 for (unsigned int i=0; i<NLIMBS; i++) {
140 ret |= c->limb[LIMBPERM(i)];
141 }
142
143 return word_is_zero(ret);
144 }
145