Thiết kế phần cứng xử lý ntt và intt cho mã hóa lượng tử crystals kyber

TỔNG QUAN

Tình hình nghiên cứu trong và ngoài nước

2.1.1! Tình hình nghiên cứu ngoài nước

Trong các nghiên cứu trước đây, mã hóa lượng tử đã được triển khai trên phần cứng với một dạng mã hóa lattice-based gọi là Round5 Nghiên cứu này tập trung vào thiết kế phần cứng cho hàm băm SHA-3 Keccak, AES-GCM và thuật toán Round5 Lợi thế của mô-đun Round5 cho thấy sự đơn giản và hiệu quả khi áp dụng trên phần cứng, mở ra triển vọng cho việc ứng dụng mã hóa lượng tử trong tương lai Điều này không chỉ tiếp nối việc xử lý mã hóa trên phần cứng mà còn giúp giảm tải yêu cầu về tài nguyên xử lý cho các vi xử lý tác vụ chính.

Nghiên cứu [6] giới thiệu thiết kế phần cứng hoàn chỉnh cho CRYSTALS-Kyber, mang lại hiệu suất tăng tốc gấp 129 lần so với triển khai trên bộ xử lý Cortex-M4 [7].

[8], Jati và cộng sự trình bày thiết kế chống tấn công kênh ngoại (side-channel attack) đầu tiên của CRYSTALS-Kyber trên phần cứng với hiệu suất ấn tượng

Zhao và cộng sự đã tiến hành phân tích mã phần mềm nhằm tối ưu hóa thiết kế, đạt được kết quả tích cực Các triển khai của Kyber có sự đa dạng, từ bộ xử lý lai kết hợp giữa phần cứng và phần mềm cho đến các giải pháp phần cứng thuần túy.

Gần đây, việc triển khai phần cứng CRYSTALS-Kyber đã tối ưu hóa hiệu quả xử lý các thuật toán NTT và INTT Điều này được thực hiện nhờ vào việc các thành phần còn lại của Kyber dựa trên mã hóa hiện đại thuần túy, có thể tái sử dụng từ các nghiên cứu trước đây.

Trong các nghiên cứu đó, nhiều hướng tối ưu khác nhau được trình bày Nghiên cứu

Kỹ thuật K2-RED mới được trình bày trong [15] mang lại hiệu suất vượt trội cho việc tính số dư modulo trong cấu trúc NTT, so với các phương pháp truyền thống như Barret và Montgomery Ngoài ra, một kỹ thuật tính số dư modulo khác trong [16], [17] cũng đã được cải tiến với các hằng số được tính toán trước, góp phần nâng cao hiệu quả tính toán.

Zhang và cộng sự đã đề xuất sơ đồ truy cập bộ nhớ kiểu ping-pong nhằm tối ưu hóa hiệu quả truy cập RAM, đồng thời giải quyết vấn đề tắc nghẽn trong truy cập bộ nhớ, góp phần vào việc ứng dụng phần cứng của mã hóa lượng tử Ngoài ra, Poppelmann và cộng sự cũng đã giới thiệu cấu trúc chủ-tớ cho nhiều bộ nhân đa thức, kết hợp xử lý tính toán cho những phần yêu cầu sức mạnh xử lý lớn.

2.1.2! Tình hình nghiên cứu trong nước

Nghiên cứu mã hóa lượng tử tại Việt Nam vẫn còn hạn chế, nhưng đã có những tiến bộ đáng kể trong lĩnh vực phần cứng ứng dụng công nghệ FPGA và các thuật toán như Fast Fourier Transform trong những năm gần đây.

Nghiên cứu về hệ thống tính toán Fast Fourier Transform (FFT) 2048 điểm trên nền tảng FPGA cho thấy khả năng thực hiện phép nhân hiệu quả, với bộ nhân CORDIC là một giải pháp tối ưu Các nghiên cứu đã chỉ ra rằng cấu trúc bộ nhân sử dụng thanh ghi dịch có thể cải thiện hiệu suất tính toán FFT Biến đổi Fourier nhanh (FFT) không chỉ quan trọng trong xử lý tín hiệu và hình ảnh mà còn đang được ứng dụng trong mã hóa lượng tử, mở ra nhiều cơ hội cho các ứng dụng thực tiễn.

Nhiệm vụ đề tài

Nhiệm vụ của đề tài bao gồm các mục tiêu cụ thể nhằm đạt được kết quả mong muốn và xác định giới hạn của nghiên cứu Bài viết sẽ trình bày các kết quả nghiên cứu đã được thực hiện để minh chứng cho những mục tiêu đã đề ra.

Nội dung 1: Tìm hiểu lý thuyết mã hóa bất đối xứng, mã hóa lượng tử, NTT, các thành phần toán học cần thiết để thiết kế phần cứng

Nội dung 2: Xây dựng thiết kế phần cứng xử lý NTT và INTT cho mã hóa lượng tử CRYSTALS-Kyber, tổng hợp thiết kế và mô phỏng kiểm tra

Nội dung 3: Đánh giá, bàn luận về thiết kế So sánh kết quả đạt được với các nghiên cứu trước

Nội dung 4: Bàn luận về hướng phát triển tương lai và kết luận cho nghiên cứu

Phần tiếp theo của luận văn sẽ trình bày nội dung 1, trong khi phần 4 sẽ nêu rõ các điểm chính được đề cập trong nội dung 2 Tại phần 4, học viên sẽ trình bày các thông tin chi tiết liên quan đến nội dung này.

3 Học viên thực hiện kết luận và bàn luận hướng phát triển theo nội dung 4 ở phần 5 của luận văn Phần 6 là danh mục các công trình nghiên cứu của học viên Phần 7 là danh mục tài liệu tham khảo Phần 8 là phụ lục, gồm các ghi chú về từ ngữ sử dụng trong luận văn và các thông tin thêm.

NHỮNG NGHIÊN CỨU LÝ THUYẾT

Lý thuyết về mã hóa và mã hóa bất đối xứng

Mã hóa là quá trình biến đổi thông tin bằng cách sử dụng một chìa khóa mật mã, cho phép chỉ những bên sở hữu chìa khóa đó mới có khả năng giải mã và truy cập vào thông tin có nghĩa.

Mã hóa gồm 2 loại: mã hóa đối xứng và mã hóa bất đối xứng

Mã hóa bất đối xứng là phương pháp mã hóa sử dụng hai chìa khóa: chìa khóa công khai và chìa khóa bí mật Chìa khóa bí mật có thể mã hóa thông tin, trong khi chỉ có chìa khóa công khai mới có thể xác nhận và giải mã Phương pháp này thường dựa trên các vấn đề toán học phức tạp mà chỉ có thể giải quyết theo một chiều.

Hóa RSA dựa vào độ phức tạp của việc phân tích mã hóa công khai, trong đó mã hóa này được biểu diễn dưới dạng một hằng số mũ với chìa khóa bí mật Việc phân tích này liên quan đến việc tìm các thừa số của hằng số mũ, điều này tạo ra độ khó cho việc giải mã thông tin.

Mô hình mã hóa bất đối xứng bao gồm hai loại chìa khóa: chìa khóa công khai và chìa khóa bí mật Trong quá trình trao đổi thông tin, chìa khóa công khai được chia sẻ giữa hai bên, Bob và Alice, trong khi chìa khóa bí mật được giữ riêng bởi mỗi bên, đảm bảo tính bảo mật cho cuộc đối thoại.

Lý thuyết về CRYSTALS-Kyber

Lý thuyết về CRYSTALS-Kyber được giới thiệu bởi tác giả Avanzi và cộng sự, với thông tin chi tiết có sẵn tại trang web của CRYSTALS-Kyber Đây là một loại mã hóa sau lượng tử chưa được chuẩn hóa và đang trong quá trình cập nhật liên tục Trong nghiên cứu này, phiên bản CRYSTALS-Kyber được lựa chọn là phiên bản 3.

CRYSTALS-Kyber là một mô hình mã hóa bất đối xứng dựa trên bài toán Module Learning With Errors (MLWE) Mô hình này bao gồm hai phần chính: mã hóa công khai chống lại tấn công chọn văn bản (CPAPKE) và cơ chế đóng gói khóa bảo mật (CCAKEM) CPAPKE là bước cần thiết trong CCAKEM để thực hiện quá trình tạo mã khóa, mã hóa và giải mã Mặc dù CPAPKE có ba bước khác nhau, nhưng tất cả đều yêu cầu một phép toán nhân đa thức phức tạp Tóm lại, CRYSTALS-Kyber là hệ thống mã hóa bất đối xứng dựa trên MLWE và giao thức trao đổi kết quả từ phép toán này.

7 giới hạn �∀, nhiễu � thuộc phân phối nhiễu � và �, tìm � Các phương pháp được trình bày sau nhằm để tinh chỉnh độ phức tạp và hiệu quả của giải thuật

Hình 2 Minh họa gốc toán học phức tạp của phép toán lưới mà Kyber dựa trên

Cơ chế giao tiếp và chuyển đổi từ văn bản gốc m sang văn bản đã được mã hóa c được minh họa trong hình 3 Trong quá trình này, Alice và Bob thực hiện giao tiếp mã hóa Kyber Alice tạo ra chìa khóa mã, bao gồm chìa khóa công khai và chìa khóa bí mật Bob sử dụng chìa khóa công khai để mã hóa văn bản gốc m, sau đó Alice sử dụng chìa khóa riêng tư để giải mã văn bản đã mã hóa c trở lại văn bản gốc m.

Hình 3 Quy trình tạo khóa, mã hóa và giải mã của dạng mã hóa lưới

Figure 4 illustrates Ring-learning with errors (RLWE), a method that reduces the storage of matrices from \( n^2 \) elements to \( n \) elements This serves as the foundation for the Module Learning with Errors (MLWE) scheme used in Kyber.

Hình 4 minh họa về Ring-learning with errors (RLWE), trong khi Hình 5 trình bày Module-learning with errors (MLWE) mà Kyber áp dụng Kyber sử dụng thông số k để gia tăng độ phức tạp của ma trận A, từ đó nâng cao tính linh hoạt cho thuật toán.

Hình 5 Module-learning with errors (MLWE)

Kyber sử dụng nhiều phép nhân đa thức, với các đa thức được biểu diễn qua hệ số sắp xếp theo bậc trong ngôn ngữ lập trình thông thường Ba thuật toán chính của Kyber bao gồm mã hóa, giải mã và tạo mã, được thể hiện rõ ràng trong hình 6.

Hình 6 Ba giải thuật tao mã, mã hóa và giải mã của Kyber [2]

Một phương pháp hiệu quả để xử lý phép nhân đa thức là Biến đổi Số học (NTT), và vì lý do này, NTT được tích hợp vào định nghĩa của Kyber Các tham số của các phiên bản Kyber đã được tối ưu hóa để tính toán hiệu quả với NTT Hình 7, 8, 9 minh họa vai trò quan trọng của NTT trong quá trình tạo khóa, mã hóa và giải mã của Kyber.

9 Hình 7 NTT trong giải thuật tạo mã của Kyber [2]

Hình 8 NTT trong giải thuật mã hóa của Kyber [2]

