[Crypto] 06 – Mã Vigenere - Nhat Truong Blog

Giới thiệu

yptoCả 3 loại mã tôi đã giới thiệu ở các bài trước: mã Caesar, mã Affine và mã thay thế đơn giản được gọi chung là mã thay thế dùng một bảng chữ cái (monoalphabetic substitution cipher). Nghĩa là ta dùng một bảng ánh xạ các chữ cái trong bảng mã thành bản rõ và tất cả các các chữ cái trong bản mã đều dùng chung một bảng ánh xạ.

Yếu điểm của loại mã này là bản mã sẽ giữ lại đặc điểm mẫu từ và đặc điểm tần suất của văn bản gốc. Để loại bỏ nhược điểm trên, các nhà lập mã đã tạo ra một hệ mã khác gọi là mã thay thế dùng nhiều bảng chữ cái (polyalphabetic substitution cipher).

Ví dụ đơn giản là trường hợp dùng 2 bảng chữ cái Cipher alphabet 1 và Cipher alphabet 2 làm khóa mã:

Khi đó chữ cái thứ nhất trong bản rõ sẽ được mã hóa theo Cipher alphabet 1, tức là a -> F, b -> Z. Chữ cái thứ 2 trong bản rõ được mã hóa theo Cipher alphabet 2, tức là a -> G, b -> O. Và sau đó lặp lại, chữ cái thứ 3 mã hóa theo Cipher alphabet 1, … Theo cách này, bản rõ NHATTRUONGBLOG sẽ được mã hóa thành SHFYGSNJSTZADT. Có thể thấy 2 chữ T trong bản rõ được mã hóa thành 2 cách khác nhau: Y và G.

Và mã Vigenere là loại mã thay thế dùng nhiều bảng chữ cái như vậy. Cách thức mã hóa như sau:

Giả sử ta cần mã hóa câu: divert troops to east ridge (chuyển quân sang bờ phía đông). Đầu tiên chọn ra một cụm từ làm khóa. Ví dụ WHITE. Ta sẽ viết cụm WHITE này lặp lại đến khi bằng độ dài bản rõ. Rồi lập sơ đồ sau:

Theo sơ đồ, kí tự đầu tiên của bản rõ, chữ d được mã hóa theo mã Caesar với key là a -> W, hay nói cách khác k = 22, vậy d mã hóa thành Z. Tiếp tục, kí tự thứ 2, chữ i mã hóa theo mã Caesar với key là a -> H, hay k = 7, vậy i -> P. Tương tự đến hết. Bản rõ divert troops to east ridge sẽ được mã hóa thành ZPDXVP AZHSLZ BH IWZB KMZNM.

Hoặc có thể thực hiện mã Vigenere bằng hình vuông Vigenere:

Các dòng được tô đậm tương ứng với các chữ cái của khóa, W: dòng 22, H: dòng 7, I: dòng 8, T: dòng 19, E dòng 4. Vậy ta mã hóa từng chữ cái trong bản rõ theo thứ tự dòng 22 (a -> W) -> 7 (a -> H) -> 8 -> 19 -> 4 rồi lặp lại -> 22 -> 7 -> …

Và đây là định nghĩa sơ đồ mã hóa Vigenere một cách toán học như sau:

S = (P, C, K, E, D)

Trong đó P = C = K = Zm26 , các hàm lập mã và giải mã được cho bởi:

E(p1, ..., pm) = (p1 + k1, ..., pm + km) mod 26

D(c1, ..., cm) = (c1 + k1, ..., cm + km) mod 26

với mọi p =(p1,..., pm) ∈ P, c =(c1,..., cm) ∈ C , K = (k1,..., km) ∈ K, m là chiều dài khóa.

le chiffre indéchiffrable

Với key = WHITE gồm 5 chữ cái như trên, không gian khóa là 265 = 11.881.376. Vậy nếu biết trước key có 5 kí tự, với một máy tính tầm trung, thuật toán Brute-force sẽ phá mã trong vòng vài giờ. Nhưng nếu chiều dài khóa tăng lên, không gian khóa sẽ tăng theo hàm số mũ. Bảng sau cho ta thấy không gian khóa ứng với chiều dài khóa:

Nếu key gồm 14 kí tự thì không gian khóa là > 6.1019. Con số quá lớn cho thuật toán Brute-force có thể làm việc được. Và điều quan trọng nữa là ta không biết key gồm bao nhiêu kí tự. Thực tế thì người mã hóa thường chọn key là một cụm từ có nghĩa để thuận tiện cho trao đổi khóa, điều này làm hạn chế không gian khóa rất nhiều, tuy nhiên nó vẫn đủ để làm bạn bó tay nếu giải mã bằng Brute-force.

