Trong thực tế, để chọn một cách ngẫu nhiên thống nhất $x\in \mathbb{Z}^*_q$, chúng tôi giảm nhiệm vụ đó thành vấn đề chọn các bit độc lập và ngẫu nhiên thống nhất. Trên một hệ thống máy tính hiện đại, sẽ có một số dịch vụ hệ điều hành cung cấp các bit như vậy, ví dụ: /dev/urandom trên nhiều dẫn xuất Unix (chúng ta sẽ quay lại vấn đề làm cách nào để có được những bit như vậy trong phần thứ hai).
Phương pháp đơn giản nhất để chọn ngẫu nhiên thống nhất $x\in \mathbb{Z}^*_q$, đó là một số nguyên trong $[0,q)$, đôi khi được gọi là lấy mẫu từ chối, diễn ra như sau:
- Là sơ bộ được thực hiện một lần cho dù có bao nhiêu lần $x$ chúng tôi muốn tạo: như một chức năng (xác định) của $q$, chọn một số $k$ với $2^k\ge q$, ví dụ. $k$ nhiều hơn một chút so với số bit trong biểu thức nhị phân của $q$.
- Vẽ tranh $k$ bit ngẫu nhiên và độc lập thống nhất $b_i$, vì $0\le i<k$
- lắp ráp các $k$ bit thành số nguyên $y=\sum b_i\,2^i$
- Nếu $y<(2^k\bmod q)$, tiếp tục ở 2.
- Tính toán và xuất $x=y\bmod q$.
Xác suất mà $x$ là bất kỳ số nguyên cụ thể trong $[0,q)$ chính xác $1/q$ theo giả thuyết các bit $b_i$ là ngẫu nhiên và độc lập thống nhất.
Các biến thể phổ biến:
- Sản xuất các bit $b_i$ nhóm trong một từ máy tính, và/hoặc $k$ buộc phải là bội số của một số kích thước từ.
- Độ bền lớn ở 2: $y=\sum b_i\,2^{k-i-1}$; điều này cũng cho phép $y$ được xây dựng khi chúng ta vẽ $b_i$ như $y_0=0$, $y_{i+1}=y_i+y_i+b_i$ vì $0\le i<k$, $y=y_k$.
- Điều kiện kiểm tra khác nhau ở 4, ví dụ: $y\ge2^k-(2^k\bmod q)$.
Chúng tôi cũng có thể loại bỏ bước 4 (trong trường hợp đó, phương pháp này không còn là lấy mẫu từ chối). Trừ khi $q$ là lũy thừa của hai, điều này để lại các số nguyên trong $[0,2^k\bmod q)$ nhiều khả năng hơn những người trong $[(2^k\bmod q), q)$, với xác suất $\lceil 2^k/q\rceil/2^k$ còn hơn là $\ltầng 2^k/q\rtầng/2^k$. Nhưng nếu $k$ lớn hơn một cách phù hợp so với số lượng bit trong $q$ (Nói, $k\>\lceil\log_2 q\rceil+64$ ), hoặc/và nếu $\min(2^k\bmod q,-2^k\bmod q)/q$ nhỏ hơn một số giới hạn phù hợp (ví dụ: $2^{-128}$ ), thì sai lệch này không thể phát hiện được bằng thực nghiệm.
(Có những đặc điểm tốt hơn khi chúng ta có thể loại bỏ bước 4 và các phương pháp phức tạp hơn để giảm thiểu số lượng $b_i$ được tạo ra khi thực hiện nhiều $x$, nhưng việc sử dụng chúng không phổ biến).
Chúng ta quay lại vấn đề chọn các bit ngẫu nhiên và độc lập thống nhất, hoặc có lẽ là các từ máy tính bao gồm các bit như vậy.
Tất cả các phương pháp được đề xuất đều sử dụng cùng một nguyên tắc chung: (các) nguồn ngẫu nhiên không hoàn hảo được xử lý sau thành các bit với hy vọng không thể phân biệt được (thực sự, kể cả đối với các đối thủ mạnh tùy ý; hoặc như một dự phòng, có thể tính toán được) từ các bit độc lập và ngẫu nhiên thống nhất mong muốn.
Nguồn ví dụ:
- Đầu vào bao gồm tổ hợp phím, vị trí chuột, micrô, đầu vào máy ảnh.
- Thời gian khi tổ hợp phím xảy ra, vị trí chuột thay đổi, khối đĩa hoặc gói Ethernet/Wifi/Bluetooth/USB đến bo mạch chủ, được đo, ví dụ: theo chu kỳ đồng hồ kể từ khi máy tính khởi động
- Một thiết bị chuyên dụng. Một phương pháp so sánh điện áp tức thời trên một Đi-ốt Zener theo ý nghĩa của nó và lấy mẫu kết quả theo các khoảng thời gian đều đặn. Một ví dụ khác về bộ tạo dao động hỗn loạn hy vọng bằng cách sử dụng một bộ dao động độc lập có hy vọng khác.
Rất nhiều nỗ lực nên được thực hiện trong việc giám sát (các) nguồn, để đảm bảo nó/chúng hoạt động bình thường (hoặc nếu chúng ta kết hợp nhiều nguồn, để ước tính mức tối thiểu Sự hỗn loạn chúng tôi có thể tin tưởng rằng họ cùng nhau phân phối).
Một trong những phương pháp hậu xử lý hiệu quả đơn giản nhất là băm: một số bit từ (các) nguồn được băm và kết quả (hoặc một phần của chúng) tạo thành đầu ra có điều kiện. Điều đó an toàn cho một hàm băm không thể phân biệt về mặt tính toán với một lời tiên tri ngẫu nhiên (đối với độ dài đầu vào được sử dụng) và đủ lớn (min-)entropy của đầu vào băm.
Nếu chúng ta cần nhiều bit ngẫu nhiên, chúng ta có thể tạo ra chúng với chi phí thấp bằng cách gieo một Trình tạo số ngẫu nhiên giả an toàn bằng mật mã với sự ngẫu nhiên thu được như trong đoạn cuối. Tuy nhiên, nếu trạng thái của CSPRNG bị xâm phạm (ví dụ: bởi các kênh bên cạnh), thì tất cả đầu ra của nó là. Vì lý do này, có nhiều phương pháp phức tạp hơn để thu được các bit ngẫu nhiên có độ an toàn cao ở tốc độ cao, theo cách phục hồi độc đáo khỏi sự xâm phạm trạng thái bên trong của chúng.
Ngoài ra: trên các CPU hiện đại, thường có một nguồn chết (đôi khi nằm trong chipset). Thông thường, đầu ra của nó không thể truy cập được theo cách được ghi chép đầy đủ. Lời bào chữa cho điều đó là mọi người sẽ sử dụng nó trực tiếp hoặc/và khoe khoang về việc phát hiện ra một số sai lệch trong đó mặc dù điều đó được mong đợi. Lập trình viên được cho là sử dụng đầu ra có điều kiện bí ẩn thông qua một số lệnh (ví dụ: RDRAND). Cách theo dõi sức khỏe của nguồn thường được ghi lại kém và/hoặc không được hỗ trợ trong phần mềm/HĐH. Các vấn đề khác có thể xảy ra với RNG dựa trên CPU bao gồm bảo vệ kém tính bảo mật của đầu ra, xem ví dụ: cái này. Rút ra (ý định chơi chữ) kết luận của riêng bạn về việc liệu chúng có nên được tin cậy là nguồn duy nhất hay tính ngẫu nhiên trong tiền điện tử.
