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