Random Number Generation and CSPRNG Quality (TAOCP Vol. 2) — Statistical Testing and Seed Management, Upstream of Nonce-Reuse Incidents TODO
Concept
Random number generators split into PRNGs, which deterministically generate a sequence from a seed, and CSPRNGs, which are designed to guarantee unpredictability. Statistical test suites check whether output shows abnormal structure in uniformity or independence, but passing those tests doesn't imply cryptographic security. Generators that look statistically fine, like linear congruential generators or the Mersenne Twister, can have their internal state reconstructed from just a small amount of observed output, letting an attacker predict every value from then on. A CSPRNG must ensure that knowing previous outputs gives no meaningful edge in predicting the next bit, that exposing the state can't roll back to recover past outputs, and that seeding comes from an OS entropy source. Failures usually come from seed and state management, not the algorithm — classic cases are seeding right after boot when entropy is scarce, and state duplication from fork or VM snapshot cloning.
Signature nonces, session tokens, and key generation all depend on this, and a single reproducible random value leads straight to a leaked private key. ECDSA in particular: reuse the same nonce across two different signatures and the private key can be recovered algebraically.
Code & Formula
# 난수 생성과 CSPRNG 품질 — 통계적 검정(빈도·런) 통과가 예측불가능성을 뜻하지 않음을 보인다.
# 선형합동생성기(LCG)는 검정을 통과해도 상태 복원이 쉽고, secrets 는 OS 엔트로피 기반이라 다르다.
import secrets
class WeakLCG:
"""교육용 취약 PRNG — 통계 검정은 통과하지만 관측값으로 상태를 복원해 다음 값을 예측 가능."""
def __init__(self, seed):
self.state = seed
self.a, self.c, self.m = 1103515245, 12345, 2**31
def next(self):
self.state = (self.a * self.state + self.c) % self.m
return self.state
def monobit_test(bits):
"""간단 빈도 검정: 0/1 비율이 균형에 가까운지만 본다 (진짜 무작위성 증명은 아님)."""
ones = sum(bits)
return abs(ones - len(bits) / 2) < len(bits) * 0.05
lcg = WeakLCG(seed=42)
lcg_bits = [lcg.next() & 1 for _ in range(1000)]
print("LCG passes naive monobit test:", monobit_test(lcg_bits))
# 취약점: 연속된 출력 두 개만 관측하면 다음 값을 그대로 예측할 수 있다 (선형 재귀이므로)
attacker_lcg = WeakLCG(seed=1)
observed = [attacker_lcg.next() for _ in range(2)]
recovered = WeakLCG(seed=42)
recovered.state = lcg.state # 공격자가 내부 상태를 역산했다고 가정
predicted_next = recovered.next()
actual_next = lcg.next()
print("LCG next value predictable once state is known:", predicted_next == actual_next)
# CSPRNG: secrets 모듈은 OS 엔트로피(os.urandom)를 쓰고, 이전 출력으로 다음을 예측할 수 없다
csprng_bits = [secrets.randbits(1) for _ in range(1000)]
print("CSPRNG passes naive monobit test too:", monobit_test(csprng_bits))
print("=> passing a statistical test proves nothing about predictability;")
print(" seed source and state-recovery resistance are what make a generator crypto-safe")
docs/code/algorithms/algorithms-84.py
Exercise
Compare seed/output reproducibility between a language's general-purpose random function and its cryptographic random function (e.g., Node.js's Math.random vs. crypto.randomBytes), and check whether two children of a forked process draw the same values.
Practical Connection
Every signing path Verex touches — order signatures, oracle submissions, relayer keys — has its security riding on the quality of the nonce and key-generation randomness, so the rule is to use a vetted library with a deterministic nonce spec rather than rolling your own.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.