Mật mã thường được nhắc tới như là mặt trận hoạt động thầm lặng của con người. Tuy nhiên, trong lịch sử mật mã đã xảy ra không ít biến cố sinh tử, như sự kiện Mỹ tuyên chiến trong Chiến tranh thế giới thứ I sau khi bức điện Zimmermann bị lộ, vụ Midway khi Mỹ đã thám được mật mã của Nhật Bản và giành được chiến thắng giòn giã trên thực địa, vụ đánh đứt đường giao thông sinh tử của Nhật và diệt các tàu ngầm Đức…. Vang dội nhất là sự kiện Alan Turing giải được máy mã Enigma, được đánh giá là lý do rút ngắn Chiến tranh thế giới thứ II được 1 năm. Các chuyên gia còn cho rằng, chiếc máy Turing Bombe do ông và đồng nghiệp chế tạo để giải máy mã Enigma của Đức chính là thế hệ máy tính đầu tiên trên thế giới. Ngày nay, thuật toán Shor giải bài toán phân tích số cũng được coi là đột phá thúc đẩy nghiên cứu và chế tạo máy tính lượng tử.

Đôi nét về mật mã

Trong số các phương thức để bảo vệ thông tin thì mật mã đóng vai trò vô cùng quan trọng. Mật mã là kỹ thuật biến đổi thông tin dưới dạng rõ (đọc hiểu) thành thông tin dưới dạng mã mà bất kì ai không có thẩm quyền đều không thể đọc hiểu thông tin đó.

Lịch sử cho thấy, con người đã biết sử dụng các phương pháp mật mã từ rất sớm. Các tài liệu của Ấn Độ, Ai Cập và La Mã cổ đại là minh chứng cho thấy mật mã đã được sử dụng từ rất lâu, với các phương thức đa dạng và ở nhiều lĩnh vực khác nhau, thậm chí để mã hoá các đơn thuốc chữa bệnh. Trong những năm tháng “tăm tối” của thời kỳ Trung cổ, thực tiễn hoạt động mã hoá được giấu kín, thậm chí các nhà mật mã còn bị thủ tiêu sau một thời gian làm việc. Đến thời kỳ Phục Hưng, mật mã lại được hồi sinh. Có thể nói nếu như nghệ thuật, thi ca được phát triển nở rộ nhờ cuộc sống lao động sản xuất và chính nhu cầu nội tại của đời sống tinh thần con người, thì mật mã được thúc đẩy bởi các cuộc đấu tranh chính trị, quân sự và ngoại giao diễn ra không ngừng.

Trong thế kỷ XV - XVI, mật mã đã được sử dụng rộng rãi tại Châu Âu, nơi diễn ra sôi nổi các hoạt động chính trị, quân sự và ngoại giao. Chính những cuộc đấu tranh sôi động này đã sinh ra những thiên tài toán học và mã thám như Viete (Pháp), Bazier, Babbage, Kasiski (Đức). Đến thế kỷ XVIII - XIX thì mật mã đã trở thành một ngành công nghiệp thực thụ khi mỗi quốc gia Châu Âu đều thành lập các các ban mật mã và các phòng mã thám, thường được gọi là “phòng đen”. Thế kỷ XX được đánh dấu bằng hai cuộc chiến tranh thế giới với hàng trăm cuộc xung đột vũ trang và cuộc chiến tranh lạnh kéo dài gần nửa thế kỷ, kéo theo sự phát triển vượt bậc của mật mã. Cũng chính trong thế kỷ này, mật mã đã trở thành ngành khoa học thực sự nhờ phát minh của nhà toán học kiêm kỹ sư lỗi lạc người Mỹ C. Shannon. Ông đã vận dụng khái niệm độ bất định (entropy) trong vật lý học để xây dựng khái niệm toán học về độ mật và lý thuyết các hệ mật. Ông cũng là người đã đặt nền móng cho khoa học về thông tin.

Sự phát triển vượt bậc của khoa học tính toán những năm 50 và 60 của thế kỷ XX đã tạo tiền đề cho sự ra đời mật mã hiện đại. Đặc biệt, cuộc cách mạng tin học và sự ra đời của mạng truyền thông máy tính vào nửa cuối thế kỷ XX đã thúc đẩy sự ra đời của mật mã khoá công khai. Nhờ mật mã khoá công khai mà mật mã đã xâm nhập sâu rộng vào các lĩnh vực kinh tế - xã hội, là yếu tố không thể thiếu để đảm bảo an toàn cho các hoạt động giao dịch điện tử nói chung và thương mại điện tử nói riêng trên phạm vi toàn thế giới.

