Abstract:

A refreshing thing about modern number-theoretic cryptography is that it shows how bad at sums computers really are. Even the most advanced primary-school techniques of long multiplication and long division cannot provide useful speeds when faced with 300-digit modular exponentiations.

This talk will cover the problems of designing hardware for large-integer arithmetic and the ways round them, and will describe a new design for a modular multiplication chip.

Long division is made of subtractions and it needs the result of each subtraction when deciding what to do next; but in silicon, binary subtraction (like addition) is an inescapably slow operation. The algorithm described here takes a ruthless approach: don't get it right slowly, get it wrong fast; and hope that the resulting errors (which double on every clock tick) will be noticeable before they are too large to correct. This balancing act leads to a design that is fast, economical in silicon, easily verifiable, and, unusually in this field, is as efficient for modular multiplication as it is for modular exponentiation.

Speaker:

Martin Kochanski is the inventor of Cardbox, a respected and widely used flat-file text database for DOS and Windows. He has been involved in cryptography since 1979, breaking several commercial encryption products as well as the Lu-Lee public-key cryptosystem; he has also designed and implemented FAP4, the world's first commercially available RSA encryption chip. He is the publisher of Universalis, which provides the daily Liturgy of the Hours through the Web, on palmtops, and through mobile phones.

paper