Nhưng, điều đáng nói của mã Vigenere không phải ở không gian khóa lớn của nó, nên nhớ mã thay thế đơn giản có không gian khóa là 26! > 4 x 1026. Điểm đáng bàn là ở chỗ: mỗi kí tự của bản rõ có thể được mã hóa thành nhiều kí tự khác nhau nên bản mã sẽ mất đi tính chất mẫu từ và tính chất phân bố tần suất của văn bản gốc. Khiến cho việc thám mã dựa trên 2 phương pháp phân tích mẫu từ và phân tích tần suất đã đề cập cũng … bó tay.

Chính vì thế mà trong khoảng thiên niên kỷ thứ I (SCN), mã Vigenere từng được coi là le chiffre indéchiffrable (tiếng Pháp nghĩa là Mật mã không thể phá nổi). Có vẻ như các nhà thám mã đã vươn lên trước các nhà tạo mã một bước trong cuộc đối đấu của mình. Tuy nhiên, vâng vẫn là tuy nhiên, như slogan của blog NO SYSTEM IS SAFE, hệ mã này vẫn có nhược điểm có thể khai thác được, tôi sẽ giới thiệu ở phần sau.

Giờ thì chúng ta sẽ viết chương trình mã hóa trước đã.

Code

LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' def vigenere_cipher(message, key, MODE): translated = [] keyIndex = 0 key = key.upper() for symbol in message: num = LETTERS.find(symbol.upper()) if num != -1: if MODE.upper() == 'ENCRYPT': num += LETTERS.find(key[keyIndex]) elif MODE.upper() == 'DECRYPT': num -= LETTERS.find(key[keyIndex]) num %= len(LETTERS) if symbol.isupper(): translated.append(LETTERS[num]) elif symbol.islower(): translated.append(LETTERS[num].lower()) keyIndex += 1 if keyIndex == len(key): keyIndex = 0 else: translated.append(symbol) return ''.join(translated) def main(): message = """Alan Mathison Turing was a British mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine. Turing is widely considered to be the father of computer science and artificial intelligence. During World War II, Turing worked for the Government Code and Cypher School (GCCS) at Bletchley Park, Britain's codebreaking centre.""" key = 'NHATTRUONGBLOG' cipher = vigenere_cipher(message, key, 'ENCRYPT') print('nMessage: ' + message) print('nCiphertext: ' + cipher) message = vigenere_cipher(cipher, key, 'DECRYPT') print('nMessage after decrypt: ' + message) if __name__ == '__main__': main()

Kết quả:

Thám mã

Nếu người gửi dùng key là một từ Tiếng Anh có nghĩa, bạn dễ dàng dùng Brute-force để crack nó bằng cách cho key lần lượt là các từ trong file dictionary.txt và giải mã xem có thu được đoạn văn có nghĩa không.

Ở đây ta giả sử rằng không biết gì về key, đó có thể là 1 dãy kí tự ngẫu nhiên, và ta phải tìm cách phá nó. Bước đầu tiên ta cần xác định chiều dài khóa là bao nhiêu bằng cách dùng phép thử Kasiski.

Phép thử Kasiski

Giả sử có bản mã như sau:

PPQCAXQVEKGYBNKMAZUYBNGBALJONITSZMJYIMVRAGVOHTVRAUCTKSGDDWUOXITLA ZUVAVVRAZCVKBQPIWPOU

Hãy tìm những cụm kí tự (>= 3 kí tự) lặp lại nhiều lần trong đoạn mã trên. Ta thấy có 3 cụm lặp lại là: VRA, AZU, và YBN

PPQCAXQVEKGYBNKMAZUYBNGBALJONITSZMJYIMVRAGVOHTVRAUCTKSGDDWUOXITLA ZUVAVVRAZCVKBQPIWPOU PPQCAXQVEKGYBNKMAZUYBNGBALJONITSZMJYIMVRAGVOHTVRAUCTKSGDDWUOXITLA ZUVAVVRAZCVKBQPIWPOU PPQCAXQVEKGYBNKMAZUYBNGBALJONITSZMJYIMVRAGVOHTVRAUCTKSGDDWUOXITLA ZUVAVVRAZCVKBQPIWPOU

Nhận xét: các cụm VRA cách nhau 8 và 24 kí tự, cụm AZU cách nhau 48 kí tự, cụm YBN cách nhau 8 kí tự.

Bạn đọc chú ý nếu 2 kí tự trong bản rõ cách nhau n kí tự và n là bội số của chiều dài khóa thì chúng sẽ được mã hóa giống nhau thành cùng 1 kí tự trong bản mã. Đó là đặc điểm của mã Vigenere. Do đó nếu ta tìm được các cụm từ lặp lại thì khả năng chúng là do cùng một cụm từ trong bản rõ được mã hóa giống nhau do khoảng cách của chúng là bội số của chiều dài khóa. Vì thế phép thử Kasiski nói rằng chiều dài khóa phải là ước số của các khoảng cách trên. Như vậy trong trường hợp này chiều dài khóa có thể là 2, 4, hoặc 8.

Vậy giả sử chiều dài khóa là 4. Ta sẽ chia bản mã thành 4 bản mã con: Bản thứ 1 chứa các kí tự thứ 1, 5, 9, 13, … Bản thử 2 chứa các kí tự thứ 2, 6, 10, 14, … Mỗi bản mã con này do cùng 1 kí tự trong key (tạm gọi là subkey) mã hóa nên, sau đó áp dụng phép phân tích tần suất dưới đây để tìm ra subkey.

Phân tích tần suất

Làm sao để phân tích tần suất 1 đoạn mã. Đầu tiên ta làm quen với khái niệm Điểm số tương đồng tần suất. Đoạn văn bản sau được mã hóa bằng mã thay thế: Sy l nlx sr pyyacao l ylwj eiswi upar lulsxrj isr sxrjsxwjr, ia esmm rwctjsxsza sj wmpramh, lxo txmarr jia aqsoaxwa sr pqaceiamnsxu, ia esmm caytra jp famsaqa sj. Sy, px jia pjiac ilxo, ia sr pyyacao rpnajisxu eiswi lyypcor l calrpx ypc lwjsxu sx lwwpcolxwa jp isr sxrjsxwjr, ia esmm lwwabj sj aqax px jia rmsuijarj aqsoaxwa. Jia pcsusx py nhjir sr agbmlsxao sx jisr elh. -Facjclxo Ctrramm

Nếu ta tính tần suất xuất hiện của từng kí tự và sắp xếp chúng theo thứ tự giảm dần sẽ được dãy ASRXJILPWMCYOUEQNTHBFZGKVD. Ta sẽ xét sự tương đồng của dãy này với dãy tần suất giảm chuẩn trong Tiếng anh (được thống kê sẵn) là ETAOINSHRDLCUMWFGYPBVKJXQZ và chỉ xét sự tương đồng của nhóm 5 kí tự thường gặp nhất với nhóm 6 kí tự ít gặp nhất ta được:

Có 2 kí tự xuất hiện trong top 6 của 2 nhóm, và có 3 kí tự xuất hiện trong bottom 6 của 2 nhóm. Khi đó ta nói Điểm số tương đồng tần suất của đoạn mã này là 5.

Xét một đoạn văn bản khác được mã hóa bằng mã chuyển vị (thay đổi vị trí các kí tự theo một cách nào đó):

I rc ascwuiluhnviwuetnh,osgaa ice tipeeeee slnatsfietgi tittynecenisl. e fo f fnc isltn sn o a yrs sd onisli ,l erglei trhfmwfrogotn,l stcofiit.aea wesn,lnc ee w,l eIh eeehoer ros iol er snh nl oahsts ilasvih tvfeh rtira id thatnie.im ei-dlmf i thszonsisehroe, aiehcdsanahiec gv gyedsB affcahiecesd d lee onsdihsoc nin cethiTitx eRneahgin r e teom fbiotd n ntacscwevhtdhnhpiwru

Ta cũng tính điểm số tương đồng tần suất:

Ở đây điểm số là 9, điểm số cao như vậy là do bản mã và bản rõ dùng cùng một bộ kí tự giống nhau, bản mã chỉ hoán vị các kí tự của bản rõ. Như vậy có thể áp dụng phép phân tích tần suất này cho mỗi subkey ở phần trên. Với mỗi subkey ta có một đoạn bản mã nhỏ. Với mỗi đoạn mã này, thử giải mã theo mã Caesar với subkey từ 0 -> 25 và tính điểm số này, điểm số càng cao chứng tỏ khả năng key của chúng ta càng chính xác! Nhờ đó xác định được các subkey, suy ra key và tìm ngược lại được bản rõ.

Code

z

le chiffre indéchiffrable (Mật mã không thể phá nổi)

Phép thử Kasiski

Phương pháp dùng chỉ số trùng hợp

… Đang edit …

Bên lề

Mật mã đồng âm, mật mã sách, mật mã âm tiết, mật mã Playfair. Mật mã ADFGVX (trộn giữa thay thế và hoán vị)

Chia sẻ:

• Twitter
• Facebook

Thích Đang tải...

Có liên quan