Lượt xem: 7121 | Gửi lúc: 02/06/2015 15:05:31
Bookmark and Share

Kỹ thuật thám mã và xu hướng tính toán song song

Những nhà lập mã có không gian rộng lớn để tìm hiểu và triển khai ý tưởng của mình, trong khi những người phá mã bị giới hạn trong thời gian nhất định phải tìm ra thủ thuật mà người lập mã thực thi. Tuy nhiên, với công nghệ hiện đại ngày nay, với việc sử dụng hệ thống máy tính xử lý song song có hiệu năng cao, năng lực thám mã đã tăng lên rất lớn và là thách thức đối với những nhà lập mã.

Bảo đảm tính bí mật và toàn vẹn của thông tin đóng vai trò rất quan trọng trong lĩnh vực chính trị, quân sự của mọi thời đại và cả lĩnh vực kinh tế xã hội trong thời đại số ngày nay. Mật mã và những khoa học liên quan đóng vai trò chính trong việc này. Những người lập mã cố gắng thiết kế những hệ mật “không thể phá được”, còn những người phá mã (mã thám) lại luôn cố gắng để tìm cách giải mã được những bí mật do mật mã đảm bảo.

Lập mã và thám mã trong điều kiện thủ công

Mật mã thường được hiểu một cách phi hình thức gồm một phương pháp mã hóa tổng quát, được gọi là thuật toán và một khóa mã xác định chi tiết chính xác của một quá trình mã hóa cụ thể. Thông thường người ta dùng hai kỹ thuật chuyển vị, thay thế hoặc kết hợp để thành một thuật toán mã hóa. 

Điển hình cho chuyển vị là hệ mật chuyển vị Caesar. Mỗi ký tự bản rõ được thay thế bằng ký tự cũng trong bảng chữ cái đó nhưng đứng cách nó một số vị trí cố định. Tuy đơn giản như vậy nhưng cũng phải rất lâu người ta mới tìm cách phá được nó, nhờ phát hiện tính quy luật của ngôn ngữ: tần suất của từng chữ cái và những kết hợp có thể của các chữ cái trong mỗi ngôn ngữ cụ thể.

Để tránh bộc lộ tần suất, một cải tiến quan trọng, không dịch chuyển theo một số vị trí cố định nữa mà theo một khóa thỏa thuận giữa hai bên (chữ cái đầu chuyển dịch theo chỉ định của ký tự khóa đầu tiên, chữ cái thứ hai chuyển dịch theo chỉ định của ký tự khóa thứ hai,…), được gọi là mật mã Vigenère. Nếu như khóa được chọn ngẫu nhiên và độ dài bằng độ dài bản rõ thì ta đã có được một hệ mật mã không thể phá được. Đó chính là một loại mã duy nhất về lý thuyết chứng minh không thể phá được và là tiền đề cho loại mã dữ liệu do Gilbert Vernam sáng chế ra, gọi là OTP (one-time pad). Tuy nhiên, điều kiện trao đổi khóa là khó khăn, nên thường khóa mã chỉ là một từ với vài ký tự. Do đó, tần số của chuỗi ký tự (bộ đôi, bộ ba,…) vẫn nổi lên và Charles Babbage đã phát hiện ra cách thám. Có lẽ việc tính toán với khối lượng lớn trong cách thám mã đã gợi ý cho Babbage sáng chế ra máy tính cơ khí đầu tiên trên thế giới.

Từ thực tiễn, thuật toán là thành phần tĩnh, khó thay đổi, khóa mã là thành phần dễ thay đổi hơn, Auguste Kerchhoffs đã đưa ra một nguyên tắc vào năm 1883: sự an toàn của một hệ thống mật mã không phụ thuộc vào việc giữ bí mật thuật toán mã hóa. Độ an toàn chỉ dựa vào việc giữ bí mật khóa mã (lập mã và giải mã). Từ nguyên tắc này, các tiêu chuẩn mật mã đã có cơ sở lý luận dẫn dắt. Tuy nhiên, những thuật toán mã hóa được công bố hiện nay cũng chỉ dùng trong lĩnh vực mật mã dân sự, còn trong lĩnh vực an ninh quốc phòng thì vẫn được giữ bí mật.

