A RADIX-4 MODULAR MULTIPLICATION HARDWARE ALGORITHM FOR MODULAR EXPONENTIATION

A fast radix-4 modular multiplication hardware algorithm is proposed. It is efficient for modular exponentiation with a large modulus used in public-key cryptosystems such as RSA cryptosystem. The operands and the result of multiplication which are intermediate results in modular exponentiation are represented in a redundant representation. The computation proceeds in serial-parallel fashion. Each subtraction for the division for residue calculation is embedded in the repeated multiply-addition. Each intermediate result is represented in a more redundant representation than that for the operands and the result, so that the number of the required addition/subtractions is reduced. All addition/subtractions are carried out without carry propagation. The algorithm is efficient for modular exponentiation, because only one carry propagate addition is required in the whole computation for a modular exponentiation. A serial-parallel modular multiplier based on the algorithm has a regular cellular array structure with a bit slice feature and is suitable for VLSI implementation. It seems easy to fabricate an RSA chip based on the multiplier using today's technology, which is expected to have a throughput of several times as large as that of the fastest actual RSA chip.