# 블룸 블룸 슙 (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은 누구나 바로 소인수분해할 수 있으므로 전혀 안전하지 않습니다.

---
출처: https://achivx.kr/glossary/blum-blum-and-shub-bbs-%EB%B8%94%EB%A3%B8-%EB%B8%94%EB%A3%B8-%EC%95%A4-%EC%8A%88%EB%B8%8C-bbs/ · ACHIVX 용어 사전 · 수정일 2026-10-20