Giảm bảo mật của các thuật toán khóa đối xứng là gì?

Tôi đang đọc trang Wikipedia về mật mã hậu lượng tử. Nó nói rằng các thuật toán mật mã mong muốn có thể rút gọn thành một số bài toán cụ thể, nghĩa là tính khó hiểu của hệ thống về cơ bản phải xuất phát từ độ cứng của một số bài toán.

Ví dụ, mật mã dựa trên lưới, Diffie-Hellman, RSA, hệ thống McEliece, mật mã đa biến quy về bài toán vectơ ngắn nhất, bài toán logarit rời rạc, phân tích thành thừa số nguyên, bài toán giải mã hội chứng, bài toán giải phương trình bậc hai nhiều biến tương ứng.

Tôi không thể xem bất kỳ ví dụ nào về thuật toán khóa đối xứng. Tại sao vậy? Tôi cho rằng họ không cần thuộc tính này do bản chất của mật mã khóa đối xứng?

Có phải vì nó không bắt buộc mật mã khóa công khai không đối xứng và do đó không cần một hệ thống dễ mã hóa, khó giải mã nào đó chuyển thành hàm một chiều, khó đảo ngược do toán học đằng sau nó?

cảm ơn vì câu trả lời, nó rất hữu ích.

tôi không thể xem bất kỳ ví dụ nào về thuật toán khóa đối xứng. nhưng tại sao?

Có một số cách có thể để trả lời điều này; đơn giản nhất là các thuật toán khóa đối xứng là dựa trên các vấn đề toán học cụ thể (chúng tôi thường không diễn đạt nó theo cách đó).

Để lấy một số ví dụ về thuật toán assymetric:

ví dụ ... diffie-hellman, rsa ... rút gọn thành ... bài toán logarit rời rạc, phân tích thừa số nguyên ... tương ứng.

Điều đó là không chính xác; nếu bạn được cung cấp một Oracle có thể phá vỡ Diffie-Hellman, thì không có cách nào biết cách sử dụng nó để giải quyết các vấn đề về nhật ký rời rạc; nếu bạn được cung cấp một Oracle có thể phá vỡ RSA, thì không có cách nào để sử dụng nó để tính toán.

Thay vào đó, những gì Diffie-Hellman rút gọn được gọi là "vấn đề Diffie-Hellman" (về mặt kỹ thuật, cDH hoặc dDH, tùy thuộc vào những gì Oracle của bạn làm); những gì RSA rút gọn được gọi là "vấn đề RSA".

Bây giờ, sự khác biệt giữa "vấn đề Diffie-Hellman" hay "vấn đề RSA" và "vấn đề AES" là gì? Ngoài thực tế là "vấn đề AES" mất nhiều thời gian hơn để mô tả và cảm thấy tùy tiện hơn, tôi không thể thấy một vấn đề nào (và chắc chắn "vấn đề AES" đã được nghiên cứu khá kỹ). Và, nếu chúng ta đang sử dụng AES ở một số chế độ, thì nhìn chung có bằng chứng cho thấy tính bảo mật của chế độ giảm xuống thành "vấn đề AES", do đó đây không chỉ là một trò chơi chữ ngớ ngẩn.

Một cách khác để tiếp cận câu hỏi (nếu chúng ta nhấn mạnh vào 'các bài toán đơn giản' như một cách để loại bỏ 'bài toán AES') là lưu ý rằng chúng ta biết các nguyên hàm đối xứng quy giản thành các bài toán đơn giản; tuy nhiên những bản mã nguyên thủy đó thường chạy chậm hơn nhiều (và thường có bản mã lớn hơn nhiều) so với những gì chúng ta sử dụng trong thực tế và vì vậy chúng ta không bao giờ sử dụng chúng, đặc biệt là vì chúng ta không biết bất kỳ bằng chứng nào cho thấy 'bài toán đơn giản' thực sự khó hơn. hơn là 'bài toán phức tạp' mà chúng ta sử dụng trong thực tế.

Người ta có thể lật lại vấn đề này và hỏi 'tại sao chúng ta cứ khăng khăng dựa vào các thuật toán bất đối xứng cho các bài toán khó cụ thể?'. Một câu trả lời là các thuật toán bất đối xứng cố gắng làm nhiều hơn một thuật toán đối xứng; một thuật toán bất đối xứng không chỉ cần trông 'ngẫu nhiên', mà nó còn cần được bảo mật ngay cả khi kẻ tấn công nhận được gợi ý dưới dạng khóa chung. Khóa chung này phải liên quan bằng cách nào đó với khóa riêng, nhưng không phải theo cách rõ ràng (và tất nhiên, các hoạt động dễ dàng được cung cấp khóa riêng phải không khả thi nếu chỉ được cung cấp khóa chung). Cách duy nhất mà chúng ta biết để có một mối quan hệ mơ hồ như vậy là biến mối quan hệ đó thành một vấn đề khó đơn giản hơn.

Trong chừng mực có sự giảm thiểu bảo mật trong mật mã đối xứng, chúng có xu hướng áp dụng cho các công trình sử dụng các nguyên mẫu lý tưởng hóa như một chức năng giả ngẫu nhiên hoặc một hoán vị giả ngẫu nhiên. Vì vậy, ví dụ, Luby và Rackoff đã chứng minh rằng có thể xây dựng một hoán vị giả ngẫu nhiên từ một hàm giả ngẫu nhiên bằng cách sử dụng cấu trúc Feistel ba vòng. Tương tự như vậy, các nhà mật mã đối xứng có thể cố gắng chứng minh rằng chế độ hoạt động của mật mã khối mở rộng một hoán vị giả ngẫu nhiên trên kích thước khối thành một hoán vị giả ngẫu nhiên trên một phần dữ liệu lớn hơn.

Sau đó, sự đảm bảo xuất phát từ niềm tin rằng các nguyên hàm đối xứng mà chúng ta sử dụng có thể phân biệt được với các đối tác giả ngẫu nhiên được lý tưởng hóa của chúng. Liệu có đảm bảo hơn trong tuyên bố "phá vỡ cấu trúc này cũng khó như phân biệt SHA256 với hàm giả ngẫu nhiên" hay "phá vỡ cấu trúc này khó như bài toán Diffie-Hellman quyết định trong nhóm này" là tùy thuộc vào người tiêu dùng.