How to catch the book thief of Tiki

-Please scroll down for English-

Có một dạo, cứ hở đến 3 giờ trưa là mình cùng đại ca Alex Huỳnh huy động anh em trong lab truy cập vào tiki tham gia giải đố, với niềm tin mạnh mẽ là ba, bốn bộ não đã quen với việc giải mã các dòng code thì đây chỉ là trò trẻ con. Thể lệ trò này trích nguyên văn như sau: 

Sau nhiều phi vụ đột nhập “ngân hàng” sách thành công từ tên Siêu Trộm, Siêu nhân Tiki quyết định đầu tư bảo mật an ninh với thật nhiều vũ khí hiện đại. Tuy nhiên cách đây mấy ngày, tên Siêu Trộm đã đột nhập thành công lấy đi một lương lớn sách quý của Tiki và lấy luôn toàn bộ vũ khí dùng để đề phòng siêu trộm. Sau đó hắn để lại một lá thư thách thức cả thể giới.

“Nếu muốn lấy lại sách hãy giải những câu đố của ta. Và đừng quên đường đến kho báu luôn tràn đầy cạm bẫy” – Ký tên: Siêu trộm

Hãy cùng siêu nhân Tiki tìm lại những cuốn sách quý giá này và bạn sẽ là người sở hữu chúng!

Mọi thứ tưởng ngon ăn trong tầm tay, cơ mà cứ hễ tới mấy giây phút quyết định cuối cùng đểu làm vụt mất cơ hội. Dĩ nhiên với tư duy của 1 con mọt sách và vốn kinh nghiệm giải mật thư gần như con số KHÔNG, vũ khí duy nhất mình có được chính là bác Google và bộ các giải thuật kèm heuristic nửa vời :)) Dù sao, đây cũng là một bài toán thú vị khi mình có thể phát triển một hệ thống nhỏ đơn giản để giải quyết nó.

Mục tiêu trò chơi như sau: người chơi được giao cho một chuỗi kí tự, khi giải mã ra thì đó là tên 1 sản phẩm. Tìm đến trang web bán sản phẩm này sẽ tìm ra được link dẫn đến kho báu. Mình hệ thống hóa lại bài toán như sau:

  1. Chuỗi kí tự được cho đã mã hóa bằng một phương pháp mã hóa cơ bản, tạm chia làm 2 nhóm là mã chuyển vị và mã thay thế. Người chơi sẽ dựa theo gợi ý  mà đoán đó là mã nào. Theo kinh nghiệm của mình, một số là các biến thể của mã hóa Ceasar, trong đó 26 kí tự của bảng chữ cái latin được dịch đi một vài vị trí. Đối với mã thay thế, có thể nhắc đến là mật mã chuồng heo với gợi ý : “Có một loài vật có thể giúp ta giải được điều này, chúng rất mập và ham ăn”. Dù sao, cả hai mã này đủ đơn giản để con người bình thường có thể suy luận ra. Tuy nhiên thực tế thì một số gợi ý khó xơi, phải là kiểu hướng đạo sinh dày dạn kinh nghiệm thì may ra.
  2. Giải mã tuy xong, nhưng con đường chông gai mới thật sự bắt đầu từ đây. Các chữ cái đã bị hoán đổi vị trí, tạo thành cụm từ vô nghĩa. Người chơi phải mò ra được cụm từ gốc. Điểm khó xơi ở chỗ: đôi khi kết quả là một đường link website (“hot.tiki.vn”) hay là một thứ ngay cả đọc bằng  tiếng Việt cũng thấy lạ đời (“LOXOBOPTAY” – Lò xo bóp tay).
  3. Kiếm ra sản phẩm rồi, bây giờ người chơi sẽ lật tung cái trang  web để tìm link sản phẩm, sau đó mòn mỏi dò theo từng dòng chữ, nhiều khi nó chỉ là hyperlink đến dấu chấm cỏn con. Tìm được thì coi như 80% là ăn chắc, nếu không chậm tay hơn mấy đứa khác.
Caesar3

Ceasar Encryption

