Tìm hiểu về mã hóa cổ điển – w3seo tìm hiểu các hệ mã cổ điển

Bạn đang đọc: Tìm hiểu về mã hóa cổ điển – w3seo tìm hiểu các hệ mã cổ điển

Rate this post

Mật mã đã có từ rất truyền kiếp, cách đây khoảng chừng trên 3.000 năm. Ngay từ khi con người biết sử dụng chữ viết như thể một công cụ trao đổi thông tin thì họ đã có nhu yếu che giấu đi một phần của thông tin và chỉ được cho phép những người nhất định được biết. Lịch sử của mật mã hoàn toàn có thể chia thành hai quy trình tiến độ :

Mật mã cổ điển từ ngày xưa đến giữa thập kỷ 70 của thế kỷ trước.

Mật mã hiện đại bắt đầu từ những năm 1970 đến ngày nay.

Các bài viết liên quan:

Những đặc điểm chính để phân biệt mật mã cổ điển và hiện đại gồm có:

Đối tượng của mật mã cổ điển là những ký tự (có thể là ký tự chữ viết, ký tự số hoặc các ký tự tượng hình) còn đối tượng của mật mã hiện đại là các bit thông tin.

Công cụ thực hiện mật mã cổ điển là thủ công, cơ học hay các máy điện toán đơn giản còn công cụ thực hiện mật mã hiện đại là các máy tính điện tử tốc độ cao.

Ưng dụng của mật mã cổ điển khá hạn hẹp và chủ yếu tập trung vào quân sự còn mật mã hiện đại có miền ứng dụng rộng hơn trong các giao dịch điện tử của đông đảo người dùng.

Và cuối cùng là yếu tố thời gian: mật mã cổ điển có từ lâu đời còn mật mã hiện đại chỉ mới ra đời cách đây bốn thập niên.

Mật mã cổ xưa được thực thi trên những ký tự nên khá đơn thuần và gồm có những kỹ thuật chính sau đây :

Kỹ thuật thay thế các ký tự, bao gồm thay thế tuần tự, thay thế đơn từ và thay thế đa từ.

Kỹ thuật đổi chỗ các ký tự.

Kỹ thuật kết hợp cả thay thế lẫn đổi chỗ các ký tự.

Sau đây tất cả chúng ta sẽ lần lượt khảo sát những kỹ thuật mật mã cổ xưa. Mục tiêu của việc khảo sát và điều tra và nghiên cứu là để có được một cái nhìn tổng quát về kỹ thuật mật mã cổ xưa và xem xét chúng đã được vận dụng như thế nào vào những thuật toán mật mã tân tiến .

Các hệ mã hóa cổ điển

Hệ mã CAESAR

Hơn 2 nghìn năm trước kia, nhà vua La Mã Julius Caesar ( 100 năm trước CN ) đã đề xuất kiến nghị một thuật toán mang tên ông với ý tưởng sáng tạo như sau : Giả sử ta có bảng ký tự 26 vần âm A, B, C, … Z được xếp thành một vòng tròn. Mỗi vần âm trong bản nguồn sẽ được sửa chữa thay thế bởi vần âm thứ ba sau nó để có bản mã .
Ví dụ : Thay mỗi vần âm bởi chữ thứ ba sau nó trong bảng vần âm : MOI NGAY TOI CHON MOT NIEM VUI ( plaintext ) -> PRLQ JDB WRL FKRQ PRW QLHP YXL ( cipher text ) .
Việc thay thế sửa chữa được triển khai dựa trên bảng sau :

Quá trình mã hóa sẽ so sánh từ những ký tự của bản nguồn đến những ký tự của bản mã. Quá trình giải thuật sẽ được triển khai ngược lại .

Nếu việc thay thế được thực hiện không chỉ bởi ký tự thứ 3 sau nó mà là ở một khoảng cách k nào đó khác thì ta sẽ có thuật toán Caesar mở rộng.

Trong trường hợp này, giá trị k sẽ là khóa và phải được giữ bí hiểm. Vì bảng vần âm chỉ có 26 vần âm nên giá trị k chỉ hoàn toàn có thể từ 0 đến 25 ( 0 là trường hợp tầm thường ). Để việc mã hóa hoàn toàn có thể lập trình được, ta sẽ gán những ký tự A, B, C, … bởi những số lượng 0, 1, 2, … như bảng dưới đây :
Khi đó, việc mã hóa và giải thuật được trình diễn dưới dạng công thức toán học như sau :

Ta có: P = C = K = Z26;

Mã hóa : ek(x) = (x + k) mod 26

Giải mã : dk(y) = (y – k) mod 26

Với k = 3 thì đó chính là thuật toán Caesar .

