Unix Review > Archives > 2006 > October 2006
Print-Friendly Version

October 2006

Book Review: BigNum Math

Reviewed by Cameron Laird

BigNum Math: Implementing Cryptographic Multiple Precision Arithmetic
By Tom St. Denis
O'Reilly, 2006
ISBN: 1-59749-112-8
272 pages

BigNum Math has our children wary — they know Daddy likes books and numbers and calculations, but isn't doing arithmetic going backward? They suspect a trick.

The trick, of course, is that anything can be stretched, expanded, abstracted, or reworked to become entirely more challenging than its original form. Children's games become million-dollar industries when played by sufficiently expert athletes, and, treated with enough panache, peanut butter is a gourmet item.

Or, as in the case at hand, when the additions and multiplications contribute to "Implementing Cryptographic Multiple Precision Arithmetic" (the book's subtitle), the numeric tables and rules we learned in grade school appear in a whole new light.

Cryptographic purposes

Humans demand privacy and authentication with sufficient enthusiasm to support a lively market in codes. For our purposes, codes are cryptographic objects; their effective management requires multiplication of numbers like 83567040975197715972768175 and 6089933037757203664490167389076125.

For your virtual private network (VPN) or DVD player to be fast enough to satisfy you as a customer, then, depends crucially on arithmetic that goes beyond the kind taught in elementary school. At one level or another, you rely on "multiple-precision" calculations.

Many languages support arithmetic within definite limits; you can write:

	my_product = factor1 * factor2    
but there are problems if my_product gets too big or too small or too unlucky. "Unlucky" here refers to the fact that, while you might see nothing extraordinary in:
	one_fifth = 1. / 5.
	product = 5. * one_fifth
	difference = product - 1.    
most computing systems do not, for rather involved historical and technical reasons, recognize that difference should be 0.

This just won't do, especially not for codes and cyphers. Keys have to be exactly right, and it's not enough to say that the computer "lost a little precision" in unlocking nuclear launch codes or directing space probes hundreds of millions of kilometers distant.

Bignums, or multi-precision, arithmetics, give exact results for operations beyond the ranges supported by conventional hardware and languages. BigNum Math methodically documents the algorithms and source code for one particular implementation, LibTomCrypt.

"Methodically" here is a key word. Computing arithmetic has been documented many times. No other work I know, though, not even Knuth's Volume 2, simultaneously takes such care to detail mundane matters like signs and magnitude differences, while also describing advanced and even deep results from Karatsuba multiplication and modular exponentiation. BigNum Math is unique.

Specialized, high in quality

It's quite specialized, both for good and bad. The languages of expression are pseudocode and executable C. The algorithms are almost exclusively for multi-precision integer calculations, not rational, floating-point, or infinite-precision ones.

Let's be clear on these distinctions. A modern CPU might offer 32- or even 64-bit integer arithmetic in its dedicated hardware. For the cryptographic purposes that motivate him, BigNum Math author Tom St. Denis needs a couple of hundreds of bits of full precision. To achieve these, he defines C structures that represent multiple-precision integers. For his purposes, though, the precision is fixed at compile time. Given this context, he makes detailed and subtle measurements that yield tiny but definite performance improvements.

With some effort, St. Denis's ideas and algorithms can be translated to infinite-precision code. Infinite-precision numbers, standard in such languages as Lisp and the latest Python, are variable-length representations, ones whose precisions are determined at the time of execution. Number theorists typically need this sort of arithmetic more than the multiple-precision forms of BigNum Math.

The text is clear and relentlessly dry. Typographical errors are few and inconsequential: a single word missing or out of place. Symbolic expressions have been reviewed carefully; from everything I've noticed, they're entirely correct.

Only the very few programmers who need to implement a multiple-precision arithmetic library will want to read BigNum Math through from cover to cover. There are many more people, though, who might like to have on their shelves a reference that supplies many unique passages. Anyone tuning high- or variable-precision arithmetic, anyone looking to implement specialized primality tests or exponentiation speed-ups, and anyone analyzing cryptography constraints will find in BigNum Math descriptions and results published nowhere else.

Cameron is vice president of the Phaseit, Inc., consultancy, specializing in high-reliability and high-performance applications managed by high-level languages. He's implemented comprehensive multiple-precision arithmetics for multiple companies and remains passionate about details of numeric representations. For UnixReview, he has reviewed more than 50 books.

Sys Admin Spotlight

CMP DevNet Spotlight

Highlighting Multiple Search Keywords in ASP.NET
This article demonstrates how to highlight a multiple keywords within a DataGrid control, no matter where they are in the text.

In the News

Mexico's Telmex To Spin Off International Business
The largest fixed-line telephone operator in Mexico said it wants to free the faster-growing international operations from the slow-growth parent company.

Microsoft Opens Up Customer Care Framework
The latest version improves third-party application support but is best matched with Microsoft SharePoint Server.

Bomb Scare Forces Evacuation Of 200 eBay Workers
The affected areas of campus have since been reopened.

Dell To Sell Solaris Servers
The agreement aims at Dell's efforts to meet server customer demand and Sun's goal to sell more Solaris services and support.

Penryn's Got The Power For Wall Street Computing

A fascinating nugget hidden amid Intel's announcement of its 45-nm Penryn processors is just who really needs these powerful chips. Sure, PC gamers want the hot Core 2 Extreme QX9650. And enterprises everywhere more or less buy into the "better performance per watt" sell of the server-side Xeon Penryns. But the folks for whom this stuff is like silicon heroin -- they can�t live without it and they gotta have it now -- are the IT elite who run the data centers for the various stock exchanges.

Microsoft Releases Security Guide For Office Apps
The guide is a set of documents and software to help organizations secure one of the world's most popular set of applications.

Microsoft Smartens Windows Embedded CE With Web Services
Release Candidate 2 of version 6.0 also updates the OS's ability to manage video telephony, pluggable font engine support, and thin-client technology.


Sys Admin and The Perl Journal CD-ROM version 11.0

Version 11.0 delivers every issue of Sys Admin from 1992 through 2005 and every issue of The Perl Journal from 1996-2002 in one convenient CD-ROM!

Order now!


Try VMWare Workstation for Free! Register here.
VMware Workstation: The gold standard in desktop virtualization. Click here for your free trial.

Get your FREE 30 day VMware Workstation trial Now!
Virtualize your desktop today with VMware Workstation.

Easy & Powerful Server Monitoring that Just Works
Fortune 500 clients include Financial, Healthcare & Telco Companies. Free Trial Download.

Office Accounting Pro 08
Get organized and save time. Download your free trial today!

Wanna see your ad here?