Tính ngẫu nhiên và giả ngẫu nhiên

Tính ngẫu nhiên là huyết mạch của mật mã học — các khóa, số nonce và thách thức phải không thể đoán trước — và tính giả ngẫu nhiên cho phép một hạt giống thực sự ngẫu nhiên ngắn được kéo dài thành các chuỗi dài không thể phân biệt được với ngẫu nhiên đối với bất kỳ đối thủ hiệu quả nào.

Definition

Tính giả ngẫu nhiên là thuộc tính không thể phân biệt được về mặt tính toán với tính ngẫu nhiên thực sự; một bộ tạo giả ngẫu nhiên mở rộng một cách xác định một hạt giống ngẫu nhiên ngắn thành một đầu ra dài hơn mà không thuật toán hiệu quả nào có thể phân biệt được với ngẫu nhiên.

Scope

Chủ đề này bao gồm vai trò của tính ngẫu nhiên trong mật mã học: các yêu cầu đối với nguồn entropy và bộ tạo số ngẫu nhiên thực sự, các định nghĩa và cấu trúc của bộ tạo giả ngẫu nhiên và hàm giả ngẫu nhiên an toàn về mặt mật mã, và những hậu quả thảm khốc của tính ngẫu nhiên yếu hoặc được sử dụng lại. Nó đề cập đến cách các đối tượng giả ngẫu nhiên chính thức hóa các nguyên thủy đối xứng. Nó không bao gồm các thuật toán mã hóa cụ thể và các giả định về độ khó, được xử lý trong các chủ đề liên quan.

Core questions

• Tại sao mật mã học yêu cầu tính ngẫu nhiên không thể đoán trước, và điều gì sẽ xảy ra nếu không có nó?
• Điều gì phân biệt một bộ tạo an toàn về mặt mật mã với một bộ tạo thống kê?
• Làm thế nào một hạt giống thực sự ngẫu nhiên ngắn có thể được kéo dài thành đầu ra giả ngẫu nhiên dài?
• Các hàm và hoán vị giả ngẫu nhiên là gì, và chúng mô hình hóa các thuật toán mã hóa như thế nào?
• Entropy chất lượng cao được thu thập và điều hòa trong các hệ thống thực tế như thế nào?

Key concepts

• entropy và tính ngẫu nhiên thực sự
• bộ tạo số ngẫu nhiên
• bộ tạo giả ngẫu nhiên (PRG)
• hàm giả ngẫu nhiên (PRF)
• hoán vị giả ngẫu nhiên (PRP)
• tính không thể phân biệt được về mặt tính toán
• hạt giống và dẫn xuất khóa
• lỗi sử dụng lại tính ngẫu nhiên
• điều hòa entropy

Key theories

Bộ tạo giả ngẫu nhiên

Một bộ tạo giả ngẫu nhiên mở rộng một hạt giống ngắn thành một chuỗi dài hơn không thể phân biệt được với tính ngẫu nhiên đồng nhất đối với bất kỳ bộ phân biệt hiệu quả nào; các bộ tạo như vậy tồn tại nếu và chỉ nếu các hàm một chiều tồn tại, liên kết tính giả ngẫu nhiên với các nền tảng của mật mã học.

Các hàm và hoán vị giả ngẫu nhiên

Một họ hàm giả ngẫu nhiên, có thể xây dựng từ bất kỳ bộ tạo giả ngẫu nhiên nào, không thể phân biệt được với một hàm thực sự ngẫu nhiên đối với một đối thủ truy vấn nó; đối tượng này làm nền tảng cho việc mô hình hóa bảo mật của các thuật toán mã hóa khối và mã xác thực thông điệp.

Mechanisms

