Title :
A radix-4 modular multiplication hardware algorithm for modular exponentiation
Author_Institution :
Dept. of Inf. Sci., Kyoto Univ., Japan
fDate :
8/1/1992 12:00:00 AM
Abstract :
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 the 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-add. 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/subtraction are carried out without carry propagation. 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
Keywords :
cryptography; digital arithmetic; RSA cryptosystem; VLSI; bit slice; cellular array structure; division subtraction; modular exponentiation; public-key cryptosystems; radix-4 modular multiplication hardware algorithm; redundant representation; repeated multiply-add; residue calculation; serial-parallel modular multiplier; Algorithm design and analysis; Circuits; Computer security; Digital arithmetic; Hardware; Information science; Iterative algorithms; Public key cryptography; Throughput; Very large scale integration;
Journal_Title :
Computers, IEEE Transactions on
