Release 2.4.3.

[catacomb] / README.mp

Multiprecision maths library


	Catacomb comes with a fairly reasonable multiprecision maths
	library.  It's not stunningly fast, and doesn't do everything,
	but it seems good for the sorts of things needed in
	cryptographic algorithms (which, for example, GMP isn't[1]).

	There are basically three layers to the system:

	  * The low-level `mpx' layer, which implements some basic
	    arithmetic but is fairly unpleasant to actually use.

	  * A high-level `mp' layer, which provides a useful `mp'
	    multiprecision type and implements useful arithmetic on
	    them.

	  * Everything else.  A collection of miscellaneous routines for
	    performing particular operations efficiently or simply.

	[1] In particular, GMP is truly rotten at converting numbers
	    into well-defined binary formats.  It has its own format,
	    but it's not defined in the manual, has changed once before,
	    probably doesn't conform to any standards in the
	    cryptographic community, and can only be written to or read
	    from a file stream, so you can't use it in memory (for
	    example to encrypt it).  Basically, it's a right pain.


The low-level interface

	The low level is described in `mpx.h'.  It includes everything
	else it needs.

	An integer is represented in an array of words.  Each word has
	type `mpw' (multi precision word).  The least significant word
	comes first.  An array is described by its `base' -- the address
	of the first element -- and its `limit' -- the address *just
	after* the last element.  Thus, the length of the array is
	`limit - base'.  This representation is particularly convenient
	for many things.  An old version used base and length, which was
	a nuisance.

	The largest value which can be represented in a word is
	MPW_MAX.  The number of bits used in the representation of a
	word is MPW_BITS.  Actually, you might be able to use more bits
	and store larger numbers, but everything will go wrong if you
	try.

	The macro call MPW(x) returns the low MPW_BITS bits of x.  It's
	very useful in low-level arithmetic.

	The call MPWS(n) tells you the `sizeof' an array of n words.
	It's also very useful.  Try not to get MPW and MPWS confused
	because they mean very different things.

	The actual low-level macros and functions are documented
	relatively well.  They are given source and destination arrays
	for things to be read and written to.  Usually the sources
	mustn't overlap the destinations, and destinations certainly
	mustn't overlap other destinations; sometimes this restriction
	is lifted, where it would be both convenient and easy to do so.
	Sources can overlap each other without problems, because they're
	not written to.

	The difficult parts are the Karatsuba functions.  Karatsuba
	and Ofman discovered a neat recursive way to multiply large
	numbers.  It requires quite a bit of workspace, and adds some
	overhead, but has lower asymptotic complexity than the standard
	multiply algorithm.  Usually, Karatsuba functions get used
	automatically by the rest of the library when appropriate and
	you don't have to care.


