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 7128741 : fd_curve25519_scalar_validate( uchar const s[ 32 ] ) {
59 7128741 : ulong s0 = fd_ulong_load_8_fast( s );
60 7128741 : ulong s1 = fd_ulong_load_8_fast( s + 8 );
61 7128741 : ulong s2 = fd_ulong_load_8_fast( s + 16 );
62 7128741 : ulong s3 = fd_ulong_load_8_fast( s + 24 );
63 7128741 : ulong l0 = *(ulong *)(&fd_curve25519_scalar_minus_one[ 0 ]);
64 7128741 : ulong l1 = *(ulong *)(&fd_curve25519_scalar_minus_one[ 8 ]);
65 7128741 : ulong l2 = *(ulong *)(&fd_curve25519_scalar_minus_one[ 16 ]);
66 7128741 : ulong l3 = *(ulong *)(&fd_curve25519_scalar_minus_one[ 24 ]);
67 7128741 : return (
68 7128741 : (s3 < l3)
69 7128741 : || ((s3 == l3) && (s2 < l2))
70 7128741 : || ((s3 == l3) && (s2 == l2) && (s1 < l1))
71 7128741 : || ((s3 == l3) && (s2 == l2) && (s1 == l1) && (s0 <= l0))
72 7128741 : ) ? s : NULL;
73 7128741 : }
74 :
75 : /* fd_curve25519_scalar_muladd computes s = (a*b+c) mod l where a, b and c
76 : are 256-bit values. a is stored in 32-byte little endian form and a
77 : points to the first byte of a. Similarly for b and c. l is:
78 :
79 : 2^252 + 27742317777372353535851937790883648493.
80 :
81 : The result can be represented as a 256-bit value and stored in a
82 : 32-byte little endian form. s points to where to store the result.
83 :
84 : Does no input argument checking. The caller takes a write interest
85 : in s and a read interest in a, b and c for the duration of the call.
86 : Returns s and, on return, s will be populated with the 256-bit
87 : result. In-place operation fine. */
88 :
89 : uchar *
90 : fd_curve25519_scalar_muladd( uchar s[ 32 ],
91 : uchar const * a,
92 : uchar const b[ 32 ],
93 : uchar const c[ 32 ] );
94 :
95 : static inline uchar *
96 : fd_curve25519_scalar_mul ( uchar * s,
97 : uchar const * a,
98 86040 : uchar const * b ) {
99 86040 : return fd_curve25519_scalar_muladd( s, a, b, fd_curve25519_scalar_zero );
100 86040 : }
101 :
102 : static inline uchar *
103 : fd_curve25519_scalar_add ( uchar * s,
104 : uchar const * a,
105 16896 : uchar const * b ) {
106 16896 : return fd_curve25519_scalar_muladd( s, a, fd_curve25519_scalar_one, b );
107 16896 : }
108 :
109 : static inline uchar *
110 : fd_curve25519_scalar_sub ( uchar * s,
111 : uchar const * a,
112 417 : uchar const * b ) {
113 : //TODO implement dedicated neg/sub
114 417 : return fd_curve25519_scalar_muladd( s, fd_curve25519_scalar_minus_one, b, a );
115 417 : }
116 :
117 : static inline uchar *
118 : fd_curve25519_scalar_neg ( uchar * s,
119 1356 : uchar const * a ) {
120 : //TODO implement dedicated neg/sub
121 1356 : return fd_curve25519_scalar_muladd( s, fd_curve25519_scalar_minus_one, a, fd_curve25519_scalar_zero );
122 1356 : }
123 :
124 : static inline uchar *
125 : fd_curve25519_scalar_set ( uchar * s,
126 624 : uchar const * a ) {
127 624 : return fd_memcpy( s, a, 32 );
128 624 : }
129 :
130 : static inline uchar *
131 : fd_curve25519_scalar_from_u64( uchar * s,
132 39 : ulong const x ) {
133 39 : fd_memset( s, 0, 32 );
134 39 : *((ulong *)s) = x;
135 39 : return s;
136 39 : }
137 :
138 : static inline uchar *
139 : fd_curve25519_scalar_inv( uchar * s,
140 123 : uchar const * a ) {
141 123 : uchar t[ 32 ];
142 : // TODO: use mul chain to save ~12% https://briansmith.org/ecc-inversion-addition-chains-01#curve25519_scalar_inversion
143 : /* the bits of -2 are the same as -1, except the first few (that we skip):
144 : -1 = 0xEC ... = b 1110 1100 ...
145 : -2 = 0xEB ... = b 1110 1011 ...
146 : ^ bit 7 ^ bit 0
147 : */
148 : /* bit 0 == 1 */
149 123 : fd_memcpy( t, a, 32 );
150 123 : fd_memcpy( s, a, 32 );
151 : /* bit 1 == 1 */
152 123 : fd_curve25519_scalar_mul( t, t, t );
153 123 : fd_curve25519_scalar_mul( s, s, t );
154 : /* bit 2 == 0 */
155 123 : fd_curve25519_scalar_mul( t, t, t );
156 : /* from bit 3 on, use -1 bits */
157 30873 : for( ulong i=3; i<=252; i++ ) {
158 30750 : fd_curve25519_scalar_mul( t, t, t );
159 30750 : if( (fd_curve25519_scalar_minus_one[ i/8 ] & (1 << (i % 8))) ) {
160 8733 : fd_curve25519_scalar_mul( s, s, t );
161 8733 : }
162 30750 : }
163 123 : return s;
164 123 : }
165 :
166 : static inline void
167 : fd_curve25519_scalar_batch_inv( uchar s [ 32 ], /* sz scalars */
168 : uchar allinv[ 32 ], /* 1 scalar */
169 : uchar const a [ 32 ], /* sz scalars */
170 123 : ulong sz ) {
171 123 : uchar acc[ 32 ];
172 123 : fd_memcpy( acc, fd_curve25519_scalar_one, 32 );
173 1101 : for( ulong i=0; i<sz; i++ ) {
174 978 : fd_memcpy( &s[ i*32 ], acc, 32 );
175 978 : fd_curve25519_scalar_mul( acc, acc, &a[ i*32 ] );
176 978 : }
177 :
178 123 : fd_curve25519_scalar_inv( acc, acc );
179 123 : fd_memcpy( allinv, acc, 32 );
180 :
181 1101 : for( int i=(int)sz-1; i>=0; i-- ) {
182 978 : fd_curve25519_scalar_mul( &s[ i*32 ], &s[ i*32 ], acc );
183 978 : fd_curve25519_scalar_mul( acc, acc, &a[ i*32 ] );
184 978 : }
185 123 : }
186 :
187 : void
188 : fd_curve25519_scalar_wnaf( short slides[ 256 ], /* 256-entry */
189 : uchar const n[ 32 ], /* 32-byte, assumes valid scalar */
190 : int bits ); /* range: [1:12], 1 = NAF */
191 :
192 : FD_PROTOTYPES_END
193 :
194 : #endif /* HEADER_fd_src_ballet_ed25519_fd_curve25519_scalar_h */
|
