Trình tạo số

Trình (công cụ) tạo số ngẫu nhiên là một quá trình lấy số ngẫu nhiên mỗi khi chúng ta cần, mà chúng ta không thể xác định một số cụ thể từ các số được tạo trước đó. Con số này có thể được tạo ra bằng thuật toán hoặc thiết bị phần cứng.

Ứng dụng của trình tạo số ngẫu nhiên

Việc tạo số ngẫu nhiên thường cần thiết cho nhiều nhiệm vụ khác nhau, từ trò chơi máy tính đến các ứng dụng thông thường. Ví dụ, hệ thống sử dụng trình tạo số ngẫu nhiên để hiển thị một banner ngẫu nhiên hoặc một đơn vị quảng cáo ngẫu nhiên trên một trang web. Trong mật mã học, số ngẫu nhiên cũng được sử dụng để tạo ra một mã hoặc khóa duy nhất.

Việc tạo số ngẫu nhiên được sử dụng để tạo các số hoặc văn bản cho hình ảnh xác thực, mã hóa, tạo salt để lưu trữ mật khẩu, sử dụng trong trình tạo mật khẩu, thứ tự lá bài trong sòng bạc trực tuyến, sử dụng trong việc ra quyết định, lấy mẫu và mô phỏng.

Thuật toán tạo số ngẫu nhiên thường được sử dụng trong các trò chơi video. Ngay cả khi bạn chơi ở cùng một cấp độ trong một trò chơi, nhưng nó sẽ không hoàn toàn giống nhau mỗi khi bạn cố gắng hoàn thành một nhiệm vụ. Có thể sự khác biệt không được nhìn thấy ở vị trí hoặc nhiệm vụ. Tuy nhiên, chúng sẽ được thấy ở số lượng kẻ thù tiếp cận và các khu vực mà chúng xuất hiện, sự thay đổi khí hậu và các rào cản khác nhau gặp phải. Điều này làm cho trò chơi trở nên hấp dẫn hơn.

Sự khác biệt giữa một chuỗi ngẫu nhiên và một chuỗi không ngẫu nhiên

Ví dụ dãy số: 1 , 2 , 3 , 4 , 5. Có phải là dãy số ngẫu nhiên không?

Một biến ngẫu nhiên là một biến mà trong một lần thử có thể nhận một trong tập hợp các giá trị. Và bạn không thể dự đoán chính xác sự xuất hiện của một giá trị cụ thể trước khi nó xuất hiện.

Giả sử các số đã cho có được bằng cách gõ vào một trong các hàng trên cùng của bàn phím. Trong trường hợp này, hóa ra sự kết hợp này không phải là ngẫu nhiên vì sau số 5, số tiếp theo là số 6, có thể được dự đoán với xác suất cao.

Một chuỗi sẽ được coi là ngẫu nhiên chỉ khi không có sự phụ thuộc giữa các ký tự.

Điều kiện cơ bản, mà vô cùng quan trọng cho nguyên tắc chính xác và công bằng của trình tạo số ngẫu nhiên, là xác suất tuyệt đối bằng nhau của bất kỳ số nào có thể xuất hiện trong hệ thống này. Điều này chỉ ra sự độc lập hoàn toàn của yếu tố ngẫu nhiên và sự độc lập của những số khác xuất hiện trước hoặc sau số ngẫu nhiên.

Ví dụ, giả sử bạn tung một con xúc xắc sáu mặt lần đầu tiên. Trong trường hợp đó, bạn có thể có bất kỳ số nào từ 1 đến 6 xuất hiện với cùng một xác suất. Bất kể số bạn nhận được, bạn có thể tung xúc xắc lại với cùng một cơ hội để nhận được cùng một số trong lần tung thứ hai, lần thứ một trăm hoặc lần thứ một nghìn.

Các chuỗi chữ số trong số Pi dường như không có sự lặp lại, và đối với nhiều người, nó có vẻ là ngẫu nhiên. Giả sử trình tạo số ngẫu nhiên của chúng ta dựa trên biểu diễn bit của Pi, bắt đầu từ một điểm không biết trước. Một trình tạo số như vậy có thể không thể đoán trước trong nhiều ngữ cảnh, có thể vượt qua một số bài kiểm tra về tính ngẫu nhiên. Tuy nhiên, việc dựa vào Pi cho mục đích mật mã tiềm ẩn những rủi ro. Nếu một kẻ xấu xác định được một đoạn cụ thể của Pi đang được sử dụng, họ có thể dự đoán được cả các đoạn trước và sau đó, từ đó đe dọa tính bảo mật của hệ thống.

