Về một giải pháp cứng hóa phép tính lũy thừa modulo

Bài viết trình bày giới thiệu, phân tích lựa chọn thuật toán lũy thừa modulo và phép nhân modulo Montgomery dựa trên một số công trình nghiên cứu trên thế giới. Phép tính lũy thừa modulo được thực thi bằng ngôn ngữ mô tả phần cứng HDL Verilog số modulo lựa chọn 2048 bit, chip FPGA XC7z045.
Nội dung trích xuất từ tài liệu:
Về một giải pháp cứng hóa phép tính lũy thừa modulo Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin Về ột giải pháp cứng h a phép t nh y thừa modulo Trần Văn Thắng, Hoàng Văn Thức Tóm tắt— h p t nh th o u o à ph p Keywords: RSA; Montgomery multiplication; t nh n trong ngu n th t FPGA. à ph p t nh phứ t p, ti u t n tài ngu n và th i gi n th hi n i tv i s n Th I. GIỚI THIỆU thi ứng h ph p t nh th o u o tr n thể n i cho đến th i điể hiện t i RS gi p n ng o t , gi th i gi n à hệ ật h a c ng hai đang được ứng ho ph p t nh, p ứng u ầu trong ài to n dụng rộng r i nhất trong các sản ph bảo ật th t Tr ng t ph p t nh th à ph p và an toàn th ng tin. Để hệ thống ật RS nh n o u o s n Trong n i ung ài o được ứng dụng ột cách hiệu quả và an toàn, h ng tôi trình à gi i thi u, ph n t h, h n thu t to n th o u o và ph p nh n o u o trên thế giới đ c nhiều c ng tr nh nghiên cứu Montgo er tr n t s ông trình nghi n cải tiến thuật toán t nh y thừa odu o trên ứu tr n th gi i h p t nh th o uo ph n cứng và ph n ề , đ y à phép t nh c ượ th thi ằng ngôn ngữ ô t phần ứng bản tiêu tốn nhiều th i gian t nh toán nhất trong HDL Veri og s o uo h n 2048 it, hip các nguyên th y ật RS . Trên c sở các XC7z045 K t qu th hi n ph p t nh ết quả đ được c ng bố trên thế giới, trong bài th o u o v i h i gi i ph p thi t k õi I nh n viết này chúng t i tr nh bày việc ph n t ch, ựa Montgo er kh nh u ượ tổng hợp ngắn g n chọn và triển hai cài đặt cứng h a thuật toán tr n B ng 1 và B ng 2. tính y thừa odu o với độ dài odu o à 2048 Abstract— Modular exponentiation is the bit, đưa ra ột số đánh giá ban đ u hi ết quả basic operation in cryptography algorithm RSA. cài đặt được thực thi trên hip Xi inx X 7z045. This’s o p i te gorith , onsu ing resource and time to implement (especially with Để thực hiện phép y thừa odu o, chúng large number). Hardware implementation of ta c thể sử dụng ột trong các thuật toán: phép modular exponentiation on the FPGA would y thừa nhị ph n từ trái qua phải (Left-to-right increase speed, reduce computation time that is Binary Exponentiation), phép y thừa nhị ph n required by the practice. The heart of modular từ phải qua trái (Right-to-left Binary operand is modular multiplication of large Exponentiation) phép y thừa cửa sổ trượt number. In this paper we presented introduction, (Slide-window Exponentiation). Tùy thuộc vào the analysis, choosing modular exponentiation i trư ng cài đặt à ỗi thuật toán c những algorithm and modular multiplication điể nh yếu hác nhau. Dưới đ y chúng t i Montgomery based on several public researchs xin giới thiệu ột số thuật toán t nh y thừa on the world. Modular exponentiation operation is implemented with hardware language HDL odu o đưa ra ph n t ch, ựa chọn ra ột thuật Verilog with the modulus is chosen as 2048 bit, toán hiệu quả thực thi trên nền tảng ph n cứng chip FPGA XC7z045. Implementation results of FPGA. modular exponentiation with two different Ph n tiếp theo c a bài báo sẽ c bố cục như designs of IPcore Montgomery is briefly sau: Mục II sẽ tr nh bày ột số thuật toán y presented in Table 1 and Table 2. thừa odu o và một số cải biên cho phép nh n Từ khóa: RSA; Montgomery multiplication; nhanh Montgomery. Tiếp theo Mục III sẽ tr nh FPGA. bày cách triển hai thực hiện. Kết quả thực hiện sẽ được tr nh bày trong Mục IV và cuối cùng à Bài báo được nhận ngày 01/11/2018. Bài báo được gửi Mục Kết uận. nhận xét và được chấp nhận đăng bởi phản biện thứ nhất vào ngày 02/12/2018 và 20/12/2018. Bài báo được gửi nhận xét và được chấp nhận đăng bởi phản biện thứ hai vào ngày 5/12/2018 và 28/12/2018. Số 2.CS (08) 2018 45 Journal of Science and Technology on Information Security II. THUẬT TOÁN LŨY THỪ MODULO Thuật toán [3]. Lũy thừa nhị phân từ trái A. Một số thuật toán lũy thừa modulo qua phải Thuật toán [1]. Thuật toán lũy thừa từ trái Đ u vào: g ϵ G, A à ột số nguyên dư ng qua phải k-ary và e = (et et-1....e1 e0 )2 Đ u vào: g và e = (et et-1....e1 e0 )b ở đ y b = Đ u ra: ge 2 và k ≥ 1; k 1. A ← 1 Đ u ra: ge 2. Cho i ch y từ t giả d n về 0 thực hiện 1. T nh toán trước như sau: 1.1. g0 ← 1 2.1. A← A.A 1.2. Cho i ch y từ 1 tới (2k - 1) thực hiện: 2.2. Nếu ei = ...