The high-level interface

	The high-level invents a type, `mp'.  It's a structured type,
	with the following members:

	mpw *v, *vl	Base and limit of the word array.
	size_t sz	Number of words actually allocated to the array.
	unsigned f	Various flags.
	unsigned ref	Number of references to the integer.

	The flags are interesting.  Here's what they mean:

	MP_NEG		The number is negative
	MP_BURN		Burn the number after using it
	MP_CONST	The number mustn't be modified or freed
	MP_UNDEF	The number contains no interesting value
	MP_DESTROYED	The number has been freed once already

	The last one is handy for catching bugs.  MP_NEG is obvious --
	Catacomb uses a signed-magnitude representation because things
	are usually easier that way.  MP_CONST is set on various
	constants provided for general convenience so they don't get
	destroyed by accident.  MP_UNDEF is used to avoid copying
	useless data.

	MP_BURN marks a `secret' number.  Secret numbers are overwritten
	with zeroes (`burnt') when they're freed.  Secrecy is a viral
	concept: anything calculated from a secret number is also
	secret, so they get burnt too.

	Most of the time, you refer to numbers by their addresses.  Lots
	of `mp *' pointers get used.  You hardly ever see a real `mp',
	just pointers to them.

	There are a collection of utility functions for keeping the
	system running -- for creating new numbers without interesting
	values, for throwing old ones away, for extending the amount of
	memory they use, and so on.

	Throwing numbers away is simple.  You pass the pointer to the
	number to `mp_drop'.  If someone else still has a reference to
	the number, it stays where it is, but remembers that you're not
	interested in it any more.  If nobody's interested then the
	number is disposed of.

	You can add a reference using MP_COPY.  It returns the new
	reference.  The new reference is the same as the old one, but
	it's a useful fiction to pretend that it's different.

	Real arithmetic happens in a fairly uniform way.  There's an
	important point to make about `destinations', though.  Just
	about all of the arithmetic functions take `destination'
	arguments (one for each result), with the idea that, at least
	conceptually, they store the results there.  What actually
	happens is that a reference is lost to whatever the destination
	used to refer to, and a reference to the new result is gained.
	The address might be different, and then again it might not.
	Destinations can be the same as sources -- that works fine.
	Finally, there's the magic value `MP_NEW'.  MP_NEW is a special
	constant which, as a destination, means `create a new place and
	put the answer there'.

	The idea is that, sometimes it helps that memory is already
	allocated for a destination, so it doesn't have to be obtained
	specially, and, even more often, you want to throw away old
	intermediate results while you're calculating new ones.

	Here are some examples of how to do it right:

	x = mp_add(MP_NEW, y, z);
		Assumes x didn't have a useful value before.
		Afterwards it refers to the sum of y and z.  y and z
		themselves are unchanged.

	y = mp_add(y, y, z);
		Add z to y.  Now y is the sum of z and the old y.  z is
		unchanged.

	q = MP_NEW;
	mp_div(&q, &x, x, y);
		Sets q (a new value) equal to x / y, and puts the
		remainder back in x.  y is unchanged.

	z = mp_sub(z, y, z);
		Subtract z from y, putting the result back in z.  y is
		unchanged.

	x = mp_mul(y, y, z);
		Multiply y by z, putting the result in x, but making y
		no longer useful.

	Here are some examples of how to do it wrong:

	mp_mul(y, y, z);
		mp_mul might choose somewhere other than y's storage to
		write its result.  (In fact, the current version
		certainly will.)  So y is trashed because there are no
		references to it any more, and the result of the
		multiplication is lost.

	x = mp_mul(y, y, z);
	x = mp_add(x, x, y);
		Whoops.  We stored the result in x, but y still got
		trashed and might contain anything.  Adding it to x is a
		bad move.

	It's not hard once you get the hang of it, although it might
	feel a bit weird to start with.


Modular multiplication and exponentiation

	Lots of public-key crypto uses modular multiplication and
	exponentiation operations.  Doing them efficiently is very
	important.  Multiplication on its own is easy, and Catacomb's
	multiplication algorithms are fairly good (though not up with
	the very best).  Doing the modular reduction afterwards is the
	tricky bit.

	There are three approaches to modular reduction in Catacomb.
	All of them have their good and bad points.

	1. Use mp_div

	For a one-off calculation, this is a good idea.  Division is a
	slow operation -- that's a shame, but life's like that.  But
	when you're doing a one-shot operation, that's the best you can
	manage.

	2. Use Barrett reduction

	Barrett reduction is a system whereby you do a little
	precomputation up-front (one division, in fact) and are then
	able to perform modular reductions without resorting to
	expensive division operations.  To use it, you initialize a
	`context' with the modulus, reduce some numbers, and then
	destroy the context when you've finished.

	Conceptually, Barrett reduction is simple.  You give it x and it
	gives you back x mod m.  The mathematics behind it is fairly
	clever, though -- the real manual has a page of explanation for
	how it works.

	Barrett reduction works on any positive modulus m.  It will do a
	modular reduction on any integer x which is at most twice as
	long as m (in words).  x can be larger than m^2, but it mustn't
	be more than twice as long.

	3. Use Montgomery reduction

	Montgomery reduction is a little more clever.  It does a little
	more work up-front than Barrett reduction, and understanding the
	benefits is a little harder.  However, it's actually slightly
	more efficient for general use.  There's also a disadvantage
	that Montgomery reduction only works when the modulus is *odd*.
	It all goes horribly wrong with an even modulus.  Don't try it.

	I'm not going to explain how Montgomery reduction actually
	works.  But I am going to explain how to use it.

	The precomputation for Montgomery reduction, performed when you
	initialize a context, computes a value called R, and also R^2
	(both mod m).  (It also computes some other stuff, but that's
	not important for this discussion.)  Note that R is dependent on
	the modulus m.

	A Montgomery reduction takes a number x, which should be less
	than m^2 (it can actually be a bit larger) and computes the
	value x R^{-1} mod m.  That doesn't sound very useful, does it?

	Things start looking more hopeful when you multiply your inputs
	by R.  (There's a clever way of doing that: see below.)	 To
	compute xy mod m, you can first calculate xR and yR, multiply
	them together to get xyR^2, and do a Montgomery reduction to get
	xyR^2 R^{-1} mod m.  Then the R^{-1} cancels one of the Rs and
	you end up with xyR mod m.  Essentially, you do your entire
	calculation with an extra factor of R all the way through it.

	Removing the factor of R at the end is easy.  You just run the
	Montgomery reduction algorithm again -- the R^{-1} cancels the R
	and the answer pops out the end.  Getting the factor of R in the
	first place is easy -- you multiply by R^2 and do a reduction.

	The multiply-and-reduce thing is so common that there's a
	dedicated function which does them both in one go.

	Here's a simple example of multiplying two numbers mod m:

		mpmont mm;
		mp *ar, *br, *p;
		mpmont_create(&mm, m);
		ar = mpmont_mul(MP_NEW, a, m.r2);	/* aR mod m */
		br = mpmont_mul(MP_NEW, b, m.r2);	/* bR mod m */
		p = mpmont_mul(&mm, MP_NEW, ar, br);	/* abR mod m */
		p = mpmont_reduce(&mm, p, p);		/* ab mod m */
		mpmont_destroy(&mm);
		mp_drop(ar);
		mp_drop(br);

	Actually, it's not a very clever example.  Here's a better way,
	for such a simple calculation:

		mpmont mm;
		mp *p;
		mpmont_create(&mm, m);
		p = mpmont_mul(&mm, MP_NEW, a, b);	/* abR^{-1} mod m */
		p = mpmont_mul(&mm, p, p, mm.r2);	/* ab mod m */
		mpmont_destroy(&mm);

	Of course, for a single multiply-and-reduce, you're better off
	just using

		mp *p = mp_mul(MP_NEW, a, b);
		mp_div(0, &p, p, m);

	the traditional division method.

	Both Barrett and Montgomery reduction methods have modular
	exponentiation functions.  If m is a message, n is an RSA
	modulus, and e is the public exponent, I can do an RSA
	encryption simply by doing

		mpmont mm;
		mpmont_create(&mm, n);		/* RSA modulus is odd */
		c = mpmont_exp(&mm, MP_NEW, m, e);
		mpmont_destroy(&mm);

	(Yes, it's well worth creating a Montgomery context for a
	full-blown exponentiation, unless someone's deliberately gone
	out of their way to make it easy for you by choosing a very
	small public exponent.)

	RSA decryption is fully covered by the library, because doing it
	properly is complicated and difficult since it involves playing
	with blinding factors and the Chinese Remainder Theorem.

	(There's also a useful RSA parameter recovery system which can
	determine all the useful bits of information for efficient RSA
	decryption given a very small amount of information.  For
	example, given the modulus and both exponents, it can recover
	the two secret factors.  This is, by the way, a good reason not
	to share a modulus among many users.)


Finding prime numbers

	Prime numbers are important too.  Finding them is not ever-so
	easy.  There's a huge variety of useful properties which are
	needed, and it's basically impossible to cover everything.

	Catacomb has two useful facilities.  There's a fast sequential-
	search filtering system called `pfilt', and a good (but
	probabilistic) primality tester which implements the Rabin-
	Miller test.

	Over the top of this is a configurable plug-in-appropriate-bits
	system called `pgen' which ties everything together.  You're
	much better off using `pgen' than grovelling about with the
	filter and Rabin-Miller tests by hand.  The low-level details
	are much better used to create new `pgen' components.


Conclusion

	This basically concludes the tour of Catacomb's multiprecision
	maths library.  I hope it's provided enough background that the
	comments start making sense.

-- [mdw]

\f
Local variables:
mode: text
End: