|
380
|
1 /** math functions **/ |
|
|
2 |
|
|
3 #define LTC_MP_LT -1 |
|
|
4 #define LTC_MP_EQ 0 |
|
|
5 #define LTC_MP_GT 1 |
|
|
6 |
|
|
7 #define LTC_MP_NO 0 |
|
|
8 #define LTC_MP_YES 1 |
|
|
9 |
|
|
10 #ifndef MECC |
|
|
11 typedef void ecc_point; |
|
|
12 #endif |
|
|
13 |
|
|
14 #ifndef MRSA |
|
|
15 typedef void rsa_key; |
|
|
16 #endif |
|
|
17 |
|
|
18 /** math descriptor */ |
|
|
19 typedef struct { |
|
|
20 /** Name of the math provider */ |
|
|
21 char *name; |
|
|
22 |
|
|
23 /** Bits per digit, amount of bits must fit in an unsigned long */ |
|
|
24 int bits_per_digit; |
|
|
25 |
|
|
26 /* ---- init/deinit functions ---- */ |
|
|
27 |
|
|
28 /** initialize a bignum |
|
|
29 @param a The number to initialize |
|
|
30 @return CRYPT_OK on success |
|
|
31 */ |
|
|
32 int (*init)(void **a); |
|
|
33 |
|
|
34 /** init copy |
|
|
35 @param dst The number to initialize and write to |
|
|
36 @param src The number to copy from |
|
|
37 @return CRYPT_OK on success |
|
|
38 */ |
|
|
39 int (*init_copy)(void **dst, void *src); |
|
|
40 |
|
|
41 /** deinit |
|
|
42 @param a The number to free |
|
|
43 @return CRYPT_OK on success |
|
|
44 */ |
|
|
45 void (*deinit)(void *a); |
|
|
46 |
|
|
47 /* ---- data movement ---- */ |
|
|
48 |
|
|
49 /** negate |
|
|
50 @param src The number to negate |
|
|
51 @param dst The destination |
|
|
52 @return CRYPT_OK on success |
|
|
53 */ |
|
|
54 int (*neg)(void *src, void *dst); |
|
|
55 |
|
|
56 /** copy |
|
|
57 @param src The number to copy from |
|
|
58 @param dst The number to write to |
|
|
59 @return CRYPT_OK on success |
|
|
60 */ |
|
|
61 int (*copy)(void *src, void *dst); |
|
|
62 |
|
|
63 /* ---- trivial low level functions ---- */ |
|
|
64 |
|
|
65 /** set small constant |
|
|
66 @param a Number to write to |
|
|
67 @param n Source upto bits_per_digit (actually meant for very small constants) |
|
|
68 @return CRYPT_OK on succcess |
|
|
69 */ |
|
|
70 int (*set_int)(void *a, unsigned long n); |
|
|
71 |
|
|
72 /** get small constant |
|
|
73 @param a Number to read, only fetches upto bits_per_digit from the number |
|
|
74 @return The lower bits_per_digit of the integer (unsigned) |
|
|
75 */ |
|
|
76 unsigned long (*get_int)(void *a); |
|
|
77 |
|
|
78 /** get digit n |
|
|
79 @param a The number to read from |
|
|
80 @param n The number of the digit to fetch |
|
|
81 @return The bits_per_digit sized n'th digit of a |
|
|
82 */ |
|
|
83 unsigned long (*get_digit)(void *a, int n); |
|
|
84 |
|
|
85 /** Get the number of digits that represent the number |
|
|
86 @param a The number to count |
|
|
87 @return The number of digits used to represent the number |
|
|
88 */ |
|
|
89 int (*get_digit_count)(void *a); |
|
|
90 |
|
|
91 /** compare two integers |
|
|
92 @param a The left side integer |
|
|
93 @param b The right side integer |
|
|
94 @return LTC_MP_LT if a < b, LTC_MP_GT if a > b and LTC_MP_EQ otherwise. (signed comparison) |
|
|
95 */ |
|
|
96 int (*compare)(void *a, void *b); |
|
|
97 |
|
|
98 /** compare against int |
|
|
99 @param a The left side integer |
|
|
100 @param b The right side integer (upto bits_per_digit) |
|
|
101 @return LTC_MP_LT if a < b, LTC_MP_GT if a > b and LTC_MP_EQ otherwise. (signed comparison) |
|
|
102 */ |
|
|
103 int (*compare_d)(void *a, unsigned long n); |
|
|
104 |
|
|
105 /** Count the number of bits used to represent the integer |
|
|
106 @param a The integer to count |
|
|
107 @return The number of bits required to represent the integer |
|
|
108 */ |
|
|
109 int (*count_bits)(void * a); |
|
|
110 |
|
|
111 /** Count the number of LSB bits which are zero |
|
|
112 @param a The integer to count |
|
|
113 @return The number of contiguous zero LSB bits |
|
|
114 */ |
|
|
115 int (*count_lsb_bits)(void *a); |
|
|
116 |
|
|
117 /** Compute a power of two |
|
|
118 @param a The integer to store the power in |
|
|
119 @param n The power of two you want to store (a = 2^n) |
|
|
120 @return CRYPT_OK on success |
|
|
121 */ |
|
|
122 int (*twoexpt)(void *a , int n); |
|
|
123 |
|
|
124 /* ---- radix conversions ---- */ |
|
|
125 |
|
|
126 /** read ascii string |
|
|
127 @param a The integer to store into |
|
|
128 @param str The string to read |
|
|
129 @param radix The radix the integer has been represented in (2-64) |
|
|
130 @return CRYPT_OK on success |
|
|
131 */ |
|
|
132 int (*read_radix)(void *a, const char *str, int radix); |
|
|
133 |
|
|
134 /** write number to string |
|
|
135 @param a The integer to store |
|
|
136 @param str The destination for the string |
|
|
137 @param radix The radix the integer is to be represented in (2-64) |
|
|
138 @return CRYPT_OK on success |
|
|
139 */ |
|
|
140 int (*write_radix)(void *a, char *str, int radix); |
|
|
141 |
|
|
142 /** get size as unsigned char string |
|
|
143 @param a The integer to get the size (when stored in array of octets) |
|
|
144 @return The length of the integer |
|
|
145 */ |
|
|
146 unsigned long (*unsigned_size)(void *a); |
|
|
147 |
|
|
148 /** store an integer as an array of octets |
|
|
149 @param src The integer to store |
|
|
150 @param dst The buffer to store the integer in |
|
|
151 @return CRYPT_OK on success |
|
|
152 */ |
|
|
153 int (*unsigned_write)(void *src, unsigned char *dst); |
|
|
154 |
|
|
155 /** read an array of octets and store as integer |
|
|
156 @param dst The integer to load |
|
|
157 @param src The array of octets |
|
|
158 @param len The number of octets |
|
|
159 @return CRYPT_OK on success |
|
|
160 */ |
|
|
161 int (*unsigned_read)(void *dst, unsigned char *src, unsigned long len); |
|
|
162 |
|
|
163 /* ---- basic math ---- */ |
|
|
164 |
|
|
165 /** add two integers |
|
|
166 @param a The first source integer |
|
|
167 @param b The second source integer |
|
|
168 @param c The destination of "a + b" |
|
|
169 @return CRYPT_OK on success |
|
|
170 */ |
|
|
171 int (*add)(void *a, void *b, void *c); |
|
|
172 |
|
|
173 |
|
|
174 /** add two integers |
|
|
175 @param a The first source integer |
|
|
176 @param b The second source integer (single digit of upto bits_per_digit in length) |
|
|
177 @param c The destination of "a + b" |
|
|
178 @return CRYPT_OK on success |
|
|
179 */ |
|
|
180 int (*addi)(void *a, unsigned long b, void *c); |
|
|
181 |
|
|
182 /** subtract two integers |
|
|
183 @param a The first source integer |
|
|
184 @param b The second source integer |
|
|
185 @param c The destination of "a - b" |
|
|
186 @return CRYPT_OK on success |
|
|
187 */ |
|
|
188 int (*sub)(void *a, void *b, void *c); |
|
|
189 |
|
|
190 /** subtract two integers |
|
|
191 @param a The first source integer |
|
|
192 @param b The second source integer (single digit of upto bits_per_digit in length) |
|
|
193 @param c The destination of "a - b" |
|
|
194 @return CRYPT_OK on success |
|
|
195 */ |
|
|
196 int (*subi)(void *a, unsigned long b, void *c); |
|
|
197 |
|
|
198 /** multiply two integers |
|
|
199 @param a The first source integer |
|
|
200 @param b The second source integer (single digit of upto bits_per_digit in length) |
|
|
201 @param c The destination of "a * b" |
|
|
202 @return CRYPT_OK on success |
|
|
203 */ |
|
|
204 int (*mul)(void *a, void *b, void *c); |
|
|
205 |
|
|
206 /** multiply two integers |
|
|
207 @param a The first source integer |
|
|
208 @param b The second source integer (single digit of upto bits_per_digit in length) |
|
|
209 @param c The destination of "a * b" |
|
|
210 @return CRYPT_OK on success |
|
|
211 */ |
|
|
212 int (*muli)(void *a, unsigned long b, void *c); |
|
|
213 |
|
|
214 /** Square an integer |
|
|
215 @param a The integer to square |
|
|
216 @param b The destination |
|
|
217 @return CRYPT_OK on success |
|
|
218 */ |
|
|
219 int (*sqr)(void *a, void *b); |
|
|
220 |
|
|
221 /** Divide an integer |
|
|
222 @param a The dividend |
|
|
223 @param b The divisor |
|
|
224 @param c The quotient (can be NULL to signify don't care) |
|
|
225 @param d The remainder (can be NULL to signify don't care) |
|
|
226 @return CRYPT_OK on success |
|
|
227 */ |
|
|
228 int (*mpdiv)(void *a, void *b, void *c, void *d); |
|
|
229 |
|
|
230 /** divide by two |
|
|
231 @param a The integer to divide (shift right) |
|
|
232 @param b The destination |
|
|
233 @return CRYPT_OK on success |
|
|
234 */ |
|
|
235 int (*div_2)(void *a, void *b); |
|
|
236 |
|
|
237 /** Get remainder (small value) |
|
|
238 @param a The integer to reduce |
|
|
239 @param b The modulus (upto bits_per_digit in length) |
|
|
240 @param c The destination for the residue |
|
|
241 @return CRYPT_OK on success |
|
|
242 */ |
|
|
243 int (*modi)(void *a, unsigned long b, unsigned long *c); |
|
|
244 |
|
|
245 /** gcd |
|
|
246 @param a The first integer |
|
|
247 @param b The second integer |
|
|
248 @param c The destination for (a, b) |
|
|
249 @return CRYPT_OK on success |
|
|
250 */ |
|
|
251 int (*gcd)(void *a, void *b, void *c); |
|
|
252 |
|
|
253 /** lcm |
|
|
254 @param a The first integer |
|
|
255 @param b The second integer |
|
|
256 @param c The destination for [a, b] |
|
|
257 @return CRYPT_OK on success |
|
|
258 */ |
|
|
259 int (*lcm)(void *a, void *b, void *c); |
|
|
260 |
|
|
261 /** Modular multiplication |
|
|
262 @param a The first source |
|
|
263 @param b The second source |
|
|
264 @param c The modulus |
|
|
265 @param d The destination (a*b mod c) |
|
|
266 @return CRYPT_OK on success |
|
|
267 */ |
|
|
268 int (*mulmod)(void *a, void *b, void *c, void *d); |
|
|
269 |
|
|
270 /** Modular squaring |
|
|
271 @param a The first source |
|
|
272 @param b The modulus |
|
|
273 @param c The destination (a*a mod b) |
|
|
274 @return CRYPT_OK on success |
|
|
275 */ |
|
|
276 int (*sqrmod)(void *a, void *b, void *c); |
|
|
277 |
|
|
278 /** Modular inversion |
|
|
279 @param a The value to invert |
|
|
280 @param b The modulus |
|
|
281 @param c The destination (1/a mod b) |
|
|
282 @return CRYPT_OK on success |
|
|
283 */ |
|
|
284 int (*invmod)(void *, void *, void *); |
|
|
285 |
|
|
286 /* ---- reduction ---- */ |
|
|
287 |
|
|
288 /** setup montgomery |
|
|
289 @param a The modulus |
|
|
290 @param b The destination for the reduction digit |
|
|
291 @return CRYPT_OK on success |
|
|
292 */ |
|
|
293 int (*montgomery_setup)(void *a, void **b); |
|
|
294 |
|
|
295 /** get normalization value |
|
|
296 @param a The destination for the normalization value |
|
|
297 @param b The modulus |
|
|
298 @return CRYPT_OK on success |
|
|
299 */ |
|
|
300 int (*montgomery_normalization)(void *a, void *b); |
|
|
301 |
|
|
302 /** reduce a number |
|
|
303 @param a The number [and dest] to reduce |
|
|
304 @param b The modulus |
|
|
305 @param c The value "b" from montgomery_setup() |
|
|
306 @return CRYPT_OK on success |
|
|
307 */ |
|
|
308 int (*montgomery_reduce)(void *a, void *b, void *c); |
|
|
309 |
|
|
310 /** clean up (frees memory) |
|
|
311 @param a The value "b" from montgomery_setup() |
|
|
312 @return CRYPT_OK on success |
|
|
313 */ |
|
|
314 void (*montgomery_deinit)(void *a); |
|
|
315 |
|
|
316 /* ---- exponentiation ---- */ |
|
|
317 |
|
|
318 /** Modular exponentiation |
|
|
319 @param a The base integer |
|
|
320 @param b The power (can be negative) integer |
|
|
321 @param c The modulus integer |
|
|
322 @param d The destination |
|
|
323 @return CRYPT_OK on success |
|
|
324 */ |
|
|
325 int (*exptmod)(void *a, void *b, void *c, void *d); |
|
|
326 |
|
|
327 /** Primality testing |
|
|
328 @param a The integer to test |
|
|
329 @param b The destination of the result (FP_YES if prime) |
|
|
330 @return CRYPT_OK on success |
|
|
331 */ |
|
|
332 int (*isprime)(void *a, int *b); |
|
|
333 |
|
|
334 /* ---- (optional) ecc point math ---- */ |
|
|
335 |
|
|
336 /** ECC GF(p) point multiplication (from the NIST curves) |
|
|
337 @param k The integer to multiply the point by |
|
|
338 @param G The point to multiply |
|
|
339 @param R The destination for kG |
|
|
340 @param modulus The modulus for the field |
|
|
341 @param map Boolean indicated whether to map back to affine or not (can be ignored if you work in affine only) |
|
|
342 @return CRYPT_OK on success |
|
|
343 */ |
|
|
344 int (*ecc_ptmul)(void *k, ecc_point *G, ecc_point *R, void *modulus, int map); |
|
|
345 |
|
|
346 /** ECC GF(p) point addition |
|
|
347 @param P The first point |
|
|
348 @param Q The second point |
|
|
349 @param R The destination of P + Q |
|
|
350 @param modulus The modulus |
|
|
351 @param mp The "b" value from montgomery_setup() |
|
|
352 @return CRYPT_OK on success |
|
|
353 */ |
|
|
354 int (*ecc_ptadd)(ecc_point *P, ecc_point *Q, ecc_point *R, void *modulus, void *mp); |
|
|
355 |
|
|
356 /** ECC GF(p) point double |
|
|
357 @param P The first point |
|
|
358 @param R The destination of 2P |
|
|
359 @param modulus The modulus |
|
|
360 @param mp The "b" value from montgomery_setup() |
|
|
361 @return CRYPT_OK on success |
|
|
362 */ |
|
|
363 int (*ecc_ptdbl)(ecc_point *P, ecc_point *R, void *modulus, void *mp); |
|
|
364 |
|
|
365 /** ECC mapping from projective to affine, currently uses (x,y,z) => (x/z^2, y/z^3, 1) |
|
|
366 @param P The point to map |
|
|
367 @param modulus The modulus |
|
|
368 @param mp The "b" value from montgomery_setup() |
|
|
369 @return CRYPT_OK on success |
|
|
370 @remark The mapping can be different but keep in mind a ecc_point only has three |
|
|
371 integers (x,y,z) so if you use a different mapping you have to make it fit. |
|
|
372 */ |
|
|
373 int (*ecc_map)(ecc_point *P, void *modulus, void *mp); |
|
|
374 |
|
|
375 /** Computes kA*A + kB*B = C using Shamir's Trick |
|
|
376 @param A First point to multiply |
|
|
377 @param kA What to multiple A by |
|
|
378 @param B Second point to multiply |
|
|
379 @param kB What to multiple B by |
|
|
380 @param C [out] Destination point (can overlap with A or B |
|
|
381 @param modulus Modulus for curve |
|
|
382 @return CRYPT_OK on success |
|
|
383 */ |
|
|
384 int (*ecc_mul2add)(ecc_point *A, void *kA, |
|
|
385 ecc_point *B, void *kB, |
|
|
386 ecc_point *C, |
|
|
387 void *modulus); |
|
|
388 |
|
|
389 /* ---- (optional) rsa optimized math (for internal CRT) ---- */ |
|
|
390 |
|
|
391 /** RSA Key Generation |
|
|
392 @param prng An active PRNG state |
|
|
393 @param wprng The index of the PRNG desired |
|
|
394 @param size The size of the modulus (key size) desired (octets) |
|
|
395 @param e The "e" value (public key). e==65537 is a good choice |
|
|
396 @param key [out] Destination of a newly created private key pair |
|
|
397 @return CRYPT_OK if successful, upon error all allocated ram is freed |
|
|
398 */ |
|
|
399 int (*rsa_keygen)(prng_state *prng, int wprng, int size, long e, rsa_key *key); |
|
|
400 |
|
|
401 |
|
|
402 /** RSA exponentiation |
|
|
403 @param in The octet array representing the base |
|
|
404 @param inlen The length of the input |
|
|
405 @param out The destination (to be stored in an octet array format) |
|
|
406 @param outlen The length of the output buffer and the resulting size (zero padded to the size of the modulus) |
|
|
407 @param which PK_PUBLIC for public RSA and PK_PRIVATE for private RSA |
|
|
408 @param key The RSA key to use |
|
|
409 @return CRYPT_OK on success |
|
|
410 */ |
|
|
411 int (*rsa_me)(const unsigned char *in, unsigned long inlen, |
|
|
412 unsigned char *out, unsigned long *outlen, int which, |
|
|
413 rsa_key *key); |
|
|
414 } ltc_math_descriptor; |
|
|
415 |
|
|
416 extern ltc_math_descriptor ltc_mp; |
|
|
417 |
|
|
418 int ltc_init_multi(void **a, ...); |
|
|
419 void ltc_deinit_multi(void *a, ...); |
|
|
420 |
|
|
421 #ifdef LTM_DESC |
|
|
422 extern const ltc_math_descriptor ltm_desc; |
|
|
423 #endif |
|
|
424 |
|
|
425 #ifdef TFM_DESC |
|
|
426 extern const ltc_math_descriptor tfm_desc; |
|
|
427 #endif |
|
|
428 |
|
|
429 #ifdef GMP_DESC |
|
|
430 extern const ltc_math_descriptor gmp_desc; |
|
|
431 #endif |
|
|
432 |
|
|
433 #if !defined(DESC_DEF_ONLY) && defined(LTC_SOURCE) |
|
|
434 |
|
|
435 #define MP_DIGIT_BIT ltc_mp.bits_per_digit |
|
|
436 |
|
|
437 /* some handy macros */ |
|
|
438 #define mp_init(a) ltc_mp.init(a) |
|
|
439 #define mp_init_multi ltc_init_multi |
|
|
440 #define mp_clear(a) ltc_mp.deinit(a) |
|
|
441 #define mp_clear_multi ltc_deinit_multi |
|
|
442 #define mp_init_copy(a, b) ltc_mp.init_copy(a, b) |
|
|
443 |
|
|
444 #define mp_neg(a, b) ltc_mp.neg(a, b) |
|
|
445 #define mp_copy(a, b) ltc_mp.copy(a, b) |
|
|
446 |
|
|
447 #define mp_set(a, b) ltc_mp.set_int(a, b) |
|
|
448 #define mp_set_int(a, b) ltc_mp.set_int(a, b) |
|
|
449 #define mp_get_int(a) ltc_mp.get_int(a) |
|
|
450 #define mp_get_digit(a, n) ltc_mp.get_digit(a, n) |
|
|
451 #define mp_get_digit_count(a) ltc_mp.get_digit_count(a) |
|
|
452 #define mp_cmp(a, b) ltc_mp.compare(a, b) |
|
|
453 #define mp_cmp_d(a, b) ltc_mp.compare_d(a, b) |
|
|
454 #define mp_count_bits(a) ltc_mp.count_bits(a) |
|
|
455 #define mp_cnt_lsb(a) ltc_mp.count_lsb_bits(a) |
|
|
456 #define mp_2expt(a, b) ltc_mp.twoexpt(a, b) |
|
|
457 |
|
|
458 #define mp_read_radix(a, b, c) ltc_mp.read_radix(a, b, c) |
|
|
459 #define mp_toradix(a, b, c) ltc_mp.write_radix(a, b, c) |
|
|
460 #define mp_unsigned_bin_size(a) ltc_mp.unsigned_size(a) |
|
|
461 #define mp_to_unsigned_bin(a, b) ltc_mp.unsigned_write(a, b) |
|
|
462 #define mp_read_unsigned_bin(a, b, c) ltc_mp.unsigned_read(a, b, c) |
|
|
463 |
|
|
464 #define mp_add(a, b, c) ltc_mp.add(a, b, c) |
|
|
465 #define mp_add_d(a, b, c) ltc_mp.addi(a, b, c) |
|
|
466 #define mp_sub(a, b, c) ltc_mp.sub(a, b, c) |
|
|
467 #define mp_sub_d(a, b, c) ltc_mp.subi(a, b, c) |
|
|
468 #define mp_mul(a, b, c) ltc_mp.mul(a, b, c) |
|
|
469 #define mp_mul_d(a, b, c) ltc_mp.muli(a, b, c) |
|
|
470 #define mp_sqr(a, b) ltc_mp.sqr(a, b) |
|
|
471 #define mp_div(a, b, c, d) ltc_mp.mpdiv(a, b, c, d) |
|
|
472 #define mp_div_2(a, b) ltc_mp.div_2(a, b) |
|
|
473 #define mp_mod(a, b, c) ltc_mp.mpdiv(a, b, NULL, c) |
|
|
474 #define mp_mod_d(a, b, c) ltc_mp.modi(a, b, c) |
|
|
475 #define mp_gcd(a, b, c) ltc_mp.gcd(a, b, c) |
|
|
476 #define mp_lcm(a, b, c) ltc_mp.lcm(a, b, c) |
|
|
477 |
|
|
478 #define mp_mulmod(a, b, c, d) ltc_mp.mulmod(a, b, c, d) |
|
|
479 #define mp_sqrmod(a, b, c) ltc_mp.sqrmod(a, b, c) |
|
|
480 #define mp_invmod(a, b, c) ltc_mp.invmod(a, b, c) |
|
|
481 |
|
|
482 #define mp_montgomery_setup(a, b) ltc_mp.montgomery_setup(a, b) |
|
|
483 #define mp_montgomery_normalization(a, b) ltc_mp.montgomery_normalization(a, b) |
|
|
484 #define mp_montgomery_reduce(a, b, c) ltc_mp.montgomery_reduce(a, b, c) |
|
|
485 #define mp_montgomery_free(a) ltc_mp.montgomery_deinit(a) |
|
|
486 |
|
|
487 #define mp_exptmod(a,b,c,d) ltc_mp.exptmod(a,b,c,d) |
|
|
488 #define mp_prime_is_prime(a, b, c) ltc_mp.isprime(a, c) |
|
|
489 |
|
|
490 #define mp_iszero(a) (mp_cmp_d(a, 0) == LTC_MP_EQ ? LTC_MP_YES : LTC_MP_NO) |
|
|
491 #define mp_isodd(a) (mp_get_digit_count(a) > 0 ? (mp_get_digit(a, 0) & 1 ? LTC_MP_YES : LTC_MP_NO) : LTC_MP_NO) |
|
|
492 #define mp_exch(a, b) do { void *ABC__tmp = a; a = b; b = ABC__tmp; } while(0); |
|
|
493 |
|
|
494 #define mp_tohex(a, b) mp_toradix(a, b, 16) |
|
|
495 |
|
|
496 #endif |
|
|
497 |
|
|
498 /* $Source: /cvs/libtom/libtomcrypt/src/headers/tomcrypt_math.h,v $ */ |
|
|
499 /* $Revision: 1.43 $ */ |
|
|
500 /* $Date: 2006/12/02 19:23:13 $ */ |
