Mật mã Caesar

Bách khoa toàn thư mở Wikipedia
Bước tới điều hướng Bước tới tìm kiếm
Nguyên tắc của mật mã Caesar là văn bản mã được tạo ra bằng cách thay thế mỗi chữ cái trong văn bản với một chữ cái cách nó một đoạn cho trước trong bảng chữ cái. Trong ví dụ trên độ dịch là 3.

Trong mật mã học, Mật mã Caesar, còn được biết đến với những cái tên Mật mã của Caesar, Mật mã chuyển vị, Mã của Caesar hay Chuyển vị Caesar, là một trong những kỹ thuật mã hóa đơn giản và phổ biến nhất. Đây là một dạng mật mã thay thế, trong đó mỗi ký tự trên văn bản thô sẽ được thay bằng một ký tự khác, có vị trí cách nó một khoảng xác định trong bảng chữ cái. Ví dụ với độ dịch chuyển là 3, D sẽ trở thành A, E sẽ trở thành B, v.v. Tên của kỹ thuật mã hóa này được đặt theo tên của Julius Caesar, người đã sử dụng nó trong các thư từ bí mật của mình.[1]

Bước mã hóa được thực hiện trong mật mã Caesar thường được kết hợp như một phần của các dạng mã hóa phức tạp hơn, chẳng hạn như mật mã Vigenère, và hiện nay vẫn được áp dụng cho mã hóa ROT13. Cũng giống như tất cả các dạng mật mã thay thế một bảng chữ cái khác, mật mã Caesar rất dễ bị phá giải và về cơ bản không đáp ứng đủ khả năng bảo mật thông tin liên lạc trong thực tế hiện đại.

Ví dụ[sửa | sửa mã nguồn]

Mô tả cách thay thế các ký tự trong một bộ mật mã Caesar có thể thực hiện bằng cách sắp hai bảng chữ cái trên hai hàng song song với nhau; bảng chữ cái mật mã sẽ là bảng chữ cái thô đã được dịch sang trái hoặc sang phải một số vị trí. Ví dụ, dưới đây là một bộ mật mã Caesar được thiết lập bằng phép dịch sang trái 3 vị trí, tương đương với phép dịch sang phải 23 vị trí (con số vị trì dịch này được sử dụng làm khóa mã):

Thô:     ABCDEFGHIJKLMNOPQRSTUVWXYZ
Mật mã:  DEFGHIJKLMNOPQRSTUVWXYZABC

Khi tiến hành mã hóa, người gửi mật mã sẽ tra cứu từng ký tự của tin nhắn gốc trên dòng "thô" và sau đó viết ra ký tự tương ứng lấy từ dòng "mật mã".

Văn bản thô:     THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
Văn bản mật mã:  QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD

Quá trình giải mã của người nhận mật mã được thực hiện ngược lại, với thao tác dịch sang phải 3 vị trí.

Mã hóa cũng có thể được biểu diễn thông qua số học mô đun, bằng cách gán các ký tự bằng các con số, theo tuần tự, A → 0, B → 1, ..., Z → 25.[2] Mã hóa một chữ cái x bằng phép dịch chuyển n vị trí có thể mô tả bằng biểu thức toán học sau:[3]

Giải mã được mô tả tương tự,

(Có nhiều định nghĩa cho phép toán Modulo. Trong trường hợp trên, kết quả phải nằm trong khoảng từ 0 đến 25. Do đó nếu x+n hoặc x-n không nằm trong đoạn 0...25, ta phải cộng hoặc trừ nó với 26.)

Loại mã hóa này có các giải pháp thay thế của từng ký tự là không đổi trong suốt quá trình mã hóa tin nhắn, vì vậy nó được xếp vào dạng thay thế một bảng chữ cái, khác với thay thế nhiều bảng chữ cái.

Lịch sử và ứng dụng[sửa | sửa mã nguồn]

Mật mã Caesar được đặt theo tên của Julius Caesar, người đã sử dụng dạng mã hóa này với phép dịch chuyển 3 vị trí.

