Dạo vừa mới đây tôi có thử mức độ với Matasano"s crypto challenges (cryptopals.com). Về cơ bạn dạng đây là tập hợp những thử thách về mã hóa, mật mã; trong các số đó người nghịch sẽ nạm gắng dứt các bài bác tập thực hành thực tế về mã hóa (bao gồm cài đặt 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. Trong challenge 3 cùng 4, bạn được yêu ước phá mã cổ điển, ví dụ là single-byte XOR. Thuật toán mã hóa thật đối kháng giản, các bạn sẽ chọn một khóa K (độ dài 1 byte) cùng lần lượt XOR với những byte đầu vào của bạn dạng rõ. Dễ dàng thấy đây là phiên phiên bản mởi rộng tân tiến của mật mã Caesar. Dưới đó 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ách thức 3, các bạn sẽ được cung ứng một bạn dạng mã ( được mã hóa áp dụng single-byte XOR) và quá trình của bạn là search ra phiên bản rõ. Với bài bác này, do không khí khóa nhỏ (256 giá trị), bạn cũng có thể thử 256 giá chỉ trị hoàn toàn có thể của khóa (0x00 -> 0xFF), decrypt phiên bản mã cùng với khóa kia và chú ý xem bạn dạng rõ nào gần giống 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 sinh sản một chương trình auto giải mã. Để làm cho được câu hỏi 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 phải biết đoạn text vừa gỉa mã được tương đương với giờ Anh như thế nào. Và ta sẽ chọn bạn dạng rõ gồm điểm số cao nhất.
Các hệ mã truyền thống đều rất có thể bị phá bằng phân tích gia tốc (Frequency analysis), cho nên vì thế để tạo hàm "chấm điểm" ta rất có thể sử dụng kỹ năng về phân bố tỷ lệ của những chữ dòng trong tiếng anh. Hình bên dưới là tần suất xuất hiện thêm của các chữ mẫu trong tiếng Anh.
Với challenge 3 này, tôi sử dụng thống kê Chi-squared để đánh trọng số (chấm điểm) cho bản rõ. Hiểu 1-1 giản, thống kê lại Chi-squared trình diễn độ tương đồng giữa 2 phân bố xác suất, 2 phân bố càng tương đương nhau thì gía trị Chi-squared của chúng càng nhỏ và bởi 0 nếu 2 phân bố giống hệt 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 mở ra mong chờ (Expected) của chữ cái i trong đoạn text.
Xem thêm: Bỏ Túi Các Cách Làm Lông Mày Rậm Cho Nam Giới, 11 Cách Làm Lông Mày Rậm Cho Nam
Bởi vì trong một câu giờ Anh, ký tự khoảng chừng trắng (space) cũng xuất hiện không ít nên để rất có thể đánh gía giỏi hơn, tôi đã áp dụng cả ký kết tự space thời điểm tính Chi-squared. Chúng ta có thể lấy dữ liệu phần trăm của bảng chữ cái tiếng Anh bao hàm space tại http://www.data-compression.com/english.shtml.
Ta có thể xong xuôi challenge 3 bằng phương pháp chọn ra bản rõ gồm Chi-squared bé bỏng nhất.
Nhưng để dứt challenge 4 ta rất cần được sử dụng tấn công gía trọng số đúng đắn hơn, kia là sử dụng Chi-square cho cặp 2 chữ cái. Tài liệu các chúng ta có thể lấy trên english_bigram.
Trong bài viết tới, tôi sẽ trình diễn lời giải của bản thân cho challenges 5 và 6. Nếu khách hàng là người yêu thích tìm hiểu, nghiên cứu mật mã và các phương pháp phá mã hiện nay đại, bạn nên thử sức với Matasano"s crypto challenges.
