ThaiDN - Mật mã hiện đại

 Tôi dự tính viết về đề tài này từ cả năm nay, mà mãi tới bây giờ mới có đủ động lực để viết. Có hai lý do khiến tôi bắt đầu.

Thứ nhất, số là tôi đang theo học mật mã, mà kinh nghiệm cho thấy cách học (và đọc sách) tốt nhất là viết, tóm tắt lại và giải thích rành mạch rõ ràng những gì vừa học được cho người khác. Chừng nào làm được như thế thì mới có thể xem là đã hiểu được vấn đề đang muốn học.

Thứ hai, hôm rồi tôi đọc một mẩu chuyện về Richard Feynman, trong đó có đoạn kể về lúc Feynman bị bệnh, gần đất xa trời, ông tâm sự rằng, "[I'm going to die but I'm not as sad as you think because] when you get as old as I am, you start to realize that you've told most of the good stuff you know to other people anyway". Đương nhiên những gì tôi biết làm sao mà "good" bằng những gì Feynman biết, nhưng dẫu sao thì tôi cũng sẽ học theo Feynman, có biết cái gì hay ho thì giải thích cho nhiều người khác cùng biết.

--*--

I. Mở đầu

1. Giới thiệu

Loạt bài này tôi sẽ giới thiệu về mật mã học hiện đại, tập trung vào giải thích cách thức hoạt động của các thành phần mật mã cơ sở (cryptographic primitive) và làm sao sử dụng chúng cho đúng cách.

Mật mã là công cụ rất mạnh mẽ làm nhiều người lầm tưởng rằng cứ sử dụng mật mã là an toàn, mà không biết rằng mật mã là con dao hai lưỡi. Bạn có thể xây dựng một hệ thống với đầy đủ các ý tưởng hay ho nhất của mật mã, nhưng nếu bạn không dùng mật mã đúng cách, hệ thống của bạn sẽ hoàn toàn thiếu an toàn.

Đã có rất nhiều ví dụ, mà tiêu biểu là các kết quả làm việc gần đây của tôi và đồng nghiệp (xem đây, đây và đây). Hoặc như gần đây, hệ thống bảo vệ máy PS3 của Sony bị phá vỡ hoàn toàn chỉ vì sử dụng sai mật mã. Không riêng gì Sony, mà rất nhiều hãng lớn trên thế giới, từ Oracle, Yahoo!, đến Microsoft, đã sử dụng sai mật mã và làm cho sản phẩm của họ thiếu an toàn.

Điều này cho thấy, chỉ biết mật mã giúp gì cho bạn là chưa đủ, mà bạn cần phải biết làm thế nào để sử dụng chúng đúng cách. Khi biết cách sử dụng đúng mật mã rồi, bạn sẽ có thể dùng mật mã để xây dựng các hệ thống an toàn hơn, và đồng thời có thể đánh giá được sản phẩm sử dụng mật mã của bên thứ ba.

Giáo trình mà tôi sử dụng là cuốn sách "Introduction To Modern Cryptography" của Jonathan Katz và Yehuda Lindell (từ đây về sau gọi là KL). Trong quá trình học mật mã, tôi cũng đã đọc thử nhiều sách khác nhau, nhưng cuốn KL này là thích hợp hơn nhất cho việc tìm hiểu mật mã học hiện đại. KL cũng được sử dụng làm giáo trình để dạy mật mã cho cấp đại học và cao học ở nhiều trường đại học trên thế giới. Bạn nào có điều kiện thì nên mua sách. Nếu là sinh viên thì có thể liên hệ với tôi (ở TP.HCM) để mượn sách mà đọc. 

Một cuốn sách miễn phí khác có thể dùng để thay thế KL là cuốn Handbook of Applied Cryptography. Kết thúc mỗi bài viết, tôi sẽ liệt kê trang nào trong KL hoặc HAC cần phải đọc.

Loạt bài được chia làm ba phần lớn. Phần đầu tiên nói về mã đối xứng, phần thứ hai nói về mã bất đối xứng, và phần thứ ba sẽ bàn về các đề tài nâng cao. Trong phần thứ nhất tôi sẽ giải quyết vấn đề: làm thế nào để chị A và anh B liên lạc với nhau an toàn, khi hai người đã có một khóa bí mật chung? Vấn đề của phần thứ hai sẽ là làm thế nào để chị A và anh B chưa quen biết nhau có thể tạo ra một khóa bí mật chung chỉ có hai anh chị biết mà thôi? Trong phần thứ ba, tùy vào tình hình mà tôi sẽ viết về các đề tài như tiền điện tử, bầu cử điện tử hay đấu giá điện tử.

Tôi cũng muốn lưu ý là nội dung loạt bài sẽ có những phần không nằm trong cuốn KL, và tôi sẽ cố gắng để người đọc hiểu được loạt bài này mà không cần phải tham khảo thêm tài liệu khác. Nghĩa là khi nào cần thì tôi sẽ cung cấp các kiến thức hỗ trợ, ví dụ như các kiến thức toán (bao gồm lý thuyết xác suất, lý thuyết số, đại số trừu tượng và một ít lý thuyết độ phức tạp tính toán). Tôi cũng không chắc là tôi làm được (tự vì tôi cũng đang học như bạn mà thôi!), nhưng mà tôi sẽ cố gắng. Mục tiêu của tôi là nếu bạn theo sát loạt bài viết này từ đầu, thì khi kết thúc, bạn sẽ hiểu mật mã học hiện đại hoạt động ra sao, và cách sử dụng chúng như thế nào cho đúng và an toàn.

2. Tại sao mật mã?

Trước khi đi vào nội dung chính của bài viết đầu tiên, tôi muốn dành ra ít phút để thuyết phục bạn là tại sao chúng ta cần phải học mật mã. Cá nhân tôi thấy có ba lý do chính.

