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