Trình Tạo Số Ngẫu Nhiên

Về trình tạo này

Máy tính là cỗ máy tất định, điều đó làm cho việc sinh "ngẫu nhiên" trở nên kỳ lạ. Lịch sử các bộ sinh số giả ngẫu nhiên (PRNG) trên máy tính bắt đầu với phương pháp bình phương ở giữa của John von Neumann năm 1946, bình phương số trước đó, lấy các chữ số ở giữa làm giá trị mới, lặp lại. Chính von Neumann gọi việc dùng bộ sinh số ngẫu nhiên mà không hiểu trọn vẹn là "trạng thái có tội", vì bình phương ở giữa có các chế độ thất bại rõ rệt (chu trình về không, chu kỳ ngắn). Bộ sinh đồng dư tuyến tính của Lehmer (LCG, 1951), x_(n+1) = (a × x_n + c) mod m, là họ PRNG đầu tiên có tính chất thống kê hợp lý; rand() của thư viện chuẩn C vẫn thường dùng biến thể LCG. Mersenne Twister (Matsumoto và Nishimura, 1997-1998) cho ta bộ sinh có chu kỳ 2¹⁹⁹³⁷−1 (đúng vậy, một số 6.000 chữ số) và tính chất thống kê xuất sắc; trở thành mặc định trong Python, R, MATLAB, PHP và nhiều ngôn ngữ khác. Họ xorshift của Marsaglia (2003) nhanh hơn nhiều và đủ nhỏ để vừa trong một thanh ghi phần cứng; V8 hiện đại (engine JavaScript của Chrome) dùng biến thể xorshift128+ cho Math.random(). PCG (Permuted Congruential Generator) của Melissa O'Neill (2014) là trạng thái nghệ thuật hiện tại về thống kê cho PRNG không-mật-mã, kết hợp tiến trạng thái kiểu LCG với hoán vị đầu ra để có tính chất thống kê tuyệt vời ở chi phí thấp.

PRNG an toàn về mật mã (CSPRNG) là một loài khác. Tính chất định nghĩa: dù kẻ tấn công biết mọi đầu ra trước đây của bộ sinh, họ không thể đoán đầu ra kế tiếp với lợi thế tốt hơn không đáng kể. System call getrandom() của Linux (thêm trong kernel 3.17, tháng 10 năm 2014) và /dev/urandom bên dưới dùng bộ sinh dựa trên ChaCha20 được seed bởi nguồn entropy phần cứng (RDRAND, thời điểm ngắt, nhiễu âm thanh). BCryptGenRandom của Windows dùng kiến tạo AES-CTR-DRBG (NIST SP 800-90A) seed từ nhiều nguồn entropy. macOS / iOS dùng CSPRNG dẫn xuất từ Fortuna. Khác biệt giữa PRNG và CSPRNG quan trọng to lớn: PRNG hợp với ngẫu nhiên trong game, bucketing A/B testing, hoặc mô phỏng; cho mọi thứ kẻ tấn công có thể cố đoán (token phiên, sinh mật khẩu, định danh bảo mật), chỉ CSPRNG mới an toàn.

Hai API ngẫu nhiên của JavaScript

Math.random() là API cũ và đơn giản, trả về số dấu chấm động phân phối xấp xỉ đều trong [0, 1). Đặc tả ECMAScript có chủ ý để thuật toán bên dưới không được nêu cụ thể ("approximately uniform distribution between 0 and 1, exclusive"), và các engine đã đổi cái họ dùng qua nhiều năm. V8 (Chrome) dùng Park-Miller LCG đến 2015, sau đó chuyển sang xorshift128+ để có tính chất thống kê tốt hơn. SpiderMonkey (Firefox) và JavaScriptCore (Safari) dùng các bộ sinh không-mật-mã nhanh tương tự. Math.random() đủ nhanh và đều cho cơ chế game, mô phỏng, và mọi ứng dụng nơi tính khó-đoán không phải yêu cầu bảo mật. Nó không an toàn về mật mã, chu kỳ do triển khai định nghĩa, trạng thái có thể được khôi phục từ một số ít đầu ra, và chuỗi không an toàn cho việc sinh mật khẩu hay các trường hợp dùng nhạy cảm với bảo mật. crypto.getRandomValues() là CSPRNG của Web Crypto API. Nó đổ vào một typed array các byte ngẫu nhiên an toàn về mật mã lấy từ CSPRNG của hệ điều hành (cùng nguồn TLS dùng cho khóa phiên). Có sẵn trong mọi trình duyệt hiện đại từ khoảng 2014; kích thước buffer tối đa trong một lần gọi là 65.536 byte. Lựa chọn đúng cho mọi số ngẫu nhiên quan trọng, sinh token, định danh bảo mật, sinh mật khẩu, mọi thứ kẻ tấn công có thể cố đoán.

