BSD Licensed Big Integer C lib with fast modpow

Question

I'm searching a fast (specially the p^n mod g operation, should be implemented with montgomery) big integer library. I know there is GMP but GMP is LGPL which doesn't fit my requirements.

I tried http://www.acme.com/software/bigint/ and tried to optimize the modpow in there. But do to the fact that the data is stored with base 2^32 it is not so easy to do some optimizations in the modpow.

I also tried giantint from http://www.perfsci.com/free-software.asp but this library has some messed up memory management. It constantly crashes with some malloc/free problems. Maybe the bignum from OpenSSL would do what I'm searching for? But I don't wan't to add the entire OpenSSL lib to my project. Maybe It's possible to extract the bignum part from OpenSSL?

Anyone any suggestions?

P.S. the lib should run on the iPhone/iPad.

Answer 1

Try looking in libtomcrypt. It must have some big integer implementation which is probably small and efficient. There seems to be no official upstream anymore but the dropbear ssh implementation uses it and you can find the source with dropbear.