1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
#ifndef _IPXE_WEIERSTRASS_H
#define _IPXE_WEIERSTRASS_H
/** @file
*
* Weierstrass elliptic curves
*
*/
FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
#include <ipxe/bigint.h>
#include <ipxe/crypto.h>
/** Number of axes in Weierstrass curve point representation */
#define WEIERSTRASS_AXES 2
/**
* Maximum multiple of field prime encountered during calculations
*
* Calculations are performed using values modulo a small multiple of
* the field prime, rather than modulo the field prime itself. This
* allows explicit reductions after additions, subtractions, and
* relaxed Montgomery multiplications to be omitted entirely, provided
* that we keep careful track of the field prime multiple for each
* intermediate value.
*
* Relaxed Montgomery multiplication will produce a result in the
* range t < (1+m/k)N, where m is this maximum multiple of the field
* prime, and k is the constant in R > kN representing the leading
* zero padding in the big integer representation of the field prime.
* We choose to set k=m so that multiplications will always produce a
* result in the range t < 2N.
*
* This is expressed as the base-two logarithm of the multiple
* (rounded up), to simplify compile-time calculations.
*/
#define WEIERSTRASS_MAX_MULTIPLE_LOG2 5 /* maximum reached is mod 20N */
/**
* Determine number of elements in scalar values for a Weierstrass curve
*
* @v len Length of field prime, in bytes
* @ret size Number of elements
*/
#define weierstrass_size( len ) \
bigint_required_size ( (len) + \
( ( WEIERSTRASS_MAX_MULTIPLE_LOG2 + 7 ) \
/ 8 ) )
/**
* Define a Weierstrass projective co-ordinate type
*
* @v size Number of elements in scalar values
* @ret weierstrass_t Projective co-ordinate type
*/
#define weierstrass_t( size ) \
union { \
bigint_t ( size ) axis[3]; \
struct { \
bigint_t ( size ) x; \
bigint_t ( size ) y; \
bigint_t ( size ) z; \
}; \
bigint_t ( size * 3 ) all; \
}
/** Indexes for stored multiples of the field prime */
enum weierstrass_multiple {
WEIERSTRASS_N = 0,
WEIERSTRASS_2N,
WEIERSTRASS_4N,
WEIERSTRASS_NUM_MULTIPLES
};
/** Number of cached in Montgomery form for each Weierstrass curve */
#define WEIERSTRASS_NUM_MONT 3
/** Number of cached big integers for each Weierstrass curve */
#define WEIERSTRASS_NUM_CACHED \
( WEIERSTRASS_NUM_MULTIPLES + \
1 /* fermat */ + 1 /* mont */ + \
WEIERSTRASS_NUM_MONT )
/**
* A Weierstrass elliptic curve
*
* This is an elliptic curve y^2 = x^3 + ax + b
*/
struct weierstrass_curve {
/** Number of elements in scalar values */
const unsigned int size;
/** Curve name */
const char *name;
/** Length of raw scalar values */
size_t len;
/** Field prime */
const uint8_t *prime_raw;
/** Constant "a" */
const uint8_t *a_raw;
/** Constant "b" */
const uint8_t *b_raw;
/** Base point */
const uint8_t *base;
/** Cached field prime "N" (and multiples thereof) */
bigint_element_t *prime[WEIERSTRASS_NUM_CACHED];
/** Cached constant "N-2" (for Fermat's little theorem) */
bigint_element_t *fermat;
/** Cached Montgomery constant (R^2 mod N) */
bigint_element_t *square;
/** Cached constants in Montgomery form */
union {
struct {
/** Cached constant "1", in Montgomery form */
bigint_element_t *one;
/** Cached constant "a", in Montgomery form */
bigint_element_t *a;
/** Cached constant "3b", in Montgomery form */
bigint_element_t *b3;
};
bigint_element_t *mont[WEIERSTRASS_NUM_MONT];
};
};
extern int weierstrass_multiply ( struct weierstrass_curve *curve,
const void *base, const void *scalar,
void *result );
/** Define a Weierstrass curve */
#define WEIERSTRASS_CURVE( _name, _curve, _len, _prime, _a, _b, _base ) \
static bigint_t ( weierstrass_size(_len) ) \
_name ## _cache[WEIERSTRASS_NUM_CACHED]; \
static struct weierstrass_curve _name ## _weierstrass = { \
.size = weierstrass_size(_len), \
.name = #_name, \
.len = (_len), \
.prime_raw = (_prime), \
.a_raw = (_a), \
.b_raw = (_b), \
.base = (_base), \
.prime = { \
(_name ## _cache)[0].element, \
(_name ## _cache)[1].element, \
(_name ## _cache)[2].element, \
}, \
.fermat = (_name ## _cache)[3].element, \
.square = (_name ## _cache)[4].element, \
.one = (_name ## _cache)[5].element, \
.a = (_name ## _cache)[6].element, \
.b3 = (_name ## _cache)[7].element, \
}; \
static int _name ## _multiply ( const void *base, \
const void *scalar, \
void *result ) { \
return weierstrass_multiply ( &_name ## _weierstrass, \
base, scalar, result ); \
} \
struct elliptic_curve _curve = { \
.name = #_name, \
.pointsize = ( WEIERSTRASS_AXES * (_len) ), \
.keysize = (_len), \
.multiply = _name ## _multiply, \
}
#endif /* _IPXE_WEIERSTRASS_H */
|