Cái bẫy lệch modulo

Sinh một số nguyên đều trong dải cụ thể từ một CSPRNG khó hơn vẻ ngoài. Cách tiếp cận ngây thơ, crypto.getRandomValues(new Uint8Array(1))[0] % 6 cho cú lăn xúc xắc, sinh phân phối lệch vì 256 không chia đều cho 6. Giá trị 0-3 mỗi cái xuất hiện 43 lần trong dải 0-255; giá trị 4-5 xuất hiện 42 lần. Lệch nhỏ với dải nhỏ nhưng có thật, và phát hiện được trên các chuỗi dài. Cách sửa chuẩn là lấy mẫu có loại bỏ: sinh một byte ngẫu nhiên, kiểm tra nó có rơi trong bội số lớn nhất của dải bạn vừa với (ở đây, 252 = 42 × 6), dùng nếu có, vứt và thử lại nếu không. Tỉ lệ loại bỏ bị giới hạn bởi (dải / lũy thừa 2 kế tiếp), nên cho "1-6" bạn lãng phí khoảng 1,5% byte; cho "1-1000000" với số nguyên ngẫu nhiên 32 bit, bạn lãng phí khoảng 0,02%. Mọi thư viện ngẫu nhiên nghiêm túc đều cài lấy mẫu có loại bỏ; Math.floor(Math.random() * (max - min + 1)) + min dựa trên Math.random() tránh được lệch vì độ chính xác của Math.random() cao đủ (53 bit định trị) để lệch nằm dưới mức con người phát hiện được trên mọi dải hợp lý. Bộ sinh này dùng đầu ra CSPRNG với lấy mẫu có loại bỏ, đầu ra đều trên mọi dải số nguyên yêu cầu.

Trường hợp dùng và mức ngẫu nhiên cần cho mỗi cái

• Bốc thăm và xổ số. Cho việc bốc thăm phi tiền tệ (đổi bàn làm việc, chia đội cho hackathon, sơ đồ chỗ ngồi lớp), Math.random() dùng được. Cho bốc thăm có tiền hoặc bất kỳ thứ gì bị quản lý, hãy dùng CSPRNG và lý tưởng là công bố seed để có khả năng kiểm chứng.
• Cơ chế game. Lăn xúc xắc, xáo bài, vật phẩm rơi, sinh thủ tục. Math.random() là lựa chọn chuẩn, nhanh, đủ đều, đủ khó-đoán để người chơi không nhận ra khuôn mẫu. CSPRNG dành cho game bài online nơi server phải ngăn gian lận.
• Phân chia bucket cho A/B testing. Hash định danh người dùng với một bí mật ổn định để đặt mỗi người vào một bucket một cách tất định; dùng Math.random() sẽ làm người dùng rơi vào bucket khác nhau qua các lần tải trang, phá hỏng trải nghiệm. Phân chia bằng hash là khuôn mẫu đúng; ngẫu nhiên chỉ phục vụ việc chọn seed của thí nghiệm, một lần duy nhất.
• Lấy mẫu ngẫu nhiên cho khảo sát. Rút một tập con đại diện từ dân số. Math.random() dùng được; câu hỏi thống kê là mẫu của bạn có đủ lớn không, không phải nguồn ngẫu nhiên có an toàn về mật mã không.
• Sinh dữ liệu kiểm thử. Faker, dữ liệu mock, fixture cơ sở dữ liệu tổng hợp. Math.random() với seed cố định (cho khả năng tái lập) là lựa chọn đúng.
• Khóa mật mã, token phiên, sinh mật khẩu. Chỉ CSPRNG, crypto.getRandomValues() trong trình duyệt, module secrets trong Python, crypto/rand trong Go, không bao giờ là ngẫu nhiên mặc định của ngôn ngữ. Một bug ở tầng này làm tổn hại mọi thứ phụ thuộc vào nó; hậu quả từ "phiên của mọi người đều có thể bị chiếm" đến "khóa mã hóa có thể khôi phục".

