Nghiên cứu đánh giá hiệu năng các lược đồ chữ ký số RSSA và Ecdsa - ĐInh Quốc Tiến

Thông tin khoa học công nghệ Đ.Q. Tiến, N.T. Trung, L.Đ. Hùng, “Nghiên cứu đánh giá chữ ký số RSA và ECDSA.” 164 NGHIÊN CỨU ĐÁNH GIÁ HIỆU NĂNG CÁC LƯỢC ĐỒ CHỮ KÝ SỐ RSA VÀ ECDSA Đinh Quốc Tiến*, Nguyễn Thành Trung, Lê Đình Hùng Tóm tắt: Trong bài báo này chúng tôi thực hiện đánh giá hiệu năng của 2 lược đồ chữ ký số RSA và ECDSA ở cùng mức an toàn bit (RSA 2048 bit so với ECDSA 256 bit). Kết quả cho thấy, lược đồ ECDSA có tốc độ thực hiện nhanh hơn nhiều so với lược đồ RSA. Kết quả này cũng giúp chúng ta phản biện lại các kết quả của nhóm N. Jansma [1] và nhóm A. Kaur [2]. Từ khóa: Lược đồ chữ ký số, RSA, ECDSA. 1. MỞ ĐẦU Chữ ký số có tầm quan trọng trong truyền thông số, đặc biệt nó được sử dụng để kiểm tra định danh của người ký lên thông báo và đồng thời đảm bảo rằng thông báo đó không bị sửa sau khi ký. Để sinh chữ ký số và kiểm tra chữ ký số người ta sử dụng các hệ mật khóa công khai như RSA, ECDSA, Như chúng ta đã biết, cộng đồng mật mã đã tin dùng bảng an toàn bit tương đương của ECDSA và RSA theo [4] như trong Bảng 1 sau: Bảng 1. Độ an toàn bit của ECDSA và RSA. Đối xứng ECC RSA 80 163 1024 112 233 2240 128 283 3072 192 409 7680 256 571 15360 Trong các bài báo [1] và [2] đã đưa ra kết quả so sánh rằng tốc độ thực hiện của lược đồ RSA nhanh hơn rất nhiều so với lược đồ ECDSA với cùng độ an toàn bit. Nhưng chúng tôi nhận thấy sự so sánh trong 2 bài báo đó có lẽ là không hợp lý với lý do sau:  Trong [1] các tác giả thực hiện so sánh tốc độ của 2 lược đồ chữ ký sử dụng 2 bộ thư viện khác nhau, cụ thể: thực hiện lược đồ ECDSA theo thư viện phần mềm borzoi 1.02 và lược đồ RSA theo bộ mã nguồn Crypto++ 5.1. Kết quả so sánh tốc độ được đưa ra trong Bảng 5-3 và Bảng 5-4 của [1] cho thấy với cùng độ an toàn bit (RSA 2240 đối với ECC 233) lược đồ RSA thực hiện nhanh hơn lược đồ ECC khoảng hơn 2 lần (0.15 giây đối với 0.34 giây).  Trong khi đó trong Bảng 1 của [2] đã tham chiếu sai về độ an toàn bit, ví dụ như sử dụng ECC 160 bit so với RSA 2048 bit, hay ECC 210 bit so với RSA 3072 bit, Điều này cũng ảnh hưởng nhiều đến kết quả so sánh tốc độ trong Bảng 2 của [2] rằng lược đồ RSA thực hiện nhanh hơn rất nhiều so với lược đồ ECC (khoảng 20 lần). Trong bài báo này, chúng tôi khắc phục các điểm không hợp lý trên bằng việc thực hiện cài đặt và so sánh thời gian chạy của 2 lược đồ chữ ký RSA và ECDSA trên cùng một bộ thư viện tính toán miracle-5.3 với tham chiếu an toàn tương đương ở Bảng 1. Hơn nữa, trong cài đặt cho lược đồ chữ ký ECDSA, chúng tôi áp dụng phương pháp biểu diễn wmbNAF [6] để cải tiến tốc độ của phép nhân điểm trên đường cong elliptic. Kết quả của công việc này nhằm khẳng định lại việc so sánh tốc độ thực hiện của 2 lược đồ ECDSA và RSA với cùng mức an toàn bit. Trước tiên, dưới đây chúng tôi trình bày sơ lược về các lược đồ chữ ký số RSA và ECDSA mà sẽ được sử dụng trong cài đặt. Thông tin khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 40, 12 - 2015 165 2. CÁC LƯỢC ĐỒ CHỮ KÝ SỐ 2.1. Lược đồ chữ ký số RSA Hệ mật khóa công khai RSA được sử dụng khá phổ biến (có từ năm 1977) trong nhiều lược đồ mật mã. Trước khi thực hiện thuật toán mật mã RSA thì phải sinh cặp khóa bí mật/công khai. 2.1.1. Thủ tục sinh cặp khóa RSA Cặp khóa công khai và bí mật có thể được sinh sử dụng thuật toán trong [5] như sau: 1. Tìm 2 số nguyên tố p và q có độ dài k/2 bit. 2. Tính n pq và ( ) ( )( )n p q1 1    . 3. Chọn e ngẫu nhiên sao cho gcd(e, ( )n ) = 1 và tính mod ( )d e n1  . 4. Cặp ( , )e n công bố công khai, được gọi là khóa công khai; cặp ( , )d n giữ bí mật bởi người sở hữu, được gọi là khóa bí mật. Việc tìm 2 số nguyên tố p và q là phép toán có chi phí lớn nhất trong thủ tục sinh khóa, theo đánh giá thô thì nó tương đương với tổng thời gian thực hiện thủ tục sinh khóa RSA. 2.1.2. Thủ tục sinh chữ ký RSA Chữ ký của thông điệp m là một phép lũy thừa modulo của giá trị băm thông báo với số mũ là khóa bí mật. Chú ý rằng H là một hàm băm mật mã mà đầu ra của nó có độ dài bit không vượt quá n (nếu điều kiện này không được thỏa mãn thì các đầu ra của H phải bị chặt ngắn). Khi đó chữ ký s nhận được như sau: 1. h = H(m) 2. s = hd (mod n) Thông thường các hàm băm được sử dụng như trong FIPS 180-2 [3]. 2.1.3. Thủ tục kiểm tra chữ ký RSA Để kiểm tra chữ ký s của thông điệp m, trước tiên chữ ký phải được giải mã sử dụng khóa công khai của người ký (n, e). Từ đó, nhận được giá trị h’, và kiểm tra sự trùng khớp với giá trị băm thông điệp m như sau: 1. h’ = se (mod n) 2. h = H(m) 3. Nếu h’ = h thì “Chấp nhận chữ ký”, ngược lại “Không chấp nhận”. 2.2. Lược đồ chữ ký số ECDSA Lược đồ chữ ký số ECDSA là phiên bản sử dụng đường cong elliptic của thuật toán chữ ký số quen thuộc DSA. Nó là lược đồ chữ ký số dựa trên đường cong elliptic chuẩn phổ biến nhất, đã được công bố trong các chuẩn ANSI X9.62, FIPS 186-2, IEEE 1363- 2000 và ISO/IEC 15946-2. 2.2.1. Thủ tục sinh khóa trên đường cong elliptic Một đường cong elliptic E trên trường nguyên tố p với p nguyên tố, điểm  pP E  có cấp nguyên tố ,n G P là nhóm sinh bởi điểm P cũng có cấp nguyên tố. Một cặp khóa trên đường cong elliptic tương ứng với một tập các tham số miền ( , , , , , , , )D p FR S a b P n h theo chuẩn ISO/IEC 15946-1:2002(E) như sau. Khóa công khai là một điểm được chọn ngẫu nhiên Q trong nhóm P được sinh bởi P. Khóa bí mật tương ứng sẽ là logPd Q . Thuật toán sinh cặp khóa trên đường cong elliptic như sau. Thông tin khoa học công nghệ Đ.Q. Tiến, N.T. Trung, L.Đ. Hùng, “Nghiên cứu đánh giá chữ ký số RSA và ECDSA.” 166 1. Chọn ngẫu nhiên một số nguyên [1, 1].d n  2. Tính .Q dP 3. Trả về ( , )Q d . 2.2.2. Thủ tục sinh chữ ký ECDSA Để ký một thông báo ,m thực thể A với cặp khóa bí mật/công khai  ,x Q thực hiện theo thuật toán dưới đây. 1. Chọn ngẫu nhiên một số nguyên [1, 1].k n  2. Tính  1 1,kP x y , và chuyển 1x thành một số nguyên 1x . 3. Tính 1 mod .r x n Nếu 0r  thì quay trở lại Bước 1. 4. Tính  e H m . 5. Tính  1 mod .s k e dr n  Nếu 0s  thì quay trở lại Bước 1. 6. Chữ ký  , .r s 2.2.3. Thủ tục kiểm chữ ký ECDSA Để kiểm tra tính hợp lệ của chữ ký  ,r s của A trên thông báo ,m thực thể B nhận một bản có xác thực các tham số chung và khóa công khai Q của A. Sau đó B thực hiện theo thuật toán dưới đây. 1. Kiểm tra ,r s là các số nguyên trong khoảng  1, .n Nếu lỗi thì “Chữ ký không hợp lệ”. 2. Tính  .e H m 3. Tính 1 mod .w s n 4. Tính 1 modu ew n và 2 mod .u rw n 5. Tính 1 2 1 1( , )X u P u Q x y   . 6. Nếu X   thì “Chữ ký không hợp lệ”; 7. Chuyển 1x thành một số nguyên 1x ; tính 1 mod .v x n 8. Nếu v r thì “Chữ ký hợp lệ”; ngược lại “Chữ ký không hợp lệ”. Việc kiểm tra chữ ký cho ta khẳng định chính xác về tính hợp lệ của chữ ký bởi vì nếu chữ ký thực sự là do A tạo ra thì khi đó  1 mods k e dr n  . Điều này dẫn đến:    1 1 1 1 2 mod .k s e xr s e s rd we wrd u u d n           Do đó  1 2 1 2X u P u Q u du P kP     , và do vậy .v r 3. ĐÁNH GIÁ HIỆU NĂNG CỦA CÁC LƯỢC ĐỒ CHỮ KÝ SỐ 3.1. Phép nhân vô hướng điểm trên đường cong elliptic Phép nhân vô hướng trên đường cong elliptic là phép toán trọng tâm và tốn thời gian nhất trong nhiều hệ mật khóa công khai dựa vào đường cong elliptic như các hệ mật đường cong elliptic ECC, đường cong Hyperelliptic HECC và các hệ mật dựa vào cặp. Các thuật toán truyền thống để cài đặt phép toán này thường được dựa vào khai triển nhị phân của các số (ví dụ như NAF, wNAF), trong đó việc thực thi thành công của phương Thông tin khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 40, 12 - 2015 167 pháp dựa vào các phép toán điểm cơ bản, tức là nhân đôi và cộng. Trong [6], Longa đã tổng quát hóa ý tưởng của việc kết hợp một vài cơ số để biểu diễn các số và sau đó giải quyết bài toán tìm các biểu diễn nhiều cơ số ngắn hiệu quả theo một biểu diễn tựa NAF nhiều cơ số cửa sổ độ rộng w (gọi là wmbNAF – w window multibase Non-Adjacent Form), nó phép giảm mật độ khác không cần thiết trong biểu diễn nhiều cơ số của các số nguyên theo chi phí bộ nhớ cho một tập mở rộng các chữ số tính trước: 1 1 1 1 1 1 1 1 0, 1, 2,..., \ 1 , 2 ,..., 2 2                                     w w i a a k a a a . Thuật toán 1 dưới đây để tìm biểu diễn wmbNAF của giá trị vô hướng k. Thuật toán 1. Tính wmbNAF của một số nguyên dương. Đầu vào: số nguyên k, tập cơ số  = a1, a2, , aJ, ja   là các số nguyên tố dương với 1 j J  và cửa sổ w  2, với w   . Đầu ra:         2 11 2 1,..., NAF ..., , a aJ wa a k k k 1. i = 1 2. while k > 0 do 2.1 If k mod a1 = 0 or k mod a2 = 0 or or k mod aJ = 0 then ki = 0 2.2 Else 2.2.1 ki = k mods 1 wa 2.2.2 k = k - ki 2.3 2.3.1 If k mod a1 = 0 then 1/k k a ,  1 ai ik k 2.3.2 elseif k mod a2 = 0 then 2/k k a ,  2  a i ik k 2.3.J elseif k mod aJ = 0 then / Jk k a ,   J a i ik k 2.4 i = i + 1 3. Return     2 12 1..., ,a ak k Trong đó hàm ki = k mods 1 wa được tính như sau:  If 1 1mod / 2 w wk a a then  1 1mod w wik k a a  Else 1mod w ik k a Thuật toán 1 định nghĩa cửa sổ độ rộng w chỉ cho cơ số chính a1 để xấp xỉ mọi sự tính toán. Theo cách này, đảm bảo thực hiện w phép toán liên tiếp theo a1 trước khi thực hiện một phép cộng. Mật độ của phương pháp này được rút gọn hơn khi số lượng cơ số tăng lên vì thuật toán tìm kiếm thêm các số chia cho các cơ số còn lại. Với biểu diễn wmbNAF thì phép nhân vô hướng điểm trên đường cong elliptic được thực hiện theo Thuật toán 2 dưới đây. Thuật toán 2. Phép nhân vô hướng điểm trên đường cong elliptic theo biểu diễn wmbNAF. Thông tin khoa học công nghệ Đ.Q. Tiến, N.T. Trung, L.Đ. Hùng, “Nghiên cứu đánh giá chữ ký số RSA và ECDSA.” 168 Đầu vào: cửa sổ độ rộng 2w  , biểu diễn vô hướng       1 2 11 2 1,..., la a alk k k k từ Thuật toán 1 trên, và   pP E . Đầu ra: kP 1. Tính trước Pi = iP với i  (theo Định nghĩa ở trên). 2. Q = 0 3. For i = l – 1 downto 0 do 3.1. Q = (ai)Q 3.2. If   0i a ik then If   0i a ik then Q = Q +  ai ik P Else Q = Q -  ai ik P 4. Return Q Trong thuật toán này  ia ik là chữ số thứ i và chỉ số ai   (tập các cơ số) ký hiệu cơ số tương ứng với chữ số. Như vậy, phép toán Q = (ai)Q trong bước 3.1 là một trong các phép toán nhân điểm (nhân đôi, nhân ba, nhân năm,). Trong bước 3.2 của Thuật toán 2, phép cộng điểm được thực hiện khi gặp phần tử khác 0 trong khai triển nhiều cơ số. 3.2. Đánh giá hiệu năng Chúng tôi đã cài đặt các module chương trình nhân nhanh điểm trên đường cong elliptic sử dụng biểu diễn dạng NAF, wNAF, mbNAF và wmbNAF. Cụ thể với bộ tham số miền đường cong Elliptic trên p với p là số nguyên tố cỡ 256 bit và thực hiện trên máy laptop T61 tốc độ 1.8GHz, thì với 10000 (mười nghìn) phép nhân điểm đối với mỗi phương pháp, chúng tôi thu được bảng dưới đây so sánh tốc độ nhân điểm trên đường cong elliptic giữa các phương pháp NAF, wNAF, mbNAF, wmbNAF và phép nhân điểm trong bộ chương trình miracle phiên bản 5.3 với tham số miền đường cong Elliptic trên p với p là số nguyên tố cỡ 256 bit. Bảng 2. So sánh tốc độ nhân điểm trên đường cong elliptic. Dạng biểu diễn Thời gian (ms) Tốc độ tăng (%) NAF 232613 -4 wNAF 186589 16 mbNAF 214049 4 wmbNAF 184892 17 miracle-5.3 224048 0 Bảng 2 cho thấy rằng đối với biểu diễn dạng wNAF và wmbNAF thì tốc độ nhân điểm mới tăng lên tốt nhất khoảng 17% so với phép nhân điểm trong bộ chương trình miracle phiên bản 5.3, đối với biểu diễn dạng mbNAF thì tốc độ tăng không đáng kể khoảng 4%, còn đối với biểu diễn dạng NAF thì tốc độ bị giảm khoảng 4%. Nguyên nhân của việc cài đặt phép nhân điểm với biểu diễn dạng mbNAF có tốc độ tăng không đáng kể là do trong chương trình chưa sử dụng các phép nhân điểm hiệu quả (nhân ba, nhân năm,) nó được sử dụng trong mỗi vòng lặp ở Bước 3.1 của Thuật toán 2. Đặc biệt, nếu có nhiều hơn một phép toán điểm hiệu quả thì có thể sử dụng wmbNAF độ rộng thay đổi hiệu quả, do nó có tính mềm dẻo trong việc xác định các kích cỡ cửa sổ khác nhau dựa vào chi phí cụ thể giữa các phép toán điểm. Thông tin khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 40, 12 - 2015 169 Chúng tôi thực hiện cài đặt, so sánh tốc độ thực hiện 2 lược đồ chữ ký RSA và ECDSA trên cùng một bộ thư viện tính toán miracle-5.3. Xây dựng các module chương trình thực hiện hệ chữ ký số ECDSA dựa trên đường cong elliptic trên trường p với p là số nguyên tố cỡ 256 bit, thực hiện hệ chữ ký số RSA với số modulus 2048 bit, và sử dụng hàm băm SHA2-256. Các module chạy trên 2 môi trường là PC Pentium (R) Duo-Core CPU E5700 3GHz và thiết bị USB PKI Token có chip vi xử lý ARM nhân Cortex M3, tốc độ 100 Mhz. Kết quả thực nghiệm được thể hiện ở Bảng 3 dưới đây. Bảng 3. Thực nghiệm cài đặt các lược đồ trên PC và thiết bị USB PKI Token. Lược đồ / Môi trường RSA ECDSA Sinh chữ ký Kiểm tra chữ ký Sinh chữ ký Kiểm tra chữ ký PC 62ms 47ms 15ms 16ms USB PKI Token 2,5s 2s 1s 1s Kết quả cho thấy, trên cả 2 môi trường làm việc, lược đồ ECDSA có tốc độ thực hiện nhanh hơn nhiều so với lược đồ RSA ở cùng mức an toàn bit: nhanh hơn khoảng 3.5 lần trên PC và khoảng 2 lần trong USB PKI Token. 4. KẾT LUẬN Trong bài báo này chúng tôi đã thực hiện cài đặt, so sánh tốc độ thực hiện 2 lược đồ chữ ký RSA và ECDSA cùng độ an toàn bit trên cùng một bộ thư viện tính toán miracle- 5.3 và trên cùng môi trường. Kết quả cho thấy, trên cả 2 môi trường làm việc, lược đồ ECDSA có tốc độ thực hiện nhanh hơn nhiều so với lược đồ RSA ở cùng mức an toàn bit: nhanh hơn khoảng 3.5 lần trên PC và khoảng 2 lần trong USB PKI Token. Điều này giúp chúng ta khẳng định lại niềm tin về tốc độ vượt trội của lược đồ chữ ký số ECDSA so với lược đồ chữ ký số RSA. Các kết quả này khẳng định xu hướng sử dụng lược đồ ECDSA thay cho lược đồ RSA trong tương lai, đặc biệt đối với các thiết bị có tài nguyên hạn chế như smartcard, USB Token, TÀI LIỆU THAM KHẢO [1]. N. Jansma, B. Arrendondo, “Performance Comparation of Elliptic Curve and RSA Digital Signatures”, April 28, 2004. [2]. A. Kaur, V. Goyal, “A comparative analysis of ECDSA V/S RSA algorithm”, International Joural of Computer Science and Informatics, ISSN (PRINT): 2231- 5292, Volume-3, Issue-1, 2013. [3]. FIPS 180-2: “The Secure Hash Standard”. Available (28 April 2004) at: [4]. A. Lenstra, and E. Verheul, “Selecting Cryptographic Key Sizes”, Journal of Cryptology 14 (2001) 255-293. [5]. W. Mao. “Modern Cryptography: Theory and Practice”. Copyright 2004. [6]. P. Longa, "Accelerating the Scalar Multiplication on Elliptic Curve Cryptosystems over Prime Fields" Master's Thesis, University of Ottawa, 2007. Thông tin khoa học công nghệ Đ.Q. Tiến, N.T. Trung, L.Đ. Hùng, “Nghiên cứu đánh giá chữ ký số RSA và ECDSA.” 170 ABSTRACT STUDY OF PERFORMACE ANALYSIS ON RSA AND ECDSA DIGITAL SIGNATURE SCHEMES In this paper, we analyze the performance of both RSA and ECDSA digital signature schemes in the same bit security level (RSA 2048 bit vs ECDSA 256 bit). In results, the ECDSA scheme runs much faster than RSA one in the same bit security level. This help us review the results of N. Jansma [1] and A. Kaur [2]. Keywords: Digital Signature Scheme, RSA, ECDSA. Nhận bài ngày 16 tháng 09 năm 2015 Hoàn thiện ngày 18 tháng 11 năm 2015 Chấp nhận đăng ngày 25 tháng 12 năm 2015 Địa chỉ: Viện Khoa học – Công nghệ mật mã, Ban cơ yếu Chính phủ. * Email : tiendq77@gmail.com