Ok, vậy cái não mình nó sử dụng cho việc gì ấy nhở. Với các con chiên ngoan đạo của Khoa học máy tính giáo phái, khả năng tự động hóa có thể thấy ở cả ba bước. Khổ nỗi, tín đồ này còn non lắm, chỉ dám đụng đến bước 1 và 2 thôi. Cụ thể thế này:

  1. Nhằm đối phó với mã thay thế, đơn giản chỉ  cần phát sinh các tổ hợp từ khả dĩ của mỗi chữ cái. Chẳng hạn cho chuỗi dài 10 kí tự, như vậy mỗi kí tự có 26 khả năng cho 26 chữ cái latin với giả định chúng khác nhau đôi một, kết quả trả về là 26^10 chuỗi khả dĩ. STUPIDDDDDDD… Ngay cả khi tìm được từ đúng, chưa chắc mình đã tin, bởi nó còn bị lọc bởi bước hoán vị. Gặp dạng này thì bó tay, tốt nhất tra Google cho đúng loại mã rồi chuyển thủ công. Nếu may mắn, ta gặp được biến thể của Ceasar thì mọi thứ ngon ăn hơn nhiều. Chuỗi kí tự gốc có thể tìm được bằng cách dịch chuyển dọc theo bảng chữ cái một số lượng vị trí, như vậy ta sẽ luôn thu được 26 chuỗi tiềm năng, công việc mò kim đáy bể coi bộ dễ thở hơn tí xíu.
  2. Vụ hoán vị hơi khó xơi hơn tí, kĩ thuật mình áp dụng tỉ lệ nghịch với độ ngớ ngẩn: đơn giản nhất, chỉ phát sinh các hoán vị có thể có và in ra file. Thử đoán với chuỗi “UVHKUMINOBTA”, các bạn có bao nhiêu hoán vị? 12! đó, tức 479001600 tổ hợp. Để tui thêm dấu chấm cho dễ nhìn chút: 479.001.600. Khá tức cười là sáng hôm sau, té ngửa khi ổ C giảm từ 4.5 GB xuống 1.5GB mà không biết tại sao. Một hồi chợt nhớ ra thì kiểm tra file ghi kết quả nặng tới 3GB, chỉ 1 từ: “khủng khiếp”. Sau đó, thông minh hơn xíu, mình cho các kết quả hoán vị phải chứa từ trong từ điển và được sắp xếp theo chiều dài giảm dần. Thực nghiệm lại chứng minh một điều: đừng đùa với hoán vị và tiếng Việt. Với chuỗi kết quả (“KHUVUONBIMAT” – khu vườn bí mật), trong từ điển chuẩn tiếng Việt chỉ có “vườn”, không “khu vườn”.  Dĩ nhiên là có thể bổ sung “khu vườn” và tạo từ điển mới, tuy nhiên mình e rằng khi chạy ra kết quả thì thiên hạ đã giải xong ráo trọi.

Mặc dù đã cố gắng thiết lập mọi thứ thật hệ thống và khoa học, bùng nổ tổ hợp không khiến cho câu đố dễ thở hơn bao nhiêu. Và tay trắng thì vẫn hoàn trắng tay. Mình may mắn chạm đến bước 3 cỡ bốn lần, tuy nhiên hầu hết là dựa theo comment của người chơi khác để mò theo, nhưng rồi cũng chậm tay hơn kẻ khác.

Ok, chuyện chỉ có thế. Mọi người ngủ ngon, giữ sức khỏe và đừng thức khuya quá nhé.

230px-Pigpen_cipher_key.svg (1)

Pigpen Cipher


There is a period of time, when it came to 3.pm, me and brother Alex Huỳnh assembled all brothers and sisters in lab accessing to tiki to participate in puzzle contest, with strong belief that the combination of fours brain which is used to with deciphering code can turn this thing into child play. Below is the rule:

After many successful intrusion of Super Burglary to “book bank”, Tiki Superman decides to invest into security with plenty of modern technology. However a few days ago, Super Burglary broke into the bank and successfully removed a large number of book of Tiki. He then left a letter challenging the world.