Lập mã bằng các máy cơ khí và thám mã bằng thiết bị điện tử

Khi điện tín và vô tuyến điện được phát minh, lượng thông tin trao đổi tăng lên đáng kể, do đó để đáp ứng yêu cầu bảo mật, người ta đã không thể chỉ làm thủ công nữa mà cần cơ giới hóa và máy mã ra đời. Một trong những hệ máy mã nổi tiếng nhất là Enigma của Đức, được sáng chế từ cuối thế chiến I và được sử dụng rộng rãi trong thế chiến II. Nó có thiết kế rất phức tạp và người Đức tin rằng không ai có thể phá nổi.

Tuy nhiên, trước áp lực chiến tranh đe dọa tới đất nước, Biuro Szyfrów - Cơ quan an ninh của Ba Lan đã tập trung vào nghiên cứu Enigma. May mắn là họ có được một nhân vật tài năng là Marian Rejewski. Ông đã nghiên cứu ra cách tìm ra khóa được phía Đức sử dụng nhờ một máy điện từ (được gọi là máy “Bom”). Khi thế chiến II nổ ra, Ba Lan bị Đức chiếm đóng, Chính phủ Ba Lan chuyển sang Anh, và kiến thức về Enigma và máy “bom” được trao cho Đồng minh. Trường Mật mã của Chính phủ Anh ở Bletchley Park đã nắm vững những kỹ thuật này. Trong đội mã thám của Anh có nhà toán học Alan Turing, người đã đề xuất ra máy tính Turing vạn năng, đến giờ vẫn là mô hình lý thuyết cho tất cả các phát kiến của khoa học tính toán. Trong quá trình này, người Anh đã đề xuất và sản xuất được những máy tính số điện tử lập trình được đầu tiên trên thế giới. Colossus Mark1 đã vận hành được vào tháng 12/1943, và được sử dụng tại Bletchley Park vào 5/2/1944. Colossus Mark 2 đã đi vào hoạt động 1/6/1944. Tuy nhiên, muốn giữ bí mật, nên các máy “Bom”, Colossus và các thiết kế đã bị hủy sau khi chiến tranh kết thúc (cũng như phát kiến về mật mã khóa công khai sau này vào đầu thập kỷ 70, may mắn là sau đó các nhà toán học Mỹ đã làm được việc tương tự năm 1977). Phiên bản “tái tạo” của Colossus được hoàn thành và đưa vào Bảo tàng tính toán quốc gia ở Bletchley Park năm 2007.

Lập mã và thám mã bằng máy tính điện tử

Từ sau thế chiến thứ II, thời chiến tranh lạnh, cuộc chạy đua về mật mã không được tiết lộ nhiều. Giai đoạn này các máy tính điện tử vạn năng được sản xuất và đưa vào ứng dụng trong mọi lĩnh vực của cuộc sống, và chắc chắn đã được sử dụng vào công việc lập mã và phá mã.

Mật mã hiện đại thường được nói tới với ba sự kiện. Thứ nhất là về lý thuyết, Claude Shanon trong công bố năm 1949 đã thiết lập nền tảng lý thuyết cho mật mã học, định nghĩa độ an toàn của mật mã và chứng minh duy nhất có một loại mật mã không thể phá được là OTP. Thứ hai, về thực tiễn, do phải trao đổi dữ liệu và bảo mật dữ liệu trên các máy tính, nhu cầu chuẩn hóa mật mã ra đời. Từ năm 1975 đã đưa ra yêu cầu và năm 1977 tiêu chuẩn DES được chấp thuận (dựa trên Lucifer do Host Fiestel của IBM đề xuất và sự can thiệp của Cơ quan An ninh quốc gia Mỹ - NSA). Thứ ba là phát kiến vào năm 1977 về loại mật mã mà không cần giữ bí mật khóa mã hóa, chỉ cần giữ khóa giải mã (sau này được gọi là mật mã khóa công khai).

