隨意無線網路(Ad Hoc Networks)是由一群無固定基礎建設的行動通訊裝置集合而成，在這樣的網路環境中面臨許多挑戰，如遭受到主動及被動的攻擊、須提供即時與隨地之服務。因此本研究提出以門檻值憑證中心之架構為基礎，應用橢圓曲線密碼系統，建立適合隨意無線網路之公開金鑰基礎建設，使網路中被授命之節點(Mobile Agent Partial CA,稱之MAPC)能聯合簽署憑證，達到隨意無線網路之安全目標。本研究以橢圓曲線進行加解密，並以ECDSA進行數位簽署，如此與RSA比較大幅度降低運算時間及金鑰長度；同時亦採用秘密分享更新及定期對MAPC進行稽核之方式，來抵抗各種攻擊；另外針對隨意無線網路節點之移動特性，設計一MAPC個數、門檻值為可變動的網路環境，使隨意無線網路之公開金鑰基礎建設更具可行性。隨意無線網路的無線、移動性等特性，導致安全控管成為隨意無線網路中較弱的一環，公開金鑰基礎建設即提供了金匙分配及身分認證的安全機制，使得網路內之訊息傳遞能達成機密性、認證性、完整性及不可否認性之安全目標。

Mobile Ad Hoc network is a set of mobile devices without infrastructure. There are a lot of challenges in this environment, such as active interfering and passive eavesdropping, and offer the service on every time everywhere. Our research proposes to build PKI (Public Key Infrastructure) in Ad Hoc network which is base on threshold CA (Certificate Authority) and ECC (Elliptic Curve Cryptography) making partial authorized nodes (says Mobile Agent Partial CA, MAPC) in the network a coalition and to sign the certificate together to reach the secure goal of Ad Hoc network. In this research, we use ECC in encryption and decryption and sign the digital signature with ECDSA. After comparing with RSA, our research reduces the calculation time and cut down the length of key in evidence. Furthermore, we adopt to update the secret sharing periodical and audit MAPCs on a regular time schedule to prevent various kinds of attacks. According to the mobility of Ad Hoc network, we design a network environment which can modulate the number of MAPCs and the threshold value, making PKI in Ad Hoc network feasible and robust. Because of wireless, mobility and some properties of Ad Hoc network, security control is the vulnerability in the Ad Hoc network. By the key distribution and the identity authentication in PKI, the communication in the network achieves the secure gold that ensures privacy, authenticity, integrity and non-repudiation.

目 錄
1.	導論	1
2.	背景知識	3
2.1.	門檻值秘密分享	3
2.2.	橢圓曲線密碼學	4
2.2.1.	橢圓曲線密碼演算法	5
2.2.2.	橢圓曲線數位簽章演算法	6
3.	文獻探討	8
3.1.	JIEJUN KONG ET AL.之研究	9
3.2.	A. HERZBERG ET AL.之研究	11
4.	主架構	13
4.1.	環境初始化	15
4.1.1.	CA auditor參數設定：	15
4.1.2.	MAPC參數設定	15
4.1.3.	CA auditor分配參數	16
4.2.	憑證議題	17
4.2.1.	憑證頒發	17
4.2.2.	憑證更新及撤回	21
4.3.	取得秘密分享	21
4.4.	秘密分享暨門檻值更新	23
4.5.	離開網路標準流程	25
4.5.1.	MAPC主動離開網路流程	25
4.5.2.	Authorized user離開網路流程	25
4.6.	定理證明	26
5.	綜合分析與比較	28
5.1.	安全性與效能分析	29
5.2.	綜合比較	34
6.	結論	36
7.	參考文獻	37
附錄一：門檻值秘密分享	41
附錄二：橢圓曲線定義及運算規則	42
圖 目 錄
圖 1 :SHAMIR多項式方法原理	4
圖 2 :AD-HOC裝置進出及權限變更意識圖	13
圖 3 :系統架構圖	14
圖 4 :憑證頒發替代模式	17
圖 5 :MAPC定期稽核流程圖	30
圖 6 :橢圓曲線之圖形	42
圖 7 :兩個相異的點相加	43
圖 8 :雙倍的點 	44
表 目 錄
表 1 :不同安全度下RSA與ECC之金鑰長度比較	31
表 2 :不同安全度下RSA與ECDSA之密鑰長度比較	32
表 3 :ECDSA與 RSA簽章系統計算時間比較	32
表4 :本文與KONG等人之解決方案比較	35

