在通訊技術快速發展的時代，資訊安全已經成為當前的重要課題。隨著計算性能的提升，全球科研力量正在加速推動量子計算的發展。量子計算機一旦成熟，將對現有的公鑰密碼體制造成嚴重威脅。例如，RSA和橢圓曲線加密算法面臨被在多項式時間內破解的風險。在諸多信息安全技術中，密碼編碼算法尤為關鍵。它們是保護信息傳輸和資料儲存安全的基石。一旦加密演算法被攻破，小則可能造成單個用戶的資料泄露，大則可能導致難以估量的損失。
為應對上述威脅，美國國家標準暨技術研究院（NIST）自2016年起組織了密碼學算法競賽，以標準化後量子時代的密碼技術，而CRYSTALS-Kyber為首批進入確認名單的加密，相較於NTRU、SABER等演算法，因相對小的加密金鑰可方便交換且執行快速的原因，所以被選為PQC目前的公鑰加密/金鑰建立的標準。
CRYSTALS-Kyber密碼的設計與實現中利用了KECCAK算法中的SHAKE擴展功能以及SHA-3雜湊功能。SHAKE用於擴展種子生成所需的隨機數，SHA-3則提供HASH以驗證信息完整性。Kyber官方論文亦指出AES也可以在Kyber中取代SHA-3用於擴展偽隨機位。本文將分析Kyber中的SHA-3與AES在功能與效能上的區別，並為不同應用場景設計對應的硬體加速器，以加速Kyber的密碼算法。
本文將參考AES和KECCAK的標準文檔，並基於CRYSTALS-Kyber算法的不同應用場景，設計對應的硬體加速器。我們將使用TSMC 40nm ASIC製程和FPGA開發板分別實現設計的硬體電路，收集其時脈頻率、面積、功耗等關鍵指標，並進行定量比較分析。通過比較，我們將評估在不同場景下，AES和KECCAK based硬體加速器的效能優劣。

In the era of fast-growing information technology, information security has become critical. Quantum computing poses serious threats to existing public key cryptosystems once mature, as algorithms like RSA and ECC face the risk of being cracked in polynomial time. Amid information security technologies, cryptographic algorithms are vital cornerstones for securing data transmission and storage. Breaking such algorithms may result in anything from individual privacy breaches to substantial financial losses.
To address the concerns, the National Institute of Standards and Technology (NIST) has hosted cryptographic competitions since 2016 to standardize post-quantum cryptography. As one of the first third-round candidates selected, CRYSTALS-Kyber features relatively small keys for efficient communication and fast speed, making it promising for post-quantum public key encryption/key establishment.
The CRYSTALS-Kyber design uses the SHAKE and SHA-3 functions of KECCAK for random number expansion and hashing. AES is pointed out to be able to replace SHA-3 for randomness generation in Kyber as well. This paper will analyze SHA-3 and AES’s functional and efficiency differences in enabling Kyber cryptographic algorithms, and architecting dedicated hardware accelerators for various application scenarios.

