進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-2707202015125300
論文名稱(中文) 應用於車內通訊以預先計算及多工處理之高效視窗橢圓曲線加密法
論文名稱(英文) Efficient Window-based ECC with Precomputation and Multitasking for In-Vehicle Communication
校院名稱 成功大學
系所名稱(中) 資訊工程學系
系所名稱(英) Institute of Computer Science and Information Engineering
學年度 108
學期 2
出版年 109
研究生(中文) 柯懷貿
研究生(英文) Huai-Mao Ko
學號 P76071195
學位類別 碩士
語文別 英文
論文頁數 76頁
口試委員 指導教授-張燕光
口試委員-陳永源
口試委員-陳培殷
口試委員-梁秋國
口試委員-楊中平
中文關鍵字 橢圓曲線加密法  進階加密標準  車聯網  MPC5748G  FreeRTOS  視窗法  非毗鄰表示法  預先計算  多工處理 
英文關鍵字 Elliptic Curve Cryptography  Advanced Encryption Standard  Internet of Vehicle  MPC5748G  FreeRTOS  Window based method  Non-adjacent form  Precomputation  Multitasking 
學科別分類
中文摘要 近年車聯網技術的蓬勃發展,使得其安全性越來越重要。橢圓曲線加密系統(ECC)是近年熱門的加密法,能以256位元的金鑰達成和RSA加密法在3072位元金鑰同樣的安全性。然而在車用開發版MPC5748G上作為gateway實現ECC,會因開發版資源有限且演算法複雜導致大幅延遲,不利於車聯網環境。尤其在車用設備之間的溝通上,若不能達成即時性,會影響駕駛安全。
考量到車內網路快速通訊的需求,本論文提出利用預先計算及多工處理來實現的基於窗口法之高效橢圓曲線加密系統。在車內網路會使用到的ECC演算法中,包括生成公鑰、Elliptic Curve Digital Signature Algorithm (ECDSA) 及Elliptic Curve Diffie-Hellman (ECDH),分析其中點乘法會重複使用到的被乘點,在預先計算階段先建出仿射基點表(Affine base-point table)。然後利用多工處理的特性,讓開發版在演算複雜的ECC時,幾乎不會影響其他設備間的溝通,並且同時建出雅可比公鑰表(Jacobian public-key table)。已知固定窗口(fixed window)及滑動窗口(sliding window)的非毗鄰表示法(non-adjacent form)能讓點乘法進一步精簡化,再分別套用上述的兩種表格,使得點乘法幾乎用不到點加倍運算。因此大幅提升ECC演算法效能,90毫秒內就能做完單次點乘法,耗時約為傳統方案的五分之一。而最花時間的ECDSA Verification能以約400毫秒完成,相較於其他方案皆超過500毫秒,更能夠適用於車內網路。最後,也提出讓車用設備在免ECDSA下,快速更新共同金鑰及公私鑰的方法,並且符合向前保密性(Forward Secrecy)。讓整體車內網路架構在受到中間人攻擊(man-in-the-middle)、重放攻擊(replay)以及共同金鑰洩漏的情況下,能夠維持安全性。
英文摘要 In recent years, the flourishing development of Internet of Vehicle (IoV) makes its security more important. Elliptic Curve Cryptosystems (ECC) that is the popular cryptograph nowadays only requires 256-bit keys to achieve the same level of security as RSA requiring 3072-bit keys. However, most development IoV boards like NXP MPC5748G perform ECC-based algorithms too slowly to meet IoV real-time requirement due to resource-constraints and algorithm’s complexity. Especially, the drivers may fall into danger if vehicular devices are unable to communicate in real-time.
In order to achieve fast in-vehicle communication, we propose an efficient window-based Elliptic Curve Cryptosystem augmented with precomputation and multitasking. By analyzing the reusable points needed in the scalar multiplications of ECC-based algorithms like public-key generation, Elliptic Curve Digital Signature Algorithm (ECDSA), and Elliptic Curve Diffie-Hellman (ECDH), we build Affine base-point table in the precomputation phase. Moreover, with the usage of multitasking, the communications between devices are nearly unaffected when the board is processing the complex ECC algorithms, and Jacobian public-key table is able to be built in the meantime.
As we know, the fixed window and sliding window methods with non-adjacent form can simplify scalar multiplications. We further apply Affine base-point table and Jacobian public-key table to these two window methods respectively, and propose two new schemes, fixed doubling-precomputation window method (fixed DPW method) and sliding doubling- precomputation window method (sliding DPW method) to nearly avoid the need of point doublings for achieving better performance. As a result, ECC’s performance can be improved to complete a single scalar multiplication in about 90ms which is a fifth of the time needed for the tradition scheme. Even for the most time-consuming process of ECDSA_verification, our improved approach takes about 400ms that is shorter than 500ms needed in the original approach. Finally, we also propose a fast scheme to update symmetric keys and private/public keys without ECDSA while providing Forward Secrecy.
By using our proposed schemes, we are able to show that the in-vehicle networks can resist intrusion from man-in-the-middle attack, replay attack, and the leakage of symmetric keys to keep the communication secure.
論文目次 摘要 i
Abstract ii
誌謝 iv
TABLE OF CONTENTS v
LIST OF TABLES vii
LIST OF FIGURES viii
Chapter 1 Introduction 1
1.1 Introduction 1
1.2 Organization of the Thesis 3
Chapter 2 Related work 4
2.1 Elliptic curve cryptography 4
2.1.1 Point addition and Point doubling 4
2.1.2 Public-key generation and Double-and-Add 7
2.1.3 Elliptic Curve Digital Signature Algorithm 9
2.1.4 Elliptic Curve Diffie-Hellman 10
2.2 Advanced Encryption Standard 11
2.3 Hash-based Message Authentication Code 12
2.3.1 Challenge-Handshake Authentication Protocol 12
2.3.2 Authenticated Encryption 13
2.4 Some improvements for scalar multiplication 14
2.4.1 Jacobian Coordinates 14
2.4.2 Doubling precomputation method 18
2.4.3 Fixed window method with non-adjacent form 19
2.4.4 Sliding window method with non-adjacent form 23
Chapter 3 Proposed scheme 27
3.1 Motivation & Overview 27
3.2 Analyzing the reusable points 29
3.3 Fixed doubling-precomputation window method 31
3.4 Affine base-point table 37
3.5 Multitasking 38
3.5.1 Computation task 38
3.5.2 Communication task 41
3.6 Sliding doubling-precomputation window method 46
3.7 Jacobian public-key table 51
3.8 Improved approach for ECDSA_verification 56
3.9 Updating keys 57
3.9.1 Updating symmetric keys 58
3.9.2 Updating key pairs 59
3.9.3 Security 62
Chapter 4 Experimental Result 64
4.1 Experimental Environment 64
4.2 Performance Evaluation 64
4.2.1 Performance of proposed schemes 65
4.2.2 Response time 70
Chapter 5 Conclusion 72
References 74