Thứ nhất, mật mã là công cụ rất quan trọng, được sử dụng ở mọi nơi. Tôi đồ rằng nhiều bạn dùng mật mã hàng ngày mà lại không biết. Bạn có dùng GMail hoặc có bao giờ mua hàng trên Amazon không? Nếu có thì bạn đã dùng mật mã rồi đó.

Bạn có chú ý là khi bạn vào GMail hoặc Amazon, địa chỉ mà bạn sử dụng bắt đầu bằng HTTPS thay vì HTTP không? Chữ S trong HTTPS là viết tắt của Secure, hiểu nôm na rằng HTTPS là phiên bản an toàn hơn so với HTTP, và sự an toàn này là nhờ vào bộ giao thức mật mã mang tên Secure Socket Layer, phiên bản mới hơn gọi là Transport Layer Security. Nhờ có SSL/TLS mà bạn có thể an tâm giao dịch với Amazon mà không sợ thông tin giao dịch của bạn bị đánh cắp hoặc chỉnh sửa trong quá trình truyền từ máy tính của bạn lên đến máy chủ của Amazon. Nói cách khác, không có mật mã thì đã không có thương mại điện tử rồi!

SSL/TLS được dùng chủ yếu để bảo vệ thế giới web, mà Internet thì đâu chỉ có web. Mật mã còn có thể được sử dụng để đảm bảo an toàn cho email. Email có hai vấn đề cần phải giải quyết. Thứ nhất, làm thế nào để đảm bảo tính riêng tư, tỉ như chị A viết thư cho anh B, thì chỉ có anh B đọc được thư đó thôi, không ai khác đọc được cả. Thứ hai, làm thế nào để hiện thực hóa vấn đề chữ ký trong thư từ thông thường, nói cách khác làm sao để anh B biết chắc là thư đang đọc đến từ chị A, không bị ai sửa chữa giả mạo gì cả, và sau này chị A cũng không thể chối là chị không phải là tác giả của lá thư đó? Đây chính là yêu cầu bắt buộc của khái niệm chữ ký điện tử mà chúng ta thường nghe. Tương tự như SSL/TLS, PGP/OpenPGP là tiêu chuẩn phổ biến nhất để bảo vệ email thông qua các thành tựu của mật mã học.

Nếu bạn là lập trình viên, thì chắc chắn sẽ có lúc nào đó bạn gặp phải vấn đề xác thực người dùng, và lúc đó bạn sẽ cần phải sử dụng mật mã để xây dựng nên một cơ chế quản lý mật khẩu và xác thực người dùng một cách an toàn. Thay vì lưu mật mã trực tiếp xuống cơ sở dữ liệu, nhiều lập trình viên đã biết sử dụng các thuật toán băm một chiều để bảo vệ mật khẩu. Tuy vậy phần lớn trong số đó vẫn sử dụng sai mật mã, khiến cho mặc dù có dùng mật mã, nhưng hệ thống của họ vẫn không an toàn hơn là mấy. Thí dụ như nếu bạn chỉ băm mật khẩu xuyên qua MD5 một lần, thì bạn đã làm sai! Cách làm đúng là phải băm ít nhất 1000 lần, và còn nhiều tiểu tiết khác nữa!

Người ta còn dùng mật mã để bảo vệ các giao thức mạng không dây. Thầy tôi thường nói ông phải cảm ơn những người đã thiết kế ra tiêu chuẩn 802.11i, còn được biết đến là WEP, bởi WEP đã phạm phải mọi sai lầm từng được biết đến trong các sách giáo khoa về mật mã, nên mỗi lần cần đưa ra ví dụ về cách sử dụng sai mật mã, thầy tôi chỉ việc lấy một ví dụ từ WEP! Ông gọi WEP là một giao thức được "thiết kế sau những cánh cửa đóng", đi ngược lại hoàn toàn với tiêu chí mở trong mã hóa (tôi sẽ nói thêm về tiêu chí mở này ở bên dưới). Trong loạt bài này, bạn sẽ thấy ngoài WEP ra còn có rất nhiều giao thức, thuật toán mã hóa được "thiết kế sau những cánh cửa đóng", và tất cả đều không an toàn.

Ngoài những ứng dụng trực tiếp kể trên ra, mật mã còn được sử dụng trong nhiều lĩnh vực có vẻ không liên quan mấy, ví dụ như bầu cử, đấu giá, tiền điện tử hay bảo vệ bản quyền điện tử. Đây là những chủ đề mà bản thân tôi chưa có cơ hội tìm hiểu; dẫu vậy tôi có kế hoạch sẽ tìm hiểu chúng trong tương lai gần. Tóm lại, lý do thứ nhất cần phải học mật mã là vì mật mã rất mạnh mẽ và có thể giúp chúng ta giải quyết nhiều vấn đề tự nhiên đến từ cuộc sống.

Thứ hai, mật mã rất đẹp, đơn giản vì nó là sự giao thoa và ứng dụng của rất nhiều nhánh trong toán học, mà toán đẹp cỡ nào thì khỏi phải bàn rồi phải không? ;-).

Giáo sư Phạm Huy Điển từng viết rất hay như thế này:

Lâu nay không ít người cảm thấy thất vọng vì đã “uổng công” học Toán. Nghe người ta nói thì Toán học là “chìa khóa” cho mọi vấn đề, nhưng trên thực tế thì học sinh sau khi tốt nghiệp lại chẳng biết dùng kiến thức Toán đã học được trong nhà trường vào việc gì trong cuộc sống, nhất là những bài toán khó mà họ đã tốn bao công sức nhồi nhét trong các “lò luyện” đủ loại. Đây là một thực tế, xuất phát từ việc xác định nội dung và phương pháp dạy Toán không hợp lý trong các nhà trường hiện nay. Toán học đã bị biến thành một môn “đánh đố thuần túy”, thay vì một bộ môn khoa học mang đầy chất thực tiễn. Tuy nhiên, còn một lý do khác khiến chúng ta không nhìn thấy được bóng dáng của Toán học trong thực tiễn thường ngày, đó là Toán học ngày nay không mấy khi trực tiếp đi được vào các ứng dụng trong thực tiễn mà thường phải “ẩn” sau các ngành khoa học khác: Sinh học, Môi trường, Tài chính, Kinh tế… và thậm chí ngay cả Công nghệ thông tin, một lĩnh vực có thể xem như là được sinh ra từ Toán học. Đã có những ý kiến nói về sự lãng phí của nguồn nhân lực đang làm Toán hiện nay và không ít người cũng đã tưởng là thật…

