CSPRNG Là Gì — Lịch Sử, Thuật Toán & Ứng Dụng Sinh Số Ngẫu Nhiên An Toàn

System 04/04/2026 25 lượt xem

CSPRNG — Cryptographically Secure PRNG

1. Định Nghĩa

CSPRNG (Cryptographically Secure Pseudo-Random Number Generator — Bộ sinh số ngẫu nhiên giả an toàn về mặt mật mã) là PRNG thỏa mãn thêm 2 tính chất bảo mật:

  1. Next-bit test: Biết n bit đầu tiên, KHÔNG THỂ dự đoán bit thứ (n+1) với xác suất > 50% trong thời gian đa thức (polynomial time)
  2. State compromise resilience: Ngay cả khi attacker biết được state hiện tại, KHÔNG THỂ khôi phục các output trước đó

Nói đơn giản: CSPRNG tạo ra output mà ngay cả siêu máy tính cũng không thể phân biệt với số ngẫu nhiên thật.

2. So Sánh PRNG vs CSPRNG

Tính chất PRNG (Xorshift128+) CSPRNG (ChaCha20)
Tốc độ Cực nhanh (2-3 ns/number) Nhanh (10-20 ns/number)
Dự đoán được? Có — biết vài output → khôi phục state Không — bất khả thi về mặt tính toán
Chu kỳ 2¹²⁸ − 1 2²⁵⁶ (ChaCha20)
Dùng cho mật mã? ❌ KHÔNG ✅ CÓ
API Math.random() crypto.getRandomValues(), /dev/urandom

3. Lịch Sử Phát Triển

3.1. Thế hệ đầu: Blum-Blum-Shub (1986)

Lenore Blum, Manuel Blum và Michael Shub đề xuất BBS — CSPRNG đầu tiên có chứng minh bảo mật toán học. Dựa trên bài toán residuosity quadratic:

// BBS: x(n+1) = x(n)² mod M
// M = p × q (tích 2 số nguyên tố lớn)
// Output: bit cuối cùng của mỗi x(n)

def bbs(seed, p, q, n):
    M = p * q
    x = seed
    bits = []
    for _ in range(n):
        x = (x * x) % M
        bits.append(x & 1)  # lấy LSB
    return bits

# Rất chậm — chỉ có giá trị lý thuyết

BBS cực chậm (phải tính modular exponentiation) — chỉ có giá trị lý thuyết. Nhưng đặt nền tảng cho CSPRNG hiện đại.

3.2. Yarrow & Fortuna (1999/2003)

Bruce Schneier (cùng Niels Ferguson) thiết kế Yarrow (1999) rồi Fortuna (2003):

  • Yarrow: Dùng bởi macOS/FreeBSD cho /dev/random (ban đầu)
  • Fortuna: Cải tiến — tự động quản lý nhiều entropy pool, tránh single point of failure
  • Cả hai dùng AES-256 làm block cipher nội bộ

macOS chuyển từ Yarrow sang Fortuna từ macOS 10.12 (Sierra).

3.3. ChaCha20-based CSPRNG (2008–nay)

Daniel J. Bernstein thiết kế ChaCha20 (biến thể của Salsa20). Hiện tại:

  • Linux 4.8+ (2016): /dev/urandom dùng ChaCha20 thay LFSR
  • OpenBSD arc4random(): ChaCha20 từ 2013
  • Chrome/Node.js crypto.getRandomValues(): ChaCha20 trên nền OS
  • Rust rand crate: ChaCha12 mặc định

4. Các Thuật Toán CSPRNG Hiện Đại

4.1. ChaCha20 — Stream Cipher CSPRNG

ChaCha20 là stream cipher hoạt động trên ma trận 4×4 (16 words, mỗi word 32-bit = 512 bits):

// ChaCha20 quarter-round (core operation)
function quarterRound(state, a, b, c, d) {
  state[a] += state[b]; state[d] ^= state[a]; state[d] = rotl32(state[d], 16);
  state[c] += state[d]; state[b] ^= state[c]; state[b] = rotl32(state[b], 12);
  state[a] += state[b]; state[d] ^= state[a]; state[d] = rotl32(state[d], 8);
  state[c] += state[d]; state[b] ^= state[c]; state[b] = rotl32(state[b], 7);
}

function rotl32(v, n) {
  return ((v << n) | (v >>> (32 - n))) >>> 0;
}

// 20 rounds = 10 × (4 column rounds + 4 diagonal rounds)
// Input: 256-bit key + 96-bit nonce + 32-bit counter
// Output: 512 bits ngẫu nhiên mỗi block

4.2. AES-CTR-DRBG (NIST SP 800-90A)

Chuẩn NIST cho CSPRNG trong chính phủ Mỹ và ngành tài chính:

# Cấu trúc AES-CTR-DRBG (simplified)
class CTR_DRBG:
    def __init__(self, entropy, nonce):
        self.key = AES_key_from(entropy, nonce)  # 256-bit
        self.counter = 0
        self.reseed_counter = 0

    def generate(self, num_bytes):
        if self.reseed_counter > 2**48:
            self.reseed()  # bắt buộc reseed
        blocks = []
        for _ in range(num_bytes // 16 + 1):
            self.counter += 1
            blocks.append(AES_encrypt(self.key, self.counter))
            self.reseed_counter += 1
        return b''.join(blocks)[:num_bytes]

4.3. HMAC-DRBG (RFC 6979)

Dùng HMAC-SHA256 làm core. Đặc biệt quan trọng cho deterministic ECDSA (tránh lỗi reuse nonce):

// HMAC-DRBG pseudocode (RFC 6979)
// K = HMAC key, V = value (both 256-bit)
K = 0x00...00  (32 bytes)
V = 0x01...01  (32 bytes)

// Update:
K = HMAC(K, V || 0x00 || seed_material)
V = HMAC(K, V)
K = HMAC(K, V || 0x01 || seed_material)
V = HMAC(K, V)

// Generate:
V = HMAC(K, V)  → output
// Mỗi lần generate xong phải update K, V

5. Ứng Dụng Cụ Thể

CSPRNG được dùng trong mọi hệ thống bảo mật:

  • TLS/SSL: Tạo session key, nonce, IV cho mỗi kết nối HTTPS
  • SSH: Tạo ephemeral key cho key exchange
  • OAuth/JWT: Tạo access token, refresh token
  • Mật khẩu: Tạo salt cho bcrypt/argon2, tạo mật khẩu ngẫu nhiên
  • Blockchain: Tạo private key (256-bit) cho ví Bitcoin/Ethereum
  • Gambling: Provably fair — seed được hash trước, reveal sau để chứng minh không gian lận

6. API Trong Các Ngôn Ngữ

JavaScript (Browser & Node.js)

// Browser
const buffer = new Uint8Array(32);
crypto.getRandomValues(buffer);

// Node.js
import { randomBytes, randomUUID } from "node:crypto";
const key = randomBytes(32); // 256-bit key
const uuid = randomUUID();   // v4 UUID (122 random bits)

Python

import secrets
import os

# Tạo token URL-safe
token = secrets.token_urlsafe(32)  # 256-bit

# Tạo số ngẫu nhiên trong range
pin = secrets.randbelow(1_000_000)  # 6-digit PIN

# Bytes thô từ OS
raw = os.urandom(32)

# ⚠️ KHÔNG dùng `random` module cho bảo mật!
import random  # ❌ dùng Mersenne Twister — KHÔNG CSPRNG

Rust

use rand::rngs::OsRng;
use rand::RngCore;

fn main() {
    let mut key = [0u8; 32];
    OsRng.fill_bytes(&mut key); // /dev/urandom
    println!("256-bit key: {:?}", key);

    // Hoặc dùng getrandom crate (lower-level)
    let mut buf = [0u8; 16];
    getrandom::getrandom(&mut buf).expect("failed");
}

Java

import java.security.SecureRandom;

SecureRandom csprng = SecureRandom.getInstanceStrong();
byte[] key = new byte[32];
csprng.nextBytes(key); // 256-bit random key

// Hoặc sinh số trong range
int pin = csprng.nextInt(1_000_000); // 6-digit PIN

C (Linux)

#include <sys/random.h>
#include <stdio.h>

int main() {
    unsigned char key[32];
    // getrandom() — Linux 3.17+ (glibc 2.25+)
    ssize_t ret = getrandom(key, sizeof(key), 0);
    if (ret != sizeof(key)) {
        perror("getrandom failed");
        return 1;
    }
    // key now contains 256 bits of CSPRNG output
    return 0;
}

7. Lỗi Bảo Mật Nổi Tiếng

  • Debian OpenSSL (2008 — CVE-2008-0166): Comment nhầm 2 dòng code → entropy chỉ còn PID (~32,000 giá trị) → TẤT CẢ key SSL trên Debian trong 2 năm đều có thể brute-force
  • Sony PS3 ECDSA (2010): Dùng static k (nonce) cho ECDSA → lộ private key, jailbreak toàn bộ PS3
  • Android SecureRandom (2013): Thiếu entropy initialization → ví Bitcoin trên Android bị trộm
  • Dual_EC_DRBG (2013): NSA cài backdoor trong chuẩn NIST — Kleptographic attack

Bài viết liên quan

Đại Diễn Pháp Là Gì — Thuật Toán Bói Kinh Dịch Cổ Đại Với 50 Thẻ Thi

Đại Diễn Pháp (大衍法) là gì? Phương pháp bói Kinh Dịch cổ đại 3000 năm với 50 thẻ ...

System

Entropy Là Gì — Từ Nhiệt Động Học Đến Tin Học & Mật Mã

Entropy là gì? Từ Boltzmann (nhiệt động học), Shannon (lý thuyết thông tin), đến...

System