臺灣博碩士論文加值系統

這篇論文中介紹了一個同時適用在有限質數場和GF(2^m)有限場的橢圓曲線純量乘法器的通用型硬體架構。這個所提出的純量乘法器能支援最多256位元任意長度的有限質數場，且它也能應付GF(2^m)有限場不同的場多項式degree和p(x)。實現此可變的通用型硬體架構是根據蒙哥馬利的技術，包括蒙哥馬利的乘法器以及除法器。而所提出的蒙哥馬利模數除法理論也可以用來取代在蒙哥馬利域中的一個模數反元素運算和一個模數乘法運算。這個理論在計算模數除法時，比原本橢圓曲線所使用的方法效能較好，且設計成硬體時也比其他模數除法理論需要較小的面積。而用所提出的純量乘法器架構來計算橢圓曲線上的純量乘法也有合理的速度，例如它只需3.3毫秒就可以完成一個192位元的純量乘法運算。

1 introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivation . . . . . . . . . . . . . . . . . . . . 3
1.3 Thesis Organization . . . . . . . . . . . . . . . . . . . . . 4
2 Elliptic Curves 5
2.1 Basic Facts .. . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Elliptic Curves Arithmetic . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1 Elliptic Curves over the Reals . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.2 Elliptic Curves over Prime Fields . . . . . . . . . . . . . . . . . . . . . . . .12
2.2.3 Elliptic Curves over Extension of Binary Fields . . . . . . . . . . . 13
2.3 Elliptic Curves Scalar Multiplication . . . . . . . . . . . . . . . .. . . . 14
2.3.1 Double-and-Add Algorithm . . . . . . . . . . . . . . . . . . . . . . 14
2.3.2 Addition-Subtraction Method . . . . . . . . . . . . . . . . . . . .. . . . 15
2.3.3 Binary NAF Method . . . . . . . . . . . . . . . . . . . . .. . . 15
3 Finite Field Arithmetic 17
3.1 Modular Multiplication . . . . . . . . . . . . . . . . .. . . 17
3.1.1 Montgomery Multiplication Algorithm . . . . . . . . . . . . . . .. . . . . .. . 17
3.1.2 Modified Montgomery Multiplication Algorithm . . . . . . . . . .. . . . . . . . . . . . 19
3.2 Modular Inversion . . . . . . . . . . . . . . . . . . . . . . 21
3.2.1 Extended Euclidean Algorithm . . . . . . . . . . . . .. . . . . . . . . 21
3.2.2 Montgomery Modular Inverse Algorithm . . . . . . . . . . . . . . .. . . . . . . 23
3.3 Modular Division . . . . . . . . . . . . . . . . . . . . . . 25
3.3.1 Modular Division Algorithm . . . . . . . . . . . . . . . . . . . . . . 25
3.3.2 Montgomery Modular Division Algorithm . . . . . . . . . . . . .. . . . . . . . . 27
4 Proposed Universal Architectures 30
4.1 Universal Dual-field Montgomery Multiplier . . . . . . . . . . . . . . . . . . . . .. 30
4.2 Universal Dual-field Montgomery Divider . . . . . . . . . . . . . . . . .. . . . . . 33
4.3 Universal Dual-field Scalar Multiplier . . . . . . . . . . . . . . .. . . . . . . 36
5 Implementation Results 39
5.1 Design and Test Consideration . . . . . . . . . . . . . . . . . . . . 39
5.2 Hardware Implementation . . . . . . . . . . . .. . . . . . . . 40
5.2.1 ASIC Implementation . . . . . . . . . .. . . . . . . . . . 40
5.2.2 FPGA Implementation . . . . . .. . . . . . . . 42
6 Conclusion 44
A Elliptic Curve Cryptography 45
A.1 Elliptic Curve El-Gamal . . . . . . . . . . . . . . . . . . . . . . . 45
A.2 Elliptic Curve Diffe-Hellman . . . . . . . . . . . . . .. . . . . . . . . 45
A.2.1 Key Exchange . . . . . . . . . . . .. . . . . . . . . . 46
A.3 Elliptic Curve Digital Signature Algorithm . . . . . . . . . . . . . . . . . . 46
A.3.1 Key Pair Generation . . . . . . . . . . .. . . . . . . . 46
A.3.2 Signature Generation . . .. . . . . . . . . 46
A.3.3 Signature Verification . . . . . . . . . . . . . . . . . . 47

[1] W. Diffie and M. E. Hellman, “New directions in cryptography,” IEEE Transactions
on Information Theory, vol. IT-22, no. 6, pp. 644–654, 1976.
[2] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures
and public-key cryptosystems,” Commun. ACM, vol. 21, no. 2, pp. 120–126, 1978.
[3] T. E. Gamal, “A public key cryptosystem and a signature scheme based on discrete
logarithms,” in Proceedings of CRYPTO 84 on Advances in cryptology. New York,
NY, USA: Springer-Verlag New York, Inc., 1985, pp. 10–18.
[4] J. Cowie, B. Dodson, R. M. Elkenbracht-Huizing, A. K. Lenstra, P. L. Montgomery,
and J. Zayer, “A world wide number field sieve factoring record: On to 512 bits.”
in ASIACRYPT ’96: Proceedings of the International Conference on the Theory and
Applications of Cryptology and Information Security, 1996, pp. 382–394.
[5] V. S. Miller, “Use of elliptic curves in cryptography,” in Advances in Cryptology -
CRYPTO ’85, ser. Lecture Notes in Computer Science, H. C. Williams, Ed., vol. 218.
Springer-Verlag, 1986, pp. 417–426.
[6] N. Koblitz, “Elliptic curve cryptosystems,” Mathematics of Computation, vol. 48, no.
177, pp. 203–209, January 1987.
[7] Recommendation on Key Management, NIST Special Publications Std. 800-57, 2005.
[8] Advanced Encryption Standard (AES), FIPS PUBS Std. 197, 2001.
[9] Public Key Cryptography For The Financial Services Industry: Key Agreement and
Key Transport Using Elliptic Curve Cryptography, ANSI Std. X9.63, 2001.
48
[10] Public Key Cryptography For The Financial Services Industry: The Elliptic Curve
Digital Signature Algorithm (ECDSA), ANSI Std. X9.62, 2005.
[11] P. L. Montgomery, “Modular multiplication without trial division,” Mathematics of
Computation, vol. 44, no. 170, pp. 519–521, April 1985.
[12] B. S. Kaliski, Jr., “The Montgomery inverse and its applications,” IEEE Transactions
on Computers, vol. 44, no. 8, pp. 1064–1065, Auguest 1995.
[13] N. Koblitz, A course in number theory and cryptography. New York, NY, USA:
Springer-Verlag New York, Inc., 1987.
[14] J. H. Silverman, The Arithmetic of Elliptic Curves. New York, NY, USA: Springer-
Verlag New York, Inc., 1986.
[15] J. A. Solinas, “Efficient arithmetic on koblitz curves,” Des. Codes Cryptography,
vol. 19, no. 2-3, pp. 195–249, 2000.
[16] F. Morain and J. Olivos, “Speeding up the computations on an elliptic curve using
addition-subtraction chains,” Informatique th´eorique et Applications, vol. 24, pp.
531–544, 1990.
[17] C�� etin Kaya Ko��c, T. Acar, and B. S. Kaliski, Jr., “Analyzing and comparing mont-
gomery multiplication algorithms,” IEEE Micro, vol. 16, no. 3, pp. 26–33, June 1996.
[18] C. D. Walter, “Montgomery exponentiation needs no final subtractions,” Electronics
Letters, vol. 35, no. 21, pp. 1831–1832, October 1999.
[19] C�� . K. Ko��c and T. Acar, “Fast software exponentiation in GF(2k),” in ARITH ’97:
Proceedings of the 13th Symposium on Computer Arithmetic (ARITH ’97). Wash-
ington, DC, USA: IEEE Computer Society, 1997, p. 225.
[20] W. Diffie and M. E. Hellman, “New directions in cryptography,” IEEE Trans. Info.
Theory, vol. IT-22, pp. 644–654, November 1976.
[21] D. E. Knuth, The Art of Computer Programming, 3rd ed. Addison-Wesley, 1998,
vol. 2, ch. Seminumerical Algorithms.
49
[22] S. C. Shantz, “From euclid’s gcd to montgomery multiplication to the great divide,”
Sun Microsystems laboratories, Tech. Rep. TR-2001-95, June 2001.
[23] N. Takagi, “A vlsi algorithm for modular division based on the binary GCD algo-
rithm,” IEICE Trans. Fundamentals, vol. E81-A, no. 5, pp. 724–728, May 1998.
[24] C. C. Lin, F. K. Chang, H. C. Chang, and C. Y. Lee, “An universal VLSI architecture
for bit-parallel computation in GF(2m),” IEEE Asia-Pacific Conference on Circuits
and Systems, vol. 1, pp. 125–128, December 2004.
[25] A. Daly, L. Marnane, and E. Popovici, “Fast modular inversion in the montgomery
domain on reconfigurable logic,” in Irish signals and systems Conference (ISSC 2003),
July 2003, pp. 363–367.
[26] A. Daly and W. Marnane, “Efficient architectures for implementing Montgomery
modular multiplication and RSA modular exponentiation on reconfigurable logic,”
in FPGA ’02: Proceedings of the 2002 ACM/SIGDA tenth international symposium
on Field-programmable gate arrays. New York, USA: ACM Press, 2002, pp. 40–49.
[27] A. Daly, W. P. Marnane, T. Kerins, and E. M. Popovici, “Fast modular division for
application in ecc on reconfigurable logic.” in FPL, 2003, pp. 786–795.
[28] A. Tenca and L. Tawalbeh, “Algorithm for unified modular division in GF(p) and
GF(2n) suitable for cryptographic hardware,” Electronics Letters, vol. 40, no. 5, pp.
304–306, 2004.
[29] L. A. Tawalbeh, A. F. Tenca, S. Park, and C. K. Ko��c, “Use of elliptic curves in cryp-
tography,” in Thirty-Eighth Asilomar Conference on Signals, Systems, and Comput-
ers, vol. 1, November 2004, pp. 483–487.
[30] A. Satoh and K. Takano, “A scalable dual-field elliptic curve cryptographic proces-
sor,” IEEE Trans. Comput., vol. 52, no. 4, pp. 449–460, 2003.
[31] G. Z. Lu, “Hardware implementation of elliptic curve cryptosystem over finite fields
GF(p) and GF(2m),” Master’s thesis, National Chiao Tung University, 2004.
50
[32] C. J. McIvor, M. McLoone, and J. V. McCanny, “Hardware elliptic curve crypto-
graphic processor over GF(p),” IEEE Transactions on Circuits and Systems, vol. 53,
no. 9, pp. 1946–1957, September 2006.
[33] W. C. Hsu, “Design and implementation for elliptic curve cryptosystems,” Master’s
thesis, National Chiao Tung University, 2005.
[34] N. A. Saqib, F. Rodriguez-Henriquez, and A. Diaz-Perez, “A parallel architecture for
fast computation of elliptic curve scalar multiplication over GF(2m),” ipdps, vol. 04,
p. 144a, 2004.
[35] P. H. W. Leong and I. K. H. Leung, “A microcoded elliptic curve processor using fpga
technology,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems,
vol. 10, no. 5, pp. 550–559, October 2002.
[36] Public Key Cryptography Using Irreversible Algorithms - Part 2: The Secure Hash
Algorithm (SHA-1), ANSI Std. X9.30, 1997.