Một lược đồ chữ ký xây dựng 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ố

Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 57
MỘT LƯỢC ĐỒ CHỮ KÝ XÂY DỰNG 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Ố 
Nguyễn Vĩnh Thái1, Lưu Hồng Dũng2* 
Tóm tắt: Bài báo đề xuất một lược đồ chữ ký số xây dựng 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 trên Zp với phân tích một số nguyên 
lớn ra các thừa số nguyên tố. Vì thế, thuật toán chữ ký mới đề xuất ở đây có thể đáp 
ứng được các ứng dụng có yêu cầu cao về độ an toàn trong thực tế. 
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 ĐỀ 
Nâng cao độ an toàn cho các thuật toán mật mã khóa công khai và chữ k ý số 
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 [1-8]. Trong bài báo này, 
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ả đề xuất một lược đồ chữ ký số được xây dựng 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 trên Zp (bài toán logarit 
rời rạc) 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ố (bài toán 
phân tích số). Ngoài việc nâng cao độ an toàn cho thuật toán như [1-8], lược đồ 
chữ ký được đề xuất ở đây còn cho phép các thực thể cuối (người ký) trong cùng 
một hệ thống có thể sử dụng chung một bộ tham số (tham số miền) do nhà cung 
cấp dịch vụ tạo ra. Do đó, có thể sử dụng lược đồ mới đề xuất trong việc xây dựng 
các giao thức mật mã nhằm chống lại các dạng tấn công giả mạo rất hiệu quả. 
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ố. 
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 [10], 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ông nghệ thông tin 
N. V. Thái, L. H. Dũng, “Một lược đồ chữ ký xây dựng trên tính khó  và phân tích số.” 58 
đượ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 [9] của 
Hoa Kỳ cho hệ mật RSA. 
2.2. Bài toán logarit rời rạc trên  
Cho cặp số nguyên dương (, ) với  là số nguyên tố, còn  là một phần tử 
của nhóm 
∗ . Khi đó, bài toán logarit rời rạc trên Z hay còn gọi là bài toán 
DLP(,) đượ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: 
   =  
Giải thuật cho bài toán DLP(,) có thể được viết như một thuật toán tính hàm 
DLP(,)(. ) với biến đầu vào là , còn giá trị hàm là  của phương trình sau: 
 = DLP(,)() 
Bài toán DLP(,) là cơ sở để xây dựng nên hệ mật ElGamal [11]. Hiện tại chưa 
có giải thuật hiệu quả (thời gian đa thức hay đa thức xác suất) cho DLP(,) và độ 
an toàn của thuật toán DSA trong chuẩn chữ ký số DSS của Hoa Kỳ là một minh 
chứng thực tế cho tính khó giải của bài toán này. 
3. XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ 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Ố 
3.1. Thuật toán hình thành tham số và khóa 
Các tham số hệ thống hay tham số miền được nhà cung cấp dịch vụ chứng thực 
số hình thành bằng thuật toán như sau: 
a) Thuật toán 1. Hình thành các tham số hệ thống 
Input: ,  - độ dài (tính theo bit) của các số nguyên tố , . 
Output: , , . 
Bước 1. Chọn cặp số ,  nguyên tố với: 
() = , () =  sao cho |( − 1) 
Bước 2. Chọn  là phần tử sinh của nhóm 
∗ theo: 
 = 

   , với  ∈ (1, ) 
Chú thích: (. ): hàm tính độ dài (theo bit) của một số. 
Mỗi thực thể cuối/người sử dụng trong hệ thống hình thành khóa của mình bằng 
thuật toán như sau: 
b) Thuật toán 2. Hình thành khóa 
Input: , , , ,  - độ dài (tính theo bit) của các số nguyên tố , . 
Output: , , , . 
Bước 1. Chọn cặp số ,  là các nguyên tố với: 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 59
() = , () =  
Bước 2. Tính  = . , nếu  ≤  thì thực hiện lại Bước 1. 
Bước 3. Tính () = ( − 1). ( − 1) 
Bước 4. Chọn giá trị bí mật thứ nhất  trong khoảng (1, ) 
Bước 5. Tính giá trị y theo: 
 = ()()

   (1) 
Kiểm tra nếu:  ≥ () hoặc: gcd (, ()) ≠ 1 thì thực hiện lại từ Bước 4. 
Bước 6. Tính giá trị bí mật thứ hai  theo: 
 = 
  () (2) 
Bước 7. Chọn hàm băm : {0,1}∗ →  với  < ℎ <  
Chú thích: 
- p, q, g: Tham số hệ thống (tham số miền). 
- x1, x2: Khóa bí mật. 
- y, n: Khóa công khai. 
3.2. Thuật toán ký 
a) Thuật toán 3: Sinh chữ ký 
Input: p, q , g, (), ,   - bản tin cần ký 
 Output: , - chữ ký 
Bước 1. Chọn ngẫu nhiên giá trị  trong khoảng (1, ) 
Bước 2. Tính giá trị: 
 =    (3) 
Bước 3. Tính thành phần thứ nhất  của chữ ký theo: 
 = (‖)   (4) 
Bước 4. Tính thành phần thứ hai  của chữ ký theo: 
 = ( × ( + )  )
   (5) 
Chú thích: toán tử "||": ph