Viện Tiêu chuẩn và Công nghệ Quốc gia Hoa Kỳ đã đề xuất "Bộ thử nghiệm thống kê cho Trình tạo số ngẫu nhiên và Giả ngẫu nhiên cho Ứng dụng Mật mã." Nó bao gồm 15 thử nghiệm thống kê với mục đích xác định mức độ ngẫu nhiên của các bit được tạo ra bởi cả trình tạo phần cứng và phần mềm.

Các loại công cụ tạo số ngẫu nhiên

Có hai loại trình tạo số ngẫu nhiên (RNG): trình tạo số ngẫu nhiên thực (TRNG) và trình tạo số ngẫu nhiên giả (PRNG). TRNG sử dụng hiện tượng vật lý để tạo ra các số, trong khi PRNG sử dụng các thuật toán toán học.

Một thuật toán tạo số ngẫu nhiên thực được tạo ra với một thiết bị phần cứng sử dụng các quy trình vật lý nhỏ để tạo ra các số ngẫu nhiên, tức là entropy. Entropy là sự hỗn loạn thuần túy, không có chọn lọc.

Trình tạo số ngẫu nhiên thực sử dụng các hiện tượng vật lý như:

• phóng xạ,
• nhiễu nhiệt,
• nhiễu điện từ,
• cơ học lượng tử, và những hiện tượng khác.

Một TRNG (trình tạo số ngẫu nhiên thực) thường được sử dụng trong các hệ thống hướng tới tính bảo mật trên toàn thế giới và một số dạng của mã hóa.

Các trình tạo số ngẫu nhiên sử dụng các nguồn entropy để tích lũy entropy và nhận giá trị ban đầu (seed) cần thiết cho trình tạo số ngẫu nhiên.

Thuật toán trình tạo số ngẫu nhiên giả được sử dụng trong các lĩnh vực không đặt ra mối quan tâm lớn về bảo mật. Tính ngẫu nhiên giúp tránh sự lặp lại và làm cho quy trình trở nên hấp dẫn hơn đối với người dùng cuối. Chi phí triển khai công nghệ trình tạo số ngẫu nhiên giả là rẻ hơn và nhanh chóng hơn vì nó không đòi hỏi phần cứng và có thể dễ dàng được tích hợp vào mã chương trình. Mặc dù quy trình này không hoàn toàn ngẫu nhiên và được xác định dựa trên một thuật toán, nhưng nó phù hợp hơn cho các trò chơi và các chương trình lập trình.

Các PRNG sử dụng một giá trị ban đầu duy nhất, từ đó sự giả ngẫu nhiên của nó được tạo ra. Trong khi đó, trình tạo số ngẫu nhiên thực luôn tạo ra một số ngẫu nhiên bằng cách có một giá trị ngẫu nhiên chất lượng cao được cung cấp ban đầu bởi các nguồn entropy khác nhau.

Quá trình tạo số ngẫu nhiên giả cũng có nhược điểm của nó. Chúng hoạt động vì chúng ngẫu nhiên đối với con mắt không chuyên nghiệp, chưa qua đào tạo. Tuy nhiên, giả sử bạn biết giá trị ban đầu cho một chuỗi cụ thể của PRNG. Trong trường hợp đó, bạn có thể dự đoán được các số tiếp theo sẽ là gì.

Những người thích chơi game nhanh thường khai thác điểm yếu này - họ gọi đó là sự điều khiển của PRNG. Họ làm cho trò chơi chạy theo cách có thể dự đoán được để họ có thể vượt qua nó càng nhanh càng tốt. May mắn thay, điều này không gây ra các vấn đề quan trọng.

Nhưng có những lúc việc dự đoán số ngẫu nhiên còn quan trọng hơn nhiều. Ví dụ: khi tạo khóa bảo mật.

Nếu kẻ tấn công tìm ra giá trị ban đầu được sử dụng để tạo khóa RSA trong chứng chỉ TLS, họ có thể giải mã được lưu lượng truy cập mạng. Điều này có nghĩa là họ có thể lấy mật khẩu và thông tin cá nhân được gửi qua Internet.

Trong những tình huống này, cần có một cách an toàn hơn để lấy số ngẫu nhiên, tức là một trình tạo số ngẫu nhiên thực.

Trình tạo số của Google

