Xây dựng lược đồ chữ ký số trên bài toán phân tích số

Trong các giao dịch điện tử, chữ ký số (Digital Signature) được sử dụng nhằm đáp ứng yêu cầu chứng thực về nguồn gốc và tính toàn vẹn của thông tin. Bài viết trình bày lược đồ chữ ký số RSA, lược đồ đầu tiên theo hệ mật khóa công khai dựa trên bài toán phân tích số và hướng phát triển các lược đồ chữ ký số mới dựa trên tính khó giải của bài toán này
Nội dung trích xuất từ tài liệu:
Xây dựng lược đồ chữ ký số trên bài toán phân tích số 92 TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ TRÊN BÀI TOÁN PHÂN TÍCH SỐ Hoàng Thị Mai1 Trường Đại học Thủ đô Hà Nội Tóm tắt: Trong các giao dịch điện tử, chữ ký số (Digital Signature) được sử dụng nhằm đáp ứng yêu cầu chứng thực về nguồn gốc và tính toàn vẹn của thông tin. Bài báo trình bày lược đồ chữ ký số RSA, lược đồ đầu tiên theo hệ mật khóa công khai dựa trên bài toán phân tích số và hướng phát triển các lược đồ chữ ký số mới dựa trên tính khó giải của bài toán này. Từ khoá: Chữ ký số, lược đồ chữ ký số, bài toán phân tích số, chữ ký số RSA. 1. ĐẶT VẤN ĐỀ Với sự phát triển mạnh mẽ của công nghệ thông tin và truyền thông, đặc biệt là mạng Internet, ngày càng có nhiều thông tin được lưu trữ trên máy tính và truyền đi trên mạng. Theo [1], một hệ truyền tin được gọi là truyền thông tin an toàn và bảo mật khi có các đặc tính sau: 1- Tính bảo mật (Confidentiality): ngăn chặn được vấn đề xem trộm thông báo; 2- Tính chứng thực (Authentication): nhằm đảm bảo rằng thông báo gửi đi thực sự là của người gửi và không bị thay đổi trong quá trình truyền tin; 3- Tính không từ chối (Nonrepudiation): nhằm xác định rằng thông báo là do chính người gửi gửi đi, người gửi không thể chối bỏ trách nhiệm. Chữ ký số là một cơ chế cho phép đảm bảo tính chứng thực và tính không từ chối của một hệ truyền tin. Một chữ ký số kèm theo mỗi thông báo được tạo ra dựa trên giá trị băm của thông điệp và một cách mã hóa giá trị băm này nhờ khóa riêng của người gửi. Hầu hết các lược đồ chữ ký số hiện nay đều dựa trên tính khó của bài toán: phân tích một số nguyên lớn ra các thừa số nguyên tố, bài toán khai căn và bài toán logarit rời rạc trong modulo hợp số. Thuật toán chữ ký số đầu tiên (RSA) [2] được đề xuất và công bố bởi Ron 1 Nhận bài ngày 16.01.2016, gửi phản biện và duyệt đăng ngày 25.01.2016. Liên hệ tác giả: Hoàng Thị Mai; Email: htmai@daihocthudo.edu.vn. . TẠP CHÍ KHOA HỌC  SỐ 2/2016 93 Rivest, Adi Shamir và Len Adleman vào năm 1977 tại Viện Công nghệ Massachusetts (MIT) Hoa Kỳ. Thuật toán chữ ký số này được xây dựng dựa trên tính khó của bài toán phân tích một số nguyên lớn ra các thừa số nguyên tố. Dựa trên nền tảng thuật toán chữ ký số RSA, có nhiều hướng nghiên cứu phát triển các lược đồ chữ ký số. 2. LƯỢC ĐỒ CHỮ KÝ SỐ RSA 2.1. Bài toán phân tích một số nguyên lớn ra các thừa số nguyên tố Bài toán phân số về cơ bản có thể được phát biểu như sau: Cho số , hãy tìm biểu diễn: , với ei ≥1 và pi là các số nguyên tố. Trong hệ mật RSA [2], bài toán phân tích số được sử dụng làm cơ sở để hình thành cặp khóa công khai (e)/bí mật (d) cho mỗi thực thể ký và có thể phát biểu như sau: − Cho p, q là 2 số nguyên tố lớn và mạnh; − Từ p và q dễ dàng tính được: ; − Từ n rất khó tìm được p và q. Với việc giữ bí mật các tham số p, q thì khả năng tính được khóa mật (d) từ khóa công khai (e) và modulo n là rất khó thực hiện, nếu p, q được chọn đủ lớn và mạnh [3,4]. 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 cho nó và hệ mật RSA là một chứng minh thực tế cho tính khó giải của bài toán này. Trong ứng dụng thực tế, các tham số {p,q} của hệ mật RSA có thể chọn theo Chuẩn X9.31 [5] hay FIPS 186-3 [6] của Hoa Kỳ như sau: Chuẩn X9.31. Theo X9.31, tiêu chuẩn đối với các tham số {p,q} của hệ mật RSA bao gồm: - Độ dài modulo n (nlen) là: 1024+256s (s ≥ 0). - 2511+128s ≤ p, q ≤ 2511+128s (s ≥ 0). - |p – q| > 2412+128s (s ≥ 0). - Các ước nguyên tố của p±1 và q±1 (các số nguyên tố bổ trợ), ký hiệu là: p1, p2 và: q1, q2 phải thỏa mãn các thông số kỹ thuật được cho trong Bảng 1.1 dưới đây: Bảng 1: Tiêu chuẩn an toàn đối với các số nguyên tố bổ trợ nlen Độ dài tối thiểu của p1, p2 và Độ dài tối đa của p1, p2 và q1, q2 q1, q2 1024 + 256.s > 100 bit ≤ 120 bit Chuẩn FIPS 186-3. Theo FIPS 186-3, tiêu chuẩn đối với các tham số {p,q} của hệ mật RSA bao gồm: 94 TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI - 2511+128s ≤ p, q ≤ 2511+128s (s ≥ 0). - |p – q| > . - Các ước nguyên tố của p±1 và q±1 (các số nguyên tố bổ trợ), ký hiệu là: p1, p2 và q1, q2 phải thỏa mãn các thông số kỹ thuật được cho trong Bảng 2 dưới đây: Bảng 2: Tiêu chuẩn an toàn đối với các số nguyên tố bổ trợ Độ dài của Độ dài tối thiểu Độ dài tối đa của len(p1) + len(p2) modulo n của p1, p2, q1, q2 và len(q1) + len(q2) (nlen) Các số nguyên tố Các số nguyên tố xác xuất chứng minh được 1024 bit > 100 bit < 496 bit < 239 bit 2048 bit > 140 bit < 1007 bit < 494 bit 3072 bit > 170 bit < 1518 bit < 750 bit 2.2. Chữ ký số RSA 2.2.1. Sơ đồ chung của chữ ký số Một sơ đồ chữ ký số là bộ năm (P, A, K, S, V) thoả mãn các điều kiện dưới đây: - P là tập hữu hạn các thông báo có thể có. - A là tập hữu hạn các chữ ký có thể có. - K là tập tập hữu hạn các khoá. Mỗi khóa k ∈ K gồm hai thành phần k=(k1,k2) trong đó k1 là khóa bí mật dành cho việc ký, k2 là khóa công khai dành ch ...