Bài toán: Tung đồng xu qua điện thoại

Bài viết hôm nay chúng ta sẽ tìm hiểu cách giải quyết vấn đề tung đồng xu qua cuộc gọi điện thoại hoặc tin nhắn sử dụng toán học (cụ thể hơn là mật mã) để đảm bảo không có ai gian lận nhé.

Có một cặp vợ chồng đang chuẩn bị thủ tục ly dị, vì sắp ly dị nên hai người không hề tin tưởng nhau. Hiện tại 2 người không muốn gặp mặt nhau, họ đã nghĩ ra 1 sáng kiến, đó là chồng sẽ tung đồng xu, nếu vợ đoán đúng kết quả tung đồng xu thì vợ sẽ thừa hưởng toàn bộ tài sản và ngược lại nếu sai thì người chồng sẽ thừa hưởng toàn bộ tài sản.

Vì là gọi điện thoại nên người chồng có thể gian lận để tạo lợi thế cho mình để nhận toàn bộ tài sản (ví dụ: chồng tung đồng xu ra mặt sấp, vợ đoán đúng nhưng anh chồng lại bảo, tôi vừa tung được mặt ngửa)

Liệu có cách nào để người chồng không thể gian lận hay không ?

Một số ký hiệu và thuật ngữ trong bài

Thuật ngữ

Ký hiệu

Trong bài viết này, tác giả trình bày 3 phương án khác nhau để tạo ra giao thức tung đồng xu qua điện thoại công bằng đó là:

Sử dụng hàm băm (sử dụng tính chất 1 chiều của hàm băm);

Sử dụng mật mã đối xứng (sử dụng tính chất sau: “khi không biết khóa mã hóa, không thể giải mã được thông tin”);

Sử dụng mật mã khóa công khai (độ khó dựa trên 2 bài toán: Tìm căn bậc nào đó theo modulo , và bài toán logarithm rời rạc (discrete logarithm)).

Chúng ta kí hiệu chung cho 2 người tham gia giao thức này là vợ là V, chồng là C.

Ký hiệu kết quả tung đồng xu mặt sấp là 0, mặt ngửa là 1 để thuận tiện trong việc trình bày và triển khai giao thức.

Sử dụng hàm băm

Ta ký hiệu hàm băm là , giao thức được mô tả như sau:

C tung đồng xu và nhận được , trong đó ;

C sinh ngẫu nhiên số ;

C tính giá trị sau đó gửi cho V;

V đoán và gửi đáp án của mình cho C;

C gửi cho V để thực hiện kiểm tra, V kiểm tra phương trình sau để biết mình đoán đúng hay không: nếu , vợ đoán đúng và ngược lại thì vợ đoán sai.

Đánh giá độ an toàn

Ví dụ

Trong ví dụ này, chúng ta sử dụng hàm băm MD5 (xem thêm tại [1]).

C tung đồng xu và nhận được (nhận được mặt ngửa);

C sinh ngẫu nhiên số ;

Ta có
C tính giá trị sau đó gửi cho V;

V đoán và gửi đáp án của mình cho C;

C gửi cho V số để thực hiện kiểm tra, V kiểm tra phương trình sau:

Vậy là V đã chiến thắng trong trò chơi may rủi này.

Độc giả có thể truy cập website này để tính toán hàm băm MD5

Sử dụng hệ mật mã đối xứng

Hệ mã hóa đối xứng đã phát triển mạnh mẽ trong những năm 1970 và 1980 khi các thuật toán mã hóa mới được đưa ra và trở thành các tiêu chuẩn. Chúng được cải tiến để đảm bảo tính bảo mật và hiệu suất của quá trình mã hóa, các tiêu chuẩn mã hóa đối xứng hiện đại đã đạt đến tiệm cận an toàn tuyệt đối nếu không biết chìa khóa mã hóa. Có thể kể đến 1 số tiêu chuẩn tiêu biểu như: AES, IDEA, A5, RC5, …

Trong các hệ mật mã đối xứng, theo thiết kế sẽ có 2 hàm là hàm mã hóa và hàm giải mã với khóa , chúng ta ký hiệu hàm mã hóa là hàm giải mã là . Giao thức được mô tả như sau:

C tung đồng xu và nhận được , trong đó ;

C sinh ngẫu nhiên số ;

C tính giá trị sau đó gửi cho V;

V đoán và gửi đáp án của mình cho C;