Hình 9 trình bày NTT trong giải thuật giải mã của Kyber Bảng 1 cung cấp thông số chi tiết cho từng phiên bản của Kyber, được tối ưu hóa cho việc sử dụng NTT Nghiên cứu chủ yếu tập trung vào phiên bản với thông số n = 256 của Kyber.

Bảng 1 Thông số của từng phiên bản Kyber

Bảng dưới đây trình bày các thông số của các phiên bản Kyber, bao gồm Kyber512, Kyber768 và Kyber1024 với các tham số như n, k, q, η1, η2, (du,dv) và δ NTT (Biến đổi số học nhanh) đóng vai trò quan trọng trong thuật toán mã hóa CRYSTALS-Kyber Phần tiếp theo sẽ trình bày lý thuyết về NTT, INTT và các thuật toán tương ứng được sử dụng trong nghiên cứu.

Lý thuyết về Number Theoretic Transform (NTT)

Mã hóa CRYSTALS-Kyber dựa vào yếu tố thiết yếu là NTT, với nghiên cứu chi tiết về phép nhân đa thức trong Kyber NTT, viết tắt của Number Theoretic Transform, và INTT, hay NTT -1, là phép biển đổi ngược Inverse Number Theoretic Transform, đóng vai trò quan trọng trong việc xác định vị trí sử dụng các thuật toán này.

Để biểu thị một đa thức trên máy tính, phương pháp biểu diễn hệ số (coefficient representation) được sử dụng Dạng hiển thị này lưu trữ các hệ số của phương trình dưới dạng một dãy hệ số trên máy tính.

Một phương pháp khác để biểu diễn đa thức là thông qua dạng giá trị, trong đó một đa thức bậc d cần d+1 điểm để thể hiện Điểm nổi bật của dạng biểu diễn này là việc nhân đa thức trở nên đơn giản hơn Để chuyển đổi giữa dạng hệ số và dạng giá trị, kỹ thuật Biến đổi Fourier nhanh (FFT) và Biến đổi Fourier ngược (IFFT) được áp dụng.

Kỹ thuật FFT và IFFT có độ phức tạp O(N log N), mang lại cải thiện đáng kể so với độ phức tạp O(N!) của Biến đổi Fourier rời rạc Trong trường hợp một trường giới hạn trong vành như Kyber trong trường Zq, việc thay đổi dạng biểu diễn của đa thức được thực hiện thông qua kỹ thuật Biến đổi Số lý (NTT) và Biến đổi Nghịch đảo NTT (INTT).

Kết quả nhân đa thức ℎ = � ∙ � có thể được tính với NTT và INTT như phương trình bên dưới:

Phiên bản cổ điển của NTT là phương trình như sau [32]:

� = 0, 1, , � − 1 Phiên bản cổ điển của INTT là phương trình như sau [32]:

� = 0, 1, , � − 1 Với ω∗ là primitive nth root of unity Để tính toán chi tiết NTT, các butterfly unit (BU) của Fast Fourier Transform (FFT)

Các phương pháp NTT với BU Cooley-Tuckey (CT) và INTT với BU Gentleman-Sande (GS) được sử dụng để thiết kế hiệu quả cho phần cứng có thể lập trình được Hình 11 minh họa sơ đồ tổng quát cho các đơn vị BU này.

Hình 10 Mô hình của các Butterfly Unit (BU) (1) Cooley - Tukey Butterfly (2) Gentleman -

3.3.2! Phiên bản NTT/INTT tối ưu được sử dụng

Kyber có độ dài n = 256, với ma trận A hoặc phương trình h có 256 phần tử hệ số Để xử lý NTT cho hai hàm f và g với 256 phần tử hệ số thành 512 phần tử hệ số, trong đó có 256 phần tử đệm bằng 0, cần sử dụng thuật toán NTT với Negative Wrapped Convolution (NWC) như được trình bày bởi Poppelman và cộng sự Theo Định lý 1, với ω là căn bậc nguyên bậc 2^n thuộc tập hữu hạn Zp, các vectơ W và Z được định nghĩa với độ dài n và 2n, trong đó phần tử sau chứa số 0 Định lý 2 cho biết ω là căn bậc nguyên n-th thuộc Zp và ω ≠ 1, từ đó đưa ra các quy tắc tính toán cho phép nhân các phần tử hệ số.

