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

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.

pdf9 trang | Chia sẻ: thanhle95 | Lượt xem: 324 | Lượt tải: 0download
Bạn đang xem nội dung tài liệu Về một thuật toán nhân điểm an toàn của hệ mật Elliptic, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
JOURNAL OF SCIENCE OF HNUE FIT., 2013, Vol. 58, pp. 131-139 This paper is available online at 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 : y2 = 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/Z2 và y = Y/Z3 cho ta phương trìnhEJ = Y 2 = X3+aXZ4+bZ6. Khi đó, hai điểm (X : Y : Z) và (r2X : r3Y : rZ) được coi như là cùng một điểm với r ∈ F ∗p . Đặ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 ECDBLJ X3 = T, Y3 = −8Y 4 1 +M(S − T ), Z3 = 2Y1Z1 S = 4X1Y 2 1 ,M = 3X 2 1 + aZ 4 1 , T = −2S +M 2 ECADDJ X3 = −H 3 − 3U1H2 +R 2, Y3 = −S1H 3 +R(U1H 2 −X3), Z3 = Z1Z2H U1 = X1Z 2 2 , U2 = X2Z 2 1 , S1 = Y1Z 3 2 , S2 = Y2Z 3 1 ,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. . . d1d0)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ếu (di == 1) thì Q← ECADD(Q,P ) 3. Trả về Q. Phương pháp cửa sổ: Trong phương pháp này, ta lựa chọn một độ lớn của cửa sổ là w và tính trước 2w giá trị kP với k = 0, 1, 2, ..., 2w − 1. Thuật toán sử dụng biểu diễn của khóa bí mật dưới dạng d = d0 + 2wd1 + 2wd2 + ... + 2mwdm: Thuật toán 2: Nhân điểm sử dụng phương pháp cửa sổ Input: w, P ∈ E(Fp), d = d0 + 2wd1 + 2wd2 + ... + 2mwdm. Output: dP . 1. Q←∞ 2. Cho i = 0 đếnm thực hiện: 2.1. Q← 2wQ (sử dụng lặp lại các phép toán nhân đổi điểm ECDBL). 2.2. Nếu di > 0 thì Q← ECADD(Q, diP ). 3. Trả về Q[0]. Thuật toán này có lợi thế hơn so với phương pháp nhị phân là sử dụng ít phép cộng điểm hơn. Thông thường, như được đề nghị bởi NIST, giá trị tốt nhất cho độ lớn của cửa sổ là w = 4. Độ phức tạp tổng thể của thuật toán này với d là một số n-bít là (n+1) phép ECDBL và 2w − 2 + n w phép ECADD. Phương pháp cửa sổ NAF: Phương pháp này dựa vào biểu diễn NAF - Non-Adjacent Form của một số nguyên. Một số nguyên d có thể biểu diễn dưới dạng NAF trong cửa sổ có độ lớn w theo thuật toán sau: Thuật toán 3: Biểu diễn wNAF của một số nguyên Input: Độ lớn của cửa sổ w, số nguyên d độ dài n-bít. Output: Biểu diễn wNAF của d : (di−1, di−2, ..., d0). 1. i← 0 2. Trong khi (d > 0) thực hiện: 2.1. Nếu (d mod 2) == 1 thì (di ← d mods 2w; d← d− di); Còn không thì di ← 0 2.2. d← d/2; i← i+ 1 3. Trả về (di−1, di−2, ..., d0). Trong đó hàm mods được định nghĩa là: - Nếu d > 2w−1 thì trả về (dmod 2w)− 2w còn không thì trả về (dmod 2w). Thuật toán nhân điểm kiểu cửa sổ NAF yêu cầu tính trước dãy các điểm {1, 3, 5, ..., 2w−1− 1}P và các điểm đối của chúng (điểm đối của P (x, y) là −P (x,−y)). Thuật toán nhân điểm sẽ như sau: Thuật toán 4: Nhân điểm theo phương pháp cửa sổ NAF 133 Nguyễn Hữu Hùng Input: (di−1, di−2, ..., d0), P ∈ E(Fp). Output: dP . 1. Q←∞ 2. Cho j = (i− 1) giảm đến 0 thực hiện: 2.1. Q← ECDBL(Q) 2.2. Nếu (dj! = 0) thì Q← ECADD(Q, djP ) 3. Trả về Q. Phương pháp này yêu cầu tính trước 1 phép ECDBL và w−1 phép ECADD. Sau đó thuật toán yêu cầu n phép ECDBL và n w + 1 phép ECADD. Như vậy, độ phức tạp tổng thể của thuật toán, không kể phép biểu diễn NAF, là (n+1) phép ECDBL và w− 1+ n w + 1 phép ECADD. Phương pháp luôn-cộng và nhân đôi: Thuật toán 5: Nhân điểm sử dụng phương pháp luôn-cộng và nhân đôi Input: d = (dn−1. . . d1d0)2, P ∈ E(Fp), (dn−1 = 1). Output: dP . 1. Q[0]← P 2. Cho i = (n− 2) giảm đến 0 thực hiện: 2.1. Q[0]← ECDBL(Q[0]) 2.2. Q[1− di]← ECADD(Q[0], P ) 3. Trả về Q[0]. Độ phức tạp của thuật toán này là (n− 1) phép ECDBL và (n− 1) phép ECADD. Rõ ràng thuật toán này không để lộ bít thông tin của khóa bí mật khi thực hiện phép nhân. Thuật toán Montgomery-bậc thang: Thuật toán 6: Nhân điểm sử dụng phương pháp Montgomery-bậc thang Input: P ∈ E(Fp), d = d0 + 21d1 + 22d2 + ...+ 2ndn. Output: dP . 1. R0 ←∞, R1 ← P 2. Cho i = 0 đến n thực hiện: 2.1. Nếu (di == 0) thì: - R1 ← ECADD(R0, R1) - R0 ← ECDBL(R0) 2.2. Còn không thì: - R0 ← ECADD(R0, R1) - R1 ← ECDBL(R1) 3. Trả về R0. Độ phức tạp và thời gian chạy của thuật toán này tương đương với phương pháp 134 Về một thuật toán nhân điểm an toàn của hệ mật elliptic nhân điểm luôn-cộng và nhân đôi. Phương pháp này tiếp cận cách nhân điểm theo các khoảng thời gian cố định. Điều này có hiệu quả trong việc chống lại các tấn công kênh kề, ở đó kẻ tấn công sẽ khám phá từng bít khóa bí mật bằng cách đo sự chênh lệch năng lượng và thời gian thực hiện của các bước trong thuật toán. 2.2. Các tấn công phân tích năng lượng đối với hệ mật Elliptic 2.2.1. SPA và các phương pháp kháng SPA SPA theo dõi việc tiêu thụ năng lượng của các thiết bị, và phát hiện sự khác nhau giữa các thao tác sử dụng khoá bí mật. Các Thuật toán 1, 2 và 4 ở trên đều bị tấn công bởi SPA. Phép nhân vô hướng được tính bởi công thức cộng, cụ thể là ECDBL và ECADD, dựa trên các bít của khoá bí mật vô hướng. Thao tác ECADD trong các thuật toán này được tính khi và chỉ khi bít cơ sở là 1, trong khi đó ECDBL luôn luôn được tính. Công thức cộng là một tập hợp các phép toán của một trường xác định. Có nhiều điều khác nhau giữa các phép toán cơ sở của phép ECDBL và phép ECADD. Vì vậy, SPA có thể phát hiện bít bí mật. Phương pháp kháng SPA: Với mục đích kháng lại SPA, phải loại bỏ mối liên quan giữa thông tin bít và phép cộng chúng. Phương pháp đơn giản được đề xuất bởi Coron [1] thể hiện trong Thuật toán 5 và 6. Trong các thuật toán này, luôn luôn thực hiện tính ECADD bất kể bít khóa bí mật là 0 hay 1. Như vậy, kẻ tấn công không thể đoán các bít thông tin của khóa bí mật bằng phương pháp SPA. 2.2.2. DPA và các phương pháp kháng DPA Tấn công phân tích năng lượng vi sai theo dõi việc tiêu thụ năng lượng và phân tích thông tin này cùng với các công cụ thống kê tinh vi hơn. Một phương pháp là an toàn chống lại SPA nhưng có thể không an toàn dưới DPA. Kẻ tấn công DPA cố gắng đoán phép tính cP với số nguyên c được thực hiện trong phép nhân vô hướng. Anh ta nhận được các năng lượng tiêu thụ cho việc tính cPi với i = 1, 2, 3. . . , và phát hiện ra đỉnh xuất hiện từ hàm tương quan dựa trên bít cụ thể của cPi. DPA có thể áp dụng với các Thuật toán 5 và 6 bởi vì dãy các điểm được tạo ra từ các thuật toán này là tất định và DPA có thể tìm ra mối tương quan đối với một bít cụ thể. Phương pháp kháng DPA của Coron: Coron [1] chỉ ra rằng nó cần thiết để chèn các số ngẫu nhiên trong quá trình tính dP để chống lại DPA. Dựa trên sự ngẫu nhiên hoá các toạ độ Jacobian (hoặc toạ độ xạ ảnh). Để chống lại DPA, chuyển P = (x, y) trong hệ toạ độ affine thành P = (r2x : r3y : r) trong hệ toạ độ Jacobian với một giá trị ngẫu nhiên r ∈ K∗. Giá trị ngẫu nhiên này sẽ tạo ra tính ngẫu nhiên trong mỗi biểu diễn của điểm và làm ngẫu nhiên việc tiêu thụ năng lượng trong phép nhân vô hướng dP . 2.2.3. ZVP và các phương pháp kháng ZVP Tấn công phân tích năng lượng của Goubin: Goubin [3] đã đề xuất một phương pháp phân tích năng lượng mới sử dụng một điểm mà có thể đã không được ngẫu nhiên 135 Nguyễn Hữu Hùng bởi phương pháp kháng DPA như mô tả ở trên. Goubin tập trung vào các điểm (x, 0) và (0, y). Các điểm này được biểu diễn tương ứng là (X : 0 : Z) và (0 : Y : Z) trong toạ độ Jacobian. Ngay cả khi các điểm đó được ngẫu nhiên hoá thì một trong các toạ độ của nó vẫn bằng không, cụ thể là (r2X : 0 : rZ) và (0 : r3Y : rZ) đối với số nguyên ngẫu nhiên nào đó r ∈ K∗. Như vậy, kẻ tấn công có thể phát hiện điểm (x, 0) hoặc (0, y) được sử dụng trong phép nhân vô hướng sử dụng DPA. Kẻ tấn công có thể khám phá khoá bí mật sử dụng các điểm đó như sau: Đối với một giá trị vô hướng c đã cho, luôn có thể tạo ra một điểm P thoả mãn P = (c−1#E)(0, y), bởi vì ta xét với bậc của đường cong #E là nguyên tố. Nếu như kẻ tấn công chọn P như là điểm cơ sở cho phép nhân vô hướng, DPA có thể phát hiện được là cP có được tính hay không trong quá trình nhân vô hướng. Khi đó kẻ tấn công có thể nhận được toàn bộ khoá bí mật bằng cách áp dụng đệ quy quá trình này từ bit cao nhất. Tấn công điểm giá trị-không [2] (ZPA - Zero-value Point Attack): Tấn công của Goubin được mô tả ở trên chỉ là một trường hợp riêng ở đây. Mục đích của tấn công điểm giá trị-không (Zero-Point Attack - ZPA) là khám phá khoá bí mật bằng việc chọn thích ứng điểm cơ sở P . Ta giả sử rằng phép nhân vô hướng được tính theo Thuật toán 5. Kẻ tấn công có thể khám phá khoá bí mật từ bít cao nhất. Bít có ý nghĩa thứ hai dn−2 có thể được khám phá bằng cách kiểm tra khi một trong các phép tính ECDBL(2Q), ECADD(2Q,Q), ECDBL(3Q) và ECADD(3Q,Q) được thực hiện. Rõ ràng rằng, bít dn−2 = 0 thì Thuật toán 5 sẽ thực hiện hai phép tính là ECDBL(2Q) và ECADD(2Q,Q). Bít dn−2 = 1 thì Thuật toán 2 sẽ thực hiện phép tính ECDBL(3Q) và ECADD(3Q,Q). Nếu tồn tại các thanh ghi giá trị-không trong khi thực hiện các phép tính này thì kẻ tấn công có thể phát hiện ra phép tính bằng cách đo năng lượng tiêu thụ sụt giảm. Tương tự như vậy cho các bít tiếp theo. Như vậy, nếu muốn tìm một điểm P mà nhận thanh ghi giá trị-không tại ECDBL, ta có thể sử dụng điểm cơ sởQ = (c−1 mod#E)P với số nguyên c nào đó cho tấn công này. Đối với phép cộng ECADD, phải tìm điểm cơ sở Q sao cho tạo ra thanh ghi giá trị-không khi thực hiện ECADD(cQ,Q). Tóm lại, kẻ tấn công phải tìm điểm Q mà tạo ra thanh ghi giá trị-không tại ECDBL(cQ) hoặc ECADD(cQ,Q) đối với một số c đã cho. Ta gọi các điểm đó là điểm giá trị-không (Zero-Value Point - ZVP). Phương pháp kháng ZPA: Điểm cơ sở P (x0, y0) của đường cong elliptic E trên trường hữu hạn FP xác định bởi y2 = x3 + ax + b phải thỏa mãn một số tính chất như x0 6= 0, 3x20 + a 6= 0 và 5x40 + 2ax20 − 4bx0 + a2 6= 0. 2.3. Đề xuất thuật toán an toàn và hiệu quả 2.3.1. Thuật toán kết hợp giữa phương pháp cửa sổ và phương pháp luôn-cộng và nhân đôi Từ những phân tích về các tấn công SPA, DPA và ZPA ở trên, chúng tôi kết hợp giữa Thuật toán 4 và Thuật toán 5 để đưa ra một thuật toán đảm bảo an toàn kháng lại các 136 Về một thuật toán nhân điểm an toàn của hệ mật elliptic tấn công phân tích năng lượng đã biết, đồng thời mang tính hiệu quả trong thực tế. Trong thuật toán này, giống như phương pháp đã mô tả ở Thuật toán 4, yêu cầu tính trước dãy các điểm {1, 3, 5, ..., 2w−1− 1}P và các điểm đối của chúng (điểm đối của P (x, y) là −P (x,−y)), trong đó biểu diễn wNAF của d là di−1, di−2,...,d0. Thuật toán 7: Nhân điểm sử dụng kết hợp hai phương pháp cửa sổ và wNAF Input: biểu diễn wNAF của khóa bí mật d = (di−1, di−2, ..., d0), P ∈ E(Fp). Output: dP. 1. Q←∞ 2. Cho j = (i− 1) giảm đến 0 thực hiện: 2.1. Q← ECDBL(Q) 2.2. Nếu (dj > 0) thì: Q← Q + djP và Q[1]← Q+ (−|dj |P ); Còn không thì: Q← Q+ (−|dj |P ) và Q[1]← Q + (|dj|P ) 3. Trả về Q. Phân tích tính đúng đắn và độ phức tạp của thuật toán: Rõ ràng thuật toán này tương đương với Thuật toán 4 - phương pháp cửa sổ NAF nếu như trong bước 2.2 bỏ đi bước tínhQ[1], việc thực hiện thêm bước tính này không làm ảnh hưởng hay thay đổi đầu ra của thuật toán, mà nó chính là ý tưởng của Thuật toán 5 - phương pháp luôn-cộng và nhân đôi để làm cho không có sự khác biệt về thời gian cũng như năng lượng tiêu thụ trong mỗi vòng lặp. Như vậy, độ phức tạp tổng thể của thuật toán này sẽ là (n+ 1) phép ECDBL và w− 1 + 2n w + 1 phép ECADD, tức là nhiều hơn n w + 1 phép ECADD so với Thuật toán 4. So với Thuật toán 5 và 6, số phép cộng ECADD là (n − 1) thì thuật toán này ít hơn cỡ 3n 5 − 4 phép toán ECADD nếu chọn độ lớn cửa sổ w = 4. 2.3.2. Một số kết quả thực nghiệm Dựa trên thư viện tính toán Elliptic Miracl [6], chúng tôi đã thực hiện việc cài đặt các Thuật toán 1, 4, 5 và 7 để thực hiện việc so sánh tốc độ tính toán cũng như kiểm tra tính đúng đắn của thuật toán đã đề xuất. Kết quả như sau: Cài đặt Thuật toán 1 - Phép nhân theo kiểu nhị phân (Ngôn ngữ C++): void PhepNhan_NhiPhan(Big *d, ECn *P, ECn *Q){ int i, n; n = logb2(d->getbig()); /* Ham lay so bit cua khoa bi mat*/ *Q = *P; for(i=n-2; i>=0; i–){ *Q+=*Q; if (mr_testbit(d->getbig(),i)==1) *Q+=*P; /* Ham kiem tra bit */ } } 137 Nguyễn Hữu Hùng Thuật toán 4 - Mã nguồn có sẵn của Phương pháp cửa sổ NAF (Ngôn ngữ C): void ecurve_mult(_MIPD_ big e,epoint *pa,epoint *pt){ . . . . . . . . . . . . . . . . . . . . . nb=logb2(d); /*So bit cua khoa bi mat */ for (i=nb-2;i>=1;) { /* Tinh windows naf */ n=mr_naf_window(h, d, i, &nbs, &nzs, WINDOWS_SZ); // h = 3d for (j=0;j<nbs;j++) ecurve_double(pt); if (n>0) ecurve_add(table[n/2],pt); if (n<0) ecurve_sub(table[(-n)/2],pt); i-=nbs; . . . . . . . . . . . . . . . . . . . . . } Cài đặt Thuật toán 5 - Phương pháp luôn cộng và nhân đôi (Ngôn ngữ C++): void PhepNhan_LuonCongvaNhan(Big *d, ECn *P, ECn *Q){ int i, n; ECn Q0, Q1; n = logb2(d->getbig()); Q0 = *P; for(i=n-2; i>=0; i–){ Q0+=Q0; if (mr_testbit(d->getbig(),i)==1) Q0+=*P; else {Q1=Q0; Q1+=*P;} } *Q=Q0; } Cài đặt Thuật toán 7 - Phương pháp kết hợp (Ngôn ngữ C): void PhepNhan_Kethop(Big *d, ECn *P, ECn *Q){ . . . . . . . . . . . . . . . . . . . . . epoint_copy(pa,pt); nb=logb2(d); for (i=nb-2;i>=1;) { n=mr_naf_window(h, d, i, &nbs, &nzs, WINDOWS_SZ); for (j=0;j<nbs;j++) ecurve_double(pt); if (n>0) {ecurve_add(table[n/2],pt); epoint_copy(pt,Q1); ecurve_sub(table[n/2],Q1);} if (n<0) { ecurve_sub(table[(-n)/2],pt); epoint_copy(pt,Q1); ecurve_add(table[-n/2],Q1);} i-=nbs; . . . . . . . . . . . . . . . . . . . . . } 138 Về một thuật toán nhân điểm an toàn của hệ mật elliptic So sánh thời gian tính của các thuật toán: Số lần thực hiện Thời gian tính (giây) Ghi chú TT 2 1000 15 C++, CPU 2GHZ, RAM 3GB TT 4 1000 11 C++, CPU 2GHZ, RAM 3GB TT 5 1000 18 C++, CPU 2GHZ, RAM 3GB TT 7 1000 14 C++, CPU 2GHZ, RAM 3GB 3. Kết luận Việc nghiên cứu các thuật toán nhân điểm an toàn và hiệu quả được ứng dụng rất nhiều trong việc cài đặt hệ mật Elliptic bằng phần mềm cũng như phần cứng. Kết hợp với các thuật toán nhân điểm đã biết, chúng tôi đã đề xuất ra được một thuật toán nhân điểm hiệu quả và an toàn chống lại kiểu tấn công phân tích năng lượng SPA/DPA. Chúng tôi cũng đã cài đặt thành công thuật toán đã đề xuất, đồng thời đưa ra một số kết quả thực nghiệm để so sánh tính hiệu quả của chúng. TÀI LIỆU THAM KHẢO [1] J.S. Coron, 1999. Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems. CHES ’99 Proceedings of the First International Workshop on Cryptographic Hardware and Embedded Systems, pp. 292-302 Springer, Verlag London, UK. [2] Toru Akishita and Tsuyoshi Takagi, 2003. Zero-Value Point Attacks on Elliptic Curve Cryptosystem. Lecture Notes in Computer Science, Vol. 2851, pp. 218-233. [3] Louis Goubin, 2003. A Refined Power-Analysis Attack on Elliptic Curve Cryptosystems. PKC ’03 Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography, Public Key Cryptography, Springer-Verlag London, pp. 199-210. [4] Bodo Muller, 2001. Securing Elliptic Curve Point Multiplication against Side-Channel Attacks. Springer, Verlag LNCS 2200, pp. 324-334. [5] [6] Miracl, ABSTRACT A secure point multiplication algorithm in elliptic cryptosystems Point multiplication is a procedure frequently performed in elliptic cryptosystems. It is particularly sensitive when performing multiplications between a secret key and a public point. The power analysis attack method can discover the secret key when using conventional point multiplication, such as the binary. This paper will introduce and analyze known algorithms and propose a secure and effective algorithm that will be able to resist a power analysis attack. 139
Tài liệu liên quan