Một phương pháp hiệu quả thực hiện phép nhân điểm trên đường cong elliptic sử dụng thuật toán NAF

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Viện Điện tử, 10 - 2015 217 MỘT PHƯƠNG PHÁP HIỆU QUẢ THỰC HIỆN PHÉP NHÂN ĐIỂM TRÊN ĐƯỜNG CONG ELLIPTIC SỬ DỤNG THUẬT TOÁN NAF Hoàng Văn Quân1*, Nguyễn Biên Cương 2, Lều Đức Tân2 Tóm tắt: Trong vài năm trở lại đây, mật mã đường cong Elliptic đã được sử dụng khá rộng rãi trong nhiều lĩnh vực. Một trong số những phép tính phức tạp trong thực hiện mật mã đường cong elliptic là phép tính nhân điểm. Trong nội dung bài báo này, chúng tôi đề xuất một phương pháp thực hiện phép nhân điểm trên đường cong Elliptic trên trường hữu hạn theo thuật toán NAF (Non Adjacent Form) để khai triển một số nguyên. Thuật toán được cài đặt trực tiếp trên phần cứng FPGA mà không cần tính toán trước như thuật toán nhân điểm sử dụng NAF thông thường. Từ khóa: Thuật toán NAF, Thuật toán nhân điểm, Mật mã, Cứng hóa ECC trên FPGA. 1. MỞ ĐẦU Phép tính cơ bản và quan trọng nhất trong thuật toán mật mã elliptic là phép nhân vô hướng một điểm trên đường cong elliptic với một số nguyên dương (k.P với k là số nguyên dương, P là một điểm trên đường cong Elliptic). Trong những năm gần đây, đã có nhiều thuật toán lý thuyết được công bố để thực hiện tăng tốc cho phép tính này. Trong số những thuật toán trên thì thuật toán nhân điểm dựa trên khai triển một số nguyên theo thuật toán NAF là một trong những phương pháp tính toán hiệu quả cho cài đặt trên phần cứng FPGA [1,2,4]. Thuật toán đơn giản nhất sử dụng cho tính toán phép nhân điểm là thuật toán nhị phân. Tuy nhiên, thuật toán này hoạt động khá chậm vì cần nhiều số lượng phép tính cộng điểm và nhân đôi elliptic [1,3]. Thuật toán nhân điểm dựa trên khai triển một số nguyên theo NAF đã có những cải tiến đáng kể khi giảm được số lượng phép cộng điểm từ w-1 xuống 2*(w-1)/3 (với w là số bit 1 trong biểu diễn nhị phân của k). Thuật toán nhân điểm theo NAF dựa trên ý tưởng phép cộng điểm và phép trừ điểm có hiệu quả tính toán tương đương nhau, nên sử dụng khai triển theo NAF(k) thay vì sử dụng biểu diễn nhị phân của k. Bài báo này trình bày phương pháp triển khai một số nguyên theo NAF tính toán trực tiếp trong thực hiện phép nhân điểm, với phương pháp này cho ta hiệu quả về thời gian tính toán và tài nguyên sử dụng khi thực hiện phép nhân điểm trên phần cứng. 2. MỘT SỐ THUẬT TOÁN TÍNH TOÁN PHÉP NHÂN ĐIỂM ELLIPTIC Phép nhân vô hướng giữa một điểm trên đường cong E với một số nguyên dương k, được xác định như sau: Q=k.P, P là một điểm trên đường cong E và 1 ≤ k < ord(E) (2.1) Công nghệ thông tin & Khoa học máy tính H.V.Quân, N. B.Cương, L.Đ. Tân, “Một phương pháp hiệu quả thuật toán NAF.” 218 Thuật toán đơn giản nhất dùng để tính phép nhân vô hướng là thuật toán nhị phân hay còn gọi là thuật toán nhân đôi và cộng. 2.1. Thuật toán 1: Nhân điểm theo phương pháp nhị phân [1] Đầu vào: Điểm P, số nguyên k có kích thước l bit 1 ; 0 2     l j j j k k  0,1jk  . Đầu ra: Q = k.P Bước 1: Q ← O Bước 2: vòng lặp 1j l  đến 0 Bước 2.1: 2.Q Q Bước 2.2: nếu 1 j k thì  Q Q P Bước 3: Kết thúc vòng lặp Bước 4: Trả về giá trị Q. Thuật toán nhân điểm theo phương pháp nhị phân yêu cầu l-1 phép nhân đôi và w-1 phép cộng điểm; trong đó l: chiều dài chuỗi bit trong biểu diễn nhị phân của số nguyên k, w-1 là số các bit ‘1’ có trong chuỗi bit. 2.2. Thuật toán 2: Nhân điểm theo phương pháp biểu diễn m-ary [1] Thuật toán này sử dụng biểu diễn m-ary của số nguyên k, trong đó 2 rm  , với 1r  . Thuật toán nhị phân là trường hợp đặc biệt của m-ary khi r = 1. Đầu vào: điểm P, số nguyên k có kích thước l bit và có biểu diễn m-ary là   1 0 2 ; 0,1,..., 1 ; / d j j jj k k k m d l r       . Đầu ra: .Q k P . Tính toán trước: Bước 1: 1 P P Bước 2: vòng lặp 2i  đến 1m  thực hiện : 1   i i P P P . Kết thúc vòng lặp. Bước 3: Q O Bước 4: vòng lặp chính: 1j d  đến 0 thực hiện : Bước 2.1: .Q m Q Bước 2.2: jk Q Q P  Bước 5: Kết thúc vòng lặp chính. Bước 6: Trả về giá trị Q. Thuật toán nhân điểm theo m-ary yêu cầu  1d r phép nhân đôi và 2m  phép cộng điểm với  l d r . Như vậy, số phép nhân đôi của thuật toán m-ary lớn nhất là 1 1r l   của thuật toán nhị phân. 2.3. Thuật toán nhân điểm dựa trên khai triển một số nguyên theo NAF [1] Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Viện Điện tử, 10 - 2015 219 Phép cộng điểm và trừ điểm có hiệu quả tương đương nhau trên trường hữu hạn. Trên ( ), 3GF p p  nếu  ( , )P x y p    thì  ( , ) pP x y     , với GF(2n) thì  2( , ) nP x x y     do vậy tính toán phép cộng điểm và trừ điểm có hiệu quả tương đương nhau trên ( )GF p , (2 )nGF . Với thuật toán NAF ta có thể biểu diễn một số nguyên dương k theo dạng các số có dấu  1 0 2 0, 1 l i i ii k k k        ; trong đó hai số ki liên tiếp khác không. Thuật toán 3: Khai triển một số nguyên dương theo NAF Đầu vào: số nguyên dương k; Đầu ra: NAF(k); Thực hiện: Bước 1: Đặt c:=k ; Bước 2: Gán tập S := ; Bước 3: Trong khi c > 0 thực hiện vòng lặp: 3.1. Nếu c lẻ thì: đặt u := 2 - (c mod 4); đặt c := c – u; 3.2. Còn không thì: u:= 0; 3.3. Kết thúc Nếu; Bước 4: Thêm u vào tập S; Bước 5: Đặt c := c/2; Bước 6: Kết thúc vòng lặp; Trả về tập S; Tính chất của khai triển một số nguyên theo NAF. a. Với một số nguyên dương k, khai triển NAF(k) là duy nhất. b. NAF(k) có số chữ số khác không ít nhất trong tất cả các biểu diễn có dấu của k. c. Chiều dài của dãy NAF(k) lớn hơn 1 so với chiều dài dãy biểu diễn nhị phân của k. d. Nếu l là chiều dài dãy NAF(k) thì 12 2 3 3 l l k    e. Mật độ số chữ số khác không trong biểu diễn NAF của một số có chiều dài l bit xấp xỉ l/3. Thuật toán 4 : Nhân điểm Elliptic dựa trên triển khai theo NAF [1,4] Đầu vào: điểm P, số nguyên k có kích thước l bit ,   1 0 2 0 ,1 , 0         l j j j j k k k k ; Đầu ra: Q = k.P Thực hiện: Bước 1: Sử dụng thuật toán 3 để tính khai triển một số nguyên dương; Bước 2: Q ← O Công nghệ thông tin & Khoa học máy tính H.V.Quân, N. B.Cương, L.Đ. Tân, “Một phương pháp hiệu quả thuật toán NAF.” 220 Bước 3: vòng lặp i = l-1 tới 0 thực hiện 3.1. Q ← 2Q 3.2. Nếu ki = 1 thì Q ← Q + P 3.3. Nếu ki = -1 thì Q ← Q - P Bước 4: Kết thúc vòng lặp; Trả về kết quả Q; Với tính chất thứ (e) của khai triển một số nguyên theo NAF ta có thể thấy với một số k có biểu diễn nhị phân với chiều dài l, giả sử số bit 1 tương đương số bit 0 là l/2 thì biểu diễn theo NAF(k) có số bit khác không là l/3, như vậy khi sử dụng nhân điểm dựa trên NAF số phép tính cộng điểm sẽ là l/3, trong khi sử dụng thuật toán nhân điểm theo phương pháp nhị phân số phép tính cộng điểm cần sử dụng là l/2. Điều này chứng tỏ thuật toán NAF hiệu quả hơn thuật toán nhị phân về tốc độ tính toán. Ngoài ra, còn một số thuật toán khác sử dụng cho phép nhân điểm vô hướng: thuật toán Sliding Window, thuật toán Montgomery 3. ĐỀ XUẤT THUẬT TOÁN NHÂN ĐIỂM ELLIPTIC DỰA TRÊN TRIỂN KHAI MỘT SỐ NGUYÊN THEO NAF TÍNH TOÁN TRỰC TIẾP Trong thuật toán 4, Bước 1 cần tính khai triển một số nguyên dương theo thuật toán 3. Các giá trị của NAF(k) cần được lưu lại sau đó thực hiện thuật toán nhân điểm theo thuật toán 4. Quá trình này khiến thuật toán không được tính toán trực tiếp và cần không gian bộ nhớ để lưu các giá trị sinh ra từ NAF(k), các giá trị này không có ý nghĩa trong tính toán thuật toán nhân điểm vì kết quả cuối cùng cần tính là kết quả Q= k.P. Trong nội dung bài báo này chúng tôi đề xuất thuật toán nhân điểm dựa trên NAF (Thuật toán 5) và có thể tính toán trực tiếp mà không cần lưu trước các tham số biểu diễn NAF của k (bỏ qua Bước 1 trong Thuật toán 4) Thuật toán 5: Nhân điểm Elliptic dựa trên NAF thực hiện tính toán trực tiếp Đầu vào: điểm P, số nguyên k có kích thước l bit ,   1 0 2 0,1 , 0 l j j j j k k k k        ; Đầu ra: Q = k.P; Thực hiện: Bước 1: Đặt c:= k; Bước 2: Đặt Q = O; Bước 3: Trong khi c > 0 thực hiện vòng lặp: 3.1 Nếu c0=1 thì: 3.1 .1 Nếu c1 = 0 thì : c= c - 1; Q := Q + P; 3 .1.2 Còn không (c1 = 1 )thì: Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Viện Điện tử, 10 - 2015 221 c := c + 1; Q := Q - P; 3.1.3 Kết thúc Nếu; 3.2 Kết thúc Nếu; Bước 4: Q:= 2Q Bước 5: c := c/2; Bước 6: Kết thúc vòng lặp; Trả về giá trị: Q; Khẳng định 1. Nếu bỏ qua các bước tính liên quan đến điểm Q, thì Thuật toán 5 chính là triển khai NAF của số nguyên k. Chứng minh: Dễ thấy Bước 1 của Thuật toán 5 chính là Bước 1 của Thuật toán 3. Bước 2 của Thuật toán 3 chỉ để lưu biểu diễn theo NAF của k. Ta cần chỉ rõ Bước 3 của Thuật toán 5 chính là Bước 3 của Thuật toán 3. Thật vậy, dựa trên tính chất của phép modulo có dạng sau: b = a mod 2n , với:   1 0 2 , 0 , 1 l j j j j a a a      , khi đó nếu l>n thì   1 0 2 , 0,1 n j j j j b a a      (3.1) Áp dụng tính chất (c) của biểu diễn theo NAF, ta có: c mod 4 = c1c0, trong đó c0 là bit có trọng số bé nhất của biểu diễn nhị phân của c. Thay vào bước 3.1 của thuật toán 3 ta có: c lẻ => c0 = 1, do vậy u := 2 - (c mod 4) = 2 - {01,11} ={1,- 1} => c ={c-1, c+1} tương ứng với bước 3.1.1 và 3.1.2 của Thuật toán 5. Bỏ qua Bước 4 của Thuật toán 3 (lưu giá trị vào tập S), bước 5 của hai thuật toán là như nhau. Như vậy, nếu bỏ qua các phép toán liên quan đến điểm Q, Thuật toán 5 chính là triển khai theo NAF của số nguyên k theo Thuật toán 3. Khẳng định 2. Kết quả thực hiện Thuật toán 5 chính là thực hiện phép nhân điểm theo Thuật toán 4 mà không cần tập S để lưu biểu diễn theo NAF của số nguyên k. Với thuật toán 5 mà bài báo đề xuất, quá trình tính toán phép nhân điểm không cần tính toán trước NAF(k). Việc tính toán NAF(k) được thực hiện song song với quá trình tính toán phép nhân điểm. Quá trình khai triển NAF được thực hiện thông qua việc kiểm tra các bit số 0 (bit có trọng số nhỏ nhất LSB) và bit số 1 trong biểu diễn nhị phân của k. Với thuật toán 5, việc thiết kế thuật toán trên phần cứng hoàn toàn có thể thực hiện trực tiếp, không cần tính toán trước biểu diễn theo NAF của số nguyên k, đồng thời không cần sử dụng thêm bộ nhớ để lưu biểu diễn NAF(k) (tập S trong Thuật toán 3). Điều này vừa hạn chế được tài nguyên thiết kế khối nhân điểm trên phần cứng, vừa tăng tốc độ quá trình tính toán phép nhân điểm. 4. CỨNG HÓA PHÉP NHÂN ĐIỂM THEO THUẬT TOÁN ĐỀ XUẤT 4.1. Lựa chọn đường cong Elliptic Công nghệ thông tin & Khoa học máy tính H.V.Quân, N. B.Cương, L.Đ. Tân, “Một phương pháp hiệu quả thuật toán NAF.” 222 Trong rất nhiều các đường cong Elliptic, không phải đường cong nào cũng có tính chất mật mã tốt. Trong bài báo này, đường cong elliptic trên trường GF(2n) theo khuyến nghị của NIST [6] được lựa chọn với các tham số như sau: - Tham số cho đường cong trên GF(2n). - Đa thức bất khả quy: 283 12 7 5( ) 1F x x x x x     - Điểm cơ sở ( , )G GG x y trong đó: x =503213f78ca44883f1a3b8162f188e553cd265f23c1567a16876913b0c2ac2458492836G 1ccda380f1c9e318d90f95d07e5426fe87e45c0e8184698e45962364e34116177dd2259Gy  - Bậc của điểm G (là số nguyên tố): = 3885337784451458141838923813647037813284811733793061324295874997529815829704422603873n Đồng thừa số (cofactor): h = 4. k= 3F00000FFFFFFFF800003800F8000E0000E000000FFFFFFE00000FFFFFFC0007E000000 Công cụ được lựa chọn cho cứng hóa là FPGA trên kít chip Znq7Z045FFG900- 3 của Xilinx. 4.2. Mô hình thiết kế và kết quả thực hiện Mô hình thực hiện cứng hóa phép nhân điểm trên trường hữu hạn GF(2n) dựa trên khai triển một số nguyên theo thuật toán NAF tính toán trực tiếp được thể hiện như trên hình 1, ta có thể thấy module cứng hóa phép nhân điểm cần sử dụng các module cộng điểm elliptic, module nhân đôi và module thực hiện khai triển theo NAF(k). Kết quả thực hiện giao diện mức trên cùng bằng công nghệ FPGA được thể hiện trong hình 2. Bảng 1. So sánh tham số cứng hóa phép nhân điểm trên FPGA. Tham số Thuật toán nhân điểm sử dụng NAF (TT4) Thuật toán đề xuất sử dụng NAF tính toán trực tiếp (TT5) Number of Slice Registers: 6920 6629 Number of Slice LUTs 7746 7093 Number of LUT Flip Flop pairs used 9457 8814 Thời gian tính toán 2583s 2575s Frequency 100 MHz 100 MHz 5. KẾT LUẬN Đóng góp chính của bài báo là việc đề xuất một thuật toán nhân điểm hiệu quả về mặt thời gian tính toán và tài nguyên sử dụng so với thuật toán nhân điểm theo NAF thông thường. Cài đặt thực hành cũng cho thấy những kết quả phù hợp với lý thuyết, tốc độ tính toán phép nhân điểm theo thuật toán đề xuất (thuật toán 5) nhanh hơn và sử dụng ít tài nguyên hơn so với thuật toán nhân điểm sử dụng NAF Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Viện Điện tử, 10 - 2015 223 truyền thống (thuật toán 4) trên trường GF(2n). Đây là yếu tố rất quan trọng để thực hiện cứng hóa mật mã đường cong elliptic như giao thức trao đổi khóa ECDH, ECHQMV, thuật toán chữ ký số ECDSA, GOST R34.10-2012 [5] nhằm tiết kiệm thời gian tính toán và tài nguyên của thiết bị xử lý trung tâm tại các nút mạng khi phải thực hiện đồng thời nhiều kết nối tại cùng một thời điểm (nghĩa là phải thực hiện nhiều phép nhân điểm đồng thời) trong thực tế khi các mạng truyền số liệu làm việc ở tốc độ cao, băng thông lớn, đa dịch vụ và yêu cầu thời gian thực. TÀI LIỆU THAM KHẢO [1]. Darrel Hankerson, Alfred Menezes, Scott Vanstone, “Guide to Elliptic Curve Cryptography”, Springer – 2004. [2]. Francisco Rodri’guez – Henri’quez, N.A.Saqib, A.Di’az-Pe`rez. “Cryptopraphic Algorithms on Reconfigurable Hardware”. Springer, 2007. [3]. Jerome, A.Solinas,“Efficient Arithmetic on Koblitz Curves”. Centre for Applied Cryptographic Research, University of Waterloo, 2000. [4]. Jean-Piere Deschamps, Ge’ry Jean Antoine Bioul, Gustavo D.Stuter, “Hardware Implementation of Finite-Field Arthmetic”, Mc Graw Hill Press, 2009. [5]. Н а ц и о н а л ь н ы й с т а н д а р т р о с с и й с к о й ф е д е р а ц и и гост р 34.10 ─ 2012 [6]. National Institute for Standards and Technology (NIST), “Recommended Elliptic Curve for Federal Government Use”, July 1999. Hình 2. Kết quả thực hiện phép nhân điểm elliptic GF(2n) trên FPGA Hình 1. Mô hình thực hiện cứng hóa phép nhân điểm elliptic trên GF(2n). Công nghệ thông tin & Khoa học máy tính H.V.Quân, N. B.Cương, L.Đ. Tân, “Một phương pháp hiệu quả thuật toán NAF.” 224 ABSTRACT AN EFFECTIVE METHOD IMPLEMENTATION POINT MULTIPLICATON ON ELLIPTIC CURVE ALGORITHM USING NAF In recent years, Elliptic curve cryptosystems have used popularly in many fields. One of complicated operators in elliptic curve cryptosystem is scalar point-multiplication. In this paper we outline a solution to implement scalar point-multiplication for Elliptic curve on finite field based on NAF (Non Adjacent Form) algorithm. Our design can be implemented directly in FPGA and without any pre-computations as in traditional NAF. Keywords: Algorithms NAF, Point multiplication, Cryptography, Hardened Elliptic Curve Cryptography in FPGA. Nhận bài ngày 21 tháng 07 năm 2015 Hoàn thiện ngày 10 tháng 08 năm 2015 Chấp nhận đăng ngày 07 tháng 09 năm 2015 Địa chỉ: 1 Cục Cơ yếu – BTTM; *Email: hoangvanquan@gmail.com ; 2 Viện KHCN Mật mã/Ban Cơ yếu Chính phủ