iPXE
Macros | Enumerations | Functions
weierstrass.c File Reference

Weierstrass elliptic curves. More...

#include <errno.h>
#include <ipxe/weierstrass.h>

Go to the source code of this file.

Macros

#define WEIERSTRASS_zero   WEIERSTRASS_a
 Zero register (for add/subtract operations. More...
 
#define WEIERSTRASS_REGISTER(name)   _C2 ( WEIERSTRASS_, name )
 Construct big integer register index. More...
 
#define WEIERSTRASS_OP(opcode, dest, left, right)
 Define a bytecode operation. More...
 
#define WEIERSTRASS_OPCODE(op)   ( ( (op) >> 12 ) & 0xf )
 Extract bytecode operation code. More...
 
#define WEIERSTRASS_DEST(op)   ( ( (op) >> 8 ) & 0xf )
 Extract destination big integer register. More...
 
#define WEIERSTRASS_LEFT(op)   ( ( (op) >> 4 ) & 0xf )
 Extract left source big integer register. More...
 
#define WEIERSTRASS_RIGHT(op)   ( ( (op) >> 0 ) & 0xf )
 Extract right source big integer register. More...
 
#define WEIERSTRASS_ADD3(dest, augend, addend)   WEIERSTRASS_OP ( WEIERSTRASS_OP_ADD, dest, augend, addend )
 Define a three-argument addition operation. More...
 
#define WEIERSTRASS_ADD2(augend, addend)   WEIERSTRASS_ADD3 ( augend, augend, addend )
 Define a two-argument addition operation. More...
 
#define WEIERSTRASS_MOV(dest, source)   WEIERSTRASS_ADD3( dest, source, zero )
 Define a move operation. More...
 
#define WEIERSTRASS_SUB3(dest, minuend, subtrahend, multiple)
 Define a three-argument subtraction operation. More...
 
#define WEIERSTRASS_SUB2(minuend, subtrahend, multiple)   WEIERSTRASS_SUB3 ( minuend, minuend, subtrahend, multiple )
 Define a two-argument subtraction operation. More...
 
#define WEIERSTRASS_STOP   WEIERSTRASS_SUB2 ( zero, zero, 0N )
 Define a stop operation. More...
 
#define WEIERSTRASS_MUL3(dest, multiplicand, multiplier)   WEIERSTRASS_OP ( WEIERSTRASS_OP_MUL, dest, multiplicand, multiplier )
 Define a three-argument multiplication operation. More...
 
#define WEIERSTRASS_MUL2(multiplicand, multiplier)   WEIERSTRASS_MUL3 ( multiplicand, multiplicand, multiplier )
 Define a two-argument multiplication operation. More...
 
#define weierstrass_add(curve, augend, addend, result)
 Add points on curve. More...
 
#define weierstrass_verify(curve, point)
 Verify point is on curve. More...
 

Enumerations

enum  weierstrass_register {
  WEIERSTRASS_a = 0, WEIERSTRASS_3b, WEIERSTRASS_x1, WEIERSTRASS_y1,
  WEIERSTRASS_z1, WEIERSTRASS_x2, WEIERSTRASS_y2, WEIERSTRASS_z2,
  WEIERSTRASS_Wt, WEIERSTRASS_Wxy, WEIERSTRASS_Wyz, WEIERSTRASS_Wzx,
  WEIERSTRASS_Wp, WEIERSTRASS_x3, WEIERSTRASS_y3, WEIERSTRASS_z3,
  WEIERSTRASS_NUM_REGISTERS = 16
}
 Big integer register names. More...
 
enum  weierstrass_opcode {
  WEIERSTRASS_OP_SUB_0N = 0, WEIERSTRASS_OP_SUB_2N = WEIERSTRASS_2N, WEIERSTRASS_OP_SUB_4N = WEIERSTRASS_4N, WEIERSTRASS_OP_ADD,
  WEIERSTRASS_OP_MUL
}
 Bytecode operation codes. More...
 

Functions

 FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
 
static void weierstrass_init (struct weierstrass_curve *curve)
 Initialise curve. More...
 
static void weierstrass_exec (const struct weierstrass_curve *curve, void **regs, unsigned int size, unsigned int op)
 Execute bytecode instruction. More...
 
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. More...
 
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. More...
 
static int weierstrass_verify_raw (const struct weierstrass_curve *curve, const bigint_element_t *point0)
 Verify point is on curve. More...
 
int weierstrass_multiply (struct weierstrass_curve *curve, const void *base, const void *scalar, void *result)
 Multiply curve point by scalar. More...
 

Detailed Description

Weierstrass elliptic curves.

The implementation is based upon Algorithm 1 from "Complete addition formulas for prime order elliptic curves" (Joost Renes, Craig Costello, and Lejla Batina), available from

https://www.microsoft.com/en-us/research/wp-content/uploads/2016/06/complete-2.pdf

The steps within the algorithm have been reordered and temporary variables shuffled to reduce stack usage, and calculations are carried out modulo small multiples of the field prime in order to elide reductions after intermediate addition and subtraction operations.

The algorithm is encoded using a bytecode representation, since this substantially reduces the code size compared to direct implementation of the big integer operations.

Definition in file weierstrass.c.

Macro Definition Documentation

◆ WEIERSTRASS_zero

#define WEIERSTRASS_zero   WEIERSTRASS_a

Zero register (for add/subtract operations.

Definition at line 91 of file weierstrass.c.

◆ WEIERSTRASS_REGISTER

#define WEIERSTRASS_REGISTER (   name)    _C2 ( WEIERSTRASS_, name )

Construct big integer register index.

Definition at line 94 of file weierstrass.c.

◆ WEIERSTRASS_OP

#define WEIERSTRASS_OP (   opcode,
  dest,
  left,
  right 
)
Value:
( ( (opcode) << 12 ) | \
( WEIERSTRASS_REGISTER ( dest ) << 8 ) | \
( WEIERSTRASS_REGISTER ( left ) << 4 ) | \
( WEIERSTRASS_REGISTER ( right ) << 0 ) )
opcode
uint8_t opcode
Opcode.
Definition: ena.h:16
WEIERSTRASS_REGISTER
#define WEIERSTRASS_REGISTER(name)
Construct big integer register index.
Definition: weierstrass.c:94
dest
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 a bytecode operation.

Parameters
opcodeOperation code
destDestination big integer register name
leftLeft source big integer register name
rightRight source big integer register name

Definition at line 118 of file weierstrass.c.

◆ WEIERSTRASS_OPCODE

#define WEIERSTRASS_OPCODE (   op)    ( ( (op) >> 12 ) & 0xf )

Extract bytecode operation code.

Definition at line 125 of file weierstrass.c.

◆ WEIERSTRASS_DEST

#define WEIERSTRASS_DEST (   op)    ( ( (op) >> 8 ) & 0xf )

Extract destination big integer register.

Definition at line 128 of file weierstrass.c.

◆ WEIERSTRASS_LEFT

#define WEIERSTRASS_LEFT (   op)    ( ( (op) >> 4 ) & 0xf )

Extract left source big integer register.

Definition at line 131 of file weierstrass.c.

◆ WEIERSTRASS_RIGHT

#define WEIERSTRASS_RIGHT (   op)    ( ( (op) >> 0 ) & 0xf )

Extract right source big integer register.

Definition at line 134 of file weierstrass.c.

◆ WEIERSTRASS_ADD3

#define WEIERSTRASS_ADD3 (   dest,
  augend,
  addend 
)    WEIERSTRASS_OP ( WEIERSTRASS_OP_ADD, dest, augend, addend )

Define a three-argument addition operation.

Definition at line 137 of file weierstrass.c.

◆ WEIERSTRASS_ADD2

#define WEIERSTRASS_ADD2 (   augend,
  addend 
)    WEIERSTRASS_ADD3 ( augend, augend, addend )

Define a two-argument addition operation.

Definition at line 141 of file weierstrass.c.

◆ WEIERSTRASS_MOV

#define WEIERSTRASS_MOV (   dest,
  source 
)    WEIERSTRASS_ADD3( dest, source, zero )

Define a move operation.

Definition at line 145 of file weierstrass.c.

◆ WEIERSTRASS_SUB3

#define WEIERSTRASS_SUB3 (   dest,
  minuend,
  subtrahend,
  multiple 
)
Value:
WEIERSTRASS_OP ( _C2 ( WEIERSTRASS_OP_SUB_, multiple ), \
dest, minuend, subtrahend )
WEIERSTRASS_OP
#define WEIERSTRASS_OP(opcode, dest, left, right)
Define a bytecode operation.
Definition: weierstrass.c:118
dest
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
_C2
EFI_SYSTEM_TABLE * _C2(PLATFORM, _systab)
System table passed to entry point.
subtrahend
static __always_inline off_t userptr_t subtrahend
Definition: librm.h:147

Define a three-argument subtraction operation.

Definition at line 149 of file weierstrass.c.

◆ WEIERSTRASS_SUB2

#define WEIERSTRASS_SUB2 (   minuend,
  subtrahend,
  multiple 
)    WEIERSTRASS_SUB3 ( minuend, minuend, subtrahend, multiple )

Define a two-argument subtraction operation.

Definition at line 154 of file weierstrass.c.

◆ WEIERSTRASS_STOP

#define WEIERSTRASS_STOP   WEIERSTRASS_SUB2 ( zero, zero, 0N )

Define a stop operation.

Definition at line 158 of file weierstrass.c.

◆ WEIERSTRASS_MUL3

#define WEIERSTRASS_MUL3 (   dest,
  multiplicand,
  multiplier 
)    WEIERSTRASS_OP ( WEIERSTRASS_OP_MUL, dest, multiplicand, multiplier )

Define a three-argument multiplication operation.

Definition at line 161 of file weierstrass.c.

◆ WEIERSTRASS_MUL2

#define WEIERSTRASS_MUL2 (   multiplicand,
  multiplier 
)    WEIERSTRASS_MUL3 ( multiplicand, multiplicand, multiplier )

Define a two-argument multiplication operation.

Definition at line 165 of file weierstrass.c.

◆ weierstrass_add

#define weierstrass_add (   curve,
  augend,
  addend,
  result 
)
Value:
do { \
weierstrass_add_raw ( (curve), (augend)->all.element, \
(addend)->all.element, \
(result)->all.element ); \
} while ( 0 )
result
uint16_t result
Definition: hyperv.h:33

Add points on curve.

Parameters
curveWeierstrass curve
augendPoint (x1,y1,z1) to be added
addendPoint (x2,y2,z2) to be added
result0Point (x3,y3,z3) to hold result

Definition at line 629 of file weierstrass.c.

◆ weierstrass_verify

#define weierstrass_verify (   curve,
  point 
)
Value:
( { \
weierstrass_verify_raw ( (curve), (point)->all.element ); \
} )

Verify point is on curve.

Parameters
curveWeierstrass curve
pointPoint (x,y,z) to be verified
Return values
rcReturn status code

Definition at line 757 of file weierstrass.c.

Enumeration Type Documentation

◆ weierstrass_register

enum weierstrass_register

Big integer register names.

Enumerator
WEIERSTRASS_a 
WEIERSTRASS_3b 
WEIERSTRASS_x1 
WEIERSTRASS_y1 
WEIERSTRASS_z1 
WEIERSTRASS_x2 
WEIERSTRASS_y2 
WEIERSTRASS_z2 
WEIERSTRASS_Wt 
WEIERSTRASS_Wxy 
WEIERSTRASS_Wyz 
WEIERSTRASS_Wzx 
WEIERSTRASS_Wp 
WEIERSTRASS_x3 
WEIERSTRASS_y3 
WEIERSTRASS_z3 
WEIERSTRASS_NUM_REGISTERS 

Definition at line 51 of file weierstrass.c.

51  {
52 
53  /*
54  * Read-only registers
55  */
56 
57  /* Curve constant "a" (for multiply), zero (for add/subtract) */
58  WEIERSTRASS_a = 0,
59  /* Curve constant "3b" */
60  WEIERSTRASS_3b,
61  /* Augend (x,y,z) co-ordinates */
62  WEIERSTRASS_x1,
63  WEIERSTRASS_y1,
64  WEIERSTRASS_z1,
65  /* Addend (x,y,z) co-ordinates */
66  WEIERSTRASS_x2,
67  WEIERSTRASS_y2,
68  WEIERSTRASS_z2,
69 
70  /*
71  * Read-write registers
72  */
73 
74  /* Temporary working registers */
75  WEIERSTRASS_Wt,
76  WEIERSTRASS_Wxy,
77  WEIERSTRASS_Wyz,
78  WEIERSTRASS_Wzx,
79  /* Low half of multiplication product */
80  WEIERSTRASS_Wp,
81  /* Result (x,y,z) co-ordinates */
82  WEIERSTRASS_x3,
83  WEIERSTRASS_y3,
84  WEIERSTRASS_z3,
85 
86  /* Number of registers */
87  WEIERSTRASS_NUM_REGISTERS = 16
88 };

◆ weierstrass_opcode

enum weierstrass_opcode

Bytecode operation codes.

Enumerator
WEIERSTRASS_OP_SUB_0N 

Subtract big integers (and add nothing)

WEIERSTRASS_OP_SUB_2N 

Subtract big integers (and add 2N)

WEIERSTRASS_OP_SUB_4N 

Subtract big integers (and add 4N)

WEIERSTRASS_OP_ADD 

Add big integers.

WEIERSTRASS_OP_MUL 

Multiply big integers (and perform Montgomery reduction)

Definition at line 97 of file weierstrass.c.

97  {
98  /** Subtract big integers (and add nothing)*/
99  WEIERSTRASS_OP_SUB_0N = 0,
100  /** Subtract big integers (and add 2N) */
101  WEIERSTRASS_OP_SUB_2N = WEIERSTRASS_2N,
102  /** Subtract big integers (and add 4N) */
103  WEIERSTRASS_OP_SUB_4N = WEIERSTRASS_4N,
104  /** Add big integers */
105  WEIERSTRASS_OP_ADD,
106  /** Multiply big integers (and perform Montgomery reduction) */
107  WEIERSTRASS_OP_MUL,
108 };
WEIERSTRASS_OP_ADD
Add big integers.
Definition: weierstrass.c:105
WEIERSTRASS_OP_SUB_2N
Subtract big integers (and add 2N)
Definition: weierstrass.c:101
WEIERSTRASS_OP_SUB_0N
Subtract big integers (and add nothing)
Definition: weierstrass.c:99
WEIERSTRASS_OP_MUL
Multiply big integers (and perform Montgomery reduction)
Definition: weierstrass.c:107
WEIERSTRASS_OP_SUB_4N
Subtract big integers (and add 4N)
Definition: weierstrass.c:103

Function Documentation

◆ FILE_LICENCE()

FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL  )

◆ weierstrass_init()

static void weierstrass_init ( struct weierstrass_curve *  curve)
static

