Line data Source code
1 : #include "./fd_bn254.h"
2 : #include "../fiat-crypto/bn254_64.c"
3 :
4 : /* Fp = base field */
5 :
6 305886 : #define FLAG_INF ((uchar)(1 << 6))
7 305751 : #define FLAG_NEG ((uchar)(1 << 7))
8 245685 : #define FLAG_MASK 0x3F
9 :
10 : /* const 0. */
11 : const fd_bn254_fp_t fd_bn254_const_zero[1] = {{{
12 : 0x0UL, 0x0UL, 0x0UL, 0x0UL,
13 : }}};
14 :
15 : /* const p, used to validate a field element. NOT Montgomery.
16 : 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47 */
17 : const fd_bn254_fp_t fd_bn254_const_p[1] = {{{
18 : 0x3c208c16d87cfd47, 0x97816a916871ca8d, 0xb85045b68181585d, 0x30644e72e131a029,
19 : }}};
20 :
21 : /* const 1/p for CIOS mul */
22 : static const ulong fd_bn254_const_p_inv = 0x87D20782E4866389UL;
23 :
24 : /* const 1. Montgomery.
25 : 0x0e0a77c19a07df2f666ea36f7879462c0a78eb28f5c70b3dd35d438dc58f0d9d */
26 : const fd_bn254_fp_t fd_bn254_const_one_mont[1] = {{{
27 : 0xd35d438dc58f0d9d, 0x0a78eb28f5c70b3d, 0x666ea36f7879462c, 0x0e0a77c19a07df2f
28 : }}};
29 :
30 : /* const x, used by fd_bn254_g2_frombytes_check(). scalar (NOT Montgomery)
31 : 0x44e992b44a6909f1 (64-bit) */
32 : const fd_bn254_scalar_t fd_bn254_const_x[1] = {{{
33 : 0x44e992b44a6909f1, 0x0, 0x0, 0x0,
34 : }}};
35 :
36 : /* const b=3, in curve equation y^2 = x^3 + b. Montgomery.
37 : 0x2a1f6744ce179d8e334bea4e696bd2841f6ac17ae15521b97a17caa950ad28d7 */
38 : const fd_bn254_fp_t fd_bn254_const_b_mont[1] = {{{
39 : 0x7a17caa950ad28d7, 0x1f6ac17ae15521b9, 0x334bea4e696bd284, 0x2a1f6744ce179d8e
40 : // 0x3UL, 0x0UL, 0x0UL, 0x0UL,
41 : }}};
42 :
43 : /* const p-1, to check if sqrt exists. Montgomery.
44 : 0x2259d6b14729c0fa51e1a247090812318d087f6872aabf4f68c3488912edefaa */
45 : const fd_bn254_fp_t fd_bn254_const_p_minus_one_mont[1] = {{{
46 : 0x68c3488912edefaa, 0x8d087f6872aabf4f, 0x51e1a24709081231, 0x2259d6b14729c0fa,
47 : }}};
48 :
49 : /* const (p-1)/2, used to check if an element is positive or negative,
50 : and to calculate sqrt() in Fp2. NOT Montgomery.
51 : 0x183227397098d014dc2822db40c0ac2ecbc0b548b438e5469e10460b6c3e7ea3 */
52 : const fd_bn254_fp_t fd_bn254_const_p_minus_one_half[1] = {{{
53 : 0x9e10460b6c3e7ea3, 0xcbc0b548b438e546, 0xdc2822db40c0ac2e, 0x183227397098d014,
54 : }}};
55 :
56 : /* const (p-3)/4, used to calculate sqrt() in Fp and Fp2. bigint (NOT Montgomery)
57 : 0x0c19139cb84c680a6e14116da060561765e05aa45a1c72a34f082305b61f3f51 */
58 : const fd_uint256_t fd_bn254_const_sqrt_exp[1] = {{{
59 : 0x4f082305b61f3f51, 0x65e05aa45a1c72a3, 0x6e14116da0605617, 0x0c19139cb84c680a,
60 : }}};
61 :
62 : static inline int
63 93372 : fd_bn254_fp_is_neg_nm( fd_bn254_fp_t * x ) {
64 93372 : return fd_uint256_cmp( x, fd_bn254_const_p_minus_one_half ) > 0;
65 93372 : }
66 :
67 : static inline fd_bn254_fp_t *
68 : fd_bn254_fp_frombytes_nm( fd_bn254_fp_t * r,
69 : uchar const buf[32],
70 : int big_endian,
71 : int * is_inf,
72 643935 : int * is_neg ) {
73 : /* Flags (optional) */
74 643935 : if( is_inf != NULL /* && is_neg != NULL */ ) {
75 245685 : *is_inf = !!(buf[ big_endian ? 0 : 31 ] & FLAG_INF);
76 245685 : *is_neg = !!(buf[ big_endian ? 0 : 31 ] & FLAG_NEG);
77 : /* If both flags are set (bit 6, 7), return error.
78 : https://github.com/arkworks-rs/algebra/blob/v0.4.2/ec/src/models/short_weierstrass/serialization_flags.rs#L75 */
79 245685 : if( FD_UNLIKELY( *is_inf && *is_neg ) ) {
80 0 : return NULL;
81 0 : }
82 245685 : }
83 :
84 643935 : fd_memcpy( r, buf, 32 );
85 643935 : if( FD_BIG_ENDIAN_LIKELY( big_endian ) ) {
86 1500 : fd_uint256_bswap( r, r );
87 1500 : }
88 643935 : if( is_inf != NULL ) {
89 245685 : r->buf[ 31 ] &= FLAG_MASK;
90 245685 : }
91 :
92 : /* Field element */
93 643935 : if( FD_UNLIKELY( fd_uint256_cmp( r, fd_bn254_const_p ) >= 0 ) ) {
94 0 : return NULL;
95 0 : }
96 643935 : return r;
97 643935 : }
98 :
99 : static inline uchar *
100 : fd_bn254_fp_tobytes_nm( uchar buf[32],
101 : fd_bn254_fp_t * a,
102 404511 : int big_endian ) {
103 404511 : if( FD_BIG_ENDIAN_LIKELY( big_endian ) ) {
104 612 : fd_uint256_bswap( a, a );
105 612 : }
106 404511 : fd_memcpy( buf, a, 32 );
107 404511 : return buf;
108 404511 : }
109 :
110 : static inline int
111 : fd_bn254_fp_eq( fd_bn254_fp_t const * r,
112 2777010 : fd_bn254_fp_t const * a ) {
113 2777010 : return fd_uint256_eq( r, a );
114 2777010 : }
115 :
116 : static inline fd_bn254_fp_t *
117 : fd_bn254_fp_from_mont( fd_bn254_fp_t * r,
118 277953 : fd_bn254_fp_t const * a ) {
119 277953 : fiat_bn254_from_montgomery( r->limbs, a->limbs );
120 277953 : return r;
121 277953 : }
122 :
123 : static inline fd_bn254_fp_t *
124 : fd_bn254_fp_to_mont( fd_bn254_fp_t * r,
125 463341 : fd_bn254_fp_t const * a ) {
126 463341 : fiat_bn254_to_montgomery( r->limbs, a->limbs );
127 463341 : return r;
128 463341 : }
129 :
130 : static inline fd_bn254_fp_t *
131 : fd_bn254_fp_neg_nm( fd_bn254_fp_t * r,
132 6129 : fd_bn254_fp_t const * a ) {
133 6129 : if( FD_UNLIKELY( fd_bn254_fp_is_zero( a ) ) ) {
134 0 : return fd_bn254_fp_set_zero( r );
135 0 : }
136 : /* compute p-a */
137 30645 : for( ulong i=0, cy=0; i<4; i++ ) {
138 24516 : ulong p = fd_bn254_const_p->limbs[i];
139 24516 : ulong b = a->limbs[i];
140 24516 : b += cy;
141 24516 : cy = (b < cy);
142 24516 : cy += (p < b);
143 24516 : r->limbs[i] = p - b;
144 24516 : }
145 6129 : return r;
146 6129 : }
147 :
148 : static inline fd_bn254_fp_t *
149 : fd_bn254_fp_set( fd_bn254_fp_t * r,
150 5140932 : fd_bn254_fp_t const * a ) {
151 5140932 : r->limbs[0] = a->limbs[0];
152 5140932 : r->limbs[1] = a->limbs[1];
153 5140932 : r->limbs[2] = a->limbs[2];
154 5140932 : r->limbs[3] = a->limbs[3];
155 5140932 : return r;
156 5140932 : }
157 :
158 : INLINE fd_bn254_fp_t *
159 : fd_bn254_fp_add( fd_bn254_fp_t * r,
160 : fd_bn254_fp_t const * a,
161 90012915 : fd_bn254_fp_t const * b ) {
162 90012915 : fiat_bn254_add( r->limbs, a->limbs, b->limbs );
163 90012915 : return r;
164 90012915 : }
165 :
166 : INLINE fd_bn254_fp_t *
167 : fd_bn254_fp_sub( fd_bn254_fp_t * r,
168 : fd_bn254_fp_t const * a,
169 61147986 : fd_bn254_fp_t const * b ) {
170 61147986 : fiat_bn254_sub( r->limbs, a->limbs, b->limbs );
171 61147986 : return r;
172 61147986 : }
173 :
174 : INLINE fd_bn254_fp_t *
175 : fd_bn254_fp_neg( fd_bn254_fp_t * r,
176 258054 : fd_bn254_fp_t const * a ) {
177 258054 : fiat_bn254_opp( r->limbs, a->limbs );
178 258054 : return r;
179 258054 : }
180 :
181 : static inline fd_bn254_fp_t *
182 : fd_bn254_fp_halve( fd_bn254_fp_t * r,
183 224256 : fd_bn254_fp_t const * a ) {
184 224256 : int is_odd = a->limbs[0] & 0x1;
185 224256 : fd_uint256_add( r, a, is_odd ? fd_bn254_const_p : fd_bn254_const_zero );
186 224256 : r->limbs[0] = (r->limbs[0] >> 1) | (r->limbs[1] << 63);
187 224256 : r->limbs[1] = (r->limbs[1] >> 1) | (r->limbs[2] << 63);
188 224256 : r->limbs[2] = (r->limbs[2] >> 1) | (r->limbs[3] << 63);
189 224256 : r->limbs[3] = (r->limbs[3] >> 1);
190 224256 : return r;
191 224256 : }
192 :
193 : FD_UINT256_FP_MUL_IMPL(fd_bn254_fp, fd_bn254_const_p, fd_bn254_const_p_inv)
194 :
195 : static inline fd_bn254_fp_t *
196 : fd_bn254_fp_sqr( fd_bn254_fp_t * r,
197 63834279 : fd_bn254_fp_t const * a ) {
198 63834279 : return fd_bn254_fp_mul( r, a, a );
199 63834279 : }
200 :
201 : fd_bn254_fp_t *
202 : fd_bn254_fp_pow( fd_bn254_fp_t * restrict r,
203 : fd_bn254_fp_t const * a,
204 152865 : fd_uint256_t const * b ) {
205 152865 : fd_bn254_fp_set_one( r );
206 152865 : if( fd_uint256_is_zero( b ) ) return r; /* x^0 = 1 */
207 :
208 : /* There must be a bit set, as b>0, so if we reach i==0, it must be set. */
209 152865 : int i = 255;
210 518781 : while( !fd_uint256_bit( b, i ) ) i--;
211 :
212 38920389 : for( ; i>=0; i--) {
213 38767524 : fd_bn254_fp_sqr( r, r );
214 38767524 : if( fd_uint256_bit( b, i ) ) {
215 16785057 : fd_bn254_fp_mul( r, r, a );
216 16785057 : }
217 38767524 : }
218 152865 : return r;
219 152865 : }
220 :
221 : /* fd_bn254_fp_inv computes r = 1 / a.
222 : a MUST not be 0.
223 : Computes via a^{-1} <=> a^{p-2}. */
224 : static inline fd_bn254_fp_t *
225 : fd_bn254_fp_inv( fd_bn254_fp_t * r,
226 122772 : fd_bn254_fp_t const * a ) {
227 122772 : fd_uint256_t p_minus_2[1];
228 122772 : fd_bn254_fp_set( p_minus_2, fd_bn254_const_p );
229 122772 : p_minus_2->limbs[0] -= 2UL;
230 122772 : return fd_bn254_fp_pow( r, a, p_minus_2 );
231 122772 : }
232 :
233 : static inline fd_bn254_fp_t *
234 : fd_bn254_fp_sqrt( fd_bn254_fp_t * r,
235 30093 : fd_bn254_fp_t const * a ) {
236 : /* Alg. 2, https://eprint.iacr.org/2012/685 */
237 :
238 30093 : fd_bn254_fp_t a0[1], a1[1];
239 :
240 30093 : fd_bn254_fp_pow( a1, a, fd_bn254_const_sqrt_exp );
241 :
242 30093 : fd_bn254_fp_sqr( a0, a1 );
243 30093 : fd_bn254_fp_mul( a0, a0, a );
244 30093 : if( FD_UNLIKELY( fd_bn254_fp_eq( a0, fd_bn254_const_p_minus_one_mont ) ) ) {
245 0 : return NULL;
246 0 : }
247 :
248 30093 : fd_bn254_fp_mul( r, a1, a );
249 30093 : return r;
250 30093 : }
|
