[Crypto] 06 – Mã Vigenere

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ã:

Bạn đang đọc: [Crypto] 06 – Mã Vigenere

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ế sửa chữa dùng nhiều bảng vần âm 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 hoàn toàn có thể thực thi mã Vigenere bằng hình vuông vắn Vigenere :
Các dòng được tô đậm tương ứng với những vần âm 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 vần âm 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 vần âm như trên, khoảng trống 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, khoảng trống khóa sẽ tăng theo hàm số mũ. Bảng sau cho ta thấy khoảng trống khóa ứng với chiều dài khóa :
Nếu key gồm 14 kí tự thì khoảng trống khóa là > 6.1019. Con số quá lớn cho thuật toán Brute-force hoàn toàn có thể thao tá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ế khoảng trống khóa rất nhiều, tuy nhiên nó vẫn đủ để làm bạn bó tay nếu giải thuật bằng Brute-force .
Nhưng, điều đáng nói của mã Vigenere không phải ở khoảng trống khóa lớn của nó, nên nhớ mã thay thế sửa chữa đơn thuần có khoảng trống khóa là 26 ! > 4 x 1026. Điểm đáng bàn là ở chỗ : mỗi kí tự của bản rõ hoàn toàn có thể được mã hóa thành nhiều kí tự khác nhau nên bản mã sẽ mất đi đặc thù mẫu từ và đặc thù 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 chiêu thức nghiên cứu và phân tích mẫu từ và nghiên cứu 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ì tất cả 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 thuận tiện dùng Brute-force để crack nó bằng cách cho key lần lượt là những từ trong file dictionary.txt và giải thuật 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, đó hoàn toàn có thể là 1 dãy kí tự ngẫu nhiên, và ta phải tìm cách phá nó. Bước tiên phong ta cần xác lập 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

Xem thêm: Mã hóa video hiệu quả cao – Wikipedia tiếng Việt

Nhận xét : những 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ú ý quan tâm 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 thù của mã Vigenere. Do đó nếu ta tìm được những cụm từ lặp lại thì năng lực 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 những khoảng cách trên. Như vậy trong trường hợp này chiều dài khóa hoàn toàn 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 những kí tự thứ 1, 5, 9, 13, … Bản thử 2 chứa những 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 đó vận dụng phép nghiên cứu và 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 Open 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ị ( biến hóa vị trí những 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ị những kí tự của bản rõ. Như vậy hoàn toàn có thể vận dụng phép nghiên cứu và 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 thuật 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ỏ năng lực key của tất cả chúng ta càng đúng chuẩn ! Nhờ đó xác lập được những 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 hề 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ế sửa chữa và hoán vị )
Advertisement

Chia sẻ:

• Twitter
• Facebook

Thích bài này:

Thích

Xem thêm: Giáo án dạy học Toán 11 theo định hướng phát triển phẩm chất năng lực – https://thomaygiat.com

Đang tải …

Có liên quan

Source: https://thomaygiat.com
Category : Kỹ Thuật Số