# Tổng quan về sinh số ngẫu nhiên: từ entropy đến PRNG và CSPRNG


## 1. “Số ngẫu nhiên” có thể đến từ hai nơi

Khi một chương trình yêu cầu số ngẫu nhiên, có hai công việc rất khác nhau có thể đang diễn ra:

1. **Thu nhận entropy từ thế giới thực:** đo một hiện tượng khó dự đoán như nhiễu điện tử hoặc độ lệch thời gian của các sự kiện hệ thống.
2. **Mở rộng một trạng thái hữu hạn bằng thuật toán tất định:** từ một seed ngắn, sinh nhanh một luồng bit dài có tính chất thống kê hoặc tính chất mật mã mong muốn.

Hệ điều hành hiện đại thường kết hợp cả hai. Nó gom các tín hiệu khó dự đoán, kiểm tra và trộn chúng thành seed; sau đó một **bộ sinh số giả ngẫu nhiên an toàn mật mã** (cryptographically secure pseudorandom number generator, CSPRNG) mở rộng seed đó thành lượng dữ liệu lớn. Vì vậy, “ngẫu nhiên vật lý” và “PRNG tất định” không nhất thiết là hai lựa chọn loại trừ nhau: nhánh thứ nhất thường nuôi seed và reseed cho nhánh thứ hai.

<link rel="stylesheet" href="/css/rng-overview-map.css">

<figure class="rng-family-map" aria-label="Bản đồ các phương pháp sinh số ngẫu nhiên">
  <div class="rng-family-map__root">Random-number generation</div>
  <div class="rng-family-map__root-arrow" aria-hidden="true">↓</div>
  <div class="rng-family-map__branches">
    <section class="rng-family-map__branch rng-family-map__branch--entropy">
      <header class="rng-family-map__branch-header">
        <span>Nguồn đầu vào</span>
        <h4>Entropy từ thế giới thực</h4>
      </header>
      <ul class="rng-family-map__list">
        <li><strong>Nhiễu nhiệt, nhiễu điện tử</strong><small>dao động vi mô trong phần cứng</small></li>
        <li><strong>Timing, interrupts, thiết bị</strong><small>độ lệch thời gian và hoạt động hệ thống</small></li>
        <li><strong>Hiện tượng lượng tử</strong><small>đo đạc photon hoặc quá trình lượng tử</small></li>
      </ul>
      <div class="rng-family-map__flow" aria-hidden="true">↓</div>
      <div class="rng-family-map__result">
        <strong>Entropy đã kiểm tra và conditioning</strong>
        <small>seed / reseed cho bộ sinh tất định</small>
      </div>
    </section>
    <section class="rng-family-map__branch rng-family-map__branch--deterministic">
      <header class="rng-family-map__branch-header">
        <span>Thuật toán mở rộng</span>
        <h4>PRNG tất định</h4>
      </header>
      <div class="rng-family-map__prng-branches">
        <section class="rng-family-map__subbranch rng-family-map__subbranch--simulation">
          <h5>Nhanh, phục vụ mô phỏng</h5>
          <ul class="rng-family-map__algorithms">
            <li><strong>LCG</strong><code>x ← ax + c mod m<br>output ← x</code></li>
            <li><strong>PCG</strong><code>x ← ax + c mod m<br>output ← permutation(x)</code></li>
            <li><strong>Xorshift và họ hàng</strong><small>xorshift* · xoroshiro · xoshiro</small></li>
            <li><strong>Mersenne Twister</strong><small>trạng thái lớn, chu kỳ rất dài</small></li>
            <li><strong>LXM</strong><small>LCG + xorshift-based generator + mixer</small></li>
            <li><strong>Counter-based</strong><small>Philox · Threefry</small><code>counter, key → mixing → output</code></li>
          </ul>
        </section>
        <section class="rng-family-map__subbranch rng-family-map__subbranch--security">
          <h5>Bảo mật, khó dự đoán</h5>
          <ul class="rng-family-map__algorithms rng-family-map__algorithms--security">
            <li><strong>ChaCha-based CSPRNG</strong></li>
            <li><strong>AES / CTR_DRBG</strong></li>
            <li><strong>HMAC_DRBG</strong></li>
            <li><strong>Hash_DRBG</strong></li>
          </ul>
        </section>
      </div>
    </section>
  </div>
  <figcaption>Nguồn entropy cung cấp tính khó dự đoán ban đầu; thuật toán tất định mở rộng trạng thái đó theo mục tiêu thống kê hoặc bảo mật.</figcaption>
</figure>

Sơ đồ này phân loại theo **vai trò thiết kế**, không phải theo phả hệ. PCG không phải hậu duệ của Mersenne Twister; Philox cũng không phải “bản nâng cấp kế tiếp” của xoshiro. Mỗi họ giải quyết một tập yêu cầu khác nhau.

