Nghiên cứu đánh giá hiệu năng các lược đồ chữ ký số RSA và ECDSA

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