Initialise curve.

Parameters
curveWeierstrass curve

Definition at line 173 of file weierstrass.c.

173  {
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 }
__attribute__
#define __attribute__(x)
Definition: compiler.h:10
weierstrass_curve::square
bigint_element_t * square
Cached Montgomery constant (R^2 mod N)
Definition: weierstrass.h:111
weierstrass_curve::prime
bigint_element_t * prime[WEIERSTRASS_NUM_CACHED]
Cached field prime "N" (and multiples thereof)
Definition: weierstrass.h:107
size
uint8_t size
Entry size (in 32-bit words)
Definition: ena.h:16
weierstrass_curve::mont
bigint_element_t * mont[WEIERSTRASS_NUM_MONT]
Definition: weierstrass.h:122
DBGC
#define DBGC(...)
Definition: compiler.h:505
bigint_init
#define bigint_init(value, data, len)
Initialise big integer.
Definition: bigint.h:61
weierstrass_curve::b3
bigint_element_t * b3
Cached constant "3b", in Montgomery form.
Definition: weierstrass.h:120
bigint_copy
#define bigint_copy(source, dest)
Copy big integer.
Definition: bigint.h:234
weierstrass_curve::fermat
bigint_element_t * fermat
Cached constant "N-2" (for Fermat's little theorem)
Definition: weierstrass.h:109
weierstrass_curve::b_raw
const uint8_t * b_raw
Constant "b".
Definition: weierstrass.h:102
weierstrass_curve::a
bigint_element_t * a
Cached constant "a", in Montgomery form.
Definition: weierstrass.h:118
WEIERSTRASS_NUM_MONT
#define WEIERSTRASS_NUM_MONT
Number of cached in Montgomery form for each Weierstrass curve.
Definition: weierstrass.h:77
weierstrass_curve::name
const char * name
Curve name.
Definition: weierstrass.h:94
uint8_t
unsigned char uint8_t
Definition: stdint.h:10
weierstrass_curve::len
size_t len
Length of raw scalar values.
Definition: weierstrass.h:96
weierstrass_curve::one
bigint_element_t * one
Cached constant "1", in Montgomery form.
Definition: weierstrass.h:116
bigint_montgomery
#define bigint_montgomery(modulus, value, result)
Perform classic Montgomery reduction (REDC) of a big integer.
Definition: bigint.h:313
bigint_multiply
#define bigint_multiply(multiplicand, multiplier, result)
Multiply big integers.
Definition: bigint.h:259
bigint_reduce
#define bigint_reduce(modulus, result)
Reduce big integer R^2 modulo N.
Definition: bigint.h:273
product
uint8_t product
Product string.
Definition: smbios.h:16
weierstrass_curve::size
const unsigned int size
Number of elements in scalar values.
Definition: weierstrass.h:92
bigint_subtract
#define bigint_subtract(subtrahend, value)
Subtract big integers.
Definition: bigint.h:98
bigint_add
#define bigint_add(addend, value)
Add big integers.
Definition: bigint.h:86
bigint_ntoa
#define bigint_ntoa(value)
Transcribe big integer (for debugging)
Definition: bigint.h:49
len
uint32_t len
Length.
Definition: ena.h:14
weierstrass_curve::prime_raw
const uint8_t * prime_raw
Field prime.
Definition: weierstrass.h:98
bigint_t
typedef bigint_t(X25519_SIZE) x25519_t
An X25519 unsigned big integer used in internal calculations.
weierstrass_curve::a_raw
const uint8_t * a_raw
Constant "a".
Definition: weierstrass.h:100

References __attribute__, weierstrass_curve::a, weierstrass_curve::a_raw, weierstrass_curve::b3, weierstrass_curve::b_raw, bigint_add, bigint_copy, bigint_init, bigint_montgomery, bigint_multiply, bigint_ntoa, bigint_reduce, bigint_subtract, bigint_t(), DBGC, weierstrass_curve::fermat, len, weierstrass_curve::len, weierstrass_curve::mont, weierstrass_curve::name, weierstrass_curve::one, weierstrass_curve::prime, weierstrass_curve::prime_raw, product, size, weierstrass_curve::size, weierstrass_curve::square, WEIERSTRASS_NUM_MONT, and WEIERSTRASS_NUM_MULTIPLES.

Referenced by weierstrass_multiply().

◆ weierstrass_exec()

static void weierstrass_exec ( const struct weierstrass_curve *  curve,
void **  regs,
unsigned int  size,
unsigned int  op 
)
static

Execute bytecode instruction.

Parameters
curveWeierstrass curve
regsRegisters
sizeBig integer size
opOperation

Definition at line 267 of file weierstrass.c.

269  {
270  const bigint_t ( size ) __attribute__ (( may_alias ))
271  *prime = ( ( const void * ) curve->prime[0] );
272  bigint_t ( size * 2 ) __attribute__ (( may_alias ))
273  *product = regs[WEIERSTRASS_Wp];
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 );
301  bigint_montgomery_relaxed ( prime, product, dest );
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 )
343  bigint_subtract ( subtrahend, dest );
344  DBGCP ( curve, "%s\n", bigint_ntoa ( dest ) );
345 }
__attribute__
#define __attribute__(x)
Definition: compiler.h:10
WEIERSTRASS_RIGHT
#define WEIERSTRASS_RIGHT(op)
Extract right source big integer register.
Definition: weierstrass.c:134
weierstrass_curve::prime
bigint_element_t * prime[WEIERSTRASS_NUM_CACHED]
Cached field prime "N" (and multiples thereof)
Definition: weierstrass.h:107
size
uint8_t size
Entry size (in 32-bit words)
Definition: ena.h:16
WEIERSTRASS_OPCODE
#define WEIERSTRASS_OPCODE(op)
Extract bytecode operation code.
Definition: weierstrass.c:125
bigint_montgomery_relaxed
#define bigint_montgomery_relaxed(modulus, value, result)
Perform relaxed Montgomery reduction (REDC) of a big integer.
Definition: bigint.h:299
WEIERSTRASS_OP_ADD
Add big integers.
Definition: weierstrass.c:105
assert
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
bigint_copy
#define bigint_copy(source, dest)
Copy big integer.
Definition: bigint.h:234
weierstrass_curve::name
const char * name
Curve name.
Definition: weierstrass.h:94
regs
struct i386_regs regs
Definition: registers.h:15
WEIERSTRASS_OP_SUB_0N
Subtract big integers (and add nothing)
Definition: weierstrass.c:99
op
static uint16_t struct vmbus_xfer_pages_operations * op
Definition: netvsc.h:327
bigint_multiply
#define bigint_multiply(multiplicand, multiplier, result)
Multiply big integers.
Definition: bigint.h:259
dest
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
DBGCP
#define DBGCP(...)
Definition: compiler.h:539
product
uint8_t product
Product string.
Definition: smbios.h:16
WEIERSTRASS_LEFT
#define WEIERSTRASS_LEFT(op)
Extract left source big integer register.
Definition: weierstrass.c:131
WEIERSTRASS_DEST
#define WEIERSTRASS_DEST(op)
Extract destination big integer register.
Definition: weierstrass.c:128
WEIERSTRASS_OP_MUL
Multiply big integers (and perform Montgomery reduction)
Definition: weierstrass.c:107
subtrahend
static __always_inline off_t userptr_t subtrahend
Definition: librm.h:147
bigint_subtract
#define bigint_subtract(subtrahend, value)
Subtract big integers.
Definition: bigint.h:98
bigint_add
#define bigint_add(addend, value)
Add big integers.
Definition: bigint.h:86
bigint_ntoa
#define bigint_ntoa(value)
Transcribe big integer (for debugging)
Definition: bigint.h:49
NULL
#define NULL
NULL pointer (VOID *)
Definition: Base.h:321
bigint_t
typedef bigint_t(X25519_SIZE) x25519_t
An X25519 unsigned big integer used in internal calculations.

