PHP producer/consumer libraries?

Paul Crowley paul at ciphergoth.org
Mon Jun 27 16:15:23 PDT 2005


meepbear * wrote:
> I gave up looking for a bigint class for PHP since as far as I can tell, 
> noone ever wrote one and just started my own. I can add, substract, 
> multiply, divide and divide with remainder and I think I figured out a 
> way to do powmod using those

Cool!  Chapter 14 of The Handbook of Applied Cryptography has lots of 
information on how to do efficient bignum math:

http://www.cacr.math.uwaterloo.ca/hac/

Montgomery multiplication, for example, is a pretty neat trick.

> It still needs a random number and pseudo-prime generator though and a 
> thorough test.

Why does it need a pseudoprime generator?  Even if you're not happy to 
use the default "p" given in the spec for some reason, you can generate 
your own p using OpenSSL or similar and hard-wire it into your code.

Generating a random bignum is a tricky business!  It's just occurred to 
me that the cheapest way to do it is to try generating the number most 
significant word first.  As you generate each word, test if the 
resulting number is bigger than your ceiling, if so give up and start 
again.  This way you'll usualy either reject on the very first step or 
get all the way to the end.

Best of luck!
-- 
   __
\/ o\ Paul Crowley, paul at ciphergoth.org
/\__/ http://www.ciphergoth.org/


More information about the yadis mailing list