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
|
/*
* Verse routines for big integer operations.
* Handy in heavy encryption done during connect.
*/
#include <limits.h>
#include "v_randgen.h"
/* ----------------------------------------------------------------------------------------- */
typedef unsigned short VBigDig; /* Type used to hold one digit of a bignum. */
typedef unsigned int VBigDigs; /* Should hold precisely two digits. */
#define V_BIGBITS (CHAR_BIT * sizeof (VBigDig))
/* Use this macro to initialize big number variables, like so:
* VBigDig BIGNUM(foo, 128), BIGNUM(bar, 256);
* Creates automatic variables 'foo' of 128 bits, and 'bar' of 256.
*
* Note that 'bits' must be a multiple of V_BIGBITS, completely
* arbitrary number sizes are not supported by this module.
*/
#define VBIGNUM(n, bits) n[1 + (bits / V_BIGBITS)] = { bits / V_BIGBITS }
/* ----------------------------------------------------------------------------------------- */
/* Import/export numbers from raw bits. The number x must have been allocated
* with the desired number of bits to read/write.
*/
extern void v_bignum_raw_import(VBigDig *x, const void *bits);
extern void v_bignum_raw_export(const VBigDig *x, void *bits);
/* Initializers. */
extern void v_bignum_set_zero(VBigDig *x);
extern void v_bignum_set_one(VBigDig *x);
extern void v_bignum_set_digit(VBigDig *x, VBigDig y);
extern void v_bignum_set_string(VBigDig *x, const char *string); /* Decimal. */
extern void v_bignum_set_string_hex(VBigDig *x, const char *string);
extern void v_bignum_set_bignum(VBigDig *x, const VBigDig *y);
/* x = <bits> most significant <bits> bits of <y>, starting at <msb>. Right-
* adjusted in x, so that e.g. y=0xcafebabec001 msb=47 bits=16 gives x=0xcafe.
*/
extern void v_bignum_set_bignum_part(VBigDig *x, const VBigDig *y,
unsigned int msb, unsigned int bits);
extern void v_bignum_set_random(VBigDig *x, VRandGen *gen);
/* Handy during debugging. */
extern void v_bignum_print_hex(const VBigDig *x);
extern void v_bignum_print_hex_lf(const VBigDig *x);
/* Bit operators. */
extern void v_bignum_not(VBigDig *x);
extern int v_bignum_bit_test(const VBigDig *x, unsigned int bit);
extern void v_bignum_bit_set(VBigDig *x, unsigned int bit);
extern int v_bignum_bit_msb(const VBigDig *x);
extern int v_bignum_bit_size(const VBigDig *x);
extern void v_bignum_bit_shift_left(VBigDig *x, unsigned int count);
extern void v_bignum_bit_shift_left_1(VBigDig *x);
extern void v_bignum_bit_shift_right(VBigDig *x, unsigned int count);
/* Comparators. */
extern int v_bignum_eq_zero(const VBigDig *x); /* x == 0. */
extern int v_bignum_eq_one(const VBigDig *x); /* x == 1. */
extern int v_bignum_eq(const VBigDig *x, const VBigDig *y); /* x == y. */
extern int v_bignum_gte(const VBigDig *x, const VBigDig *y); /* x >= y. */
/* Number vs single-digit arithmetic. */
extern void v_bignum_add_digit(VBigDig *x, VBigDig y); /* x += y. */
extern void v_bignum_sub_digit(VBigDig *x, VBigDig y); /* x -= y. */
extern void v_bignum_mul_digit(VBigDig *x, VBigDig y); /* x *= y. */
/* Arithmetic. */
extern void v_bignum_add(VBigDig *x, const VBigDig *y); /* x += y. */
extern void v_bignum_sub(VBigDig *x, const VBigDig *y); /* x -= y. */
extern void v_bignum_mul(VBigDig *x, const VBigDig *y); /* x *= y. */
extern void v_bignum_div(VBigDig *x, const VBigDig *y, VBigDig *remainder);
extern void v_bignum_mod(VBigDig *x, const VBigDig *y); /* x %= y. */
/* Barrett reducer for fast x % m computation. Requires precalcing step. */
extern const VBigDig * v_bignum_reduce_begin(const VBigDig *m);
extern void v_bignum_reduce(VBigDig *x, const VBigDig *m, const VBigDig *mu);
extern void v_bignum_reduce_end(const VBigDig *mu);
/* Compute x *= x, assuming x only uses half of its actual size. */
extern void v_bignum_square_half(VBigDig *x);
/* Compute pow(x, y, n) == (x raised to the y:th power) modulo n. */
extern void v_bignum_pow_mod(VBigDig *x, const VBigDig *y, const VBigDig *n);
|