� = Υ�), … , �(,#∃)Wvà � = Υ�), … , �(,#∃)W là các vectơ có độ dài � với các phần tử thuộc Zp

1 Tích từng thành phần hệ số bọc dương của � và � là ��� #∃(��� (�) ���.(�))

2 Gọi � = Υ�), … , �(,#∃)W là tích hệ số bọc âm của � và � Cho �∴, �∴ �à �̅ được xác định là Υ�), ��∃, … , � (∗#∃) �(,#∃)W, Υ�), ��∃, … , � (∗#∃) �(,#∃)W và Υ�), ��∃, … , � (∗#∃) �(,#∃)W Khi đó �̅ = ��� #∃(��� (�∴) ∗ ���.(�∴)). Ở bài nghiên cứu này, ta định nghĩa với ω∗ là primitive nth root of unity và � = � , Với các phép toán trong vành �∀[�]/(� , + 1), có thể sử dụng NWC Định lý 2.2 nếu thỏa mãn điều kiện � ≡ 1 ��� 2�

Với Kyber, số nguyên tố � không thỏa mãn � ≡ 1 ��� 2� với Kyber thuộc vành đa thức �∀ là vành �∀[�]/(� , + 1) ( � = 3329; � = 256)

Kết quả NTT/INTT của Kyber có thể được tính bằng tích hệ số bọc âm, theo phần 2 của định lý 2 (NWC) Phương trình bậc n có thể được phân tích như sau: � ∈.

�∀[�]/(� , + 1) ở dạng coefficient representation thành hai phương trình bậc �/2 là �/0/,(� ! ) và �122(� ! ) tương ứng với các hệ số chẵn và lẻ tương ứng và �/0/,, �122 ∈

�∀[� ! ]/Υ(� ! ) ,/! + 1W Khi đó, ta có thể khôi phục �(�) bằng cách sắp xếp hệ số với

Để tính NTT/INTT cho Kyber, chúng ta sử dụng NWC cho hai phương trình �/0/,, �122 với hệ số �′ = �/2 = 256/2 = 128, từ đó định nghĩa � = 128 Cụ thể, NTT được tính với ���(�(�)) = (���(�/0/,), ���(�122)), trong khi INTT cũng được tính theo cách tương tự.

Khi đó số nguyên tố � thỏa mãn � ≡ 1 ��� 2� với Kyber thuộc vành đa thức �∀ là vành �∀[�]/(� , + 1) ( � = 3329; � = 128)

Khi sử dụng NWC, cần thực hiện quy trình xử lý trước và sau cho các hệ số đa thức đầu vào và đầu ra, nhân chúng với � và � #∃ như mô tả trong hình 11 Điều này giúp loại bỏ các thành phần � và đưa bài toán về kết quả � = ��� #∃(��� (�).

Hình 11 NWC NTT và INT với xử lý trước và xử lý sau Phiên bản NWC của NTT là phương trình như sau :

� = 0, 1, , � − 1 Phiên bản NWC của INTT là phương trình như sau :

Để tối ưu hóa cho thuật toán NTT, một giải pháp hiệu quả là sử dụng thuật toán NTT/INTT với độ phức tạp thấp, như được nghiên cứu trong tài liệu [32] Đặc biệt, độ phức tạp của thuật toán NTT cổ điển với NWC cần được xem xét kỹ lưỡng để cải thiện hiệu suất.

�Υ� 2ϕ log � + �W, �ϕ log �2 là độ phức tạp của NTT và N bước nhân ban đầu với �!, � , Sử dụng kết quả của phương trình (3) từ [32] như sau:

Sử dụng kết quả của (3) thay cho �, sẽ giảm bớt bước tiền xử lý xử lý và độ phức tạp của giải thuật NTT xuống còn �Υ� 2ϕ log �W

Nghiên cứu [32] đã đề xuất một phương pháp mới cho INTT nhằm loại bỏ bước xử lý hậu kỳ 1/N bằng cách chia nửa kết quả từ BU GS Phương pháp này giúp giảm độ phức tạp của INTT xuống còn �Υ� 2ϕ log � + �W, tối ưu hóa cấu hình xử lý với BU của Gentleman-Sande.

#∋�!& #∃ Phương trình (4) cho thấy đây là phương trình tương tự NWC INTT ở trên, nhưng đã giảm xuống N/2 điểm thay vì N điểm

Có thể chứng minh lại (4) đơn giản hơn từ gốc của NTT, NTT thực hiện Cooley-Tuckey với số lượng lớp � với 2 8 = �, ở lớp cuối cũng ta sẽ có:

Ở bước tính nghịch đảo NTT, chúng ta có các biểu thức �ο () và �ο (∃) Cần tìm �) và �9: Để đạt được kết quả, ta lần lượt thực hiện phép cộng và phép trừ giữa hai phương trình.

Với số lượng lớp � và công thức 2^8 = �, việc chia 2 là bước rút gọn từ gốc của từng lớp nghịch đảo NTT (INTT) thành 2^#8 = 1/� Thay vì xử lý 1/� ở giai đoạn cuối, chúng ta thực hiện chia 2 cho từng kết quả của BU GS Do đó, bỏ qua phần hậu xử lý 1/�, độ phức tạp hiện tại của INTT được cải thiện.

Tương tự như NTT (3), độ phức tạp hiện tại của INTT là �Υ� 2ϕ log � + �W Ta cũng có kết quả phương trình INTT gốc

Kết quả từ (5) cũng giúp giảm bước xử lý hậu kỳ nhân � #∃ Qua đó giảm độ phức tạp của INTT còn �Υ� 2ϕ log �W

Thuật toán 1 và 2 mô tả các phép toán NTT và INTT đã được tối ưu hóa, là phiên bản cơ sở cho thiết kế phần cứng Những sửa đổi nhỏ được thực hiện để phù hợp với thiết kế này, như đã nêu trong tài liệu [5] [19] [32] Thuật toán 1 giới thiệu giải thuật NTT với độ phức tạp thấp thông qua phương pháp BU Cooley - Tukey Hàm đảo ngược bit (bit-reverse) là hàm thực hiện việc đảo thứ tự các hệ số của đa thức Trong khi đó, Thuật toán 2 trình bày giải thuật INTT sử dụng phương pháp BU Gentleman – Sande.

Thuật toán 1 Low complexity NTT operation with Cooley – Tuckey butterfly

Input: polynomial �(�), �∃, … , �,#∃) as �(�) ∈ ℤ∀[�]/(�,+ 1), �, ∈ ℤ∀is the N-th primitive root of unity, � = 2 8 and �!,= � ,

Thuật toán 2 Low complexity INTT operation with Gentleman – Sande butterfly

Input: polynomial �Γ(�), �∃, … , �,#∃) as �Γ(�) ∈ ℤ∀[�]/(�,+ 1), �, ∈ ℤ∀is the n-th primitive root of unity, � = 2 8 and �!,= � ,

Lý thuyết về phép toán rút gọn modulo Exact-KRED

