Modular multiplication and exponentiation
Lots of public-key crypto uses modular multiplication and
- exponentation operations. Doing them efficiently is very
+ 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
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.
+ 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 `pgen', and a good (but
+ search filtering system called `pfilt, and a good (but
probabilistic) primality tester which implements the Rabin-
Miller test.
- The idea is that you initialize a pgen object with a starting
- place. It spends a short time initializing itself, and then
- tells you whether the number you gave it is (a) definitely
- composite, (b) definitely prime (only for small numbers), or (c)
- it doesn't know. The advantage of the pgen system is that it's
- good at stepping regularly. You can advance it by 2 or 4 very
- rapidly, and it will give you the same sort of answer for the
- next number.
-
- When you find a number which pgen says it doesn't know about,
- you must test it more thoroughly. This is time-consuming, but
- pgen has weeded out many no-hopers so it's not so bad.
-
- The Rabin-Miller test takes a number to test, and stores it in a
- context. You then give it some random numbers, and it gives you
- results. When you've finished, you destroy the context.
-
- The Rabin-Miller test has two possible responses: (a) definitely
- not prime, and (b) probably prime. Answer (a) is certain.
- Answer (b) you may get with a composite number at most one time
- in four. If you try n times, the probability of a composite
- number going unnoticed is at most one in 4^n. In fact, the real
- probability is *much* lower than this.
-
- It's also important to bear in mind that this is examining the
- probability that a number passes n Rabin-Miller tests given
- that it's composite. What's actually interesting the the
- probability that a number is composite given that it passed n
- tests. This probability is lower still. For 1024-bit numbers,
- which are about the right size by current standards of security,
- you need only five tests to ensure a probability of less than 1
- in 2^80 of a composite number slipping through.
-
- There are specialized functions for finding various sorts of
- prime numbers with particular properties. Read the header files
- to find out what they do.
+ Over the top of this is a confgurable plug-in-appropriate-bits
+ system called `pgen' which tied 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
projects / u / mdw / catacomb / blobdiff