論文審定書 i
論文提要 ii
誌謝 iii
摘要 iv
Abstract v
目錄 vi
圖次 ix
表次 xii
第一章 序論 1
1.1 研究動機和目的 1
1.2 論文架構 3
第二章 研究背景 4
2.1 Shor’s Algorithm 4
2.2 PQC後量子密碼學[5] 5
2.3 晶格密碼學 7
2.4 Learning with errors 10
2.4.1 LWE 10
2.4.2 Ring-LWE(Ring Learning With Errors) 11
2.4.3 M-LWE 12
2.5 Crystals Kyber 13
2.5.1 Kyber參數集 15
2.5.2 基本演算法 15
2.5.3 Kyber.CPAPKE 17
2.5.4 Kyber.CCAKEM 21
2.6 雜湊函數 22
2.7 KECCAK 23
2.7.1 海綿結構 24
2.7.2 Input Padding 26
2.8 KECCAK-p 27
2.8.1 State Array 28
2.8.2 Step Mappings[30] 29
2.9 AES 35
2.9.1 有限體的運算 37
2.9.2 SubBytes / Inv-SubBytes 39
2.9.3 ShiftRows / Inv-ShiftRows 42
2.9.4 MixColumns/ Inv-MixColumns 43
2.9.5 Key Expansion 44
第三章 電路設計方法 46
3.1 KECCAK基礎硬體電路設計 46
3.2 AES Core基礎硬體電路設計 51
3.2.1 SubBytes / Inv-SubBytes 52
3.2.2 ShiftRows / Inv-ShiftRows 59
3.2.3 MixColumns/ Inv-MixColumns 59
3.2.4 Key Expansion 64
3.3 Kyber SHA-3應用分析 69
3.4 應用於Kyber之KECCAK電路設計 70
3.4.1 Padding 72
3.4.2 Truncate 73
3.4.3 KECCAK PE 74
3.4.4 Controller 77
3.5 應用於Kyber之AES-CTR電路設計 80
3.5.1 AES-CTR Parallels 81
3.5.2 AES-CTR pipelined 85
第四章 數據比較分析 88
4.1 Synopsys Design Compiler數據分析 88
4.2 Xilinx Vivado數據分析 92
4.2.1 SHA-3 比較 92
4.2.2 SHA-3與AES-CTR比較 96
第五章 結論與未來展望 98
5.1 結論 98
5.2 未來展望 99
參考文獻 100

