Mật mã đã có từ rất lâu đời, cách đây khoảng trên 3.000 năm. Ngay từ khi con người biết sử dụng chữ viết như là một công cụ trao đổi thông tin thì họ đã có nhu cầu che giấu đi một phần của thông tin và chỉ cho phép những người nhất định được biết. Lịch sử của mật mã có thể chia thành hai giai đoạ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ổ điển được thực thi trên các ký tự nên khá đơn giản và bao gồm các 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 chúng ta sẽ lần lượt khảo sát các kỹ thuật mật mã cổ điển. Mục tiêu của việc khảo sát 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ổ điển và xem xét chúng đã được áp dụng như thế nào vào các thuật toán mật mã hiện đại.
Các hệ mã hóa cổ điển
Hệ mã CAESAR
Hơn 2.000 năm trước đây, hoàng đế La Mã Julius Caesar (100 năm trước CN) đã đề xuất một thuật toán mang tên ông với ý tưởng như sau: Giả sử ta có bảng ký tự 26 chữ cái A, B, C, …Z được xếp thành một vòng tròn. Mỗi chữ cái trong bản nguồn sẽ được thay thế bởi chữ cái thứ ba sau nó để có bản mã.
Ví dụ: Thay mỗi chữ cái bởi chữ thứ ba sau nó trong bảng chữ cái: MOI NGAY TOI CHON MOT NIEM VUI (plaintext) -> PRLQ JDB WRL FKRQ PRW QLHP YXL (cipher text).
Việc thay thế được thực hiện dựa trên bảng sau:
Quá trình mã hoá sẽ đối chiếu từ các ký tự của bản nguồn đến các ký tự của bản mã. Quá trình giải mã sẽ được thực hiện 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à khoá và phải được giữ bí mật. Vì bảng chữ cái chỉ có 26 chữ cái nên giá trị k chỉ có thể từ 0 đến 25 (0 là trường hợp tầm thường). Để việc mã hoá có thể lập trình được, ta sẽ gán các ký tự A, B, C,… bởi các con số 0, 1, 2,…như bảng dưới đây:
Khi đó, việc mã hoá và giải mã được biểu 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à khoá mà người ta sử dụng ký tự mã ứng với ký tự nguồn A là khoá. Vậy trong thuật toán Caesar, khoá sẽ là chữ D.
Công cụ mã hóa Ceasar
Thám mã Ceasar
Để thám mã thuật toán Caesar chúng ta có thể dùng phương pháp vét cạn, vì không gian khoá chỉ là 26 nên có thể dễ dàng thử tất cả khoá. Chúng ta sẽ thử từng khoá cho đến khi nhận được bản nguồn có nghĩa thì có thể suy ra đó chính là khoá cần tìm.
Một phương pháp khác là phân tích tần số xuất hiện của chữ cái. Trong mỗi ngôn ngữ, từng chữ cái sẽ có tần số xuất hiện khác nhau, và ta có thể xây dựng tần số chuẩn cho các chữ cái trong ngôn ngữ đó.
Việc tìm tần số chuẩn của các chữ cái có thể thực hiện bằng cách thống kê một tập rất lớn các văn bản của ngôn ngữ đó, và tính tỷ lệ số lượng từng chữ cái trên tổng số chữ cái của tập các văn bản.
Ý tưởng ở đây là nếu ta có một văn bản đủ dài thì các tần số các chữ cái xuất hiện 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 có thể dự đoán khoá mã hoá.
Ví dụ như trong bảng chữ cái tiếng Anh, ta biết chữ E có tần số xuất hiện nhiều nhất mà trong văn bản mã chữ G xuất hiện nhiều nhất thì có thể dự đoán chữ G trong bản mã đã được mã hoá từ chữ E. Từ đó có thể dự đoán khoá mật mã là 2 hoặc C.
Trong thực tế, khi phân tích tần số, người ta không sử dụng một chữ cái đơn lẻ mà sử dụng cụm chữ cái phổ biến hoặc quan hệ của vài chữ cái với nhau. Việc phân tích tần số chữ cái sẽ giúp ta rút gọn số lượng phép thử khoá khi thám mã.
Mã hóa thay thế đơn
Trong thuật toán Caesar mở rộng, tất cả các ký tự đều dịch chuyển 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ừ.
Trong trường hợp này, khoá mã hoá sẽ không còn là một số 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 các ký tự A đến Z.
Ví dụ một khoá mã hoá của thuật toán thay thế đơn từ: DKVQFIBJWPESCXHTMYAUOLRGZN. Dựa vào khoá này ta có thể biết AàD, BàK,… Ví dụ, chuỗi ký tự: THUAT TOAN THAY THE DON TU sẽ được mã hoá với khoá trên thành: UJODU UHDX UJDZ UJF QHX UO.
Như vậy, mỗi khoá của thuật toán thay thế đơn từ là một hoán vị của chuỗi ký tự A đến Z. Khoá dài như vậy nên không dễ dàng nhớ được nó. Để có thể nhớ được một khoá dài thì người ta thoả thuận một phương pháp tạo khoá từ một “từ khoá” (key word) ngắn.
Ví dụ, một khoá thay thế đơn từ có thể được tạo từ một từ khoá 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 thực tế, người ta có thể sử dụng các phương pháp khác nhau để biến đổi một từ khoá dễ nhớ thành một khoá mã hoá khó nhớ.
Về cơ bản, các biến đổi này đều có những bước như loại bỏ các ký tự trùng trong từ khoá và thêm các ký tự khác cho đủ 26 ký tự. Tuy nhiên, cách thức thực hiện có thể khác nhau.
Quy trình biến đổi từ khoá thành khoá cần phải được thống nhất giữa người gửi và người nhận. Trong các thuật toán mã hoá hiện đại, quy trình biến đổi từ khoá ban đầu thành các khoá thực sự dùng để mã hoá thường được công bố công khai cùng với thuật toán mã hoá.
Thám mã thay thế đơn
Mỗi khoá là một hoán vị của 26 ký tự nên ta có tổng cộng 26! ~ 4 ´ 1026 khóa. Đây là một số lượng khá lớn đối với kỹ thuật vét cạn khoá nên để thám mã, người ta thường sử dụng phương pháp phân tích tần số ký tự xuất hiện kết hợp với việc phân tích các cụm từ thường hay xuất hiện trong tiếng Anh như: THE, AND, FOR,… Với không gian khóa lớn như vậy, phương pháp này tồn tại khá lâu.
Các phiên bản của nó được dùng trong các chính phủ và quân đội cho đến thời kỳ trung đại. Có thể làm cho phương pháp này mạnh hơn bằng cách thực hiện thay thế 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 thay thế đơn từ, mỗi ký tự nguồn đều biến thành một ký tự xác định dựa vào khoá, không phụ thuộc vào vị trí của ký tự đó trong bản nguồn.
Ví dụ, nếu ký tự A đã xác định là sẽ biến đổi thành D thì tất cả các ký tự A trong bản nguồn đều biến thành D trong bản mã.
Kỹ thuật thay thế đa từ cho phép, ví dụ, các ký tự A trong bản nguồn có thể biến thành các ký tự khác nhau trong bản mã. Ta sẽ xem xét một đại diện của kỹ thuật 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) đề xuất. Ví dụ, thuật toán có thể được trình bày 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, hiện nay ta không cần tra cứu thủ công như ngày xưa mà có thể viết một đoạn mã ngắn để thực hiện thao tác này.
Khoá của thuật toán mã hoá đa từ có độ dài bằng độ dài của bản nguồn. Tuy nhiên, việc xây dựng khoá (key) từ từ khoá (keyword) như trên có điểm yếu do việc lặp lại một cách đơn giản từ khoá. Trên thực tế, chúng ta có thể dùng một số phương pháp khác nhau để xây dựng khoá.
Vigenere đề xuất sử dụng phương pháp tạo khoá tự động (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ư là khóa để mã hoá 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ã hoá T dùng khoá C sẽ có kết quả là V, H dùng khoá I sẽ có kết quả là P,…Ngoài ra, có thể tạo khóa bằng cách lấy các ký tự bắt đầu từ một vị trí (trang, dòng) nào đó trong một cuốn sách xác định trước. Người ta gọi đó là mã hoá 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 phân tích tần số các cặp chữ cái bởi vì khóa mã hoá và bản nguồn được viết trên cùng một ngôn ngữ.
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 áp dụng cho “tần số xuất hiện của ký tự X được mã hoá bởi ký tự Y”. Một phương pháp thám mã nữa do nhà mật mã học người Đức Friedrich Kasiski (1805-1881) đề xuất bằng cách tìm kiếm các đoạn lặp lại trong bản mã để dự đoán độ dài của từ khoá.
Từ đó sẽ xác định được toàn bộ nội dung của từ khoá bằng phương pháp thám mã áp dụng cho kỹ thuật thay thế đơn từ.
Mã hóa hoán vị
Về bản chất thì kỹ thuật hoán vị chỗ chính là trường hợp đặc biệt của kỹ thuật thay thế. Trong kỹ thuật này, tập hợp các ký tự của bản nguồn sẽ không thay đổi so với bản mã mà chỉ thay đổi vị trí của các ký tự. Có một số kỹ thuật đổi chỗ đơn giả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ã.
Khoá của thuật toán đổi chỗ theo hàng chính là số phần tử của khoá và hoán vị của các phần tử đó.
Thám mã bắt đầu từ việc dự đoán số phần tử đó (chính là số cột của bảng). Để làm điều đó, ta tìm kiếm tất cả các khả năng đổi chỗ trong chu kỳ dự kiến để tìm ra mẫu chung (sử dụng danh sách các cặp, bộ ba,…có nghĩa).
Nếu các ký tự 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ương tự trong các nhóm khác. Khi đã tìm được các cụm từ có nghĩa, chúng ta sẽ đồng thời tìm được thứ tự đảo của khoá và sẽ suy ra khoá.
Mã hóa kết hợp
Trong thực tế người sử dụng có thể kết hợp cả hai kỹ thuật 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 kết hợp đó đã tạo ra một thuật toán mã hoá hiệu quả được quân đội Đức sử dụng trong đại chiến thế giới 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ó sá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ã hoá 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).
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à khoá ta sẽ nhận được chuỗi mã cuối cùng là: DXVV FXGV VVXD GAGV VGDG FXVG XDFX.
Thuật toán này thực tế không an toàn, nó đã bị thám mã bởi quân đội Pháp và đã bị bẻ khoá ngay trong năm 1918.
