# Linux 核心專題: 亂數產生器研究
> 執行人: ShamrockLee
> [期末專題講解影片](https://youtu.be/dZ66QkoA5YI)
> [簡報](https://docs.google.com/presentation/d/18_HDogktJwnkModepk0hZDRlmVGEcARfH4GRRdwAujo/edit?usp=sharing)
:::info
勘誤:
* 範圍: 簡報、期末專題解說影片的「 PRNG 介紹」
```diff
-虛擬亂數產生器是一種能產生性質類似亂數的數列的遞迴函數
+虛擬亂數產生器是一種能產生性質類似亂數的數列的演算法
```
解釋:
* 如果直接以遞迴函數作為 PRNG 來產生數列，那只要知道比該遞迴函數的輸入還要多的項，就能預測往後的數值，密碼學上不安全。
* PRNG 內部的狀態 (state) 變化能夠由遞迴函數描述，而輸出值是由內部狀態透過令一個函數決定。
$$
\begin{cases} state_{i+1} = f(state_i) \\ output_i = g(state_i) \end{cases}
$$
* $state_0$ 由亂數種子 (seed) 決定。
:::
:::success
:question: 提問清單
* Tausworthe generator 一度使用於 Linux 核心 (`lib/random32.c`) 作為 PRNG，後續 Linux 改版時，基於什麼考量變更 PRNG 呢？
> 根據 Willy Tarreau 所貢獻的 commit [`c51f8f88d705`](https://github.com/torvalds/linux/commit/c51f8f88d705e06bd696d7510aff22b33eb8e638) 當中的 commit message ，利用 Tausworthe generator (LFSR) 實作的 PRNG 能讓攻擊者從一段已知的數列推測其他部份的值，導致運用於 SSL 等需要 CSPRNG 的場合時不安全。
> 該 commit 解決的方式，是將 prandom （ Linux PRNG ）改以基於 SipHash 的演算法實作。[name=ShamrockLee]
:::
## 任務簡述
[第 3 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz3)第三題介紹到 Linear feedback shift register (LFSR)，這也是 Linux 核心亂數產生器 (RNG) 的基礎之一。本任務探討 [Linux RNG](https://www.amossys.fr/fr/ressources/blog-technique/linux-csprng-architecture/) 的原理、實作機制，以及應用場景。
相關素材:
* [初探 Linux kernel 亂數產生器 – random generator](https://szlin.me/2016/10/05/%E5%88%9D%E6%8E%A2-linux-kernel-%E4%BA%82%E6%95%B8%E7%94%A2%E7%94%9F%E5%99%A8-random-generator/)
* [The Raspberry Pi’s Hardware Random Number Generator](http://scruss.com/blog/2013/06/07/well-that-was-unexpected-the-raspberry-pis-hardware-random-number-generator/)
## 重做[第 3 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz3)第三題，並彙整其他學員的成果
### 線性回饋移位暫存器原理與 Linux 核心當中的實作與應用
線性回饋移位暫存器，正如其名，是指遞迴關係能以線性函數（具疊加性、一次齊次性的函數）表達、主要以一串位移暫存器組成的電子電路，或上述電路所代表的演算法。
Fibonacci LFSR （又稱 Maximum-length LFSR ）由一列相接的移位暫存器組成，邏輯電平隨時脈朝右方傳遞，並透過對事先選定的幾個暫存器值做抑或運算決定最左方的數值。其值構成的序列稱為 maximum-length sequence （ MLS 、 M-sequence ）。
以軟體實作相應的 PRNG 時，能定義 `lfsr` 函式，其輸入值為指向無號整數的指標，該整數的各個位元即對應到電字電路各個移位暫存器的邏輯電平。以最高位對應上述最左端的暫存器，並以位元右移模擬移位暫存器的行為。
（圖片取自 Wikipedia，以 CC0 授權。原圖為 SVG 檔。之後有時間的話，打算以 Graphviz 重製。）
上圖展示一個 Fibonacci 線性回饋移位暫存器，以第 11, 13, 14, 16 位元的值做 XOR 運算後指派到第 1 位元，而第 k 位元的值指派到第 k + 1 位元（$k \ge 1$）。
（目前未能理解 $x^{16} + x^{14} + x^{13} + x^{11} + 1$ 與上述運算的關聯。）
> 多項式的乘方跟 64-bit 整數第幾位數正好相反。第 0 位是 $x^{64}$ ，第 1 位是 $x^{63}$ 故式子中 `(*up) >> 3` 是代表 $x^{64-3}$ 為 $x^{61}$ 以此類推。
> `lib/random32.c` 內有說明。 PRNG 用 LFSR 去產生。
以下測驗 `3` 中的程式碼，便是利用 `((*up) >> (64 - k)) & 1` 取得 $2^{64 - k}$ 位的值以做 XOR 運算，接著利用 `((*up) >> 1) | (new_bit << 63)` 得到將運算結果指派到 $2^{63}$ 位，其他位右移一位的值，並指派回 `*up` 。
```c
/* Implementation of LFSR (linear feedback shift register)
* on uint64_t using irreducible polynomial x^64 + x^61 + x^34 + x^9 + 1
* (On 32 bit we could use x^32 + x^22 + x^2 + x^1 + 1)
*/
static void lfsr(uint64_t *up)
{
uint64_t new_bit =
((*up) ^ ((*up) >> 3) ^ ((*up) >> 30) ^ ((*up) >> 55)) & 1u;
/* don't have to map '+1' in polynomial */
*up = ((*up) >> 1) | (new_bit << 63);
/* shift *up by 1 to RIGHT and insert new_bit at "empty" position */
}
```
以線性回饋移位暫存器的原理實作的 PRNG 又稱為 Tausworthe 產生器（ Tausworthe generator ），或許和 Robert C. Tausworthe 於 1965 年在期刊 *Mathematics of Computation* 上發表的論文 *Random Numbers Generated by Linear Recurrence Modulo Two* 有關。這個別稱在 Linux 核心專案中也有出現。
利用
```bash
git log --grep='\(LFSR\|[Ll]inear [Ff]eedback [Ss]hift [Rr]egister\|[Tt]ausworthe\)'
```
能列出 Linux 核心原始碼中，所有 commit message 提到 LFSR 的 commits 。截至 `v6.4-rc6` （ commit `858fd168a95c` ），在 `master` 分支上共有[ 23 個 commits ](https://gist.github.com/ShamrockLee/14bdd8b71c75aedd4a3a508fd642da4b#file-git_log_lk_grep_lfsr_till_6-4-rc6-log)含有此關鍵字。再以關鍵字搜尋程式碼，能幫助我們了解 LFSR 實作於 Liunx 核心的過程。
Linux 核心專案於 `2.6.2-rc2` 開始採用 Git 版本控制系統，對應的 commit `1474855d0878` 也是專案中最早的 commit 。而在這之前， Fibonacci LFSR 實作就已出現在 `drivers/net/ewrk3.c` 的函數 `get_hw_addr` 中，作為 EtherWORKS 乙太網路卡 driver 的一部分。
另外在 `net/core/utils.c` 當中， `net-random` 函數時做了 taus88 演算法，是一種 maximally equidistributed combined Tausworthe generator ，是由 Pierre L'Ecuyer 所設計的演算法，週期大約為 $2^{88}$ 。
當時雖然已有 `include/linux/random.h` ，但直到 commit `aaa248f6c9c8` （發布於 `2.6.19-rc3` ）， `net_random` 才獨立成 `lib/random32.c` 當中的 `random32` ，並宣告於 `include/linux/random.h` 中。
`random32` 經過一系列改進，包含 reseeding 與升級演算法到 taus113 （ commit `a98814cef879` ）。
Fibonacci LFSR 或 Galoise LFSR 仍被當做一種簡單的 PRNG ，在 driver 、 profiler 等處實作。
### 整數 $\log_2$ 在 Linux 核心當中的實作
整數 $\log_2$ 函數在 Linux 核心當中以 `ilog2` 命名。
Linux 核心專案中， `include/linux/ilog2.h` 提供 `__ilog2_u32` 、 `__ilog2_u64` 函數，及 `log2` 、 `const_log2` 巨集。前二者事實上就只是回傳 `fls(n) - 1` （或 `fls64(n) - 1`）。
巨集 `log2(n)` 針對輸入型別選擇要呼叫的函數。巨集 `const_log2(n)` 主要在提供類似 C++ `constexpr` 在編譯時求值的支援。實作方式是藉由 GCC extension `__builtin_constant_p(n)` 偵測輸入值是否在編譯階段已知；若是則傳入一連串條件運算子，從左至右一一確認每個位元是否為零；若否則調用 `log2(n)` 巨集。
Linux 核心針對不同的處理器指令提供不同的 `fls` 實作，針對有支援 GCC extension `__builtin_clz(n)` 的環境，直接使用 `32 - __builtin_clz(n)` 或 `64 - __buitlin_clz(n)` 。針對其他指令集，則使用 inline assembly 實作。另外有 `include/asm-generic/bitops/fls.h` ，使用以下 C 語言實作，透過二分搜尋來找到變數左方位元皆為零的區域大小。
```c
/**
* fls - find last (most-significant) bit set
* @x: the word to search
*
* This is defined the same way as ffs.
* Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
*/
static __always_inline int fls(unsigned int x)
{
int r = 32;
if (!x)
return 0;
if (!(x & 0xffff0000u)) {
x <<= 16;
r -= 16;
}
if (!(x & 0xff000000u)) {
x <<= 8;
r -= 8;
}
if (!(x & 0xf0000000u)) {
x <<= 4;
r -= 4;
}
if (!(x & 0xc0000000u)) {
x <<= 2;
r -= 2;
}
if (!(x & 0x80000000u)) {
x <<= 1;
r -= 1;
}
return r;
}
```
#### 無分支、不使用 extension 的 `fls` 實作嘗試
Linux 核心專案未提供，不使用編譯器 extension 且平台無關的 `fls` 實作。我嘗試改寫上述平台無關的實作，以
```c
x = x << (!(x & 0xffff0000u)) << 4
```
或
```c
static int x1 = x << (!(x & 0xffff0000u)) << 4
```
取代
```c
if (!(x & 0xffff0000u)) {
x <<= 16;
}
```
試圖避開（顯式）分支，但以 `gcc -O2 -std=c99 -S` 編譯後，卻發現編譯產生的組合語言，分支和原本的實作一樣多。
我另外在 [quiz2](https://hackmd.io/@ShamrockLee/sysprog2023q1-quiz2#%E5%BB%B6%E4%BC%B8%E5%95%8F%E9%A1%8C%EF%BC%9A%E7%84%A1%E5%88%86%E6%94%AF%E7%9A%84-floor_log2_u32-%E8%88%87-ceil_log2_u32-%E5%AF%A6%E4%BD%9C%EF%BC%88%E5%90%AB%E4%BE%8B%E5%A4%96%E8%99%95%E7%90%86%EF%BC%89) 中實作了，但指令數量從 Linux 核心實作的 24 個，上升到 40 個。尚未測試過效能，但以指令數量的成長來看，可能會造成效能損失。即使如此，在有 constant time 要求或其他需要避免分支的場合，還是有潛在用途。
:::warning
對照〈[回顧 bitops 並改進](https://hackmd.io/@sysprog/ByS9w_lHh)〉
:notes: jserv
:::
上述無分支的 `fls` 實作，其原理為
1. 將最高非零位元以外的位元設為零
2. 以 bit masks 做二分搜尋，算出非零位元的索引
另外，將第一部的「最高非零位元」改為「最低非零位元」，就能實作 `fls` 。
〈[回顧 bitops 並改進](https://hackmd.io/@sysprog/ByS9w_lHh)〉制定 `gen_ffs` 與 `gen_fls` 巨集界面，並透過 `_Pragma("GCC unroll 6")` 運算子在巨集內展開迴圈（ unroll loop ），不增加 branch 就能相容不同整數型態寬度的輸入值。（選用 6 是因為 $2^6 = 64$ 。〈回顧 bitops 並改進〉文中也提到，若未來要適用於 128-bit 的輸入值，能上調為 7 。）
上述技巧僅適用於 GCC 編譯器。考慮到 Clang 也支援 loop unrolling ，能定義巨集
```c
#ifdef __clang__
#define unroll_ffls_branchless _Pragma("clang loop unroll_count(6)")
#elif __GNUC__ >= 8
#define unroll_ffls_branchless _Pragma("GCC unroll 6")
#else
#define unroll_ffls_branchless
#endif
```
並將 `unroll_ffls_branchless` 加在巨集定義的迴圈之前，這樣無論以 GCC 與 Clang 編譯，迴圈都能正確展開。類似的作法出現在 Linux 核心 [`i40e_xsk` driver](https://github.com/torvalds/linux/blob/v6.4-rc7/drivers/net/ethernet/intel/i40e/i40e_xsk.h) 、 [`ice_xsk` driver](https://github.com/torvalds/linux/blob/v6.4-rc7/drivers/net/ethernet/intel/ice/ice_xsk.h) 當中。
利用前述迴圈展開技巧，能將 `fls` 、 `ffs` 實作所需的步驟拆解為三個巨集
* `__preserve_msb_branchless` 「保留非零最高位元」的無分支實作
* `__preserve_lsb_branchless` 「保留非零最低位元」的無分支實作
* `__locate_bit_branchless` 「定位非零位元索引」的無分支實作
對照 `gen_fls` 與 `gen_ffs` 界面，能分別實作 `gen_fls_branchless` 與 `gen_ffs_branchless` 巨集。其界面相容於，能如同 `gen_f{f,l}s` 一般套用到相關 `clz` 、 `ctz` 等函數實作。
〈回顧 bitops 並改進〉對 Linux 核心當中現有實作分析後，發現「索引從 1 開始」與「索引從 0 零開始」兩種風格，並以「回傳 0 」處理「索引從 0 開始」風格的例外（輸入值為 0 的情形）。這樣一來，「從 0 開始」在輸入值為 0 、為 1 時會對應到同樣的值，而有資訊損失。因此我針對「從 1 開始」實作運算步驟，並在 `gen_fls_branchless` 與 `gen_ffs_branchless` 內處理「從 0 開始」的例外。
「從 1 開始」特別考慮輸入值為零的情形，拆解的三個巨集都要具備處理此種例外的步驟。上述例外處理主要透過 `!!` 將數值對應到 0 或 1 （編譯成組合語言後會是 `TEST` 指令），或使用 bit mask 。
以下是實作的程式碼：
`__preserve_msb_branchless`:
```c
/* Preserve the most significant bit set of X and unset others.
* Return zero when non set.
*/
#define __preserve_msb_branchless(X, type) \
do { \
type __is_nonzero = !!(X); \
(X) = (X) >> 1; \
unroll_ffls_branchless for (size_t _i_exp = 1; \
_i_exp < (sizeof(X) << 3); _i_exp <<= 1) \
{ \
(X) |= (X) >> _i_exp; \
} \
(X) += __is_nonzero; \
} while (0)
```
不考慮整數類型寬度與 0 輸入值處理的話，這段程式的行為就是
1. 將非零最高位以下的位元都設為 1 ，本身設為 0
```c
x = x >> 1;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
// ...
```
2. 加一後就留下目標位元
```c
x += 1;
```
例外處理的部份，則是考慮當輸入值為零時，步驟 1 做完之後 x 會是 0 ，和 輸入值是 1 的情形無法分別，故須在進行步驟 1 之前先儲存 `!!x` ，以決定步驟 2 是否要加一。
`__preserve_lsb_branchless`:
```c
/* Preserve the least significant bit set of X and unset others.
* Return zero when non set.
*/
#define __preserve_lsb_branchless(X, type) \
do { \
unroll_ffls_branchless for (size_t _i_exp = 1; \
_i_exp < (sizeof(X) << 3); _i_exp <<= 1) \
{ \
(X) |= (X) << _i_exp; \
} \
type _x_upperfilled = (X); \
(X) = ~(X) + (!!_x_upperfilled); \
(X) &= _x_upperfilled; \
} while (0)
```
仿照 `__preserve_msb_branchless` 的思路，這次把最低非零位元右方的位元都設為 1 ，這樣為 0 的位元剛好就都在目標位元左方。
這時套用 bitwise NOT 翻轉所有位元，就呈現類似 `__preserve_msb_branchless` 第一部進行完之後的情形，接著只要加 1 就好。
`__locate_bit_branchless`:
```c
/* Take in an unsigned integer with at most one bit set, and then
* output the 1-based digit of that bit. Return 0 if no bits are set.
*
* Bits higher than (2**64 - 1) will be truncated.
*
* Determine the result bit value through binary search with the following
* masks:
*
* 0b01010101'01010101'01010101'01010101'01010101'01010101'01010101'01010101u
* 0b01100110'01100110'01100110'01100110'01100110'01100110'01100110'01100110u
* 0b01111000'01111000'01111000'01111000'01111000'01111000'01111000'01111000u
* 0b01111111'10000000'01111111'10000000'01111111'10000000'01111111'10000000u
* 0b01111111'11111111'10000000'00000000'01111111'11111111'10000000'00000000u
* 0b01111111'11111111'11111111'11111111'10000000'00000000'00000000'00000000u
* 0b10000000'00000000'00000000'00000000'00000000'00000000'00000000'00000000u
*/
#define __locate_bit_branchless(x_pow2, in_type, out_type) \
((out_type) (((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \
0x5555555555555555u)))) \
<< 0) + \
((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \
0x6666666666666666u)))) \
<< 1) + \
((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \
0x7878787878787878u)))) \
<< 2) + \
((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \
0x7f807f807f807f80u)))) \
<< 3) + \
((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \
0x7fff80007fff8000u)))) \
<< 4) + \
((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \
0x7fffffff80000000u)))) \
<< 5) + \
((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \
0x8000000000000000u)))) \
<< 6)))
```
`gen_fls_branchless`:
```c
/* Branchless version of gen_fls */
#define gen_fls_branchless(in_type, out_type, start_from, fn_name) \
static __always_inline out_type fn_name(in_type x) \
{ \
__preserve_msb_branchless(x, in_type); \
out_type _ret = __locate_bit_branchless(x, in_type, out_type); \
return _ret - (out_type) ((!(start_from)) & (!(_ret))); \
}
}
```
`gen_ffs_branchless`:
```c
/* Branchless version of gen_ffs */
#define gen_ffs_branchless(in_type, out_type, start_from, fn_name) \
static __always_inline out_type fn_name(in_type x) \
{ \
__preserve_lsb_branchless(x, in_type); \
out_type _ret = __locate_bit_branchless(x, in_type, out_type); \
return _ret - (out_type) ((!(start_from)) & (!(_ret))); \
}
```
2023-07-11 更新：
根據 Linux 核心官方文件 [Minimal requirements to compile the Kernel](https://www.kernel.org/doc/html/latest/process/changes.html) ， Linux 核心專案支援以 5.1 版或之後的 GCC 編譯。這代表 Linux 核心內的程式，以受到支援的編譯器版本編譯，產生的目的碼都必須有正確的行為。
`gen_f{f,l}s_bratchless` 的價值在於產生沒有分支的 `ffs` 、 `fls` 實作，但前述實作用到的 `_Pragma("GCC unroll 6")` 功能，在 GCC 8才加入。原本設想以 conditional directives 定義巨集 `unroll_ffls_branchless` 以避免在未支援此 directive 的編譯器上編譯時產生的警告訊息或錯誤，但這也意謂在上述較低版本的編譯器上，迴圈可能根本沒展開，而導致出現分支。這對於 `gen_f{f,l}s` 可能只是效能下降，但對於 `gen_f{f,l}s_branchless` 來說是行為不正確，必須改善。
以下是改善後的實作：
```c
/* Preserve the most significant bit set of X and unset others.
* Return zero when non set.
*/
#define __preserve_msb_branchless(X, type) \
do { \
type _is_nonzero = !!(X); \
(X) >>= 1; \
(X) |= (X) >> 1; \
(X) |= (X) >> 2; \
(X) |= (X) >> 4; \
(X) |= (X) >> ((sizeof(type) > 1) << 3); \
(X) |= (X) >> ((sizeof(type) > 2) << 4); \
(X) |= (X) >> ((sizeof(type) > 4) << 5); \
(X) += _is_nonzero; \
} while (0)
```
```c
/* Preserve the least significant bit set of X and unset others.
* Return zero when non set.
*/
#define __preserve_lsb_branchless(X, type) \
do { \
(X) |= (X) << 1; \
(X) |= (X) << 2; \
(X) |= (X) << 4; \
(X) |= (X) << ((sizeof(type) > 1) << 3); \
(X) |= (X) << ((sizeof(type) > 2) << 4); \
(X) |= (X) << ((sizeof(type) > 4) << 5); \
type _x_upperfilled = (X); \
(X) = ~(X) + (!!_x_upperfilled); \
(X) &= _x_upperfilled; \
} while (0)
```
為了不依賴迴圈展開就能相容不同整數類型寬度，我們能手動展開至符合 64 位元整數類型的執行次數，再將每次執行欲移動的位元數與類型寬度比較，再用這項布林值決定是否歸零移動的位元數。由於比較的部份在編譯時期已知，能期待編譯器將之最佳化而不產生分支。
### `lab0-c` 中 [`log2_lshift16.h`](https://github.com/sysprog21/lab0-c/blob/master/log2_lshift16.h) 的原理與效能改善
#### 原理
`lab0-c` 當中的 `log2_lshift16.h` 儲存有預先計算好的 $\log_2$ 值對應關係。其結構是由條件控制所建立的 search tree 。其輸入值比數學上的值向左偏移 16 位元，輸出值比數學上的值向左偏移 3 位元，以整數表示定點數（ fixed-point number ）。
由輸出值皆為負數看來，輸入值對應到定點數 $(0, 1]$ 的範圍。
#### 效能改善
藉由 $\log$ 的數學特性，能將輸入值限縮在更小的範圍，強制其小數點後第一位（整數的 $2^{15}$ 位）為 1 ，否則先左移再查詢。這樣就能降低樹高，減少查詢時間。搭配指令集對 `__builtin_clz64` 的支援，預期能達到更高的效能，並減少檔案大小。
<!--
### TODO
1. 解釋 [Linear feedback shift register](https://en.wikipedia.org/wiki/Linear-feedback_shift_register) (LFSR) 的運作原理，搭配在 [Linux 核心原始程式碼](https://github.com/torvalds/linux)中，用 `git log` 和 `grep` 找出 LFSR 的應用案例
2. 解釋給定程式碼運作的原理
3. 在 Linux 核心原始程式碼中找到 $\log_2(x)$ 的實作 (整數)，要涵蓋不同的整數型態寬度，以及是否能運用微處理器提供的指令來加速。也從 Linux 核心找出整數 $\log_2(x)$ 的應用案例並解說。
4. `lab0-c` 提供類似的實作 [log2_lshift16.h](https://github.com/sysprog21/lab0-c/blob/master/log2_lshift16.h)，解釋其原理並嘗試改進其效能
-->
## Linux RNG 架構與文獻探討
### 隨機事件收集
* Linux 核心從多重來源蒐集隨機事件並估計其「熵」
* 硬體隨機數產生器（ HWRNG ）
* 鍵盤、滑鼠輸入（計算週期數）
* 中斷事件（計算週期數）
* Linus Jitter Dance
### 隨機事件混合
* LFSR
### TODO: 研讀 Linux RNG 相關文獻並記錄自己的認知和疑惑
至少要涵蓋以下:
* [random.c - Inside the Linux Kernel's RNG](https://www.zx2c4.com/projects/linux-rng-5.17-5.18/inside-linux-kernel-rng-presentation-sept-13-2022.pdf) / [演講錄影](https://t.co/kewXWerNmI)
* [Linux RNG architecture](https://www.amossys.fr/fr/ressources/blog-technique/linux-csprng-architecture/)
* [Documentation and Analysis of the Linux Random Number Generator](https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/Studies/LinuxRNG/LinuxRNG_EN.pdf)
儘量紀錄理解狀況、彙整文件，並紀錄問題。藉由上述認知回覆下方問題:
* Linux RNG 如何達到 [CSPRNG](https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator) 要求？以真實應用場景來舉例說明
* LFSR 在 Linux RNG 的實作有何影響？以 Linux 核心原始程式碼搭配解說
* Linux 的 `/dev/random` 和 `/dev/urandom` 對應到內部哪些實作？如何運用硬體 RNG 或者相關機制 (例如 Raspberry Linux 的 [/dev/hwrng](https://www.arch13.com/raspberry-pi-random-number-generation/)) 呢？如何確保其「夠亂」呢？
## TODO: 撰寫 Linux 核心模擬測試 RNG 框架並提供可能的 `hwrng` 實作
對 Linux RNG 有足夠認知後，撰寫 Linux 核心模組來測試，並搭配 Linux 核心原始程式碼和〈[Documentation and Analysis of the Linux Random Number Generator](https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/Studies/LinuxRNG/LinuxRNG_EN.pdf)〉，探討如何運用硬體特性作為有效的 entropy source，從而實作 hwrng。
Sign in with Wallet
Connect another wallet