Các tiêu chuẩn mật mã DES và AES đều là các tiêu chuẩn về mã khối với thuật toán mã và giải mã có thể được thực hiện trên máy tính thông thường, thậm chí trên những thiết bị tính toán yếu. Tuy nhiên, để phá mã với phương thức vét cạn (ngay cả với khóa 56 bit của DES) thì khá khó khăn với máy tính thông thường. Nó chỉ được phá với thời gian hợp lý bằng những thiết bị thiết kế chuyên dụng hoặc kết hợp nhiều máy tính. Nếu muốn phân tích số nguyên tố lớn (trong bài toán phá mã RSA) cần huy động một năng lực tính toán rất cao.

Sử dụng tính toán song song trong thám mã

Xu hướng tính toán song song

Vào năm 1945, Von Neumann đã đề xuất kiến trúc máy tính điện tử, trong đó chương trình và dữ liệu được lưu trữ trong bộ nhớ; Các lệnh và dữ liệu được đưa vào bộ xử lý theo chỉ đạo của bộ điều khiển. Về nguyên tắc, chúng được tiến hành tuần tự theo dòng lệnh. Để có thể làm được nhiều công việc (hoặc cùng một công việc nhưng với nhiều dữ liệu khác nhau) người ta phải ghép nhiều bộ xử lý lại thành máy đa xử lý đối xứng (symmetric multiprocessing), hoặc phân công công việc cho các máy tính trên mạng theo kiểu lưới (grid) hoặc phân tán (distributed). 

Những tiến bộ trong lĩnh vực điện tử, đặc biệt là trong lĩnh vực bán dẫn đảm bảo tăng mật độ bóng bán dẫn trong mạch tích hợp lên 2 lần trong khoảng 2 năm (định luật Moore), và đây cũng là tỷ lệ tăng tốc độ xử lý của bộ xử lý tương ứng. Tuy nhiên do tốc độ tăng, nhiệt tỏa ra nhiều và không thể có cách giảm nhiệt tốt, người ta phải tìm xu hướng khác. Đầu tiên về logic, họ tạo nhiều luồng trong bộ xử lý, có thể thực hiện song song một cách logic (ví dụ như Hyper Theading Technology của Intel từ năm 2002). Sau đó người ta phát hiện ra rằng, có thể ghép các nhân (core) xử lý độc lập trong bộ xử lý, có thể dùng chung bộ nhớ (multi-core processor). Từ năm 2005, xu thế tăng tốc độ đã dừng lại và xu thế đa nhân sẽ trở thành chủ đạo trong tiến bộ của bộ xử lý.

Một xu hướng khác là các mạch chuyên dụng được tận dụng để tính toán cho những bài toán đặc thù. Ví dụ như GPU (graphics processing unit) lúc đầu chỉ tăng tốc cho việc xử lý và hiển thị đồ họa, nhưng sau đó đã được cải tiến để phục vụ một số tính toán và trở thành GPU đa dụng (GPGPU- general purpose GPU). Trên những GPU này cũng được tích hợp nhiều nhân và chúng có thể xử lý song song.

Để có thể thực hiện nhiều công việc, hệ điều hành phải điều phối để máy tính phục vụ nhiều người dùng. Lúc đầu, hệ điều hành xử lý theo lô (batch), tuần tự từ công việc này đến công việc khác (như OS/360 của IBM), sau đó thì có thể phân chia thời gian (time-sharing) để phục vụ nhiều người dùng một lúc. Thực chất, đó chỉ là xử lý “giả song song”, máy tính dành cho mỗi công việc một khoảng thời gian theo kiểu xoay vòng. Bắt đầu là đề xuất Multics (Multiplexed Information and Computing Service) của MIT vào năm 1964. Các hậu duệ của Multics là các phiên bản UNIX (kể cả các phiên bản Linux) đều có tính năng này, đồng thời nó còn có thể phân công xử lý song song thực sự giữa các bộ xử lý hoặc các nhân. Microsoft chiếm ưu thế lớn trong lĩnh vực hệ điều hành cho máy tính cá nhân, tuy nhiên những hệ điều hành đầu tiên cho PC như MS-DOS và những phiên bản đầu của Windows chưa thể hỗ trợ đa nhiệm. Chỉ từ Windows 95 thì tính năng đa nhiệm mới được hỗ trợ. Với dòng máy chủ thì từ Windows NT đã hỗ trợ đa xử lý, đa người dùng. 

