[Hướng dẫn] Thực hiện giải mã mật mã Vigenere khi không có khóa

Hôm nay đổi gió tí không thiên về kĩ thuật nữa :D làm một cái giải mã cho tươi mới.

1/ Giới thiệu sơ lược: Mật mã Vigenere(VG) được ra đời cách đây khá lâu, đây là một cải tiến của mật mã Ceasar. Sự khác nhau của Ceasar và Vigenere nằm ở độ dài của khóa. Đối với Ceasar thì mã khóa chỉ là một số chỉ "độ dịch chuyển", số này có thể chuyền thành một chữ cái để trở thành một key. Trong khi đó VG thì sử dụng một từ để mã hóa. Sự khác biệt này tạo cho VG một sự phức tạp trong quá trình cố gắng giãi mã không khóa.

2/ Cách mã hóa của VG: Mã khóa của VG là một từ vì vậy mỗi chữ cái trong đoạn văn bản rõ sẽ được mã hóa bằng cách dịch chuyển một đoạn bằng key của chữ cái trong từ mã khóa.

3/ Cách giải mã: Bằng cách thống kê các bộ 3 hoặc bộ 4 trong văn bản mã hóa, từ đó xác định 2 yếu tố của khóa đó chính là:

• Độ dài mã khóa.
• Kĩ tự của các chữ cái trong mã khóa.

4/ Cách tiến hành:  

Ở hướng dẫn này thì mình sẽ dùng thống kê các bộ 3. Và giải mã một đoạn văn bản tiếng Anh.
Bước 1: Gồm 3 công việc:

• Tìm và đếm các bộ ba trong đoạn văn bản mã hõa
•  Xác định độ dài giữa những bộ ba giống nhau.
•  Tìm ước số của độ dài này

Đến đây đã, sau đó sẽ tiếp tục các step sau.
Tại sao chúng ta phải quan tâm đến ước số của các độ dài. Vì mật mã Virgenere dùng một key là một từ khóa, nó có một độ dài nhất định, mình gọi là L. Vậy thì sau nhiều lần nhảy lên L chữ cái, thì chúng ta có thể gặp được một chữ cái được mã hóa bằng 1 chữ cái ở một vị trí nhất định của từ khóa. Độ dài khóa sẽ quyết định điều này
VD: Mình có một đoạn văn bản mã hóa sau (không cần nhìn vào để rối mắt làm gì)

KXTGOBGVNGRLDMKGNVOSNLHKQPESREJSWLOUQERMBZMGUTEJQQEHEFRPEKTRTXEVTYKRKANXCFOMTYQATGCFOTLWTVCRDANPGERKHRXIGGTCKXTDEWWVTZEIVLAFOEGWIVEZHCOMWRPXTGLVCVNZONVSSGLMGXHWRLDMKUUSGPOGKEQJUJTYGVYGUYCZEUODGXOLHVTMGZTGNECWGVVXIFGYGPPOIKJWODVZPKTZEIWFICCLDIIKNFVGHWAKKRGLHVTIAJEHWMNLICNMOFPFUWITICKXIWSSWXOFLPQREUOITICLSFNYTAOEJINUENKXHGUKMROOIEILOOTFUSLNERTYBAKTWFEATZURESRCAMMHOJUMBDEKJMSKIOUXEHGLKHEOICNXACEPQYTZRFWKHWVVTCTZIEICOMNVGHTGKEQAWZEEKXCGMVUXOKOCXMNYTYGVUTIBEYBWIKKWRWACNCSAMGNIYGUAWWTZAMGXOXOCNSWLHVUXEHSRPHYGUNKPLTEJQPVANXVLEJUSKOCMBVKRLWSJVLAFTNQQIFUKGW

Bây giờ chúng ta sẽ thống kê các bộ ba-> tìm độ dài giữa các bộ ba-> tìm ước 

Ở trên là bảng thống kê các bộ ba và ước số của độ dài khóa. Lưu ý ở đây là mình giả định rằng từ khóa sẽ nhỏ hơn 20 chữ cái, nên mình chỉ chọn các ước nhỏ hơn 20. Nếu tăng lên thì các ước số cũng ít xuất hiện hơn. Có thể an tâm với test này.
Từ bảng này chúng ta sẽ quyết định độ dài khóa là bao nhiêu. Các bạn có thể thấy ở cột 2, 3 và 6 xuất hiện nhiều nhất. Chúng ta sẽ nghi ngờ rằng từ khóa có thể có độ dài là 2 hoặc 3 hoặc 6.
Tất nhiên giả định này rất hợp lý vì sự lặp lại các từ khóa này theo một chu kì sẽ tạo nên nhiều sự xuất hiện lại các bộ ba, được mã hóa từ một bộ ba văn bản rõ bằng một đoạn con của từ khóa.
Với 3 sự lựa chọn là 2 hoặc 3 hoặc 6. Chúng ta sẽ thử với 3 lựa chọn này, nhưng mình sẽ "gợi ý" bạn nên dùng 6, vì đó là đáp án, ok? :))