Trong nhiều trường hợp, người ta không sử dụng số k như là khóa mà người ta sử dụng ký tự mã ứng với ký tự nguồn A là khóa. Vậy trong thuật toán Caesar, khóa sẽ là chữ D .

Công cụ mã hóa Ceasar

Thám mã Ceasar

Để thám mã thuật toán Caesar tất cả chúng ta hoàn toàn có thể dùng giải pháp vét cạn, vì khoảng trống khóa chỉ là 26 nên hoàn toàn có thể thuận tiện thử tổng thể khóa. Chúng ta sẽ thử từng khóa cho đến khi nhận được bản nguồn có nghĩa thì hoàn toàn có thể suy ra đó chính là khóa cần tìm .
Một giải pháp khác là nghiên cứu và phân tích tần số Open của vần âm. Trong mỗi ngôn từ, từng vần âm sẽ có tần số Open khác nhau, và ta hoàn toàn có thể thiết kế xây dựng tần số chuẩn cho những vần âm trong ngôn từ đó .
Việc tìm tần số chuẩn của những vần âm hoàn toàn có thể thực thi bằng cách thống kê một tập rất lớn những văn bản của ngôn từ đó, và tính tỷ suất số lượng từng vần âm trên tổng số vần âm của tập những văn bản .
Ý tưởng ở đây là nếu ta có một văn bản đủ dài thì những tần số những vần âm Open trong văn bản đó sẽ gần giống với tần số chuẩn. Đó là thông tin quan trọng để ta hoàn toàn có thể Dự kiến khóa mã hóa .
Ví dụ như trong bảng vần âm tiếng Anh, ta biết chữ E có tần số Open nhiều nhất mà trong văn bản mã chữ G Open nhiều nhất thì hoàn toàn có thể Dự kiến chữ G trong bản mã đã được mã hóa từ chữ E. Từ đó hoàn toàn có thể Dự kiến khóa mật mã là 2 hoặc C.
Trong trong thực tiễn, khi nghiên cứu và phân tích tần số, người ta không sử dụng một vần âm đơn lẻ mà sử dụng cụm vần âm thông dụng hoặc quan hệ của vài vần âm với nhau. Việc nghiên cứu và phân tích tần số vần âm sẽ giúp ta rút gọn số lượng phép thử khóa khi thám mã .

Mã hóa thay thế đơn

Trong thuật toán Caesar lan rộng ra, toàn bộ những ký tự đều di dời một khoảng cách như nhau là k .

Mở rộng thuật toán này, ta sẽ cho các ký tự có thể di chuyển với những khoảng cách khác nhau. Đó chính là kỹ thuật thay thế đơn từ.

Xem thêm: TOP 5 game tư duy trí tuệ cực hấp dẫn để luyện não

Trong trường hợp này, khóa mã hóa sẽ không còn là một số ít nữa mà sẽ là một bộ 26 số từ 0 đến 25, hay, nói khác đi, là một hoán vị của dãy những ký tự A đến Z.
Ví dụ một khóa mã hóa của thuật toán thay thế sửa chữa đơn từ : DKVQFIBJWPESCXHTMYAUOLRGZN. Dựa vào khóa này ta hoàn toàn có thể biết AàD, BàK, … Ví dụ, chuỗi ký tự : THUAT TOAN THAY THE DON TU sẽ được mã hóa với khóa trên thành : UJODU UHDX UJDZ UJF QHX UO .
Như vậy, mỗi khóa của thuật toán sửa chữa thay thế đơn từ là một hoán vị của chuỗi ký tự A đến Z. Khóa dài như vậy nên không thuận tiện nhớ được nó. Để hoàn toàn có thể nhớ được một khóa dài thì người ta thỏa thuận hợp tác một chiêu thức tạo khóa từ một “ từ khóa ” ( key word ) ngắn .
Ví dụ, một khóa sửa chữa thay thế đơn từ hoàn toàn có thể được tạo từ một từ khóa Julius Caesar như sau :

Viết các ký tự của từ khoá liền nhau: JULIUSCAESAR

Tính từ trái qua phải, loại đi các ký tự trùng lắp: JULISCAER

Viết tiếp các ký tự của bảng chữ cái theo thứ tự từ ký tự cuối, ký tự nào đã có rồi thì bỏ qua: JULISCAERTVWXYZBDFGHKMNOPQ

Như vậy là ta đã có một hoán vị 26 ký tự có thể dùng làm khoá

Trên trong thực tiễn, người ta hoàn toàn có thể sử dụng những chiêu thức khác nhau để đổi khác một từ khóa dễ nhớ thành một khóa mã hóa khó nhớ .
Về cơ bản, những biến hóa này đều có những bước như vô hiệu những ký tự trùng trong từ khóa và thêm những ký tự khác cho đủ 26 ký tự. Tuy nhiên, phương pháp thực thi hoàn toàn có thể khác nhau .
Quy trình biến hóa từ khóa thành khóa cần phải được thống nhất giữa người gửi và người nhận. Trong những thuật toán mã hóa văn minh, tiến trình đổi khác từ khóa khởi đầu thành những khóa thực sự dùng để mã hóa thường được công bố công khai minh bạch cùng với thuật toán mã hóa .