Đối với các bộ xử lý đa nhân, Microsoft đã hỗ trợ từ nền tảng .NET 2.0 (và C# 2005). Khi đó một thành phần BackgroundWorker được đưa vào để có thể thực hiện một tác vụ (task) trong một luồng độc lập tách biệt với luồng chính. Tuy nhiên, lập trình đó còn khó khăn và các cải tiến liên tục được đưa ra. Từ nền tảng .NET 4.0, khả năng mở rộng song song (.NET Parallel Extensions) được bổ sung, đặc biệt nó cung cấp một thư viện các lớp là Task Paralell Library, cho phép lập trình song song theo tác vụ, một tầng logic cao hơn và dễ sử dụng.

Ứng dụng tính toán song song trong thám mã

Hiện nay, hầu như thiết kế các hệ mật cho mật mã dân sự đã tuân thủ nguyên tắc Kerchhoffs: công khai thuật toán và giữ bí mật khóa. Những thuật toán này thường được cộng đồng phân tích kỹ lưỡng, trao đổi và khắc phục những lỗi thiết kế. Do đó, những cố gắng thám mã khai thác điểm yếu của thuật toán thường không hiệu quả. Gần như chỉ còn cách thám dựa trên vét cạn khóa là khả dĩ. Tuy nhiên, lường trước điều này, các khóa thường được khuyến cáo phải có đủ độ dài cần thiết để các máy tính thông thường trong một thời gian nhất định không thể tìm ra được.

Các cơ quan trong lĩnh vực quốc phòng, an ninh của các chính phủ thường được trang bị những siêu tính, các cụm máy tính, hoặc mạng chuyên dụng để tổ chức mô hình tính toán lưới, hoặc phân tán nhằm phá mã những thông tin họ quan tâm. Các cụm máy tính có tăng cường GPU (thường được gọi là tính toán hiệu năng cao) cũng đã được dùng để phá mã những tệp được bảo vệ bằng mật khẩu. Đó sẽ là xu hướng đa nhân ngày càng phát triển. Nhiều máy tính để bàn đã có thể có bộ vi xử lý tám nhân và sẽ còn tăng lên trong những năm tới. Các hệ điều hành đã có chức năng hỗ trợ đa luồng. Các ngôn ngữ lập trình cho phép người lập trình song song hiệu quả và dễ dàng.

Sự phát triển về khả năng tính toán sẽ là một cơ hội cho những người thám mã và thách thức cho những nhà lập mã trong thời gian tới khi mà máy tính lượng tử chưa được phổ biến.

Tài liệu tham khảo

1. Simon Singh, The Code Book: The Science of secrecy from ancient Egypt to quantum cryptography, Random House Inc., 1999 (Bản dịch của Phạm Văn Thiều, Phạm Thu Hằng, Nhà Xuất Bản Trẻ, 2011).

2. David Padua (Ed.): Encyclopedia of Parallel Computing, Springer, 2011.

3. Thomas Rauber, Gudula Runger: Parallel Programming for Multicore and Cluster Systems, 2nd Ed., Springer, 2013.

4. Rodney Ringler: C# Multithreaded and Parallel Programming, PACKT Publishing, 2014.

5. Phan Đắc Dũng, Dương Nhật Tân, Phạm Hồng Phong, Nguyễn Hữu Đức và Nguyễn Thanh Thủy: Ứng dụng công nghệ tính toán CUDA trong bài toán khôi phục mật khẩu tệp nén Zip, Trung tâm Tính toán hiệu năng cao, Đại học Bách khoa Hà Nội. 


TS. Nguyễn Văn Ngọc, Bộ Công an