“If you want to get back the books, solve my puzzles. And do not forget that the way to the treasure always full of pitfalls” – Signed: Super Burglary.

Let’s help Tiki Superman to get back those valuable book and you’ll be owning them!

Everything seems easy, yet all the opportunities passed through my hand without noticing me. Of course with the mindset of a bookworm and experience in solving puzzles is ZERO, my only weapons are Google and amateur algorithms plus heuristics  :)) However, this is still an interesting problem in which I can develop a small and simple system to solve it.

After receiving a string of characters, players have to decipher it and find the name of a product. Then you have to log in to that website, look for the hidden link which lead to the treasure. I systemized them as below:

  1. String of characters are encrypted by simple encryption, can be classified into 2 kinds: subtitution cipher and displacement cipher (too bad that I can not remember exactly their name in English, sorry prof Tran Minh Triet :((  ). Player will find the exact encryption type based on the hint. According to my experience, some of them are variant forms of Ceasar, in which 26 characters of latin alphabet will be moved for a number of position to the origin. To the subsitution one, pigpen cipher is a typical example with the hint: “There is one animal can help you solve the puzzle, which is very fat and hoggish (always hungry for foods)”. However, these both techniques are basic for normal people to figure out. In practice, you must be a boyscott to be able to solve them.
  2. The decipher stage is done, but the tough part is still ahead. All the characters have been permuted, you must find their origin message by permute them back. It is difficult because: sometimes, the origin message is a link (“hot.tiki.vn”) or a word which is also hard to recognize(‘LOXOBOPTAY’ – lò xo bóp tay – spring of hands).
  3. Finding out the product, players now have to search for the website of that product, looking at word by word and find a hyperlink hidden somewhere, most of the time is just a small dot. If you are good and fast, 80% you can find the treasure.

Ok, so how did I used my brain for? If you are the sons of Computer Science religion, the automatic ability can be applied to all 3 stages. Despite of that fact, I am still young and inexperienced, so I only concern about the first and second stages. To be more specific, it will be like this:

  1. In order to pass the subtitution encryption, we can generate all the possible combinatory for each string. For example, with a string of length 10, each character can represent for 26 characters, with assumption they are individual different. It will be 26^10 possible strings. STUPIDDDDDDD… Even if you found the right string, how can you know they are the right one because it is also protected by permutation filter. This one seem impossible, so the best thing I recommend is using Google and use the encryption table to manually decipher it. If you are lucky, life is much easier when it is Ceasar variants. The origin string can be found by moved each characters in a fixed number of positions. We will always get 26 potential strings, so you can stop holding your breath and let the power of computation be your assistant.
  2. The permutation is much more difficult to deal with, the techniques I used is inversely proportional to its silly. The simplest method is generating all permutation and printed it to file. With string “UVHKUMINOBTA”, guess how many string you got? 12!, or 479001600 combinations. Let me put some more dots: 479.001.600. It’s quite funny when i woke up in the morning and see the disk capacity of C drive decreased dramatically from 4.5 GB to 1.5 GB. It took me a while until I remember created the result file. Not out of my suspect, its size is near 3 GB. Only 1 words to describe my feeling: “terrific”.  My second approach is more intelligent, in which the permutation must contain at least one word in Vietnamese dictionary and sorted by the length decrease. Practive show my solution is far more from right: you should not play with permutations and Vietnameses language. With result string (“KHUVUONBIMAT”- khu vườn bí mật, which means “secret garden”), you can not find the “khu vườn” word (“garden”), but only “vườn”. Of course you can add “khu vườn” and create a new dictionary, but I’m afraid you can not make it far in this way.

Even though I have set everything in systematically and scientific way, combinatorial explosion can not be avoided and that can not make the puzzle more easier as I expected. I was lucky reach the stage 3 for 4 times, however most of them based on the comments of other players.

Ok, that’s the story I want to tell today. Good night everyone, keep up the good work and healthy, and don’t stay  up too late.

Advertisements

One comment

  1. giahy2507 · January 27, 2016

    =D

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.