Phiên bản rút gọn modulo cải tiến Exact-KRED được phát triển từ thiết kế KRED, K-RED-2x và K2-RED KRED là một biến thể của bộ rút gọn modulo Montgomery, được tối ưu hóa cho một loại modulus đặc biệt, như được mô tả trong phương trình liên quan.

Kyber sử dụng modulus là số nguyên tố q = 3329 với k = 13 và m = 8 Khi áp dụng KRED và K-RED-2x cho một số đầu vào C, kết quả thu được là � ∙ � ��� � Sử dụng K 2 -RED, kết quả là � ! ∙ � ��� � Nghiên cứu cho thấy K 2 -RED tiết kiệm bộ nhớ hơn và phù hợp với mô-đun 12-bit � hơn so với K-RED-2x Đơn vị mô-đun được thực hiện sau bước nhân trong BU, và để bù phần dư � ! trong kết quả � >>, cần xử lý trước � thành � > = (� #! ∙ �) ��� �.

Thuật toán Exact-KRED cho Kyber được trình bày trong thuật toán 3, trong đó các chức năng zero-extend và signed-extend thực hiện việc mở rộng độ dài bit với phần đệm tương ứng là 0 và theo dấu của số nhị phân Chiều dài bit của phần mở rộng được ghi chú sau hàm Theo tài liệu [20], giải thuật KRED chỉ ra rằng có những trường hợp kết quả bị tràn với một số giá trị nhất định Trong quá trình triển khai K2-RED, kết quả sẽ bị tràn khi giá trị � >> lớn hơn modulus q, dẫn đến tình trạng này xảy ra.

Để giải quyết tình trạng số âm hiển thị dưới dạng không dấu công 2 ∃! > �, một phép cộng có điều kiện cho � >> đã được thêm vào sau dòng 6 của thuật toán 3.

Thuật toán 3 Exact-KRED for Kyber NTT/INTT accelerator

1: Cl ← zero-extend(�≅, … , �∃, �)) to 16-bit

4: Cl’← zero-extend(�′≅, … , �′∃, �′)) to 12-bit

5: Ch’←signed-extend(�′!?, … , �′Α, �′Β) to 12-bit

Về bộ nhớ BRAM M10K trên FPGA Cyclone V

Bộ nhớ BRAM M10K trên FPGA Cyclone V hỗ trợ nhiều chế độ, bao gồm Simple Dual Port và True Dual Port Để thực hiện cấu hình BU 2x2 với 2 đầu vào 24-bit cho 2 BU, chế độ Simple Dual Port là lựa chọn phù hợp đáp ứng đủ nhu cầu sử dụng.

Theo nghiên cứu [29], khi sử dụng BRAM M10K, quá trình tạo BRAM thông qua ngôn ngữ mô tả phần cứng hoặc trình tạo IP từ Quartus cần phải thực hiện việc đặt thanh ghi đầu ra cho BRAM.

Số lượng lớp thanh ghi đầu ra tối ưu cho thiết kế là từ 2 đến 3 lớp, đủ để phần mềm Quartus sắp xếp đường đi cho dữ liệu từ BRAM đến mạch tổ hợp tiếp theo với hiệu suất tốt nhất Việc sử dụng nhiều hơn 3 lớp thanh ghi thường không cần thiết, trừ một số trường hợp đặc biệt do giới hạn của 3 tầng logic của chip.

Xử lý tính toán lý thuyết trên phần mềm máy tính

Phần giải thuật NTT/INTT và các Twiddle Factor được xử lý và tính toán trước trên máy tính bằng phần mềm Microsoft Excel Trong đó có các bước:

