Tìm hiểu việc phân tích mật mã đối xứng bằng phương pháp đại số

14:34 | 03/01/2010 | GP MẬT MÃ
Việc thiết kế và phân tích các hệ mã đối xứng bằng phương pháp đại số đã xuất hiện từ rất sớm, nhưng phải đến những năm cuối thế kỷ XX thì nó mới được quan tâm nhiều. Đặc biệt là từ giai đoạn đề xuất, tuyển chọn Tiêu chuẩn mã hóa tiên tiến - AES thì phương pháp đại số được phát triển nhanh chóng. Một số báo cáo hỗ trợ cho các ứng cử viên AES đã coi việc ngăn chặn tấn công đại số như những tiêu chí đánh giá độ an toàn của mã khối do mình đề xuất.



Chúng ta đều biết rằng, một mã khối hay một mã dòng bao gồm nhiều thành phần, việc thực hiện theo quy trình mỗi thành phần đó trong quá trình mã hóa nhiều khi không phải là việc thực hiện một đa thức đại số, cho nên việc mã hóa theo quy trình lại càng không phải là trực tiếp tính toán một hay nhiều đa thức. Ý tưởng chính của phân tích đại số là viết lại hệ mật dưới dạng tập các phương trình đại số. Bản rõ, bản mã và khóa được kết hợp chặt chẽ vào các phương trình, trong đó các bit khóa là những ẩn số đối với nhà mã thám.
Trong thực tế đã xảy ra tình trạng sau: Với mật mã không đối xứng (mật mã khóa công khai), chẳng hạn hệ mã Mc Elice, hệ mật được biểu diễn dưới dạng một hệ phương trình đại số bậc nhất có số ẩn nhiều hơn số phương trình là k. Nghĩa là người ta muốn bắt buộc nhà mã thám tìm khóa trong một không gian k chiều. Đối với mật mã đối xứng, tình hình diễn ra dường như ngược lại. Người ta có thể thu được hệ phương trình vượt mức xác định từ một hệ mật, nghĩa là số phương trình có thể vượt trên số ẩn rất nhiều. Điều lo ngại rằng hệ thống các phương trình này vô nghiệm sẽ không xảy ra bởi các phương trình này đều được rút ra từ một hệ mật với cùng một khóa (ta biết trước rằng, hệ phương trình này luôn có nghiệm, đó chính là khóa cần tìm).
Ta hãy điểm qua việc biểu diễn mã khối đã cho dưới dạng một tập các  phương trình. Đã có một số phương pháp thực hiện điều này: Chẳng hạn, người ta sử dụng đa thức nội suy Lagrange biểu diễn sự phụ thuộc giữa bản rõ và bản mã dưới dạng một đa thức trên cơ sở biết một số cặp rõ/mã tương ứng. Một phương pháp khác là diễn tả mỗi thành phần của mã khối bằng một tập các phương trình đại số. Tổng hợp tất cả các phương trình này lại chúng ta sẽ nhận được một hệ rất lớn các phương trình, chúng xác định hoàn toàn mã khối về mặt toán học.
Với phần lớn mã khối, Hộp S là nguồn phi tuyến duy nhất và các phương trình mô tả Hộp S sẽ là trở ngại chính ngăn cản việc giải hệ mật một cách dễ dàng. Với kích cỡ thực tế của bất kỳ Hộp S nào, người ta có thể dễ dàng tìm ra một hệ các đa thức nhiều biến độc lập tuyến tính làm cơ sở cho các đa thức nhiều biến, nó tạo ra không gian của tất cả các phương trình có thể giữa các bit đầu vào và các bit đầu ra. Trong không gian này người ta sẽ tìm tập các phương trình càng đơn giản càng tốt nhưng vẫn xác định hoàn toàn Hộp S. Trong một số trường hợp, tập tối ưu các phương trình này trên GF(2) có thể là vượt mức xác định, tùy thuộc vào bản chất đại số của Hộp S. Đó là trường hợp của Rijndael và Serpent với kích thước nhỏ (4 bit) của các hộp thế.
Không thể thực hiện tìm kiếm vét cạn trên tất cả các tập phương trình có thể, thậm chí đối với các Hộp S nhỏ. Vì vậy, người ta hạn chế tìm kiếm đối với các hệ chỉ chứa những phương trình từ cơ sở. Sự hạn chế này tạo ra các hệ đủ đơn giản đối với các Hộp S nhỏ, mặc dù những kết quả này nhanh chóng giảm giá trị khi kích cỡ của Hộp S tăng lên. Tuy nhiên, trong thực tế nhiều Hộp S lớn được rút ra từ các hàm đại số đơn giản và điều này thường trực tiếp dẫn đến các hệ đa thức đơn giản. Mặc dù vậy, không có gì đảm bảo rằng các hệ phương trình đó là tối ưu nên các kết quả đưa ra ở đây phải được coi chỉ là xấp xỉ. Do đó, cách hiệu quả để tìm hệ tối ưu cho các Hộp S bất kỳ vẫn là bài toán mở.
Nếu có thể giải được hệ này (tấn công đại số) nhanh hơn tìm kiếm khóa vét cạn thì có thể coi như mã khối đã bị phá vỡ. Có thể chúng ta nghĩ rằng hệ các phương trình đại số là những vấn đề đã được nghiên cứu từ rất lâu và rất kỹ nên không còn gì để nghiên cứu nữa. Tuy nhiên vẫn cần tiếp tục nghiên cứu để giải bài toán mật mã này và thực tế đã có nhiều nghiên cứu mới để giải các hệ đại số được lập ra theo kiểu này.
Trước hết người ta tìm cách giải hệ các phương trình bậc hai. Phương pháp cơ bản để giải hệ các phương trình bậc hai được gọi là tuyến tính hóa. Trong phương pháp này, mỗi số hạng của phương trình bậc hai được thay thế bằng số hạng tuyến tính mới và hệ trở thành tuyến tính. Tuy nhiên, phương pháp này đưa vào nhiều số hạng mới mà việc tìm ra lời giải duy nhất bằng cách sử dụng các phương pháp thông thường đối với hệ tuyến tính sẽ cần đến nhiều phương trình. Nhìn chung, nếu chúng ta có hệ phương trình bậc hai của n biến, phương pháp tuyến tính hóa yêu cầu khoảng n2/2 phương trình độc lập. Như vậy, đối với những trường hợp các hệ vượt mức xác định, việc giải hệ phương trình bậc hai sẽ thuận lợi hơn trường hợp tổng quát.
Sự vượt quá mức xác định của các hệ phương trình đã thúc đẩy người ta tìm kiếm các thuật toán tốt hơn. Kỹ thuật tuyến tính hóa mở rộng (XL) đã được đề xuất. Ý tưởng chính của phương pháp này là nhân các phương trình với một số biến để tạo ra một phương trình mới. Nếu một phương trình được nhân với tất cả n biến thì n phương trình mới bậc lớn hơn 1 sẽ được tạo ra. Với giả định rằng tất cả các phương trình mới là độc lập thì lại có thể thực hiện ngay phương pháp tuyến tính hóa (tuyến tính hóa mở rộng thậm chí còn được thực hiện khi chỉ cho trước 0.1n2 phương trình).
Cho đến nay, rất khó để ước lượng chính xác thành công của phương pháp tuyến tính hóa mở rộng, vì phương pháp này không nhất thiết tạo ra nhiều phương trình độc lập như mong đợi. Hơn nữa, nếu bậc cao nhất của hệ tăng lên thì phương pháp tuyến tính hóa thậm chí yêu cầu nhiều phương trình hơn nữa. Người ta nhận thấy rằng, trong trường hợp tuyến tính hóa mở rộng, rất khó để tính chính xác độ phức tạp về mặt thời gian của thuật toán hoặc thậm chí để thảo luận về những thành công của nó
Một biến thể khác của phương pháp tuyến tính hóa mở rộng được đề xuất đó là tuyến tính hóa thưa mở rộng (XSL). Phương pháp này cố gắng khai thác cấu trúc của các phương trình liên quan đến mã khối. Nó đã dẫn đến thực tế rằng nhiều phương trình mới sẽ được thêm vào mà không thêm vào các số hạng mới.
Thật ra, khi biểu diễn một mã khối dưới dạng một hệ phương trình đại số, người ta thường thu được nhiều phương trình đại số bậc cao hơn 2. Khi đó, cần thực hiện các phép biến đổi để đưa chúng về hệ các phương trình bậc 2. Về mặt lý thuyết có thể làm được việc này nhưng phải trả giá về mặt tính toán. Nhà phát triển mật mã sẽ cố gắng thiết kế sao cho cái giá này đối với việc thám mã là rất cao. Một trong những thủ thuật cơ bản để hạ bậc các phương trình như thế là nhân đa thức f trong hệ các phương trình nói trên với một đa thức thích hợp g để thu được đa thức có bậc thấp hơn. Giá phải trả sẽ càng cao nếu nhà mã thám buộc phải tìm g trong tập các đa thức có bậc đủ lớn. Điều này dẫn đến khái niệm độ triệt tiêu đại số cực đại. Nhà phát triển mật mã sẽ cố gắng thiết kế sao cho hàm f (là đa thức biểu diễn một vòng hay đa thức biểu diễn một hộp S của mã khối, hoặc f là hàm tổ hợp trong mã dòng) có độ triệt tiêu đại số đủ lớn. Đây là bài toán rất quan trọng và cũng rất khó khăn đối với người thiết kế mật mã và do đó họ không thể không quan tâm đến một cách thích đáng.
Cho đến nay, tấn công đại số đang là mối đe dọa đối với mật mã đối xứng. Mặc dù chưa có báo cáo nào được công bố cho thấy hiệu quả thực tế của phương pháp này trong việc phá vỡ mã khối, nhưng nhiều nhà khoa học cho rằng nó đã thành công trong việc phá vỡ một số mã dòng cụ thể. Đó thực sự là một hồi chuông cảnh báo cho những người lập mã.
Đối với một hệ mật mà người ta chưa có những đánh giá tin cậy, nếu đưa vào ứng dụng thì người sử dụng nó để mã hóa thông tin mật có thể sẽ gặp những rủi ro không lường trước được. Trái lại, trong hoàn cảnh đó nhà mã thám có thể gặp được những may mắn bất ngờ. Vì vậy, những người sử dụng mật mã rất cần những hệ mật đã được đánh giá là tin cậy và không nên sử dụng hệ mật nào chưa được đánh giá là bền vững trong bảo mật. Theo nghĩa đó, tấn công đại số thực sự cũng là một lĩnh vực cần được các nhà lập mã quan tâm thấu đáo.

Tin cùng chuyên mục

Tin mới