Thám mã thay thế đơn

Mỗi khóa là một hoán vị của 26 ký tự nên ta có tổng số 26 ! ~ 4 ´ 1026 khóa. Đây là một số lượng khá lớn so với kỹ thuật vét cạn khóa nên để thám mã, người ta thường sử dụng chiêu thức nghiên cứu và phân tích tần số ký tự Open phối hợp với việc nghiên cứu và phân tích những cụm từ thường hay Open trong tiếng Anh như : THE, AND, FOR, … Với khoảng trống khóa lớn như vậy, giải pháp này sống sót khá lâu .
Các phiên bản của nó được dùng trong những chính phủ nước nhà và quân đội cho đến thời kỳ trung đại. Có thể làm cho chiêu thức này mạnh hơn bằng cách thực thi thay thế sửa chữa mỗi ký tự nhiều lần với nhiều khóa khác nhau .

Kỹ thuật thay thế đa từ

Trong kỹ thuật sửa chữa thay thế đơn từ, mỗi ký tự nguồn đều biến thành một ký tự xác lập dựa vào khóa, không nhờ vào vào vị trí của ký tự đó trong bản nguồn .
Ví dụ, nếu ký tự A đã xác lập là sẽ đổi khác thành D thì tổng thể những ký tự A trong bản nguồn đều biến thành D trong bản mã .
Kỹ thuật sửa chữa thay thế đa từ được cho phép, ví dụ, những ký tự A trong bản nguồn hoàn toàn có thể biến thành những ký tự khác nhau trong bản mã. Ta sẽ xem xét một đại diện thay mặt của kỹ thuật sửa chữa thay thế đa từ với thuật toán do nhà toán học người Pháp Blaise de Vigenere ( 1523 – 1596 ) yêu cầu. Ví dụ, thuật toán hoàn toàn có thể được trình diễn như sau :

Từ khoá là CIPHER được xếp kề nhau: CIPHERCIPHERCIPHER …

Sử dụng chuỗi đó như là tập hợp các khoá để mã hoá các ký tự bản nguồn. Ví dụ bản nguồn là THUAT TOAN THAY THE DA TU thì ký tự T sẽ mã hoá bằng khoá C (dùng mật mã Caesar mở rộng) thành V, ký tự H với khoá I thành P, …

Cuối cùng ta nhận được bản mã: VPJHX KQIC ALRA BWL HR VC Để có thể xác định nhanh kết quả của mật mã Caesar mở rộng,

Vigenere sử dụng bảng sau để tra cứu:

Tuy nhiên, lúc bấy giờ ta không cần tra cứu bằng tay thủ công như thời xưa mà hoàn toàn có thể viết một đoạn mã ngắn để thực thi thao tác này .
Khóa của thuật toán mã hóa đa từ có độ dài bằng độ dài của bản nguồn. Tuy nhiên, việc thiết kế xây dựng khóa ( key ) từ từ khóa ( keyword ) như trên có điểm yếu do việc lặp lại một cách đơn thuần từ khóa. Trên thực tiễn, tất cả chúng ta hoàn toàn có thể dùng một số ít chiêu thức khác nhau để kiến thiết xây dựng khóa .
Vigenere đề xuất kiến nghị sử dụng chiêu thức tạo khóa tự động hóa ( Autokey ) bằng cách sử dụng keyword ghép vào phần đầu của bản nguồn và sử dụng như thể khóa để mã hóa cho bản nguồn .

Ví dụ có thể dùng khoá CIPHERTHUATTOANTHAYTHEDATU để mã hoá bản nguồn THUAT TOAN THAY THE DA TU.

Như vậy mã hóa T dùng khóa C sẽ có hiệu quả là V, H dùng khóa I sẽ có hiệu quả là P., … Ngoài ra, hoàn toàn có thể tạo khóa bằng cách lấy những ký tự khởi đầu từ một vị trí ( trang, dòng ) nào đó trong một cuốn sách xác lập trước. Người ta gọi đó là mã hóa bằng sách ( Book cipher ) .

Thám mã thay thế đa từ(vegenere)

Có thể bẻ khóa Autokey và Book cipher bằng cách nghiên cứu và phân tích tần số những cặp vần âm chính do khóa mã hóa và bản nguồn được viết trên cùng một ngôn từ .
Thay vì sử dụng bảng tần số cho 26 ký tự có độ dài 26 ´ 1, ta sẽ sử dụng bảng tần số 26 ´ 26 vận dụng cho “ tần số Open của ký tự X được mã hóa bởi ký tự Y ”. Một chiêu thức thám mã nữa do nhà mật mã học người Đức Friedrich Kasiski ( 1805 – 1881 ) đề xuất kiến nghị bằng cách tìm kiếm những đoạn lặp lại trong bản mã để Dự kiến độ dài của từ khóa .
Từ đó sẽ xác lập được hàng loạt nội dung của từ khóa bằng chiêu thức thám mã vận dụng cho kỹ thuật thay thế sửa chữa đơn từ .

Mã hóa hoán vị

Về thực chất thì kỹ thuật hoán vị chỗ chính là trường hợp đặc biệt quan trọng của kỹ thuật thay thế sửa chữa. Trong kỹ thuật này, tập hợp những ký tự của bản nguồn sẽ không biến hóa so với bản mã mà chỉ đổi khác vị trí của những ký tự. Có 1 số ít kỹ thuật đổi chỗ đơn thuần như sau :

Đảo ngược từ (Mirror cipher): Các ký tự trong bản mã được viết theo thứ tự ngược lại so với bản nguồn: TOI AN COM à MOC NA IOT

Hình học (Geometric Figure): Viết bản nguồn theo một mẫu và đọc theo mẫu khác.

Đổi chỗ theo hàng (Row Transposition ciphers): Viết bản nguồn theo hàng, hoán vị các cột theo khóa và sau đó đọc lại theo hàng để có được bản mã.

Đổi chỗ lộn xộn (Nihilist cipher): Đổi chỗ cả dòng và cột. Viết thông điệp theo hàng, theo khóa. Để có bản mã, ta đọc từ trái sang phải theo từng hàng, thứ tự hàng được xác định bằng khóa viết theo cột.

Đổi chỗ đường chéo (Diagonal cipher): Viết thông điệp giống như trên và thông điệp theo đường zig-zag để có bản mã.

Khóa của thuật toán đổi chỗ theo hàng chính là số thành phần của khóa và hoán vị của những thành phần đó .

Thám mã mở màn từ việc dự đoán số thành phần đó ( chính là số cột của bảng ). Để làm điều đó, ta tìm kiếm tổng thể những năng lực đổi chỗ trong chu kỳ luân hồi dự kiến để tìm ra mẫu chung ( sử dụng list những cặp, bộ ba, … có nghĩa ) .
Nếu những ký tự hoàn toàn có thể được sắp xếp lại trong một nhóm thì ta thử xem xét việc sắp xếp tựa như trong những nhóm khác. Khi đã tìm được những cụm từ có nghĩa, tất cả chúng ta sẽ đồng thời tìm được thứ tự hòn đảo của khóa và sẽ suy ra khóa .

Mã hóa kết hợp

Trong thực tiễn người sử dụng hoàn toàn có thể tích hợp cả hai kỹ thuật sửa chữa thay thế và đổi chỗ vào trong cùng một thuật toán .
Ví dụ dưới đây cho thấy việc phối hợp đó đã tạo ra một thuật toán mã hóa hiệu suất cao được quân đội Đức sử dụng trong đại chiến quốc tế lần thứ nhất. Đó là thuật toán ADFGVX ( năm 1918 ) .

Thuật toán được mô tả như sau:

Chỉ có sáu chữ cái này được sử dụng để mã hoá dữ liệu và sau đó dữ liệu được truyền đi bằng tín hiệu Morse. Mã MORSE của các chữ này phân biệt rất rõ.

36 ký tự (gồm 26 chữ cái và 10 chữ số) được xếp vào một bảng 6 ´ 6 với tên hàng và cột là các ký tự ADFGVX. Mỗi chữ cái trong bản nguồn được thay bởi một cặp hai chữ cái là chỉ số hàng – cột.

Sử dụng kỹ thuật đổi chỗ cùng với khóa để tách và đổi chỗ các chữ cái. Ví dụ ta cần mã hoá bản nguồn: GIONOSUNGLA530

Theo bảng trên, mỗi ký tự bản nguồn được mã hóa bởi hai ký tự khác, thành : FV XF VD GX VD XG XA GX FV DV GV DX GG VV.

Chuỗi ký tự trung gian này sẽ được mã hoá bằng kỹ thuật đổi chỗ với từ khoá: DEUTSCH (2376514).

Xem thêm: Lịch sử Internet – Wikipedia tiếng Việt

Chuỗi này sẽ được viết vào bảng theo thứ tự từ trái qua phải, từ trên xuống dưới :

Đọc bảng theo cột và khóa ta sẽ nhận được chuỗi mã sau cuối là : DXVV FXGV VVXD GAGV VGDG FXVG XDFX .