RANDOM.ORG và phân biệt ngẫu nhiên thực sự

RANDOM.ORG được Mads Haahr ra mắt năm 1998 tại Trinity College Dublin và vẫn là tham chiếu của "ngẫu nhiên thật" online. Trong khi mọi CSPRNG cuối cùng dẫn xuất các bit từ biến đổi thuật toán của một trạng thái được seed phần cứng (một quá trình tất định, dù khó đoán với kẻ tấn công), RANDOM.ORG đo nhiễu khí quyển bắt được bằng máy thu radio và chuyển nhiễu analog đó trực tiếp thành bit. Điều đó làm nó là True Random Number Generator (TRNG) chứ không phải Pseudo-Random Number Generator: các bit đến từ một quá trình vật lý xác thực không-tất-định, không phải thuật toán tất định. RANDOM.ORG được các nhà điều hành xổ số, nhà nghiên cứu học thuật làm các nghiên cứu mù đôi, và game nơi tính ngẫu nhiên có thể kiểm chứng quan trọng dùng. Đánh đổi: một lần đi-về mạng cho mỗi yêu cầu, một hạn ngạch mỗi ngày cho hạng miễn phí, và câu hỏi triết học về việc bạn tin nguồn entropy mà RANDOM.ORG tuyên bố hơn CSPRNG cục bộ. Cho phần lớn việc dùng, CSPRNG cục bộ đã đủ; cho các trường hợp một bên thứ ba phải xác minh ngẫu nhiên độc lập, RANDOM.ORG cung cấp chứng nhận ngẫu nhiên đã ký dưới dạng dịch vụ trả phí.

Lấy mẫu không hoàn lại, xáo bài Fisher-Yates

Khi bạn cần N số không trùng trong một dải, chọn 6 số giữa 1 và 49 cho xổ số, chọn 10 người thắng từ 1.000 đăng ký, cách ngây thơ "sinh và loại nếu trùng" hoạt động cho N nhỏ nhưng suy giảm mạnh khi N gần kích thước dải (cơ hội rút số mới giảm khi pool teo lại). Thuật toán chuẩn là xáo Fisher-Yates, có nguồn gốc từ bảng thống kê của Fisher và Yates năm 1938 và được Donald Knuth định dạng hiện đại trong khoa học máy tính năm 1969 (đôi khi gọi là Knuth shuffle). Thuật toán cực kỳ đơn giản: viết các số 1 đến N vào một mảng; cho i từ N-1 xuống 1, đổi chỗ phần tử i với một phần tử ngẫu nhiên giữa 0 và i (bao gồm); mảng giờ được xáo đều. Lấy K phần tử đầu cho K số ngẫu nhiên không trùng. Chi tiết then chốt: chỉ số ngẫu nhiên phải nằm trong [0, i], bao gồm, dùng [0, i-1] đưa vào lệch tinh tế mà cộng đồng mật mã đã mất nhiều năm để mô tả (biến thể Sattolo, đôi khi bị dùng nhầm thay cho Fisher-Yates thật). Cho dải rất lớn nơi cấp phát mảng tất cả N giá trị không thực tế (ví dụ chọn 100 giá trị duy nhất giữa 1 và 10⁹), lấy mẫu hồ chứa (Vitter, 1985) xử lý đầu vào theo luồng hoặc không có giới hạn trong một lượt với bộ nhớ có giới hạn.

Quy ước lăn xúc xắc

