-- © NQH (
Trong bài về các chương
trình đẹp xấu, vân vân, tôi có nhắc đến
các chương trình C được rắc rối hóa
(obfuscated C code) và cả một cuộc
thi quốc tế hàng năm cho các chương trình này.
Sau đây là một ví dụ:
#include <stdio.h> int O,o,i;char*I="";main(l){O&=l&1?*I:~*I,*I++||(l=2*getchar(),i+=O>8\?o:O?0:o+1,o=O>9,O=-1,I="t8B~pq`",l>0)?main(l/2):printf("%d\n",--i);}
Bạn thử bỏ vài phút nghĩ xem
chương trình trên làm gì? Tôi chọn ví
dụ này vì nó ngắn. Các ví dụ khác trông “ghê
gớm” hơn nhiều: ví
dụ 1, ví dụ 2,
ví dụ 3.
Thế các chương trình loại này
chỉ dùng để đố nhau cho vui, hay có ứng
dụng gì khác?
Thử tưởng tượng ta tìm được
một phương thức nào đó để viết
một chương trình O làm công việc như sau: cho
một chương trình P bất kỳ, O sẽ biến P
thành chương trình O(P) với chức
năng hệt như P, chỉ khác ở chỗ là
đọc O(P) ta không thể hiểu được logic
của nó, và vì thế ta không biết P thật sự
chạy như thế nào. [Kể cả là đọc
bằng máy tính hay đọc bằng mắt thường!]
Một chương trình O như vậy có
rất nhiều ứng dụng trong mật mã hóa, đánh
dấu mờ (watermark) phần mềm, bảo vệ
phần mềm (software protection), vân vân.
Ví dụ tôi có một giải thuật tân
kỳ nào đó và tôi muốn bán cho người khác
để họ dùng giải thuật này trong một chương
trình lớn. Tôi viết giải thuật này thành
một đoạn mã gọi là P, sau đó tôi gửi O(P) cho người mua và họ có thể dùng
O(P) trực tiếp mà tôi không bị tiết lộ giải
thuật này. Nói chung, O có thể dùng
để chống reverse-engineering. Đây là
ứng dụng bảo vệ phần mềm của O.
Đánh dấu mờ phần mềm (wartermarking
software) là một ứng dụng hay nếu ta có thể
thực sự viết O. Ý nghĩa căn bản của cái
gọi là “đánh dấu mờ” như sau:
Những điều trên có khả năng hiện thực hóa được nếu ta có bộ rắc rối hóa O. Ta bỏ vào trong P một đoạn mã C(G) nào đó để nhận dạng khách hàng G. (C(G) không làm gì cả, chỉ dùng để nhận dạng G.) Sau đó ta đưa cho khách hàng chương trình O(P). Chương trình O(P) giống hệt P+C(G), nhưng đã bị rắc rối đến mức khách hàng không thể hiểu được logic của nó, và vì thế không thể bỏ C(G) ra khỏi nó được. Dĩ nhiên còn nhiều chi tiết kỹ thuật và lý thuyết cần dùng cho việc này, nhưng về mặt trực quan thì có khả năng điều này có thể hiện thực hóa được nếu ta có O.
Hệ thống mật mã khóa công cộng (public key
crypto-system, hay PKC) là ý tưởng đột phá
của ngành mật mã học (cryptography). Các PKC như RSA
hiện nay đóng vai trò thiết yếu trong các hoạt
động cần bảo mật máy tính như
thương mại điện tử (e-commerce), chữ ký
điện tử (digital signature),
vân vân. Whitfield
Diffie, Martin Hellman,
và Ralph Merkle có thể
được coi là cha đẻ của ý tưởng mật
mã hóa không cần bí mật này, mặc dù tổ
chức GCHQ của Anh nói
rằng họ có
ý tưởng này trước đó vài năm, nhưng
không đăng báo vì là bí mật quốc gia.
Bài báo đầu tiên về
đề tài này của Diffie và Hellman đăng năm 1976
(W. Diffie and M. Hellman. New Directions in Cryptography.
IEEE Trans. Info. Theory 22(6): 644-654 (1976)). Tuy
nhiên họ đã trình bày ý tưởng này ở một
hội nghị vào tháng 6 năm 1975.
“Mật mã hóa không cần bí mật” nghe có
vẻ nghịch lý. Chính vì thế mà ý
tưởng PKC là một đột phá của thế
kỷ 20 trong ngành mật mã học. Trước khi có
ý tưởng PKC, để gửi hay lưu trữ
một tài liệu mật nào đó, ta cần một khóa bí
mật (secret key - còn gọi là khóa riêng - private key).
Khi mật mã hóa tài liệu, ta dùng khóa bí
mật. Khi giải mã tài liệu, ta
cũng cần nó. Mức độ
bảo mật của hệ thống bằng với
mức độ bảo mật của khóa này, và trong
chừng mực nào đó, mức độ bảo mật
của giải thuật mã hóa và giải mã. Hiển nhiên là một giải thuật tốt thì
có nhiều người cần dùng, và vì thế ta chỉ có
thể giữ bí mật cái khóa riêng thôi, còn giải
thuật thì không phải là bí mật.
Khó khăn của hệ thống mật mã
khóa riêng (private key crypto-system) kiểu này nằm ở
việc phân phối khóa riêng. Nếu một
người ở Mỹ muốn gửi tài liệu bí
mật cho người ở Việt
Ý tưởng của một hệ
thống PKC như sau. Người
nhận có một cặp khóa D (bí mật) và E
(công cộng). Người nhận cho thiên hạ
biết khóa E. Để đơn giản, bạn có
thể hiểu E như một hàm số hay một
chương trình mà cho một thông điệp M thì E(M) là thông điệp M đã
được mật mã hóa. Dĩ nhiên việc giải mã
ra M từ E(M) là cực kỳ khó,
trừ khi ta có D. Ta chỉ cần D(E(M)) = M
với mọi M là xong. (Chú ý rằng cả E
và D đều có thể xem như các chương trình
máy tính. E là chương trình công
cộng, còn D là chương trình bí mật.)
Vậy PKC thì liên quan gì đến rắc
rối hóa chương trình?
Với bộ rắc rối hóa
chương trình O, ta có thể biến một hệ
thống mật mã khóa riêng thành hệ thống mật mã
khóa công cộng. Hệ thống mật mã khóa riêng có
thể được mô tả như sau: bên gửi và bên
nhận dùng chung một khóa bí mật K cùng với một
giải thuật mã hóa E và giải mã D. Gọi EK là chương trình mã hóa dùng E
với khóa K, và DK là
chương trình giải mã dùng D với khóa K. Để mã
hóa một thông điệp M thì bên gửi sẽ gửi EK(M), và
bên nhận giải mã với DK(EK(M)) = M.
Như ta đã nói trong các bài trước,
việc làm thế nào để phân phối và đồng ý
với khóa K là vấn đề khó giải quyết
của hệ thống mật mã khóa riêng. Với
bộ rắc rối hóa O, bên nhận có thể cho mọi
người biết O(EK). Ai muốn gửi thông
điệp M thì chỉ cần gửi O(EK)(M) là xong. Nhờ có O, không
thể đoán được K từ O(EK).
Cho đến đây, ta vẫn chưa định
nghĩa rõ ràng thế nào là một bộ rắc rối hóa
chương trình bằng toán học. Bộ
rắc rối hóa phải thỏa mãn những tính chất
gì thì các ứng dụng nêu trên mới có thể thành
hiện thực được? Tệ
hơn nữa, nhỡ khi không tồn tại một bộ
rắc rối hóa như ta mong muốn thì sao? Làm sao chứng minh được điều này?
Về mặt trực quan, một chương trình P sau
khi được rắc rối hóa thành O(P)
thì ta không thể hiểu được logic của O(P)
nữa. Làm thế nào để mô tả
điều này về mặt toán học?
Một bài báo của Barak,
Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, và Yang nghiên cứu
định nghĩa như sau. Tôi chỉ
mô tả lại đây ý tưởng chính đằng sau
định nghĩa của họ. Định
nghĩa cụ thể bằng toán học bạn có thể
đọc trực tiếp.
Nếu O(P) cực kỳ khó
hiểu, thì có O(P) cũng không khác gì có P như một
hộp đen (blackbox). Hộp đen ở đây
được hiểu là ta không biết P hoạt
động thế nào, chỉ biết rằng cho bất
kỳ input x nào thì ta biết output P(x) tương ứng
của chương trình P, nhưng không có thông tin gì khác
về việc làm thế nào mà P tính được P(x). Ví
dụ, người ta có thể bán cho bạn một cái máy
mà ta gõ vào tiếng Việt thì máy dịch sang tiếng Anh.
Giả sử bạn không bao giờ mở máy ra xem thì
bạn có truy cập theo kiểu hộp
đen đến cái giải thuật dịch đấy.
Nếu P là giải thuật dịch, việc bạn có O(P) cũng chẳng hơn gì có cái máy dịch
không được tháo ra, dù O(P) vẫn là mã nguồn
của P (chỉ bị rắc rối hóa đi thôi).
Cụ thể hơn về mặt toán học, thì O là
bộ rắc rối hóa tốt nếu những gì ta tính
toán được hay suy ra được từ O(P) cũng y như những gì ta tính toán
được hay suy ra được từ truy cập
kiểu hộp đen đến P.
Nếu ta chấp nhận
định nghĩa này của bộ rắc rối hóa
(định nghĩa có thể hơi mạnh quá), thì các tác
giả bài báo trên chứng minh được rằng
tồn tại một họ F các hàm số không
thể rắc rối hóa được theo
nghĩa như sau. Tồn tại một thuộc
tính p: F –> {0,1} của các hàm
số này thỏa mãn tính chất sau đây:
Có lẽ cần giải thích chi
tiết hơn một chút. Giả sử tồn
tại một bộ rắc rối hóa O. Nếu O
là bộ rắc rối hóa tốt thì, theo định
nghĩa, nếu ta chọn một hàm f bất kỳ
từ họ F thì việc có O(f)
cũng không hơn gì việc có truy cập kiểu hộp
đen đến f. Gọi Q = O(f). Theo tính
chất (1) thì ta có thể tính p(f)
một cách hiệu quả. Theo tính chất (2) thì ta không tính
được p(f)
một cách hiệu quả nếu chỉ có truy cập
kiểu hộp đen đến f. Như vậy rõ
ràng là O(f) chứa nhiều “thông tin” (trong trường
hợp này là thuộc tính p của f) hơn là cái
hộp đen tính f. Nói cách khác, O đã không hoàn
toàn rắc rối hóa f.
Vài hướng nghiên cứu tiếp:
-- © NQH (