Mật mã Caesar được đặt theo tên của Julius Caesar. Theo Suetonius, Caesar đã sử dụng dạng mã hóa này với phép dịch chuyển 3 vị trí (A trở thành D khi mã hóa và D trở thành A khi giải mã) để bảo vệ các thông điệp có ý nghĩa quân sự. Dù rằng theo các ghi chép, Caesar là người đầu tiên áp dụng mật mã Caesar, người ta còn biết tới các loại mật mã thay thế khác được dùng từ trước đó nữa.[4][5]

"Nếu có điều gì bí mật muốn nói, ông viết chúng bằng mật mã. Bằng việc thay đổi thứ tự bảng chữ cái, ông khiến người khác nghĩ rằng những ký tự ấy là không thể đọc được. Nếu ai đó muốn giải mật mã để lấy nghĩa của thông điệp, họ phải dịch chuyển từ chữ cái thứ tư, ấy là D và thay bằng chữ A, và cứ thế tiếp tục với các chữ cái khác." — Suetonius, Cuộc đời Julius Caesar 56

Cháu trai Caesar là Augustus cũng sử dụng mật mã, nhưng bằng cách sử dụng ký tự thay thế nằm ngay bên phải, và không quay ngược lại đầu bảng chữ cái:

"Bất cứ khi nào viết mật mã, ông sẽ thay chữ B cho chữ A, C cho B và các chữ cái còn lại theo cùng một nguyên tắc, riêng với chữ Z thì sử dụng AA để thay thế." — Suetonius, Cuộc đời Augustus 88

Có bằng chứng cho thấy Julius Caesar đã sử dụng các bộ mã phức tạp hơn,[6] một tác gia có tên Aulus Gellius từng đề cập tới một chuyên luận (hiện đã thất lạc) về mật mã của Caesar:

"Thậm chí còn có một chuyên luận khá tài tình của nhà ngữ pháp Probus, liên quan đến ý nghĩa bí mật của các chữ cái trong những bức thư tín của Caesar." —  Aulus Gellius, Attic Nights 17.9.1–5

Không thể đánh giá chính xác mức độ hiệu quả của mật mã Caesar vào thời điểm đó, nhưng có thể nó đã mang lại sức bảo mật đáng kể, đặc biệt là vì hầu hết kẻ thù của Caesar đều mù chữ và số còn lại thì cho là các thông điệp được viết bằng một thứ ngoại ngữ không xác định.[7] Lúc này, vẫn chưa có bất cứ ghi chép nào về kỹ thuật phá giải các loại mật mã thay thế đơn giản. Những bằng chứng sớm nhất còn sót lại về phương pháp thám mã Caesar có niên đại từ khoảng thế kỷ thứ 9, đó là các công trình của Al-Kindi trong thế giới Ả Rập, với việc khám phá ra phương pháp phân tích tần suất.[8]

Mật mã Caesar với phép dịch chuyển một vị trí được sử dụng ở mặt sau của mezuzah để mã hóa tên của Chúa. Đây có thể là vật được lưu giữ từ trước khi người Do Thái không được phép có mezuzah. Bản thân các chữ cái của mật mã đã chứa đựng "tên vị thần" mang ý nghĩa tôn giáo mà tín ngưỡng Do Thái giáo chính thống cho là có thể kiểm soát được các thế lực quỷ dữ.[9]

Vào thế kỷ 19, phần quảng cáo cá nhân trên các tờ báo đôi khi là nơi người ta sử dụng để trao đổi những thông điệp mã hóa, sử dụng các bộ mã đơn giản. Kahn (1967) mô tả về các trường hợp mà những cặp đôi tham gia đối đáp bí mật với nhau bằng cách dùng mật mã Caesar trên tờ The Times.[10] Ngay cả vào cuối năm 1915, mật mã Caesar vẫn được sử dụng khi quân đội Nga thay thế nó cho những dạng mật mã phức tạp hơn, vốn tỏ ra quá khó đối với họ; thế nhưng các nhà phân tích mật mã người Áo và người Đức lại rất dễ dàng phá giải các tin nhắn mã hóa của quân đội Nga.[11][12]

Cấu trúc của hai đĩa quay với mật mã Caesar có thể được sử dụng trong cả việc mã hóa lẫn giải mã.

Ngày nay, chúng ta có thể tìm thấy mật mã Caesar trong các trò chơi dành cho trẻ em, chẳng hạn như vòng giải mã bí mật. Thuật toán ROT13 là một mật mã Caesar với độ dịch chuyển 13, nó được sử dụng để làm xáo trộn các văn bản được tìm thấy trên Usenet và dùng để che mờ đoạn văn (như đoạn cuối của câu chuyện cười hay phần tiết lộ nội dung câu chuyện), nhưng không được dùng như một phương pháp mã hóa nghiêm túc.[11]

Mật mã Vigenère sử dụng mật mã Caesar với độ dịch chuyển khác nhau tại mỗi vị trí trong văn bản; giá trị của mỗi khóa mã được xác định bằng một từ khóa lặp lại. Nếu từ khóa có dung lượng bằng tin nhắn, được chọn ngẫu nhiên, không bị người khác biết đến và không bao giờ được sử dụng lại, thì đây là dạng mật mã một lần, được chứng minh là không thể phá giải. Điều kiện trên khó tới mức gần như không bao giờ đạt được. Những từ khóa ngắn hơn tin nhắn (ví dụ: "Complete Victory" được Liên minh miền Nam sử dụng trong Nội chiến Hoa Kỳ), tạo ra một dạng mật mã tuần hoàn có thể phá giải bằng cách thực hiện phân tích tần suất với thống kê nâng cao.[13]

Tháng 4 năm 2006, trùm Mafia Bernardo Provenzano bị bắt ở Sicilia khi đang trên đường chạy trốn, một phần vì các thông điệp bị phá giải của ông ta được viết bằng một biến thể vụng về của mật mã Caesar. Mật mã của Provenzano sử dụng các con số, trong đó "A" được viết là "4", "B" là "5", v.v.[14]

Năm 2011, Rajib Karim bị kết án ở Vương quốc Anh về "tội khủng bố" sau khi sử dụng mật mã Caesar để liên lạc với các nhà hoạt động Hồi giáo Bangladesh, thảo luận về âm mưu làm nổ máy bay hoặc phá vỡ mạng CNTT của British Airways. Mặc dù các bên có quyền tiếp cận các kỹ thuật mã hóa tốt hơn nhiều (bản thân Karim đã sử dụng PGP để lưu trữ dữ liệu trên đĩa máy tính), nhưng họ vẫn chọn bộ mã của riêng mình (được triển khai trên Microsoft Excel), khước từ một bộ mã phức tạp hơn có tên Mujahedeen Secrets, "bởi vì các 'kaffir' hay những kẻ ngoại đạo biết về nó, nên sẽ kém bảo mật hơn". Suy nghĩ trên khiến họ tạo một trình ứng dụng an ninh qua trạng thái mập mờ.[15]

Giải mã[sửa | sửa mã nguồn]

Độ

dịch

Bản thô ứng viên
0 >exxegoexsrgi
1 dwwdfndwrqfh
2 cvvcemcvqpeg
3 buubdlbupodf
4 attackatonce
5 zsszbjzsnmbd
6 yrryaiyrmlac
...
23 haahjrhavujl
24 gzzgiqgzutik
25 fyyfhpfytshj

Mật mã Caesar rất dễ bị phá, ngay cả trong trường hợp người giải mã chỉ có trong tay các bản mật mã. Có hai tình huống được xem xét:

  1. người giải mã biết (hoặc đoán) rằng một số dạng mật mã thay thế đơn giản đã được sử dụng, nhưng không biết cụ thể đó là mật mã Caesar;
  2. người giải mã biết chính xác mật mã Caesar được sử dụng, nhưng không biết giá trị khóa mã.