May mắn thay, khoa học Mật mã đã góp một phần quan trọng trong việc làm sáng tỏ cái “sự thật oan trái” này. Có thể nói rằng hiếm có lĩnh vực nào mà vai trò của các công cụ Toán học lại được thể hiện rõ ràng đến như vậy. Chính Toán học đã làm nên cuộc cách mạng trong công nghệ mật mã, trước hết là bằng sự hiện thực hóa các ý tưởng về mật mã khóa công khai mà các nhà mật mã chuyên nghiệp đã ấp ủ từ lâu, và sau đó là đưa một số kết quả của Toán học (thuộc loại trừu tượng vào bậc nhất) tiếp cận với các ứng dụng trong thực tiễn.

Bạn nào hồi phổ thông có học chuyên toán chắc hẳn sẽ nhớ đến định lý nhỏ (rất đẹp!) của Fermat phát biểu rằng: nếu là số nguyên tố, thì ta có: . Khi học mật mã, bạn sẽ thấy lại định lý này và nhiều ứng dụng tuyệt vời của nó! Tôi có thể bật mí sơ là hệ mã nổi tiếng RSA được xây dựng dựa trên kết quả của định lý đơn giản này!

Ngoài toán ra, mật mã học hiện đại còn được xây dựng dựa trên lý thuyết trung tâm của khoa học máy tính: lý thuyết độ phức tạp tính toán (mà thiệt ra cũng là toán thôi). Thành ra đối với những người học khoa học máy tính hoặc nói đơn giản là làm IT như chúng ta, tìm hiểu về mật mã là một cách để thưởng thức cái đẹp của khoa học máy tính.

Bạn nào học lý thuyết độ phức tạp tính toán rồi thì đều biết là có những bài toán mà chúng ta chưa biết khó cỡ nào, chỉ biết là sao bao nhiêu năm nghiên cứu, thế giới vẫn chưa tìm ra thuật toán "hiệu quả" để giải. Câu hỏi là có cách nào lợi dụng những bài toán khó đó để phục vụ cho lợi ích của con người? Nghe có vẻ hơi ngược đời đúng không, chưa tìm ra lời giải thì làm sao mà lợi với chả dụng? Thế mà những người tiên phong của mật mã hiện đại đã nghĩ ra cách sử dụng các bài toán khó như thế và chính những ứng dụng độc đáo sáng tạo như thế này làm nên vẻ đẹp của mật mã!

Lý do thứ ba? Tự bảo vệ những quyền con người cơ bản của chính chúng ta!

Ai cũng có quyền có bí mật, và ai cũng có quyền quyết định khi nào và như thế nào họ sẽ tiết lộ bí mật đó cho người khác. Chúng ta kết nối vào Internet để gửi email, đọc blog, mua một món hàng hay công bố một bài viết mới; mỗi một hành động như thế đều có thể được diễn dịch theo nhiều ngữ nghĩa khác nhau, mà mỗi cách diễn dịch đôi khi lại đem đến những thiệt hại không mong muốn cho chính chúng ta. Thành ra cách tốt nhất là hạn chế tiết lộ danh tính, và nếu ẩn danh được thì càng tốt (cá nhân tôi cho rằng, sở dĩ Internet phát triển như ngày nay một phần là vì bản chất ẩn danh của nó, dẫu đây chỉ là một sự ngộ nhận). Hơn nữa, không phải cái gì chúng ta nói, chúng ta viết đều là dành cho tất cả mọi người; đôi khi chúng ta muốn chỉ duy nhất một nhóm vài người có thể đọc và nghe được những ý kiến của chúng ta. Đây là quyền riêng tư. Mời bạn đọc thêm A Cypherpunk's Manifesto.

Ai cũng có quyền tự do ngôn luận, tự do thể hiện, tự do tí toáy, ở ngoài đời thật hoặc ở trên Internet. Chắc hắn không cần phải giải thích, tất cả chúng ta đều biết những quyền này quan trọng như thế nào đối với sự tự do của mỗi cá nhân. Vậy ai muốn xâm hại những quyền con người cơ bản của chúng ta? Tôi nghĩ câu hỏi này là thừa, bởi vì rõ ràng sự tự do của tất cả chúng ta đã, đang và sẽ bị xâm hại. Khi bạn không kết nối vào được Facebook, nghĩa là bạn đã không còn được tự do.

May mắn thay, những thành tựu trong vài chục năm vừa qua của mật mã có thể phần nào giúp tất cả chúng ta đảm bảo được tính riêng tư và sự tự do trong cuộc sống hàng ngày. Tôi hi vọng là qua loạt bài viết này, tất cả các bạn sẽ hiểu được sức mạnh của mật mã, rồi từ đó sử dụng chúng đúng cách để bảo vệ những quyền và lợi ích chính đáng của bản thân.

3. Nguyên lý Kerckhoff

Nguyên lý do ông Kerckhoff phát biểu vào thế kỷ 19 với nội dung như sau:

Một hệ thống mã hóa phải an toàn ngay cả khi tất cả thông tin về hệ thống đó đều đã được công bố ra ngoài. Bí mật duy nhất của hệ thống là một khóa ngắn.