[1] P. W. Shor, "Algorithms for quantum computation: discrete logarithms and factoring," in Proceedings 35th annual symposium on foundations of computer science, 1994: Ieee, pp. 124-134.
[2] P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer," SIAM review, vol. 41, no. 2, pp. 303-332, 1999.
[3] D. Beckman, A. N. Chari, S. Devabhaktuni, and J. Preskill, "Efficient networks for quantum factoring," Physical Review A, vol. 54, no. 2, pp. 1034-1063, 1996.
[4] J. Preskill, "Quantum computing in the NISQ era and beyond," Quantum, vol. 2, pp. 79-99, 2018.
[5] D. J. Bernstein and T. Lange, "Post-quantum cryptography," Nature, vol. 549, no. 7671, pp. 188-194, 2017.
[6] D. Micciancio and O. Regev, "Lattice-based cryptography," in Post-quantum cryptography: Springer, 2009, pp. 147-191.
[7] R. J. McEliece, "A public-key cryptosystem based on algebraic," Coding Thv, vol. 4244, pp. 114-116, 1978.
[8] C. Wolf, "Multivariate quadratic polynomials in public key cryptography," Cryptology ePrint Archive, 2005.
[9] J. Ding and D. Schmidt, "Rainbow, a new multivariable polynomial signature scheme," in International conference on applied cryptography and network security, 2005: Springer, pp. 164-175.
[10] L. Lamport, "Constructing digital signatures from a one way function," 1979.
[11] D. Jao and L. De Feo, "Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies," in Post-Quantum Cryptography: 4th International Workshop, PQCrypto 2011, Taipei, Taiwan, November 29–December 2, 2011. Proceedings 4, 2011: Springer, pp. 19-34.
[12] M. Ajtai, "Generating hard instances of lattice problems," in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, 1996, pp. 99-108.
[13] D. Aggarwal, Y. Chen, R. Kumar, and Y. Shen, "Improved (provable) algorithms for the shortest vector problem via bounded distance decoding," in 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), 2021: Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
[14] A. Mihăiţă and E. Simion, "A survey on lattice-based cryptography," 2012.
[15] O. Goldreich, D. Micciancio, S. Safra, and J.-P. Seifert, "Approximating shortest lattice vectors is not harder than approximating closest lattice vectors," Information Processing Letters, vol. 71, no. 2, pp. 55-61, 1999.
[16] M. R. Albrecht, R. Player, and S. Scott, "On the concrete hardness of learning with errors," Journal of Mathematical Cryptology, vol. 9, no. 3, pp. 169-203, 2015.
[17] O. Regev, "On lattices, learning with errors, random linear codes, and cryptography," Journal of the ACM (JACM), vol. 56, no. 6, pp. 1-40, 2009.
[18] V. Lyubashevsky, C. Peikert, and O. Regev, "On ideal lattices and learning with errors over rings," in Advances in Cryptology–EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30–June 3, 2010. Proceedings 29, 2010, pp. 1-23.
[19] C. Peikert, "A decade of lattice cryptography," Foundations and trends® in theoretical computer science, vol. 10, no. 4, pp. 283-424, 2016.
[20] Z. Wang, Q. Lai, and F.-H. Liu, "Ring/Module Learning with Errors Under Linear Leakage–Hardness and Applications," in IACR International Conference on Public-Key Cryptography, 2024, pp. 275-304.
[21] R. Avanzi et al., "CRYSTALS-Kyber algorithm specifications and supporting documentation," NIST PQC Round, vol. 2, no. 4, pp. 1-43, 2019.
[22] G. Alagic et al., "Status report on the third round of the NIST post-quantum cryptography standardization process," 2022.
[23] A. Dolmeta, M. Martina, and G. Masera, "Hardware architecture for CRYSTALS-Kyber post-quantum cryptographic SHA-3 primitives," in 2023 18th Conference on Ph. D Research in Microelectronics and Electronics (PRIME), 2023, pp. 209-212.
[24] M. J. Dworkin, "SHA-3 standard: Permutation-based hash and extendable-output functions," 2015.
[25] J. Daemen and V. Rijmen, The design of Rijndael. Springer, 2002.
[26] D. E. Standard, "Data encryption standard," Federal Information Processing Standards Publication, vol. 112, 1999.
[27] M. J. Wiener, "Efficient DES Key Search," Bell-Northern Research,, August 20, 1993.
[28] D. Canright, "A very compact S-box for AES," in International Workshop on Cryptographic Hardware and Embedded Systems, 2005, pp. 441-455.
[29] N. F. Pub, "197: Advanced encryption standard (AES)," Federal information processing standards publication, vol. 197, 2001.
[30] G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche, "Keccak," in Annual international conference on the theory and applications of cryptographic techniques, 2013, pp. 313-314.
[31] X. Zhang and K. K. Parhi, "High-speed VLSI architectures for the AES algorithm," IEEE transactions on very large scale integration (VLSI) systems, vol. 12, no. 9, pp. 957-967, 2004.
[32] J. Guajardo and C. Paar, "Itoh-Tsujii inversion in standard basis and its application in cryptography and codes," Designs, Codes and Cryptography, vol. 25, no. 2, pp. 207-216, 2002.
[33] T. Wada. "SubBytes Transform circuit for AES Cipher (Version 1.0).", 2003.
[34] J. Boyar and R. Peralta, "A new combinational logic minimization technique with applications to cryptology," in Experimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010, pp. 178-189.
[35] A. Maximov and P. Ekdahl, "New circuit minimization techniques for smaller and faster AES SBoxes," IACR Transactions on Cryptographic Hardware and Embedded Systems, pp. 91-125, 2019.
[36] H. Lipmaa, P. Rogaway, and D. Wagner, "CTR-mode encryption," in First NIST Workshop on Modes of Operation, 2000, vol. 39: Citeseer. MD.
[37] 王信中, 林志修, and 吳安宇, "具成本效益的 AES 加密引擎之設計與實現 DESIGN AND IMPLEMENTATION OF COST-EFFICIENT AES CRYPTOGRAPHIC ENGINE," 國立臺灣大學 [臺大工程] 學刊, 88, pp. 51-60, 2003.
[38] A. Dolmeta, M. Martina, and G. Masera, "Comparative study of Keccak SHA-3 implementations," Cryptography, vol. 7, no. 4, pp. 60-76, 2023.
[39] A. Sideris, T. Sanida, and M. Dasygenis, "A novel hardware architecture for enhancing the keccak hash function in fpga devices," Information, vol. 14, no. 9, pp. 475-490, 2023.
[40] K. Kim, S. Choi, H. Kwon, Z. Liu, and H. Seo, "FACE–LIGHT: Fast AES–CTR mode encryption for low-end microcontrollers," 22nd International Conference in Information Security and Cryptology–ICISC 2019, pp. 102-114.