References __attribute__, assert(), bigint_add, bigint_copy, bigint_montgomery_relaxed, bigint_multiply, bigint_ntoa, bigint_subtract, bigint_t(), DBGCP, dest, weierstrass_curve::name, NULL, op, weierstrass_curve::prime, product, regs, size, subtrahend, WEIERSTRASS_DEST, WEIERSTRASS_LEFT, WEIERSTRASS_OP_ADD, WEIERSTRASS_OP_MUL, WEIERSTRASS_OP_SUB_0N, WEIERSTRASS_OPCODE, WEIERSTRASS_RIGHT, WEIERSTRASS_Wp, and WEIERSTRASS_Wt.

Referenced by weierstrass_add_raw(), and weierstrass_verify_raw().

◆ weierstrass_add_raw()

static void weierstrass_add_raw ( const struct weierstrass_curve *  curve,
const bigint_element_t *  augend0,
const bigint_element_t *  addend0,
bigint_element_t *  result0 
)
static

Add points on curve.

Parameters
curveWeierstrass curve
augend0Element 0 of point (x1,y1,z1) to be added
addend0Element 0 of point (x2,y2,z2) to be added
result0Element 0 of point (x3,y3,z3) to hold result

Points are represented in projective coordinates, with all values in Montgomery form and in the range [0,4N) where N is the field prime.

The augend may have the same value as the addend (i.e. this routine may be used to perform point doubling as well as point addition), and either or both may be the point at infinity.

The result may overlap either input, since the inputs are fully consumed before the result is written.

Definition at line 366 of file weierstrass.c.

