Line data Source code
1 : #ifndef HEADER_fd_src_ballet_ed25519_fd_curve25519_scalar_h
2 : #define HEADER_fd_src_ballet_ed25519_fd_curve25519_scalar_h
3 :
4 : /* fd_curve25519_scalar.h provides the public Curve25519 scalar API.
5 :
6 : All operations in this API should be assumed to take a variable
7 : amount of time depending on inputs. (And thus should not be exposed
8 : to secret data) */
9 :
10 : #include "../fd_ballet_base.h"
11 : #include "../bigint/fd_uint256.h"
12 :
13 : static const uchar fd_curve25519_scalar_zero[ 32 ] = {
14 : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
15 : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
16 : };
17 :
18 : static const uchar fd_curve25519_scalar_one[ 32 ] = {
19 : 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
20 : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
21 : };
22 :
23 : /* l = 2^252 + 27742317777372353535851937790883648493
24 : = 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed
25 : l-1 = 0x10...ec */
26 : static const uchar fd_curve25519_scalar_minus_one[ 32 ] = {
27 : 0xec, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58,
28 : 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
29 : 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
30 : 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10,
31 : };
32 :
33 : FD_PROTOTYPES_BEGIN
34 :
35 : /* fd_curve25519_scalar_reduce computes s mod l where s is a 512-bit value. s
36 : is stored in 64-byte little endian form and in points to the first
37 : byte of s. l is:
38 :
39 : 2^252 + 27742317777372353535851937790883648493.
40 :
41 : The result can be represented as a 256-bit value and stored in a
42 : 32-byte little endian form. out points to where to store the result.
43 :
44 : Does no input argument checking. The caller takes a write interest
45 : in out and a read interest in in for the duration of the call.
46 : Returns out and, on return, out will be populated with the 256-bit
47 : result. In-place operation fine. */
48 :
49 : uchar *
50 : fd_curve25519_scalar_reduce( uchar out[ 32 ],
51 : uchar const in [ 64 ] );
52 :
53 : /* fd_curve25519_scalar_validate checks whether the given Ed25519 scalar n
54 : matches the canonical byte representation.
55 : Not constant time and thus should not be exposed to secrets.
56 : Returns s if canonical, NULL otherwise. */
57 :
58 : static inline uchar const *
59 7122306 : fd_curve25519_scalar_validate( uchar const s[ 32 ] ) {
60 : /* If none of the top 4 bits are set, then the scalar fits into S \in [0, 2^252),
61 : which is a tighter range than [0, L), which is about [0, 2^252.2). In this case
62 : we can "succeed-fast" and skip the full canonical check. */
63 7122306 : if ( FD_UNLIKELY( s[31] & 0xF0 ) ) {
64 : /* Assuming canonical and IID scalars, the chance of the 252nd bit being
65 : set is roughly 1/2^128 or log2(1 - (2^252 - 1) / L). */
66 :
67 : /* If any of the top 3 bits are set, the scalar representation must be invalid. */
68 3217517 : if ( FD_LIKELY( s[31] & 0xE0 ) ) return NULL;
69 :
70 : /* Nothing left for us to do except determine if `s` is between [2^252, L) or not. */
71 3013626 : ulong s0 = fd_ulong_load_8_fast( s );
72 3013626 : ulong s1 = fd_ulong_load_8_fast( s + 8 );
73 3013626 : ulong s2 = fd_ulong_load_8_fast( s + 16 );
74 3013626 : ulong s3 = fd_ulong_load_8_fast( s + 24 );
75 3013626 : ulong l0 = *(ulong *)(&fd_curve25519_scalar_minus_one[ 0 ]);
76 3013626 : ulong l1 = *(ulong *)(&fd_curve25519_scalar_minus_one[ 8 ]);
77 3013626 : ulong l2 = *(ulong *)(&fd_curve25519_scalar_minus_one[ 16 ]);
78 3013626 : ulong l3 = *(ulong *)(&fd_curve25519_scalar_minus_one[ 24 ]);
79 3013626 : ulong r; int b;
80 3013626 : fd_ulong_sub_borrow( &r, &b, s0, l0, 1 );
81 3013626 : fd_ulong_sub_borrow( &r, &b, s1, l1, b );
82 3013626 : fd_ulong_sub_borrow( &r, &b, s2, l2, b );
83 3013626 : fd_ulong_sub_borrow( &r, &b, s3, l3, b );
84 3013626 : return b ? s : NULL;
85 3217517 : }
86 3904789 : return s;
87 7122306 : }
88 :
89 : /* fd_curve25519_scalar_muladd computes s = (a*b+c) mod l where a, b and c
90 : are 256-bit values. a is stored in 32-byte little endian form and a
91 : points to the first byte of a. Similarly for b and c. l is:
92 :
93 : 2^252 + 27742317777372353535851937790883648493.
94 :
95 : The result can be represented as a 256-bit value and stored in a
96 : 32-byte little endian form. s points to where to store the result.
97 :
98 : Does no input argument checking. The caller takes a write interest
99 : in s and a read interest in a, b and c for the duration of the call.
100 : Returns s and, on return, s will be populated with the 256-bit
101 : result. In-place operation fine. */
102 :
103 : uchar *
104 : fd_curve25519_scalar_muladd( uchar s[ 32 ],
105 : uchar const * a,
106 : uchar const b[ 32 ],
107 : uchar const c[ 32 ] );
108 :
109 : static inline uchar *
110 : fd_curve25519_scalar_mul ( uchar * s,
111 : uchar const * a,
112 45 : uchar const * b ) {
113 45 : return fd_curve25519_scalar_muladd( s, a, b, fd_curve25519_scalar_zero );
114 45 : }
115 :
116 : static inline uchar *
117 : fd_curve25519_scalar_add ( uchar * s,
118 : uchar const * a,
119 9 : uchar const * b ) {
120 9 : return fd_curve25519_scalar_muladd( s, a, fd_curve25519_scalar_one, b );
121 9 : }
122 :
123 : static inline uchar *
124 : fd_curve25519_scalar_sub ( uchar * s,
125 : uchar const * a,
126 0 : uchar const * b ) {
127 : //TODO implement dedicated neg/sub
128 0 : return fd_curve25519_scalar_muladd( s, fd_curve25519_scalar_minus_one, b, a );
129 0 : }
130 :
131 : static inline uchar *
132 : fd_curve25519_scalar_neg ( uchar * s,
133 24 : uchar const * a ) {
134 : //TODO implement dedicated neg/sub
135 24 : return fd_curve25519_scalar_muladd( s, fd_curve25519_scalar_minus_one, a, fd_curve25519_scalar_zero );
136 24 : }
137 :
138 : static inline uchar *
139 : fd_curve25519_scalar_set ( uchar * s,
140 33 : uchar const * a ) {
141 33 : return fd_memcpy( s, a, 32 );
142 33 : }
143 :
144 : static inline uchar *
145 : fd_curve25519_scalar_from_u64( uchar * s,
146 0 : ulong const x ) {
147 0 : fd_memset( s, 0, 32 );
148 0 : *((ulong *)s) = x;
149 0 : return s;
150 0 : }
151 :
152 : static inline uchar *
153 : fd_curve25519_scalar_inv( uchar * s,
154 0 : uchar const * a ) {
155 0 : uchar t[ 32 ];
156 : // TODO: use mul chain to save ~12% https://briansmith.org/ecc-inversion-addition-chains-01#curve25519_scalar_inversion
157 : /* the bits of -2 are the same as -1, except the first few (that we skip):
158 : -1 = 0xEC ... = b 1110 1100 ...
159 : -2 = 0xEB ... = b 1110 1011 ...
160 : ^ bit 7 ^ bit 0
161 : */
162 : /* bit 0 == 1 */
163 0 : fd_memcpy( t, a, 32 );
164 0 : fd_memcpy( s, a, 32 );
165 : /* bit 1 == 1 */
166 0 : fd_curve25519_scalar_mul( t, t, t );
167 0 : fd_curve25519_scalar_mul( s, s, t );
168 : /* bit 2 == 0 */
169 0 : fd_curve25519_scalar_mul( t, t, t );
170 : /* from bit 3 on, use -1 bits */
171 0 : for( ulong i=3; i<=252; i++ ) {
172 0 : fd_curve25519_scalar_mul( t, t, t );
173 0 : if( (fd_curve25519_scalar_minus_one[ i/8 ] & (1 << (i % 8))) ) {
174 0 : fd_curve25519_scalar_mul( s, s, t );
175 0 : }
176 0 : }
177 0 : return s;
178 0 : }
179 :
180 : /* fd_curve25519_scalar_batch_inv computes the modular inverse of each
181 : scalar in a[] using Montgomery's batch inversion trick (one inversion
182 : + 3(sz-1) multiplications). s[] receives the individual inverses;
183 : allinv receives the inverse of the product of all nonzero inputs.
184 : Zero inputs are skipped and their corresponding output set to zero.
185 : https://github.com/dalek-cryptography/curve25519-dalek/blob/curve25519-4.1.3/curve25519-dalek/src/scalar.rs#L788-L837 */
186 : static inline void
187 : fd_curve25519_scalar_batch_inv( uchar s [ 32 ], /* sz scalars */
188 : uchar allinv[ 32 ], /* 1 scalar */
189 : uchar const a [ 32 ], /* sz scalars */
190 0 : ulong sz ) {
191 0 : uchar acc[ 32 ];
192 0 : fd_memcpy( acc, fd_curve25519_scalar_one, 32 );
193 0 : for( ulong i=0; i<sz; i++ ) {
194 0 : if( FD_UNLIKELY( fd_memeq( &a[ i*32 ], fd_curve25519_scalar_zero, 32 ) ) ) {
195 0 : fd_memcpy( &s[ i*32 ], fd_curve25519_scalar_zero, 32 );
196 0 : } else {
197 0 : fd_memcpy( &s[ i*32 ], acc, 32 );
198 0 : fd_curve25519_scalar_mul( acc, acc, &a[ i*32 ] );
199 0 : }
200 0 : }
201 :
202 0 : fd_curve25519_scalar_inv( acc, acc );
203 0 : fd_memcpy( allinv, acc, 32 );
204 :
205 0 : for( int i=(int)sz-1; i>=0; i-- ) {
206 0 : if( FD_UNLIKELY( fd_memeq( &a[ i*32 ], fd_curve25519_scalar_zero, 32 ) ) ) continue;
207 0 : fd_curve25519_scalar_mul( &s[ i*32 ], &s[ i*32 ], acc );
208 0 : fd_curve25519_scalar_mul( acc, acc, &a[ i*32 ] );
209 0 : }
210 0 : }
211 :
212 : void
213 : fd_curve25519_scalar_wnaf( short slides[ 256 ], /* 256-entry */
214 : uchar const n[ 32 ], /* 32-byte, assumes valid scalar */
215 : int bits ); /* range: [1:12], 1 = NAF */
216 :
217 : FD_PROTOTYPES_END
218 :
219 : #endif /* HEADER_fd_src_ballet_ed25519_fd_curve25519_scalar_h */
|