Bộ sinh số ngẫu nhiên là xúc xắc cải trang. D6 (xúc xắc sáu mặt) là mặc định phổ quát của board game, dải 1-6. D20 (xúc xắc hai mươi mặt) là xúc xắc biểu tượng của Dungeons & Dragons dùng cho kiểm tra khả năng, lăn tấn công và lăn cứu, hệ thống bonus của D&D làm cho một cú lăn D20 cộng bonus thuộc tính quyết định kết quả phần lớn hành động. D100 (phần trăm, 1-100) được dùng cho lăn phần trăm trong Call of Cthulhu, Warhammer Roleplay và nhiều hệ thống xác suất nguy kịch. Ký pháp NdM nghĩa là "lăn N xúc xắc M mặt mỗi cái và cộng"; NdM+B thêm bonus. 3d6 lăn ba xúc xắc sáu mặt và cộng (dải 3-18, dải điểm thuộc tính kinh điển của D&D, với phân phối tam giác xoay quanh 10-11). Cho mô phỏng công bằng, sinh một số nguyên đều trong [1, M] cho mỗi xúc xắc và cộng là tương đương chính xác với lăn xúc xắc vật lý, phân phối CSPRNG bên dưới đều hơn bất kỳ xúc xắc vật lý nào bạn có thể mua. Sòng bạc và game được quản lý dùng RNG chứng nhận đã được kiểm thử bằng các bộ pin thống kê (BigCrush của TestU01, NIST SP 800-22) để chứng minh tính đều cho cơ quan quản lý; cùng tiêu chuẩn áp dụng cho RNG xổ số.

Seed và khả năng tái lập

Một tính chất tinh tế nhưng quan trọng của PRNG: chúng tất định cho một seed cho trước. Cố định seed về một giá trị đã biết, và chuỗi số "ngẫu nhiên" chính xác có thể tái lập. Vô giá cho kiểm thử (một unit test dùng dữ liệu ngẫu nhiên nên cố định seed để các thất bại tái lập được) và cho bốc thăm có thể kiểm chứng (công bố seed trước khi bốc, rồi ai cũng có thể xác minh kết quả). Module random của Python có random.seed(value) cho việc đó; Random của Java nhận seed trong constructor. Math.random() của JavaScript có chủ ý không phơi ra API seed, các engine xem seed như trạng thái nội bộ, nhưng nhiều thư viện thuần JS (seedrandom, pcg-random) cung cấp PRNG có seed. CSPRNG theo thiết kế là khác: chúng không phơi ra seed vì ý nghĩa duy nhất là tính khó-đoán. Nếu bạn cần tái lập, hãy dùng PRNG có seed tường minh; nếu bạn cần bảo mật, hãy dùng CSPRNG và chấp nhận rằng bạn không thể tái lập chuỗi sau đó.

Quyền riêng tư: vì sao chỉ trong trình duyệt, ngay cả với số ngẫu nhiên

Bản thân số ngẫu nhiên hiếm khi chứa thông tin nhạy cảm, vậy vì sao kiến trúc thuần trình duyệt quan trọng? Hai lý do. Thứ nhất, khi một số ngẫu nhiên được dùng làm token phiên, idempotency key, thử thách xác thực, hoặc bất kỳ giá trị bí mật nào khác, sinh nó trên server bên thứ ba nghĩa là server đó đã thấy giá trị trước khi bạn dùng, một phơi bày nhỏ nhưng có thật. Thứ hai, các bộ sinh phía server hứa "ngẫu nhiên mật mã" không thể được người dùng kiểm chứng; một server có lỗi hoặc độc hại có thể trả về giá trị không-ngẫu-nhiên hoặc lệch trông như ngẫu nhiên, và bạn không có cách nào phát hiện lệch nếu không lấy mẫu khổng lồ. Một bộ sinh chỉ-trình-duyệt thực thi cùng cuộc gọi crypto.getRandomValues() mà ứng dụng của bạn sẽ thực thi phía server; entropy đến từ cùng nguồn hệ điều hành (Linux getrandom(), Windows BCryptGenRandom, macOS); không có bên thứ ba nào thấy đầu ra. Bạn có thể kiểm chứng bằng cách mở tab Network của DevTools khi bấm Sinh, không có request đi ra. Đặt trang offline (chế độ máy bay) sau khi đã tải xong và bộ sinh vẫn hoạt động.

Câu hỏi thường gặp