Thực tế cho thấy tất cả các công nghệ mã hóa "thiết kế sau những cánh cửa đóng" đều bị phá vỡ nhanh chóng ngay khi một ai đó "reverse engineer" và công bố thiết kế của chúng. RC4 (dùng để mã hóa mạng không dây), A5/1 (dùng để mã hóa mạng điện thoại GSM), CSS (dùng để mã hóa đĩa DVD), Crypto-1 (dùng để mã hóa các thẻ thanh toán điện tử)... tất cả đều bị phá vỡ trong một thời gian ngắn, kể từ lúc thuật toán bị "reverse engineer".

Thành ra khi sử dụng mật mã, chúng ta sẽ tuyệt đối tuân thủ nguyên lý Kerckhoff này. Nói cách khác, chúng ta chỉ sử dụng những thuật toán, tiêu chuẩn, hệ thống mã hóa mở. May mắn là đã có sẵn rất nhiều thuật toán, tiêu chuẩn và hệ thống mã hóa mở, chúng ta chỉ việc chọn cái thích hợp mà dùng, không cần phải xây dựng lại từ đầu. Tuyệt đối không sử dụng những tiểu chuẩn, thuật toán, hệ thống đóng! Nói cách khác, tránh "security through obscurity".

Mật mã là sân chơi của những ông già bảo thủ ;-), những người luôn đặt ra những điều kiện khó nhất, và rồi cố gắng xây dựng một hệ thống an toàn trong những điều kiện đó. Điều thú vị là họ thành công!

 

 ==============================================

 

 Mới đây mà đã gần 10 tháng kể từ ngày tôi viết phần 1 của loạt bài này. Tôi bắt đầu phần 2 này cách đây cũng khá lâu, nhưng gặp trở ngại khi viết mã LaTex trên Blogger nên cứ chần chừ rồi quên hẳn. Hồi tháng 4, anh Phan Dương Hiệu có viết một bài rất công phu về hành trình 35 năm của mật mã khóa công khai. Hôm nay ngồi đọc lại bài viết rất hay đó tự dưng tôi thấy… nao nao và quyết định là phải viết tiếp loạt bài này. Phần thứ 2 này tôi sẽ điểm lại lịch sử của mật mã. Bạn nào có cuốn KL thì có thể đọc chương 1 và chương 2. Trong hai phần tiếp theo tôi sẽ giới thiệu mã dòng (stream cipher) và mã khối (block cipher).
—-

II. Lịch sử

We stand today on the brink of a revolution in cryptography.

Whitfield Diffie và Martin Hellman đã viết đầy hứng khởi như thế trong bài báo New Directions in Cryptography công bố năm 1976. Quả đúng như vậy. Trước Diffie-Hellman, mật mã là sân chơi của quân đội, chính phủ và những tập đoàn lớn. Nếu tôi không lầm thì công trình nghiên cứu về mật mã duy nhất được phổ biến rộng rãi là cuốn The Codebreakers xuất bản lần đầu năm 1967 của David Kahn. Bài báo của Diffie-Hellman vừa khai sinh ra mật mã khóa công khai, vừa đánh dấu sự bắt đầu của mật mã hiện đại. Trong vòng vài chục năm, mật mã từ một nghệ thuật đã trở thành một ngành khoa học được giảng dạy và nghiên cứu khắp nơi trên thế giới. Các ứng dụng của mật mã không chỉ còn gói gọn trong ngành công nghiệp quốc phòng mà đã hiện diện trong mọi mặt của đời sống hàng ngày (mời bạn xem thêm bài của anh Hiệu). Mật mã hiện đại cũng là đề tài của loạt bài viết này. Tuy vậy, mật mã là một trong những nghệ thuật cổ xưa nhất của loài người với lịch sử hàng ngàn năm và tôi không thể viết về mật mã mà không giới thiệu sơ qua về lịch sử phát triển của ngành. Dẫu vậy, tôi cũng lưu ý là phần giới thiệu dưới đây chỉ là “cưỡi ngựa xem hoa”, bạn nào muốn tìm hiểu ngọn ngành thì nên đọc cuốn The Codebreakers.
Từ xa xưa, mật mã là nghệ thuật giữ bí mật nhằm giải quyết vấn đề truyền thông tin an toàn giữa người gửi và người nhận. Chẳng hạn như nhà vua cần truyền mệnh lệnh cho tướng ngoài mặt trận. Một cách đơn giản là ông ấy viết mệnh lệnh vào một lá thư, rồi gửi cho người đưa tin và người này sẽ đi từ kinh thành ra mặt trận để trao thư. Với cách làm này, ông vua không có cách nào đảm bảo được rằng chỉ có tướng quân mới xem được thư. Người đưa thư có thể phản bội, trao thư cho kẻ thù, hoặc họ cũng có thể bị kẻ thù bắt trên đường đi từ kinh thành ra mặt trận. Để giải quyết vấn đề này, nhà vua có thể sử dụng mã (cipher). Một mã thường bao gồm 2 hàm:

• : lập mã. Hàm này nhận vào một bản rõ (plaintext)  và một khóa (key)  rồi xuất ra một bản mã (ciphertext) .

• : giải mã. Hàm này nhận vào một bản mã và một khóa rồi xuất ra một bản rõ .

Các tài liệu mật mã thường gọi ông vua, tướng quân và kẻ thù trong ví dụ ở trên lần lượt là Alice, Bob và Eve, nên tôi cũng sẽ gọi như thế ở đây. Alice và Bob muốn gửi thông điệp cho nhau và không muốn Eve coi trộm. Để sử dụng được một bộ mã, Alice và Bob phải thống nhất với nhau một khóa mà Eve không biết. Làm sao Alice và Bob làm được điều đó? Chúng ta sẽ cùng đi tìm câu trả lời khi bàn về mã hóa khóa công khai, còn bây giờ cứ giả sử là bằng cách nào đó Alice và Bob đã có chung một khóa như thế.
1. Mã thay thế (substitution cipher)
Lập mã – Giải mã
Ý tưởng của mã thay thế rất đơn giản: thay mỗi ký tự trong bằng một ký tự khác. Quy tắc thay thế chính là khóa , trong đó mỗi khóa là một hoán vị của bảng chữ cái. Ví dụ:

Khóa: (A -> H, B -> N, C -> D, D -> X,..., Z -> Y)
Bản rõ: ABCZ
Bản mã: HNDY

Mã thay thế được sử dụng rộng rãi trong nhiều thế kỷ. Tương truyền rằng Julius Caesar, vị lãnh tụ lừng danh của Đế Chế La Mã, đã sử dụng một loại mã thay thế để bảo vệ tính bí mật của các văn bản quân sự.
Thám mã
Người đầu tiên đưa ra phương pháp phá các mã thay thế là Al-Kindi, một người Ả Rập sống vào thế kỷ thứ 9. Sau khi nghiên cứu kỹ lưỡng cuốn kinh Koran, Al-Kindi đã có một quan sát rất thú vị rằng trong một văn bản đủ dài, mỗi ký tự trong bộ chữ cái Ả Rập sẽ xuất hiện với tần suất tương đương với tần suất mà chúng xuất hiện trong kinh Koran. Nói cách khác, tần suất xuất hiện của các ký tự trong một văn bản là ổn định và điều này đúng không chỉ với tiếng Ả Rập mà còn đúng với tiếng Anh và nhiều ngôn ngữ khác (kể cả tiếng Việt?). Ví dụ như trong tiếng Anh, các ký tự xuất hiện nhiều nhất là “e” (12.7%), “t” (9.1%) và “a” (8.1%). Ngoài ra, tần suất của các bộ hai ký tự (digram) và bộ ba ký tự (trigram) cũng ổn định. Ví dụ như trong tiếng Anh, các bộ hai ký tự xuất hiện nhiều nhất luôn là “th”, “he”, “an” và “in” và bộ ba ký tự phổ biến nhất là “tha”.
Dựa vào quan sát này, Al-Kindi đã đề ra phương pháp thám mã phân tích tần suất (frequency analysis). Ý tưởng là tính tần suất của từng ký tự, từng bộ hai ký tự và từng bộ ba ký tự trong bản mã rồi so sánh các tần suất đó với tần suất chuẩn trong ngôn ngữ của bản rõ. Ví dụ như bản rõ là tiếng Anh và sau khi tính tần suất của các ký tự trong bản mã chúng ta nhận thấy “x” và “m” xuất hiện nhiều nhất thì “x” rất có thể là “e” và “m” có thể là “t”. Bước tiếp theo là thử thay thế “x” bằng “e” và “m” bằng “t” (cũng như các thay thế thích hợp khác) trong bản mã, rồi xem có xác định được từ hoặc cụm từ có nghĩa nào hay không.
Ngoài phương pháp thủ công này, mục 1.3 cuốn KL có mô tả một thuật toán thực hiện thám mã bằng phân tích tần suất hoàn toàn tự động. Lưu ý rằng phân tích tần suất là dạng tấn công chỉ biết bản mã (ciphertext-only attack), nghĩa là chỉ cần nhìn vào bản mã là có thể tìm được khóa và bản rõ. Đây là một tấn công rất yếu nhưng vẫn đủ mạnh để phá mã thay thế.
Bài tập 1: Tính số lượng khóa có thể có của mã thay thế vừa mô tả. Hi vọng con số này sẽ giúp bạn hiểu rằng chiều dài khóa không đảm bảo được sự an toàn của mã và đừng bao giờ xài mã có khóa dài 1 triệu bit .
2. Mã Vigenère
Lập mã – Giải mã
Mã Vigenère được phát minh vào khoảng thế kỷ 16. Mục tiêu của mã Vigenère rất rõ ràng: chống thám mã bằng phương pháp phân tích tần suất. Nói cách khác, tần suất của các ký tự trong bản mã phải khác với tần suất của các ký tự trong bản rõ. Để đạt được mục tiêu này, những người phát minh ra mã Vigenère đã có một ý tưởng rất hay: chọn sao cho (ký hiệu chỉ chiều dài của x) và mỗi ký tự của sẽ được mã hóa bằng một ký tự tương ứng của . Nếu xem mỗi ký tự A-Z tương đương với 0-25 thì lập mã bằng mã Vigenère sẽ là  và giải mã sẽ là , trong đó là bản rõ, là bản mã và là khóa.
Thực tế thì mã Vigenère có khác một chút so với mô tả ở trên của tôi: thay vì dùng một khóa ngẫu nhiên với , người ta dùng một khóa ngắn và lập đi lập lại khóa này cho đến khi dài bằng với bản rõ. Ví dụ như với là “TANCONGNGAY” và là “KHMT” thì mã hóa bằng mã Vigenère sẽ như sau:

Bản rõ: TANCONGNGAY
Khóa: KHMTKHMTKHM
Bản mã: DHZVYUSGQHK

Bài tập 2: Tìm hiểu cách phá mã Vigenère bằng phương pháp phân tích tần suất.

3. Mã máy rôtơ (rotor machines cipher)

