Line data Source code
1 : #ifndef HEADER_fd_src_ballet_ed25519_fd_curve25519_h
2 : #error "Do not include this directly; use fd_curve25519.h"
3 : #endif
4 :
5 : /* fd_curve25519.h provides the public Curve25519 API.
6 :
7 : Most operations in this API should be assumed to take a variable
8 : amount of time depending on inputs. (And thus should not be exposed
9 : to secret data).
10 :
11 : Const time operations are made explicit, see fd_curve25519_secure.c */
12 :
13 : #include "../../fd_ballet_base.h"
14 : #include "../fd_f25519.h"
15 : #include "../fd_curve25519_scalar.h"
16 :
17 : /* CURVE25519_PRECOMP_XY turns on/off the precomputation of (Y-X), (Y+X)
18 : in precomputation tables. */
19 : #define CURVE25519_PRECOMP_XY 1
20 :
21 : /* struct fd_curve25519_edwards (aka fd_curve25519_edwards_t) represents
22 : a point in Extended Twisted Edwards Coordinates.
23 : https://eprint.iacr.org/2008/522 */
24 : struct fd_curve25519_edwards {
25 : fd_f25519_t X[1];
26 : fd_f25519_t Y[1];
27 : fd_f25519_t T[1];
28 : fd_f25519_t Z[1];
29 : };
30 : typedef struct fd_curve25519_edwards fd_curve25519_edwards_t;
31 :
32 : typedef fd_curve25519_edwards_t fd_ed25519_point_t;
33 : typedef fd_curve25519_edwards_t fd_ristretto255_point_t;
34 :
35 : #include "../table/fd_curve25519_table_ref.c"
36 :
37 : FD_PROTOTYPES_BEGIN
38 :
39 : /* fd_ed25519_point_set sets r = 0 (point at infinity). */
40 : FD_25519_INLINE fd_ed25519_point_t *
41 1714750 : fd_ed25519_point_set_zero( fd_ed25519_point_t * r ) {
42 1714750 : fd_f25519_set( r->X, fd_f25519_zero );
43 1714750 : fd_f25519_set( r->Y, fd_f25519_one );
44 1714750 : fd_f25519_set( r->Z, fd_f25519_one );
45 1714750 : fd_f25519_set( r->T, fd_f25519_zero );
46 1714750 : return r;
47 1714750 : }
48 :
49 : /* fd_ed25519_point_set_zero_precomputed sets r = 0 (point at infinity). */
50 : FD_25519_INLINE fd_ed25519_point_t *
51 75091072 : fd_ed25519_point_set_zero_precomputed( fd_ed25519_point_t * r ) {
52 75091072 : #if CURVE25519_PRECOMP_XY
53 75091072 : fd_f25519_set( r->X, fd_f25519_one ); /* Y-X = 1-0 = 1 */
54 75091072 : fd_f25519_set( r->Y, fd_f25519_one ); /* Y+X = 1+0 = 1 */
55 75091072 : fd_f25519_set( r->Z, fd_f25519_one ); /* Z = 1 */
56 75091072 : fd_f25519_set( r->T, fd_f25519_zero ); /* kT = 0 */
57 75091072 : return r;
58 : #else
59 : return fd_ed25519_point_set_zero( r );
60 : #endif
61 75091072 : }
62 :
63 : /* fd_ed25519_point_set sets r = a. */
64 : FD_25519_INLINE fd_ed25519_point_t * FD_FN_NO_ASAN
65 : fd_ed25519_point_set( fd_ed25519_point_t * r,
66 681652 : fd_ed25519_point_t const * a ) {
67 681652 : fd_f25519_set( r->X, a->X );
68 681652 : fd_f25519_set( r->Y, a->Y );
69 681652 : fd_f25519_set( r->Z, a->Z );
70 681652 : fd_f25519_set( r->T, a->T );
71 681652 : return r;
72 681652 : }
73 :
74 : /* fd_ed25519_point_from sets r = (x : y : z : t). */
75 : FD_25519_INLINE fd_ed25519_point_t *
76 : fd_ed25519_point_from( fd_ed25519_point_t * r,
77 : fd_f25519_t const * x,
78 : fd_f25519_t const * y,
79 : fd_f25519_t const * z,
80 1313394 : fd_f25519_t const * t ) {
81 1313394 : fd_f25519_set( r->X, x );
82 1313394 : fd_f25519_set( r->Y, y );
83 1313394 : fd_f25519_set( r->Z, z );
84 1313394 : fd_f25519_set( r->T, t );
85 1313394 : return r;
86 1313394 : }
87 :
88 : /* fd_ed25519_point_from sets (x : y : z : t) = a. */
89 : FD_25519_INLINE void
90 : fd_ed25519_point_to( fd_f25519_t * x,
91 : fd_f25519_t * y,
92 : fd_f25519_t * z,
93 : fd_f25519_t * t,
94 2411236 : fd_ed25519_point_t const * a ) {
95 2411236 : fd_f25519_set( x, a->X );
96 2411236 : fd_f25519_set( y, a->Y );
97 2411236 : fd_f25519_set( z, a->Z );
98 2411236 : fd_f25519_set( t, a->T );
99 2411236 : }
100 :
101 : /* fd_ed25519_point_sub sets r = -a. */
102 : FD_25519_INLINE fd_ed25519_point_t *
103 : fd_ed25519_point_neg( fd_ed25519_point_t * r,
104 515048 : fd_ed25519_point_t const * a ) {
105 515048 : fd_f25519_neg( r->X, a->X );
106 515048 : fd_f25519_set( r->Y, a->Y );
107 515048 : fd_f25519_set( r->Z, a->Z );
108 515048 : fd_f25519_neg( r->T, a->T );
109 515048 : return r;
110 515048 : }
111 :
112 : /* fd_ed25519_point_is_zero returns 1 if a == 0 (point at infinity), 0 otherwise. */
113 : FD_25519_INLINE int
114 0 : fd_ed25519_point_is_zero( fd_ed25519_point_t const * a ) {
115 0 : return fd_f25519_is_zero( a->X ) & fd_f25519_eq( a->Y, a->Z );
116 0 : }
117 :
118 : /* fd_ed25519_point_eq returns 1 if a == b, 0 otherwise. */
119 : FD_25519_INLINE int
120 : fd_ed25519_point_eq( fd_ed25519_point_t const * a,
121 2 : fd_ed25519_point_t const * b ) {
122 2 : fd_f25519_t x1[1], x2[1], y1[1], y2[1];
123 2 : fd_f25519_mul( x1, b->X, a->Z );
124 2 : fd_f25519_mul( x2, a->X, b->Z );
125 2 : fd_f25519_mul( y1, b->Y, a->Z );
126 2 : fd_f25519_mul( y2, a->Y, b->Z );
127 2 : return fd_f25519_eq( x1, x2 ) & fd_f25519_eq( y1, y2 );
128 2 : }
129 :
130 : /* fd_ed25519_point_eq returns 1 if a == b, 0 otherwise.
131 : b is a point with Z==1, e.g. a decompressed point. */
132 : FD_25519_INLINE int
133 : fd_ed25519_point_eq_z1( fd_ed25519_point_t const * a,
134 515048 : fd_ed25519_point_t const * b ) { /* b.Z == 1, e.g. a decompressed point */
135 515048 : fd_f25519_t x1[1], y1[1];
136 515048 : fd_f25519_mul( x1, b->X, a->Z );
137 515048 : fd_f25519_mul( y1, b->Y, a->Z );
138 515048 : return fd_f25519_eq( x1, a->X ) & fd_f25519_eq( y1, a->Y );
139 515048 : }
140 :
141 : /* fd_curve25519_into_precomputed transforms a point into
142 : precomputed table format, e.g. replaces T -> kT to save
143 : 1mul in the dbl-and-add loop. */
144 : FD_25519_INLINE void
145 5448000 : fd_curve25519_into_precomputed( fd_ed25519_point_t * r ) {
146 5448000 : #if CURVE25519_PRECOMP_XY
147 5448000 : fd_f25519_t add[1], sub[1];
148 5448000 : fd_f25519_add_nr( add, r->Y, r->X );
149 5448000 : fd_f25519_sub_nr( sub, r->Y, r->X );
150 5448000 : fd_f25519_set( r->X, sub );
151 5448000 : fd_f25519_set( r->Y, add );
152 5448000 : #endif
153 5448000 : fd_f25519_mul( r->T, r->T, fd_f25519_k );
154 5448000 : }
155 :
156 : /* fd_ed25519_point_add_final_mul computes just the final mul step in point add.
157 : See fd_ed25519_point_add_with_opts. */
158 : FD_25519_INLINE fd_ed25519_point_t *
159 : fd_ed25519_point_add_final_mul( fd_ed25519_point_t * restrict r,
160 47446419 : fd_ed25519_point_t const * a ) {
161 47446419 : fd_f25519_t const *r1 = a->X;
162 47446419 : fd_f25519_t const *r2 = a->Y;
163 47446419 : fd_f25519_t const *r3 = a->Z;
164 47446419 : fd_f25519_t const *r4 = a->T;
165 :
166 47446419 : fd_f25519_mul4( r->X, r1, r2,
167 47446419 : r->Y, r3, r4,
168 47446419 : r->Z, r2, r3,
169 47446419 : r->T, r1, r4 );
170 47446419 : return r;
171 47446419 : }
172 :
173 : /* fd_ed25519_point_add_final_mul_projective computes just the final mul step
174 : in point add, assuming the result is projective (X, Y, Z), i.e. ignoring T.
175 : This is useful because dbl only needs (X, Y, Z) in input, so we can save 1mul.
176 : See fd_ed25519_point_add_with_opts. */
177 : FD_25519_INLINE fd_ed25519_point_t *
178 : fd_ed25519_point_add_final_mul_projective( fd_ed25519_point_t * restrict r,
179 134789637 : fd_ed25519_point_t const * a ) {
180 134789637 : fd_f25519_mul3( r->X, a->X, a->Y,
181 134789637 : r->Y, a->Z, a->T,
182 134789637 : r->Z, a->Y, a->Z );
183 134789637 : return r;
184 134789637 : }
185 :
186 : /* Dedicated dbl
187 : https://eprint.iacr.org/2008/522
188 : Sec 4.4.
189 : This uses sqr instead of mul. */
190 : FD_25519_INLINE fd_ed25519_point_t *
191 : fd_ed25519_partial_dbl( fd_ed25519_point_t * r,
192 136010499 : fd_ed25519_point_t const * a ) {
193 136010499 : fd_f25519_t r1[1], r2[1], r3[1], r4[1];
194 136010499 : fd_f25519_t r5[1];
195 :
196 136010499 : fd_f25519_add_nr( r1, a->X, a->Y );
197 :
198 136010499 : fd_f25519_sqr4( r2, a->X,
199 136010499 : r3, a->Y,
200 136010499 : r4, a->Z,
201 136010499 : r5, r1 );
202 :
203 : /* important: reduce mod p (these values are used in add/sub) */
204 136010499 : fd_f25519_add( r4, r4, r4 );
205 136010499 : fd_f25519_add( r->T, r2, r3 );
206 136010499 : fd_f25519_sub( r->Z, r2, r3 );
207 :
208 136010499 : fd_f25519_add_nr( r->Y, r4, r->Z );
209 136010499 : fd_f25519_sub_nr( r->X, r->T, r5 );
210 136010499 : return r;
211 136010499 : }
212 :
213 : FD_25519_INLINE fd_ed25519_point_t * FD_FN_NO_ASAN
214 : fd_ed25519_point_dbln( fd_ed25519_point_t * r,
215 : fd_ed25519_point_t const * a,
216 681000 : int n ) {
217 681000 : fd_ed25519_point_t t[1];
218 681000 : fd_ed25519_partial_dbl( t, a );
219 681000 : for( uchar i=1; i<n; i++ ) {
220 0 : fd_ed25519_point_add_final_mul_projective( r, t );
221 0 : fd_ed25519_partial_dbl( t, r );
222 0 : }
223 681000 : return fd_ed25519_point_add_final_mul( r, t );
224 681000 : }
225 :
226 : FD_PROTOTYPES_END
|
