블룸 블룸 슙 (Blum Blum Shub, BBS)

블룸 블룸 슙(BBS)은 x(n+1) = x(n)² mod M 반복으로 비트를 뽑는 의사난수 생성기로, 출력 예측이 큰 수의 소인수분해만큼 어렵다는 것이 증명된 대표적인 '증명 가능한 안전성' 생성기입니다.

자세히 알아보기

BBS는 레노어 블룸(Lenore Blum), 마누엘 블룸(Manuel Blum), 마이클 슙(Michael Shub)이 제안했습니다. 1982년 CRYPTO 학회 발표(논문집 1983년)에서 처음 소개되었고, 1986년 SIAM Journal on Computing에 「A Simple Unpredictable Pseudo-Random Number Generator」로 정식 발표되었습니다. 이름의 BB&S, BBS는 세 저자의 성에서 왔습니다.

동작은 단순합니다.

1. 4로 나눈 나머지가 3인 큰 소수 p, q를 고르고 M = p·q로 둡니다(이런 M을 블룸 정수라고 합니다).
2. M과 서로소인 시드 s를 골라 x(0) = s² mod M으로 시작합니다.
3. x(n+1) = x(n)² mod M을 반복하고, 매 단계 x의 최하위 비트(또는 몇 개의 하위 비트)를 출력합니다.

p와 q를 모르는 사람이 출력의 다음 비트를 무작위 추측보다 잘 맞힐 수 있다면, 그 능력으로 이차잉여 문제(사실상 M의 소인수분해와 연결된 문제)를 풀 수 있다는 것이 증명되어 있습니다. 이 때문에 "증명 가능한 안전성"을 가진 생성기의 교과서 예시가 되었습니다. 원 논문은 수열의 주기 길이를 계산하는 방법도 다루며, 시드가 짧은 주기에 빠지지 않는지 확인하는 방법을 제시했습니다. 실제로는 M이 충분히 크면 짧은 주기에 걸릴 확률이 매우 낮습니다.

단점은 속도입니다. 비트 하나(또는 몇 개)를 얻을 때마다 수천 비트 크기의 모듈러 제곱이 필요해, AES-CTR이나 ChaCha20 기반 생성기, NIST SP 800-90A의 HMAC_DRBG·CTR_DRBG보다 훨씬 느립니다. 그래서 실무에서는 거의 쓰이지 않고, 이론적 기준점으로 주로 다뤄집니다.

블록체인·암호화폐에서는

지갑이나 노드가 BBS를 직접 쓰는 경우는 드뭅니다. 키 생성에는 운영체제의 암호학적 난수 생성기나 표준 DRBG가 쓰입니다. 다만 "안전성을 계산 난제로 환원한다"는 BBS의 증명 방식은 RSA 등 공개 키 암호와 블록체인 암호 설계 전반의 사고방식과 같습니다.

쉽게 말하면

비밀 두 소수를 아는 사람에게만 규칙이 보이고, 모르는 사람에게는 동전 던지기처럼 보이는 숫자 제조기입니다.

예시

학습용으로 아주 작은 수를 써 보겠습니다(실제로는 수천 비트 크기의 소수를 씁니다). p = 11, q = 23은 모두 4로 나눈 나머지가 3이므로 M = 253입니다. 시드 s = 3이면 x(0) = 9입니다.

• x(1) = 9² mod 253 = 81 → 최하위 비트 1
• x(2) = 81² mod 253 = 236 → 0
• x(3) = 236² mod 253 = 36 → 0
• x(4) = 36² mod 253 = 31 → 1

출력 비트열은 1, 0, 0, 1, …입니다. 이렇게 작은 M은 누구나 바로 소인수분해할 수 있으므로 전혀 안전하지 않습니다.