369  {
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;
390  void *regs[WEIERSTRASS_NUM_REGISTERS];
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 */
564  WEIERSTRASS_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 }
__attribute__
#define __attribute__(x)
Definition: compiler.h:10
uint16_t
unsigned short uint16_t
Definition: stdint.h:11
WEIERSTRASS_STOP
#define WEIERSTRASS_STOP
Define a stop operation.
Definition: weierstrass.c:158
weierstrass_curve::prime
bigint_element_t * prime[WEIERSTRASS_NUM_CACHED]
Cached field prime "N" (and multiples thereof)
Definition: weierstrass.h:107
weierstrass_exec
static void weierstrass_exec(const struct weierstrass_curve *curve, void **regs, unsigned int size, unsigned int op)
Execute bytecode instruction.
Definition: weierstrass.c:267
size
uint8_t size
Entry size (in 32-bit words)
Definition: ena.h:16
weierstrass_curve::b3
bigint_element_t * b3
Cached constant "3b", in Montgomery form.
Definition: weierstrass.h:120
WEIERSTRASS_MOV
#define WEIERSTRASS_MOV(dest, source)
Define a move operation.
Definition: weierstrass.c:145
assert
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
weierstrass_t
#define weierstrass_t(size)
Define a Weierstrass projective co-ordinate type.
Definition: weierstrass.h:57
WEIERSTRASS_MUL3
#define WEIERSTRASS_MUL3(dest, multiplicand, multiplier)
Define a three-argument multiplication operation.
Definition: weierstrass.c:161
weierstrass_curve::a
bigint_element_t * a
Cached constant "a", in Montgomery form.
Definition: weierstrass.h:118
weierstrass_curve::name
const char * name
Curve name.
Definition: weierstrass.h:94
WEIERSTRASS_SUB2
#define WEIERSTRASS_SUB2(minuend, subtrahend, multiple)
Define a two-argument subtraction operation.
Definition: weierstrass.c:154
regs
struct i386_regs regs
Definition: registers.h:15
result
uint16_t result
Definition: hyperv.h:33
op
static uint16_t struct vmbus_xfer_pages_operations * op
Definition: netvsc.h:327
DBGC2
#define DBGC2(...)
Definition: compiler.h:522
WEIERSTRASS_MUL2
#define WEIERSTRASS_MUL2(multiplicand, multiplier)
Define a two-argument multiplication operation.
Definition: weierstrass.c:165
weierstrass_curve::size
const unsigned int size
Number of elements in scalar values.
Definition: weierstrass.h:92
WEIERSTRASS_ADD3
#define WEIERSTRASS_ADD3(dest, augend, addend)
Define a three-argument addition operation.
Definition: weierstrass.c:137
bigint_ntoa
#define bigint_ntoa(value)
Transcribe big integer (for debugging)
Definition: bigint.h:49
WEIERSTRASS_ADD2
#define WEIERSTRASS_ADD2(augend, addend)
Define a two-argument addition operation.
Definition: weierstrass.c:141
bigint_t
typedef bigint_t(X25519_SIZE) x25519_t
An X25519 unsigned big integer used in internal calculations.

References __attribute__, weierstrass_curve::a, assert(), weierstrass_curve::b3, bigint_ntoa, bigint_t(), DBGC2, weierstrass_curve::name, op, weierstrass_curve::prime, regs, result, size, weierstrass_curve::size, WEIERSTRASS_3b, WEIERSTRASS_a, WEIERSTRASS_ADD2, WEIERSTRASS_ADD3, weierstrass_exec(), WEIERSTRASS_MOV, WEIERSTRASS_MUL2, WEIERSTRASS_MUL3, WEIERSTRASS_NUM_REGISTERS, WEIERSTRASS_STOP, WEIERSTRASS_SUB2, weierstrass_t, WEIERSTRASS_Wp, WEIERSTRASS_Wt, WEIERSTRASS_Wxy, WEIERSTRASS_Wyz, WEIERSTRASS_Wzx, WEIERSTRASS_x1, WEIERSTRASS_x2, WEIERSTRASS_x3, WEIERSTRASS_y1, WEIERSTRASS_y2, WEIERSTRASS_y3, WEIERSTRASS_z1, WEIERSTRASS_z2, and WEIERSTRASS_z3.

◆ weierstrass_add_ladder()

static void weierstrass_add_ladder ( const bigint_element_t *  operand0,
bigint_element_t *  result0,
unsigned int  size,
const void *  ctx,
void *tmp  __unused 
)
static

Add points on curve as part of a Montgomery ladder.

Parameters
operandElement 0 of first input operand (may overlap result)
resultElement 0 of second input operand and result
sizeNumber of elements in operands and result
ctxOperation context
tmpTemporary working space (not used)

Definition at line 644 of file weierstrass.c.

647  {
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 }
size
uint8_t size
Entry size (in 32-bit words)
Definition: ena.h:16
ctx
struct golan_eq_context ctx
Definition: CIB_PRM.h:28
weierstrass_add
#define weierstrass_add(curve, augend, addend, result)
Add points on curve.
Definition: weierstrass.c:629
assert
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
weierstrass_t
#define weierstrass_t(size)
Define a Weierstrass projective co-ordinate type.
Definition: weierstrass.h:57
__attribute__
A 16-bit general register.
Definition: registers.h:24
result
uint16_t result
Definition: hyperv.h:33
bigint_size
#define bigint_size(bigint)
Determine number of elements in big-integer type.
Definition: bigint.h:40
weierstrass_curve::size
const unsigned int size
Number of elements in scalar values.
Definition: weierstrass.h:92
weierstrass_curve
A Weierstrass elliptic curve.
Definition: weierstrass.h:90