Trong trường hợp đầu tiên, mật mã có thể phá giải bằng các phương pháp tương tự như đối với các dạng mật mã thay thế đơn giản nói chung, chẳng hạn như phân tích tần suất hay phân tích các từ mẫu.[16] Khi phân tích, có khả năng người giải mã sẽ nhanh chóng nhận thấy tính quy tắc trong giải pháp thay thế và suy ra rằng kỹ thuật mã hóa được dùng là mật mã Caesar.

Biểu đồ phân bố các chữ cái trong một mẫu văn bản tiếng Anh điển hình có hình dạng đặc biệt và dễ đoán. Phép dịch chuyển Caesar "xoay" biểu đồ này và có thể xác định bằng cách xem xét biểu đồ.

Trong trường hợp thứ hai, công việc giải mã thậm chí còn nhẹ nhàng hơn. Vì số khóa mã có khả năng được sử dụng là giới hạn (25 khóa mã đối với bảng chữ cái tiếng Anh), mỗi khóa mã có thể được kiểm tra lần lượt bằng kiểu tấn công vét cạn. Một cách để thực hiện là thử giải một đoạn trích nhỏ của bản mật mã với tất cả các khóa mã có thể, và viết lên trên một bảng,[17] đôi khi gọi là "giải mã một phần bản thô".[18] Ví dụ với đoạn mật mã "EXXEGOEXSRGI"; bản thô có thể nhìn ra ngay lập tức với phép dịch bốn vị trí.[19] Còn có một cách khác, đó là với mỗi chữ cái của bản mật mã, toàn bộ bảng chữ cái sẽ được sắp theo thứ tự ngược lại, bắt đầu từ chữ cái đó. Tăng tốc cho phương pháp bằng việc chuẩn bị trước một tập hợp các dải chữ cái được viết theo thứ tự ngược lại. Sau đó, căn chỉnh các dải để tạo thành các bản mật mã được viết trên từng dòng, trong đó sẽ có một dòng chính là bản thô.

Chúng ta cũng có thể tấn công vét cạn bằng cách so phân phối tần suất của từng chữ cái. Cụ thể, với việc vẽ biểu đồ tần suất của mỗi chữ cái trong bản mật mã, và biết trước phân phối dự kiến của các chữ cái trong ngôn ngữ gốc của bản thô, người giải mã có thể dễ dàng tìm ra độ dịch vị trí bằng cách xem xét sự dời chỗ của các đặc điểm cụ thể trên biểu đồ. Đây gọi là phân tích tần suất. Ví dụ, trong ngôn ngữ tiếng Anh, tần suất các chữ cái E, T, (thường là phổ biến nhất) và Q, Z (thường là ít thường xuyên nhất) là dấu hiệu đặc trưng.[20] Máy tính có thể làm điều này bằng cách so gần khớp phân phối tần suất thực tế với dự kiến, ví dụ như sử dụng phương pháp kiểm định chi bình phương.[21]

Đối với bản thô viết bằng ngôn ngữ tự nhiên, thường sẽ chỉ có một cách giải mã hợp lý, mặc dù đối với những bản thô quá ngắn, có thể có nhiều đáp án khác nhau. Ví dụ, bản mật mã MPQY có thể giải mã thành "aden" hoặc "know" (giả sử bản thô là tiếng Anh); tương tự, "ALIIP" thành "dolls" hoặc "wheel"; và "AFCCP" thành "jolly" hoặc "cheer" (xem thêm khoảng cách unicity).

Với mật mã Caesar, việc mã hóa một bản thô nhiều lần chồng chéo không gia tăng thêm khả năng bảo mật. Điều này do khi thực hiện hai mã hóa, ví dụ, mã hóa khóa A rồi tiếp tục mã hóa khóa B, tương đương với việc thực hiện một mã hóa khóa (A + B) duy nhất. Theo thuật ngữ toán học, tập hợp các phép tính mã hóa trong mỗi khóa có thể tạo thành một nhóm dưới hàm hợp.[22]

Xem thêm[sửa | sửa mã nguồn]

