Đề xuất dạng tham số cho các hệ mật có độ an toàn dựa trên bài toán logarit rời rạc trên trường GF(p)

Bài viết đề xuất một dạng tham số nguyên tố p với mục tiêu hỗ trợ việc tính toán nhanh trên GF(p) mà không ảnh hưởng đến độ an toàn của các hệ mật có độ an toàn dựa trên bài toán logarit rời rạc trên trường này.
Nội dung trích xuất từ tài liệu:
Đề xuất dạng tham số cho các hệ mật có độ an toàn dựa trên bài toán logarit rời rạc trên trường GF(p) Công nghệ thông tin<br /> <br /> ĐỀ XUẤT DẠNG THAM SỐ CHO CÁC HỆ MẬT CÓ ĐỘ AN TOÀN<br /> DỰA TRÊN BÀI TOÁN LOGARIT RỜI RẠC TRÊN TRƯỜNG GF(P)<br /> <br /> Hoàng Văn Việt1*, Vũ Bá Nhã2<br /> <br /> Tóm tắt: Khi sử dụng các hệ mật khóa công khai như RSA, Elgamal, Diffie-<br /> Helman, ... ngoài việc quan tâm hàng đầu là tính an toàn thì một quan tâm nữa của<br /> người ứng dụng là tính hiệu quả của chúng. Bài báo đề xuất một dạng tham số<br /> nguyên tố p với mục tiêu hỗ trợ việc tính toán nhanh trên GF(p) mà không ảnh<br /> hưởng đến độ an toàn của các hệ mật có độ an toàn dựa trên bài toán logarit rời<br /> rạc trên trường này.<br /> Từ khóa: Mật mã khóa công khai, Logarith rời rạc, Giao thức trao đổi khóa.<br /> <br /> <br /> 1. ĐẶT VẤN ĐỀ<br /> Trong thực tế, sử dụng các hệ mật khóa công khai như RSA, Elgamal, Diffie-<br /> Helman, ... ngoài việc quan tâm hàng đầu là tính an toàn thì một quan tâm nữa<br /> của người ứng dụng là tính hiệu quả của chúng. Nhiều nghiên cứu có tính hệ<br /> thống tập trung vào vấn đề tìm ra các thuật toán nhanh cho phép tính modulo trên<br /> vành được phát triển nhiều nhất trong đó kết quả tốt nhất là thuật toán của<br /> Barrett [1], trong đó, có thể kể đến việc tìm ra các loại modulo đặc biệt hỗ trợ<br /> cho việc tính toán nhanh điển hình là các số nguyên tố NIST (National Institute<br /> of Standards and Technology) được đưa vào chuẩn FIPS 186-2 [2] để dùng cho<br /> các ứng dụng hệ mật trên các đường cong elliptic. Đối với những ứng dụng của<br /> các hệ mật có độ an toàn dựa trên bài toán logarit rời rạc trên trường GF(p) thì<br /> ngoài như một điều kiện bắt buộc trong việc sử dụng phần mềm LINUX<br /> (freesoftware) là các số nguyên tố p phải có 64 bít cao nhất bằng 1 thì chưa có<br /> một công bố nào liên quan đến tham số p nhằm hỗ trợ tính toán nhanh phép rút<br /> gọn trên GF(p). Trong bài này, chúng tôi tập trung tìm ra một dạng tham số<br /> nguyên tố p với mục tiêu hỗ trợ việc tính toán nhanh trên GF(p) mà không ảnh<br /> hưởng đến độ an toàn của các hệ mật có độ an toàn dựa trên bài toán logarit rời<br /> rạc trên trường này với mục đích khuyến cáo người dùng sử dụng chúng và có<br /> thể cao hơn là đưa chúng vào các chuẩn để sử dụng.<br /> <br /> Phần còn lại của bài báo được cấu trúc như sau: Mục 2 trình bày về phép rút<br /> gọn trên GF(p); Mục 3 và 4 trình bày về việc tồn tại và cách sinh các tham số p an<br /> toàn có dạng đặc biệt; Cuối cùng là phần kết luận.<br /> <br /> <br /> 72 H. V. Việt, V. B. Nhã, “Đề xuất dạng tham số cho các hệ mật… trên trường GF(p).”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> 2. PHÉP RÚT GỌN TRÊN GF(p)<br /> <br /> Trong các ứng dụng mật mã chúng ta thường xuyên phải thực hiện phép toán<br /> rút gọn các số nguyên nào đó theo modulo , thực chất là tính . Hiển<br /> nhiên phép rút gọn có thể thực hiện thông qua một phép chia cho , tuy nhiên<br /> việc làm này sẽ phải trả một chi phí cao cho việc tính toán. Bằng cách “tránh” việc<br /> chia Barrett đã đưa ra một thuật toán chi phí thấp hơn.<br /> 2.1. Chi phí tính toán cho một số phép toán số học<br /> Theo như Donald E. Knuth [4] thì số phép toán cơ bản (còn gọi là chi phí) cho<br /> một số phép toán số học theo thuật toán của Karatsuba và Ofman [5] trên các số<br /> nguyên k-bít như sau:<br /> Phép nhân: ; Phép chia là: .<br /> Thuật toán của Karatsuba và Ofman dựa trên kết quả sau:<br /> Định lý Karatsuba-Ofman “Để nhân hai số nguyên k-bits chỉ cần tiến hành<br /> nhân 3 cặp số nguyên -bít”.<br /> Rút gọn theo thuật toán Barrett [4]<br /> Thuật toán Barrett.<br /> Input: p, b ≥ 3, k = ,0≤z< ,m= .<br /> Output: z mod p.<br /> 1. q ← .<br /> <br /> 2. r ← .<br /> 3. if r < 0 then .<br /> 4. while r ≥ p do: .<br /> 5. return (r).<br /> Chi phí tính toán cho một phép rút gọn của thuật toán Barrett được đánh giá<br /> trong kết quả dưới đây.<br /> Kết quả 1. Chi phí tính toán cho thuật toán rút gọn Barrett theo modulo gồm<br /> k ký tự bằng chi phí của hai phép nhân hai số nguyên k ký tự.<br /> Chứng minh<br /> Để thực hiện thuật toán trên chúng ta cần đến hai phép nhân số lớn, một là<br /> ở bước 1 và một là q.p trong bước 2. Rõ ràng cả 4 giá trị , m,<br /> q và p đều là các số k ký tự nên kết quả 1 đã được chứng minh.<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san An toàn Thông tin, 05 - 2017 73<br />  Công nghệ thông tin<br /> <br /> 2.2. Rút gọn với giá trị p đặc biệt<br /> Định nghĩa 1. Cho b là một số tự nhiên lớn hơn 1 bất kỳ, số nguyên tố p =<br /> (1) được gọi là có dạng đặc biệt nếu a < (2).<br /> Thuật toán đề xuất. (rút gọn theo modulo p dạng đặc biệt)<br /> Input: p = , b ≥ 3, a < ,0≤z< .<br /> Output: z mod p.<br /> 1. r ← z mod ...