References __attribute__, assert(), bigint_size, ctx, result, size, weierstrass_curve::size, weierstrass_add, and weierstrass_t.

Referenced by weierstrass_multiply().

◆ weierstrass_verify_raw()

static int weierstrass_verify_raw ( const struct weierstrass_curve *  curve,
const bigint_element_t *  point0 
)
static

Verify point is on curve.

Parameters
curveWeierstrass curve
point0Element 0 of point (x,y,z) to be verified
Return values
rcReturn status code

As with point addition, points are represented in projective coordinates, with all values in Montgomery form and in the range [0,4N) where N is the field prime.

Definition at line 671 of file weierstrass.c.

672  {
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;
686  void *regs[WEIERSTRASS_NUM_REGISTERS];
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 */
723  WEIERSTRASS_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 }
__attribute__
#define __attribute__(x)
Definition: compiler.h:10
EINVAL
#define EINVAL
Invalid argument.
Definition: errno.h:428
uint16_t
unsigned short uint16_t
Definition: stdint.h:11
WEIERSTRASS_STOP
#define WEIERSTRASS_STOP
Define a stop operation.
Definition: weierstrass.c:158
weierstrass_curve::prime
bigint_element_t * prime[WEIERSTRASS_NUM_CACHED]
Cached field prime "N" (and multiples thereof)
Definition: weierstrass.h:107
weierstrass_exec
static void weierstrass_exec(const struct weierstrass_curve *curve, void **regs, unsigned int size, unsigned int op)
Execute bytecode instruction.
Definition: weierstrass.c:267
size
uint8_t size
Entry size (in 32-bit words)
Definition: ena.h:16
DBGC
#define DBGC(...)
Definition: compiler.h:505
bigint_grow
#define bigint_grow(source, dest)
Grow big integer.
Definition: bigint.h:208
bigint_is_zero
#define bigint_is_zero(value)
Test if big integer is equal to zero.
Definition: bigint.h:133
weierstrass_curve::b3
bigint_element_t * b3
Cached constant "3b", in Montgomery form.
Definition: weierstrass.h:120
WEIERSTRASS_MOV
#define WEIERSTRASS_MOV(dest, source)
Define a move operation.
Definition: weierstrass.c:145
weierstrass_t
#define weierstrass_t(size)
Define a Weierstrass projective co-ordinate type.
Definition: weierstrass.h:57
WEIERSTRASS_MUL3
#define WEIERSTRASS_MUL3(dest, multiplicand, multiplier)
Define a three-argument multiplication operation.
Definition: weierstrass.c:161
weierstrass_curve::a
bigint_element_t * a
Cached constant "a", in Montgomery form.
Definition: weierstrass.h:118
weierstrass_curve::name
const char * name
Curve name.
Definition: weierstrass.h:94
WEIERSTRASS_SUB2
#define WEIERSTRASS_SUB2(minuend, subtrahend, multiple)
Define a two-argument subtraction operation.
Definition: weierstrass.c:154
regs
struct i386_regs regs
Definition: registers.h:15
op
static uint16_t struct vmbus_xfer_pages_operations * op
Definition: netvsc.h:327
bigint_montgomery
#define bigint_montgomery(modulus, value, result)
Perform classic Montgomery reduction (REDC) of a big integer.
Definition: bigint.h:313
WEIERSTRASS_MUL2
#define WEIERSTRASS_MUL2(multiplicand, multiplier)
Define a two-argument multiplication operation.
Definition: weierstrass.c:165
weierstrass_curve::size
const unsigned int size
Number of elements in scalar values.
Definition: weierstrass.h:92
WEIERSTRASS_ADD3
#define WEIERSTRASS_ADD3(dest, augend, addend)
Define a three-argument addition operation.
Definition: weierstrass.c:137
WEIERSTRASS_ADD2
#define WEIERSTRASS_ADD2(augend, addend)
Define a two-argument addition operation.
Definition: weierstrass.c:141
bigint_t
typedef bigint_t(X25519_SIZE) x25519_t
An X25519 unsigned big integer used in internal calculations.

References __attribute__, weierstrass_curve::a, weierstrass_curve::b3, bigint_grow, bigint_is_zero, bigint_montgomery, bigint_t(), DBGC, EINVAL, weierstrass_curve::name, op, weierstrass_curve::prime, regs, size, weierstrass_curve::size, WEIERSTRASS_3b, WEIERSTRASS_a, WEIERSTRASS_ADD2, WEIERSTRASS_ADD3, weierstrass_exec(), WEIERSTRASS_MOV, WEIERSTRASS_MUL2, WEIERSTRASS_MUL3, WEIERSTRASS_NUM_REGISTERS, WEIERSTRASS_STOP, WEIERSTRASS_SUB2, weierstrass_t, WEIERSTRASS_Wp, WEIERSTRASS_Wt, WEIERSTRASS_x1, and WEIERSTRASS_y1.

◆ weierstrass_multiply()

