Rust: 關於隨機數

在這篇文章中，將 “隨機數” 主題分解爲不同成分，並將它們映射到 Rust 生態系統中。

真正的隨機性

出於加密目的 (例如，生成用於公鑰加密的密鑰對)，你希望使用從物理信號(硬件隨機數生成器、鍵盤輸入等) 派生的真正隨機數。這裏 API 的形狀是：

fn fill_buffer_with_random_data(buf: &mut [u8])

由於這基本上需要與一些物理設備通信，因此該任務由操作系統處理。不同的操作系統提供不同的 api，這超出了本文的範圍 (以及我自己的知識範圍)。

這是 Rust 標準庫的一個主要缺陷，它沒有公開該功能。獲取加密安全的隨機數據與獲取當前時間或讀取標準輸入屬於同一類操作系統服務。可以說，它甚至更重要，因爲使用此功能的大多數應用程序都對安全性至關重要。

但是，Rust 中的 getrandom crate 爲該功能提供了一個跨平臺包裝器。

僞隨機數發生器

對於各種非加密隨機算法，你希望從一個固定的、確定的種子開始，並生成一組在統計上與隨機數難以區分的數字流。這裏 API 的形狀是：

fn random_u32(state: &mut f64) -> u32

有很多不同的算法可以做到。fastrand crate 實現了一些足夠接近隨機性的狀態。

或者，一個足夠好的 PRNG(僞隨機數生成器) 可以在 9 行代碼中實現：

pub fn random_numbers(seed: u32) -> impl Iterator<Item = u32> {
  let mut random = seed;
  std::iter::repeat_with(move || {
    random ^= random << 13;
    random ^= random >> 17;
    random ^= random << 5;
    random
  })
}

這段代碼是從 Rust 的標準庫 (源代碼) 中提取的。

播種 PRNG 的最佳方法通常是使用固定常數。如果你確實需要在種子中添加一些隨機性，你可以使用以下方法：

pub fn random_seed() -> u64 {
  std::hash::Hasher::finish(&std::hash::BuildHasher::build_hasher(
    &std::collections::hash_map::RandomState::new(),
  ))
}

在 Rust 中，Hashmap 包括一些隨機化，以避免由於碰撞而產生的可利用的漏洞行爲。上面的代碼片段提取了這種隨機性。

非均勻分佈隨機數

好的 PRNG 會給你一個 u32 數字序列，其中每個數字都可能和其他數字一樣。你可以使用 random_u32() % 10 將其轉換爲從 0 到 10 的數字。這對於大多數目的來說已經足夠好了，但卻無法通過嚴格的統計測試。因爲 232 不能被 10 整除，0 出現的頻率會比 9 略高。有一種算法可以正確地做到這一點 (如果 random_u32() 非常大，並且在 232 除以 10 後餘數落入範圍，則將其丟棄並重試)。

有時你想使用 random_u32() 來生成其他類型的隨機事物，比如 3D 球體上的隨機點，或者隨機排列。

球面：在單位立方體中生成隨機點；如果它也在單位球中，則將其投射到表面上，否則將其扔掉並重試。

排列：選擇一個隨機元素爲第一，然後從其餘元素中選擇一個隨機元素爲第二，以此類推的簡單算法。

有一些庫提供了這樣的算法集合。例如，fastrand 包括最常見的，如生成範圍內的數字，生成浮點數或變換切片。

rand 包括了更深奧的情況，如在球面或正態分佈上的點。

全局隨機數

在任何情況下，這個功能都可以通過在 thread local 中存儲 PRNG 的狀態來實現：

use std::cell::Cell;
pub fn thread_local_random_u32() -> u32 {
  thread_local! {
      static STATE: Cell<u64> = Cell::new(random_seed())
  }
  STATE.with(|cell| {
    let mut state = cell.get();
    let result = random_u32(&mut state);
    cell.set(state);
    result
  })
}

rand 允許你混合和匹配不同的 prng 和算法。

隨機性的種類

儘管這兩個用例在名稱中都有 “隨機性”，但它們是互不關聯的，底層算法和 api 沒有任何共同之處。它們在物理上是不同的：一個是系統調用，另一個是將整數映射到隨機數的純函數。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/b-iVxfHdt-cfJiwPUkyugQ

猜你喜歡