Máy mã Enigma

Enigma là máy mã đã đi vào lịch sử. Việc thám mã Enigma thành công đã trở thành một trong những sự kiện vang dội nhất của Chiến tranh thế giới thứ II và theo đánh giá của các chuyên gia, sự kiện này đã rút ngắn chiến tranh được một năm.

Enigma được một kỹ sư người Đức là Arthur Scherbius thiết kế phát minh đầu tiên vào năm 1918. Những phiên bản đầu tiên được sử dụng trong thương mại vào năm 1923. Đến năm 1926, Hải quân Đức là lĩnh vực vũ trang đầu tiên sử dụng Enigma. Năm 1928, quân đội Đức sử dụng Enigma phiên bản G, sau đổi thành Enigma I vào năm 1930. Enigma I chỉ đư­ợc sử dụng trong các tổ chức vũ trang và các cơ quan chính phủ tr­ước và trong Chiến tranh thế gi­ới thứ II. Nhìn chung, thời điểm trước Chiến tranh thế giới thứ II, máy mã Enigma đã được triển khai rộng rãi trong các lực lượng vũ trang và các cơ quan chính phủ Đức và còn được các nước Đồng minh là Ý và Nhật sử dụng.

Enigma là máy cơ điện, có cấu tạo từ bốn bộ phận chính: Bàn phím, bảng các phích cắm (plugboard), bảng đèn (lampboard) và hệ thống các rotor. Hệ thống rotor là phần trung tâm của Enigma, có số lượng rotor từ 3 trở lên và được đánh số bằng chữ La mã (I, II, II, IV, V,…) để phân biệt lẫn nhau. Mỗi rotor là một đĩa tròn dẹt có bánh răng, trên mỗi mặt có một vòng 26 chữ cái với các điểm tiếp xúc tạo thành mạng lưới truyền tín hiệu điện. Mỗi điểm tiếp xúc của mặt này được nối với một điểm tiếp xúc của mặt kia theo một quy tắc nhất định. Mỗi rotor có một kiểu nối khác nhau, phiên bản dùng trong thương mại khác với phiên bản dùng trong quốc phòng. Các rotor được sắp xếp theo một thứ tự và được bố trí sao cho các điểm tiếp xúc ở mặt “đầu vào” của chiếc này được nối với mặt “đầu ra” của chiếc tiếp theo, đầu ra của chiếc cuối được nối với mặt đầu vào của chiếc đầu. Khi tín hiệu đầu ra từ rotor cuối trở lại rotor đầu tiên, thì tín hiệu rơi vào điểm tiếp xúc nào, đèn báo tương ứng với điểm tiếp xúc đó sẽ bật sáng và đó chính là bản mã của ký tự đầu vào. Khoá mã của Enigma được thay đổi hàng ngày, do đó người ta sử dụng một tài liệu hỗ trợ được gọi là codebook (sách mã hóa), trong đó ghi danh mục khoá được thiết lập hàng ngày. Trong quân sự, mạng liên lạc mật Enigma được chia thành các mạng con khác nhau và mỗi mạng sử dụng một phiên bản riêng của Enigma.

Công việc hàng ngày của các nhân viên sử dụng Enigma như sau: Đầu tiên, thiết lập trạng thái của máy theo chỉ dẫn của codebook để đưa máy vào trạng thái hoạt động. Khi có bức điện cần mã hoá được chuyển từ người chỉ huy, các nhân viên thiết lập trạng thái ban đầu cho các rotor (trạng thái này có thể theo dõi trên ấy sổ của máy), sau đó lần lượt ấn các chữ cái của bức điện. Mỗi chữ cái trong bức điện sẽ được mã hoá bởi khoá mật mã, từng chữ cái của bản mã sẽ hiện lên trên bảng đèn. Nhân viên chỉ cần ghi lại bản mã và truyền đi qua thiết bị thông tin. Vì hệ mật mã sử dụng trong Enigma là đối xứng nên để giải điện, nhân viên tại đầu nhận chỉ cần thực hiện ngược lại quy trình trên. Khoá mật mã của Enigma được cấu tạo từ bốn thành phần:

- Lựa chọn các rotor và thứ tự của chúng (ví dụ, trong tập các rotor, chọn các rotor I, III, IV và sắp đặt chúng từ trái sang phải theo thứ tự III, IV, I).

- Trạng thái ban đầu của các rotor (do nhân viên chọn, thay đổi theo từng bức điện).

- Các cài đặt vòng (ring settings) của rotor – trạng thái của các vòng chữ cái liên quan đến kết nối rotor.

- Trạng thái phích cắm – các kết nối của các phích cắm trên bảng phích cắm.

Cuộc chiến thám mã Enigma và sự ra đời của máy tính điện tử thế hệ đầu tiên

Khoá mã là yếu tố quan trọng nhất đảm bảo an toàn cho một máy mã. Đối với Enigma, con số khóa mã có thể có lên đến 26!26!25!13!. Đây là số khổng lồ với hơn 90 chữ số không tận cùng. Bởi vậy, nếu một nhà mã thám có trong tay một siêu máy tính có khả năng kiểm tra một tỷ khả năng trong một giây, thì phải mất một vài tỷ năm mới tính hết mọi khả năng của khóa Enigma. Điều đó có nghĩa là việc rà soát lại toàn bộ không gian khoá là việc không thể thực hiện được ngay cả bằng các phương tiện tính toán của ngày nay.

Từ khi Enigma được đưa vào khu vực quân sự, ngay lập tức nó trở thành đối tượng của các các cơ quan tình báo thông tin, trước hết là của Anh, Pháp và Mỹ, tuy nhiên việc thám mã Enigma vẫn chưa thành công. Vào thời gian này, cơ quan mật mã của Ba Lan cũng vào cuộc. Song phải đợi đến tháng 9/1932 khi chàng sinh viên 27 tuổi Marian Rejewski cùng hai người bạn từ đại học tổng hợp Poznan là Henryk Zygalski và Jerzy Rozycki - những người anh hùng tương lai trong công cuộc chinh phục enigma - gia nhập Ban mật mã, thì việc thám mã Enigma của Ba Lan mới bước vào giai đoạn mới.

Tháng 12/1932, Ban mật mã Ba Lan đã nhận được từ đại uý Gustav Bertrand của cơ quan tình báo quân sự Pháp một số tài liệu, trong đó đặc biệt có hai trang sử dụng khoá Enigma do cơ quan tình báo quân sự Pháp lấy được từ phía Đức. Những trang khoá này đã cho phép giảm được một số lượng lớn ẩn số trong các phương trình mà Rejewski thiết lập để giải Enigma. Để hiểu được ý nghĩa của sự kiện này, cần lưu ý rằng trong mã thám, nếu số lượng khoá mã lớn thì rất ít khi các nhà mã thám sử dụng lối tấn công vét cạn, tức lần lượt thử tất cả các khoá mã. Đối với Enigma, cách làm này lại càng không thể thực hiện được. Vì vậy, các nhà mã thám thường tìm mọi thông tin liên quan, nhất là những sơ suất trong khi sử dụng máy, những bối cảnh của bức điện và kể cả phương pháp đánh cắp để lấy được các thông tin bên lề, đây là những dữ liệu quý giá để giảm lượng tính toán đến mức có thể thực hiện được. Đối với việc thám mã Enigma cũng không là ngoại lệ. Sơ suất đầu tiên và tự nhiên nhất là người Đức luôn sử dụng cuốn sổ ghi chép bản rõ và bản mã của chúng, cũng như khoá đã sử dụng. Khi cuốn sổ này lọt vào tay đối phương, đây là tư liệu lý tưởng để dựa vào đó khôi phục lại toàn bộ hoặc từng phần khoá mã. Marian Rejewski đã thực hiện một tấn công quan trọng nhất trong lịch sử mật mã bằng cách sử dụng lý thuyết nhóm sơ cấp để giải các kết nối và cài đặt bên trong rotor của Enigma. Sau khi Rejewski tái tạo lại cấu trúc của máy Enigma, ngư­ời Ba Lan đã giải mã được một phần rất đáng kể các cuộc liên lạc qua Enigma được người Đức thực hiện trong tháng 12/1938. Người Ba Lan còn tiến xa hơn khi chế tạo được các thiết bị dò khoá là Cyclometer, Zygalski sheets và đặc biệt là máy dò khóa “Polish Bombe” do Rejewski chế tạo. Những thiết bị này đã tạo hỗ trợ rất lớn trong việc giải được một số lượng điện mật nhất định của Đức.