Thư mục[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

  1. ^ Suetonius, Vita Divi Julii 56.6
  2. ^ Luciano, Dennis; Gordon Prichett (tháng 1 năm 1987). “Cryptology: From Caesar Ciphers to Public-Key Cryptosystems”. The College Mathematics Journal 18 (1): 2–17. JSTOR 2686311. doi:10.2307/2686311. 
  3. ^ Wobst, Reinhard (2001). Cryptology Unlocked. Wiley. tr. 19. ISBN 978-0-470-06064-3. 
  4. ^ “Cracking the Code”. Central Intelligence Agency. Truy cập ngày 21 tháng 2 năm 2017. 
  5. ^ Singh, Simon (2000). The Code Book. Anchor. tr. 289-290. ISBN 0-385-49532-3. 
  6. ^ Reinke, Edgar C. (tháng 12 năm 1962). “Classical Cryptography”. The Classical Journal 58 (3): 114. 
  7. ^ Pieprzyk, Josef; Thomas Hardjono; Jennifer Seberry (2003). Fundamentals of Computer Security. Springer. tr. 6. ISBN 3-540-43101-2. 
  8. ^ Singh, Simon (2000). The Code Book. Anchor. tr. 14–20. ISBN 0-385-49532-3. 
  9. ^ Alexander Poltorak. “Mezuzah and Astrology”. chabad.org. Truy cập ngày 13 tháng 6 năm 2008. 
  10. ^ Kahn, David (1967). The Codebreakers. tr. 775–6. ISBN 978-0-684-83130-5. 
  11. ^ a ă Wobst, Reinhard (2001). Cryptology Unlocked. Wiley. tr. 20. ISBN 978-0-470-06064-3. 
  12. ^ Kahn, David (1967). The Codebreakers. tr. 631–2. ISBN 978-0-684-83130-5. 
  13. ^ Kahn, David (1967). The Codebreakers. ISBN 978-0-684-83130-5. 
  14. ^ Leyden, John (19 tháng 4 năm 2006). “Mafia boss undone by clumsy crypto”. The Register. Truy cập ngày 13 tháng 6 năm 2008. 
  15. ^ “BA jihadist relied on Jesus-era encryption”. The Register. 22 tháng 3 năm 2011. Truy cập ngày 1 tháng 4 năm 2011. 
  16. ^ Beutelspacher, Albrecht (1994). Cryptology. Mathematical Association of America. tr. 9–11. ISBN 0-88385-504-6. 
  17. ^ Leighton, Albert C. (tháng 4 năm 1969). “Secret Communication among the Greeks and Romans”. Technology and Culture 10 (2): 139–154. JSTOR 3101474. doi:10.2307/3101474. 
  18. ^ Sinkov, Abraham; Paul L. Irwin (1966). Elementary Cryptanalysis: A Mathematical Approach. Mathematical Association of America. tr. 13–15. ISBN 0-88385-622-0. 
  19. ^ Beutelspacher, Albrecht (1994). Cryptology. Mathematical Association of America. tr. 8–9. ISBN 0-88385-504-6. 
  20. ^ Singh, Simon (2000). The Code Book. Anchor. tr. 72–77. ISBN 0-385-49532-3. 
  21. ^ Savarese, Chris; Brian Hart (15 tháng 7 năm 2002). “The Caesar Cipher”. Truy cập ngày 16 tháng 7 năm 2008. 
  22. ^ Wobst, Reinhard (2001). Cryptology Unlocked. Wiley. tr. 31. ISBN 978-0-470-06064-3. 

Liên kết ngoài[sửa | sửa mã nguồn]


Mật mã cổ điển
Mật mã: ADFGVX | Affine | Atbash | Khóa tự động | Hai chiều | Sách | Caesar | Dvorak | Bốn hình vuông | Hill | Chuyển vị | Chuồng heo | Playfair | Đa ký tự | Reihenschieber | Khóa di động | Thay thế | Dịch chuyển | Ba chiều | Hai hình vuông | Vigenère

Phân tích mã: Phân tích tần suất | Chỉ số trùng hợp | Phép thử Kasiski
Linh tinh: Mật mã | Bảng Polybius | Gậy | bảng kiểm tra Straddling | Tabula recta