iPXE
weierstrass.c
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2024 Michael Brown <mbrown@fensystems.co.uk>.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License as
6  * published by the Free Software Foundation; either version 2 of the
7  * License, or any later version.
8  *
9  * This program is distributed in the hope that it will be useful, but
10  * WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
17  * 02110-1301, USA.
18  *
19  * You can also choose to distribute this program under the terms of
20  * the Unmodified Binary Distribution Licence (as given in the file
21  * COPYING.UBDL), provided that you have satisfied its requirements.
22  */
23 
24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
25 
26 /** @file
27  *
28  * Weierstrass elliptic curves
29  *
30  * The implementation is based upon Algorithm 1 from "Complete
31  * addition formulas for prime order elliptic curves" (Joost Renes,
32  * Craig Costello, and Lejla Batina), available from
33  *
34  * https://www.microsoft.com/en-us/research/wp-content/uploads/2016/06/complete-2.pdf
35  *
36  * The steps within the algorithm have been reordered and temporary
37  * variables shuffled to reduce stack usage, and calculations are
38  * carried out modulo small multiples of the field prime in order to
39  * elide reductions after intermediate addition and subtraction
40  * operations.
41  *
42  * The algorithm is encoded using a bytecode representation, since
43  * this substantially reduces the code size compared to direct
44  * implementation of the big integer operations.
45  */
46 
47 #include <errno.h>
48 #include <ipxe/weierstrass.h>
49 
50 /** Big integer register names */
52 
53  /*
54  * Read-only registers
55  */
56 
57  /* Curve constant "a" (for multiply), zero (for add/subtract) */
59  /* Curve constant "3b" */
61  /* Augend (x,y,z) co-ordinates */
65  /* Addend (x,y,z) co-ordinates */
69 
70  /*
71  * Read-write registers
72  */
73 
74  /* Temporary working registers */
79  /* Low half of multiplication product */
81  /* Result (x,y,z) co-ordinates */
85 
86  /* Number of registers */
88 };
89 
90 /** Zero register (for add/subtract operations */
91 #define WEIERSTRASS_zero WEIERSTRASS_a
92 
93 /** Construct big integer register index */
94 #define WEIERSTRASS_REGISTER( name ) _C2 ( WEIERSTRASS_, name )
95 
96 /** Bytecode operation codes */
98  /** Subtract big integers (and add nothing)*/
100  /** Subtract big integers (and add 2N) */
102  /** Subtract big integers (and add 4N) */
104  /** Add big integers */
106  /** Multiply big integers (and perform Montgomery reduction) */
108 };
109 
110 /**
111  * Define a bytecode operation
112  *
113  * @v opcode Operation code
114  * @v dest Destination big integer register name
115  * @v left Left source big integer register name
116  * @v right Right source big integer register name
117  */
118 #define WEIERSTRASS_OP( opcode, dest, left, right ) \
119  ( ( (opcode) << 12 ) | \
120  ( WEIERSTRASS_REGISTER ( dest ) << 8 ) | \
121  ( WEIERSTRASS_REGISTER ( left ) << 4 ) | \
122  ( WEIERSTRASS_REGISTER ( right ) << 0 ) )
123 
124 /** Extract bytecode operation code */
125 #define WEIERSTRASS_OPCODE( op ) ( ( (op) >> 12 ) & 0xf )
126 
127 /** Extract destination big integer register */
128 #define WEIERSTRASS_DEST( op ) ( ( (op) >> 8 ) & 0xf )
129 
130 /** Extract left source big integer register */
131 #define WEIERSTRASS_LEFT( op ) ( ( (op) >> 4 ) & 0xf )
132 
133 /** Extract right source big integer register */
134 #define WEIERSTRASS_RIGHT( op ) ( ( (op) >> 0 ) & 0xf )
135 
136 /** Define a three-argument addition operation */
137 #define WEIERSTRASS_ADD3( dest, augend, addend ) \
138  WEIERSTRASS_OP ( WEIERSTRASS_OP_ADD, dest, augend, addend )
139 
140 /** Define a two-argument addition operation */
141 #define WEIERSTRASS_ADD2( augend, addend ) \
142  WEIERSTRASS_ADD3 ( augend, augend, addend )
143 
144 /** Define a move operation */
145 #define WEIERSTRASS_MOV( dest, source ) \
146  WEIERSTRASS_ADD3( dest, source, zero )
147 
148 /** Define a three-argument subtraction operation */
149 #define WEIERSTRASS_SUB3( dest, minuend, subtrahend, multiple ) \
150  WEIERSTRASS_OP ( _C2 ( WEIERSTRASS_OP_SUB_, multiple ), \
151  dest, minuend, subtrahend )
152 
153 /** Define a two-argument subtraction operation */
154 #define WEIERSTRASS_SUB2( minuend, subtrahend, multiple ) \
155  WEIERSTRASS_SUB3 ( minuend, minuend, subtrahend, multiple )
156 
157 /** Define a stop operation */
158 #define WEIERSTRASS_STOP WEIERSTRASS_SUB2 ( zero, zero, 0N )
159 
160 /** Define a three-argument multiplication operation */
161 #define WEIERSTRASS_MUL3( dest, multiplicand, multiplier ) \
162  WEIERSTRASS_OP ( WEIERSTRASS_OP_MUL, dest, multiplicand, multiplier )
163 
164 /** Define a two-argument multiplication operation */
165 #define WEIERSTRASS_MUL2( multiplicand, multiplier ) \
166  WEIERSTRASS_MUL3 ( multiplicand, multiplicand, multiplier )
167 
168 /**
169  * Initialise curve
170  *
171  * @v curve Weierstrass curve
172  */
173 static void weierstrass_init ( struct weierstrass_curve *curve ) {
174  unsigned int size = curve->size;
175  bigint_t ( size ) __attribute__ (( may_alias )) *prime =
176  ( ( void * ) curve->prime[0] );
177  bigint_t ( size ) __attribute__ (( may_alias )) *fermat =
178  ( ( void * ) curve->fermat );
179  bigint_t ( size ) __attribute__ (( may_alias )) *square =
180  ( ( void * ) curve->square );
181  bigint_t ( size ) __attribute__ (( may_alias )) *one =
182  ( ( void * ) curve->one );
183  bigint_t ( size ) __attribute__ (( may_alias )) *a =
184  ( ( void * ) curve->a );
185  bigint_t ( size ) __attribute__ (( may_alias )) *b3 =
186  ( ( void * ) curve->b3 );
187  bigint_t ( size ) __attribute__ (( may_alias )) *mont =
188  ( ( void * ) curve->mont[0] );
189  bigint_t ( size ) __attribute__ (( may_alias )) *temp =
190  ( ( void * ) curve->prime[1] );
191  bigint_t ( size * 2 ) __attribute__ (( may_alias )) *product =
192  ( ( void * ) temp );
193  bigint_t ( size ) __attribute__ (( may_alias )) *two =
194  ( ( void * ) temp );
195  static const uint8_t one_raw[] = { 1 };
196  static const uint8_t two_raw[] = { 2 };
197  size_t len = curve->len;
198  unsigned int i;
199 
200  /* Initialise field prime */
201  bigint_init ( prime, curve->prime_raw, len );
202  DBGC ( curve, "WEIERSTRASS %s N = %s\n",
203  curve->name, bigint_ntoa ( prime ) );
204 
205  /* Calculate Montgomery constant R^2 mod N */
206  bigint_reduce ( prime, square );
207  DBGC ( curve, "WEIERSTRASS %s R^2 = %s mod N\n",
208  curve->name, bigint_ntoa ( square ) );
209 
210  /* Calculate constant "3b" */
211  bigint_init ( b3, curve->b_raw, len );
212  DBGC ( curve, "WEIERSTRASS %s b = %s\n",
213  curve->name, bigint_ntoa ( b3 ) );
214  bigint_copy ( b3, a );
215  bigint_add ( b3, b3 );
216  bigint_add ( a, b3 );
217 
218  /* Initialise "a" */
219  bigint_init ( a, curve->a_raw, len );
220  DBGC ( curve, "WEIERSTRASS %s a = %s\n",
221  curve->name, bigint_ntoa ( a ) );
222 
223  /* Initialise "1" */
224  bigint_init ( one, one_raw, sizeof ( one_raw ) );
225 
226  /* Convert relevant constants to Montgomery form
227  *
228  * We rely on the fact that the prime multiples have not yet
229  * been calculated, and so can be used as a temporary buffer.
230  */
231  for ( i = 0 ; i < WEIERSTRASS_NUM_MONT ; i++ ) {
232  static const char *names[] = { " ", " a", "3b" };
233  bigint_multiply ( &mont[i], square, product );
234  bigint_montgomery ( prime, product, &mont[i] );
235  DBGC ( curve, "WEIERSTRASS %s %sR = %s mod N\n",
236  curve->name, names[i], bigint_ntoa ( &mont[i] ) );
237  }
238 
239  /* Calculate constant "N-2"
240  *
241  * We rely on the fact that the prime multiples have not yet
242  * been calculated, and so can be used as a temporary buffer.
243  */
244  bigint_copy ( prime, fermat );
245  bigint_init ( two, two_raw, sizeof ( two_raw ) );
246  bigint_subtract ( two, fermat );
247  DBGC ( curve, "WEIERSTRASS %s N-2 = %s\n",
248  curve->name, bigint_ntoa ( fermat ) );
249 
250  /* Calculate multiples of field prime */
251  for ( i = 1 ; i < WEIERSTRASS_NUM_MULTIPLES ; i++ ) {
252  bigint_copy ( &prime[ i - 1 ], &prime[i] );
253  bigint_add ( &prime[i], &prime[i] );
254  DBGC ( curve, "WEIERSTRASS %s %dN = %s\n",
255  curve->name, ( 1 << i ), bigint_ntoa ( &prime[i] ) );
256  }
257 }
258 
259 /**
260  * Execute bytecode instruction
261  *
262  * @v curve Weierstrass curve
263  * @v regs Registers
264  * @v size Big integer size
265  * @v op Operation
266  */
267 static void weierstrass_exec ( const struct weierstrass_curve *curve,
268  void **regs, unsigned int size,
269  unsigned int op ) {
270  const bigint_t ( size ) __attribute__ (( may_alias ))
271  *prime = ( ( const void * ) curve->prime[0] );
272  bigint_t ( size * 2 ) __attribute__ (( may_alias ))
274  bigint_t ( size ) __attribute__ (( may_alias )) *dest;
275  const bigint_t ( size ) __attribute__ (( may_alias )) *left;
276  const bigint_t ( size ) __attribute__ (( may_alias )) *right;
277  const bigint_t ( size ) __attribute__ (( may_alias )) *addend;
278  const bigint_t ( size ) __attribute__ (( may_alias )) *subtrahend;
279  unsigned int op_code;
280  unsigned int op_dest;
281  unsigned int op_left;
282  unsigned int op_right;
283 
284  /* Decode instruction */
285  op_code = WEIERSTRASS_OPCODE ( op );
286  op_dest = WEIERSTRASS_DEST ( op );
287  op_left = WEIERSTRASS_LEFT ( op );
288  op_right = WEIERSTRASS_RIGHT ( op );
289  dest = regs[op_dest];
290  left = regs[op_left];
291  right = regs[op_right];
292 
293  /* Check destination is a writable register */
294  assert ( op_dest >= WEIERSTRASS_Wt );
295 
296  /* Handle multiplications */
297  if ( op_code == WEIERSTRASS_OP_MUL ) {
298  assert ( op_left != WEIERSTRASS_Wp );
299  assert ( op_right != WEIERSTRASS_Wp );
300  bigint_multiply ( left, right, product );
302  DBGCP ( curve, "WEIERSTRASS %s R%d := R%d x R%d = %s\n",
303  curve->name, op_dest, op_left, op_right,
304  bigint_ntoa ( dest ) );
305  return;
306  }
307 
308  /* Copy left source, if required */
309  if ( op_dest != op_left )
310  bigint_copy ( left, dest );
311 
312  /* Do nothing more if addend/subtrahend is zero */
313  if ( ! op_right ) {
314  DBGCP ( curve, "WEIERSTRASS %s R%d := R%d = %s\n",
315  curve->name, op_dest, op_left, bigint_ntoa ( dest ) );
316  return;
317  }
318 
319  /* Determine addend and subtrahend */
320  addend = NULL;
321  subtrahend = NULL;
322  if ( op_code == WEIERSTRASS_OP_ADD ) {
323  DBGCP ( curve, "WEIERSTRASS %s R%d := R%d + R%d = ",
324  curve->name, op_dest, op_left, op_right );
325  addend = ( ( const void * ) right );
326  } else {
327  subtrahend = ( ( const void * ) right );
328  if ( op_code > WEIERSTRASS_OP_SUB_0N ) {
329  DBGCP ( curve, "WEIERSTRASS %s R%d := R%d - R%d + "
330  "%dN = ", curve->name, op_dest, op_left,
331  op_right, ( 1 << op_code ) );
332  addend = ( ( const void * ) curve->prime[op_code] );
333  } else {
334  DBGCP ( curve, "WEIERSTRASS %s R%d := R%d - R%d = ",
335  curve->name, op_dest, op_left, op_right );
336  }
337  }
338 
339  /* Perform addition and subtraction */
340  if ( addend )
341  bigint_add ( addend, dest );
342  if ( subtrahend )
344  DBGCP ( curve, "%s\n", bigint_ntoa ( dest ) );
345 }
346 
347 /**
348  * Add points on curve
349  *
350  * @v curve Weierstrass curve
351  * @v augend0 Element 0 of point (x1,y1,z1) to be added
352  * @v addend0 Element 0 of point (x2,y2,z2) to be added
353  * @v result0 Element 0 of point (x3,y3,z3) to hold result
354  *
355  * Points are represented in projective coordinates, with all values
356  * in Montgomery form and in the range [0,4N) where N is the field
357  * prime.
358  *
359  * The augend may have the same value as the addend (i.e. this routine
360  * may be used to perform point doubling as well as point addition),
361  * and either or both may be the point at infinity.
362  *
363  * The result may overlap either input, since the inputs are fully
364  * consumed before the result is written.
365  */
366 static void weierstrass_add_raw ( const struct weierstrass_curve *curve,
367  const bigint_element_t *augend0,
368  const bigint_element_t *addend0,
369  bigint_element_t *result0 ) {
370  unsigned int size = curve->size;
371  const bigint_t ( size ) __attribute__ (( may_alias ))
372  *prime = ( ( const void * ) curve->prime[0] );
373  const bigint_t ( size ) __attribute__ (( may_alias ))
374  *a = ( ( const void * ) curve->a );
375  const bigint_t ( size ) __attribute__ (( may_alias ))
376  *b3 = ( ( const void * ) curve->b3 );
377  const weierstrass_t ( size ) __attribute__ (( may_alias ))
378  *augend = ( ( const void * ) augend0 );
379  const weierstrass_t ( size ) __attribute__ (( may_alias ))
380  *addend = ( ( const void * ) addend0 );
381  weierstrass_t ( size ) __attribute__ (( may_alias ))
382  *result = ( ( void * ) result0 );
383  struct {
384  bigint_t ( size ) Wt;
385  bigint_t ( size ) Wxy;
386  bigint_t ( size ) Wyz;
387  bigint_t ( size ) Wzx;
388  bigint_t ( size * 2 ) Wp;
389  } temp;
391  unsigned int schedule;
392  const uint16_t *op;
393  unsigned int i;
394 
395  /* On entry, we assume that x1, x2, y1, y2, z1, z2 are all in
396  * the range [0,4N). Additions will extend the range.
397  * Subtractions will extend the range (and require an addition
398  * of a suitable multiple of the modulus to ensure that the
399  * result is a positive value). Relaxed Montgomery
400  * multiplications will reduce the range to [0,2N). The
401  * outputs x3, y3, z3 will be in the range [0,4N) and
402  * therefore usable as subsequent inputs.
403  */
404  static const uint16_t ops[] = {
405  /* [Wxy] Qxy = (x1+y1)*(x2+y2) (mod 2N) */
406  WEIERSTRASS_ADD3 ( Wt, x1, y1 ),
407  WEIERSTRASS_ADD3 ( Wxy, x2, y2 ),
408  WEIERSTRASS_MUL2 ( Wxy, Wt ),
409  /* [Wyz] Qyz = (y1+z1)*(y2+z2) (mod 2N) */
410  WEIERSTRASS_ADD3 ( Wt, y1, z1 ),
411  WEIERSTRASS_ADD3 ( Wyz, y2, z2 ),
412  WEIERSTRASS_MUL2 ( Wyz, Wt ),
413  /* [Wzx] Qzx = (z1+x1)*(z2+x2) (mod 2N) */
414  WEIERSTRASS_ADD3 ( Wt, z1, x1 ),
415  WEIERSTRASS_ADD3 ( Wzx, z2, x2 ),
416  WEIERSTRASS_MUL2 ( Wzx, Wt ),
417  /* [x3] Px = x1*x2 (mod 2N) */
418  WEIERSTRASS_MUL3 ( x3, x1, x2 ),
419  /* [y3] Py = y1*y2 (mod 2N) */
420  WEIERSTRASS_MUL3 ( y3, y1, y2 ),
421  /* [z3] Pz = z1*z2 (mod 2N) */
422  WEIERSTRASS_MUL3 ( z3, z1, z2 ),
423  /* [Wxy] Rxy = Qxy - Px - Py (mod 6N)
424  * = (x1+y1)*(x2+y2) - x1*x2 - y1*y2 (mod 6N)
425  * = x1*y2 + x2*y1 (mod 6N)
426  */
427  WEIERSTRASS_SUB2 ( Wxy, x3, 0N ),
428  WEIERSTRASS_SUB2 ( Wxy, y3, 4N ),
429  /* [Wyz] Ryz = Qyz - Py - Pz (mod 6N)
430  * = (y1+z1)*(y2+z2) - y1*y2 - z1*z2 (mod 6N)
431  * = y1*z2 + y2*z1 (mod 6N)
432  */
433  WEIERSTRASS_SUB2 ( Wyz, y3, 0N ),
434  WEIERSTRASS_SUB2 ( Wyz, z3, 4N ),
435  /* [Wzx] Rzx = Qzx - Pz - Px (mod 6N)
436  * = (z1+x1)*(z2+x2) - z1*z2 - x1*x2 (mod 6N)
437  * = x1*z2 + x2*z1 (mod 6N)
438  */
439  WEIERSTRASS_SUB2 ( Wzx, z3, 0N ),
440  WEIERSTRASS_SUB2 ( Wzx, x3, 4N ),
441  /* [Wt] aRzx = a * Rzx (mod 2N)
442  * = a * (x1*z2 + x2*z1) (mod 2N)
443  */
444  WEIERSTRASS_MUL3 ( Wt, a, Wzx ),
445  /* [Wp] 3bPz = 3b * Pz (mod 2N)
446  * = 3b*z1*z2 (mod 2N)
447  */
448  WEIERSTRASS_MUL3 ( Wp, 3b, z3 ),
449  /* [Wp] Sy = aRzx + 3bPz (mod 4N)
450  * = a*(x1*z2 + x2*z1) + 3b*z1*z2 (mod 4N)
451  */
452  WEIERSTRASS_ADD2 ( Wp, Wt ),
453  /* [Wt] Syz = Py + Sy (mod 6N)
454  * = y1*y2 + a*(x1*z2 + x2*z1) + 3b*z1*z2 (mod 6N)
455  */
456  WEIERSTRASS_ADD3 ( Wt, y3, Wp ),
457  /* [y3] Sxy = Py - Sy (mod 6N)
458  * = y1*y2 - a*(x1*z2 + x2*z1) - 3b*z1*z2 (mod 6N)
459  */
460  WEIERSTRASS_SUB2 ( y3, Wp, 4N ),
461  /* [z3] aPz = a * Pz (mod 2N)
462  * = a * z1*z2 (mod 2N)
463  */
464  WEIERSTRASS_MUL2 ( z3, a ),
465  /* [Wzx] 3bRzx = 3b * Rzx (mod 2N)
466  * = 3b * (x1*z2 + x2*z1) (mod 2N)
467  */
468  WEIERSTRASS_MUL2 ( Wzx, 3b ),
469  /* [x3] aPzx' = Px - aPz (mod 4N)
470  * = x1*x2 - a*z1*z2 (mod 4N)
471  */
472  WEIERSTRASS_SUB2 ( x3, z3, 2N ),
473  /* [Wp] Szx = a * aPzx' (mod 2N)
474  * = a * (x1*x2 - a*z1*z2) (mod 2N)
475  * = a*x1*x2 - (a^2)*z1*z2 (mod 2N)
476  */
477  WEIERSTRASS_MUL3 ( Wp, a, x3 ),
478  /* [x3] Px = aPzx' + aPz (mod 6N)
479  * = x1*x2 - a*z1*z2 + a*z1*z2 (mod 6N)
480  * = x1*x2 (mod 6N)
481  */
482  WEIERSTRASS_ADD2 ( x3, z3 ),
483  /* [Wzx] Tzx = 3bRzx + Szx (mod 4N)
484  * = a*x1*x2 + 3b*(x1*z2 + x2*z1) -
485  * (a^2)*z1*z2 (mod 4N)
486  */
487  WEIERSTRASS_ADD2 ( Wzx, Wp ),
488  /* [z3] aPzx = Px + aPz (mod 8N)
489  * = x1*x2 + a*z1*z2 (mod 8N)
490  */
491  WEIERSTRASS_ADD2 ( z3, x3 ),
492  /* [x3] 2Px = Px + Px (mod 12N)
493  * = 2*x1*x2 (mod 12N)
494  */
495  WEIERSTRASS_ADD2 ( x3, x3 ),
496  /* [x3] Tyz = 2Px + aPzx (mod 20N)
497  * = 2*x1*x2 + x1*x2 + a*z1*z2 (mod 20N)
498  * = 3*x1*x2 + a*z1*z2 (mod 20N)
499  */
500  WEIERSTRASS_ADD2 ( x3, z3 ),
501  /* [z3] Syz = Syz (mod 6N)
502  * = y1*y2 + a*(x1*z2 + x2*z1) + 3b*z1*z2 (mod 6N)
503  */
504  WEIERSTRASS_MOV ( z3, Wt ),
505  /* [Wt] Tyz = Tyz (mod 20N)
506  * = 3*x1*x2 + a*z1*z2 (mod 20N)
507  */
508  WEIERSTRASS_MOV ( Wt, x3 ),
509  /* [x3] Ux = Rxy * Sxy (mod 2N)
510  * = (x1*y2 + x2*y1) *
511  * (y1*y2 - a*(x1*z2 + x2*z1) - 3b*z1*z2) (mod 2N)
512  */
513  WEIERSTRASS_MUL3 ( x3, Wxy, y3 ),
514  /* [y3] Uy = Syz * Sxy (mod 2N)
515  * = (y1*y2 + a*(x1*z2 + x2*z1) + 3b*z1*z2) *
516  * (y1*y2 - a*(x1*z2 + x2*z1) - 3b*z1*z2) (mod 2N)
517  */
518  WEIERSTRASS_MUL2 ( y3, z3 ),
519  /* [z3] Uz = Ryz * Syz (mod 2N)
520  * = (y1*z2 + y2*z1) *
521  * (y1*y2 + a*(x1*z2 + x2*z1) + 3b*z1*z2) (mod 2N)
522  */
523  WEIERSTRASS_MUL2 ( z3, Wyz ),
524  /* [Wp] Vx = Ryz * Tzx (mod 2N)
525  * = (y1*z2 + y2*z1) *
526  * (a*x1*x2 + 3b*(x1*z2 + x2*z1) - (a^2)*z1*z2)
527  * (mod 2N)
528  */
529  WEIERSTRASS_MUL3 ( Wp, Wyz, Wzx ),
530  /* [x3] x3 = Ux - Vx (mod 4N)
531  * = ((x1*y2 + x2*y1) *
532  * (y1*y2 - a*(x1*z2 + x2*z1) - 3b*z1*z2)) -
533  * ((y1*z2 + y2*z1) *
534  * (a*x1*x2 + 3b*(x1*z2 + x2*z1) - (a^2)*z1*z2))
535  * (mod 4N)
536  */
537  WEIERSTRASS_SUB2 ( x3, Wp, 2N ),
538  /* [Wp] Vy = Tyz * Tzx (mod 2N)
539  * = (3*x1*x2 + a*z1*z2) *
540  * (a*x1*x2 + 3b*(x1*z2 + x2*z1) - (a^2)*z1*z2)
541  * (mod 2N)
542  */
543  WEIERSTRASS_MUL3 ( Wp, Wt, Wzx ),
544  /* [y3] y3 = Vy + Uy (mod 4N)
545  * = ((3*x1*x2 + a*z1*z2) *
546  * (a*x1*x2 + 3b*(x1*z2 + x2*z1) - (a^2)*z1*z2)) +
547  * ((y1*y2 + a*(x1*z2 + x2*z1) + 3b*z1*z2) *
548  * (y1*y2 - a*(x1*z2 + x2*z1) - 3b*z1*z2))
549  * (mod 4N)
550  */
551  WEIERSTRASS_ADD2 ( y3, Wp ),
552  /* [Wp] Vz = Rxy * Tyz (mod 2N)
553  * = (x1*y2 + x2*y1) * (3*x1*x2 + a*z1*z2) (mod 2N)
554  */
555  WEIERSTRASS_MUL3 ( Wp, Wxy, Wt ),
556  /* [z3] z3 = Uz + Vz (mod 4N)
557  * = ((y1*z2 + y2*z1) *
558  * (y1*y2 + a*(x1*z2 + x2*z1) + 3b*z1*z2)) +
559  * ((x1*y2 + x2*y1) * (3*x1*x2 + a*z1*z2))
560  * (mod 4N)
561  */
562  WEIERSTRASS_ADD2 ( z3, Wp ),
563  /* Stop */
565  };
566 
567  /* Initialise register list */
568  regs[WEIERSTRASS_a] = ( ( void * ) a );
569  regs[WEIERSTRASS_3b] = ( ( void * ) b3 );
570  regs[WEIERSTRASS_x1] = ( ( void * ) &augend->x );
571  regs[WEIERSTRASS_x2] = ( ( void * ) &addend->x );
572  regs[WEIERSTRASS_x3] = ( ( void * ) &result->x );
573  regs[WEIERSTRASS_Wt] = &temp;
574  schedule = ( ( ( 1 << WEIERSTRASS_NUM_REGISTERS ) - 1 )
575  - ( 1 << WEIERSTRASS_a )
576  - ( 1 << WEIERSTRASS_3b )
577  - ( 1 << WEIERSTRASS_x1 )
578  - ( 1 << WEIERSTRASS_x2 )
579  - ( 1 << WEIERSTRASS_x3 )
580  - ( 1 << WEIERSTRASS_Wt ) );
581  for ( i = 0 ; schedule ; i++, schedule >>= 1 ) {
582  if ( schedule & 1 )
583  regs[i] = ( regs[ i - 1 ] + sizeof ( *prime ) );
584  }
585  DBGC2 ( curve, "WEIERSTRASS %s augend (%s,",
586  curve->name, bigint_ntoa ( &augend->x ) );
587  DBGC2 ( curve, "%s,", bigint_ntoa ( &augend->y ) );
588  DBGC2 ( curve, "%s)\n", bigint_ntoa ( &augend->z ) );
589  DBGC2 ( curve, "WEIERSTRASS %s addend (%s,",
590  curve->name, bigint_ntoa ( &addend->x ) );
591  DBGC2 ( curve, "%s,", bigint_ntoa ( &addend->y ) );
592  DBGC2 ( curve, "%s)\n", bigint_ntoa ( &addend->z ) );
593 
594  /* Sanity checks */
595  assert ( regs[WEIERSTRASS_a] == a );
596  assert ( regs[WEIERSTRASS_3b] == b3 );
597  assert ( regs[WEIERSTRASS_x1] == &augend->x );
598  assert ( regs[WEIERSTRASS_y1] == &augend->y );
599  assert ( regs[WEIERSTRASS_z1] == &augend->z );
600  assert ( regs[WEIERSTRASS_x2] == &addend->x );
601  assert ( regs[WEIERSTRASS_y2] == &addend->y );
602  assert ( regs[WEIERSTRASS_z2] == &addend->z );
603  assert ( regs[WEIERSTRASS_x3] == &result->x );
604  assert ( regs[WEIERSTRASS_y3] == &result->y );
605  assert ( regs[WEIERSTRASS_z3] == &result->z );
606  assert ( regs[WEIERSTRASS_Wt] == &temp.Wt );
607  assert ( regs[WEIERSTRASS_Wxy] == &temp.Wxy );
608  assert ( regs[WEIERSTRASS_Wyz] == &temp.Wyz );
609  assert ( regs[WEIERSTRASS_Wzx] == &temp.Wzx );
610  assert ( regs[WEIERSTRASS_Wp] == &temp.Wp );
611 
612  /* Execute bytecode instruction sequence */
613  for ( op = ops ; *op != WEIERSTRASS_STOP ; op++ )
614  weierstrass_exec ( curve, regs, size, *op );
615  DBGC2 ( curve, "WEIERSTRASS %s result (%s,",
616  curve->name, bigint_ntoa ( &result->x ) );
617  DBGC2 ( curve, "%s,", bigint_ntoa ( &result->y ) );
618  DBGC2 ( curve, "%s)\n", bigint_ntoa ( &result->z ) );
619 }
620 
621 /**
622  * Add points on curve
623  *
624  * @v curve Weierstrass curve
625  * @v augend Point (x1,y1,z1) to be added
626  * @v addend Point (x2,y2,z2) to be added
627  * @v result0 Point (x3,y3,z3) to hold result
628  */
629 #define weierstrass_add( curve, augend, addend, result ) do { \
630  weierstrass_add_raw ( (curve), (augend)->all.element, \
631  (addend)->all.element, \
632  (result)->all.element ); \
633  } while ( 0 )
634 
635 /**
636  * Add points on curve as part of a Montgomery ladder
637  *
638  * @v operand Element 0 of first input operand (may overlap result)
639  * @v result Element 0 of second input operand and result
640  * @v size Number of elements in operands and result
641  * @v ctx Operation context
642  * @v tmp Temporary working space (not used)
643  */
644 static void weierstrass_add_ladder ( const bigint_element_t *operand0,
645  bigint_element_t *result0,
646  unsigned int size, const void *ctx,
647  void *tmp __unused ) {
648  const struct weierstrass_curve *curve = ctx;
649  const weierstrass_t ( curve->size ) __attribute__ (( may_alias ))
650  *operand = ( ( const void * ) operand0 );
651  weierstrass_t ( curve->size ) __attribute__ (( may_alias ))
652  *result = ( ( void * ) result0 );
653 
654  /* Add curve points */
655  assert ( size == bigint_size ( &operand->all ) );
656  assert ( size == bigint_size ( &result->all ) );
657  weierstrass_add ( curve, operand, result, result );
658 }
659 
660 /**
661  * Verify point is on curve
662  *
663  * @v curve Weierstrass curve
664  * @v point0 Element 0 of point (x,y,z) to be verified
665  * @ret rc Return status code
666  *
667  * As with point addition, points are represented in projective
668  * coordinates, with all values in Montgomery form and in the range
669  * [0,4N) where N is the field prime.
670  */
671 static int weierstrass_verify_raw ( const struct weierstrass_curve *curve,
672  const bigint_element_t *point0 ) {
673  unsigned int size = curve->size;
674  const bigint_t ( size ) __attribute__ (( may_alias ))
675  *prime = ( ( const void * ) curve->prime[0] );
676  const bigint_t ( size ) __attribute__ (( may_alias ))
677  *a = ( ( const void * ) curve->a );
678  const bigint_t ( size ) __attribute__ (( may_alias ))
679  *b3 = ( ( const void * ) curve->b3 );
680  const weierstrass_t ( size ) __attribute__ (( may_alias ))
681  *point = ( ( const void * ) point0 );
682  struct {
683  bigint_t ( size ) Wt;
684  bigint_t ( size * 2 ) Wp;
685  } temp;
687  const uint16_t *op;
688 
689  /* Calculate 3*(x^3 + a*x + b - y^2) */
690  static const uint16_t ops[] = {
691  /* [Wt] Tx = x^2 (mod 2N) */
692  WEIERSTRASS_MUL3 ( Wt, x1, x1 ),
693  /* [Wt] Txa = Tx + a (mod 3N)
694  * = x^2 + a (mod 3N)
695  */
696  WEIERSTRASS_MOV ( Wp, a ),
697  WEIERSTRASS_ADD2 ( Wt, Wp ),
698  /* [Wt] Txax = Txa * x (mod 2N)
699  * = (x^2 + a)*x (mod 2N)
700  * = x^3 + a*x (mod 2N)
701  */
702  WEIERSTRASS_MUL2 ( Wt, x1 ),
703  /* [Wp] Ty = y^2 (mod 2N) */
704  WEIERSTRASS_MUL3 ( Wp, y1, y1 ),
705  /* [Wt] Txaxy = Txax - Ty (mod 4N)
706  * = x^3 + a*x - y^2 (mod 4N)
707  */
708  WEIERSTRASS_SUB2 ( Wt, Wp, 2N ),
709  /* [Wp] 2Txaxy = Txaxy + Txaxy (mod 8N)
710  * = 2*(x^3 + a*x - y^2) (mod 8N)
711  */
712  WEIERSTRASS_ADD3 ( Wp, Wt, Wt ),
713  /* [Wt] 3Txaxy = 2Txaxy + Txaxy (mod 12N)
714  * = 3*(x^3 + a*x - y^2) (mod 12N)
715  */
716  WEIERSTRASS_ADD2 ( Wt, Wp ),
717  /* [Wt] 3Txaxyb = 3Txaxy + 3b (mod 13N)
718  * = 3*(x^3 + a*x - y^2) + 3b (mod 13N)
719  * = 3*(x^3 + a*x + b - y^2) (mod 13N)
720  */
721  WEIERSTRASS_ADD2 ( Wt, 3b ),
722  /* Stop */
724  };
725 
726  /* Initialise register list */
727  regs[WEIERSTRASS_a] = ( ( void * ) a );
728  regs[WEIERSTRASS_3b] = ( ( void * ) b3 );
729  regs[WEIERSTRASS_x1] = ( ( void * ) &point->x );
730  regs[WEIERSTRASS_y1] = ( ( void * ) &point->y );
731  regs[WEIERSTRASS_Wt] = &temp.Wt;
732  regs[WEIERSTRASS_Wp] = &temp.Wp;
733 
734  /* Execute bytecode instruction sequence */
735  for ( op = ops ; *op != WEIERSTRASS_STOP ; op++ )
736  weierstrass_exec ( curve, regs, size, *op );
737 
738  /* Check that result is zero (modulo the field prime) */
739  bigint_grow ( &temp.Wt, &temp.Wp );
740  bigint_montgomery ( prime, &temp.Wp, &temp.Wt );
741  if ( ! bigint_is_zero ( &temp.Wt ) ) {
742  DBGC ( curve, "WEIERSTRASS %s base point is not on curve\n",
743  curve->name );
744  return -EINVAL;
745  }
746 
747  return 0;
748 }
749 
750 /**
751  * Verify point is on curve
752  *
753  * @v curve Weierstrass curve
754  * @v point Point (x,y,z) to be verified
755  * @ret rc Return status code
756  */
757 #define weierstrass_verify( curve, point ) ( { \
758  weierstrass_verify_raw ( (curve), (point)->all.element ); \
759  } )
760 
761 /**
762  * Multiply curve point by scalar
763  *
764  * @v curve Weierstrass curve
765  * @v base Base point (or NULL to use generator)
766  * @v scalar Scalar multiple
767  * @v result Result point to fill in
768  * @ret rc Return status code
769  */
770 int weierstrass_multiply ( struct weierstrass_curve *curve, const void *base,
771  const void *scalar, void *result ) {
772  unsigned int size = curve->size;
773  size_t len = curve->len;
774  const bigint_t ( size ) __attribute__ (( may_alias )) *prime =
775  ( ( const void * ) curve->prime[0] );
776  const bigint_t ( size ) __attribute__ (( may_alias )) *prime2 =
777  ( ( const void * ) curve->prime[WEIERSTRASS_2N] );
778  const bigint_t ( size ) __attribute__ (( may_alias )) *fermat =
779  ( ( const void * ) curve->fermat );
780  const bigint_t ( size ) __attribute__ (( may_alias )) *square =
781  ( ( const void * ) curve->square );
782  const bigint_t ( size ) __attribute__ (( may_alias )) *one =
783  ( ( const void * ) curve->one );
784  struct {
785  union {
787  bigint_t ( size * 2 ) product_in;
788  };
789  union {
790  weierstrass_t ( size ) multiple;
791  bigint_t ( size * 2 ) product_out;
792  };
793  bigint_t ( bigint_required_size ( len ) ) scalar;
794  } temp;
795  size_t offset;
796  unsigned int i;
797  int rc;
798 
799  /* Initialise curve, if not already done
800  *
801  * The least significant element of the field prime must be
802  * odd, and so the least significant element of the
803  * (initialised) first multiple of the field prime must be
804  * non-zero.
805  */
806  if ( ! prime2->element[0] )
807  weierstrass_init ( curve );
808 
809  /* Use generator if applicable */
810  if ( ! base )
811  base = curve->base;
812 
813  /* Convert input to projective coordinates in Montgomery form */
814  DBGC ( curve, "WEIERSTRASS %s base (", curve->name );
815  for ( i = 0, offset = 0 ; i < WEIERSTRASS_AXES ; i++, offset += len ) {
816  bigint_init ( &temp.multiple.axis[i], ( base + offset ), len );
817  DBGC ( curve, "%s%s", ( i ? "," : "" ),
818  bigint_ntoa ( &temp.multiple.axis[i] ) );
819  bigint_multiply ( &temp.multiple.axis[i], square,
820  &temp.product_in );
821  bigint_montgomery_relaxed ( prime, &temp.product_in,
822  &temp.multiple.axis[i] );
823  }
824  bigint_copy ( one, &temp.multiple.z );
825  DBGC ( curve, ")\n" );
826 
827  /* Verify point is on curve */
828  if ( ( rc = weierstrass_verify ( curve, &temp.multiple ) ) != 0 )
829  return rc;
830 
831  /* Construct identity element (the point at infinity) */
832  memset ( &temp.result, 0, sizeof ( temp.result ) );
833  bigint_copy ( one, &temp.result.y );
834 
835  /* Initialise scalar */
836  bigint_init ( &temp.scalar, scalar, len );
837  DBGC ( curve, "WEIERSTRASS %s scalar %s\n",
838  curve->name, bigint_ntoa ( &temp.scalar ) );
839 
840  /* Perform multiplication via Montgomery ladder */
841  bigint_ladder ( &temp.result.all, &temp.multiple.all, &temp.scalar,
842  weierstrass_add_ladder, curve, NULL );
843 
844  /* Invert result Z co-ordinate (via Fermat's little theorem) */
845  bigint_copy ( one, &temp.multiple.z );
846  bigint_ladder ( &temp.multiple.z, &temp.result.z, fermat,
847  bigint_mod_exp_ladder, prime, &temp.product_out );
848 
849  /* Convert result back to affine co-ordinates */
850  DBGC ( curve, "WEIERSTRASS %s result (", curve->name );
851  for ( i = 0, offset = 0 ; i < WEIERSTRASS_AXES ; i++, offset += len ) {
852  bigint_multiply ( &temp.result.axis[i], &temp.multiple.z,
853  &temp.product_out );
854  bigint_montgomery_relaxed ( prime, &temp.product_out,
855  &temp.result.axis[i] );
856  bigint_grow ( &temp.result.axis[i], &temp.product_out );
857  bigint_montgomery ( prime, &temp.product_out,
858  &temp.result.axis[i] );
859  DBGC ( curve, "%s%s", ( i ? "," : "" ),
860  bigint_ntoa ( &temp.result.axis[i] ) );
861  bigint_done ( &temp.result.axis[i], ( result + offset ), len );
862  }
863  DBGC ( curve, ")\n" );
864 
865  return 0;
866 }
#define __attribute__(x)
Definition: compiler.h:10
uint32_t base
Base.
Definition: librm.h:252
#define EINVAL
Invalid argument.
Definition: errno.h:428
struct arbelprm_rc_send_wqe rc
Definition: arbel.h:14
unsigned short uint16_t
Definition: stdint.h:11
const uint8_t * base
Base point.
Definition: weierstrass.h:104
bigint_element_t * square
Cached Montgomery constant (R^2 mod N)
Definition: weierstrass.h:111
#define WEIERSTRASS_RIGHT(op)
Extract right source big integer register.
Definition: weierstrass.c:134
#define WEIERSTRASS_STOP
Define a stop operation.
Definition: weierstrass.c:158
weierstrass_register
Big integer register names.
Definition: weierstrass.c:51
bigint_element_t * prime[WEIERSTRASS_NUM_CACHED]
Cached field prime "N" (and multiples thereof)
Definition: weierstrass.h:107
Error codes.
static void weierstrass_exec(const struct weierstrass_curve *curve, void **regs, unsigned int size, unsigned int op)
Execute bytecode instruction.
Definition: weierstrass.c:267
uint8_t size
Entry size (in 32-bit words)
Definition: ena.h:16
#define WEIERSTRASS_AXES
Number of axes in Weierstrass curve point representation.
Definition: weierstrass.h:16
bigint_element_t * mont[WEIERSTRASS_NUM_MONT]
Definition: weierstrass.h:122
#define WEIERSTRASS_OPCODE(op)
Extract bytecode operation code.
Definition: weierstrass.c:125
Weierstrass elliptic curves.
#define DBGC(...)
Definition: compiler.h:505
#define bigint_grow(source, dest)
Grow big integer.
Definition: bigint.h:208
#define bigint_init(value, data, len)
Initialise big integer.
Definition: bigint.h:61
#define weierstrass_verify(curve, point)
Verify point is on curve.
Definition: weierstrass.c:757
struct golan_eq_context ctx
Definition: CIB_PRM.h:28
#define bigint_is_zero(value)
Test if big integer is equal to zero.
Definition: bigint.h:133
#define bigint_montgomery_relaxed(modulus, value, result)
Perform relaxed Montgomery reduction (REDC) of a big integer.
Definition: bigint.h:299
bigint_element_t * b3
Cached constant "3b", in Montgomery form.
Definition: weierstrass.h:120
unsigned long tmp
Definition: linux_pci.h:63
Add big integers.
Definition: weierstrass.c:105
#define WEIERSTRASS_MOV(dest, source)
Define a move operation.
Definition: weierstrass.c:145
static void weierstrass_add_ladder(const bigint_element_t *operand0, bigint_element_t *result0, unsigned int size, const void *ctx, void *tmp __unused)
Add points on curve as part of a Montgomery ladder.
Definition: weierstrass.c:644
static void weierstrass_init(struct weierstrass_curve *curve)
Initialise curve.
Definition: weierstrass.c:173
#define weierstrass_add(curve, augend, addend, result)
Add points on curve.
Definition: weierstrass.c:629
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
#define weierstrass_t(size)
Define a Weierstrass projective co-ordinate type.
Definition: weierstrass.h:57
#define __unused
Declare a variable or data structure as unused.
Definition: compiler.h:573
#define bigint_copy(source, dest)
Copy big integer.
Definition: bigint.h:234
uint32_t bigint_element_t
Element of a big integer.
Definition: bigint.h:15
#define WEIERSTRASS_MUL3(dest, multiplicand, multiplier)
Define a three-argument multiplication operation.
Definition: weierstrass.c:161
static void weierstrass_add_raw(const struct weierstrass_curve *curve, const bigint_element_t *augend0, const bigint_element_t *addend0, bigint_element_t *result0)
Add points on curve.
Definition: weierstrass.c:366
bigint_element_t * fermat
Cached constant "N-2" (for Fermat's little theorem)
Definition: weierstrass.h:109
const uint8_t * b_raw
Constant "b".
Definition: weierstrass.h:102
#define bigint_done(value, out, len)
Finalise big integer.
Definition: bigint.h:74
Subtract big integers (and add 2N)
Definition: weierstrass.c:101
bigint_element_t * a
Cached constant "a", in Montgomery form.
Definition: weierstrass.h:118
#define bigint_required_size(len)
Determine number of elements required for a big-integer type.
Definition: bigint.h:30
#define WEIERSTRASS_NUM_MONT
Number of cached in Montgomery form for each Weierstrass curve.
Definition: weierstrass.h:77
const char * name
Curve name.
Definition: weierstrass.h:94
unsigned char uint8_t
Definition: stdint.h:10
#define WEIERSTRASS_SUB2(minuend, subtrahend, multiple)
Define a two-argument subtraction operation.
Definition: weierstrass.c:154
size_t len
Length of raw scalar values.
Definition: weierstrass.h:96
struct i386_regs regs
Definition: registers.h:15
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
bigint_element_t * one
Cached constant "1", in Montgomery form.
Definition: weierstrass.h:116
uint16_t result
Definition: hyperv.h:33
Subtract big integers (and add nothing)
Definition: weierstrass.c:99
static uint16_t struct vmbus_xfer_pages_operations * op
Definition: netvsc.h:327
#define bigint_montgomery(modulus, value, result)
Perform classic Montgomery reduction (REDC) of a big integer.
Definition: bigint.h:313
#define DBGC2(...)
Definition: compiler.h:522
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:40
#define bigint_multiply(multiplicand, multiplier, result)
Multiply big integers.
Definition: bigint.h:259
if(len >=6 *4) __asm__ __volatile__("movsl" if(len >=5 *4) __asm__ __volatile__("movsl" if(len >=4 *4) __asm__ __volatile__("movsl" if(len >=3 *4) __asm__ __volatile__("movsl" if(len >=2 *4) __asm__ __volatile__("movsl" if(len >=1 *4) __asm__ __volatile__("movsl" if((len % 4) >=2) __asm__ __volatile__("movsw" if((len % 2) >=1) __asm__ __volatile__("movsb" return dest
Definition: string.h:150
#define DBGCP(...)
Definition: compiler.h:539
#define bigint_reduce(modulus, result)
Reduce big integer R^2 modulo N.
Definition: bigint.h:273
uint8_t product
Product string.
Definition: smbios.h:16
#define WEIERSTRASS_MUL2(multiplicand, multiplier)
Define a two-argument multiplication operation.
Definition: weierstrass.c:165
#define WEIERSTRASS_LEFT(op)
Extract left source big integer register.
Definition: weierstrass.c:131
uint16_t offset
Offset to command line.
Definition: bzimage.h:8
#define bigint_ladder(result, multiple, exponent, op, ctx, tmp)
Perform generalised exponentiation via a Montgomery ladder.
Definition: bigint.h:329
const unsigned int size
Number of elements in scalar values.
Definition: weierstrass.h:92
#define WEIERSTRASS_DEST(op)
Extract destination big integer register.
Definition: weierstrass.c:128
Multiply big integers (and perform Montgomery reduction)
Definition: weierstrass.c:107
static int weierstrass_verify_raw(const struct weierstrass_curve *curve, const bigint_element_t *point0)
Verify point is on curve.
Definition: weierstrass.c:671
weierstrass_opcode
Bytecode operation codes.
Definition: weierstrass.c:97
Subtract big integers (and add 4N)
Definition: weierstrass.c:103
static __always_inline off_t userptr_t subtrahend
Definition: librm.h:147
#define WEIERSTRASS_ADD3(dest, augend, addend)
Define a three-argument addition operation.
Definition: weierstrass.c:137
#define bigint_subtract(subtrahend, value)
Subtract big integers.
Definition: bigint.h:98
int weierstrass_multiply(struct weierstrass_curve *curve, const void *base, const void *scalar, void *result)
Multiply curve point by scalar.
Definition: weierstrass.c:770
#define bigint_add(addend, value)
Add big integers.
Definition: bigint.h:86
#define bigint_ntoa(value)
Transcribe big integer (for debugging)
Definition: bigint.h:49
uint32_t len
Length.
Definition: ena.h:14
#define NULL
NULL pointer (VOID *)
Definition: Base.h:321
const uint8_t * prime_raw
Field prime.
Definition: weierstrass.h:98
#define WEIERSTRASS_ADD2(augend, addend)
Define a two-argument addition operation.
Definition: weierstrass.c:141
typedef bigint_t(X25519_SIZE) x25519_t
An X25519 unsigned big integer used in internal calculations.
const uint8_t * a_raw
Constant "a".
Definition: weierstrass.h:100
void * memset(void *dest, int character, size_t len) __nonnull
void bigint_mod_exp_ladder(const bigint_element_t *multiplier0, bigint_element_t *result0, unsigned int size, const void *ctx, void *tmp)
Perform modular multiplication as part of a Montgomery ladder.
Definition: bigint.c:719
A Weierstrass elliptic curve.
Definition: weierstrass.h:90