## 2. Nguồn entropy: đo sự bất định, không chỉ thu thập bit

Một nguồn phần cứng có thể khai thác nhiễu nhiệt, nhiễu shot, jitter của bộ dao động vòng hoặc một phép đo lượng tử. Hệ điều hành còn có thể thu thập dữ liệu từ thời điểm ngắt, hoạt động thiết bị và các biến thiên khó dự đoán khác. Theo cách gọi của [NIST SP 800-90B](https://csrc.nist.gov/pubs/sp/800/90/b/final), nhóm thứ nhất là **physical noise source**; dữ liệu timing hoặc tương tác hệ thống thường được xem là nguồn phi vật lý. Cả hai đều có thể mang entropy, nhưng cần mô hình và cách đánh giá khác nhau.

Ba khái niệm cần tách biệt:

- **Raw noise:** các mẫu thô lấy từ hiện tượng nguồn. Chúng có thể lệch, tương quan hoặc hỏng hoàn toàn khi phần cứng gặp lỗi.
- **Entropy estimate:** cận dưới cho lượng bất định thật sự. Một nghìn bit dữ liệu thô không mặc nhiên chứa một nghìn bit entropy.
- **Conditioning:** dùng hash, HMAC hoặc một hàm trộn phù hợp để giảm lệch và cô đặc entropy. Conditioning không tạo entropy từ hư không; nó chỉ biến lượng entropy đã có thành đầu ra thuận tiện hơn.

Một entropy source hoàn chỉnh vì thế thường gồm **noise source + health tests + conditioning**. Seed ban đầu thiết lập trạng thái của bộ sinh tất định; reseed định kỳ hoặc theo sự kiện đưa entropy mới vào, hạn chế thời gian ảnh hưởng nếu trạng thái từng bị lộ.

## 3. PRNG tất định: trạng thái, bước chuyển và đầu ra

Mọi PRNG trạng thái có thể được hình dung bằng hai hàm:

$$
s_{n+1}=T(s_n),
\qquad
y_n=O(s_n),
$$

trong đó $T$ chuyển trạng thái và $O$ tạo đầu ra. Cùng thuật toán, cùng seed và cùng phiên bản triển khai sẽ cho cùng chuỗi. Đây là tính năng quan trọng của mô phỏng: một lỗi hiếm có thể được chạy lại chính xác.

Vì trạng thái chỉ có hữu hạn bit, chuỗi cuối cùng phải tuần hoàn. Một chu kỳ dài vẫn chưa đủ để bảo đảm chất lượng: ta còn phải quan tâm tới tương quan giữa các đầu ra, chất lượng từng bit, cách tạo nhiều luồng song song và khả năng khôi phục trạng thái từ những gì đã quan sát.

Seed ngẫu nhiên cũng không chữa được một thuật toán yếu. Nếu lấy entropy vật lý để seed cho LCG, đầu ra vẫn mang cấu trúc mạng lưới của LCG. Ngược lại, một PRNG tốt với seed cố định vẫn hoàn toàn có thể phục vụ mô phỏng, miễn là mục tiêu là chất lượng thống kê và khả năng tái lập chứ không phải chống kẻ tấn công.

## 4. Các họ PRNG phục vụ mô phỏng

### LCG: trạng thái chính là đầu ra

[Linear Congruential Generator](/posts/math/stats/linear-congruential-generator/) cập nhật

$$
x_{n+1}=(ax_n+c)\bmod m
$$

rồi thường chuẩn hoá trực tiếp $x_n$ thành số trong $[0,1)$. LCG nhỏ, nhanh và rất dễ học, nhưng quan hệ tuyến tính làm các bộ số liên tiếp nằm trên những mặt phẳng song song. Nó phù hợp để giải thích nguyên lý và đôi khi làm thành phần bên trong một thiết kế mạnh hơn, không phải lựa chọn mặc định cho mô phỏng quan trọng.

### PCG: giữ bước chuyển, che cấu trúc ở đầu ra

PCG dùng một bước chuyển đồng dư nhưng đưa trạng thái qua một phép hoán vị trước khi xuất:

$$
x_{n+1}=(ax_n+c)\bmod 2^b,
\qquad
y_n=\pi(x_n).
$$

Phần đồng dư quản lý chu kỳ và luồng; hàm $\pi$ trộn các bit đầu ra. Bài [Từ LCG đến PCG64DXSM](/posts/math/stats/pcg-to-pcg64dxsm/) trình bày chi tiết cách PCG64DXSM gia cố lớp trộn cho bối cảnh song song. Ý tưởng “bước chuyển đơn giản + output permutation” là đóng góp trung tâm của [họ PCG](https://www.pcg-random.org/paper.html).

### Xorshift, xoroshiro và xoshiro

Xorshift dùng các phép XOR và dịch bit để cập nhật trạng thái rất nhanh. `xorshift*` nhân đầu ra với một hằng số để che bớt cấu trúc tuyến tính. Các họ **xoroshiro** và **xoshiro** dùng những bố cục trạng thái dựa trên XOR, shift và rotate, kết hợp scrambler đầu ra như `+`, `++` hoặc `**`.

Chúng có trạng thái nhỏ, tốc độ cao và nhiều biến thể hỗ trợ jump để chia luồng. Tuy nhiên, đây vẫn là PRNG phi mật mã. Trang của các tác giả [xoshiro/xoroshiro](https://prng.di.unimi.it/) cũng nhấn mạnh việc chọn đúng biến thể cho đúng loại đầu ra thay vì xem mọi thành viên trong họ là tương đương.

### Mersenne Twister: đổi trạng thái lớn lấy chu kỳ rất dài

MT19937 có chu kỳ $2^{19937}-1$ và trạng thái nội bộ xấp xỉ 20.000 bit. [Công trình gốc của Matsumoto và Nishimura](https://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/ARTICLES/earticles.html) còn xây dựng tính phân bố đều ở nhiều chiều, khiến Mersenne Twister trở thành lựa chọn mặc định lịch sử của nhiều thư viện.

Đổi lại, trạng thái lớn tốn bộ nhớ, việc tạo nhiều luồng độc lập không tự nhiên như ở các thiết kế mới, và đầu ra không khó dự đoán khi trạng thái đã bị suy ra. Chu kỳ khổng lồ không đồng nghĩa với an toàn mật mã.

### LXM: ghép hai động cơ rồi trộn

Tên **LXM** mô tả ba thành phần:

- **L:** một linear congruential generator;
- **X:** một xor-based generator, thường thuộc họ xoroshiro hoặc xoshiro;
- **M:** một mixing function áp dụng lên tổng đầu ra của hai phần trước.

Mỗi động cơ bù cho cấu trúc của động cơ kia, còn mixer che các quan hệ đơn giản còn sót lại. [Bài báo LXM của Steele và Vigna](https://air.unimi.it/handle/2434/891478) thiết kế họ này cho các ứng dụng khoa học, học máy và chương trình song song có nhu cầu tách luồng; tác giả nói rõ đây không phải bộ sinh mật mã.

### Counter-based: biến chỉ số thành địa chỉ của điểm ngẫu nhiên

Một counter-based PRNG tính trực tiếp

$$
y=F_k(\text{counter}),
$$

thay vì buộc phải đi tuần tự từ $s_n$ tới $s_{n+1}$. Counter xác định vị trí, key xác định luồng, còn hàm $F$ trộn chúng thành đầu ra. Nhờ vậy, worker thứ $j$ có thể được cấp một miền counter hoặc key riêng mà không chia sẻ trạng thái với worker khác.

Hai họ nổi tiếng trong [Random123](https://www.thesalmons.org/john/random123/releases/1.11.2pre/docs/) là **Philox**, dùng phép nhân số nguyên và mạng kiểu Feistel, và **Threefry**, phát triển từ ý tưởng của block cipher Threefish. Khả năng truy cập trực tiếp khiến chúng đặc biệt tự nhiên trên GPU và hệ thống song song lớn.

## 5. CSPRNG: tính khó dự đoán là một yêu cầu khác

Một PRNG có thể vượt qua nhiều kiểm định thống kê nhưng vẫn hoàn toàn không an toàn. Với token, khoá, nonce hoặc salt, đối thủ được giả định là biết thuật toán và có thể quan sát nhiều đầu ra. Thiết kế phải ngăn họ suy ra trạng thái hoặc dự đoán phần đầu ra chưa thấy với chi phí khả thi.

Các CSPRNG vẫn là thuật toán tất định sau khi nhận seed. Điểm khác biệt nằm ở primitive mật mã, cách quản lý trạng thái và mô hình đối thủ:

- **ChaCha-based CSPRNG:** dùng block function của stream cipher ChaCha với key và counter. OpenBSD từng mô tả cách entropy pool cung cấp key cho ChaCha trong họ hàm [`arc4random`](https://man.openbsd.org/OpenBSD-6.5/arc4random.9).
- **CTR_DRBG:** dùng block cipher, thường là AES, để biến dãy counter thành đầu ra.
- **HMAC_DRBG:** cập nhật trạng thái và sinh bit bằng HMAC.
- **Hash_DRBG:** xây dựng quá trình cập nhật và sinh bit từ hàm hash.

Ba DRBG sau được đặc tả trong [NIST SP 800-90A Rev. 1](https://csrc.nist.gov/pubs/sp/800/90/a/r1/final). Tên thuật toán chưa đủ để bảo đảm một triển khai an toàn: seed material, reseed, giới hạn số byte sinh ra, xoá trạng thái và xử lý fork đều thuộc thiết kế hoàn chỉnh.

Trong mã ứng dụng, nên gọi API của hệ điều hành hoặc thư viện chuẩn thay vì tự lắp CSPRNG. Chẳng hạn, Python khuyến nghị [`secrets`](https://docs.python.org/3/library/secrets.html) cho mật khẩu và token; mô-đun này lấy dữ liệu từ nguồn ngẫu nhiên an toàn nhất mà hệ điều hành cung cấp.

## 6. Seed, entropy và output không phải cùng một thứ

Luồng xử lý thực tế thường có dạng:

<div class="rng-seed-pipeline" role="img" aria-label="Mẫu nhiễu đi qua kiểm tra sức khoẻ và conditioning để tạo seed material, thiết lập trạng thái DRBG rồi sinh output bytes">
  <span>noise samples</span><b aria-hidden="true">→</b><span>health tests + conditioning</span><b aria-hidden="true">→</b><span>seed material</span><b aria-hidden="true">→</b><span>DRBG state</span><b aria-hidden="true">→</b><span>output bytes</span>
</div>

Điều này giải thích vì sao hệ điều hành không cần đo một hiện tượng vật lý cho từng byte trả về. Linux mô tả kernel RNG là một CSPRNG được seed bằng entropy thu từ device drivers và các nguồn nhiễu môi trường; với ứng dụng mô phỏng cần lượng dữ liệu lớn, tài liệu [`random(7)`](https://www.man7.org/linux/man-pages/man7/random.7.html) khuyên chỉ lấy một lượng nhỏ từ hệ điều hành để seed cho PRNG ở user space.

Reseed cũng không có nghĩa là “đổ thêm vài bit bất kỳ”. Entropy mới phải khó dự đoán đối với đối thủ và được trộn vào trạng thái đúng cách. Ngược lại, đối với thí nghiệm khoa học cần tái lập bit-for-bit, ta thường **cố ý lưu seed và tên thuật toán**, không tự động reseed giữa chừng.

## 7. Chọn công cụ theo câu hỏi

| Nhu cầu | Lựa chọn điển hình | Lý do |
|---|---|---|
| Học nguyên lý PRNG | LCG | Công thức tối giản, thấy rõ chu kỳ và lattice |
| Mô phỏng tuần tự, cần tái lập | PCG64DXSM, xoshiro, LXM | Nhanh, trạng thái gọn, chất lượng thống kê tốt |
| GPU hoặc hàng triệu tác vụ song song | Philox, Threefry | Chia miền counter/key, không cần trạng thái chung |
| Tái lập kết quả từ một hệ thống cũ | Đúng thuật toán và phiên bản đã dùng, có thể là MT19937 | Khả năng tương thích quan trọng hơn việc đổi bộ sinh |
| Token, mật khẩu, khoá, nonce | API CSPRNG của hệ điều hành; trong Python dùng `secrets` | Cần tính khó dự đoán trước đối thủ |
| Một tập hữu hạn điểm phủ miền thật đều | [Scrambled Sobol](/posts/math/stats/sobol-sequence/) | Đây là Quasi-Monte Carlo, mục tiêu là giảm khoảng trống chứ không mô phỏng IID |

Không nên chọn bộ sinh chỉ bằng cách hỏi “thuật toán nào ngẫu nhiên nhất?”. Câu hỏi đúng hơn là: cần tái lập hay khó dự đoán, chạy tuần tự hay song song, cần một luồng dài hay truy cập trực tiếp, và đầu ra được dùng cho mô phỏng hay cho bí mật mật mã?

## 8. Tổng kết

Toàn bộ bức tranh có thể nén thành ba tầng:

1. **Nguồn entropy** đo sự bất định từ thế giới thực và cung cấp seed hoặc reseed.
2. **PRNG phi mật mã** ưu tiên tốc độ, chất lượng thống kê, khả năng tái lập và chia luồng cho mô phỏng.
3. **CSPRNG/DRBG** dùng primitive mật mã và quản lý trạng thái chặt chẽ để chống dự đoán.

LCG, PCG, xoshiro, Mersenne Twister, LXM và Philox không phải các nấc trên một thang đo duy nhất. Chúng là những điểm khác nhau trong không gian thiết kế. Hiểu nguồn entropy đi vào đâu, trạng thái biến đổi thế nào và đầu ra phải chống loại rủi ro nào quan trọng hơn việc ghi nhớ một danh sách tên thuật toán.