Tháng 6/1939, ba tháng trước khi Đức Quốc xã chính thức tấn công Ba Lan, hiểu đ­ược xu hướng chính trị ở Châu Âu, Bộ Tổng tham mưu ­Ba Lan quyết định chia sẻ những thành tựu thám mã Enigma với Đồng minh. Hai bộ máy mã Enigma đư­ợc chuyển tới Paris, cơ quan tình báo quân sự Pháp giữ lại một chiếc, chiếc thứ hai gửi cho cơ quan tình báo Anh. Tại Anh, vào thời kỳ đó đã có máy tính cơ học nhưng còn rất thô sơ và không có khả năng sử dụng để thám các loại máy mã có độ phức tạp cao như Enigma. Các phương pháp thám mã cổ điển do những nhà ngôn ngữ tiến hành cũng không giải quyết được vấn đề. Cơ quan tình báo thông tin của Anh và các nước Đồng minh hiểu rất rõ điều đó, nên họ đã bắt đầu huy động các nhà toán học vào cuộc. Tại trường mật mã của Anh, nơi trước đó công việc mã thám chủ yếu do các nhà nghiên cứu ngôn ngữ đảm nhiệm thì nay được bổ sung các nhà toán học làm việc trong lĩnh vực lý thuyết số. Nhà toán học Alan Turing được chỉ định đứng đầu nhóm giải mã Enigma, lúc đó ông mới 27 tuổi và đã có những công trình lý thuyết nổi tiếng về khoa học tính toán.

Sau khi được người Ba Lan chuyển giao các kỹ thuật thám mã Enigma, trong đó có máy dò khoá Polish Bombe, các nhà mã thám Anh đã kết hợp nhiều giải pháp lại với nhau, nên trong những năm đầu của thập niên 1940, cơ quan mã thám của Anh đã thu được nhiều thông tin hết sức quan trọng của Đức. Các bức điện giải mã này có mật danh là “Ultra” và được đích thân Thủ tướng Churchill trực tiếp nghiên cứu. Ông đã gọi những bức điện này là “những quả trứng vàng”. Nền tảng trong kỹ thuật được Turing và các nhà mã thám Anh sử dụng là các Crib - thuật ngữ đư­ợc họ sử dụng để chỉ một đoạn điện rõ đã biết hoặc được dự đoán ở tại một vị trí nào đó trong bản điện mã. Nguồn của Crib là các bản đã đư­ợc giải mã tr­ước đó, bao gồm những biệt ngữ quân sự Đức và những câu nói hoặc đoạn văn khuôn mẫu; các bản ghi chép tỉ mỉ phân tích các phiên liên lạc trên từng tuyến liên lạc như tần số vụ tuyến, thời gian chặn bắt các bức điện….

Tuy vậy, thành tích của những quả trứng vàng thật ra còn khiêm tốn khi chỉ chiếm một tỷ lệ nhỏ trong số các bức điện chặn bắt được và chỉ tập trung vào một số mặt trận. Hơn nữa, phía Đức cũng thường xuyên cải tiến máy Enigma cũng như phương thức sử dụng, gây nhiều khó khăn cho cơ quan mã thám của Anh. Nước Anh lại tiếp tục chịu nhiều thiệt hại do không giải được các bức điện mật. Vào giữa năm 1942, dựa trên ý tưởng của Polish Bombe, Turing đã nghiên cứu ra sơ đồ máy điện từ có khả năng tái lập vị trí cài đặt của các rotor. Máy có chức năng mô phỏng tác động của các rotor bằng các trống quay. Các trống quay này rà soát mọi vị trí có thể của các rotor chỉ trong vài giây, nhanh hơn nhiều so với Polish Bombe. Với sự hỗ trợ của máy này, người Anh đã giải được nhiều bức điện quan trọng.

