Nhưng còn việc giải mã thì sao?

Đề bài cho biết cách mã hóa nhưng không hề nói cơ chế giải mã; tìm ra cơ chế đó chính là một phần của bài. Vì đây là bài ở Vòng loại, áp lực thời gian và tính cạnh tranh thấp hơn đôi chút, nên ta có thêm thời gian để suy nghĩ hệ mật mã này phải được dùng thế nào.

Giả sử Cameron và Jamie thuộc đội Code Jam, đều biết danh sách bí mật gồm 26 số nguyên tố, và Cameron vừa gửi bản mã cho Jamie. Mỗi giá trị bản mã là tích của hai số trong danh sách, nên Jamie có thể thử chia nó cho từng số nguyên tố đã biết để tìm hai thừa số. Lưu ý một giá trị có thể là bình phương của một số nguyên tố nếu hai chữ liên tiếp trong bản rõ giống nhau.

Sau khi phân tích mọi giá trị, Jamie khôi phục bản rõ thế nào? Ta có thể cho rằng chữ thứ hai ứng với số nguyên tố xuất hiện trong cả giá trị bản mã thứ nhất lẫn thứ hai; chữ thứ ba ứng với thừa số chung của giá trị thứ hai và thứ ba; cứ thế. Hai thừa số còn lại ở đầu và cuối cho chữ đầu và chữ cuối.

Cách đó gần đúng, nhưng có một phiền toái đáng kể. Nếu bản rõ bắt đầu như ABABA..., bốn giá trị bản mã đầu đều bằng nhau vì đều là tích của hai số ứng với A và B. Đặc biệt, đầu chuỗi BABAB... trông hoàn toàn giống đầu chuỗi ABABA.... May thay, kiểu mẫu này chắc chắn kết thúc ở đâu đó: cuối cùng hoặc có hai chữ giống nhau liên tiếp, hoặc — vì bản rõ dùng hơn hai chữ khác nhau — có ba chữ liên tiếp khác nhau. Ngay khi một trong hai điều xảy ra, ta có một “điểm đột nhập”, biết thừa số nào của một giá trị thuộc về chữ nào, rồi có thể “kéo khóa” bản rõ theo cả hai hướng.

Chẳng hạn, nếu bản rõ bắt đầu bằng ABABAABAB, bốn giá trị đầu giống nhau. Giá trị thứ năm là bình phương số nguyên tố của A, nên biết chữ thứ năm và thứ sáu đều là A. Từ đó, chữ thứ tư là giá trị bản mã thứ tư chia cho số của A; chữ thứ ba là giá trị thứ ba chia cho số của B; và tiếp tục ngược về đầu. Theo chiều xuôi, chữ thứ bảy là giá trị thứ sáu chia cho số của A, rồi tiếp tục tương tự.

Nếu bản rõ bắt đầu bằng ABABCBABA, khi xét giá trị thứ ba và thứ tư ta thấy chúng khác nhau nhưng đều có số nguyên tố của B làm thừa số. Ta cũng có thể kéo khóa từ đó.

Tuy nhiên, Jamie có một lợi thế mà ta không có: ta chưa biết 26 số nguyên tố bí mật và phải tìm cách lấy được chúng.

Test Set 1

Ở Test Set 1, các giá trị bản mã là tích của các số nguyên tố nhỏ. Mỗi số nguyên tố nhỏ hơn \(10^4\), nên mỗi tích không vượt \(10^8\). Ta có thể phân tích chúng bằng cách thử mọi thừa số (nguyên tố) từ 2 tới \(10^4\). Vì mỗi chữ xuất hiện ít nhất một lần, mọi số nguyên tố trong bộ 26 số xuất hiện trong ít nhất một tích; thu thập chúng rồi sắp tăng dần để gán cho A đến Z.

Để phục hồi bản rõ, có thể dùng một chút vét cạn thay cho thao tác kéo khóa ở trên. Lấy hai thừa số của giá trị bản mã đầu và tùy ý chọn một số. Trước hết giả sử số đó ứng với chữ đầu, còn số kia ứng với chữ thứ hai. Dùng thừa số của chữ thứ hai chia giá trị bản mã thứ hai. Nếu không chia hết, ta gặp mâu thuẫn và phải đổi vai trò hai thừa số ban đầu. Nếu chia hết, thương là số ứng với chữ thứ ba, rồi lặp lại. Một trong hai lựa chọn sẽ đi hết chuỗi và cho bản rõ đúng; lựa chọn còn lại sẽ gặp mâu thuẫn, vì như phần trên đã giải thích, đề bảo đảm chỉ có một cách giải mã.

Test Set 2

Ở Test Set 2, số nguyên tố có thể khổng lồ, tới một googol (\(10^{100}\)), và tích của hai số như vậy còn lớn hơn nhiều. Thử phân tích tích là vô vọng; nếu làm được, ta cũng phá được các hệ mật mã hiện đại dựa trên giả định rằng phân tích số lớn là bất khả thi. Máy chủ Code Jam cũng chưa chạy trên máy tính lượng tử, nên không thể dùng thuật toán lượng tử.

Ta cần tìm một lỗ hổng khác. Mấu chốt là hai giá trị liên tiếp trong bản mã có ít nhất một thừa số chung. Phân tích số lớn có thể bất khả thi, nhưng tìm ước chung lớn nhất của hai số rất lớn thì hiệu quả; thuật toán Euclid đủ nhanh.

Với bản rõ như ABABC..., số nguyên tố của A có thể không xuất hiện trong bất kỳ GCD của hai giá trị liên tiếp nào. Vì vậy, hãy tính GCD của các cặp liên tiếp cho đến khi gặp hai giá trị khác nhau; GCD của chúng chính là số nguyên tố chung và không thể bằng toàn bộ một tích. Một vị trí như vậy chắc chắn tồn tại do bản rõ dùng hơn hai chữ. Từ điểm đó, chia lần lượt các tích để kéo khóa về trước và về sau, qua đó tìm mọi số nguyên tố. Cuối cùng sắp 26 số tăng dần, gán chữ và giải mã như trên. Ta thậm chí không cần biết “bevy of DP flux algorithms” là thứ gì!

Lưu ý về lựa chọn ngôn ngữ

Một kỹ năng thiết yếu trong Code Jam là chọn đúng công cụ cho bài. Có bài cần ngôn ngữ nhanh như C++ để kịp giới hạn thời gian. Với bài này, Python thường thuận tiện hơn vì xử lý số nguyên rất lớn tự nhiên dù chậm hơn đôi chút; Java cũng phù hợp nhờ có sẵn kiểu số nguyên lớn.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2019, Vòng loại, bài Cryptopangrams; kho Google Coding Competitions (Apache-2.0).