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

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].
Nội dung trích xuất từ tài liệu:
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ệ 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. 164 Đ.Q. Tiến, N.T. Trung, L.Đ. Hùng, “Nghiên cứu đánh giá… chữ ký số RSA và ECDSA.” Thông tin khoa học công nghệ 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  1)(q  1) . 3. Chọn e ngẫu nhiên sao cho gcd(e, (n ) ) = 1 và tính d  e 1 mod (n ) . 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 ...