Google có công cụ riêng để tạo số ngẫu nhiên dựa trên JavaScript. Công cụ này có thể hữu ích khi chơi game với bạn bè và gia đình. Bạn có thể tìm thấy trình tạo số này nếu bạn nhập truy vấn tìm kiếm Google "trình tạo số ngẫu nhiên" (random number generator).

Phương pháp Tuyến tính Hồi quy

Một trong những thuật toán phổ biến nhất cho trình tạo số ngẫu nhiên giả là Phương pháp Tuyến tính Hồi quy. Nó được sử dụng trong các trường hợp đơn giản và không yêu cầu cao về sức mạnh mật mã. Derrick Henry Lehmer đã đề xuất phương pháp tuyến tính hồi quy vào năm 1949.

Để triển khai việc tạo số theo phương pháp này, chúng ta cần chọn bốn số:

m > 0, mô đun

0 ≤ a ≤ m, hệ số nhân

0 ≤ c ≤ m, số gia

0 ≤ X₀ ≤ m, số khởi đầu

Chuỗi số ngẫu nhiên được tạo bằng công thức:

Xₙ₊₁ = (aXₙ + c) mod m

Điều đáng chú ý là phương pháp này phụ thuộc vào việc lựa chọn các tham số.

Ví dụ: đối với tập hợp sau:

X₀ = 3, a = 4, c = 5, m = 6

chúng ta nhận được một chuỗi lặp đi lặp lại ngắn

3, 5, 1, 3, 5, 1

trông không có vẻ là ngẫu nhiên.

Nhưng đáng để thay đổi các tham số sang bộ khác:

X₀ = 2, a = 85, c = 507, m = 1356

Và sự phân tán kết quả trở nên khó đoán hơn. Bạn phải chọn các con số cho thuật toán này một cách thật cẩn thận.

2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365, 344, 1271, 62, 353, 680, 1355, 422, 1121, 872, 47, 434, 785, 788, 1043, 1022, 593, 740, 1031, 2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365, 344, 1271, 62, 353, 680, 1355, 422, 1121, 872, 47, 434, 785, 788, 1043, 1022, 593, 740, 1031, 2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365...

Mặc dù phương pháp tuyến tính hồi quy tạo ra một chuỗi số giả ngẫu nhiên có chất lượng thống kê tốt, nhưng nó không có tính bảo mật mạnh mẽ. Các trình tạo dựa trên phương pháp tuyến tính hồi quy có thể dự đoán được, do đó bạn không thể sử dụng chúng trong công nghệ mật mã.

Phương pháp tạo số ngẫu nhiên tuyến tính hồi quy lần đầu tiên bị phá vỡ bởi Jim Reeds vào năm 1977, sau đó là bởi Joan Boyar vào năm 1982. Cô cũng đã thành công trong việc phá vỡ các trình tạo số ngẫu nhiên dựa trên phương pháp tuyến tính hồi quy bậc hai và bậc ba. Do đó, họ đã chứng minh tính kém bảo mật của các trình tạo dựa trên các phương pháp đó. Tuy nhiên, các trình tạo dựa trên phương pháp tuyến tính hồi quy vẫn giữ được tính hữu ích của chúng cho các ứng dụng không phải trong lĩnh vực mật mã, ví dụ như mô phỏng. Chúng hiệu quả và cho thấy hiệu suất thống kê tốt trong hầu hết các thử nghiệm thực nghiệm.

Các trình tạo số ngẫu nhiên dựa trên phần cứng hiện đại

QRBG121

Hiệu ứng ngẫu nhiên trong thiết bị phụ thuộc vào quá trình vật lý lượng tử của phát xạ photon trong bán dẫn và sự phát hiện tiếp theo của từng photon. Trong quá trình này, các photon được phát hiện một cách ngẫu nhiên, độc lập với nhau, và thông tin về thời gian của các photon được phát hiện được sử dụng để tạo ra các bit ngẫu nhiên.

Lava lamps

Văn phòng của CloudFlare tại San Francisco chứa các trình tạo số ngẫu nhiên được gọi là "lava lamps". Một chiếc đèn như vậy là một lọ thủy tinh được đổ đầy dầu trong suốt và parafin không trong suốt. Parafin nặng hơn một chút so với dầu, nhưng khi được làm ấm một chút, nó trở nên nhẹ hơn và nổi lên.

Sự di chuyển của các chất lỏng được theo dõi bởi một số máy ảnh chụp ảnh nhanh. Các bức ảnh được chuyển đổi thành các số, từ đó các khóa mã hóa được tạo ra.