C gửi cho V để thực hiện kiểm tra, V kiểm tra phương trình sau để biết mình đoán đúng hay không: nếu , vợ đoán đúng và ngược lại thì vợ đoán sai.

Đánh giá độ an toàn

Sử dụng hệ mật mã khóa công khai

Các hệ mật mã khóa công được sinh ra để giải quyết vấn đề trao đổi khóa (Key exchange) hay mở rộng hơn đó chính là phân phối khóa (Key distribution). Sơ đồ trao đổi khóa đầu tiên được công bố lần đầu vào năm 1976, vào năm 1978, hệ mã hóa khóa công khai được sử dụng nhiều nhất được ra đời, đó chính là hệ mật mã khóa công khai RSA, độc giả có thể tham khảo bài viết tìm hiểu về RSA tại đây. Có thể kể đến một số hệ mật mã khóa công khai tiêu biểu như: RSA, Rabin, El-gamal, hệ mật mã trên đường cong Eliptic (Elliptic Curve Cryptography), …

☝

Trao đổi khóa (Key exchange) — là quá trình 2 người tham gia sử dụng mật mã khóa công khai để truyền khóa cho nhau một cách an toàn (ví dụ: RSA, …).
Thỏa thuận khóa (Key Agreement) — về cơ bản thỏa thuận khóa khá giống với trao đổi khóa, điểm khác biệt là sau ở bước cuối của quá trình, người tham gia nhận được khóa giống nhau để thực hiện mã hóa, và giải mã (ví dụ: giao thức Diffie-Hellman, …).
Phân phối khóa (Key distribution) — được sinh ra để giải quyết vấn đề có người muốn giao tiếp an toàn với nhau, số khóa được sinh ra cho người sẽ là

Để thuận tiện trong việc biểu diễn, chúng ta sẽ sử dụng hệ mật mã RSA để triển khai giao thức này (những hệ mật mã khóa công khai khác được triển khai tương tự). Giao thức được mô tả như sau:

C tung đồng xu và nhận được , trong đó ;

C sinh cặp khóa RSA sau: — khóa công khai, — khóa bí mật;

C sinh số ngẫu nhiên );

C tính giá trị sau đó gửi cho V ;

V đoán và gửi đáp án của mình cho C;

C gửi cho V số để thực hiện kiểm tra, V kiểm tra phương trình sau để biết mình đoán đúng hay không: nếu thì V đoán đúng và ngược lại thì V đoán sai.

☝

Lưu ý: ở bước 3 chúng ta phải sinh thêm giá trị vì chỉ nhận 2 giá trị là 0 và 1, nếu chúng ta mang 0 hoặc 1 mũ bao nhiêu thì chúng ta cũng chỉ nhận được 0 và 1 mà thôi, nên chúng ta cần thêm để đảm bảo được giao thức này được triển khai an toàn.

Đánh giá độ an toàn

Ví dụ

Toàn bộ giao thức được trình bày ở trên chính là 1 dạng của Bit commitment protocol

Bit commitment protocol — Là giao thức được triển khai giữa 2 bên (người tham gia) không tin cậy, tạm gọi là Alice và Bob, thực hiện cam kết (commit) giá trị nào đó (ở trong bài, cam kết chính là tung được đồng xu mặt sấp hay ngửa), Bob nhận được xác nhận (confirmation) rằng Alice đã cam kết đến một giá trị (không cần biết đến giá trị của ). (ở trong bài, confirmation chính kết quả sau quá trình mã hóa, được ký hiệu là ). Sau đó Alice và Bob sẽ cùng kiểm tra.

☝

Hiểu đơn giản chức năng của giao thức này là: Để cam kết với giá trị Alice viết lên một tờ giấy, đưa tờ giấy vào két sắt và khóa lại, sau đó Alice gửi két sắt cho Bob trong khi vẫn giữ thông tin đó, để mở cam kết, Alice gửi chìa khóa cho Bob, Bob sẽ mở két và biết được giá trị của . Vậy két sắt ở đây chính là các hàm mã hóa đã được triển khai.

Tổng kết

Trong bài viết này, tác giả trình bày về giao thức tung đồng xu qua điện thoại công bằng sử dụng hàm băm, hệ mật mã đối xứng, hệ mật mã khóa công khai. Giao thức này đảm bảo tính an toàn và công bằng trong việc gửi và xác nhận giá trị của đồng xu. Bài viết cũng đã đánh giá độ an toàn của giao thức và cung cấp ví dụ minh họa.