cryptlib  3.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Macros
kg_ecc.c
Go to the documentation of this file.
1 /****************************************************************************
2 * *
3 * cryptlib ECC Key Generation/Checking Routines *
4 * Copyright Peter Gutmann 2006-2008 *
5 * *
6 ****************************************************************************/
7 
8 #define PKC_CONTEXT /* Indicate that we're working with PKC contexts */
9 #if defined( INC_ALL )
10  #include "crypt.h"
11  #include "context.h"
12  #include "keygen.h"
13 #else
14  #include "crypt.h"
15  #include "context/context.h"
16  #include "context/keygen.h"
17 #endif /* Compiler-specific includes */
18 
19 #if defined( USE_ECDH ) || defined( USE_ECDSA )
20 
21 /****************************************************************************
22 * *
23 * Utility Functions *
24 * *
25 ****************************************************************************/
26 
27 /* Enable various side-channel protection mechanisms */
28 
29 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
30 static int enableSidechannelProtection( INOUT PKC_INFO *pkcInfo,
31  IN_ALGO const CRYPT_ALGO_TYPE cryptAlgo )
32  {
33  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
34 
35  REQUIRES( isEccAlgo( cryptAlgo ) );
36 
37  /* Use constant-time modexp() to protect the private key from timing
38  channels.
39 
40  (There really isn't much around in the way of side-channel protection
41  for the ECC computations, for every operation we use a new random
42  secret value as the point multiplier so there doesn't seem to be much
43  scope for timing attacks. In the absence of anything better to do,
44  we set the constant-time modexp() flag just for warm fuzzies) */
45  BN_set_flags( &pkcInfo->eccParam_d, BN_FLG_EXP_CONSTTIME );
46 
47  /* Checksum the bignums to try and detect fault attacks. Since we're
48  setting the checksum at this point there's no need to check the
49  return value */
50  ( void ) calculateBignumChecksum( pkcInfo, cryptAlgo );
51 
52  return( CRYPT_OK );
53  }
54 
55 /****************************************************************************
56 * *
57 * Fixed ECC Parameters *
58 * *
59 ****************************************************************************/
60 
61 /* We always use pre-generated parameters both because it's unlikely that
62  anyone will ever decide to generate nonstandard parameters when standard
63  ones are available (or at least no sane person would, no doubt every
64  little standards committee wanting to make their mark will feel the need
65  to have their own personal incompatible parameters). In addition using
66  externally-generated parameters can (as for DSA) lead to problems with
67  maliciously-generated values (see "CM-Curves with good Cryptography
68  Properties", Neal Koblitz, Proceedings of Crypto'91, p.279), and finally
69  (also like DSA) it can lead to problems with parameter-substitution
70  attacks (see "Digital Signature Schemes with Domain Parameters", Serge
71  Vaudenay, Proceedings of ACISP'04, p.188) */
72 
73 typedef struct {
74  CRYPT_ECCCURVE_TYPE paramType;
75  const int curveSizeBits;
76  const BYTE *p, *a, *b, *gx, *gy, *n, *h;
77  } ECC_DOMAIN_PARAMS;
78 
79 static const ECC_DOMAIN_PARAMS domainParamTbl[] = {
80  /* NIST P-192, X9.62 p192r1, SECG p192r1 */
81  { CRYPT_ECCCURVE_P192, 192,
82  MKDATA( "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
83  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFE" \
84  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" ),
85  MKDATA( "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
86  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFE" \
87  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFC" ),
88  MKDATA( "\x64\x21\x05\x19\xE5\x9C\x80\xE7" \
89  "\x0F\xA7\xE9\xAB\x72\x24\x30\x49" \
90  "\xFE\xB8\xDE\xEC\xC1\x46\xB9\xB1" ),
91  MKDATA( "\x18\x8D\xA8\x0E\xB0\x30\x90\xF6" \
92  "\x7C\xBF\x20\xEB\x43\xA1\x88\x00" \
93  "\xF4\xFF\x0A\xFD\x82\xFF\x10\x12" ),
94  MKDATA( "\x07\x19\x2B\x95\xFF\xC8\xDA\x78" \
95  "\x63\x10\x11\xED\x6B\x24\xCD\xD5" \
96  "\x73\xF9\x77\xA1\x1E\x79\x48\x11" ),
97  MKDATA( "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF"
98  "\xFF\xFF\xFF\xFF\x99\xDE\xF8\x36" \
99  "\x14\x6B\xC9\xB1\xB4\xD2\x28\x31" ),
100  MKDATA( "\x01" ) },
101 #if 0
102  /* X9.62 P192v2 */
103  { CRYPT_ECCCURVE_P192v2, 192,
104  MKDATA( "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
105  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFE" \
106  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" ),
107  MKDATA( "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
108  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFE" \
109  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFC" ),
110  MKDATA( "\xCC\x22\xD6\xDF\xB9\x5C\x6B\x25" \
111  "\xE4\x9C\x0D\x63\x64\xA4\xE5\x98" \
112  "\x0C\x39\x3A\xA2\x16\x68\xD9\x53" ),
113  MKDATA( "\xEE\xA2\xBA\xE7\xE1\x49\x78\x42" \
114  "\xF2\xDE\x77\x69\xCF\xE9\xC9\x89" \
115  "\xC0\x72\xAD\x69\x6F\x48\x03\x4A" ),
116  MKDATA( "\x65\x74\xD1\x1D\x69\xB6\xEC\x7A" \
117  "\x67\x2B\xB8\x2A\x08\x3D\xF2\xF2" \
118  "\xB0\x84\x7D\xE9\x70\xB2\xDE\x15" ),
119  MKDATA( "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
120  "\xFF\xFF\xFF\xFE\x5F\xB1\xA7\x24" \
121  "\xDC\x80\x41\x86\x48\xD8\xDD\x31" ) },
122  /* X9.62 P192v3 */
123  { CRYPT_ECCCURVE_P192v3, 192,
124  MKDATA( "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
125  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFE" \
126  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" ),
127  MKDATA( "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
128  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFE" \
129  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFC" ),
130  MKDATA( "\x22\x12\x3D\xC2\x39\x5A\x05\xCA" \
131  "\xA7\x42\x3D\xAE\xCC\xC9\x47\x60" \
132  "\xA7\xD4\x62\x25\x6B\xD5\x69\x16" ),
133  MKDATA( "\x7D\x29\x77\x81\x00\xC6\x5A\x1D" \
134  "\xA1\x78\x37\x16\x58\x8D\xCE\x2B" \
135  "\x8B\x4A\xEE\x8E\x22\x8F\x18\x96" ),
136  MKDATA( "\x38\xA9\x0F\x22\x63\x73\x37\x33" \
137  "\x4B\x49\xDC\xB6\x6A\x6D\xC8\xF9" \
138  "\x97\x8A\xCA\x76\x48\xA9\x43\xB0" ),
139  MKDATA( "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
140  "\xFF\xFF\xFF\xFF\x7A\x62\xD0\x31" \
141  "\xC8\x3F\x42\x94\xF6\x40\xEC\x13" ) },
142 #endif /* 0 */
143 
144  /* NIST P-224, X9.62 P224r1, SECG p224r1 */
145  { CRYPT_ECCCURVE_P224, 224,
146  MKDATA( "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
147  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
148  "\x00\x00\x00\x00\x00\x00\x00\x00" \
149  "\x00\x00\x00\x01" ),
150  MKDATA( "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
151  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFE" \
152  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
153  "\xFF\xFF\xFF\xFE" ),
154  MKDATA( "\xB4\x05\x0A\x85\x0C\x04\xB3\xAB" \
155  "\xF5\x41\x32\x56\x50\x44\xB0\xB7" \
156  "\xD7\xBF\xD8\xBA\x27\x0B\x39\x43" \
157  "\x23\x55\xFF\xB4" ),
158  MKDATA( "\xB7\x0E\x0C\xBD\x6B\xB4\xBF\x7F" \
159  "\x32\x13\x90\xB9\x4A\x03\xC1\xD3" \
160  "\x56\xC2\x11\x22\x34\x32\x80\xD6" \
161  "\x11\x5C\x1D\x21" ),
162  MKDATA( "\xBD\x37\x63\x88\xB5\xF7\x23\xFB" \
163  "\x4C\x22\xDF\xE6\xCD\x43\x75\xA0" \
164  "\x5A\x07\x47\x64\x44\xD5\x81\x99" \
165  "\x85\x00\x7E\x34" ),
166  MKDATA( "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
167  "\xFF\xFF\xFF\xFF\xFF\xFF\x16\xA2" \
168  "\xE0\xB8\xF0\x3E\x13\xDD\x29\x45" \
169  "\x5C\x5C\x2A\x3D" ),
170  MKDATA( "\x01" ) },
171 #if 0
172  /* X9.62 P239v1 */
173  { CRYPT_ECCCURVE_P239, 239,
174  MKDATA( "\x7F\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
175  "\xFF\xFF\xFF\xFF\x7F\xFF\xFF\xFF" \
176  "\xFF\xFF\x80\x00\x00\x00\x00\x00" \
177  "\x7F\xFF\xFF\xFF\xFF\xFF" ),
178  MKDATA( "\x7F\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
179  "\xFF\xFF\xFF\xFF\x7F\xFF\xFF\xFF" \
180  "\xFF\xFF\x80\x00\x00\x00\x00\x00" \
181  "\x7F\xFF\xFF\xFF\xFF\xFC" ),
182  MKDATA( "\x6B\x01\x6C\x3B\xDC\xF1\x89\x41" \
183  "\xD0\xD6\x54\x92\x14\x75\xCA\x71" \
184  "\xA9\xDB\x2F\xB2\x7D\x1D\x37\x79" \
185  "\x61\x85\xC2\x94\x2C\x0A" ),
186  MKDATA( "\x0F\xFA\x96\x3C\xDC\xA8\x81\x6C" \
187  "\xCC\x33\xB8\x64\x2B\xED\xF9\x05" \
188  "\xC3\xD3\x58\x57\x3D\x3F\x27\xFB" \
189  "\xBD\x3B\x3C\xB9\xAA\xAF" ),
190  MKDATA( "\x7D\xEB\xE8\xE4\xE9\x0A\x5D\xAE" \
191  "\x6E\x40\x54\xCA\x53\x0B\xA0\x46" \
192  "\x54\xB3\x68\x18\xCE\x22\x6B\x39" \
193  "\xFC\xCB\x7B\x02\xF1\xAE" ),
194  MKDATA( "\x7F\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
195  "\xFF\xFF\xFF\xFF\x7F\xFF\xFF\x9E" \
196  "\x5E\x9A\x9F\x5D\x90\x71\xFB\xD1" \
197  "\x52\x26\x88\x90\x9D\x0B" ) },
198  /* X9.62 P239v2 */
199  { CRYPT_ECCCURVE_P239v2, 239,
200  MKDATA( "\x7F\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
201  "\xFF\xFF\xFF\xFF\x7F\xFF\xFF\xFF" \
202  "\xFF\xFF\x80\x00\x00\x00\x00\x00" \
203  "\x7F\xFF\xFF\xFF\xFF\xFF" ),
204  MKDATA( "\x7F\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
205  "\xFF\xFF\xFF\xFF\x7F\xFF\xFF\xFF" \
206  "\xFF\xFF\x80\x00\x00\x00\x00\x00" \
207  "\x7F\xFF\xFF\xFF\xFF\xFC" ),
208  MKDATA( "\x61\x7F\xAB\x68\x32\x57\x6C\xBB" \
209  "\xFE\xD5\x0D\x99\xF0\x24\x9C\x3F" \
210  "\xEE\x58\xB9\x4B\xA0\x03\x8C\x7A" \
211  "\xE8\x4C\x8C\x83\x2F\x2C" ),
212  MKDATA( "\x38\xAF\x09\xD9\x87\x27\x70\x51" \
213  "\x20\xC9\x21\xBB\x5E\x9E\x26\x29" \
214  "\x6A\x3C\xDC\xF2\xF3\x57\x57\xA0" \
215  "\xEA\xFD\x87\xB8\x30\xE7" ),
216  MKDATA( "\x5B\x01\x25\xE4\xDB\xEA\x0E\xC7" \
217  "\x20\x6D\xA0\xFC\x01\xD9\xB0\x81" \
218  "\x32\x9F\xB5\x55\xDE\x6E\xF4\x60" \
219  "\x23\x7D\xFF\x8B\xE4\xBA" ),
220  MKDATA( "\x7F\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
221  "\xFF\xFF\xFF\xFF\x80\x00\x00\xCF" \
222  "\xA7\xE8\x59\x43\x77\xD4\x14\xC0" \
223  "\x38\x21\xBC\x58\x20\x63" ) },
224  /* X9.62 P239v3 */
225  { CRYPT_ECCCURVE_P239v3, 239,
226  MKDATA( "\x7F\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
227  "\xFF\xFF\xFF\xFF\x7F\xFF\xFF\xFF" \
228  "\xFF\xFF\x80\x00\x00\x00\x00\x00" \
229  "\x7F\xFF\xFF\xFF\xFF\xFF" ),
230  MKDATA( "\x7F\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
231  "\xFF\xFF\xFF\xFF\x7F\xFF\xFF\xFF" \
232  "\xFF\xFF\x80\x00\x00\x00\x00\x00" \
233  "\x7F\xFF\xFF\xFF\xFF\xFC" ),
234  MKDATA( "\x25\x57\x05\xFA\x2A\x30\x66\x54" \
235  "\xB1\xF4\xCB\x03\xD6\xA7\x50\xA3" \
236  "\x0C\x25\x01\x02\xD4\x98\x87\x17" \
237  "\xD9\xBA\x15\xAB\x6D\x3E" ),
238  MKDATA( "\x67\x68\xAE\x8E\x18\xBB\x92\xCF" \
239  "\xCF\x00\x5C\x94\x9A\xA2\xC6\xD9" \
240  "\x48\x53\xD0\xE6\x60\xBB\xF8\x54" \
241  "\xB1\xC9\x50\x5F\xE9\x5A" ),
242  MKDATA( "\x16\x07\xE6\x89\x8F\x39\x0C\x06" \
243  "\xBC\x1D\x55\x2B\xAD\x22\x6F\x3B" \
244  "\x6F\xCF\xE4\x8B\x6E\x81\x84\x99" \
245  "\xAF\x18\xE3\xED\x6C\xF3" ),
246  MKDATA( "\x7F\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
247  "\xFF\xFF\xFF\xFF\x7F\xFF\xFF\x97" \
248  "\x5D\xEB\x41\xB3\xA6\x05\x7C\x3C" \
249  "\x43\x21\x46\x52\x65\x51" ) },
250 #endif /* 0 */
251 
252  /* NIST P-256, X9.62 p256r1, SECG p256r1 */
253  { CRYPT_ECCCURVE_P256, 256,
254  MKDATA( "\xFF\xFF\xFF\xFF\x00\x00\x00\x01" \
255  "\x00\x00\x00\x00\x00\x00\x00\x00" \
256  "\x00\x00\x00\x00\xFF\xFF\xFF\xFF" \
257  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" ),
258  MKDATA( "\xFF\xFF\xFF\xFF\x00\x00\x00\x01" \
259  "\x00\x00\x00\x00\x00\x00\x00\x00" \
260  "\x00\x00\x00\x00\xFF\xFF\xFF\xFF" \
261  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFC" ),
262  MKDATA( "\x5A\xC6\x35\xD8\xAA\x3A\x93\xE7" \
263  "\xB3\xEB\xBD\x55\x76\x98\x86\xBC" \
264  "\x65\x1D\x06\xB0\xCC\x53\xB0\xF6" \
265  "\x3B\xCE\x3C\x3E\x27\xD2\x60\x4B" ),
266  MKDATA( "\x6B\x17\xD1\xF2\xE1\x2C\x42\x47" \
267  "\xF8\xBC\xE6\xE5\x63\xA4\x40\xF2" \
268  "\x77\x03\x7D\x81\x2D\xEB\x33\xA0" \
269  "\xF4\xA1\x39\x45\xD8\x98\xC2\x96" ),
270  MKDATA( "\x4F\xE3\x42\xE2\xFE\x1A\x7F\x9B" \
271  "\x8E\xE7\xEB\x4A\x7C\x0F\x9E\x16" \
272  "\x2B\xCE\x33\x57\x6B\x31\x5E\xCE" \
273  "\xCB\xB6\x40\x68\x37\xBF\x51\xF5" ),
274  MKDATA( "\xFF\xFF\xFF\xFF\x00\x00\x00\x00" \
275  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
276  "\xBC\xE6\xFA\xAD\xA7\x17\x9E\x84" \
277  "\xF3\xB9\xCA\xC2\xFC\x63\x25\x51" ),
278  MKDATA( "\x01" ) },
279 
280  /* NIST P-384, SECG p384r1 */
281  { CRYPT_ECCCURVE_P384, 384,
282  MKDATA( "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
283  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
284  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
285  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFE" \
286  "\xFF\xFF\xFF\xFF\x00\x00\x00\x00" \
287  "\x00\x00\x00\x00\xFF\xFF\xFF\xFF" ),
288  MKDATA( "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
289  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
290  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
291  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFE" \
292  "\xFF\xFF\xFF\xFF\x00\x00\x00\x00" \
293  "\x00\x00\x00\x00\xFF\xFF\xFF\xFC" ),
294  MKDATA( "\xB3\x31\x2F\xA7\xE2\x3E\xE7\xE4" \
295  "\x98\x8E\x05\x6B\xE3\xF8\x2D\x19" \
296  "\x18\x1D\x9C\x6E\xFE\x81\x41\x12" \
297  "\x03\x14\x08\x8F\x50\x13\x87\x5A" \
298  "\xC6\x56\x39\x8D\x8A\x2E\xD1\x9D" \
299  "\x2A\x85\xC8\xED\xD3\xEC\x2A\xEF" ),
300  MKDATA( "\xAA\x87\xCA\x22\xBE\x8B\x05\x37" \
301  "\x8E\xB1\xC7\x1E\xF3\x20\xAD\x74" \
302  "\x6E\x1D\x3B\x62\x8B\xA7\x9B\x98" \
303  "\x59\xF7\x41\xE0\x82\x54\x2A\x38" \
304  "\x55\x02\xF2\x5D\xBF\x55\x29\x6C" \
305  "\x3A\x54\x5E\x38\x72\x76\x0A\xB7" ),
306  MKDATA( "\x36\x17\xDE\x4A\x96\x26\x2C\x6F" \
307  "\x5D\x9E\x98\xBF\x92\x92\xDC\x29" \
308  "\xF8\xF4\x1D\xBD\x28\x9A\x14\x7C" \
309  "\xE9\xDA\x31\x13\xB5\xF0\xB8\xC0" \
310  "\x0A\x60\xB1\xCE\x1D\x7E\x81\x9D" \
311  "\x7A\x43\x1D\x7C\x90\xEA\x0E\x5F" ),
312  MKDATA( "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
313  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
314  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
315  "\xC7\x63\x4D\x81\xF4\x37\x2D\xDF" \
316  "\x58\x1A\x0D\xB2\x48\xB0\xA7\x7A" \
317  "\xEC\xEC\x19\x6A\xCC\xC5\x29\x73" ),
318  MKDATA( "\x01" ) },
319 
320  /* NIST P-521, SECG p521r1 */
321  { CRYPT_ECCCURVE_P521, 521,
322  MKDATA( "\x01\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
323  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
324  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
325  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
326  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
327  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
328  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
329  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
330  "\xFF\xFF" ),
331  MKDATA( "\x01\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
332  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
333  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
334  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
335  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
336  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
337  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
338  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
339  "\xFF\xFC" ),
340  MKDATA( "\x00\x51\x95\x3E\xB9\x61\x8E\x1C" \
341  "\x9A\x1F\x92\x9A\x21\xA0\xB6\x85" \
342  "\x40\xEE\xA2\xDA\x72\x5B\x99\xB3" \
343  "\x15\xF3\xB8\xB4\x89\x91\x8E\xF1" \
344  "\x09\xE1\x56\x19\x39\x51\xEC\x7E" \
345  "\x93\x7B\x16\x52\xC0\xBD\x3B\xB1" \
346  "\xBF\x07\x35\x73\xDF\x88\x3D\x2C" \
347  "\x34\xF1\xEF\x45\x1F\xD4\x6B\x50" \
348  "\x3F\x00" ),
349  MKDATA( "\x00\xC6\x85\x8E\x06\xB7\x04\x04" \
350  "\xE9\xCD\x9E\x3E\xCB\x66\x23\x95" \
351  "\xB4\x42\x9C\x64\x81\x39\x05\x3F" \
352  "\xB5\x21\xF8\x28\xAF\x60\x6B\x4D" \
353  "\x3D\xBA\xA1\x4B\x5E\x77\xEF\xE7" \
354  "\x59\x28\xFE\x1D\xC1\x27\xA2\xFF" \
355  "\xA8\xDE\x33\x48\xB3\xC1\x85\x6A" \
356  "\x42\x9B\xF9\x7E\x7E\x31\xC2\xE5" \
357  "\xBD\x66" ),
358  MKDATA( "\x01\x18\x39\x29\x6A\x78\x9A\x3B" \
359  "\xC0\x04\x5C\x8A\x5F\xB4\x2C\x7D" \
360  "\x1B\xD9\x98\xF5\x44\x49\x57\x9B" \
361  "\x44\x68\x17\xAF\xBD\x17\x27\x3E" \
362  "\x66\x2C\x97\xEE\x72\x99\x5E\xF4" \
363  "\x26\x40\xC5\x50\xB9\x01\x3F\xAD" \
364  "\x07\x61\x35\x3C\x70\x86\xA2\x72" \
365  "\xC2\x40\x88\xBE\x94\x76\x9F\xD1" \
366  "\x66\x50" ),
367  MKDATA( "\x01\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
368  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
369  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
370  "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF" \
371  "\xFF\xFA\x51\x86\x87\x83\xBF\x2F" \
372  "\x96\x6B\x7F\xCC\x01\x48\xF7\x09" \
373  "\xA5\xD0\x3B\xB5\xC9\xB8\x89\x9C" \
374  "\x47\xAE\xBB\x6F\xB7\x1E\x91\x38" \
375  "\x64\x09" ),
376  MKDATA( "\x01" ) },
377 
378  /* End-of-list marker */
379  { CRYPT_ECCCURVE_NONE, 0, NULL, NULL, NULL, NULL, NULL, NULL, NULL },
380  { CRYPT_ECCCURVE_NONE, 0, NULL, NULL, NULL, NULL, NULL, NULL, NULL }
381  };
382 
383 /* Initialise the bignums for the domain parameter values { p, a, b, gx, gy,
384  n }. Note that although the cofactor h is given for the standard named
385  curves it's not used for any ECC operations so we don't bother allocating
386  a bignum to it */
387 
388 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
389 static int loadECCparams( INOUT CONTEXT_INFO *contextInfoPtr )
390  {
391  PKC_INFO *pkcInfo = contextInfoPtr->ctxPKC;
392  const ECC_DOMAIN_PARAMS *eccParams = NULL;
393  int curveSize, i, bnStatus = BN_STATUS;
394 
395  assert( isWritePtr( contextInfoPtr, sizeof( CONTEXT_INFO ) ) );
396 
397  /* Find the parameter info for this curve */
398  for( i = 0; domainParamTbl[ i ].paramType != CRYPT_ECCCURVE_NONE && \
399  i < FAILSAFE_ARRAYSIZE( domainParamTbl, ECC_DOMAIN_PARAMS );
400  i++ )
401  {
402  if( domainParamTbl[ i ].paramType == pkcInfo->curveType )
403  {
404  eccParams = &domainParamTbl[ i ];
405  break;
406  }
407  }
408  ENSURES( i < FAILSAFE_ARRAYSIZE( domainParamTbl, ECC_DOMAIN_PARAMS ) );
409  ENSURES( eccParams != NULL );
410 
411  /* For the named curve the key size is defined by exective fiat based
412  on the curve type rather than being taken from the public-key value
413  (which in this case is the magnitude of the point Q on the curve), so
414  we set it explicitly based on the curve type */
415  pkcInfo->keySizeBits = eccParams->curveSizeBits;
416  curveSize = bitsToBytes( eccParams->curveSizeBits );
417 
418  /* Load the parameters into the context bignums */
419  CKPTR( BN_bin2bn( eccParams->p, curveSize, &pkcInfo->eccParam_p ) );
420  CKPTR( BN_bin2bn( eccParams->a, curveSize, &pkcInfo->eccParam_a ) );
421  CKPTR( BN_bin2bn( eccParams->b, curveSize, &pkcInfo->eccParam_b ) );
422  CKPTR( BN_bin2bn( eccParams->gx, curveSize, &pkcInfo->eccParam_gx ) );
423  CKPTR( BN_bin2bn( eccParams->gy, curveSize, &pkcInfo->eccParam_gy ) );
424  CKPTR( BN_bin2bn( eccParams->n, curveSize, &pkcInfo->eccParam_n ) );
425  CKPTR( BN_bin2bn( eccParams->h, curveSize, &pkcInfo->eccParam_h ) );
426 
427  return( getBnStatus( bnStatus ) );
428  }
429 
430 /****************************************************************************
431 * *
432 * ECC Information Access Functions *
433 * *
434 ****************************************************************************/
435 
436 /* Get the nominal size of an ECC field based on an CRYPT_ECCCURVE_TYPE */
437 
438 CHECK_RETVAL STDC_NONNULL_ARG( ( 2 ) ) \
439 int getECCFieldSize( IN_ENUM( CRYPT_ECCCURVE ) \
440  const CRYPT_ECCCURVE_TYPE fieldID,
441  OUT_INT_Z int *fieldSize )
442  {
443  int i;
444 
445  assert( isWritePtr( fieldSize, sizeof( int ) ) );
446 
447  REQUIRES( fieldID > CRYPT_ECCCURVE_NONE && \
448  fieldID < CRYPT_ECCCURVE_LAST );
449 
450  /* Clear return value */
451  *fieldSize = 0;
452 
453  /* Find the nominal field size for the given fieldID */
454  for( i = 0;
455  domainParamTbl[ i ].paramType != CRYPT_ECCCURVE_NONE && \
456  i < FAILSAFE_ARRAYSIZE( domainParamTbl, ECC_DOMAIN_PARAMS );
457  i++ )
458  {
459  if( domainParamTbl[ i ].paramType == fieldID )
460  {
461  *fieldSize = bitsToBytes( domainParamTbl[ i ].curveSizeBits );
462  return( CRYPT_OK );
463  }
464  }
465 
466  retIntError();
467  }
468 
469 /* Get a CRYPT_ECCCURVE_TYPE based on a nominal ECC field size */
470 
471 CHECK_RETVAL STDC_NONNULL_ARG( ( 2 ) ) \
472 static int getECCFieldID( IN_LENGTH_SHORT_MIN( MIN_PKCSIZE_ECC ) \
473  const int fieldSize,
474  OUT_ENUM_OPT( CRYPT_ECCCURVE )
475  CRYPT_ECCCURVE_TYPE *fieldID )
476  {
477  int i;
478 
479  assert( isWritePtr( fieldID, sizeof( CRYPT_ECCCURVE_TYPE ) ) );
480 
481  REQUIRES( fieldSize >= MIN_PKCSIZE_ECC && \
482  fieldSize <= CRYPT_MAX_PKCSIZE_ECC );
483 
484  /* Clear return value */
485  *fieldID = CRYPT_ECCCURVE_NONE;
486 
487  /* Find the fieldID for the given nominal field size */
488  for( i = 0;
489  domainParamTbl[ i ].paramType != CRYPT_ECCCURVE_NONE && \
490  i < FAILSAFE_ARRAYSIZE( domainParamTbl, ECC_DOMAIN_PARAMS );
491  i++ )
492  {
493  if( bitsToBytes( domainParamTbl[ i ].curveSizeBits ) >= fieldSize )
494  {
495  *fieldID = domainParamTbl[ i ].paramType;
496  return( CRYPT_OK );
497  }
498  }
499 
500  /* Because of rounding issues in parameter bounds checking, combined
501  with the odd-length sizes chosen for some of the standard curves,
502  we can end up with a situation where the requested curve size is a
503  few bits over even the largest field size. If we run into this
504  situation then we use the largest field size */
505  if( fieldSize >= bitsToBytes( 521 ) )
506  {
507  *fieldID = CRYPT_ECCCURVE_P521;
508  return( CRYPT_OK );
509  }
510 
511  retIntError();
512  }
513 
514 /****************************************************************************
515 * *
516 * Generate an ECC Key *
517 * *
518 ****************************************************************************/
519 
520 /* Generate the ECC private value d and public value Q */
521 
522 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
523 static int generateECCPrivateValue( INOUT PKC_INFO *pkcInfo,
524  IN_LENGTH_SHORT_MIN( MIN_PKCSIZE_ECC * 8 ) \
525  const int keyBits )
526  {
527  BIGNUM *p = &pkcInfo->eccParam_p, *d = &pkcInfo->eccParam_d;
528  int bnStatus = BN_STATUS, status;
529 
530  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
531 
532  REQUIRES( keyBits >= bytesToBits( MIN_PKCSIZE_ECC ) && \
533  keyBits <= bytesToBits( CRYPT_MAX_PKCSIZE_ECC ) );
534 
535  /* Generate the ECC private value d s.t. 2 <= d <= p-2. Because the mod
536  p-2 is expensive we do a quick check to make sure that it's really
537  necessary before calling it */
538  status = generateBignum( d, keyBits, 0xC0, 0 );
539  if( cryptStatusError( status ) )
540  return( status );
541  CK( BN_sub_word( p, 2 ) );
542  if( BN_cmp( d, p ) > 0 )
543  {
544  /* Trim d down to size. Actually we get the upper bound as p-3,
545  but over a 192-bit (minimum) number range this doesn't matter */
546  CK( BN_mod( d, d, p, pkcInfo->bnCTX ) );
547 
548  /* If the value that we ended up with is too small, just generate a
549  new value one bit shorter, which guarantees that it'll fit the
550  criteria (the target is a suitably large random value, not the
551  closest possible fit within the range) */
552  if( bnStatusOK( bnStatus ) && BN_num_bits( d ) < keyBits - 5 )
553  status = generateBignum( d, keyBits - 1, 0xC0, 0 );
554  }
555  CK( BN_add_word( p, 2 ) );
556 
557  return( cryptStatusError( status ) ? status : getBnStatus( bnStatus ) );
558  }
559 
560 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
561 static int generateECCPublicValue( INOUT PKC_INFO *pkcInfo )
562  {
563  BIGNUM *d = &pkcInfo->eccParam_d;
564  BIGNUM *qx = &pkcInfo->eccParam_qx, *qy = &pkcInfo->eccParam_qy;
565  EC_GROUP *ecCTX = pkcInfo->ecCTX;
566  EC_POINT *q = pkcInfo->tmpPoint;
567  int bnStatus = BN_STATUS;
568 
569  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
570 
571  /* Calculate the public-key value Q = d * G */
572  CK( EC_POINT_mul( ecCTX, q, d, NULL, NULL, pkcInfo->bnCTX ) );
573  if( bnStatusError( bnStatus ) )
574  return( getBnStatus( bnStatus ) );
575  CK( EC_POINT_get_affine_coordinates_GFp( ecCTX, q, qx, qy,
576  pkcInfo->bnCTX ) );
577  if( bnStatusError( bnStatus ) )
578  return( getBnStatus( bnStatus ) );
579 
580  return( CRYPT_OK );
581  }
582 
583 /****************************************************************************
584 * *
585 * Check an ECC Key *
586 * *
587 ****************************************************************************/
588 
589 /* Perform validity checks on the public key. In the tradition of these
590  documents, FIPS 186 and the X9.62 standard that it's derived from
591  occasionally use different names for the parameters, the following
592  mapping can be used to go from one to the other:
593 
594  FIPS 186 X9.62/SECG Description
595  -------- ---------- -----------
596  p p Finite field Fp
597  a, b a, b Elliptic curve y^2 == x^3 + ax + b
598  xg, yg xg, yg Base point G on the curve
599  n n Prime n of order G
600  h h Cofactor
601  -------- --------- -----------
602  wx, wy xq, yq Public key Q
603  d d Private key
604 
605  We have to make the PKC_INFO data non-const because the bignum code wants
606  to modify some of the values as it's working with them */
607 
608 CHECK_RETVAL_BOOL STDC_NONNULL_ARG( ( 1, 2 ) ) \
609 static BOOLEAN checkComponentLength( const BIGNUM *component,
610  const BIGNUM *p,
611  const BOOLEAN lowerBoundZero )
612  {
613  int length;
614 
615  assert( isReadPtr( component, sizeof( BIGNUM ) ) );
616  assert( isReadPtr( p, sizeof( BIGNUM ) ) );
617 
618  /* Make sure that the component is in the range 0...p - 1 (optionally
619  MIN_PKCSIZE_ECC if lowerBoundZero is false) */
620  length = BN_num_bytes( component );
621  if( length < ( lowerBoundZero ? 0 : MIN_PKCSIZE_ECC ) || \
622  length > CRYPT_MAX_PKCSIZE_ECC )
623  return( FALSE );
624  if( BN_cmp( component, p ) >= 0 )
625  return( FALSE );
626 
627  return( TRUE );
628  }
629 
630 /* Check that y^2 = x^3 + a*x + b is in the field GF(p) */
631 
632 CHECK_RETVAL_BOOL STDC_NONNULL_ARG( ( 1, 2, 3, 4, 5 ) ) \
633 static BOOLEAN isPointOnCurve( const BIGNUM *y, const BIGNUM *x,
634  const BIGNUM *a, const BIGNUM *b,
635  INOUT PKC_INFO *pkcInfo )
636  {
637  BIGNUM *p = &pkcInfo->eccParam_p;
638  BIGNUM *tmp1 = &pkcInfo->tmp1, *tmp2 = &pkcInfo->tmp2;
639  BN_CTX *ctx = pkcInfo->bnCTX;
640  int bnStatus = BN_STATUS;
641 
642  assert( isReadPtr( y, sizeof( BIGNUM ) ) );
643  assert( isReadPtr( x, sizeof( BIGNUM ) ) );
644  assert( isReadPtr( a, sizeof( BIGNUM ) ) );
645  assert( isReadPtr( b, sizeof( BIGNUM ) ) );
646  assert( isReadPtr( p, sizeof( BIGNUM ) ) );
647  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
648 
649  CK( BN_mod_mul( tmp1, y, y, p, ctx ) );
650  CK( BN_mod_mul( tmp2, x, x, p, ctx ) );
651  CK( BN_mod_add( tmp2, tmp2, a, p, ctx ) );
652  CK( BN_mod_mul( tmp2, tmp2, x, p, ctx ) );
653  CK( BN_mod_add( tmp2, tmp2, b, p, ctx ) );
654  if( bnStatusError( bnStatus ) )
655  return( FALSE );
656  if( BN_cmp( tmp1, tmp2 ) != 0 )
657  return( FALSE );
658 
659  return( TRUE );
660  }
661 
662 /* Check the ECC domain parameters. X9.62 specifies curves in the field
663  GF(q) of size q, where q is either a prime integer or equal to 2^m (with
664  m prime). The following checks only handle curves where q is a prime
665  integer (the de facto universal standard), referred to as 'p' in the
666  following code */
667 
668 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
669 static int checkECCDomainParameters( INOUT PKC_INFO *pkcInfo,
670  const BOOLEAN isFullyInitialised )
671  {
672  EC_GROUP *ecCTX = pkcInfo->ecCTX;
673  BIGNUM *p = &pkcInfo->eccParam_p;
674  BIGNUM *a = &pkcInfo->eccParam_a, *b = &pkcInfo->eccParam_b;
675  BIGNUM *n = &pkcInfo->eccParam_n, *h = &pkcInfo->eccParam_h;
676  BIGNUM *gx = &pkcInfo->eccParam_gx, *gy = &pkcInfo->eccParam_gy;
677  BIGNUM *tmp1 = &pkcInfo->tmp1, *tmp2 = &pkcInfo->tmp2;
678  BIGNUM *tmp3_h = &pkcInfo->tmp3;
679  EC_POINT *vp = pkcInfo->tmpPoint;
680  const BOOLEAN isStandardCurve = \
681  ( pkcInfo->curveType != CRYPT_ECCCURVE_NONE ) ? TRUE : FALSE;
682  int length, i, plen, bnStatus = BN_STATUS;
683 
684  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
685 
686  /* Verify that the domain parameter sizes are valid:
687 
688  pLen >= MIN_PKCSIZE_ECC, pLen <= CRYPT_MAX_PKCSIZE_ECC
689  a, b >= 0, a, b <= p - 1
690  gx, gy >= 0, gx, gy <= p - 1
691  nLen >= MIN_PKCSIZE_ECC, nLen <= CRYPT_MAX_PKCSIZE_ECC
692  hLen >= 1, hLen <= CRYPT_MAX_PKCSIZE_ECC (if present) */
693  length = BN_num_bytes( p );
694  if( length < MIN_PKCSIZE_ECC || length > CRYPT_MAX_PKCSIZE_ECC )
695  return( CRYPT_ARGERROR_STR1 );
696  if( !checkComponentLength( a, p, TRUE ) || \
697  !checkComponentLength( b, p, TRUE ) )
698  return( CRYPT_ARGERROR_STR1 );
699  if( !checkComponentLength( gx, p, TRUE ) || \
700  !checkComponentLength( gy, p, TRUE ) )
701  return( CRYPT_ARGERROR_STR1 );
702  length = BN_num_bytes( n );
703  if( length < MIN_PKCSIZE_ECC || length > CRYPT_MAX_PKCSIZE_ECC )
704  return( CRYPT_ARGERROR_STR1 );
705  if( !BN_is_zero( h ) )
706  {
707  length = BN_num_bytes( h );
708  if( length < 1 || length > CRYPT_MAX_PKCSIZE_ECC )
709  return( CRYPT_ARGERROR_STR1 );
710  }
711 
712  /* Whether the domain parameters need to be validated each time that
713  they're loaded is left unclear in the specifications. In fact
714  whether they, or the public key data, needs to be validated at all,
715  is left unspecified. FIPS 186-3 is entirely silent on the matter and
716  X9.62 defers to an annex that contains two whole sentences that
717  merely say that it's someone else's problem. In the absence of any
718  guidance we only validate domain parameters if they're supplied
719  externally, although it could be argued that to prevent memory
720  corruption side-channel attacks we should really validate the hard-
721  coded internal ones as well.
722 
723  To activate domain validation on known curves, comment out the check
724  below */
725  if( isStandardCurve )
726  return( CRYPT_OK );
727 
728  /* Verify that p is not (obviously) composite */
729  if( !primeSieve( &pkcInfo->eccParam_p ) )
730  return( CRYPT_ARGERROR_STR1 );
731 
732  /* Verify that a, b and gx, gy are integers in the range 0...p - 1.
733  This has already been done in the range checks performed earlier */
734 
735  /* Verify that (4a^3 + 27b^2) is not congruent to zero (mod p) */
736  CK( BN_sqr( tmp1, a, pkcInfo->bnCTX ) );
737  CK( BN_mul( tmp1, tmp1, a, pkcInfo->bnCTX ) );
738  CK( BN_mul_word( tmp1, 4 ) );
739  CK( BN_sqr( tmp2, b, pkcInfo->bnCTX ) );
740  CK( BN_mul_word( tmp2, 27 ) );
741  CK( BN_add( tmp1, tmp1, tmp2 ) );
742  CK( BN_mod( tmp1, tmp1, p, pkcInfo->bnCTX ) );
743  if( bnStatusError( bnStatus ) )
744  return( getBnStatus( bnStatus ) );
745  if( BN_is_zero( tmp1 ) )
746  return( CRYPT_ARGERROR_STR1 );
747 
748  /* Verify that gy^2 is congruent to gx^3 + a*gx + b (mod p) */
749  if( !isPointOnCurve( gy, gx, a, b, pkcInfo ) )
750  return( CRYPT_ARGERROR_STR1 );
751 
752  /* Verify that:
753 
754  n is not (obviously) composite
755  n > 2^160 and n > 2^( 2s-1 ), where s is the "security level"
756 
757  The second test is about ensuring that the subgroup order is large
758  enough to make the ECDLP infeasible. X9.62 measures infeasibility
759  by the security level, and the test on 2^160 means that X9.62
760  considers that there is no worthwhile security below level 80.5.
761  The security level has already been implicitly checked via the
762  MIN_PKCSIZE_ECC constant, and n has already been tested above */
763  if( !primeSieve( &pkcInfo->eccParam_n ) )
764  return( CRYPT_ARGERROR_STR1 );
765 
766  /* Verify that n * G is the point at infinity. This runs into a nasty
767  catch-22 where we have to initialise at least some of the ECC
768  parameter information in order to perform the check, but we can't
769  (safely) use the parameters before we've checked them. To get around
770  this, if the values haven't been fully set up yet then we perform the
771  check inline in the initCheckECCKey() code */
772  if( isFullyInitialised )
773  {
774  CK( EC_POINT_mul( ecCTX, vp, n, NULL, NULL, pkcInfo->bnCTX ) );
775  if( bnStatusError( bnStatus ) )
776  return( getBnStatus( bnStatus ) );
777  if( !EC_POINT_is_at_infinity( ecCTX, vp ) )
778  return( CRYPT_ARGERROR_STR1 );
779  }
780 
781  /* Compute the cofactor h. The domain parameters may include h, but we
782  still want to compute it and check that we get the same value. The
783  cofactor will be needed for verification of the "anomalous condition".
784 
785  The curve size is #E = q+1-t, where t is the trace of Frobenius.
786  Hasse's theorem guarantees that |t| <= 2*sqrt(q). Since we work over
787  a subgroup of size n, we know that n divides #E; the cofactor h is
788  the integer such that #E = n*h.
789 
790  In the X9.62 world, h is much smaller than n. It follows that h can
791  be recomputed accurately from q and n, since there's only one integer
792  value for h that puts t in the proper range. The formula given in
793  X9.62 is:
794 
795  h = floor( ( sqrt( q ) + 1 )^2 / n )
796 
797  which expands to:
798 
799  h = floor( ( q + 1 + 2*sqrt( q ) ) / n )
800 
801  which can be seen to map to the proper cofactor: we compute a value
802  which is one more than the maximum possible curve order, and divide
803  by n. If we then verify that h is small enough (which is a
804  requirement of X9.62) then we know that we've found the proper
805  cofactor.
806 
807  The X9.62 formula is cumbersome because it requires a square root,
808  and we have to keep track of fractional bits as well. The expanded
809  formula requires less fractional bits, but it still needs a square
810  root. Instead, we can take advantage of the fact that the conditions
811  on the "security level" (n >= 2^160, n >= 2^(2s-1) and h <= 2^(s/8)
812  for an integer s) imply that n >= h^15. A consequence of this is
813  that n*h <= n^(1+1/15). n*h is the curve order, which is close to q
814  and lower than 2*q.
815 
816  Now, let qlen = log2(q) (the size of q in bits;
817  2^( qlen-1 ) <= q < 2^qlen). We then compute:
818 
819  z = q + 2^( floor( qlen/2 ) + 3 )
820 
821  which is easily obtained by shifting one bit and performing an
822  addition. It's then easily seen that z > #E. Since we work in a
823  field of sufficiently large size (according to X9.62, qlen >= 160,
824  but we may accept slightly smaller values of q, but no less than
825  qlen = 128), we can show that n is much larger than
826  2^( floor( qlen/2 ) + 4 ) (the size of n is at least 15/16ths of that
827  of q). This implies that z-n is much smaller than the minimal
828  possible size of E.
829 
830  We conclude that h = floor( z / n ), which is then the formula that
831  we apply. We also check that h is no larger than 1/14th of n (using
832  14 instead of 15 avoids rounding issues since the size in bits of h
833  is not exactly equal to log2(h), but it's still good enough for the
834  analysis above).
835 
836  For the standard named curves in GF(p) (the P-* NIST curves), h = 1
837  and is implicitly present. */
838  plen = BN_num_bits( p );
839  CK( BN_one( tmp1 ) );
840  CK( BN_lshift( tmp1, tmp1, ( plen >> 1 ) + 3 ) );
841  CK( BN_add( tmp1, tmp1, p ) );
842  CK( BN_div( tmp3_h, NULL, tmp1, n, pkcInfo->bnCTX ) );
843  if( bnStatusError( bnStatus ) )
844  return( getBnStatus( bnStatus ) );
845  if( ( BN_num_bits( tmp3_h ) * 14 ) > BN_num_bits( n ) )
846  return( CRYPT_ARGERROR_STR1 );
847  if( isStandardCurve )
848  {
849  /* This code is executed only if the early exit for known curves
850  above has been deactivated */
851  if ( !BN_is_one( tmp3_h ) )
852  return( CRYPT_ARGERROR_STR1 );
853  }
854  else
855  {
856  if( !BN_is_zero( h ) && BN_cmp( h, tmp3_h ) != 0 )
857  return( CRYPT_ARGERROR_STR1 );
858  }
859  h = tmp3_h;
860 
861  /* Verify that the MOV condition holds. We use an MOV threshold B = 100
862  as per X9.62:2005 ('98 used B = 20).
863 
864  Mathematically, we want to make sure that the embedding degree of the
865  curve (for the subgroup that we're interested in) is greater than 100.
866  The embedding degree is the lowest integer k such that r divides q^k-1
867  (using the X9.62 notations where q is the field size, here held in
868  the local variable p, while r is the subgroup order size, which the
869  code below calls n). The embedding degree always exists, except if
870  the curve is anomalous, i.e. the size of the curve is equal to the
871  field size. Anomalous curves are a bad thing to have, so they're
872  checked for later on.
873 
874  The Weil and Tate pairings allow the conversion of the ECDLP problem
875  into the "plain" DLP problem in GF(q^k), the field extension of GF(q)
876  of degree k, for which subexponential algorithms are known. For
877  example if a curve is defined over a field GF(q) such that the size
878  of q is 256 bits and n also has a size close to 256 bits then we
879  expect the ECDLP to have a cost of about O( 2^128 ), i.e. it's very
880  much infeasible. However if that curve happens to have an extension
881  degree k = 2 then a Weil or Tate pairing transforms the ECLDP into
882  the DLP in GF(q^2), a field of size 512 bits, for which the DLP is
883  non-trivial but technologically feasible.
884 
885  For a random curve, k should be a large integer of the same size as
886  n, thus making q^k astronomically high. For our purposes we want to
887  make sure that k isn't very small. X9.62 checks that k > 100, which
888  is good enough, since if if k = 101 then the 256-bit ECDLP is
889  transformed into the 25856-bit DLP, which is awfully big and totally
890  infeasible as far as we know.
891 
892  Computing the value of k is feasible if you can factor r-1, but this
893  is expensive. The X9.62 test computes q, q^2, q^3... q^100 modulo n
894  and checks that none of these equal one */
895  CK( BN_one( tmp1 ) );
896  CK( BN_mod( tmp2, p, n, pkcInfo->bnCTX ) );
897  if( bnStatusError( bnStatus ) )
898  return( getBnStatus( bnStatus ) );
899  for( i = 0; i < 100; i++ )
900  {
901  CK( BN_mod_mul( tmp1, tmp1, tmp2, n, pkcInfo->bnCTX ) );
902  if( bnStatusError( bnStatus ) )
903  return( getBnStatus( bnStatus ) );
904  if( BN_is_one( tmp1 ) )
905  return( CRYPT_ARGERROR_STR1 );
906  }
907 
908  /* Verify that the anomalous condition holds. An "anomalous curve" is a
909  curve E defined over a field of size q such that #E = q, i.e. the
910  curve size is equal to the field size. ECDLP on an anomalous curve
911  can be computed very efficiently, hence we want to avoid anomalous
912  curves.
913 
914  The curve order is r*h, where h is the cofactor, which we computed
915  (and checked) above */
916  CK( BN_mul( tmp1, n, h, pkcInfo->bnCTX ) );
917  if( bnStatusError( bnStatus ) )
918  return( getBnStatus( bnStatus ) );
919  if( BN_cmp( tmp1, p ) == 0 )
920  return( CRYPT_ARGERROR_STR1 );
921 
922  return( CRYPT_OK );
923  }
924 
925 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
926 static int checkECCPublicKey( INOUT PKC_INFO *pkcInfo )
927  {
928  BIGNUM *p = &pkcInfo->eccParam_p, *n = &pkcInfo->eccParam_n;
929  BIGNUM *qx = &pkcInfo->eccParam_qx, *qy = &pkcInfo->eccParam_qy;
930  EC_GROUP *ecCTX = pkcInfo->ecCTX;
931  EC_POINT *q = pkcInfo->tmpPoint;
932  int bnStatus = BN_STATUS;
933 
934  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
935 
936  /* Verify that the public key parameter sizes are valid:
937 
938  qx, qy >= MIN_PKCSIZE_ECC, qx, qy <= p - 1 */
939  if( !checkComponentLength( qx, p, FALSE ) || \
940  !checkComponentLength( qy, p, FALSE ) )
941  return( CRYPT_ARGERROR_STR1 );
942 
943  /* Verify that Q is not the point at infinity */
944  CK( EC_POINT_set_affine_coordinates_GFp( ecCTX, q, qx, qy,
945  pkcInfo->bnCTX ) );
946  if( bnStatusError( bnStatus ) )
947  return( getBnStatus( bnStatus ) );
948  if( EC_POINT_is_at_infinity( ecCTX, q ) )
949  return( CRYPT_ARGERROR_STR1 );
950 
951  /* Verify that qx, qy are elements in the field Fq, i.e. in the range
952  0...p - 1. This has already been done in the range checks performed
953  earlier */
954 
955  /* Verify that qy^2 is congruent to qx^3 + a*qx + b (mod p) */
956  if( !isPointOnCurve( qy, qx, &pkcInfo->eccParam_a, &pkcInfo->eccParam_b,
957  pkcInfo ) )
958  return( CRYPT_ARGERROR_STR1 );
959 
960  /* Verify that n * Q is the point at infinity */
961  CK( EC_POINT_mul( ecCTX, q, NULL, q, n, pkcInfo->bnCTX ) );
962  if( bnStatusError( bnStatus ) )
963  return( getBnStatus( bnStatus ) );
964  if( !EC_POINT_is_at_infinity( ecCTX, q ) )
965  return( CRYPT_ARGERROR_STR1 );
966 
967  return( CRYPT_OK );
968  }
969 
970 /* Perform validity checks on the private key */
971 
972 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
973 static int checkECCPrivateKey( INOUT PKC_INFO *pkcInfo )
974  {
975  BIGNUM *p = &pkcInfo->eccParam_p, *d = &pkcInfo->eccParam_d;
976  BIGNUM *tmp1 = &pkcInfo->tmp1, *tmp2 = &pkcInfo->tmp2;
977  EC_GROUP *ecCTX = pkcInfo->ecCTX;
978  EC_POINT *q = pkcInfo->tmpPoint;
979  int bnStatus = BN_STATUS;
980 
981  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
982 
983  /* Verify that the private key parameter sizes are valid:
984 
985  d >= MIN_PKCSIZE_ECC, d <= p - 1 */
986  if( !checkComponentLength( d, p, FALSE ) )
987  return( CRYPT_ARGERROR_STR1 );
988 
989  /* Verify that Q = d * G */
990  CK( EC_POINT_mul( ecCTX, q, d, NULL, NULL, pkcInfo->bnCTX ) );
991  CK( EC_POINT_get_affine_coordinates_GFp( ecCTX, q, tmp1, tmp2,
992  pkcInfo->bnCTX ) );
993  if( bnStatusError( bnStatus ) )
994  return( getBnStatus( bnStatus ) );
995  if( BN_cmp( tmp1, &pkcInfo->eccParam_qx ) != 0 || \
996  BN_cmp( tmp2, &pkcInfo->eccParam_qy ) != 0 )
997  return( CRYPT_ARGERROR_STR1 );
998 
999  return( CRYPT_OK );
1000  }
1001 
1002 /****************************************************************************
1003 * *
1004 * Generate/Initialise an ECC Key *
1005 * *
1006 ****************************************************************************/
1007 
1008 /* Initialise the mass of variables required by the ECC operations.
1009  Unfortunately there's no ECC analogue of BN_init() so we have to
1010  dynamically allocate values. In any case this is probably a better
1011  tradeoff since the EC_GROUP structure is huge and would blow out the
1012  size of the PKC_INFO for all other PKC contexts */
1013 
1014 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
1015 static int initECCVariables( INOUT PKC_INFO *pkcInfo )
1016  {
1017  EC_GROUP *ecCTX = pkcInfo->ecCTX;
1018  EC_POINT *ecPoint = pkcInfo->ecPoint;
1019  int bnStatus = BN_STATUS;
1020 
1021  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
1022 
1023  CK( EC_GROUP_set_curve_GFp( ecCTX, &pkcInfo->eccParam_p,
1024  &pkcInfo->eccParam_a, &pkcInfo->eccParam_b,
1025  pkcInfo->bnCTX ) );
1026  if( bnStatusError( bnStatus ) )
1027  return( getBnStatus( bnStatus ) );
1028  CK( EC_POINT_set_affine_coordinates_GFp( ecCTX, ecPoint,
1029  &pkcInfo->eccParam_gx,
1030  &pkcInfo->eccParam_gy,
1031  pkcInfo->bnCTX ) );
1032  if( bnStatusError( bnStatus ) )
1033  return( getBnStatus( bnStatus ) );
1034  CK( EC_GROUP_set_generator( ecCTX, ecPoint, &pkcInfo->eccParam_n,
1035  &pkcInfo->eccParam_h ) );
1036  if( bnStatusError( bnStatus ) )
1037  return( getBnStatus( bnStatus ) );
1038 
1039  return( CRYPT_OK );
1040  }
1041 
1042 /* Generate and check a generic ECC key */
1043 
1044 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
1045 int generateECCkey( INOUT CONTEXT_INFO *contextInfoPtr,
1046  IN_LENGTH_SHORT_MIN( MIN_PKCSIZE_ECC * 8 ) \
1047  const int keyBits )
1048  {
1049  PKC_INFO *pkcInfo = contextInfoPtr->ctxPKC;
1050  CRYPT_ECCCURVE_TYPE fieldID;
1051  int keySizeBits, status;
1052 
1053  assert( isWritePtr( contextInfoPtr, sizeof( CONTEXT_INFO ) ) );
1054 
1055  REQUIRES( keyBits >= bytesToBits( MIN_PKCSIZE_ECC ) && \
1056  keyBits <= bytesToBits( CRYPT_MAX_PKCSIZE_ECC ) );
1057 
1058  /* Find the fieldID matching the requested key size. This gets a bit
1059  complicated because with fixed-parameter curves the key size is taken
1060  to indicate the closest matching curve size (if we didn't do this and
1061  required that the caller specify exact sizes to match the predefined
1062  curves then they'd end up having to play guessing games to match
1063  byte-valued key sizes to oddball curve sizes like P521). To handle
1064  this we first map the key size to the matching curve, and then
1065  retrieve the actual key size in bits from the ECC parameter data */
1066  status = getECCFieldID( bitsToBytes( keyBits ), &fieldID );
1067  if( cryptStatusError( status ) )
1068  return( status );
1069  pkcInfo->curveType = fieldID;
1070  status = loadECCparams( contextInfoPtr );
1071  if( cryptStatusError( status ) )
1072  return( status );
1073  keySizeBits = pkcInfo->keySizeBits;
1074 
1075  /* Initialise the mass of variables required by the ECC operations */
1076  status = initECCVariables( pkcInfo );
1077  if( cryptStatusError( status ) )
1078  return( status );
1079 
1080  /* Generate the private key */
1081  status = generateECCPrivateValue( pkcInfo, keySizeBits );
1082  if( cryptStatusError( status ) )
1083  return( status );
1084 
1085  /* Calculate the public-key value Q = d * G */
1086  status = generateECCPublicValue( pkcInfo );
1087  if( cryptStatusError( status ) )
1088  return( status );
1089 
1090  /* Make sure that the generated values are valid */
1091  status = checkECCDomainParameters( pkcInfo, TRUE );
1092  if( cryptStatusOK( status ) )
1093  status = checkECCPublicKey( pkcInfo );
1094  if( cryptStatusOK( status ) )
1095  status = checkECCPrivateKey( pkcInfo );
1096  if( cryptStatusError( status ) )
1097  return( status );
1098 
1099  /* Enable side-channel protection if required */
1100  if( !( contextInfoPtr->flags & CONTEXT_FLAG_SIDECHANNELPROTECTION ) )
1101  return( CRYPT_OK );
1102  return( enableSidechannelProtection( pkcInfo,
1103  contextInfoPtr->capabilityInfo->cryptAlgo ) );
1104  }
1105 
1106 /* Initialise and check an ECC key. If the isECDH flag is set then it's an
1107  ECDH key and we generate the d value (and by extension the Q value) if
1108  it's not present */
1109 
1110 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
1111 int initCheckECCkey( INOUT CONTEXT_INFO *contextInfoPtr,
1112  const BOOLEAN isECDH )
1113  {
1114  PKC_INFO *pkcInfo = contextInfoPtr->ctxPKC;
1115  EC_GROUP *ecCTX = pkcInfo->ecCTX;
1116  BIGNUM *p = &pkcInfo->eccParam_p;
1117  const BOOLEAN isPrivateKey = \
1118  ( contextInfoPtr->flags & CONTEXT_FLAG_ISPUBLICKEY ) ? FALSE : TRUE;
1119  BOOLEAN generatedD = FALSE;
1120  int bnStatus = BN_STATUS, status;
1121 
1122  assert( isWritePtr( contextInfoPtr, sizeof( CONTEXT_INFO ) ) );
1123 
1124  /* If we're loading a named curve then the public-key parameters may not
1125  have been set yet, in which case we have to set them before we can
1126  continue */
1127  if( pkcInfo->curveType != CRYPT_ECCCURVE_NONE && \
1128  BN_is_zero( &pkcInfo->eccParam_p ) )
1129  {
1130  status = loadECCparams( contextInfoPtr );
1131  if( cryptStatusError( status ) )
1132  return( status );
1133  }
1134 
1135  /* Make sure that the necessary key parameters have been initialised */
1136  if( BN_is_zero( &pkcInfo->eccParam_p ) || \
1137  BN_is_zero( &pkcInfo->eccParam_a ) || \
1138  BN_is_zero( &pkcInfo->eccParam_b ) || \
1139  BN_is_zero( &pkcInfo->eccParam_gx ) || \
1140  BN_is_zero( &pkcInfo->eccParam_gy ) || \
1141  BN_is_zero( &pkcInfo->eccParam_n ) )
1142  return( CRYPT_ARGERROR_STR1 );
1143  if( !isECDH )
1144  {
1145  if( BN_is_zero( &pkcInfo->eccParam_qx ) || \
1146  BN_is_zero( &pkcInfo->eccParam_qy ) )
1147  return( CRYPT_ARGERROR_STR1 );
1148  if( isPrivateKey && BN_is_zero( &pkcInfo->eccParam_d ) )
1149  return( CRYPT_ARGERROR_STR1 );
1150  }
1151 
1152  /* Make sure that the domain parameters are valid */
1153  status = checkECCDomainParameters( pkcInfo, FALSE );
1154  if( cryptStatusError( status ) )
1155  return( status );
1156 
1157  /* Initialise the mass of variables required by the ECC operations */
1158  status = initECCVariables( pkcInfo );
1159  if( cryptStatusError( status ) )
1160  return( status );
1161 
1162  /* Additional verification for ECC domain parameters, verify that
1163  n * G is the point at infinity. We have to do this at this point
1164  rather than in checkECCDomainParameters() because it requires
1165  initialisation of values that haven't been set up yet when
1166  checkECCDomainParameters() is called */
1167  CK( EC_POINT_mul( ecCTX, pkcInfo->tmpPoint, &pkcInfo->eccParam_n,
1168  NULL, NULL, pkcInfo->bnCTX ) );
1169  if( bnStatusError( bnStatus ) )
1170  return( getBnStatus( bnStatus ) );
1171  if( !EC_POINT_is_at_infinity( ecCTX, pkcInfo->tmpPoint ) )
1172  return( CRYPT_ARGERROR_STR1 );
1173 
1174  /* If it's an ECDH key and there's no d value present, generate one
1175  now. This is needed because all ECDH keys are effectively private
1176  keys. We also update the context flags to reflect this change in
1177  status */
1178  if( isECDH && BN_is_zero( &pkcInfo->eccParam_d ) )
1179  {
1180  status = generateECCPrivateValue( pkcInfo, pkcInfo->keySizeBits );
1181  if( cryptStatusError( status ) )
1182  return( status );
1183  contextInfoPtr->flags &= ~CONTEXT_FLAG_ISPUBLICKEY;
1184  generatedD = TRUE;
1185  }
1186 
1187  /* Some sources (specifically PKCS #11) don't make Q available for
1188  private keys so if the caller is trying to load a private key with a
1189  zero Q value we calculate it for them. First, we check to make sure
1190  that we have d available to calculate Q */
1191  if( BN_is_zero( &pkcInfo->eccParam_qx ) && \
1192  BN_is_zero( &pkcInfo->eccParam_d ) )
1193  return( CRYPT_ARGERROR_STR1 );
1194 
1195  /* Calculate Q if required. This is a bit odd because if we've
1196  generated a new d value it'll cause any existing Q value to be
1197  overwritten by a new one based on the newly-generated Q value. This
1198  means that if we load an ECDH key from a certificate containing an
1199  existing Q value then this process will overwrite the value with a
1200  new one, so that the context associated with the certificate will
1201  contain a Q value that differs from the one in the certificate. This
1202  is unfortunate, but again because of the ECDH key duality we need to
1203  have both a d and a Q value present otherwise the key is useless and
1204  in order to get a d value we have to recreate the Q value */
1205  if( BN_is_zero( &pkcInfo->eccParam_qx ) || generatedD )
1206  {
1207  status = generateECCPublicValue( pkcInfo );
1208  if( cryptStatusError( status ) )
1209  return( status );
1210  }
1211 
1212  /* Make sure that the public key is valid */
1213  status = checkECCPublicKey( pkcInfo );
1214  if( cryptStatusError( status ) )
1215  return( status );
1216 
1217  /* Make sure that the private key is valid */
1218  if( isPrivateKey || generatedD )
1219  {
1220  status = checkECCPrivateKey( pkcInfo );
1221  if( cryptStatusError( status ) )
1222  return( status );
1223  }
1224 
1225  /* ECCs are somewhat weird in that the nominal key size is defined by
1226  executive fiat based on the curve type. For named curves this is
1227  fairly simple but for curves loaded as raw parameters we have to
1228  recover the nominal value from the ECC p parameter */
1229  if( pkcInfo->keySizeBits <= 0 )
1230  pkcInfo->keySizeBits = BN_num_bits( p );
1231 
1232  /* Enable side-channel protection if required */
1233  if( !( contextInfoPtr->flags & CONTEXT_FLAG_SIDECHANNELPROTECTION ) )
1234  return( CRYPT_OK );
1235  return( enableSidechannelProtection( pkcInfo,
1236  contextInfoPtr->capabilityInfo->cryptAlgo ) );
1237  }
1238 #endif /* USE_ECDH || USE_ECDSA */
Generated on Thu Jan 10 2013 10:00:45 for cryptlib by   doxygen 1.8.2