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
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