Một bộ tạo số ngẫu nhiên thực sự thu thập entropy vật lý (nhiễu nhiệt, jitter thời gian), được điều hòa và sử dụng để gieo hạt cho một bộ tạo giả ngẫu nhiên an toàn về mặt mật mã, bộ tạo này tạo ra một cách xác định tất cả các bit trông ngẫu nhiên mà một hệ thống cần. Các hàm giả ngẫu nhiên được xây dựng từ các bộ tạo (cấu trúc GGM) và mô hình các nguyên thủy được khóa; một thuật toán mã hóa khối được coi là một hoán vị giả ngẫu nhiên. Các định nghĩa bảo mật yêu cầu rằng không đối thủ hiệu quả nào, khi được cung cấp đầu ra, có thể dự đoán các bit tiếp theo hoặc phân biệt chúng với ngẫu nhiên.

Clinical relevance

Các lỗi ngẫu nhiên là một nguồn tái diễn của các sự cố thực tế thảm khốc: lỗi Debian OpenSSL năm 2008 đã làm tê liệt việc tạo khóa, các số nonce ECDSA có thể dự đoán được đã làm rò rỉ khóa riêng (Sony PlayStation 3, một số ví Bitcoin), và entropy thiết bị nhúng yếu đã tạo ra các khóa có thể đoán được trên quy mô lớn. Do đó, tính ngẫu nhiên mạnh mẽ — thu thập entropy thích hợp và các bộ tạo giả ngẫu nhiên đã được kiểm định — là điều cần thiết cho mọi triển khai mật mã.

Evidence & guidelines

NIST SP 800-90A/B/C quy định các bộ tạo bit ngẫu nhiên xác định được phê duyệt, xác thực nguồn entropy và hướng dẫn xây dựng. Thực hành tốt nhất sử dụng RNG mật mã đã được kiểm định của hệ điều hành (thay vì tự tạo), đảm bảo đủ entropy trước khi tạo khóa và không bao giờ sử dụng lại số nonce. Các bộ kiểm tra thống kê giúp phát hiện các lỗi lớn nhưng không thể thiết lập sức mạnh mật mã.

History

Lý thuyết tính toán về tính giả ngẫu nhiên được Blum và Micali và Yao thành lập vào khoảng năm 1982, định nghĩa tính không thể đoán trước và không thể phân biệt được. Goldreich, Goldwasser và Micali đã chỉ ra cách xây dựng các hàm giả ngẫu nhiên từ các bộ tạo vào năm 1986, và Hastad, Impagliazzo, Levin và Luby sau đó đã chứng minh rằng các bộ tạo giả ngẫu nhiên tồn tại nếu các hàm một chiều tồn tại. Các thảm họa thực tế lặp đi lặp lại từ tính ngẫu nhiên yếu đã giữ cho chất lượng entropy và RNG trở thành một mối quan tâm kỹ thuật trung tâm.

Key figures

• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali
• Manuel Blum
• Andrew Yao

Seminal works

• goldreich1986
• goldreich2001
• katz2020

Frequently asked questions

Tại sao tôi không thể sử dụng một hàm ngẫu nhiên thông thường như rand() cho mật mã học?

Các bộ tạo số ngẫu nhiên thông thường được xây dựng cho tính đồng nhất thống kê và tốc độ, không phải tính không thể đoán trước; đầu ra của chúng có thể được dự đoán từ một vài mẫu. Mật mã học cần các bộ tạo mà đầu ra trong tương lai không thể dự đoán được ngay cả khi biết đầu ra trong quá khứ, điều này đòi hỏi một RNG an toàn về mặt mật mã được gieo hạt bằng entropy thực sự.

Sự khác biệt giữa tính ngẫu nhiên thực sự và tính giả ngẫu nhiên là gì?

Tính ngẫu nhiên thực sự đến từ một nguồn vật lý, không thể đoán trước và có nguồn cung hạn chế. Tính giả ngẫu nhiên được tạo ra một cách xác định từ một hạt giống ngẫu nhiên thực sự ngắn và có thể được tạo ra với số lượng lớn; nó chỉ cần không thể phân biệt được với tính ngẫu nhiên thực sự đối với bất kỳ đối thủ hiệu quả nào, điều này đủ cho việc sử dụng mật mã.