Việc phát hiện ra điện năng vào thế kỷ thứ 19 đã dẫn đến sự ra đời của vô vàn máy móc, thiết bị chạy bằng điện và mã máy rôtơ là một trong số đó. Mã máy rôtơ là tên gọi chung của các loại mã mà quá trình lập mã và giải mã được thực hiện bởi các máy rôtơ điện. Mã máy rôtơ nổi tiếng nhất là máy Enigma, được Đức quốc xã sử dụng trong chiến tranh thế giới thứ II. Tôi sẽ không giải thích cơ chế hoạt động của mã máy rô tơ vì chúng ta sẽ không gặp lại mã này. Thay vào đó, chúng ta sẽ cùng điểm lại một chút thành tựu phá mã Enigma của phe Đồng Minh, mà người đóng góp lớn nhất chính là Alan Turing có-tầm-nhìn-thật-ngắn của chúng ta.
Quay lại năm 1940. Lúc này Pháp đã bị quân Hitler chiếm đóng và Anh là quốc gia duy nhất chống lại Phát Xít ở Tây Âu. Khả năng chiến đấu của Anh phụ thuộc vào nguồn hàng viện trợ từ Mỹ và phe Đồng Minh, được chuyển đến đảo quốc bằng những đoàn tàu hộ tống xuyên Bắc Đại Tây Dương. Những đoàn tàu này thường xuyên phải chơi trò “trốn tìm” với đám tàu ngầm U-boat của Hilter, vốn có nhiệm vụ định vị và đánh chìm tất cả những con tàu viện trợ, hòng làm cho Anh kiệt quệ rồi đầu hàng. Ai thắng ai thua trong trò “mèo vờn chuột” này rốt cuộc xoay quanh kết quả của cuộc chiến thông tin: liệu Đức quốc xã có thể định vị tàu hộ tống tốt hơn phe Đồng Minh định vị U-boat hay ngược lại?
Đức thua.
Nhưng lý do chính khiến Đức thất bại chỉ được công bố vào năm 1974: mã của hải quân Đức, chính là một loại mã Enigma, đã bị phá bởi Cục Mật Mã Ba Lan và phương pháp phá mã đã được chuyển đến Anh quốc chỉ vài tuần trước khi Phát Xít xâm lược Ba Lan vào năm 1939. Trong suốt cuộc chiến, quân Đồng Minh luôn định vị được tàu ngầm của Đức rồi hướng các đoàn tàu viện trợ đi vòng qua. Dẫu vậy chính phủ Anh không tiết lộ làm cách nào họ phá được các phiên bản mới của mã Enigma, vốn được điều chỉnh nhiều lần trong suốt cuộc chiến, cho đến tận năm 1996. Thông tin mà chính phủ Mỹ công bố vào năm đó cho thấy ngay khi chiến tranh vừa xảy ra, Alan Turing đã tham gia vào nỗ lực phá mã của Anh quốc ở Bletchley Party, nơi ông trở thành người có đóng góp lớn nhất cho sự phát triển của các kỹ thuật phá mã Engima nhanh và hiệu quả, dựa trên phương pháp của người Ba Lan. Cho đến năm 1945, tất cả các loại mã Enigma của Đức đều có thể bị giải mã trong vòng một hoặc hai ngày. Thành tựu này của Alan Turing và đồng nghiệp được tướng năm sao Dwight D. Eisenhower, chỉ huy tối cao của quân Đồng Minh ở Châu Âu, đánh giá là yếu tố quyết định dẫn đến chiến thắng cuối cùng của quân Đồng Minh.
4. Mã máy tính
Có một chi tiết thú vị mà bây giờ tôi mới nhận ra: giới làm mật mã rất nhạy bén với các phát minh quan trọng của nhân loại. Nếu như thế kỷ 19 họ tạo ra mã máy rôtơ để tận dụng điện năng thì từ giữa thế kỷ 20, họ sáng chế ra các loại mã máy tính để tận dụng… máy tính. Ba loại mã máy tính quan trọng nhất mà chúng ta sẽ tìm hiểu chi tiết trong hai phần tiếp theo là DES, RC4 và AES. Ở đây chúng ta sẽ bàn một chút về lịch sử của DES.
Trong những năm 1970, nhận thấy cần phải có một mã tiêu chuẩn để mã hóa dữ liệu của chính phủ cũng như dùng trong thương mại, Viện Công Nghệ và Tiêu Chuẩn Quốc Gia (NIST) của Mỹ, với sự tư vấn của Cục An Ninh Quốc Gia (NSA), tổ chức một cuộc thi để tìm ra loại mã phù hợp nhất. Cuộc thi lần thứ nhất thất bại thảm hại khi không có mã nào đạt tiêu chuẩn và NIST phải tổ chức thêm một cuộc thi khác vào mùa thu năm 1974. Lần này IBM nộp mã Lucifer, một loại mã được phát triển bởi Horst Fiestel, Don Coppersmith và đồng nghiệp trong thời gian đó. Lucifer là một mã khối, có chiều dài khóa là 128-bit và chiều dài khối là 128-bit, nhưng NSA chỉ chấp nhận Lucifer sau khi thực hiện hai điều chỉnh:

• NSA muốn giảm chiều dài khóa từ 128-bit xuống còn 48-bit. IBM không đồng ý, họ nghĩ tối thiểu phải là 64-bit. Cuối cùng hai bên đều nhượng bộ và chấp nhận khóa có chiều dài 56-bit.

• NSA điều chỉnh lại các hộp thay thế (S-box), một thành phần rất quan trọng trong cấu trúc của Lucifer. Lúc bấy giờ nhiều cryptographer tên tuổi, kể cả bộ đôi ma thuật Whitfield Diffie và Martin Hellman đều lên tiếng phản đối sự điều chỉnh này, vì họ ngờ rằng NSA đã cài một “cửa hậu” vào Lucifer, làm giảm đi sự an toàn của Lucifer. Sự thật về những hộp S-box bí ẩn này chỉ được phơi bày khi phương pháp thám mã vi phân được công bố vào những năm 90 của thế kỷ trước. Lúc bấy giờ người ta mới nhận ra rằng, sự điều chỉnh của NSA thật ra đã làm gia tăng sức mạnh của Lucifer, khiến cho mã này không bị phá vỡ dễ dàng bởi thám mã vi phân.

