Use of Montgomery Trick in Precomputation of Multi-Scalar Multiplication in Elliptic Curve Cryptosystems(Special Section on Cryptography and Information Security)
スポンサーリンク
概要
- 論文の詳細を見る
We develop efficient precomputation methods of multi-scalar multiplication on ECC. We should recall that multi-scalar multiplication is required in some elliptic curve cryptosystems including the signature verification of ECDSA signature scheme. One of the known fast computation methods of multi-scalar multiplication is a simultaneous method. A simultaneous method consists of two stages; precomputation stage and evaluation stage. Precomputation stage computes points of precomputation, which are used at evaluation stage. Evaluation stage computes multi-scalar multiplication using precomputed points. In the evaluation stage of simultaneous methods, we can compute the multi-scalar multiplied point quickly because the number of additions is small. However, if we take a large window width, we have to compute an enormous number of points in precomputation stage. Hence, we have to compute an abundance of inversions, which have large computational amount. As a result, precomputation stage requires much time, as well known. Our proposed method reduces from O(2^2ω) inversions to O(ω) inversions for a window width ω, using Montgomery trick. In addition, our proposed method computes uP and vQ first, then compute uP+vQ, where P,Q are elliptic points. This procedure enables us to remove unused points of precomputation. Compared with the method without Montgomery trick, our proposed method is 3.6 times faster in the case of the precomputation stage for simultaneous sliding window NAF method with window width w=3 and 160-bit scalars under the assumption that I/M=30, S/M=0.8, where I, M, S respectively denote computational amounts of inversion, multiplication and squaring on a finite field.
- 社団法人電子情報通信学会の論文
- 2003-01-01
著者
-
OKEYA Katsuyuki
Systems Development Laboratory, Hitachi Ltd.
-
Okeya Katsuyuki
Systems Development Laboratory Hitachi Ltd.
-
Sakurai Kouichi
Faculty Of Information Science And Electrical Engineering Kyushu University
-
Sakurai Kouichi
Faculty Of Computer Science And Communication Engineering Kyushu University
-
Sakurai Kouichi
Faculty Of Engineering Kyushu University
関連論文
- Recursive Double-Size Modular Multiplications from Euclidean and Montgomery Multipliers
- A Collaborative Role-Based Access Control for Trusted Operating Systems in Distributed Environment(Application)(Cryptography and Information Security)
- Recursive Double-Size Modular Multiplications from Euclidean and Montgomery Multipliers
- Usage Control Model and Architecture for Data Confidentiality in a Database Service Provider(Network Security)
- 1-out-of-L E-voting System with Efficient Computational Complexity Based on r-th Residue Encryption
- A-7-21 Security Policy Pre-evaluation towards Risk Analysis
- Securing provenance by distributing the provenance storage (マルチメディア通信と分散処理・コンピュータセキュリティ)
- Faster Double-Size Bipartite Multiplication out of Montgomery Multipliers
- Montgomery Multiplication with Twice the Bit-Length of Multipliers
- Use of Montgomery Trick in Precomputation of Multi-Scalar Multiplication in Elliptic Curve Cryptosystems(Special Section on Cryptography and Information Security)
- PGV-Style Block-Cipher-Based Hash Families and Black-Box Analysis(Symmetric Key Cryptography)(Cryptography and Information Security)
- 1-out-of-L E-voting System with Efficient Computational Complexity Based on r-th Residue Encryption
- A Simple Power Attack on a Randomized Addition-Subtraction Chains Method for Elliptic Curve Cryptosystems
- SCA-Resistant and Fast Elliptic Scalar Multiplication Based on wNAF (Asymmetric Cipher) (Cryptography and Information Security)
- Defeating Simple Power Analysis on Koblitz Curves(Discrete Mathematics and Its Applications)
- Security Analysis of the SPA-Resistant Fractional Width Method(Elliptic Curve Cryptography, Cryptography and Information Security)
- Cryptanalysis of Ha-Moon's Countermeasure of Randomized Signed Scalar Multiplication(Discrete Mathematics and Its Applications)
- Side Channel Attacks against Hash-Based MACs with PGV Compression Functions
- On the Importance of Protecting Δ in SFLASH against Side Channel Attacks(Tamper-Resistance)(Cryptography and Information Security)
- A New Upper Bound for the Minimal Density of Joint Representations in Elliptic Curve Cryptosystems(Discrete Mathematics and Its Applications)
- Analysis and Design of SHA-V and RIPEMD-V with Variable Output-Length
- Simple Power Analysis on Fast Modular Reduction with Generalized Mersenne Prime for Elliptic Curve Cryptosystems(Side Channel Analysis, Cryptography and Information Security)
- Enhancing Airport Access Control Security with Multiple Biometrics Contactless Smart Card (特集:新たな脅威に立ち向かうコンピュータセキュリティ技術)
- An Efficient Representation of Scalars for Simultaneous Elliptic Scalar Multiplication
- Usage Control Model and Architecture for Data Confidentiality in a Database Service Provider
- Usage Control Model and Architecture for Data Confidentiality in a Database Service Provider