Các văn phòng CloudFlare khác sử dụng các cách khác nhau để thu thập các giá trị ngẫu nhiên. Ở London, một máy ảnh ghi lại các chuyển động của ba con lắc ngẫu nhiên. Ở Singapore, một bộ đếm Geiger được sử dụng để đo sự phân rã phóng xạ của một mảnh uranium nhỏ. Trong trường hợp cuối cùng này, uranium được sử dụng như một "nguồn dữ liệu" vì phản ứng phân rã phóng xạ được đặc trưng bởi tính ngẫu nhiên của mỗi hành động phân rã.

HotBits

HotBits là một trang web cung cấp các số ngẫu nhiên thực được tạo ra bởi một bộ đếm Geiger đăng ký phóng xạ ion hóa cho mọi người. Bạn điền vào một biểu mẫu yêu cầu trên trang web chỉ định số byte ngẫu nhiên và chọn phương pháp ưa thích để nhận dữ liệu. Khi các số ngẫu nhiên được cung cấp cho khách hàng, chúng sẽ được gỡ bỏ ngay lập tức khỏi hệ thống.

Biến thiên lượng tử chân không

Ngược với tên gọi của nó ("vacuus" - trống rỗng), không thể coi chân không là trống rỗng. Theo nguyên lý bất định Heisenberg, các hạt ảo được sinh ra và chết đi liên tục.

Các chuyên gia vật lý Canada đã thiết kế một trình tạo số ngẫu nhiên có cấu trúc đơn giản và nhanh chóng dựa trên các dao động chân không. Trình tạo số ngẫu nhiên này bao gồm một xung laser với tần số bức xạ cao, một chất có chỉ số khúc xạ cao (kim cương) và một bộ cảm biến. Khi đi qua lớp kim cương, mỗi xung trên cảm biến sẽ hiển thị các đặc tính khác nhau tùy thuộc vào các dao động của trường chân không gặp phải trên đường đi của photon.

Trong quang phổ của bức xạ phân tán, các đường phổ xuất hiện. Do tính không thể dự đoán của các dao động chân không, những đường phổ này khác nhau theo cách không thể dự đoán trước được.

Trình tạo số ngẫu nhiên dựa trên ống nano cacbon

Phương pháp này kết hợp tính nén chặt với nhiễu nhiệt.

Các nhà nghiên cứu đã xây dựng một trình tạo số ngẫu nhiên từ một ô nhớ truy cập ngẫu nhiên tĩnh được in bằng mực đặc biệt chứa các ống nano cacbon bán dẫn. Ô nhớ này sử dụng các biến động nhiệt độ để tạo ra các bit ngẫu nhiên.

Trình tạo số ngẫu nhiên từ ống nano cacbon có thể được in trên các nền nhựa dẻo, cho phép tích hợp vào các thiết bị điện tử nhỏ gọn, linh hoạt, cảm biến có thể đeo, nhãn dán dùng một lần và các sản phẩm thời trang thông minh.

Cubes and và Electronic Frontier Foundation (EFF)

Công ty này đã đề xuất một cách đơn giản để tạo mật khẩu an toàn bằng cách sử dụng một trình tạo số ngẫu nhiên vật lý. Nó dựa trên việc sử dụng xúc xắc.

Ví dụ, bạn tung năm xúc xắc một lần và ghi lại các kết quả. Các con xúc xắc được sắp xếp từ trái sang phải như sau: 63131. Tiếp theo, bạn mở một danh sách dài các từ trên trang web của Tổ chức EFF để tìm từ tương ứng với số 63131. Từ đó là "turbofan".

Bạn có thể lặp lại thủ tục này nhiều lần. Ví dụ, năm lần. Bạn có thể kết thúc với một cụm từ gồm năm từ. Chẳng hạn, "turbofan purge unfitting try pruning." Nếu bạn biết cách sử dụng các quy tắc của hệ thống ghi nhớ, bạn có thể ghi nhớ những cụm từ như thế này.

Trình tạo số ngẫu nhiên lượng tử từ điện thoại thông minh Nokia

Năm 2014, Đại học Geneva đã tạo ra một thiết bị QRNG sử dụng camera của điện thoại thông minh Nokia N9.

Camera của chiếc điện thoại thông minh này đếm số lượng photon đến từng điểm ảnh. Nguồn sáng là một đèn LED tiêu chuẩn. Mỗi điểm ảnh trong camera 8 MP phát hiện khoảng 400 photon trong một khoảng thời gian ngắn. Tổng số photon tại tất cả các điểm ảnh sau đó được chuyển đổi thành một chuỗi số ngẫu nhiên.