A Signed Binary Window Method for Fast Computing over Elliptic Curves (Special Section on Cryptography and Information Security)
スポンサーリンク
概要
- 論文の詳細を見る
The basic operation in elliptic cryptosystems is the computation of a multiple d/P of a point P on the elliptic curve modulo n. We propose a fast and systematic method of reducing the number of operations over elliptic curves. The proposed method is based on pre-computation to generate an adequate addition-subtraction chain for multiplier the d. By increasing the average length of zero runs in a signed binary representation of d, we can speed up the window method. Formulating the time complexity of the proposed method makes clear that the proposed method is faster than other methods. For example, for d with length 512 bits, the proposed method requires 602.6 multiplications on average. Finally, we point out that each addition/subtraction over the elliptic curve using homogeneous coordinates can be done in 3 multiplications if parallel processing is allowed.
- 社団法人電子情報通信学会の論文
- 1993-01-25
著者
-
KOYAMA Kenji
NTT Communication Science Laboratories
-
Tsuruoka Yukio
NTT Communication Science Laboratories
関連論文
- The Security of an RDES Cryptosystem against Linear Cryptanalysis (Special Section on Cryptography and Information Security)
- Special Section on Cryptography and Information Security
- Demonstrating Possession without Revealing Factors (Special Section on Cryptography and Information Security)
- Two Discrete Log Algorithms for Super-Anomalous Elliptic Curves and Their Applications(Special Section on Cryptography and Information Security)
- Efficient Cryptosystems over Elliptic Curves Based on a Product of Form-Free Primes (Special Section on Information Theory and Its Applications)
- A New RSA-Type Scheme Based on Singular Cubic Curves y^2≡x^3+bx^2 (mod n)
- Dynamic Swapping Schemes and Differential Cryptanalysis (Special Section on Information Theory and Its Applications)
- A New Version of FEAL, Stronger against Differential Cryptanalysis (Special Section on Cryptography and Information Security)
- A New RSA-Type Scheme Based on Singular Cubic Curves (y-αx)(y-βx )≡x^3 (mod n) (Special Section on Cryptography and Information Security)
- Fast Exponentiation Algorithms Based on Batch-Processing and Precomputation (Special Section on Cryptography and Information Security)
- A Signed Binary Window Method for Fast Computing over Elliptic Curves (Special Section on Cryptography and Information Security)
- Computing Short Lucas Chains for Elliptic Curve Cryptosystems (Special Section on Discrete Mathematics and Its Applications)
- Elliptic Curve Cryptosystems and Their Applications
- On the Solutions of the Diophantine Equation x^3+y^3+z^3=n
- How to Strengthen DES-like Cryptosystems against Differential Cryptanalysis (Special Section on Cryptography and Information Security)
- Improved Elliptic Curve Methods for Factoring and Their Performance (Special Section on Cryptography and Information Security)