Fast Modular Inversion Algorithm to Match Any Operation Unit (Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• Speeding up modular inversion is one of the most important subjects in the field of information security. Over the elliptic curve - on the prime finite field in particular goals - public-key cryptosystems and digital signature schemes frequently use modular inversion if affine coordinates are selected. In the regular computer environment, most data transmission via networks and data storage on memories as well as the operation set of processors are performed in multiples of eight bits or bytes. A fast modular multiplication algorithm that matches these operation units for DSP was proposed to accelerate the Montgomery method by Dussce and Kaliski. However, modular inversion algorithms were developed using bit by bit operation and so do not match the operation unit. This paper proposes two techniques for modular inversion that suits any arbitrary processing unit. The first technique proposes a new extended GCD procedure without any division. It can be constructed by the shifting, adding and multiplying operations, all of which a Montgomery modular arithmetic algorithm employs. The second technique can reduce the delay time of post processing in the modular inversion algorithm. In particular, it is of great use for the modular inversion defined in the Montgomery representation. These proposed techniques make modular inversion about 5.5 times faster.

• 社団法人電子情報通信学会の論文
• 1999-05-25

著者

• Kobayashi Tetsutaro

  Ntt Information And Communication Systems Laboratories

• Morita Hikaru

  Ntt Information And Communication Systems Laboratories

関連論文

• Candidate One-Way Functions on Non-Supersingular Elliptic Curves(Elliptic Curve Cryptography, Cryptography and Information Security)
• Non-Supersingular Elliptic Curves for Pairing-Based Cryptosystems(Discrete Mathematics and Its Applications)
• Anonymous Hierarchical Identity-Based Encryption with Short Ciphertexts
• Faster MapToPoint on Supersingular Elliptic Curves in Characteristic 3
• Fast Modular Inversion Algorithm to Match Any Operation Unit (Special Section on Discrete Mathematics and Its Applications)
• Efficient τ-Adic Sliding Window Method on Elliptic Curve Cryptosystems(Special Section on Cryptography and Information Security)
• Lenient/Strict Batch Verification in Several Groups(Special Section on Cryptography and Information Security)
• Multiple Scalar-Multiplication Algorithm over Elliptic Curve
• A Cyclic Window Algorithm for Elliptic Curves over OEF(Special Section on Cryptography and Information Security)
• Security of ESIGN-PSS(Information Security)

スポンサーリンク