參考文獻 [1] NXP Semiconductors, MPC5748G Microcontroller Data Sheet, Available at https://www.nxp.com/docs/en/data-sheet/MPC5748G.pdf.
[2] NXP Semiconductors, MPC5748G QUICK START GUIDE (QSG) , Available at https://www.nxp.com/docs/en/quick-reference-guide/DEVKIT-MPC5748G-QSG.pdf
[3] NXP Semiconductors, MPC5748G Reference Manual, Available at https://www.nxp.com/webapp/Download?colCode=MPC5748GRM
[4] V.S. Miller, "Use of Elliptic Curves in Cryptography”, Proceedings of Advances in Cryptology – CRYPTO '85, vol. 218: Springer-Verlag, pp. 417-426, 1986.
[5] N. Koblitz, "Elliptic Curve Cryptosystems”, Proceedings of Mathematics of Computation, vol. 48, pp. 203-209, 1987.
[6] NIST, DRAFT Special Publication 800-57, “Recommendation for Key Management”, Mar 2007, Available at http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf.
[7] Youssef El Housni, “Introduction to the Mathematical Foundations of Elliptic Curve Cryptography”, hal-01914807, 2008.
[8] Hung-Nan Ye, Kuochen Wang, Rong-Hong Jan, Yuh-Jyh Hu, Yu-Chee Tseng, and Yi-Huai Hsu, “A Fast Window-based Scalar Multiplication Algorithm for Elliptic Curve Cryptography in Wireless Sensor Networks”, 2014 INTELLIGENT SYSTEMS AND APPLICATIONS (ICS 2014) Volume: 274, pp 1646-1655.
[9] Daniel M. Gordon, “Discrete logarithms in GF(P) using the number field sieve.”, SIAM J. Discrete Math., 6(1):124–138, 1993.
[10] Serge Vaudenay, “The security of DSA and ECDSA”, International Workshop on Public Key Cryptography, pp. 309-323.
[11] H. Wang, B. Sheng, and Q. Li, "Elliptic curve cryptography-based access control in sensor networks," Int. J. Security and Networks, vol. 1, pp. 127-137, 2006.
[12] Almuhammadi S., Al-Hejri I., “A comparative analysis of AES common modes of operation”, IEEE 30th Canadian Conference on Electrical and Computer Engineering (CCECE), 2017.
[13] Wikipedia, “HMAC”, Available: https://en.wikipedia.org/wiki/HMAC.
[14] G. Leduc, “Verification of two versions of the challenge handshake authentication protocol (CHAP)”, Annals of Telecommunications, 55(1-2):18–30, 2000.
[15] Y. A. Abbas, R. Jidin, N. Jamil and M. R. Z'aba, “Reusable Data-Path Architectures for EtM and MtE on FPGA”, Advanced Science Letters, vol. 24, no. 1, pp. 757-761, 2018.
[16] M. Bellare and C. Namprempre, "Authenticated encryption: Relations among notions and analysis of the generic composition paradigm", ASIACRYPT’00, vol. 1976, pp. 531-545, 2000.
[17] Anagha P. Zele, Avinash P. Wadhe, “Comparatively Study of ECC and Jacobian Elliptic Curve Cryptography”, International Journal of Science and Research (IJSR), 2015.
[18] H. Cohen, A. Miyaji, and T. Ono, “Efficient Elliptic Curve Exponentiation using Mixed Coordinates,” in Advances in Cryptology – Asiacrypt 1998, LNCS, Vol. 1514, pp. 51–65, Springer, 1998.
[19] V. Boyko, M. Peinado and R. Venkatesan, "Speeding up discrete log and factoring based schemes via precomputations" in Advances in Cryptology, Berlin, Germany:Springer-Verlag, vol. 1403, pp. 221-235, 1998.
[20] Rasmi, M, Sokhon, AA, Daoud, MS, et al, “A survey on single scalar point multiplication algorithms for elliptic curves over prime fields”, IOSR J Comput Eng 2016; 18: 31–47.
[21] Shouzhi Xu and Chengxia Li, "An Improved Sliding Window Algorithm for ECC Multiplication [J]", Proceedings of 2010 Conference on Dependable Computing (CDC’2010), pp. 335-338, November 20–22,2010.
[22] Wikipedia, “FreeRTOS”, Available: https://en.wikipedia.org/wiki/FreeRTOS.
[23] Chien, H. Y., & Chen, C. H. (2007), “Mutual authentication protocol for RFID conforming to EPC Class 1 Generation 2 standards”, Computer Standards & Interfaces, 29(2), 254–259.
[24] S. Bittl, "Efficient construction of infinite length hash chains with perfect forward secrecy using two independent hash functions", Proc. 2014 11th IEEE Int. Conf. Security and Cryptography, pp. 1-8, 2014.
[25] Adam Dunkels, "Design and Implementation of the lwIP TCP/IP Stack", Swedish Institute of Computer Science, 2001.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2025-08-24起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2025-08-24起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw