Chương 6. Một số giao thức bảo mật thông dụng khác
5. Bài toán xếp ba lô
Bài toán xếp ba lô (một số sách ghi là bài toán cái túi) là một bài toán tối ưu hóa tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét vừa vào trong một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi. Các bài toán tương tự thường xuất hiện trong nhiều vấn đề của toán ứng dụng như: Bài toán lựa chọn phương án kinh doanh, các bài toán tổ hợp, lý thuyết độ phức tạp tính toán, mật mã học.
Phát biểu của bài toán thực tế
Một người đi xa chỉ có một cái túi (ba lô) có sức chứa tối đa về trọng lượng là C. Người đó có n mặt hàng, mỗi loại có trọng lượng và giá trị khác nhau, vậy người đó nên bỏ vào ba lô những loại hàng nào và mỗi loại với số lượng bao nhiêu để đạt tổng giá trị cao nhất trong khả năng có thể mang đi được.
Trong các phát biểu sau đây ta gọi xj là số lượng đồ vật loại j, pj là đơn giá của đồ vật loại j còn ωj là giá trị của một đơn vị loại j.
Bài xếp ba lô dạng 0-1
Hạn chế về số đồ vật thuộc mỗi loại là 0 (không được chọn) và 1 (được chọn). Bài xếp ba lô 0-1 có thể được phát biểu toán học như sau:
Cực đại hóa dạng tuyến tính:
n j j j
p x
∑= 1
với các điều kiện ràng buộc:
n
j j j
j
w x c, x hoặc , j ,..., n
=
≤ = =
∑1
0 1 1
Bài xếp ba lô bị chặn
Hạn chế số đồ vật thuộc mỗi loại không được vượt quá một lượng nào đó. Bài xếp ba lô bị chặn có thể được phát biểu bằng toán học như sau:
Cực đại hóa:
n j j j
p x
∑= 1
Với các ràng buộc:
n
j j j j
j
w x c, x b , j ,..., n
=
≤ ≤ ≤ =
∑1
0 1
Bài xếp ba lô không bị chặn
Không có một hạn chế nào về số đồ vật mỗi loại.
Một trường hợp đặc biệt của bài toán này nhận được nhiều quan tâm, đó là bài toán với các tính chất:
- Là một bài toán quyết định - Là một bài toán 0/1
- Với mỗi đồ vật, chi phí bằng giá trị: C = V
Lưu ý rằng trong trường hợp đặc biệt này, bài toán tương đương với:
- Cho một tập các số nguyên, tồn tại hay không một tập con có tổng đúng bằng C?
- Hoặc nếu đồ vật được phép có chi phí âm và C được chọn bằng 0, bài toán có dạng: Cho trước một tập số nguyên, tồn tại hay không một tập con có tổng đúng bằng 0?
Trường hợp đặc biệt này được gọi là bài toán tổng các tập con (subset sum problem). Với một số lý do, trong ngành mật mã học, người ta thường dùng cụm từ "bài toán xếp ba lô" khi thực ra đang có ý nói về "bài toán tổng con".
Bài toán xếp ba lô thường được giải bằng quy hoạch động, tuy chưa có một thuật toán thời gian đa thức cho bài toán tổng quát. Cả bài xếp ba lô tổng quát và bài toán tổng con đều là các bài NP-khó, và điều này dẫn đến các cố gắng sử dụng tổng con làm cơ sở cho các hệ thống mật mã hóa khóa công khai, chẳng hạn Merkle-Hellman. Các cố gắng này thường dùng nhóm thay vì các số nguyên. Merkle-Hellman và một số thuật toán tương tự khác đã bị phá, do các bài toán tổng con cụ thể mà họ tạo ra thực ra lại giải được bằng các thuật toán thời gian đa thức.
Phiên bản bài toán quyết định của bài xếp ba lô được mô tả ở trên là NP-đầy đủ và trong thực tế là một trong 21 bài toán NP-đầy đủ của Karp.
Bài xếp ba lô dạng phân số
Với mỗi loại, có thể chọn một phần của nó (ví dụ: 1kg bánh mì có thể được cắt ra thành nhiều phần để bỏ vào ba lô)
Cách giải bằng quy hoạch động
Bài toán xếp ba lô có thể được giải trong thời gian giả-đa thức bằng quy hoạch động. Dưới đây là lời giải quy hoạch động cho bài toán xếp ba lô không bị chặn.
Gọi các chi phí là c1,..., cn và các giá trị tương ứng là v1,..., vn. Ta cần cực đại hóa tổng giá trị với điều kiện tổng chi phí không vượt quá C. Khi đó, với mỗi i ≤ C, đặt A(i) là giá trị lớn nhất có thể đạt được với tổng chi phí không vượt quá i. Rõ ràng, A(C) là đáp số của bài toán.
Định nghĩa A(i) một cách đệ quy như sau:
• A(0) = 0
• A(i) = max { vj + A(i − cj) | cj ≤ i }
Ở đây, giá trị lớn nhất của tập rỗng được lấy bằng 0. Tính dần các kết quả từ A(0) tới A(C), ta sẽ được lời giải. Do việc tính mỗi A(i) đòi hỏi xem xét n đồ vật (tất cả các giá trị này đã được tính từ trước), và có C giá trị của các A(i) cần tính, nên thời gian chạy của lời giải quy hoạch động là O(nC). Điều này không mâu thuẫn với thực tế rằng bài toán xếp ba lô là NP-đầy đủ, do C, không như n, không thuộc mức đa thức theo độ dài của đầu vào cho bài toán. Độ dài đầu vào bài toán tỉ lệ thuận với số bit trong C, chứ không tỉ lệ với chính C.
Một giải pháp quy hoạch động tương tự cho bài toán xếp ba lô 0-1 cũng chạy trong thời gian giả-đa thức. Cũng như trên, gọi các chi phí là c1,..., cn và các giá trị tương ứng là v1,..., vn. Ta cần cực đại hóa tổng giá trị với điều kiện tổng chi phí không vượt quá C. Định nghĩa một hàm đệ quy A(i, j) là giá trị lớn nhất có thể đạt được với chi phí không vượt quá j và sử dụng các đồ vật trong khoảng từ x1 tới xi.
A(i,j) được định nghĩa đệ quy như sau:
• A(0, j) = 0
• A(i, 0) = 0
• A(i, j) = A(i - 1, j) nếu ci > j
• A(i, j) = max(A(i - 1, j), vi + A(i - 1, j - ci)) nếu ci ≤ j
Để có lời giải, ta tính A(n, C). Để làm điều này, ta có thể dùng 1 bảng để lưu các tính toán trước đó. Cách giải này sẽ chạy trong thời gian O(nC) và không gian O(nC), tuy ta có thể giảm độ phức tạp không gian xuống O(C) bằng một số sửa đổi nhỏ.
Thuật toán tham lam
Martello và Toth (1990) đã đưa ra một thuật toán gần đúng kiểu tham lam (greedy approximation algorithm) để giải bài toán xếp ba lô.
Giải thuật này sắp xếp các đồ vật theo thứ tự giảm dần về giá trị, sau đó theo thứ tự đó xếp các đồ vật vào ba lô cho đến khi không cho thêm được đồ vật nào vào nữa.
Phụ lục 3
THÔNG TƯ SỐ 09/2011/TT-BCT
NGÀY 30/3/2011 CỦA BỘ CÔNG THƯƠNG
Quy định về việc quản lý, sử dụng chữ ký số, chứng thư số và dịch vụ chứng thực chữ ký số của bộ công thương
BỘ TRƯỞNG BỘ CÔNG THƯƠNG
- Căn cứ Nghị định số 189/2007/NĐ-CP ngày 27 tháng 12 năm 2007 của Chính phủ quy định chức năng, nhiệm vụ, quyền hạn và cơ cấu tổ chức của Bộ Công thương; Căn cứ Nghị quyết 59/NQ-CP về việc đơn giản hóa thủ tục hành chính thuộc phạm vi chức năng quản lý của Bộ Công thương;
- Căn cứ Nghị định số 26/2007/NĐ-CP ngày 15 tháng 02 năm 2007 của Chính phủ quy định chi tiết thi hành Luật Giao dịch điện tử về chữ ký số và dịch vụ chứng thực chữ ký số; Căn cứ Nghị định số 64/2007/NĐ-CP ngày 10 tháng 4 năm 2007 của Chính phủ quy định về ứng dụng công nghệ thông tin trong hoạt động của cơ quan nhà nước;
- Bộ trưởng Bộ Công thương quy định về việc quản lý, sử dụng chữ ký số, chứng thư số và dịch vụ chứng thực chữ ký số của Bộ Công thương như sau:
Chương I. QUY ĐỊNH CHUNG Điều 1. Phạm vi điều chỉnh
Thông tư này quy định việc quản lý, sử dụng chữ ký số, chứng thư số và dịch vụ chứng thực chữ ký số trong giao dịch điện tử của Bộ Công thương.
Điều 2. Đối tượng áp dụng
1. Tổ chức, cá nhân thuộc Bộ Công thương, Sở Công thương các tỉnh, thành phố trực thuộc Trung ương.
2. Tổ chức, cá nhân khác lựa chọn sử dụng dịch vụ chữ ký số của Bộ Công thương trong các hoạt động giao dịch điện tử do Bộ Công thương tổ chức.
Điều 3. Giải thích từ ngữ: Trong Thông tư này, các từ ngữ dưới đây được hiểu như sau:
1. “Chứng thư số” là một dạng chứng thư điện tử do Tổ chức cung cấp dịch vụ chữ ký số của Bộ Công thương cấp.
2. “Chữ ký số” là một dạng chữ ký điện tử được tạo ra bằng sự biến đổi một thông điệp dữ liệu sử dụng hệ thống mật mã không đối xứng theo đó người có được thông điệp dữ liệu ban đầu và khóa công khai của người ký có thể xác định được chính xác:
a) Việc biến đổi nêu trên được tạo ra bằng đúng khóa bí mật tương ứng với khóa công khai trong cùng một cặp khóa;
b) Sự toàn vẹn nội dung của thông điệp dữ liệu kể từ khi thực hiện việc biến đổi nêu trên.
3. “Dịch vụ chứng thực chữ ký số” là một loại hình dịch vụ do Tổ chức cung cấp dịch vụ chữ ký số của Bộ Công thương quản lý. Dịch vụ chứng thực chữ ký số bao gồm:
a) Tạo cặp khóa bao gồm khóa công khai và khóa bí mật cho thuê bao;
b) Cấp, gia hạn, tạm dừng, phục hồi và thu hồi chứng thư số của thuê bao;
c) Duy trì trực tuyến cơ sở dữ liệu về chứng thư số;
d) Những dịch vụ khác có liên quan theo quy định của Nghị định số 26/2007/NĐ-CP ngày 15 tháng 02 năm 2007 của Chính phủ quy định chi tiết thi hành Luật Giao dịch điện tử về chữ ký số và dịch vụ chứng thực chữ ký số (gọi tắt là Nghị định chữ ký số).
4. “Ký số” là việc đưa khóa bí mật vào một chương trình phần mềm để tự động tạo và gắn chữ ký số vào thông điệp dữ liệu.
5. “Người ký” là thuê bao dùng đúng khóa bí mật của mình để ký số vào một thông điệp dữ liệu.
6. “Người nhận” là tổ chức, cá nhân nhận được thông điệp dữ liệu được ký số bởi người ký, sử dụng chứng thư số của người ký đó để kiểm tra chữ ký số trong thông điệp dữ liệu nhận được và tiến hành các hoạt động, giao dịch có liên quan.
7. “Thuê bao” là tổ chức, cá nhân quy định tại Điều 2 Thông tư này; được Tổ chức cung cấp dịch vụ chữ ký số của Bộ Công thương cấp chứng thư số; chấp nhận chứng thư số và giữ khóa bí mật tương ứng với khóa công khai ghi trên chứng thư số được cấp.
8. “Tổ chức quản lý thuê bao” là các đơn vị thuộc Bộ Công thương, hoặc các tổ chức khác đề nghị cấp chứng thư số cho tổ chức, cá nhân thuộc tổ chức mình và chịu trách nhiệm theo quy định của pháp luật về quản lý tổ chức, cá nhân đó.
9. “Giao dịch điện tử của Bộ Công thương” là các hoạt động, nghiệp vụ được tiến hành bằng phương thức điện tử của Bộ Công thương.
Điều 4. Tổ chức cung cấp dịch vụ chữ ký số của Bộ Công thương Tổ chức cung cấp dịch vụ chữ ký số của Bộ Công thương, do Cục Thương mại điện tử và Công nghệ thông tin quản lý, điều hành và là tổ chức duy nhất của Bộ Công thương cung cấp dịch vụ chứng thực chữ ký số.
Điều 5. Chứng thư số
1. Nội dung chứng thư số: Chứng thư số do Tổ chức cung cấp dịch vụ chữ ký số của Bộ Công thương quản lý phải bao gồm các nội dung sau:
a) Tên tổ chức cung cấp dịch vụ chữ ký số;
b) Tên thuê bao;
c) Tên tổ chức quản lý thuê bao;
d) Số hiệu của chứng thư số;
đ) Thời hạn có hiệu lực của chứng thư số;
e) Khóa công khai của thuê bao;
g) Chữ ký số của tổ chức cung cấp dịch vụ chữ ký số;
h) Các hạn chế về mục đích, phạm vi sử dụng của chứng thư số;
i) Các hạn chế về trách nhiệm pháp lý của Tổ chức cung cấp dịch vụ chữ ký số;
k) Các thông tin khác cho mục đích quản lý, sử dụng, an toàn, bảo mật do Tổ chức cung cấp dịch vụ chữ ký số quy định.
2. Thời gian có hiệu lực của chứng thư số: Không quá 05 (năm) năm đối với chứng thư số của thuê bao.
Chương II. CHỨC NĂNG, NHIỆM VỤ CỦA TỔ CHỨC CUNG CẤP DỊCH VỤ CHỮ KÝ SỐ, QUYỀN VÀ NGHĨA VỤ CỦA CÁC ĐỐI TƯỢNG SỬ DỤNG DỊCH VỤ CHỮ KÝ SỐ Điều 6. Chức năng, nhiệm vụ của Tổ chức cung cấp dịch vụ chữ ký số
1. Quản lý việc cấp, gia hạn, tạm dừng, thu hồi, khôi phục chứng thư số và thay đổi cặp khóa cho thuê bao khi có yêu cầu. Hình thành và phát triển dịch vụ bảo đảm an toàn và an ninh thông tin; cung cấp dịch vụ chữ ký số.
2. Quản lý, vận hành hệ thống trang thiết bị kỹ thuật cung cấp dịch vụ chứng thực chữ ký số của Bộ Công thương, nghiên cứu, nâng cấp, đảm bảo duy trì hoạt động cung cấp dịch vụ chứng thực chữ ký số của Bộ Công thương an toàn, liên tục. Thử nghiệm và đề xuất ứng dụng các công nghệ mới để đảm bảo an ninh, an toàn thông tin phục vụ giao dịch điện tử.
3. Lưu trữ đầy đủ, chính xác và cập nhật thông tin của thuê bao phục vụ việc quản lý chứng thư số trong suốt thời gian chứng thư số
có hiệu lực. Trong trường hợp chứng thư bị thu hồi thì phải lưu trữ các thông tin chứng thư số của thuê bao trong thời hạn ít nhất 05 năm kể từ khi chứng thư số bị thu hồi.
4. Tổ chức cung cấp dịch vụ chữ ký số có chức năng chứng thực các chữ ký số lưu hành trên các văn bản, tài liệu điện tử và trong các giao dịch điện tử.
5. Hướng dẫn các tổ chức quản lý thuê bao, thuê bao thực hiện đúng các quy định tại Thông tư này.
Điều 7. Quyền và nghĩa vụ của tổ chức quản lý thuê bao
1. Được cung cấp thông tin hướng dẫn về trình tự, thủ tục cấp phát, quản lý và sử dụng chứng thư số.
2. Được yêu cầu Tổ chức cung cấp dịch vụ chữ ký số cấp, gia hạn, tạm dừng, khôi phục, thu hồi chứng thư số hoặc thay đổi cặp khóa cho các thuê bao do mình quản lý.
3. Chịu trách nhiệm về tính chính xác của các thông tin trên giấy đề nghị cấp, gia hạn, tạm dừng, khôi phục, thu hồi chứng thư số và thay đổi cặp khóa của thuê bao do mình quản lý.
4. Hướng dẫn, kiểm tra các thuê bao thuộc tổ chức mình quản lý, sử dụng chứng thư số và khóa bí mật theo đúng các quy định tại Thông tư này.
5. Thông báo kịp thời bằng văn bản cho Tổ chức cung cấp dịch vụ chữ ký số tạm dừng hoặc thu hồi chứng thư số của thuê bao trong các trường hợp quy định tại Điều 15 Thông tư này.
Điều 8. Quyền và nghĩa vụ của thuê bao
1. Được cung cấp thông tin hướng dẫn về trình tự, thủ tục cấp phát, quản lý và sử dụng chứng thư số.
2. Thông qua tổ chức quản lý thuê bao của mình để đề nghị cấp, gia hạn, tạm dừng, khôi phục, thu hồi chứng thư số hoặc thay đổi cặp khóa.
3. Thuê bao có thể trực tiếp gửi văn bản đề nghị Tổ chức cung cấp dịch vụ chữ ký số tạm dừng chứng thư số của mình và phải chịu trách nhiệm trước pháp luật về đề nghị đó.
4. Sử dụng chứng thư số đúng mục đích đã đăng ký.
5. Bảo quản và sử dụng khóa bí mật, các dữ liệu trong thiết bị lưu giữ khóa bí mật theo chế độ “Mật”.
6. Thông báo kịp thời cho Tổ chức cung cấp dịch vụ chữ ký số và tổ chức quản lý thuê bao của mình trong trường hợp phát hiện hoặc nghi ngờ chứng thư số, khóa bí mật không còn an toàn.
7. Tuân thủ các quy định khác của pháp luật về quản lý và sử dụng chứng thư số.
Điều 9. Nghĩa vụ của người nhận
1. Trước khi chấp nhận chữ ký số của người ký, người nhận phải kiểm tra những thông tin sau:
a) Hiệu lực, phạm vi sử dụng, giới hạn trách nhiệm chứng thư số của người ký và chữ ký số của Tổ chức cung cấp dịch vụ chữ ký số;
b) Chữ ký số phải được tạo bởi khóa bí mật ứng với khóa công khai trên chứng thư số của người ký.
2. Người nhận phải chịu mọi thiệt hại xảy ra trong trường hợp sau:
a) Không tuân thủ các quy định tại khoản 1 Điều này;
b) Đã biết hoặc được thông báo về sự không còn tin cậy của chứng thư số và khóa bí mật của người ký.
Chương III. DỊCH VỤ CHỨNG THỰC CHỮ KÝ SỐ
Điều 10. Đăng ký sử dụng dịch vụ chứng thực chữ ký số
1. Tổ chức, cá nhân tham gia sử dụng dịch vụ chứng thực chữ ký số của Bộ Công thương đăng ký một trong các thủ tục sau:
a) Cấp chứng thư số (quy định tại Điều 12 của Thông tư này);
b) Gia hạn chứng thư số (quy định tại Điều 13 của Thông tư này);
c) Thay đổi cặp khóa (quy định tại Điều 14 của Thông tư này);
d) Tạm dừng, thu hồi chứng thư số (quy định tại Điều 15 của Thông tư này);
đ) Khôi phục chứng thư số (quy định tại Điều 16 của Thông tư này).
2. Tổ chức, cá nhân có thể lựa chọn đăng ký qua mạng Internet tại địa chỉ http://www.vsign.vn hoặc đăng ký tại Trụ sở của Bộ Công thương - Cục Thương mại điện tử và Công nghệ thông tin, 25 Ngô Quyền, Hoàn Kiếm, Hà Nội.
Điều 11. Trình tự đăng ký sử dụng dịch vụ chứng thực chữ ký số qua mạng Internet
1. Tổ chức, cá nhân phải khai báo các thông tin vào phần mềm do Bộ Công thương cung cấp và gửi dữ liệu điện tử về Bộ Công thương.
Hồ sơ nộp qua mạng Internet bao gồm:
a) Bản khai điện tử yêu cầu đăng ký sử dụng dịch vụ chứng thực chữ ký số của tổ chức, cá nhân;
b) Bản scan từ bản gốc quyết định thành lập của tổ chức quản lý thuê bao đối với hồ sơ đề nghị cấp chứng thư số lần đầu (không áp dụng đối với các đơn vị thuộc Bộ Công thương).
2. Các cán bộ tiếp nhận hồ sơ và tiến hành xem xét thông tin khai báo qua mạng Internet và thông báo kết quả kiểm tra qua mạng Internet về cho các tổ chức, cá nhân. Kết quả kiểm tra có thể thuộc một trong hai trường hợp sau:
a) Đồng ý qua mạng Internet trong trường hợp các thông tin khai báo qua mạng Internet phù hợp và hợp lệ;
b) Đề nghị tổ chức, cá nhân sửa đổi, bổ sung thông tin.