- Tìm giá trị �, (với Wolfram) và �!,= � , , � > = (� #! ∙ �) ��� �

- Chuyển đổi từ công thức cấu hình 1 BU sang 2 x 2 BU

- Sắp xếp vị trí đầu vào và thứ tự truy xuất bộ nhớ

Với phiên bản � = 128 sẽ thiết kế và đánh giá, tính được giá trị

�, = 33 ∃!Β ��� 3329 = 1Dựa trên điều kiện NWC hay công thức Euler, �!,có tồn tại Để tìm �!, � , , thực hiện bảng tính Excel cho ra giá trị như sau:

Với 2 giá trị �!, = � , tìm được là 892 và 2437 Ở các phần tính toán tiếp theo, thiết kế chỉ sử dụng giá trị nhỏ hơn là 892 Bảng 3 trình bày tới số thứ tự mũ 24 trên 127 (từ 0 đến

Bảng 3 Thực hiện tính �!, ở các giá trị mũ khác nhau (bảng tới mức mũ 24)

Để tối ưu hóa vị trí Twiddle Factor và thứ tự truy xuất bộ nhớ, các thứ tự này đã được sắp xếp trước trên Excel Chi tiết về các bản số liệu được tính toán đầy đủ được trình bày trong phần phụ lục 8.3.

TRÌNH BÀY, ĐÁNH GIÁ VÀ BÀN LUẬN KẾT QUẢ

Thiết kế phần cứng xử lý NTT và INTT cho CRYSTALS-Kyber

Chúng tôi giới thiệu thiết kế phần cứng cho việc xử lý NTT và INTT trong mã hóa lượng tử CRYSTALS-Kyber, chia thành hai phần Phần đầu tiên tập trung vào cấu trúc phần cứng của bộ gia tốc được điều chỉnh theo thuật toán 1 và 2 Tiếp theo, phần thứ hai trình bày kiến trúc tổng thể của bộ gia tốc với cấu hình đơn vị cánh bướm 2x2.

4.1.1! Thiết kế butterfly unit xử lý CT/GS

4.1.1.1!Thiết kế bộ xử lý rút gọn modulo Exact-KRED

Bộ rút gọn modulo Exact-KRED được thiết kế cho q = 3329 của Kyber, bao gồm 5 tầng pipeline xử lý rút gọn modulo liên tục Quy trình đầu tiên xử lý đầu vào 24-bit từ bộ nhân DSP thành ngõ ra 16-bit, tiếp theo là quy trình thứ hai chuyển đổi ngõ ra 16-bit thành ngõ ra 12-bit Cuối cùng, bộ cộng có điều kiện được sử dụng để xử lý các trường hợp tràn, với độ dài 12-bit cho q, giúp tiết kiệm tài nguyên nhờ chỉ sử dụng một bộ cộng, bộ so sánh và một bộ mux lựa chọn điều kiện.

Sơ đồ khối bộ rút gọn modulo Exact-KRED (Hình 12) mô tả quy trình phân nhánh ngõ vào thành các dải bit cao và bit thấp Dải bit thấp được kết hợp với bộ dịch để thực hiện zero-extend và signed-extend Quy trình đầu tiên sử dụng 2 clock, và quy trình tiếp theo cũng sử dụng 2 clock, trong đó bộ cộng có điều kiện kiểm tra kết quả trước khi chuyển tiếp sang ngõ ra.

Hình 12 Sơ đồ khối của bộ rút gọn Modulo Exact-KRED

4.1.2! Bộ rút gọn modulo chia nửa

Theo thuật toán 2, bộ GS cần chia nửa theo modulus q Việc chia nửa một số theo modulo q có hai trường hợp: nếu số là chẵn, chỉ cần dịch phải để có kết quả; còn nếu số là lẻ, kết quả chia nửa modulo q được tính theo cách khác.

Vỡ nếu rỳt gọn tiếp tục ẵ ��� � khụng phải là số tiện lợi để xử lý Với q là số nguyờn tố, ∀5∃

! với � = 3329 của Kyber cho kết quả là hằng số 1665 Phương trình sau trình cho kết quả:

Bộ rút gọn modulo chia nửa chỉ bao gồm một bộ mux, một bộ cộng và một bộ dịch phải

1 vì { Φ ! | = (� ≫ 1) Bộ này được pipeline 2 tầng để tăng tốc độ của mạch

4.1.3! Thiết kế butterfly unit xử lý CT/GS

Hình 13 Phần cứng butterfly unit xử lý CT/GS Bảng 4 Bảng chân phần cứng butterfly unit xử lý CT/GS

Tên chân Loại ngõ Độ dài

The clk input serves as the system clock, while rst is used for resetting the system The u input accepts 12 data entries, t also accepts 12 data entries, and w is designated for 12 data entries related to the Twiddle Factor The sel input, with 2 options, allows users to select the operational mode.

- 10,11 Bypass (Bỏ qua và tiếp nối dữ liệu sang ngõ ra) s0 Ra 12 Ngõ ra dữ liệu kết quả 1 s0 s1 Ra 12 Ngõ ra dữ liệu kết quả 2 s1

Bộ BU bao gồm hai thành phần chính là bộ rút gọn modulo và hai bộ cộng trừ modulo Các bộ cộng trừ này được thiết kế đơn giản với khả năng sắp xếp bù q cho kết quả cộng trừ 12-bit Để tăng tốc độ mạch, mỗi bộ được áp dụng pipeline 3 tầng Bộ nhân chuyển đổi từ 12-bit sang 24-bit sử dụng một đơn vị DSP của FPGA, cùng với các thành phần nhỏ như mux và thanh ghi.

Chúng tôi đã thiết kế bộ bướm phần cứng đáp ứng yêu cầu cho cả giải thuật CT và GS Bộ BU này bao gồm các thành phần như bộ cộng số học modulo (bao gồm một phép cộng và một phép trừ), bộ nhân DSP, bộ rút gọn modulo Exact-KRED, cùng với hai bộ rút gọn modulo chia nửa.

Butterfly Unit cl clk rst u t w sel s0 s1

23 modulo chia nửa cho mức tiêu thụ tài nguyên không đáng kể Ngõ ra của bộ nhân nối trực tiếp vào ngõ vào của bộ Exact-KRED

Hình 14 trình bày cấu trúc chi tiết của thiết bị, trong đó bộ nhân DSP và đơn vị Exact-KRED có độ trễ tổng cộng là 7 chu kỳ Độ trễ này ảnh hưởng đến đường dẫn chặn dữ liệu và được điều chỉnh theo tổng độ trễ Tổng độ trễ cho mỗi quy trình thực hiện giải thuật CT/GS trên thiết bị cánh bướm được xác định rõ ràng.

Bài viết mô tả quy trình hoạt động của một hệ thống với 13 chu kỳ, trong đó đầu vào và đầu ra đã được tổ chức qua pipeline Tín hiệu Sel được sử dụng để xác định chế độ hoạt động Việc thực hiện phép cộng và phép trừ mô-đun với hai bộ cộng mô-đun không làm giảm đáng kể hiệu suất tốc độ, nhờ vào số nguyên tố q 12-bit nhỏ Đối với giải thuật CT, tín hiệu từ mux được sử dụng, và bộ cộng dự kiến nhận kết quả nhân mô-đun sau 11 xung nhịp kể từ khi dữ liệu được nhập Để đồng bộ với độ trễ của giải thuật GS, độ trễ 2 xung nhịp được thêm vào giải thuật CT Trong khi đó, giải thuật GS sử dụng đường dẫn bên dưới của mux, với bộ rút gọn modulo chia nửa tiêu tốn 2 xung nhịp Tổng độ trễ khi bộ BU hoạt động được xác định bởi các yếu tố này.

Hình 14 Bộ Butterfly Unit kết hợp CT/GS cho thuật toán độ phức tạp thấp

4.1.4! Thiết kế phần cứng xử lý NTT và INTT cho CRYSTALS-Kyber

Hình 15 Phần cứng xử lý NTT và INTT cho CRYSTALS-Kyber Bảng 5 Bảng chân phần cứng xử lý NTT và INTT cho CRYSTALS-Kyber

Tên chân Loại ngõ Độ dài

Công dụng của hệ thống bao gồm: clk (1 chân) dùng để đồng bộ hóa, rst (1 chân) để khởi động lại, data_in (48 chân) là ngõ vào dữ liệu, data_in_add (5 chân) là địa chỉ ghi dữ liệu, và data_in_done (1 chân) báo hiệu việc truyền dữ liệu đã hoàn tất với tín hiệu tích cực cao Ngoài ra, data_out (48 chân) cung cấp ngõ ra dữ liệu cho chế độ xuất dữ liệu, và mode (2 chân) xác định chế độ sử dụng.

Trong quá trình xử lý, việc xuất dữ liệu ra một chân báo hiệu cho biết quá trình đang được thực hiện tích cực Khi hoàn thành, một chân khác sẽ báo hiệu rằng quá trình xử lý đã kết thúc, đồng thời cũng cho thấy mức độ hoạt động tích cực cao.

Cấu trúc chung của bộ gia tốc NTT/INTT cho Kyber được thể hiện trong Hình 16, với kiến trúc tổng thể bao gồm hai loại bộ nhớ Một RAM được sử dụng để lưu trữ các phần tử hệ số của phương trình gốc cần thực hiện NTT/INTT, trong khi ba ROM được dùng để lưu trữ dữ liệu cần thiết RAM sử dụng Intel Cyclone V M10K ở chế độ simple dual-port, cho phép truy cập đọc ghi đồng thời vào hai địa chỉ bộ nhớ khác nhau Bộ gia tốc được thiết kế với 4 BU sắp xếp trong cấu trúc.

NTT/INTT Accelerator clk rst data_in data_in_add data_in_done mode run data_out done

Cấu hình 25 hình 2 x 2 có khả năng tính toán vượt trội với ���(�) chẵn Đối với ���(�) lẻ, hai BU ở tầng đầu sẽ được bypass, và giá trị hệ số sẽ được truyền thẳng đến hai BU tiếp theo (BU 3 và BU 4).

Dữ liệu từ RAM được truyền qua bus dữ liệu 48-bit, bao gồm 4 phần tử hệ số cho hai bộ BU song song Dữ liệu từ bus này được phân chia thành các phần, với 12 bit đầu tiên là �)) và 12 bit tiếp theo là �)∃.

