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] Local variables: mode: text End: