Xây dựng các thuật toán mật mã khóa công khai dựa trên tính khó của việc giải đồng thời 2 bài toán logarit rời rạc và phân tích số khai căn

Bài viết đề xuất xây dựng thuật toán mật mã khóa công khai từ mức độ khó của việc giải đồng thời 2 bài toán: Bài toán logarit rời rạc trên Zp và bài toán phân tích một số nguyên lớn ra các thừa số nguyên tố, hoặc: Bài toán logarit rời rạc trên Zp và bài toán khai căn trên vành Zn. 02 thuật toán mới đề xuất đảm bảo mức độ an toàn trước các tấn công: Làm lộ khóa bí mật, thám mã bản tin. Đồng thời xác thực nguồn gốc văn bản điện tử, cũng như đảm bảo việc xác thực người gửi.
Nội dung trích xuất từ tài liệu:
Xây dựng các thuật toán mật mã khóa công khai dựa trên tính khó của việc giải đồng thời 2 bài toán logarit rời rạc và phân tích số khai căn Công nghệ thông tin XÂY DỰNG CÁC THUẬT TOÁN MẬT MÃ KHÓA CÔNG KHAI DỰA TRÊN TÍNH KHÓ CỦA VIỆC GIẢI ĐỒNG THỜI 2 BÀI TOÁN LOGARIT RỜI RẠC VÀ PHÂN TÍCH SỐ/KHAI CĂN Nguyễn Vĩnh Thái1*, Lưu Hồng Dũng2 Tóm tắt: Bài báo đề xuất xây dựng thuật toán mật mã khóa công khai từ mức độ khó của việc giải đồng thời 2 bài toán: bài toán logarit rời rạc trên Zp và bài toán phân tích một số nguyên lớn ra các thừa số nguyên tố, hoặc: bài toán logarit rời rạc trên Zp và bài toán khai căn trên vành Zn. 02 thuật toán mới đề xuất đảm bảo mức độ an toàn trước các tấn công: làm lộ khóa bí mật, thám mã bản tin. Đồng thời xác thực nguồn gốc văn bản điện tử, cũng như đảm bảo việc xác thực người gửi. Từ khóa: Logarit rời rạc; Phân tích số; Khai căn; Thuật toán khóa mật mã; Hệ thống mã khóa khóa công khai. 1. ĐẶT VẤN ĐỀ Hiện tại, RSA [1] vẫn đang được sử dụng trong các giao dịch điện tử (Chính phủ điện tử, thương mại điện tử...) do tính mềm dẻo và độ an toàn của nó. Tuy nhiên, thuật toán hệ mật này cũng có một nhược điểm căn bản so với các hệ mật được xây dựng trên bài toán logarit rời rạc (ElGamal, DSA, GOST R34.10-94...) [3] đó là các thực thể đầu cuối không được phép dùng chung modulo n với nhau. Nói cách khác: mỗi thực thể đầu cuối phải sở hữu một cặp tham số ( , ) nguyên tố riêng biệt. Hơn nữa, cặp tham số này phải được giữ bí mật tuyệt đối. Trên thực tế, việc tạo ra các số nguyên tố lớn và mạnh theo các tiêu chuẩn an toàn (FIPS 186 - 4) [2] và giữ bí mật tuyệt đối cho chúng là không đơn giản, nên nhược điểm trên đã ảnh hưởng không nhỏ đến khả năng ứng dụng rộng rãi của hệ mật này (RSA) trong thực tế. Nâng cao độ an toàn cho các thuật toán mật mã khóa công khai dựa trên tính khó của việc giải đồng thời 2 bài toán khó là một hướng tiếp cận đang nhận được nhiều sự quan tâm của các nhà nghiên cứu [4 - 9]. Cũng với mục đích nâng cao độ an toàn cho thuật toán trước một số dạng tấn công trong thực tế, nhóm tác giả bài báo này đề xuất xây dựng 02 thuật toán: mật mã khóa công khai; mã hóa - xác thực dựa trên tính khó của việc giải đồng thời 2 bài toán logarit rời rạc và phân tích số/khai căn, cho phép nhiều người dùng (thực thể cuối) sử dụng chung một , nghĩa là chỉ cần tạo ra một cặp tham số ( , ) duy nhất cho tất cả các thực thể cuối. Ngoài ra, các tham số này không cần phải được giữ bí mật như ở hệ RSA mà vẫn có thể chống lại các dạng tấn công đã biết trong thực tế, đảm bảo độ an toàn của hệ thống. 2. MỘT SỐ BÀI TOÁN KHÓ ỨNG DỤNG TRONG MẬT MÃ 2.1. Bài toán phân tích số Bài toán phân tích số được phát biểu như sau: Cho số ∈ ℕ, hãy tìm biểu diễn: =Π với: ≥ 1( = 1, … , ) nguyên dương; ≥ 1 ( = 1, … , ) nguyên tố. 24 N. V. Thái, L. H. Dũng, “Xây dựng các thuật toán mật mã … và phân tích số/khai căn.” Nghiên cứu khoa học công nghệ Một trường hợp riêng của bài toán phân tích số được ứng dụng để xây dựng hệ mật RSA mà ở đó là tích của hai số nguyên tố và . Khi đó, bài toán phân tích số hay còn gọi là bài toán ( ) được phát biểu như sau: Với mỗi số nguyên dương , hãy tìm số nguyên tố hoặc thỏa mãn phương trình sau: × = . Giải thuật cho bài toán ( ) có thể được viết như một thuật toán tính hàm (.) với biến đầu vào là , còn giá trị hàm là hoặc của phương trình sau: = ( ) hoặc: = ( ) Trong hệ mật RSA, bài toán phân tích số được sử dụng trong việc hình thành cặp khóa công khai/bí mật cho mỗi thực thể ký. Với việc giữ bí mật các tham số ( , ) thì việc tính được khóa bí mật ( ) từ khóa công khai ( ) và ( ) là một bài toán khó nếu , được chọn đủ lớn và mạnh. Hiện tại bài toán trên vẫn được coi là bài toán khó do chưa có giải thuật thời gian đa thức hay đa thức xác suất cho nó và hệ mật RSA là một minh chứng thực tế cho tính khó giải của bài toán này. Trong thực tế, các tham số , có thể chọn theo FIPS 186 - 4 của Hoa Kỳ cho hệ mật RSA. 2.2. Bài toán khai căn trên Cho cặp số nguyên dương ( , ) với là tích 2 số nguyên tố và sao cho bài toán phân tích số là khó giải trên Z , còn là một giá trị thỏa mãn: 1 < < ( ) và gcd , ( ) = 1, ở đây: ( ) = ( − 1). ( − 1). Khi đó, bài toán khai căn trên Z hay còn gọi là RSAP( , ) được phát biểu như sau: Với mỗi số nguyên dương ∈ ℤ∗ , hãy tìm thỏa mãn phương trình sau: = Bài toán RSAP( , ) cũng là một cơ sở quan trọng để xây dựng nên hệ mật RSA. Ở hệ mật RSA nếu giải được RSAP( , ) , kẻ thám mã có thể tìm được bản rõ (M) từ bản mã (C) và các tham số công khai ( , ), hoặc dễ dàng tạo được chữ ký giả mạo (S) cho một bản tin bất kỳ (M) mà không cần biết khóa bí mật (d) của đối tượng ký (bị mạo danh). Tuy nh ...