solution

Trong tiếng Anh, các chữ cái xuất hiện với tần suất đặc trưng (ví dụ chữ E xuất hiện nhiều nhất). Vì mật mã Caesar chỉ dịch chuyển đều tất cả chữ cái theo cùng một khóa $k$, phân bố tần suất của bản mã chỉ là một phép xoay vòng của phân bố tần suất bản rõ. Do đó có thể phá mã bằng cách thử từng khóa $k \in [0,25]$, và chọn khóa làm cho phân bố tần suất chữ cái của bản rõ giải mã ra "giống" tiếng Anh chuẩn nhất, đo bằng thống kê chi-squared:

$\chi^2(k) = \sum_{i=0}^{25} \frac{(O_i - E_i)^2}{E_i}$

trong đó $O_i$ là số lần xuất hiện thực tế của chữ cái thứ $i$ trong bản rõ ứng với khóa $k$, $E_i = f_i \times n$ là số lần xuất hiện kỳ vọng ($f_i$ là tần suất chuẩn theo bảng dưới đây, $n$ là tổng số ký tự chữ cái trong văn bản). Khóa được chọn là khóa có $\chi^2(k)$ nhỏ nhất; nếu có nhiều khóa cùng cho $\chi^2$ nhỏ nhất, chọn khóa nhỏ nhất trong số đó.

Bảng tần suất chữ cái tiếng Anh chuẩn (không phân biệt hoa/thường):

Cho một đoạn văn bản tiếng Anh $S$ đã được mã hóa Caesar (chữ hoa/thường và các ký tự không phải chữ cái được giữ nguyên vị trí, chỉ chữ cái bị dịch chuyển), hãy tìm khóa $k$ đã dùng để mã hóa theo phương pháp trên, rồi giải mã toàn bộ $S$.

Ví dụ (rút gọn): nếu $S$ được mã hóa với $k=3$ từ một đoạn văn tiếng Anh dài, thuật toán trên sẽ tìm ra $k=3$ và khôi phục đúng đoạn văn gốc.