int weierstrass_multiply ( struct weierstrass_curve *  curve,
const void *  base,
const void *  scalar,
void *  result 
)

Multiply curve point by scalar.

Parameters
curveWeierstrass curve
baseBase point (or NULL to use generator)
scalarScalar multiple
resultResult point to fill in
Return values
rcReturn status code

Definition at line 770 of file weierstrass.c.

771  {
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 {
786  weierstrass_t ( size ) result;
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 }
__attribute__
#define __attribute__(x)
Definition: compiler.h:10
base
uint32_t base
Base.
Definition: librm.h:252
rc
struct arbelprm_rc_send_wqe rc
Definition: arbel.h:14
weierstrass_curve::base
const uint8_t * base
Base point.
Definition: weierstrass.h:104
weierstrass_curve::square
bigint_element_t * square
Cached Montgomery constant (R^2 mod N)
Definition: weierstrass.h:111
weierstrass_curve::prime
bigint_element_t * prime[WEIERSTRASS_NUM_CACHED]
Cached field prime "N" (and multiples thereof)
Definition: weierstrass.h:107
size
uint8_t size
Entry size (in 32-bit words)
Definition: ena.h:16
WEIERSTRASS_AXES
#define WEIERSTRASS_AXES
Number of axes in Weierstrass curve point representation.
Definition: weierstrass.h:16
DBGC
#define DBGC(...)
Definition: compiler.h:505
bigint_grow
#define bigint_grow(source, dest)
Grow big integer.
Definition: bigint.h:208
bigint_init
#define bigint_init(value, data, len)
Initialise big integer.
Definition: bigint.h:61
weierstrass_verify
#define weierstrass_verify(curve, point)
Verify point is on curve.
Definition: weierstrass.c:757
bigint_montgomery_relaxed
#define bigint_montgomery_relaxed(modulus, value, result)
Perform relaxed Montgomery reduction (REDC) of a big integer.
Definition: bigint.h:299
weierstrass_add_ladder
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
weierstrass_init
static void weierstrass_init(struct weierstrass_curve *curve)
Initialise curve.
Definition: weierstrass.c:173
weierstrass_t
#define weierstrass_t(size)
Define a Weierstrass projective co-ordinate type.
Definition: weierstrass.h:57
bigint_copy
#define bigint_copy(source, dest)
Copy big integer.
Definition: bigint.h:234
weierstrass_curve::fermat
bigint_element_t * fermat
Cached constant "N-2" (for Fermat's little theorem)
Definition: weierstrass.h:109
bigint_done
#define bigint_done(value, out, len)
Finalise big integer.
Definition: bigint.h:74
bigint_required_size
#define bigint_required_size(len)
Determine number of elements required for a big-integer type.
Definition: bigint.h:30
weierstrass_curve::name
const char * name
Curve name.
Definition: weierstrass.h:94
weierstrass_curve::len
size_t len
Length of raw scalar values.
Definition: weierstrass.h:96
weierstrass_curve::one
bigint_element_t * one
Cached constant "1", in Montgomery form.
Definition: weierstrass.h:116
result
uint16_t result
Definition: hyperv.h:33
bigint_montgomery
#define bigint_montgomery(modulus, value, result)
Perform classic Montgomery reduction (REDC) of a big integer.
Definition: bigint.h:313
bigint_multiply
#define bigint_multiply(multiplicand, multiplier, result)
Multiply big integers.
Definition: bigint.h:259
offset
uint16_t offset
Offset to command line.
Definition: bzimage.h:8
bigint_ladder
#define bigint_ladder(result, multiple, exponent, op, ctx, tmp)
Perform generalised exponentiation via a Montgomery ladder.
Definition: bigint.h:329
weierstrass_curve::size
const unsigned int size
Number of elements in scalar values.
Definition: weierstrass.h:92
bigint_ntoa
#define bigint_ntoa(value)
Transcribe big integer (for debugging)
Definition: bigint.h:49
len
uint32_t len
Length.
Definition: ena.h:14
NULL
#define NULL
NULL pointer (VOID *)
Definition: Base.h:321
bigint_t
typedef bigint_t(X25519_SIZE) x25519_t
An X25519 unsigned big integer used in internal calculations.
memset
void * memset(void *dest, int character, size_t len) __nonnull
bigint_mod_exp_ladder
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

References __attribute__, weierstrass_curve::base, base, bigint_copy, bigint_done, bigint_grow, bigint_init, bigint_ladder, bigint_mod_exp_ladder(), bigint_montgomery, bigint_montgomery_relaxed, bigint_multiply, bigint_ntoa, bigint_required_size, bigint_t(), DBGC, weierstrass_curve::fermat, len, weierstrass_curve::len, memset(), weierstrass_curve::name, NULL, offset, weierstrass_curve::one, weierstrass_curve::prime, rc, result, size, weierstrass_curve::size, weierstrass_curve::square, WEIERSTRASS_2N, weierstrass_add_ladder(), WEIERSTRASS_AXES, weierstrass_init(), weierstrass_t, and weierstrass_verify.

Generated by   doxygen 1.8.15