Line data Source code
1 : #include "./fd_bn254.h"
2 : #include "../fiat-crypto/bn254_64.c"
3 :
4 : /* Fp = base field */
5 :
6 0 : #define FLAG_INF ((uchar)(1 << 6))
7 0 : #define FLAG_NEG ((uchar)(1 << 7))
8 0 : #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 0 : fd_bn254_fp_is_neg_nm( fd_bn254_fp_t * x ) {
64 0 : return fd_uint256_cmp( x, fd_bn254_const_p_minus_one_half ) > 0;
65 0 : }
66 :
67 : static inline fd_bn254_fp_t *
68 : fd_bn254_fp_frombytes_be_nm( fd_bn254_fp_t * r,
69 : uchar const buf[32],
70 : int * is_inf,
71 0 : int * is_neg ) {
72 : /* Flags (optional) */
73 0 : if( is_inf != NULL /* && is_neg != NULL */ ) {
74 0 : *is_inf = !!(buf[0] & FLAG_INF);
75 0 : *is_neg = !!(buf[0] & FLAG_NEG);
76 : /* If both flags are set (bit 6, 7), return error.
77 : https://github.com/arkworks-rs/algebra/blob/v0.4.2/ec/src/models/short_weierstrass/serialization_flags.rs#L75 */
78 0 : if( FD_UNLIKELY( *is_inf && *is_neg ) ) {
79 0 : return NULL;
80 0 : }
81 0 : }
82 :
83 0 : fd_memcpy( r, buf, 32 );
84 0 : fd_uint256_bswap( r, r );
85 0 : if( is_inf != NULL ) {
86 0 : r->buf[31] &= FLAG_MASK;
87 0 : }
88 :
89 : /* Field element */
90 0 : if( FD_UNLIKELY( fd_uint256_cmp( r, fd_bn254_const_p ) >= 0 ) ) {
91 0 : return NULL;
92 0 : }
93 0 : return r;
94 0 : }
95 :
96 : static inline uchar *
97 : fd_bn254_fp_tobytes_be_nm( uchar buf[32],
98 0 : fd_bn254_fp_t * a ) {
99 0 : fd_uint256_bswap( a, a );
100 0 : fd_memcpy( buf, a, 32 );
101 0 : return buf;
102 0 : }
103 :
104 : static inline int
105 : fd_bn254_fp_eq( fd_bn254_fp_t const * r,
106 0 : fd_bn254_fp_t const * a ) {
107 0 : return fd_uint256_eq( r, a );
108 0 : }
109 :
110 : static inline fd_bn254_fp_t *
111 : fd_bn254_fp_from_mont( fd_bn254_fp_t * r,
112 0 : fd_bn254_fp_t const * a ) {
113 0 : fiat_bn254_from_montgomery( r->limbs, a->limbs );
114 0 : return r;
115 0 : }
116 :
117 : static inline fd_bn254_fp_t *
118 : fd_bn254_fp_to_mont( fd_bn254_fp_t * r,
119 0 : fd_bn254_fp_t const * a ) {
120 0 : fiat_bn254_to_montgomery( r->limbs, a->limbs );
121 0 : return r;
122 0 : }
123 :
124 : static inline fd_bn254_fp_t *
125 : fd_bn254_fp_neg_nm( fd_bn254_fp_t * r,
126 0 : fd_bn254_fp_t const * a ) {
127 0 : if( FD_UNLIKELY( fd_bn254_fp_is_zero( a ) ) ) {
128 0 : return fd_bn254_fp_set_zero( r );
129 0 : }
130 : /* compute p-a */
131 0 : for( ulong i=0, cy=0; i<4; i++ ) {
132 0 : ulong p = fd_bn254_const_p->limbs[i];
133 0 : ulong b = a->limbs[i];
134 0 : b += cy;
135 0 : cy = (b < cy);
136 0 : cy += (p < b);
137 0 : r->limbs[i] = p - b;
138 0 : }
139 0 : return r;
140 0 : }
141 :
142 : static inline fd_bn254_fp_t *
143 : fd_bn254_fp_set( fd_bn254_fp_t * r,
144 0 : fd_bn254_fp_t const * a ) {
145 0 : r->limbs[0] = a->limbs[0];
146 0 : r->limbs[1] = a->limbs[1];
147 0 : r->limbs[2] = a->limbs[2];
148 0 : r->limbs[3] = a->limbs[3];
149 0 : return r;
150 0 : }
151 :
152 : static inline fd_bn254_fp_t *
153 : fd_bn254_fp_add( fd_bn254_fp_t * r,
154 : fd_bn254_fp_t const * a,
155 0 : fd_bn254_fp_t const * b ) {
156 0 : fiat_bn254_add( r->limbs, a->limbs, b->limbs );
157 0 : return r;
158 0 : }
159 :
160 : static inline fd_bn254_fp_t *
161 : fd_bn254_fp_sub( fd_bn254_fp_t * r,
162 : fd_bn254_fp_t const * a,
163 0 : fd_bn254_fp_t const * b ) {
164 0 : fiat_bn254_sub( r->limbs, a->limbs, b->limbs );
165 0 : return r;
166 0 : }
167 :
168 : static inline fd_bn254_fp_t *
169 : fd_bn254_fp_neg( fd_bn254_fp_t * r,
170 0 : fd_bn254_fp_t const * a ) {
171 0 : fiat_bn254_opp( r->limbs, a->limbs );
172 0 : return r;
173 0 : }
174 :
175 : static inline fd_bn254_fp_t *
176 : fd_bn254_fp_halve( fd_bn254_fp_t * r,
177 0 : fd_bn254_fp_t const * a ) {
178 0 : int is_odd = r->limbs[0] & 0x1;
179 0 : fd_uint256_add( r, a, is_odd ? fd_bn254_const_p : fd_bn254_const_zero );
180 0 : r->limbs[0] = (r->limbs[0] >> 1) | (r->limbs[1] << 63);
181 0 : r->limbs[1] = (r->limbs[1] >> 1) | (r->limbs[2] << 63);
182 0 : r->limbs[2] = (r->limbs[2] >> 1) | (r->limbs[3] << 63);
183 0 : r->limbs[3] = (r->limbs[3] >> 1);
184 0 : return r;
185 0 : }
186 :
187 : FD_UINT256_FP_MUL_IMPL(fd_bn254_fp, fd_bn254_const_p, fd_bn254_const_p_inv)
188 :
189 : static inline fd_bn254_fp_t *
190 : fd_bn254_fp_sqr( fd_bn254_fp_t * r,
191 0 : fd_bn254_fp_t const * a ) {
192 0 : return fd_bn254_fp_mul( r, a, a );
193 0 : }
194 :
195 : fd_bn254_fp_t *
196 : fd_bn254_fp_pow( fd_bn254_fp_t * restrict r,
197 : fd_bn254_fp_t const * a,
198 0 : fd_uint256_t const * b ) {
199 0 : fd_bn254_fp_set_one( r );
200 :
201 0 : int i = 255;
202 0 : while( !fd_uint256_bit( b, i) ) i--;
203 0 : for( ; i>=0; i--) {
204 0 : fd_bn254_fp_sqr( r, r );
205 0 : if( fd_uint256_bit( b, i ) ) {
206 0 : fd_bn254_fp_mul( r, r, a );
207 0 : }
208 0 : }
209 0 : return r;
210 0 : }
211 :
212 : static inline fd_bn254_fp_t *
213 : fd_bn254_fp_inv( fd_bn254_fp_t * r,
214 0 : fd_bn254_fp_t const * a ) {
215 0 : fd_uint256_t p_minus_2[1];
216 0 : fd_bn254_fp_set( p_minus_2, fd_bn254_const_p );
217 0 : p_minus_2->limbs[0] = p_minus_2->limbs[0] - 2UL;
218 0 : return fd_bn254_fp_pow( r, a, p_minus_2 );
219 0 : }
220 :
221 : static inline fd_bn254_fp_t *
222 : fd_bn254_fp_sqrt( fd_bn254_fp_t * r,
223 0 : fd_bn254_fp_t const * a ) {
224 : /* Alg. 2, https://eprint.iacr.org/2012/685 */
225 :
226 0 : fd_bn254_fp_t a0[1], a1[1];
227 :
228 0 : fd_bn254_fp_pow( a1, a, fd_bn254_const_sqrt_exp );
229 :
230 0 : fd_bn254_fp_sqr( a0, a1 );
231 0 : fd_bn254_fp_mul( a0, a0, a );
232 0 : if( FD_UNLIKELY( fd_bn254_fp_eq( a0, fd_bn254_const_p_minus_one_mont ) ) ) {
233 0 : return NULL;
234 0 : }
235 :
236 0 : fd_bn254_fp_mul( r, a1, a );
237 0 : return r;
238 0 : }
|
