CHƯƠNG 1. TỔNG QUAN VỀ VẤN ĐỀ NGHIÊN CỨU VÀ CƠ SỞ LÝ THUYẾT CỦA LUẬN ÁN Nhiệm vụ của chương là tiến hành khảo sát một số lược đồ chữ ký số trên trường hữu hạn ℤp và trên vành hữu hạn ℤn , chỉ ra một số điểm tồn tại trên các lược đồ đã khảo sát như là khoảng trống về học thuật, đồng thời xác định vấn đề nghiên cứu giải quyết những khoảng trống đã chỉ ra. Nội dung phần còn lại của chương trình bày một số cơ sở lý thuyết liên quan đến vấn đề nghiên cứu được đặt ra trong luận án và được sử dụng trong nội dung nghiên cứu các chương sau của luận án. Tổng quan và vấn đề nghiên cứu của luận án 1.
Tổng quan Trong lý thuyết số, khái niệm lớp các bài toán được cho là khó, bao gồm bài toán phân tích số, ký hiệu là FP, bài toán logarit rời rạc trên trường hữu hạn ℤp ký hiệu là DLPp , bài toán logarit rời rạc trên trên vành hữu hạn ℤn , ký hiệu DLP𝑛 , bài toán khai căn theo Modulo hợp số… Hiện nay, đa số các lược đồ chữ ký số đều có độ an toàn dựa trên tính khó giải của một hoặc hai trong số bài toán khó kể trên(gọi là bài toán cơ sở). Trong một lược đồ chữ ký số thì “độ khó” của việc giả mạo chữ ký được gọi là “độ an toàn” của nó. Như vậy nếu việc giả mạo chữ ký cần đến việc giải một bài toán khó nào đó thì lược đồ này được gọi là “có độ an toàn dựa trên tính khó giải của bài toán đó”, chẳng hạn lược đồ chữ ký số RSA có độ an toàn dựa trên tính khó giải của bài toán phân tích số 𝑛 và lược đồ DSA có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên trường ℤp. Luận án chủ yếu đề cập đến lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên trường hữu hạn ℤp , được đề cập trong các tài liệu tham khảo [13], [17], [18], [27-29], [32], [33], [38], [44], [46-52] và lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc luan an 19 trên vành ℤn đã được công bố trong các tài liệu tham khảo [1-6], [11], [14-16], [21], [36], [39], [40-42], [45].2 Một số lược đồ chữ ký số trên trường ℤp Nội dung phần này NCS sẽ khảo sát một số lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên trường ℤ𝐩 , chỉ ra một số điểm còn tồn tại trên các lược đồ chữ ký này.
Khảo sát đầu tiên được thực hiện với lược đồ ElGamal và một số biến thể của nó trên trường hữu hạn ℤp. Vào năm 1985, tác giả ElGamal đã đề xuất lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toàn logarít rời rạc trên trường ℤp (còn gọi là lược đồ chữ ký số ElGamal). Kể từ khi lược đồ chữ ký số ElGamal ra đời, nhiều lược đồ chữ ký số được phát triển dựa trên lược đồ này (gọi là các biến thể của lược đồ ElGamal), tiêu biểu là lược đồ chữ ký số Schnorr năm 1990 [17], [46]; lược đồ chữ ký số DSA năm 1994 [13], [29], [49], [50], [52]; lược đồ chữ ký số GOST R34.10-94 [27] của Liên bang Nga. Điểm tồn tại chung cho lược đồ chữ ký số ElGamal cùng các biến thể có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên trường ℤ𝑝 có chi phí tính toán để sinh chữ ký cao hơn các lược đồ cùng loại trên vành ℤ𝑛 , điều này được chứng minh trong bổ đề 2.3 (khi L(p) = L(q) và phép lũy thừa và phép nghịch đảo trên vành ℤ𝒏 với n=p.q có chi phí chỉ bằng 1/3 chi phí trên trường ℤ𝑝 với L(p)=L(n)); điểm tồn tại thứ hai là lược đồ chữ ký số ElGamal cùng các biến thể của nó được xây dựng trên trường ℤp phải đối mặt với nguy cơ tấn công bằng các thuật toán giải bài toán logarit rời rạc dựa vào cấp của phần tử sinh [20] khi mà hệ tham số của các lược đồ này không đạt tiêu chuẩn an toàn, chẳng hạn thuật toán Pohlig Hellman, thuật toán Rho của Pollard và thuật toán Index calculate; điểm thức ba là cấu trúc trường hữu hạn ℤp không che giấu được cấp của phần tử sinh, điều này dẫn đến nguy cơ mất an toàn trong những tính huống lộ khóa phiên hoặc trùng khóa phiên, khẳng định này được tham khảo trên các kết quả nghiên cứu liên quan được đề cập luan an 20 trong tài liệu tham khảo[21], [33], [48-52].
Để khắc phục những điểm tồn tại đã chỉ ra, các nhà khoa học đã nghiên cứu, cải tiến các lược đồ chữ ký số ElGamal cùng các biến thể của nó với nhiều mục đích khác nhau, cụ thể là mục đích nâng cao độ an toàn được thể hiện trong các kết quả nghiên cứu [48-52]; nâng cao tốc độ sinh chữ ký và xác nhận chữ ký trong một số kết quả nghiên cứu trong [18], [29]. Dong đã đề xuất một giải pháp cải tiến tốc độ cho lược đồ DSA [29]. Một kết quả nghiên cứu khác được công bố năm 2015, các tác giả H. Iwata đã cải tiến lược đồ DSA và lược đồ Schnorr chống lại sự mất an toàn trong tình huống dùng trùng khóa phiên [28]; năm 2010 nhóm tác giả Li Xiao-fei, Shen Xuan-jing và Chen Hai-peng đã đề xuất một lược đồ sửa đổi lược đồ nguyên thủy ElGamal bằng cách thêm vào thành phần ngẫu nhiên trong mỗi phiên truyền nhằm tăng thêm tính bảo mật cho lược đồ; trong kết quả nghiên cứu của mình tác giả bài báo [13], B.
Yang đã đề xuất phương pháp chống tấn công "IP Prefix Hijacking" liên quan đến lộ hoặc trùng khóa phiên; hoặc trong kết quả nghiên cứu của ba tác giả Z. Keke công bố năm 2012 [49] và kết quả nghiên cứu của nhóm tác giả Z. Hao công bố năm 2015 [50], chỉ ra lược đồ chữ ký DSA không an toàn với phương pháp tấn công "L3 cache time attack" là một kiểu tấn công kênh kề (Side chanel attack) được đề cập trong [5]. Cho đến nay, đã có nhiều công trình khoa học trong nước và trên thế giới được công bố nhằm cải tiến lược đồ ElGamal cùng các biến thể của nó, tuy nhiên cho đến nay chưa có kết quả nghiên cứu nào có thể thể khắc phục được triệt để những tồn tại trên các lược đồ chữ ký số này, đặc biệt là khắc phục vấn đề không thể che giấu cấp của phần tử sinh trên cấu trúc trường ℤp.
Một số lược đồ chữ ký số trên vành ℤn Vấn đề nghiên cứu đã đặt ra cho các nhà khoa học trong thiết kế lược đồ chữ ký là phải chọn một cấu trúc đại số phù hợp hơn cấu trúc trường ℤp , đảm luan an 21 bảo các lược đồ chữ ký được xây dựng trên đó chi phí tính toán thấp và đảm bảo an toàn hơn. Một trong các cấu trúc tập hợp được lựa chọn là cấu trúc vành ℤn và bài toán cơ sở là bài toán logarit rời rạc, bởi một số lý do sau: Thứ nhất, chi phí tính toán của thuật toán sinh chữ ký cho các lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên vành ℤn thấp hơn nhiều chi phí tính toán cho các lược đồ chữ ký số trên trường ℤp nhờ áp dụng định lý CRT (bổ đề 2.3) Thứ hai, lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên vành ℤn che giấu được cấp của phẩn tử sinh, được chứng minh trong một số kết quả nghiên cứu [1], [3], [21], [39], [41]. Một khi giữ được bí mật giá trị cấp của phần tử sinh 𝑔 (ký hiệu là Ordn g) thì lược đồ chữ ký số không bị mất an toàn trong tình huống lộ khóa phiên hoặc trùng khóa phiên, đồng thời không bị nguy cơ tấn công bằng các thuật toán giải bài toán logarit rời rạc dựa vào cấp của phần tử sinh 𝑔, như là thuật toán Rho của Pollard, thuật toán Pohlig Hellman và thuật toán Index calculate.■ Việc tìm cấp của phần tử sinh g ∈ ℤ∗𝑛 là tương đương với việc phân tích 𝑛 ra thừa số nguyên tố. Điều này có nghĩa là cấp của 𝑔 ∈ ℤ∗n có thể giữ được bí mật với độ an toàn tương đương với độ an toàn dựa trên tính khó giải của bài toán phân tích số modulo 𝑛 ra thừa số nguyên tố.■ Do vành hữu hạn ℤn có những ưu điểm như đã nêu ở trên, nên một số lược đồ chữ ký số hoặc một số lược đồ phân phối khóa được nghiên cứu và phát triển trên cấu trúc đại số này.
Tiêu biểu cho tác giả trong nước là Nguyễn Xuân Quỳnh năm 2002 [6], Hồ Ngọc Duy năm 2017 [1], Phạm Văn Hiệp năm 2018 [3], [4], [64], [65], [66], [67]. Bên cạnh đó còn có tác giả của những lược đồ chữ ký số trên thế giới, tiêu biểu là lược đồ xác lập khóa của Okamoto E. Girault scheme [34] năm 1991, lược đồ của Chik How Tan [16] năm 2003 và S. Gupta [39] vào luan an 22 năm 2017.
Các lược đồ chữ ký trên vành ℤn này đều đảm bảo tính đúng đắn và có tính an toàn được dựa trên một hoặc hai bài toán khó nào đó[15], [16], [34], [39], [40], [42], [45]. Khảo sát các lược đồ đã công bố cho thấy các lược đồ chữ ký số trên vành ℤn đều chưa trình bày cơ sở toán học sinh ra các tham số; đa số các lược đồ đều chưa có hệ hệ tiêu chuẩn tham số an toàn hoặc tác giả chưa định hướng cho người sử dụng nên sử dụng hệ tiêu chuẩn tham số nào của thế giới. Bên cạnh đó, có những lược đồ chữ ký đề xuất mà độ lớn cấp phần tử sinh xấp xỉ độ lớn của số modulo, chẳng hạn trong [39], hoặc một số nhà khoa học đã đưa ra độ lớn cấp phần tử sinh 256 bit [1], [41] mà không có lý giải tại sao. Mặt khác, nếu cấp phần tử sinh có độ lớn 256 bit mà sử dụng hàm băm an toàn hơn, như hàm băm SHA 512 sẽ dẫn đến giảm độ an toàn cho lược đồ.
Hơn nữa, trong lược đồ của Phạm Văn Hiệp [3] được cho là có độ an toàn dựa trên hai bài toán khó, đó là bài toán FP và DLPn , không có nghĩa là kẻ tấn công phải giải đồng thời hai bài toán khó này cùng một lúc như kết luận của nhóm nghiên cứu.