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: