Philip Zimmermann

bnlib - An SDK for Big Number Arithmetic

I have a math library that does extended precision integer arithmetic (with thousands of bits of precision) suitable for public key algorithms such as Diffie-Hellman, RSA, ElGamal, or the DSA. I had previously developed my own multi-precision arithmetic library in 1986, which I used in the original PGP, which continued to be used up through PGP version 2.6.x. But in 1995, while working for me, Colin Plumb developed this new faster (much faster) big number package, bnlib, for later versions of PGP and PGPfone.

bnlib has been used in a number of crypto packages besides PGP. I use it in my new Zfone secure VoIP project. Also, the new Wireless USB standard (which I worked on) requires the use of 3072-bit Diffie-Hellman for the Numeric Association Model, and some of the vendors who make WUSB chips (such as Staccato Communications) are using bnlib to make WUSB run fast on cheap embedded processors. And it's quite compact.

For bnlib licensing information, see below.

Performance

We measured how fast bnlib performed the Diffie-Helllman calculations for the Wireless USB Association Model, on a typical CPU that might be embedded in a WUSB controller. We used a 200 MHz ARM made by Intel.

First, the processor type for the tests:

Processor       : XScale-PXA255 rev 6 (v5l)
BogoMIPS        : 198.65
Features        : swp half thumb fastmult edsp
CPU architecture: 5TE

We did the DH calculations with a 3072-bit prime, a 256-bit exponent, and the generator g=2. This matches the sizes actually used in the WUSB-AM protocol. The C compiler was gcc, using the "-march=arm5te" flag, which means that gcc is using a 32x32->64-bit inline multiply. Note that each party must perform two modular exponentiations for the DH calculation.

2^<256> mod <3072> bits AVERAGE: 0.246 s
<3072>^<256> mod <3072> bits AVERAGE: 0.327 s
Thus, the total time for the full DH calculation is .246 + .327 = .573 seconds. However, the first exponentiation may be done in advance, which would reduce user's wait time to .327 seconds.

The C code uses Montgomery multiplication to achieve these execution times. The availability of a hardware multiply instruction makes a huge difference in execution speed. bnlib spends most of its time in the multiply instruction. The wider the multiply (in bits), the faster it runs.

Code size

Some people have asked for code size estimates for running bnlib on an ARM chip. Embedded WUSB chips are often memory constrained.

Here is the total size, in bytes, of a stripped-down ARM modular exponentiation library:

   text    data     bss     dec     hex filename
   9076       8    2268   11352    2c58 bntest32.arm.o
   7608       0       0    7608    1db8 lbn32.arm.o
    316       0       0     316     13c lbnarm.arm.o
     48       0       0      48      30 lbnmem.arm.o

The "bntest32.arm.o" file is the self-test, which calls the other code and prints information about timing and correctness. The other code (7608+316+48 = 7972 bytes) is what actually does the math.

Thumb code can be used to further reduce the size of lbn32.arm.o. I don't have the thumb code size for our own builds of that module (see below for Staccato's builds). lbnarm.arm.o contains the time-critical primitives that should be written in "full-size" ARM code.

This is with only two changes to reduce code size:
- Unnecessary code (in particular, a^x * b^y (mod p)) commented out.
- The convenient variable-sized buffer wrapper layer removed, so the user has to provide their own buffers.

Roberto Aiello at Staccato Communications reports these code sizes when they build it for an ARM7: 5904 bytes when built with O3 optimization in ARM mode, and 4076 bytes when built with O3 optimization in THUMB mode. This is surprisingly small, but I don't know all the details, such as which compiler he used.

Licensing

When Colin developed bnlib for me, I agreed to let him place the bnlib code under the open-source GNU General Public License (the GPL). If you are familiar with the GPL, you know that any software that uses code under a GPL license is itself subject to the same GPL licensing terms. In other words, if you include bnlib in your product under the GPL, you must publish your own product's source code and make it available for free to everyone under the same GPL license. Many companies don't like to use code under the GPL license, because they don't want to infect their own products with the obligations of the GPL.

However, there's another way to license bnlib. Colin granted me unlimited rights to license bnlib to anyone else under non-GPL terms. This means if you purchase a license from me, you can use bnlib to create your own proprietary products.

To evaluate bnlib, you can download it by clicking here. Unzip the archive and read all the files with the .doc filenames, as well as all the README files.

If you have any questions regarding licensing, you can email me at prz at mit dot edu. Or call me at the number on my contact page.