Với hai điều chỉnh này, Lucifer được NIST chuẩn hóa thành DES. DES và phiên bản cải tiến Triple-DES được sử dụng rất rộng rãi. Hạn chế lớn nhất của DES là khóa quá ngắn và hạn chế lớn nhất của Triple-DES là tốc độ thực thi. Năm 1997, NIST lại tổ chức một cuộc thi để tìm một mã thay thế DES và kết quả là Rijndael, một mã của hai cryptographer người Bỉ chiến thắng và sau đó được chuẩn hóa thành AES. Chúng ta sẽ tìm hiểu chi tiết về AES khi nói về mã khối.
III. Khoa học mật mã
Như chúng ta đã thấy, mật mã có lịch sử kéo dài ngàn hàng năm và đã được sử dụng trong nhiều sự kiện quan trọng của nhân loại. Tuy vậy cho đến tận chiến tranh thế giới II, hầu hết các loại mã mà con người tạo ra đều đã bị phá vỡ hoàn toàn, trừ mã One-Time Pad (OTP), được phát minh năm 1917 bởi Gilbert Vernam, một kỹ sư làm việc ở Bell Labs thuộc AT&T. Dẫu vậy, trong nhiều năm liền, không một ai biết OTP thực sự an toàn đến mức nào, cho đến năm 1949, khi công trình Communication Theory of Secrecy Systems của Claude Shannon được công bố rộng rãi. Trong bài báo đó, Claude Shannon đã đặt nền móng cho lý thuyết mật mã hiện đại khi lần đầu tiên đưa ra định nghĩa toán học của khái niệm an toàn và chứng minh được OTP an toàn theo định nghĩa đó.
Để hiểu công trình của Shannon, trước tiên chúng ta cần định nghĩa khái niệm mã.
1. Định nghĩa mã
Một mã xác định trên là một cặp hai thuật toán “hiệu quả” trong đó:
,
thỏa điều kiện (gọi là điều kiện nhất quán). Có hai điểm cần lưu ý:

• Tôi để chữ “hiệu quả” trong ngoặc kép vì từ này có nghĩa khác nhau với những người khác nhau. Trong định nghĩa này, một thuật toán có thể được xem là “hiệu quả” khi nó có thời gian thực thi và yêu cầu bộ nhớ tương đương với DES.

• Nếu như luôn là thuật toán xác định (deterministic algorithm) thì thường là một thuật toán ngẫu nhiên (randomized algorithm). Nghĩa là thường sử dụng yếu tố ngẫu nhiên như một phần của thuật toán để đảm bảo rằng khi mã hóa hai lần một bản rõ giống nhau, chúng ta sẽ thu được hai bản mã hoàn toàn khác nhau.

Bài tập 3: Quân ta đang ở chiến trường. Mỗi ngày bộ chỉ huy sẽ gửi ra một lệnh cho biết hôm đó quân ta sẽ làm gì. Chỉ có hai lệnh: “TAN CONG” hoặc “PHONG THU”. Do quân địch cũng có thể nghe lén sóng radio, nên để cho an toàn, bộ chỉ huy sử dụng một mã để bảo vệ quá trình gửi và nhận lệnh. Mã này có thuật toán lập mã hoàn toàn xác định, nghĩa là bản rõ giống nhau sẽ tạo ra bản mã giống nhau. Tất cả các lệnh đều được mã hóa bằng cùng một khóa duy nhất. Chứng minh rằng ngay trong ngày thứ hai, quân địch đã có thể đoán trước chiến thuật của quân ta.
2. One-Time Pad (OTP)
Vernam tạo ra mã OTP khi tìm cách cải tiến mã Vigenère, nên ý tưởng của OTP khá giống với ý tưởng của Vigenère mà tôi mô tả ở trên, cụ thể như sau:

• . OTP xem bản rõ là một chuỗi bit “0101010101…” và mỗi khóa là một chuỗi bit ngẫu nhiên có chiều dài bằng với bản rõ.

• Lập mã: . Phép XOR thực chất là phép cộng modulo 2 khi thực hiện trên các chuỗi bit.

• Giải mã: .

Ví dụ:

Bản rõ: 10110010010
Khóa: 01101010101
Bản mã: 11011000111

Chúng ta có thể dễ dàng kiểm chứng rằng OTP thỏa yêu cầu nhất quán của một mã. Một trong những lợi thế của OTP là tốc độ thực thi rất nhanh, còn bất lợi duy nhất là chiều dài khóa phải bằng chiều dài của bản rõ. Bất lợi này làm cho OTP gần như trở thành vô dụng, bởi vì nếu như Alice và Bob đã có một cách để trao đổi khóa an toàn, thì họ đã có thể dùng ngay cách đó để trao đổi bản rõ luôn. Tuy vậy OTP vẫn được sử dụng trong thực tế và chúng ta sẽ còn gặp lại mã này trong bài sau khi bàn về mã dòng. Như đã nói ở trên, trong nhiều năm liền không ai phá được mã OTP nhưng cũng không ai chứng minh được rằng OTP là an toàn. Nhưng… an toàn là gì? Chúng ta đề cập nhiều đến khái niệm này mà không có một định nghĩa cụ thể. Đây là một thiếu sót rất lớn, bởi lẽ chỉ khi nào chúng ta định nghĩa được khái niệm an toàn của mã thì khi đó mật mã mới có thể trở thành một ngành khoa học.
3. Định nghĩa mã an toàn:
Muốn định nghĩa được mã an toàn, trước tiên chúng ta phải xác định được khả năng của kẻ tấn công Eve, nghĩa là xác định Eve có thể thực hiện được dạng tấn công nào. Có nhiều dạng tấn công và chúng ta sẽ tìm hiểu chi tiết về chúng trong các bài tới. Từ đây đến cuối bài, chúng ta sẽ giả định là kẻ tấn công chỉ thực hiện được dạng tấn công yếu nhất là tấn công biết bản mã (ciphertext-only attack) bằng cách nghe lén (eavesdropping). Quay lại câu hỏi chính, thế nào là một mã an toàn? Sau đây là một vài ý kiến phổ biến:

1. Mã an toàn là mã mà Eve không thể lấy được khóa.
2. Mã an toàn là mã mà Eve không thể giải mã toàn bộ bản rõ.
3. Mã an toàn là mã mà Eve không thể giải mã được bất kỳ bit nào của bản rõ.

