Mercurial > dropbear

comparison libtomcrypt/src/headers/tomcrypt_math.h @ 382:0cbe8f6dbf9e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
propagate from branch 'au.asn.ucc.matt.ltc.dropbear' (head 2af22fb4e878750b88f80f90d439b316d229796f) to branch 'au.asn.ucc.matt.dropbear' (head 02c413252c90e9de8e03d91e9939dde3029f5c0a)
author Matt Johnston <matt@ucc.asn.au>
date Thu, 11 Jan 2007 02:41:05 +0000
parents
children a05fb340a95d
comparison
equal deleted inserted replaced
379:b66a00272a90 382:0cbe8f6dbf9e
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 $ */