�)) là 12 bit kế tiếp và �)∃, là 12 bit cuối cùng

Dữ liệu tính toán từ hai BU được chuyển đổi từ 12-bit sang 48-bit bằng một thanh ghi dịch nối tiếp (SIPO) Sau 4 chu kỳ đầu tiên, kết quả tạo thành chuỗi 48-bit sẽ được ghi vào RAM từ thanh ghi đầu tiên Mỗi chu kỳ ghi mất 4 xung đồng hồ, sau đó 4 kết quả mới sẽ được chuẩn bị cho việc ghi tiếp theo Các thanh ghi SIPO ở các vị trí khác nhau sẽ bị trễ 1, 2, 3 xung đồng hồ tương ứng Hình 17 minh họa quá trình dữ liệu dịch vào SIPO Writeback.

Kết quả tổng hợp và mô phỏng

Kết quả mô phỏng mạch và kiểm tra với Testbench được thực hiện trên phần mềm ModelSim cho từng thiết kế nhỏ đến thiết kế tổng Việc tổng hợp mạch sử dụng phần mềm Quartus Prime Standard Edition 21.1, hỗ trợ cho Cyclone V Nghiên cứu mô phỏng và tổng hợp áp dụng chung cấu trúc cho n = 128 và n = 256, cho phép kiểm tra kết quả tính toán với số lớp NTT/INTT lẻ và so sánh với các nghiên cứu tương tự.

4.2.1! Kết quả mô phỏng ModelSim

Nghiên cứu thiết kế Testbench cho các khối nhỏ để kiểm thử kết quả Hình 21 trình bày mô phỏng kết quả của Exact-KRED

Hình 22 Mô phỏng trên dạng sóng kết quả của thiết kế Exact-KRED

Hình 23 trình bày mô phỏng kết quả trên dạng sóng kết quả của thiết kế BU với các chế độ CT, GS và bypass

Hình 23 Mô phỏng trên dạng sóng kết quả của thiết kế BU

Khối thiết kế tổng phần cứng xử lý NTT và INTT cho mã hóa lượng tử CRYSTALS-Kyber thực hiện đầy đủ chức năng nạp dữ liệu, xuất dữ liệu, NTT và INTT Hình 24 minh họa mô phỏng dạng sóng và kết quả qua bốn chu trình của khối thiết kế tổng.

Hình 24 Mô phỏng dạng sóng kết quả của phần cứng xử lý NTT và INTT

4.2.2! Kết quả tổng hợp Quartus

Kết quả tổng hợp Quartus được dùng để kiểm tra tốc độ và tài nguyên tiêu thụ của thiết kế để so sánh và kiểm tra

Hình 25 hiển thị kết quả tổng hợp tài nguyên của thiết kế phần cứng xử lý NTT và INTT cho mã hóa lượng tử CRYSTALS-Kyber Thiết kế này tiêu thụ 1322 ALMs, 2929 thanh ghi, 4 khối DSP và 2268 block memory bit từ 1 khối BRAM M10K.