Định nghĩa thứ nhất là một ngộ nhận thường gặp khi sử dụng mã. Mục tiêu tối thượng của mã là bảo vệ bản rõ, chứ không phải để bảo vệ khóa (bảo vệ khóa cũng chỉ là để bảo vệ bản rõ). Ví dụ như xét là mã cơ sở (identity cipher) với , nghĩa là không làm gì cả, nhưng vẫn an toàn theo định nghĩa thứ nhất vì không có cách nào lấy được khóa.
Định nghĩa thứ hai tốt hơn định nghĩa thứ nhất nhưng rõ ràng vẫn không đạt yêu cầu. Không ai muốn sử dụng một mã khiến kẻ tấn công giải mã được dầu chỉ một bit thông tin. Vậy định nghĩa thứ ba có đạt yêu cầu hay không? Đây là một định nghĩa tốt, dẫu vậy có nhiều trường hợp kẻ tấn công không thu được bất kỳ bit nào của bản rõ nhưng vẫn tính toán được một thuộc tính nào đó của bản rõ và như thế là đủ để phá hủy tính bí mật của bản rõ, ví dụ như ở trường hợp ở bài tập số 3. Nói cách khác, mã an toàn là mã mà kẻ tấn công không tính được bất kỳ hàm nào của bản rõ. Đây là một định nghĩa rất mạnh và chúng ta sẽ còn trở lại định nghĩa này trong thời gian tới. Trong phần tiếp theo chúng ta sẽ tìm hiểu định nghĩa an toàn theo cách của Claude Shannon.
4. An toàn tuyệt đối (perfect secrecy)
Claude Shannon là cha đẻ của lý thuyết thông tin nên định nghĩa mã an toàn của ông cũng mang “màu sắc” lý thuyết này. Shannon cho rằng một mã là an toàn tuyệt đối nếu như bản mã không tiết lộ bất kỳ “thông tin” nào về bản rõ. Để hiểu ý tưởng của Shannon, chúng ta hãy giả định rằng Eve biết được phân bố xác suất trên , nghĩa là Eve biết rõ xác suất được gửi ra ngoài của các bản rõ khác nhau. Ví dụ như Eve biết Alice chỉ gửi một trong hai bản rõ là “TAN CONG” và là “PHONG THU”. Ngoài ra Eve còn biết xác suất mà Alice gửi là 0.6 và xác suất gửi là 0.4. Rồi Eve thấy một bản mã được gửi từ Alice đến cho Bob. Shannon nói rằng mã mà Alice và Bob sử dụng là an toàn tuyệt đối nếu như việc biết thêm không làm thay đổi khả năng của Eve. Nói cách khác, không tiết lộ bất kỳ thông tin gì về bản rõ được gửi đi, bởi vì có biết hay không thì Eve vẫn chỉ biết xác suất Alice gửi là 0.6 và là 0.4.
Để tiện việc chứng minh các bổ đề, chúng ta sẽ không dùng định nghĩa nguyên thủy của Shannon mà sẽ sử dụng một định nghĩa tương đương như sau (xem bổ đề 2.3 cuốn KL):

An toàn tuyệt đối
Một mã trên là an toàn tuyệt đối nếu và chỉ nếu thỏa và , ta có Pr[E(k, ) = c] = Pr[E(k, ) = c], trong đó được chọn ngẫu nhiên (uniformly) từ (ký hiệu là ).

Chúng ta cần điều kiện vì các mã thường tiết lộ chiều dài của bản rõ. Định nghĩa này có thể hiểu như sau: nếu khóa được chọn ngẫu nhiên thì xác suất để mã hóa thành một bản mã nào đó sẽ bằng với xác suất để mã hóa thành chính bản mã đó. Nghĩa là nếu chỉ nhìn vào một bản mã thì không có cách nào biết được nguồn gốc của nó. Nói cách khác, việc quan sát được không giúp cho Eve biết được bản rõ là hay hay với bất kỳ.
Như vậy, định nghĩa của Shannon chỉ ra rằng một mã an toàn tuyệt đối sẽ không thể bị phá bằng tấn công chỉ biết bản mã, bất chấp kẻ tấn công có sức mạnh như thế nào. Đây cũng là một điểm thú vị cho thấy các mã được sử dụng trong các bộ phim Hollywood thường không phải là mã an toàn tuyệt đối, vì nhân vật chính thường giải mã thành công chỉ bằng cách nhìn chằm chằm vào bản mã (ví dụ như John Nash trong phim A Beautiful Mind).
Câu hỏi hiển nhiển bây giờ là: có mã nào là an toàn tuyệt đối hay không? Rất may câu trả lời là có.
4.1 Bổ đề “tin tốt”

OTP là an toàn tuyệt đối.

Chứng minh:
Xét một bản rõ bất kỳ . Với mọi bản mã , ta có . Điều này đúng với nên  và , ta có Pr[E(k, ) = c] = Pr[E(k, ) = c]. Vậy OTP là an toàn tuyệt đối theo định nghĩa.
Như vậy chúng ta đã tìm được một mã an toàn tuyệt đối, loạt bài này coi như đã “thành công tốt đẹp” rồi. Chưa đâu! Còn nhớ ở trên chúng ta nói OTP có một vấn đề làm cho nó trở nên vô dụng đó là chiều dài khóa lớn hơn hoặc bằng chiều dài bản rõ. Shannon chứng minh rằng không chỉ OTP mà tất cả mã an toàn tuyệt đối đều có tính chất này. Tôi gọi đây là bổ đề “tin xấu” bởi lẽ nó làm tiêu tan hi vọng về một sự an toàn tuyệt đối của tất cả chúng ta .
4.2 Bổ đề “tin xấu”

Một mã là an toàn tuyệt đối phải có . Nói cách khác chiều dài khóa phải lớn hơn hoặc bằng chiều dài bản rõ.

Bài tập 5: chứng minh bổ đề “tin xấu”.
Câu hỏi bây giờ là: có cách nào giải quyết khuyết điểm của OTP hay không? Chúng ta sẽ tìm câu trả lời trong phần kế tiếp khi bàn về mã dòng (đọc KL 61-77).