Thuật toán Turing dò tìm vị trí rotor của máy Enigma đòi hỏi phải tua đi tua lại nhiều lần bản điện rõ và điện mã. Nó được thực hiện nhờ một rơle để lưu các dữ liệu và một tập lệnh lặp. Thiết bị này có những yếu tố của máy tính điện tử ngày nay. Đến cuối năm 1943, Turing lại tiếp tục cải tiến Polish Bombe thành chiếc máy có tên là Colus hay Turing Bombe. Đó là chiếc máy tự động lập trình thực hiện các phép tính số học và logic trên hệ nhị phân. Có thể nói, với Colus, cơ quan thám mã Anh đã được trang bị phương tiện tính toán hiện đại nhất thời bấy giờ và đó là chiếc máy tính điện tử đầu tiên trên thế giới. Trên thực tế, trước chiến tranh, Turing đã có ý tưởng về một chiếc máy tính tưởng tượng, mà ngày nay giới học thuật được biết đến với cái tên là máy Turing. Nhưng việc tham gia giải mã Enigma đã tạo điều kiện cho ông kết hợp ý tưởng này với thực tế và thúc đẩy sự ra đời nhanh chóng của của máy tính hiện đại.

Thám mã hệ mật RSA thúc đẩy nghiên cứu và chế tạo máy tính lượng tử

Ý tưởng chế tạo máy tính lượng tử được đưa ra bởi nhà vật lý người Mỹ R. P. Feynman và nhà toán học người Nga I. Manin vào đầu những năm 80 của thế kỷ XX, với mục tiêu ban đầu là phục vụ cho việc mô hình hóa các hệ thống cơ học lượng tử. Vấn đề liệu các thiết bị lượng tử có thể giải được các bài toán nào đó hiệu quả hơn máy tính cổ điển không, lần đầu tiên được Manin đề cập trong cuốn “Tính được và không tính được” xuất bản năm 1980 và Feynman trong bài giảng “Mô hình hóa vật lý trên máy tính - đã hình thành những cơ sở đầu tiên cho tính toán lượng tử”.

Từ đó, hình thành ba hướng nghiên cứu: hướng thứ nhất mang tính hàn lâm, trong đó các nhà nghiên cứu cố gắng phát triển lý thuyết thông tin Shanon sang lĩnh vực tin học lượng tử; hướng thứ hai, làm rõ những hạn chế mà cơ học lượng tử đặt ra cho các thiết bị lượng tử và hướng thứ ba chỉ ra tiềm năng, cũng như ưu thế tính toán của máy tính lượng tử. Mặc dù đây là những chủ đề khoa học hấp dẫn, tuy nhiên trong suốt thập kỷ 80, trừ một số thành tựu về lý thuyết thì gần như không đạt được bước tiến nào đáng kể trong việc trả lời câu hỏi chính: Ưu thế của máy tính lượng tử là gì? Những lớp bài toán nào mà máy tính lượng tử có thể giải quyết còn máy tính cổ điển thì không?

Đầu những năm 90 của thế kỷ XX, bắt đầu xuất hiện một số kết quả theo hướng này: David Deutschи và Richard Jozsa đã chỉ ra một lớp bài toán đặc thù mà máy tính lượng tử thể hiện tính vượt trội. Một thuật toán khác – thuật toán Simon đã giải bài toán tìm chu kỳ của hàm số trong thời gian tuyến tính thay vì thời gian mũ của các thuật tóan cổ điển.

Thuật toán Simon đã làm cơ sở để Shor phát minh ra thuật toán lượng tử mang tên ông vào năm 1994. Thuật toán Shor giải được bài toán phân tích số và bài toán logarit rời rạc, nền tảng của mật mã khóa công khai hiện đại. Đây là một phát minh có tính đột phá thực sự, bởi nó đã chứng minh về nguyên tắc ưu thế tính toán của máy tính lượng tử và thực sự làm động lực cho việc chế tạo máy tính lượng tử. Nó còn thúc đẩy các nhà mật mã khẩn trương tìm kiếm các hệ mật mã có khả năng chống lại máy tính lượng tử.

Nhiều học giả cho rằng, phát minh ra lửa và máy hơi nước và phát minh máy tính đã tạo thành ba phát minh vĩ đại nhất trong lịch sử loài người. Nikita Moiseev – Nhà toán học kiêm học giả Xô Viết lỗi lạc đã giải thích sự vĩ đại ấy như sau: Nếu hình dung cả nhân loại như một cơ thể, thì phát minh ra lửa đã đưa cơ thể đó từ hoang dã lên văn minh, máy hơi nước đã bổ sung vào cơ thể đó hệ thống cơ bắp, còn máy tính cho nó bộ óc. Đánh giá này đã gián tiếp ghi nhận vai trò của mật mã trong việc thúc đẩy một trong những phát minh vĩ đại nhất của con người.