Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 1 | /* |
| 2 | * bn.h - the interface to the bignum routines. |
| 3 | * All functions which return ints can potentially allocate memory |
| 4 | * and return -1 if they are unable to. All "const" arguments |
| 5 | * are unmodified. |
| 6 | * |
| 7 | * This is not particularly asymmetric, as some operations are of the |
| 8 | * form a = b @ c, while others do a @= b. In general, outputs may not |
| 9 | * point to the same struct BigNums as inputs, except as specified |
| 10 | * below. This relationship is referred to as "being the same as". |
| 11 | * This is not numerical equivalence. |
| 12 | * |
| 13 | * The "Q" operations take "unsigned" inputs. Higher values of the |
| 14 | * extra input may work on some implementations, but 65535 is the |
| 15 | * highest portable value. Just because UNSIGNED_MAX is larger than |
| 16 | * that, or you know that the word size of the library is larger than that, |
| 17 | * that, does *not* mean it's allowed. |
| 18 | */ |
| 19 | #ifndef BN_H |
| 20 | #define BN_H |
| 21 | |
| 22 | #ifdef __cplusplus |
| 23 | extern "C" |
| 24 | { |
| 25 | #endif |
| 26 | |
| 27 | struct BigNum { |
| 28 | void *ptr; |
| 29 | unsigned size; /* Note: in (variable-sized) words */ |
| 30 | unsigned allocated; |
| 31 | }; |
| 32 | |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 33 | /* |
| 34 | * User-supplied function: if non-NULL, this is called during long-running |
| 35 | * computations. You may put Yield() calls in here to give CPU time to |
| 36 | * other processes. You may also force the computation to be aborted, |
| 37 | * by returning a value < 0, which will be the return value of the |
| 38 | * bnXXX call. (You probably want the value to be someting other than |
| 39 | * -1, to distinguish it from a n out-of-memory error.) |
| 40 | * |
| 41 | * The functions that this is called from, and the intervals at which it |
| 42 | * is called, are not well defined, just "reasonably often". (Currently, |
| 43 | * once per exponent bit in nodular exponentiation, and once per two |
| 44 | * divisions in GCD and inverse computation.) |
| 45 | */ |
| 46 | extern int (*bnYield)(void); |
| 47 | |
| 48 | /* Functions */ |
| 49 | |
| 50 | /* |
| 51 | * You usually never have to call this function explicitly, as |
| 52 | * bnBegin() takes care of it. If the program jumps to address 0, |
| 53 | * this function has bot been called. |
| 54 | */ |
| 55 | void bnInit(void); |
| 56 | |
| 57 | /* |
| 58 | * This initializes an empty struct BigNum to a zero value. |
| 59 | * Do not use this on a BigNum which has had a value stored in it! |
| 60 | */ |
| 61 | void bnBegin(struct BigNum *bn); |
| 62 | |
| 63 | /* Swap two BigNums. Cheap. */ |
| 64 | void bnSwap(struct BigNum *a, struct BigNum *b); |
| 65 | |
| 66 | /* Reset an initialized bigNum to empty, pending deallocation. */ |
| 67 | extern void (*bnEnd)(struct BigNum *bn); |
| 68 | |
| 69 | /* |
| 70 | * If you know you'll need space in the number soon, you can use this function |
| 71 | * to ensure that there is room for at least "bits" bits. Optional. |
| 72 | * Returns <0 on out of memory, but the value is unaffected. |
| 73 | */ |
| 74 | extern int (*bnPrealloc)(struct BigNum *bn, unsigned bits); |
| 75 | |
| 76 | /* Hopefully obvious. dest = src. dest may be the same as src. */ |
| 77 | extern int (*bnCopy)(struct BigNum *dest, struct BigNum const *src); |
| 78 | |
| 79 | /* |
| 80 | * Mostly done automatically, but this removes leading zero words from |
| 81 | * the internal representation of the BigNum. Use is unclear. |
| 82 | */ |
| 83 | extern void (*bnNorm)(struct BigNum *bn); |
| 84 | |
| 85 | /* |
| 86 | * Move bytes between the given buffer and the given BigNum encoded in |
| 87 | * base 256. I.e. after either of these, the buffer will be equal to |
| 88 | * (bn / 256^lsbyte) % 256^len. The difference is which is altered to |
| 89 | * match the other! |
| 90 | */ |
| 91 | extern void (*bnExtractBigBytes)(struct BigNum const *bn, |
| 92 | unsigned char *dest, unsigned lsbyte, unsigned len); |
| 93 | extern int (*bnInsertBigBytes)(struct BigNum *bn, unsigned char const *src, |
| 94 | unsigned lsbyte, unsigned len); |
| 95 | |
| 96 | /* The same, but the buffer is little-endian. */ |
| 97 | extern void (*bnExtractLittleBytes)(struct BigNum const *bn, |
| 98 | unsigned char *dest, unsigned lsbyte, unsigned len); |
| 99 | extern int (*bnInsertLittleBytes)(struct BigNum *bn, unsigned char const *src, |
| 100 | unsigned lsbyte, unsigned len); |
| 101 | |
| 102 | /* Return the least-significant bits (at least 16) of the BigNum */ |
| 103 | extern unsigned (*bnLSWord)(struct BigNum const *src); |
| 104 | |
| 105 | /* Return the selected bit of the BigNum (bit 0 is bn mod 2) */ |
| 106 | extern int (*bnReadBit)(struct BigNum const *bn, unsigned bit); |
| 107 | |
| 108 | /* |
| 109 | * Return the number of significant bits in the BigNum. |
| 110 | * 0 or 1+floor(log2(src)) |
| 111 | */ |
| 112 | extern unsigned (*bnBits)(struct BigNum const *src); |
| 113 | #define bnBytes(bn) ((bnBits(bn)+7)/8) |
| 114 | |
| 115 | /* |
| 116 | * dest += src. dest and src may be the same. Guaranteed not to |
| 117 | * allocate memory unnecessarily, so if you're sure bnBits(dest) |
| 118 | * won't change, you don't need to check the return value. |
| 119 | */ |
| 120 | extern int (*bnAdd)(struct BigNum *dest, struct BigNum const *src); |
| 121 | |
| 122 | /* |
| 123 | * dest -= src. dest and src may be the same, but bnSetQ(dest, 0) is faster. |
| 124 | * if dest < src, returns +1 and sets dest = src-dest. |
| 125 | */ |
| 126 | extern int (*bnSub)(struct BigNum *dest, struct BigNum const *src); |
| 127 | |
| 128 | /* Return sign (-1, 0, +1) of a-b. a <=> b --> bnCmpQ(a, b) <=> 0 */ |
| 129 | extern int (*bnCmpQ)(struct BigNum const *a, unsigned b); |
| 130 | |
| 131 | /* dest = src, where 0 <= src < 2^16. */ |
| 132 | extern int (*bnSetQ)(struct BigNum *dest, unsigned src); |
| 133 | |
| 134 | /* dest += src, where 0 <= src < 2^16 */ |
| 135 | extern int (*bnAddQ)(struct BigNum *dest, unsigned src); |
| 136 | |
| 137 | /* dest -= src, where 0 <= src < 2^16 */ |
| 138 | extern int (*bnSubQ)(struct BigNum *dest, unsigned src); |
| 139 | |
| 140 | /* Return sign (-1, 0, +1) of a-b. a <=> b --> bnCmp(a, b) <=> 0 */ |
| 141 | extern int (*bnCmp)(struct BigNum const *a, struct BigNum const *b); |
| 142 | |
| 143 | /* dest = src^2. dest may be the same as src, but it costs time. */ |
| 144 | extern int (*bnSquare)(struct BigNum *dest, struct BigNum const *src); |
| 145 | |
| 146 | /* dest = a * b. dest may be the same as a or b, but it costs time. */ |
| 147 | extern int (*bnMul)(struct BigNum *dest, struct BigNum const *a, |
| 148 | struct BigNum const *b); |
| 149 | |
| 150 | /* dest = a * b, where 0 <= b < 2^16. dest and a may be the same. */ |
| 151 | extern int (*bnMulQ)(struct BigNum *dest, struct BigNum const *a, unsigned b); |
| 152 | |
| 153 | /* |
| 154 | * q = n/d, r = n%d. r may be the same as n, but not d, |
| 155 | * and q may not be the same as n or d. |
| 156 | * re-entrancy issue: this temporarily modifies d, but restores |
| 157 | * it for return. |
| 158 | */ |
| 159 | extern int (*bnDivMod)(struct BigNum *q, struct BigNum *r, |
| 160 | struct BigNum const *n, struct BigNum const *d); |
| 161 | /* |
| 162 | * dest = src % d. dest and src may be the same, but not dest and d. |
| 163 | * re-entrancy issue: this temporarily modifies d, but restores |
| 164 | * it for return. |
| 165 | */ |
| 166 | extern int (*bnMod)(struct BigNum *dest, struct BigNum const *src, |
| 167 | struct BigNum const *d); |
| 168 | |
| 169 | /* return src % d, where 0 <= d < 2^16. */ |
| 170 | extern unsigned int (*bnModQ)(struct BigNum const *src, unsigned d); |
| 171 | |
| 172 | /* n = n^exp, modulo "mod" "mod" *must* be odd */ |
| 173 | extern int (*bnExpMod)(struct BigNum *result, struct BigNum const *n, |
| 174 | struct BigNum const *exp, struct BigNum const *mod); |
| 175 | |
| 176 | /* |
| 177 | * dest = n1^e1 * n2^e2, modulo "mod". "mod" *must* be odd. |
| 178 | * dest may be the same as n1 or n2. |
| 179 | */ |
| 180 | extern int (*bnDoubleExpMod)(struct BigNum *dest, |
| 181 | struct BigNum const *n1, struct BigNum const *e1, |
| 182 | struct BigNum const *n2, struct BigNum const *e2, |
| 183 | struct BigNum const *mod); |
| 184 | |
| 185 | /* n = 2^exp, modulo "mod" "mod" *must* be odd */ |
| 186 | extern int (*bnTwoExpMod)(struct BigNum *n, struct BigNum const *exp, |
| 187 | struct BigNum const *mod); |
| 188 | |
| 189 | /* dest = gcd(a, b). The inputs may overlap arbitrarily. */ |
| 190 | extern int (*bnGcd)(struct BigNum *dest, struct BigNum const *a, |
| 191 | struct BigNum const *b); |
| 192 | |
| 193 | /* dest = src^-1, modulo "mod". dest may be the same as src. */ |
| 194 | extern int (*bnInv)(struct BigNum *dest, struct BigNum const *src, |
| 195 | struct BigNum const *mod); |
| 196 | |
| 197 | /* Shift dest left "amt" places */ |
| 198 | extern int (*bnLShift)(struct BigNum *dest, unsigned amt); |
| 199 | /* Shift dest right "amt" places, discarding low-order bits */ |
| 200 | extern void (*bnRShift)(struct BigNum *dest, unsigned amt); |
| 201 | |
| 202 | /* For the largest 2^k that divides n, divide n by it and return k. */ |
| 203 | extern unsigned (*bnMakeOdd)(struct BigNum *n); |
| 204 | |
| 205 | /* |
| 206 | * Precomputed data for rapid base^exp (mod mod) computation with fixed |
| 207 | * base and mod. |
| 208 | */ |
| 209 | struct BnBasePrecomp { |
| 210 | void *array; /* Ponter to array of pointers to words */ |
| 211 | unsigned msize; /* Words in modulis (normalized) */ |
| 212 | unsigned bits; /* Bits per array element */ |
| 213 | unsigned maxebits; /* Maximum exponent bits */ |
| 214 | unsigned entries; /* Number of entries */ |
| 215 | unsigned arraysize; |
| 216 | }; |
| 217 | |
| 218 | extern int (*bnBasePrecompBegin)(struct BnBasePrecomp *pre, |
| 219 | struct BigNum const *base, struct BigNum const *mod, |
| 220 | unsigned maxebits); |
| 221 | extern void (*bnBasePrecompEnd)(struct BnBasePrecomp *pre); |
| 222 | extern int (*bnBasePrecompExpMod)(struct BigNum *dest, |
| 223 | struct BnBasePrecomp const *pre, struct BigNum const *exp, |
| 224 | struct BigNum const *mod); |
| 225 | extern int (*bnDoubleBasePrecompExpMod)(struct BigNum *dest, |
| 226 | struct BnBasePrecomp const *pre1, struct BigNum const *exp1, |
| 227 | struct BnBasePrecomp const *pre2, struct BigNum const *exp2, |
| 228 | struct BigNum const *mod); |
Alexandre Lision | 7fd5d3d | 2013-12-04 13:06:40 -0500 | [diff] [blame] | 229 | |
| 230 | #ifdef __cplusplus |
| 231 | } |
| 232 | #endif |
| 233 | |
| 234 | #endif/* !BN_H */ |