X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/6540d0692a941a46c701ceb6366d00f9a6a37ef0..3e248c3b5b309bc03eb5f70762d3f5671d51f996:/README.mp diff --git a/README.mp b/README.mp index a70e08d..8a276c4 100644 --- a/README.mp +++ b/README.mp @@ -129,7 +129,7 @@ The high-level interface 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'. @@ -163,10 +163,10 @@ The high-level interface 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 @@ -243,7 +243,7 @@ Modular multiplication and exponentiation 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 @@ -263,8 +263,8 @@ Modular multiplication and exponentiation 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); @@ -304,53 +304,34 @@ Modular multiplication and exponentiation 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 @@ -359,8 +340,7 @@ Conclusion maths library. I hope it's provided enough background that the comments start making sense. --- -[mdw] +-- [mdw] Local variables: