臺灣博碩士論文加值系統

T. Moh發明了基於馴變換(tame automorphism)的公開金鑰密碼系統，稱之為TTM (Tame Transformation Method)。在IWAP (International Workshop for Asian Public Key Infrastructures) 2002中，陳君明等人提出了TTS (Tame Transformation Signature)，同樣為基於tame automorphism之上的數位簽章演算法。本篇論文設計實作了該簽章演算法之軟體系統，並提出相關的效能報告。

T. Moh invented an asymmetric key cryptosystem based on tame transformation method called TTM (Tame Transformation Method). Unlike the ordinary discrete logarithm problem, the integer factorization problem, and the elliptic curve discrete logarithm problem which take lots of big number
modulo and exponential operations and thus are very time-consuming, TTM operates in a much higher speed.
However, since generating and verifying signatures is one of the most important applications of a public key cryptosystem, Chen et al. proposed TTS (Tame Transformation Signatures), a signature version of TTM, in IWAP
2002 [2].
What this thesis contributes is a practical and performance enhanced software system of TTS. Further, some comparisons between the performances of TTS scheme and the only three Federal Information Processing Standards (FIPS) approved algorithms for generating and verifying digital signatures:
DSA, RSA, ECDSA are made.

Abstract i
List of Figures iii
List of Tables iv
1 Introduction 1
2 Background 3
2.1 Finite Fields . . . . . . . . . . . . . . . . . . . 3
2.1.1 The Finite Field Fp . . .. . . . . . . . . . . . 4
2.1.2 The Finite Field F2m ... . . . . . . . .. . . . . 4
2.2 Tame Automorphisms to TTM . . . . . . . . . . . . . 6
2.3 TTS . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3.1 TTS-0 . . . . . . . . . . . . . . . . . . . . . . 9
2.3.2 TTS-r . . . . . . . . . . . . . . . . . . . . . . 11
3 Complexity Analysis and Discussion 13
3.1 TTS-0 . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.1 Signing Time Complexity . . . . . . . . . . . . . 13
3.1.2 Verifying Time Complexity . . . . . . . . . . . . 14
ii
3.2 TTS-r . . . . . . . . . . . . . . . . . . . . . . . 14
3.2.1 Signing Time Complexity . . . . . . . . . . . . . 14
3.2.2 Verifying Time Complexity . . . . . . . . . . . . 14
3.2.3 Discussion . . . . . . . . . . .. . . . . . . . . 14
4 Implementation Discussion and Performance Report 15
4.1 Implementation Discussion . . . . . . . . . . . . . 15
4.1.1 GF (2 8 ) Addition . . . . . . . . .. . . . . . . 15
4.1.2 GF (2 8 ) Multiplication . . . .. . . . . . . . . 16
4.1.3 Matrix Representation . . . . . . . . . .. . . . 17
4.2 Performance Report . . . . . . . . . . . . . . . . 19
5 Related Work and Performance Comparisons 22
5.1 Digital Signature Standard (DSS) . . . . . . . . . 22
5.2 Digital Signature Algorithms . . . . . .. . . . . . 23
5.2.1 The Digital Signature Algorithm (DSA) . . . . . . . . 24
5.2.2 Rivest, Shamir, and Adleman (RSA) . . . . . . . . . . 26
5.2.3 Elliptic Curve Digital Signature Algorithm (ECDSA) . 27
5.3 Performance Comparisons . . . . . . . . . . . . . . . 29
6 Conclusions and Future Work 31
Bibliography 33
iii
List of Figures
5.1 Digital Signature Standard Process . . . . . . . . . . . . . . . 23
iv
List of Tables
4.1 Notation . . . . . . . . . . . . . . . . . . . . . . . 19
4.2 TTS-0 (Env1) . . . . . . . . . .. . . . . . . . . . . . 20
4.3 TTS-r (Env1) . . . . . . . . . . . . . . . . . . . . . 20
4.4 TTS-0 (Env2) . . . . . . . . . . . . . . . . . . . . . 20
4.5 TTS-r (Env2) . . . . . . . . . . . . . .. . . . . . . . 21
5.1 Performance Comparisons . . . . . . . . . . . . . . . . 30

[1] Jiun-Ming Chen, Square-free Component Q 8 in TTM Cryptosystem, preprint.
[2] J.M. Chen, and B.Y. Yang, Tame Trnsformation Signatures With Topsy-Turvy Hashes.Proc. IWAP2002, pages 93-100.
[3] Chun-Yen Chou, D. J. Guan, and Jiun-Ming Chen, A Systematic Construction of a Q 2 k -module in TTM, Communications in Algebra, 30(2), pages 551-562 (2002).
[4] Chun-Yen Chou and D. J. Guan, Square-free Q 4 ; Q 6 and Q 8 modules in TTM, preprint
[5] Yuh-Hua Hu, Lih-Chung Wang, Jiun-ming Chen, Feipei Lai, and Chun Yen Chou, A Performance Report and Security Analysis of a fast TTM implementation, preprint.
[6] T. Moh, A Public Key System With Signature And Master Key Functions, Communications in Algebra, 27(5), 2207-2222 (1999).
[7] E.D. Win, S. Mister, B. Preneel, and M. Wiener. On the Performance of Signature Schemes Based on Elliptic Curves. Algorithmic Number 33 Theory Symposium III, LNCS 1423, J.P. Buhler, Ed., Springer-Verlag, 1998, pp. 252-266
[8] N. Koblitz, A Course in Number Theory and Cryptography, 2nd edition,Springer-Verlag, 1994.
[9] D. Johnson, A. Menezes, and S. Vanstone. The Elliptic Curve Digital Signature Algorithm, ANSI X9.62 and FIPS 186-2, 1998.
[10] Cristof Paar, A New Architecture for a Parallel Finite Field Multiplier with Low Complexity Based on Composite Fields, IEEE Transactions on Computers, Vol. 45, No. 7, July 1996.
[11] J.M. Chen, and B.Y. Yang, On the Secyrity and E鬣iency of TTS Signature Scheme, submitted.
[12] N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation, Vol. 48, No. 177, 1987, pp.203-209.
[13] V.S. Miller, Use of elliptic curves in cryptography, Advances in Cryptology - Proceedings of CRYPTO85, Springer Verlag Lecture Notes in Computer Science 218, pages 417-426, 1986.
[14] N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation, No, 48, 1987, pp. 203-209.