Hình 26 Kết quả tốc độ mạch trường hợp Slow 1100 mV 85C Hình 26 thể hiện kết quả tốc độ mạch ở trường hợp góc mô phỏng môi trường khó nhất đạt 194.48 ���

Hình 27 trình bày kết quả tốc độ mạch trong trường hợp góc mô phỏng môi trường tối ưu, đạt 368.05 mV, vượt qua giới hạn 275 mV.

Hình 28 Kết quả tốc độ mạch trung bình

Hình 28 thể hiện kết luận về tốc độ mạch trung bình đa môi trường ở mức

Đánh giá, bàn luận và so sánh kết quả

Bảng 6 Thiết kế đề xuất so với các nghiên cứu NTT tương tự trước đây (n = 256)

LUTs FFs DSPs BRAM [MHz]

1Chuyển đổi từ chia hai kết quả cycles với n = 512

4Kết quả cùng với số chu kỳ cần thiết để tiền và hậu xử lý

5Kết quả trên ALMs từ báo cáo tổng hợp của Quartus

Bảng 6 trình bày sự so sánh giữa thiết kế đề xuất trong nghiên cứu này và các nghiên cứu NTT tương tự, với lưu ý về mức độ tài nguyên tiêu thụ Các nghiên cứu thực hiện trên FPGA Intel sử dụng Quartus chỉ cung cấp kết quả tổng hợp ALM và ALUTs Nghiên cứu [30] chỉ ra rằng FPGA sử dụng công nghệ ALM cho số lượng ALUTs lớn hơn nhiều so với LUTs từ công nghệ FPGA Xilinx, do 2 ALUT trong 1 ALM không thể sử dụng đồng thời Hơn nữa, ALM còn bao gồm nhiều thanh ghi và các thành phần khác, khiến việc so sánh tài nguyên tổng hợp từ Quartus với FPGA Xilinx trở nên khó khăn Trong bảng 6, kết quả LUTs được sử dụng từ số ALM trong báo cáo tổng hợp Tỉ lệ NTT Speed Ratio so sánh thời gian tính toán trên ns với các nghiên cứu khác, trong khi tỉ lệ Area x Speed ratio so sánh thời gian tính toán với tài nguyên LUT tiêu thụ, hay còn gọi là tỉ lệ tài nguyên tiêu thụ trên tốc độ.

Nghiên cứu [31] sử dụng cấu hình 3 khối RAM và hệ thống nhân Karatsuba cùng với phiên bản cải tiến của rút gọn modulo Barret Reduction, cho thấy số lượng NTT Cycles cần thiết để tính toán phù hợp với cấu hình 2 BU Tuy nhiên, tốc độ của nghiên cứu này thấp hơn và tốn nhiều tài nguyên hơn do tích hợp nhiều tính năng So với nghiên cứu [31], thiết kế của nghiên cứu này nhanh hơn gấp 2.4 lần và có tỷ lệ tài nguyên tiêu thụ trên tốc độ tốt hơn, đạt mức 3.2 lần.

Nghiên cứu [32] đã áp dụng giải thuật mã hóa NewHope cũ, đóng vai trò tiên phong trong việc cải tiến NTT/INTT bằng cách loại bỏ các bước xử lý hậu kỳ của INTT Kết quả từ nghiên cứu này cho thấy tốc độ xử lý NTT/INTT với cấu hình 2 BU đạt cao hơn so với nghiên cứu [32], đồng thời tối ưu hóa tỷ lệ tài nguyên tiêu thụ trên tốc độ ở mức 1.1.

Nghiên cứu [33] đã áp dụng cấu trúc thêm cho RISC và xây dựng trên ASIC, tuy nhiên, tốc độ chưa cao do không tối ưu hóa mạnh cho ALU, dẫn đến đường tới hạn của thiết kế không đạt tốc độ cao Trong luận văn này, các thành phần module đã được pipeline và tối ưu hóa về tốc độ, giảm thiểu số lượng mức logic Nếu [33] hoạt động ở cùng mức tốc độ với thiết kế này, tỉ lệ tài nguyên tiêu thụ sẽ cao hơn gấp 13.4 lần.

Nghiên cứu [15] cho thấy K2-RED với cấu hình 2x2 BU mang lại tốc độ và hiệu quả tài nguyên vượt trội so với các nghiên cứu trước Số lượng thanh ghi sử dụng cũng được tối ưu hóa đáng kể Mặc dù K2-RED có một số trường hợp bị tràn, nhưng vấn đề này có thể được giải quyết bằng cách áp dụng Exact-KRED.

Nghiên cứu này đạt kết quả khá khi so sánh với các nghiên cứu tương tự gần đây, sử dụng phương pháp rút gọn modulo và giải thuật NTT/INTT tối ưu Tuy nhiên, mức tiêu thụ thanh ghi cao do tính toán trước vị trí của các hệ số Twiddle Factor có thể được cải thiện bằng cách điều chỉnh quy trình áp dụng vòng lặp máy lên phần cứng, nhằm tối ưu hóa việc sử dụng thanh ghi.

Nghiên cứu [15] đề xuất ứng dụng tính chất đảo của Twiddle Factor để tiết kiệm bộ nhớ thanh ghi cho dữ liệu Twiddle Factor INTT Điều này cho phép sử dụng chung bộ nhớ Twiddle Factor với NTT thông qua việc truy xuất theo thứ tự nghịch đảo bit và nghịch đảo dấu của BU.

Các hướng áp dụng trên FPGA Xilinx có thể được nghiên cứu thêm trong các đề tài tiếp theo, giúp dễ dàng so sánh với các nghiên cứu khác Một số hướng tối ưu bổ sung cũng được trình bày trong phần kết luận.