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 acn be the same as sources -- that works fine.
+ 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'.
Multiply y by z, putting the result in x, but making y
no longer useful.
- Here's some examples of how to do it wrong:
+ Here are some examples of how to do it wrong:
mp_mul(y, y, z);
- mp_mul might choose somewhere other than b's storage to
+ 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
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
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
+ 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
mpmont mm;
mp *ar, *br, *p;
mpmont_create(&mm, m);
- ar = mp_mul(MP_NEW, a, m.r2); /* aR mod m */
- br = mp_mul(MP_NEW, b, m.r2); /* bR mod 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);
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 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
maths library. I hope it's provided enough background that the
comments start making sense.
---
-[mdw]
+-- [mdw]
\f
Local variables:
projects / u / mdw / catacomb / blobdiff