Trong nội dung bài báo này, đề xuất một phương pháp thực hiện phép nhân điểm trên đường cong Elliptic trên trường hữu hạn theo thuật toán NAF (Non Adjacent Form) để khai triển một số nguyên. Thuật toán được cài đặt trực tiếp trên phần cứng FPGA mà không cần tính toán trước như thuật toán nhân điểm sử dụng NAF thông thường. | Một phương pháp hiệu quả thực hiện phép nhân điểm trên đường cong elliptic sử dụng thuật toán NAF Nghiên cứu khoa học công nghệ MỘT PHƯƠNG PHÁP HIỆU QUẢ THỰC HIỆN PHÉP NHÂN ĐIỂM TRÊN ĐƯỜNG CONG ELLIPTIC SỬ DỤNG THUẬT TOÁN NAF Hoàng Văn Quân1*, Nguyễn Biên Cương2, Lều Đức Tân2 Tóm tắt: Trong vài năm trở lại đây, mật mã đường cong Elliptic đã được sử dụng khá rộng rãi trong nhiều lĩnh vực. Một trong số những phép tính phức tạp trong thực hiện mật mã đường cong elliptic là phép tính nhân điểm. Trong nội dung bài báo này, chúng tôi đề xuất một phương pháp thực hiện phép nhân điểm trên đường cong Elliptic trên trường hữu hạn theo thuật toán NAF (Non Adjacent Form) để khai triển một số nguyên. Thuật toán được cài đặt trực tiếp trên phần cứng FPGA mà không cần tính toán trước như thuật toán nhân điểm sử dụng NAF thông thường. Từ khóa: Thuật toán NAF, Thuật toán nhân điểm, Mật mã, Cứng hóa ECC trên FPGA. 1. MỞ ĐẦU Phép tính cơ bản và quan trọng nhất trong thuật toán mật mã elliptic là phép nhân vô hướng một điểm trên đường cong elliptic với một số nguyên dương ( với k là số nguyên dương, P là một điểm trên đường cong Elliptic). Trong những năm gần đây, đã có nhiều thuật toán lý thuyết được công bố để thực hiện tăng tốc cho phép tính này. Trong số những thuật toán trên thì thuật toán nhân điểm dựa trên khai triển một số nguyên theo thuật toán NAF là một trong những phương pháp tính toán hiệu quả cho cài đặt trên phần cứng FPGA [1,2,4]. Thuật toán đơn giản nhất sử dụng cho tính toán phép nhân điểm là thuật toán nhị phân. Tuy nhiên, thuật toán này hoạt động khá chậm vì cần nhiều số lượng phép tính cộng điểm và nhân đôi elliptic [1,3]. Thuật toán nhân điểm dựa trên khai triển một số nguyên theo NAF đã có những cải tiến đáng kể khi giảm được số lượng phép cộng điểm từ w-1 xuống 2*(w-1)/3 (với w là số bit 1 trong biểu diễn nhị phân của k). Thuật toán nhân điểm theo NAF dựa trên ý tưởng phép cộng điểm và phép trừ điểm có .
