Trình tạo số ngẫu nhiên là gì?
Trình tạo số ngẫu nhiên (RNG) là một hệ thống tạo ra các số ngẫu nhiên hoặc giả ngẫu nhiên. Việc số tiếp theo có thực sự dự đoán được hay không phụ thuộc vào loại trình tạo. Một số trình tạo dựa trên một quá trình vật lý, một số tính toán số bằng thuật toán, và một số thuật toán được xây dựng để ngay cả người đã nhìn thấy kết quả trước đó cũng không thể dự đoán điều gì sẽ xảy ra tiếp theo. Trông có vẻ ngẫu nhiên và thực sự không thể đoán trước là hai đặc tính khác nhau, và phần lớn bài viết này nói về sự khác biệt đó.
Trình tạo số ngẫu nhiên phần cứng
Trình tạo số ngẫu nhiên phần cứng (HRNG), còn được gọi là trình tạo số ngẫu nhiên thực sự (TRNG), lấy số từ một quá trình vật lý. Những công cụ lâu đời nhất hoạt động ngay trước mắt chúng ta: đồng xu được tung lên, viên xúc xắc được gieo, bánh xe roulette quay. Cơ học mô tả đầy đủ từng hiện tượng đó, nhưng một bánh xe được chế tạo tốt vẫn không thể đoán trước trong thực tế, bởi vì những khác biệt nhỏ trong cách mỗi vòng quay bắt đầu sẽ phát triển thành những kết quả hoàn toàn khác nhau.
Thay vào đó, các trình tạo phần cứng hiện đại đo lường các hiện tượng vi mô: nhiễu hạt (shot noise) và nhiễu nhiệt trong mạch điện tử, nhiễu khí quyển, các hiệu ứng lượng tử. Đây là những nguồn entropy tốt — sự không thể đoán trước có thể đo lường được — nhưng một nguồn vật lý không hoàn hảo về bản chất: nó có thể bị lệch, có thể trôi theo thời gian và có thể hỏng hóc, do đó chất lượng của nó phải được đánh giá và theo dõi, và kết quả đầu ra cần được xử lý thêm khi cần thiết, như các tiêu chuẩn như NIST SP 800-90B mô tả. Các nguồn phần cứng được sử dụng ở nơi mà sự đảm bảo là quan trọng nhất — trên hết là trong mật mã học, nơi chúng cung cấp vật liệu khởi đầu không thể đoán trước cho các khóa đằng sau các giao thức như Transport Layer Security (TLS).
Trình tạo số giả ngẫu nhiên
Giải pháp thay thế cho thiết bị vật lý là một thuật toán. Trình tạo số giả ngẫu nhiên (PRNG) tạo ra một chuỗi trông có vẻ ngẫu nhiên nhưng hoàn toàn được xác định bởi một giá trị ban đầu gọi là hạt giống (seed). Cung cấp cùng một hạt giống cho cùng một thuật toán và bạn sẽ nhận được cùng một chuỗi số mỗi lần. Đó là một điểm yếu ở bất cứ nơi nào kết quả phải không thể đoán trước và hạt giống hoặc trạng thái nội bộ có thể bị đoán hoặc tái tạo lại; nhưng lại là một điểm mạnh ở nơi kết quả cần có thể tái lập — một mô phỏng hoặc thử nghiệm có thể được chạy lại một cách chính xác. PRNG cũng nhanh, chi phí thấp và dễ triển khai, đó là lý do tại sao hầu hết phần mềm đều dựa vào chúng. Các thuật toán nổi tiếng bao gồm bộ tạo đồng dư tuyến tính (LCG), các trình tạo xorshift và Mersenne Twister.
Mersenne Twister
Mersenne Twister, được Makoto Matsumoto và Takuji Nishimura công bố vào năm 1997, là một trong những trình tạo số giả ngẫu nhiên được sử dụng rộng rãi nhất và là mặc định trong nhiều ngôn ngữ lập trình. Tên của nó bắt nguồn từ chu kỳ — độ dài của chuỗi trước khi nó lặp lại — trong biến thể tiêu chuẩn MT19937 là số nguyên tố Mersenne 219937 − 1. Nó vượt qua hầu hết các bài kiểm tra thống kê về tính ngẫu nhiên và phù hợp cho các mô phỏng. Tuy nhiên, nó không được thiết kế để giữ bí mật: từ 624 kết quả 32-bit liên tiếp, bất kỳ ai cũng có thể tái tạo trạng thái nội bộ của nó và dự đoán mọi giá trị tiếp theo, vì vậy không được sử dụng nó cho các khóa, mật khẩu hoặc bất kỳ thứ gì khác cần phải duy trì tính không thể đoán trước.
Trình tạo an toàn mật mã và entropy
Nhiều ứng dụng cần cả hai thứ cùng một lúc: tốc độ của thuật toán và tính không thể đoán trước của nguồn vật lý. Câu trả lời là trình tạo số giả ngẫu nhiên an toàn về mặt mật mã (CSPRNG). Nó vẫn là một PRNG, nhưng được xây dựng để việc nhìn thấy một phần kết quả đầu ra không mang lại cách thực tế nào để dự đoán phần còn lại, và nó được gieo hạt giống cũng như thường xuyên được gieo lại hạt giống từ một nguồn entropy thực sự. Một hạt giống từ nguồn vật lý không làm cho một PRNG thông thường trở nên an toàn; chính thuật toán phải được thiết kế cho việc đó. Một nguồn vật lý như nhiễu nhiệt hoặc thời gian của các sự kiện phần cứng cung cấp một lượng nhỏ tính ngẫu nhiên thực sự, và từ đó CSPRNG nhanh hơn nhiều tạo ra một chuỗi giá trị dài. Sự kết hợp này là những gì hệ điều hành cung cấp cho các chương trình chạy trên đó, và đó là những gì "trình tạo số ngẫu nhiên" thường mang ý nghĩa trong thực tế hiện nay. Nó tạo ra các khóa mã hóa, mã thông báo phiên và mật khẩu.
Số ngẫu nhiên trong trình duyệt
JavaScript cung cấp cho trang web hai cách tích hợp sẵn để nhận các giá trị ngẫu nhiên, và chúng thuộc các lớp khác nhau. Math.random() là một PRNG thông thường: tiêu chuẩn ngôn ngữ để mặc thuật toán cho từng trình duyệt và không đưa ra cam kết nào về tính bảo mật — phù hợp cho hoạt ảnh, nhưng không phù hợp cho một buổi quay thưởng có thể bị khiếu nại. Cách còn lại là Web Crypto API. Phương thức crypto.getRandomValues() của nó trả về các giá trị ngẫu nhiên mạnh mẽ về mặt mật mã, được tạo ra bởi một CSPRNG được gieo hạt giống bằng entropy của hệ điều hành.
Trình tạo số ngẫu nhiên trực tuyến của chúng tôi sử dụng Web Crypto API cho mỗi lần tạo số, và các con số được tạo ra ngay trong trình duyệt của bạn chứ không phải trên máy chủ. Nguồn tương tự này cũng vận hành các trình tạo khác trên trang web này, cho dù bạn đổ xúc xắc, tung đồng xu hay tạo mật khẩu với trình tạo mật khẩu.
Từ các bit ngẫu nhiên đến một con số trong phạm vi của bạn
Một trình tạo an toàn về mặt mật mã chỉ là một nửa của một lượt quay thưởng công bằng. Nó cung cấp các bit thô, và chương trình vẫn phải biến chúng thành một con số trong phạm vi bạn cần — và đây là nơi sự thiên vị (modulo bias) có thể len lỏi vào. Giả sử nguồn cung cấp các giá trị từ 0 đến 9 với cơ hội bằng nhau và bạn cần một số từ 0 đến 5. Lấy phần dư sau khi chia cho 6 có vẻ tự nhiên, nhưng 0, 1, 2 và 3 sau đó có thể xuất hiện theo hai cách và 4 cùng 5 chỉ theo một cách; do đó mỗi số từ 0 đến 3 có 20% cơ hội, còn 4 và 5 chỉ có 10% mỗi số. Một cách để loại bỏ sự thiên vị là loại bỏ các giá trị không vừa vặn và rút lại; mục tài liệu số ngẫu nhiên sẽ đi sâu vào chi tiết điều này.
Hai điều nữa thường khiến mọi người ngạc nhiên. Việc lặp lại là bình thường: khi một số nguyên từ 1 đến 10 được rút độc lập và mỗi số có xác suất như nhau, con số vừa rút có cùng 1 trên 10 cơ hội xuất hiện lại như bất kỳ số nào khác. Một lượt rút không lặp lại là một kiểu rút khác, chứ không phải ngẫu nhiên hơn. Và một trình tạo công bằng đơn thuần không làm cho toàn bộ quy trình trở nên công bằng: danh sách người tham gia và số lần thực hiện cũng quan trọng không kém, như bài viết của chúng tôi về cách chọn người chiến thắng ngẫu nhiên giải thích.