Random Number Generation and CSPRNG Quality (TAOCP Vol. 2) — Statistical Testing and Seed Management, Upstream of Nonce-Reuse Incidents TODO

Algorithms · Day 84 / 100 · F. Cryptography & ZK (Day 82-96)

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.

Where it lands in Jayverse

• Wallet: draw key/session-key derivation from an OS CSPRNG, never a userspace equivalent. Add the exercise's fork/VM-clone reproducibility test to Wallet's key-generation suite to catch state duplication before it ships.
• Bridge relayer: verify the relayer's signing nonce uses a deterministic-nonce spec (RFC 6979), not a custom RNG. A long-lived relayer key is exactly the kind of signer this piece warns leaks a private key through nonce reuse.
• Devnet: keep Anvil's deterministic test-mode RNG walled off from anything trusting Sepolia or mainnet. Enforce that boundary in config so a devnet-seeded value never becomes the entropy source for a real signer.

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/.

한국어

난수 생성과 CSPRNG 품질 (TAOCP 2권) TODO

Algorithms · Day 84 / 100 · F. 암호학·ZK (Day 82–96)

통계적 검정·시드 관리, nonce 재사용 사고의 상류

개념

난수 생성기는 시드에서 결정적으로 수열을 만드는 PRNG와, 예측 불가능성을 보장하도록 설계된 CSPRNG로 나뉜다. 통계적 검정 묶음은 출력이 균등성·독립성 면에서 이상한 구조를 보이는지 검사하지만, 검정을 통과했다는 사실이 암호학적 안전성을 뜻하지는 않는다. 선형 합동법이나 메르센 트위스터처럼 통계적으로 무난한 생성기도 출력을 조금만 관측하면 내부 상태를 복원해 이후 값을 전부 예측할 수 있다. CSPRNG는 이전 출력을 알아도 다음 비트를 유의미하게 예측할 수 없어야 하고, 상태가 노출돼도 과거 출력을 되돌릴 수 없어야 하며, 시드는 OS 엔트로피 소스에서 받아야 한다. 실패는 대개 알고리즘이 아니라 시드·상태 관리에서 나는데, 엔트로피가 부족한 부팅 직후 시딩, fork나 VM 스냅샷 복제로 인한 상태 중복이 대표적이다.

서명 nonce, 세션 토큰, 키 생성이 모두 여기에 의존하며, 재현되는 난수 하나가 곧바로 개인키 노출로 이어진다. 특히 ECDSA는 서로 다른 두 서명에서 같은 nonce를 쓰면 대수적으로 개인키가 복원된다.

코드 · 수식

# 난수 생성과 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

연습

언어 표준 라이브러리의 일반 난수 함수와 암호용 난수 함수(예: Node.js의 Math.random과 crypto.randomBytes)로 각각 시드/출력 재현성을 실험하고, 프로세스 fork 후 두 자식이 같은 값을 뽑는지 확인하라.

실무 · Verex 연결

Verex가 다루는 서명 경로(주문 서명, 오라클 제출, 릴레이어 키)는 모두 nonce·키 생성 난수의 품질에 안전성이 걸려 있으므로, 결정적 nonce 규격을 쓰는 검증된 라이브러리를 쓰고 직접 구현하지 않는 것이 원칙이다.

Jayverse에서의 위치

• Wallet: 키/세션 키 파생은 유저스페이스 대체물이 아니라 반드시 OS의 CSPRNG에서 뽑는다. 익서사이즈의 fork/VM 클론 재현성 테스트를 Wallet의 키 생성 테스트 스위트에 추가해 상태 중복을 출시 전에 잡아낸다.
• Bridge 릴레이어: 릴레이어의 서명 nonce가 커스텀 RNG가 아니라 결정론적 nonce 스펙(RFC 6979)을 쓰는지 확인한다. 오래 사는 릴레이어 키는 이 글이 경고하는, nonce 재사용으로 개인키가 새는 바로 그 유형의 서명자다.
• Devnet: Anvil의 결정론적 테스트 모드 RNG를 Sepolia나 메인넷을 신뢰하는 어떤 것과도 분리해 둔다. devnet에서 시드된 값이 실제 서명자의 엔트로피 소스가 되지 않도록 설정으로 그 경계를 강제한다.

공부한 날 원본 커리큘럼(docs/knowledge/dev-100-curriculum.md)의 이 줄에 노트 링크와 ✅ 를 붙이면, 이 자리는 노트 본문으로 바로 이어집니다. 노트 없이 이 페이지에 바로 적어도 됩니다 — 다만 다시 생성하면 덮어쓰이므로, 남길 글은 docs/algorithms/ 의 마크다운으로 쓰는 편이 안전합니다.