Bước 2: Khi đã có một độ dài khóa giả dịnh, từ đây chúng ta sẽ tìm xem từ khóa là gì
ở bước này, độ dài khóa đã biết, vậy thì chúng ta cũng biết được chu kì lặp lại của từ khóa để mã hóa. Vậy thì giả sử từ khóa có 6 chữ cái, mình gọi là ABCDEF, bây giờ thì nhìn vào đoạn mã hóa, các chữ cái cách nhau 6 vị trí sẽ được mã hóa bởi một chữ cái của từ khóa. Vậy thì công việc bây giờ chỉ là thống kê và tìm chữ cái đó tương tự như giải mã Ceasar.

VD: mình lấy đoạn đầu tiên của đoạn văn bản script
KXTGOBGVNGRL
chữ K và G sẽ được mã hóa bởi chứ cái A  .lưu ý A chỉ là tên gọi của kí tự đầu tiên của khóa thôi, muốn biết kí tự khóa đó là gì thì tới step 3.
Bước 3: Chúng ta sẽ xác định từng kí tự một của từ khóa. Sự dụng phương pháp giải mã Ceasar
Bắt đầu, chúng ta sẽ đếm các kí tự ở vị trí thứ nhất của từ khóa. A xuất hiện bao nhiều lần, C xuất hiện bao nhiều lần,... sau đó tính tần suất xuất hiện các kí tự đó.

ở đây mình có một bảng tần xuất xuất hiện của kí tự ở vị trí đầu tiên. Ở trên là một bảng tần xuất chuẩn (tần xuất xuất hiện các kí tự tiếng Anh). Ở dưới là bảng tần xuất mà chúng ta thống kê được ở vị trí đầu tiên. Khi mình dịch chuyển đi 3 vị trí (tức là dùng mã khóa "C") thì thấy có một sự tương đồng nhẹ ở 2 bảng tần xuất. Vậy thì chúng ta có thể làm tay, nhưng lâu và phức tạp+căng mắt nữa. Chúng ta có thể dùng toán học để xác định tự tương đồng này.
Ở bước này thì chúng ta dùng phương pháp Least Square, phương pháp này hay dùng trong ngàng Calculus, dùng để đánh giá xem các giá trị thực nghiệm với giá trị tính toán chính xác có thể chấp nhận không. Vẫn hay thấy dùng nhất là biểu đồ vẽ bằng hàm số so với biểu đồ giá trị đo đạc được.

phương pháp least square: Chúng ta phải tìm một đường cong sao cho tổng này nhỏ nhất

với f(xi) là những giá trị tính toán bằng hàm. yi là giá trị đo đạc được. n là số lần lấy mẫu ở những điểm khác nhau.
với bài toán ở đây thì f(xi) chính là những giá trị ở bảng tần xuất chuẩn, yi chính là giá trị ta thống kê được, n=24 vì có 24 kí tự, ta sẽ lấy mẫu của 24 điểm này.
x^2 càng nhỏ thì error càng thấp, chúng tỏ đường cong càng tốt.
Ở đây mình có một "đường cong" tần xuất chuẩn ở trên, vậy thì mình sẽ xem bảng tần xuất ở dưới có phải đường cong tốt nhất hay không.
chúng ta sẽ thử với 24 mã khóa (từ "A" -> "Z") và chọn ra mã khóa có error thấp nhất.
sau đây là bảng tần xuất với 5 kí tự còn lại:

Văn bản rõ là: 
it took erno rubik one month to learn how to do a rubik cube. some people started thinking about how to complete and in years have got little further than one side. if you want to learn how to solve the rubik cube look no further you have come to the right place getting help with solving the rubik cube is not cheating. there are quintillion possibilities, but only one correct solution. hence without knowing how to solve a rubik cube it is nearly impossible. this six step guide will take you through everything you need to know when it comes to solving the rubik cube. it is really simple, you just have to follow the steps and you will be solving the rubik cube in less than two minutes

Lưu ý: Nếu muốn dùng với tiếng việt thì phải lập ra bản tần xuất của tiếng Việt.

Mã hóa và giải mã thật sự rất thú vị, nó chỉ xoay quanh toán và toán. Mình đang nghiên cứu một số hệ mã hóa khác và thử giải mã... có thể lần tới là RSA.
-THE END-