[1]	楊中皇，橢圓曲線密碼系統軟體實現技術之探討， Communications of the CCISA Vol. 11 No. 1 January 2005.
[2]	A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung. Proactive Secret Sharing or: How to Cope with Perpetual Leakage. Extended abstract, IBM T.J. Watson Research Center, November 1995.
[3]	A. J. Menezes and S. A. Vanstone, Elliptic curve cryptosystems and their implementation. Journal of Cryptology, 6, 209-224.1993.
[4]	A. J. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer, 1993.
[5]	A. Shamir, How to Share a Secret, Comm. ACM Vol.22, pp.612-613, 1979.
[6]	ANSI X9.62-1998-Public Key Cryptography or the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA),1998.
[7]	B. Lehane, L. Doyle and D. O'Mahony. Shared RSA Key Generation in a Mobile Ad Hoc Network MILCOM 2003, October 2003.
[8]	C. M. Li, C. M. Wang and N. Y. Lee, Threshold-multisignature schemes where suspected forgery implies traceability of adversarial shareholders, Advances in Cryptology-EuroCrypto’94, Proc., Springer Verlag, pp. 194-204, 1994.
[9]	C. T. Wang, C. H. Lin and C. C. Chang, Threshold signature schemes with traceable signers in group communications, Computer Communications, Volume 21, Issue 8,pp. 771-776, 1998.
[10]	G. R. Blakley, Safegurading Cryptographic Keys, in Proc. NCC, Vol.48,pp.313-317,AFIPS Press, Montvale , N.J.1979.
[11]	J. H. Silverman and J. Tate, Rational Points on Elliptic Curves, Undergraduate Texts in Mathematics, Springer-Verlag, 1992.
[12]	J. Kong, P. Zerfos, L. Haiyun, L. Songwu and L. Zhang, Providing Robust and Ubiquitous Security Support for Mobile Ad-Hoc Networks. IEEE 9th International Conference on Network Protocols(ICNP’01),2001.
[13]	L. Ertaul, N. Chavan. Security of Ad Hoc Networks and Threshold Cryptography. 2005. 
[14]	L. Harn, Group-oriented (t, n) threshold digital signature scheme and digital multisignature, IEE Proc., Comput. Digit. Tech., Volume 141, Issue 5, pp. 307-313,1994.
[15]	L. Zhou and Z. J. Haas. Securing Ad Hoc Networks. IEEE Networks, 13(6):24–30, 1999.
[16]	N. Koblitz, A Course in Number Theory and Cryptography (Graduate Texts in Mathematics, No 114), Springer-Verlag, 1994.
[17]	N. Koblitz, Elliptic curve cryptosystems. Mathematics of Computation, 48, 203-209.1985.
[18]	NIST, DRAFT Special Publication 800-57, Recommendation on Key Management, January 2003.
[19]	Performance of Optimized Implementations of the NESSIE Primitives, New European Schemes for Signatures, Integrity, and Encryption, http://www.cryptonessie.org.
[20]	S. Jarecki, Proactive Secret Sharing and Public Key Cryptosystems , MIT Master of Engineering Thesis, 1995 .
[21]	S. Yi and R. Kravets. Moca: Mobile certificate authority for wireless ad hoc networks. The 2nd Annual PKI Research Workshop, 2003.
[22]	V. S. Miller. Use of elliptic curves in cryptography. Advances in Cryptology- CRYPTO’85, 218, 417-426.1985.
[23]	William Stallings,密碼學與網路安全-原理與實務,碁峯資訊股份有限公司,2004年.
[24]	Y. Desmedt and Y. Frankel, Shared generation of authenticators and signatures, Advances in Cryptology－Crypto’91, Proc., pp. 457-469, 1991.
[25]	Y. Desmedt and Y. Frankel, Threshold cryptosystem, Advances in Cryptology, Proc. Of Crypto’89, pp. 307-315, 1989.