Dạo cách đây không lâu tôi có thử sức với Matasano"s crypto challenges (cryptopals.com). Về cơ bạn dạng đây là tập hợp các thử thách về mã hóa, mật mã; trong các số ấy người chơi sẽ rứa gắng chấm dứt các bài bác tập thực hành thực tế về mã hóa (bao gồm thiết lập các thuật toán mã hóa thông dụng, phá mã) từ bỏ cổ điển cho tới hiện đại. Vào challenge 3 với 4, chúng ta được yêu mong phá mã cổ điển, rõ ràng là single-byte XOR. Thuật toán mã hóa thật đối chọi giản, bạn sẽ chọn một khóa K (độ lâu năm 1 byte) cùng lần lượt XOR với những byte nguồn vào của phiên bản rõ. Dễ dàng thấy đấy là phiên bản mởi rộng tiến bộ của mật mã Caesar. Dưới đây là thuật toán mã hóa:

def single_byte_xor(msg: bytes, key: int) -> bytes: cipher = bytes(b^key for b in msg) return cipherVới thử thách 3, bạn sẽ được hỗ trợ một phiên bản mã ( được mã hóa thực hiện single-byte XOR) và các bước của các bạn là search ra bạn dạng rõ. Với bài xích này, do không khí khóa bé dại (256 giá chỉ trị), chúng ta có thể thử 256 giá trị rất có thể của khóa (0x00 -> 0xFF), decrypt phiên bản mã với khóa đó và quan sát xem bản rõ nào tương tự với giờ đồng hồ anh nhất.

Bạn đang xem: Frequency analysis là gì

Nhưng challenge 3 mong muốn bạn tạo nên một chương trình tự động hóa giải mã. Để có tác dụng được việc này, ta rất cần phải có cách để "chấm điểm" bạn dạng rõ so với tiếng Anh. Tức thị ta cần biết đoạn text vừa gỉa mã được giống như với giờ Anh như vậy nào. Với ta vẫn chọn bản rõ bao gồm điểm số cao nhất.

Các hệ mã cổ xưa đều hoàn toàn có thể bị phá bằng phân tích tần suất (Frequency analysis), cho nên vì thế để kiến tạo hàm "chấm điểm" ta rất có thể sử dụng kiến thức về phân bố tỷ lệ của các chữ cái trong giờ đồng hồ anh. Hình bên dưới là tần suất mở ra của những chữ loại trong giờ đồng hồ Anh.

*

Với challenge 3 này, tôi thực hiện thống kê Chi-squared để tấn công trọng số (chấm điểm) cho bạn dạng rõ. Hiểu 1-1 giản, thống kê lại Chi-squared màn biểu diễn độ tương đồng giữa 2 phân bố xác suất, 2 phân bổ càng như là nhau thì gía trị Chi-squared của chúng càng bé dại và bằng 0 nếu như 2 phân bố hệt nhau nhau. Dưới đấy là công thức tính Chi-squared:

*

Trong đó, Ci là số lần lộ diện của chữ cái i trong khúc text, với Ei là số lần lộ diện mong chờ (Expected) của chữ cái i trong đoạn text.

Xem thêm: Cách Tạo Động Lực Học Tiếng Nhật Dành Cho Người Mất Gốc, By Dũng Mori Kaiwa

Bởi vì chưng trong một câu tiếng Anh, ký kết tự khoảng trắng (space) cũng xuất hiện rất nhiều nên để rất có thể đánh gía xuất sắc hơn, tôi đã sử dụng cả cam kết tự space thời điểm tính Chi-squared. Chúng ta cũng có thể lấy dữ liệu xác suất của bảng chữ cái tiếng Anh bao hàm space tại http://www.data-compression.com/english.shtml.

Ta bao gồm thể dứt challenge 3 bằng cách chọn ra bạn dạng rõ bao gồm Chi-squared nhỏ nhắn nhất.

Nhưng để hoàn thành challenge 4 ta rất cần phải sử dụng tiến công gía trọng số đúng mực hơn, đó là thực hiện Chi-square đến cặp 2 chữ cái. Tài liệu các chúng ta cũng có thể lấy trên english_bigram.

Trong bài viết tới, tôi sẽ trình bày lời giải của chính mình cho challenges 5 và 6. Nếu như bạn là người yêu thích tìm hiểu, nghiên cứu mật mã và các phương thức phá mã hiện đại, bạn nên thử mức độ với Matasano"s crypto challenges.