Về một thuật toán nhân điểm an toàn của hệ mật Elliptic

Bài báo này sẽ giới thiệu, phân tích các thuật toán nhân điểm đã biết và đề xuất một thuật toán an toàn và hiệu quả, có khả năng chống lại các tấn công phân tích năng lượng. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Về một thuật toán nhân điểm an toàn của hệ mật Elliptic JOURNAL OF SCIENCE OF HNUE FIT., 2013, Vol. 58, pp. 131-139 This paper is available online at http://stdb.hnue.edu.vn VỀ MỘT THUẬT TOÁN NHÂN ĐIỂM AN TOÀN CỦA HỆ MẬT ELLIPTIC Nguyễn Hữu Hùng Ban Cơ yếu Chính phủ Email: nhhung@ca.gov.vn Tóm tắt. Phép nhân điểm là thủ tục thường xuyên phải thực hiện trong hệ mật Elliptic. Nó đặc biệt nhạy cảm khi thực hiện phép nhân giữa khóa bí mật với một điểm công khai. Các phương pháp tấn công phân tích năng lượng có thể khám phá khóa bí mật nếu sử dụng phép nhân điểm thông thường (như nhị phân). Bài báo này sẽ giới thiệu, phân tích các thuật toán nhân điểm đã biết và đề xuất một thuật toán an toàn và hiệu quả, có khả năng chống lại các tấn công phân tích năng lượng. Từ khóa: Phép nhân điểm, hệ mật Elliptic, khóa bí mật, phân tích năng lượng. 1. Giới thiệu Hệ mật Elliptic đã trở thành một phần quan trọng của mật mã khóa công khai do thực tế là người ta có thể đạt được cùng một mức độ bảo mật như RSA nhưng với độ dài khóa ngắn hơn, dung lượng lưu trữ ít hơn. Điều này làm cho hệ mật dễ dàng sử dụng trong các hệ thống thiết bị nhỏ gọn, bộ nhớ hạn chế như điện thoại di động, thiết bị cầm tay. Đây là lí do tại sao các đường cong elliptic là một chủ đề nghiên cứu quan trọng trong mật mã. Các cuộc tấn công kênh kề [2] dựa trên việc tiêu thụ năng lượng và thời gian như đã chỉ ra bởi độ phức tạp tính toán cần thiết để thực hiện phép nhân điểm khi cài đặt hệ mật Elliptic. Phép nhân điểm ở đây có dạng: Q = dP trong đó, P là một điểm công khai trên đường cong và d thường là khóa bí mật. Nếu sử dụng các phép nhân điểm thông thường, nhị phân chẳng hạn, các tấn công phân tích năng lượng sẽ phân biệt được các bít 0 và 1 của khóa bí mật d khi thực hiện phép nhân điểm. Để chống lại kiểu tấn công này, nhiều phép nhân điểm an toàn đã được đưa ra [4]. Sau đây, chúng tôi sẽ giới thiệu một thuật toán nhân điểm an toàn và phân tích tính hiệu quả cùng khả năng cài đặt thực hành của thuật toán này. 131 Nguyễn Hữu Hùng 2. Nội dung nghiên cứu 2.1. Một số phương pháp nhân điểm 2.1.1. Phép cộng điểm Xét dạng Weierstrass của một đường cong elliptic trên trường hữu hạn Fp với p > 3 nguyên tố: E : y 2 = x3 + ax + b với a, b ∈ Fp ; 4a3 + 27b2 6= 0(mod p) Tập tất cả các điểm P (x, y) thoả mãn E, cùng với điểm vô cực ∞, được kí hiệu là E(Fp ), tạo nên một nhóm Abelian. Gọi #E là cấp của E(Fp ). Để cho hệ mật elliptic an toàn, thường chọn #E là số nguyên tố. Bài báo này chỉ xét đến các trường hợp cấp của đường cong là nguyên tố. Ta kí hiệu x(P ) và y(P ) tương ứng là toạ độ x và toạ độ y của điểm P . Giả sử P1 = (x1 , y1 ) và P2 = (x2 , y2 ) là hai điểm trên E(Fp ) khác ∞. Tổng P3 = P1 + P2 = (x3 , y3 ) có thể được tính bởi x3 = λ(P1 , P2 )2 − x1 − x2 , y3 = λ(P1 , P2 )(x1 − x2 ) − y1 , trong đó λ(P1 , P2 ) = (3x21 + a)/(2y1 ) khi P1 = P2 (phép nhân đôi điểm - ECDBL) và λ(P1 , P2 ) = (y2 − y1 )/(x2 − x1 ) khi P1 ∈ / ±P2 (phép cộng điểm - ECADD). Cả hai công thức đều cần một phép tính nghịch đảo trong Fp , nó cần nhiều thời gian hơn so với phép nhân trong Fp . Người ta thường chuyển toạ độ affine (x, y) thành các toạ độ khác mà ở đó phép cộng không cần nghịch đảo, tọa độ Jacobian là một ví dụ. Trong toạ độ Jacobian, đặt x = X/Z 2 và y = Y /Z 3 cho ta phương trình EJ = Y 2 = X 3 +aXZ 4 +bZ 6 . Khi đó, hai điểm (X : Y : Z) và (r 2 X : r 3 Y : rZ) được coi như là cùng một điểm với r ∈ Fp∗ . Đặt P1 = (X1 : Y1 : Z1 ), P2 = (X2 : Y2 : Z2 ) và P3 = P1 + P2 = (X3 : Y3 : Z3 ). Phép cộng và phép nhân đôi có thể được biểu diễn như sau: Bảng 1. Phép cộng điểm trong toạ độ Jacobian X3 = T, Y3 = −8Y14 + M (S − T ), Z3 = 2Y1 Z1 ECDBLJ S = 4X1 Y12 , M = 3X12 + aZ14 , T = −2S + M 2 X3 = −H 3 − 3U1 H2 + R2 , Y3 = −S1 H 3 + R(U1 H 2 − X3 ), Z3 = Z1 Z2 H ECADDJ U1 = X1 Z22 , U2 = X2 Z12 , S1 = Y1 Z23 , S2 = Y2 Z13 , H = U2 − U1 , R = S2 − S1 2.1.2. Phép nhân điểm Trong hệ mật Elliptic cần phải tính dP , với P ∈ E(Fp ) và d là số nguyên n-bít. Các phương pháp để thực hiện phép nhân được mô tả trong [5]. Đơn giản nhất để tính dP là phương pháp nhị phân. Thuật toán 1: Nhân điểm theo phương pháp nhị phân Input: d = (dn−1 . . . d1 d0 )2 , P ∈ E(Fp ), (dn−1 = 1). Output: dP . 132 Về một thuật toán nhân điểm an toàn của hệ mật elliptic 1. Q ← P 2. Cho i = (n − 2) giảm đến 0 thực hiện: 2.1. Q ← ECDBL(Q) 2.2. N ...