Speeding up modular inversion is one of the most importantsubjects in the field of information security. Over the ellipticcurve on the prime finite field in particular goals public-keycryptosystems and digital signature schemes fre- quently use modularinversion if affine coordinates are selected. In the regular computerenvironment, most data transmission via networks and data storage onmemories as well as the operation set of processors are performed inmultiples of eight bits or bytes. A fast modular multiplicationalgorithm that matches these oper- ation units for DSP was proposedto accelerate the Montgomery method by Dusse and Kaliski 2.However, modular inversion al- gorithms were developed using bit bybit operation and so do not match the operation unit. This paperproposes two techniques for modular inversion that suits anyarbitrary processing unit. The first technique proposes a newextended GCD procedure with- out any division. It can be constructedby the shifting, adding and multiplying operations, all of which aMontgomery modular arithmetic algorithm employs. The second techniquecan reduce the delay time of post processing in the modular inversionalgo- rithm. In particular, it is of great use for the modularinversion defined in the Montgomery representation. These proposedtech- niques make modular inversion about 5.5 times faster.
展开▼
