MPLib User's Manual Duncan S Wong (swong@ccs.neu.edu) http://www.ccs.neu.edu/home/swong/MPLib/ Feb 11, 2001 Initialization Functions ------------------------ INT *MPLibMP_new(UInt16 uRefNum) Initialize and return a memory chunk of size MP_DEFAULT_BITS bits. Each byte of the memory chunk is also initialized to zero. Each INT variable should normally be initialized before use, and freed using MPLibMP_free between each initialization. Use MPLibMP_clear_free instead if the variable contains some cryptographic secret. It clears out the memory chunk by writing zero to each byte and then deallocates the memory chunk. Example: { INT *integ; integ = MPLibMP_new(MPLibRefNum); ... MPLibMP_add(MPLibRefNum, integ, ...); ... MPLibMP_sub(MPLibRefNum, integ, ...); ... MPLibMP_clear_free(MPLibRefNum, integ); } void MPLibMP_clear(UInt16 uRefNum, INT *integer) Clear the content of integer by setting each byte of integer to zero but not freeing the memory of integer void MPLibMP_free(UInt16 uRefNum, INT *integer) Free the memory of integer but would not clear the content. It is fine to use this function for all (INT *) variables when you are done with them. But MP_clear_free is recommended for cryptographic applications. void MPLibMP_clear_free(UInt16 uRefNum, INT *integer) Clear the content of integer by setting each byte of integer to zero and then free the memory of the variable. MP_CTX *MPLibMP_CTX_new(UInt16 uRefNum) Initialize the temporary buffer/variable void MPLibMP_CTX_free(UInt16 uRefNum, MP_CTX *c) Clear and free the temporary buffer MP_MONT_CTX *MPLibMP_MONT_CTX_new(UInt16 uRefNum) Allocate a memory chunk for the Montgeomery data structure. void MPLibMP_MONT_CTX_free(UInt16 uRefNum, MP_MONT_CTX *mont) Clear and free the memory chunk for Montgomery multiplication. Int16 MPLibMP_MONT_CTX_set(UInt16 uRefNum, MP_MONT_CTX *mont, INT *modulus, MP_CTX *ctx) Set the parameters of the data structure for Montgomery multiplication. Note : - modulus must be odd and positive. Assignment Functions -------------------- Int16 MPLibMP_mask_bits(UInt16 uRefNum, INT *a, Int16 n) Set a to the n low-bit of a. Note : |a| <= n INT *MPLibMP_copy(UInt16 uRefNum, INT *dest, INT *src) Copy from (INT *)src to (INT *)dest. Return the pointer of (INT *)dest. Note : Support overlapping buffers. Arithmetic Functions -------------------- Int16 MPLibMP_add(UInt16 uRefNum, INT *s, INT *a, INT *b) Set s to a + b. Return 1 if succeed; otherwise return 0. Note: s can be a or b void MPLibMP_qadd(UInt16 uRefNum, INT *r, INT *a, INT *b) Set s to a + b (quick addition). where 1) a and b are treated as unsigned, i.e. s->neg would not be updated 2) |a| is great than or equal to |b| 3) s has enough memory allocated already This function does not check the validity of the inputs for speed Note: s can be a or b Int16 MPLibMP_sub(UInt16 uRefNum, INT *r, INT *a, INT *b) Set r to a - b. Return 1 if succeed; otherwise return 0. Note: r can be a or b. void MPLibMP_qsub(UInt16 uRefNum, INT *r, INT *a, INT *b) Set r to a - b where 1) a and b are treated as unsigned --- r->neg would not be updated. 2) magnitude of a must be greater or equal to that of b. 3) r has enough memory allocated already. No validity checking of the above statements in this 'quick' subtraction function. Note: r can be a or b. Int16 MPLibMP_mul(UInt16 uRefNum, INT *r, INT *a, INT *b) Set r to a * b. This is Algorithm 14.12 on p.595 of HAC. Note: r must be different from a and b. DIGIT MPLibMP_mul_digit(UInt16 uRefNum, DIGIT *rp, DIGIT *ap, Int16 num, DIGIT w) Set rp to ap * w where ap has num digits and w is only one digit. The original value pointed by rp is overridden. Return a carry. e.g. ap = 95, num = 2 and w = 6 in radix 10; rp = 70 and 5 is returned. DIGIT MPLibMP_mul_add_digit(UInt16 uRefNum, DIGIT *rp, DIGIT *ap, Int16 num, DIGIT w) Set rp to rp + (ap * w) where ap has num digits and w is only one digit. The original value pointed by rp is overridden. Return a carry. e.g. rp = 99, ap = 95, num = 2 and w = 6 in radix 10; rp = 69 and 6 is returned. Int16 MPLibMP_sqr(UInt16 uRefNum, INT *r, INT *a) Set r to a*a. This is Algorithm 14.16 on p.597 of HAC. Note : r must not be a. Int16 MPLibMP_div(UInt16 uRefNum, INT *q, INT *r, INT *dividend, INT *divisor, MP_CTX *ctx) Set q and r to the quotient and remainder of (dividend / divisor). Note : - For computing modular reduction (i.e. dividend mod divisor), call the function as MPLibMP_div(uRefNum, NULL, r, dividend, divisor, ctx). - Check 14.2.5 on p.598 of HAC for details. Logical Functions ----------------- Int16 MPLibMP_lshift(UInt16 uRefNum, INT *to, INT *from, Int16 n) Shift (INT *)from n bits to the left and put the result to (INT *)to. Note: (INT *)from and (INT *)to can be overlapped if (from <= to) and n is +ve; otherwise, from >= to. Int16 MPLibMP_lshift1(UInt16 uRefNum, INT *r, INT *a) Set r to 2*a. Note: r can be a. Int16 MPLibMP_rshift(UInt16 uRefNum, INT *to, INT *from, Int16 n) Shift (INT *)from n bits to the right and put the result to (INT *)to. Note: (INT *)from and (INT *)to can be overlapped if (to-from) b, 0 if a = b and -1 if a < b. Int16 MPLibMP_ucmp(UInt16 uRefNum, INT *a, INT *b) Compare a and b as 'unsigned' integers. Return a positive value if a > b, zero if a = b, and a negative value if a < b. Int16 MPLibMP_is_bit_set(UInt16 uRefNum, INT *a, Int16 n) Return 1 if the n bit of (INT *) a is set (n starts at 0). Number Theoretic Functions -------------------------- Int16 MPLibMP_mod_mul(UInt16 uRefNum, INT *r, INT *a, INT *b, INT *m, MP_CTX *ctx) Set r to a * b (mod m). Classical modular multiplication (Algorithm 14.28 on p.600 of HAC) Note : - For speed, this function would not check the validity of the inputs, i.e. a, b and m are positive integers - Again for speed, the inputs a and b should be < m. Int16 MPLibMP_mont_mul(UInt16 uRefNum, INT *r, INT *a, INT *b, MP_MONT_CTX *mont, MP_CTX *ctx) Set r to abR^{-1} (mod m) where information of R and m are in (MP_MONT_CTX *) mont. Montgomery Multiplication (Algorithm 14.36 on p.602 of HAC) Note : - We assume that a, b < mont->m. - r can be a or b. - As R = b^n, the modulus (mont->m) need to be odd. INT *MPLibMP_mod_inverse(UInt16 uRefNum, INT *a, INT *n, MP_CTX *ctx) Extended Euclidean algorithm (Algorithm 2.107 on p.67 of HAC) Return x where ax == 1 (mod n). Note: - a can be > n - return NULL if gcd(a, n) > 1 Int16 MPLibMP_mod_exp(UInt16 uRefNum, INT *r, INT *a, INT *b, INT *m, MP_CTX *ctx) Set r to a^b mod m. Classical Left-to-right binary exponentiation (repeated square-and-multiply) (Algorithm 14.79 on p.615 of HAC) Note : r can be a. Int16 MPLibMP_mont_exp(UInt16 uRefNum, INT *r, INT *a, INT *e, MP_MONT_CTX *mont, MP_CTX *ctx) Set r to a^b mod m using Montgomery exponentiation (Algorithm 14.94 on p.620 of HAC). Note : - r can be a. - m is in (MP_MONT_CTX *)mont. - m must be odd. Int16 MPLibMP_gcd(UInt16 uRefNum, INT *d, INT *a, INT *b, MP_CTX *ctx) Set d to gcd(a, b). This is the classical Euclidean Algorithm (Algorithm 2.104 on p. 66 of HAC). Note : - d can be a or b. Int16 MPLibMP_binary_gcd(UInt16 uRefNum, INT *d, INT *a, INT *b, MP_CTX *ctx) Set d to gcd(a, b). Binary gcd Algorithm (Algorithm 14.54 on p. 606 of HAC) Note : - d can be a or b. - According to my implementation results, the Binary gcd algorithm (Algorithm 14.54) is SLOWER than the classical Euclidean algorithm (Algorithm 2.104) in most of the cases. Int16 MPLibMP_crt2(UInt16 uRefNum, INT *x, INT *v1, INT *v2, INT *p, INT *q, MP_CTX *ctx) Find the unique solution 0 <= x < p*q given that x \equiv v1 \pmod{p} and x \equiv v2 \pmod{q}. (i.e. x = (((v2 - v1) * u) mod q) * p + v1 where u = p^{-1} mod q and x < n) Garner's algorithm for CRT (Chinese Remainder Theorem) for special case of two moduli ^^^^^^^^^^ e.g. particularly efficient for RSA moduli n = pq Note: - This function would first check if p and q are relatively prime - This function assumes that v1 < p and v2 < q. - Return 1 is succeed; otherwise, 0. - Check HAC p.612 Algorithm 14.71 and Note 14.75(i) for details Int16 MPLibMP_probab_prime(UInt16 uRefNum, INT *n, UInt16 reps, MP_CTX *ctx) If it returns 1, then n is 'probably' prime; if it returns 2, then n is surely prime; if it returns 3, then n is not prime; if it returns 0, then something's going wrong. Note: - Reasonable values of (UInt16) reps vary from 20 to 100; a higher value lowers the error probability. - Warning: minutes or even hours may take for large value of reps if n is large. e.g. It takes over 2 minutes if n is 256 bits long and reps = 3. So if reps is 20, it would take more than an hour before your Palm getting a response... if your Palm still have power... - This function uses Miller-Rabin primality test. Conversion Functions -------------------- INT *MPLibMP_bin2bn(UInt16 uRefNum, UInt8 *s, UInt16 len) Convert a binary stream s to INT and return it as (INT *). len is the length of s in number of bytes. Note: ignore negative UInt16 MPLibMP_bn2bin(UInt16 uRefNum, INT *a, UInt8 *to) Convert (INT *) a to a binary stream (UInt8 *) to. Return length of (UInt8 *) to in number of bytes. Note: ignore negative INT *MPLibMP_ascii2bn(UInt16 uRefNum, Char *str) Convert a number in ASCII (Char *) str to INT and return it as (INT *). str is represented in HEX. Char *MPLibMP_bn2ascii(UInt16 uRefNum, INT *a) Convert (INT *) a to a hex string in ASCII and return it as (Char *). UInt32 MPLibMP_num_bits(UInt16 uRefNum, INT *a) Return the number of bits of (INT *) a. UInt16 MPLibMP_num_bits_digit(UInt16 uRefNum, DIGIT l) Return number of bits of a digit (DIGIT) l Useful Macros ------------- MP_is_zero(a) Return 1 if a is zero MP_is_one(a) Return 1 if a is one MP_is_odd(a) Return 1 if a is odd MP_zero(a) Set a to zero MP_one(a) Set a to one