Có khả thi để xây dựng toàn bộ nhánh mật mã trên một họ các nguồn giả ngẫu nhiên không?
Về lý thuyết, có. Nếu đã có một Trình tạo số ngẫu nhiên giả an toàn về mật mã và hiệu quả được xây dựng từ một hệ thống hỗn loạn, sau đó hệ thống đó có thể đóng vai trò là nền tảng của mật mã đối xứng thực tế hợp lý và thậm chí cả chữ ký.
Vấn đề là chúng ta không biết điều đó. Các PRNG được xây dựng từ một hệ thống hỗn loạn và có lập luận bảo mật thậm chí còn hơi thuyết phục¹, kém hiệu quả so với CSPRNG² hiện đại (trừ khi chúng tôi mở rộng định nghĩa về "hệ thống hỗn loạn" vượt xa các chức năng liên tục được lặp lại thông thường trên $\mathbb R$, hoặc các xấp xỉ rời rạc của chúng).
Trình tạo số ngẫu nhiên giả (bảo mật bằng mật mã), trong đó nét hiện đại, là một công cụ đủ mạnh để xây dựng tất cả các chức năng mật mã đối xứng khác: CPA và CCA(2)-mật mã an toàn, khóa mật mã, Mã xác thực tin nhắn, mã hóa xác thực, băm⦠Một số ví dụ:
- Một mật mã có thể được xây dựng từ (CS)PRNG bằng cách sử dụng khóa và IV ngẫu nhiên thực sự ngẫu nhiên để tạo PRNG và xây dựng bản mã bằng XOR đầu ra của PRNG với văn bản gốc³.Bảo mật trực tiếp theo sau bảo mật của PRNG và đó là một cách tốt và phổ biến để xây dựng một mật mã mà nó có tên: dòng mật mã.
- Mật mã khối có thể được xây dựng từ PRNG dưới dạng mật mã Feistel, bằng cách sử dụng PRNG để xây dựng các hàm vòng. Khóa, số vòng và nửa bên phải của khối khởi tạo PRNG, đầu ra là giá trị để XOR với nửa bên trái.
Những công trình này là một cách rõ ràng bảo mật bằng mật mã nếu PRNG là. Nhưng ngoại trừ mật mã dòng, chúng không được sử dụng trong thực tế, chủ yếu vì lý do hiệu quả. CSPRNG phổ biến được xây dựng từ mật mã khối hoặc/và giá trị băm, thay vì ngược lại.
Có khả thi để xây dựng các nguyên hàm tiền điện tử khóa công khai từ PRNG không?
Có cho chữ ký. Chúng ta có thể xây dựng hàm băm an toàn từ PRNG an toàn, sau đó là chữ ký an toàn từ hàm băm, bằng nhiều cách tiếp cận khác nhau, bao gồm SPHINCS. Theo lộ trình này, bất kỳ PRNG hiệu quả nào cũng dẫn đến sơ đồ chữ ký hợp lý.
Đối với mã hóa và trao đổi khóa, tôi nghi ngờ rằng một phương pháp có bằng chứng bảo mật hoặc thậm chí là một lập luận thuyết phục đã được biết đến. Tôi không bị thuyết phục bởi những nỗ lực xây dựng mã hóa bất đối xứng từ các hệ thống hỗn loạn liên tục bằng các tuyến đường trực tiếp hơn´.
¹ Chúng tôi không thể yêu cầu bằng chứng theo nghĩa toán học, vì chúng tôi không có bằng chứng bảo mật như vậy cho bất kỳ CPRNG nào. Nhưng chúng tôi không muốn chấp nhận thực tế vượt qua một bài kiểm tra ngẫu nhiên được xác định trước làm đối số bảo mật, chẳng hạn như NIST SP800-22rev1a hoặc cứng rắn hơn. Một thử nghiệm thử nghiệm ít nhất phải là: không thể đối với các nhà mật mã lành nghề của con người biết thiết kế của PRNG, được hỗ trợ bởi các máy tính cổ điển, để phân biệt với tính ngẫu nhiên thực sự, đầu ra của PRNG được gieo với tính ngẫu nhiên thực sự. Và chúng tôi muốn mở rộng điều đó đến mức không thể như vậy bắt đầu với giá trị tối thiểu của một số (các) tham số của PRNG, như kích thước trạng thái hoặc/và số vòng, với (các) tham số thực sự được sử dụng được đặt lớn hơn một cách thoải mái.
² Chẳng hạn như cái có nguồn gốc từ chacha bằng cách coi khóa và IV là hạt giống và bản rõ hoàn toàn bằng không.
³ Quá trình giải mã tương tự với trao đổi văn bản gốc và bản mã, ngoại trừ việc mã hóa lấy IV và biến nó thành phần mở đầu của bản mã, trong khi quá trình giải mã trích xuất IV từ phần mở đầu.
´ Một trong những nỗ lực (có tường phí) sử dụng đa thức Chebyshev $T_r$ mức độ lớn $r$. Khóa riêng là $r$, khóa công khai phù hợp là $T_r(x)$ đối với một số thực cố định được chọn ngẫu nhiên $x\in[-1,1]$. Đối với bất kỳ số nguyên $s>0$ nó giữ $T_r(T_s(x))=T_s(T_r(x))$ và (bỏ qua các vấn đề về cách tính toán) cho phép tương tự Trao đổi khóa Diffie-Hellman, và từ đó mã hóa ElGamal. Khi tôi đọc nó lần đầu tiên, tôi đã không bị thuyết phục bởi khẳng định bảo mật không cần tranh luận, cũng như bởi một số khía cạnh của tính khả thi (ví dụ: với độ chính xác 2048 bit cho các giá trị thực, các số nguyên $r$ và $s$ có thể được chọn là số nguyên 910-bit ngẫu nhiên, chứ không phải là tích của các số nguyên tố nhiều nhất là 133 như trong bài viết).
Cập nhật: Hệ thống mật mã được phát hiện là không an toàn, xem cái này mạo từ (có tường phí). Nó vẫn được trình bày trong này chương về Mật mã khóa công khai (paywalled) trong một thời gian dài sau đó cuốn sách về mật mã dựa trên hỗn loạn (có tường phí), với sự thừa nhận về sự không an toàn. Tôi thấy nó nói lên tình trạng của toàn bộ lĩnh vực học thuật đó. Và đó là điều tốt nhất: hầu hết các tuyên bố về bảo mật, được đưa ra với những lập luận tương đối yếu, không bao giờ được điều tra nghiêm túc và được chứng minh là sai.
