Blum, Blum and Shub (BB&S) (블룸, 블룸 앤 슈브 (BB&S))

유명한 “증명 가능한 보안” RNG를 개발한 기사. Blum, L., M. Blum, and M. Shub. 1983. Comparison of Two Pseudo-Random Number Generators. Advances in Cryptology: CRYPTO ’82 Proceedings. Plenum Press: New York. 61-78. 원본 BB&S 기사는 BB&S 시스템에서 충분히 긴 주기의 정확한 길이를 계산하는 기술을 설명합니다. 주기를 탐색하는 것보다 주기 길이를 확인하는 것이 훨씬 쉽기 때문에, 이는 x[0]이 충분히 긴 주기를 선택하는지 확인하는 실용적인 방법입니다. x[0] 값을 선택하고 확인하여 긴 주기가 선택될 때까지 수행할 수 있습니다. 현대 암호학은 격렬한 위협의 지점까지 그러한 검증이 불필요하다고 주장합니다. 그러나 원본 저자는 자신의 작업에 포함하는 것이 충분히 중요하다고 생각했습니다.

“증명 가능한 보안” 난수 생성의 도약

보안 통신의 초석인 무작위성이 증명될 수 있는 세상을 상상해 보세요. 1983년, Blum, Blum, Shub는 “두 개의 유사 난수 생성기 비교”라는 획기적인 기사로 이를 달성했습니다.

이것은 단순한 또 다른 알고리즘이 아니었습니다. BB&S는 난수 생성기(RNG)의 보안을 수학적으로 증명할 수 있는 방법을 제공했습니다. 가장 가치 있는 데이터를 보호하는 요새라고 생각하세요.

검증 가능한 보안의 힘

BB&S의 핵심 혁신 중 하나는 RNG에서 주기의 정확한 길이를 계산할 수 있다는 것이었습니다. 이것이 왜 중요할까요? 더 긴 주기는 더 강력한 보안으로 이어지기 때문입니다.

  • 쉬운 검증: 주기 길이를 확인하는 것은 전체 주기를 탐색하는 것보다 훨씬 간단하며, RNG의 강도를 보장하는 실용적인 방법을 제공합니다.
  • 선택에 대한 확신: 사용자는 시작 값을 선택하고 충분히 긴 주기를 생성하는지 확인할 수 있으므로 특정 요구 사항에 대한 최적의 보안을 보장합니다.

현대 암호학은 이러한 검증의 필요성을 낮게 평가할 수 있지만, BB&S의 제작자는 그 중요성을 인식했습니다. 그들은 진정한 보안이 투명성과 사용자 제어에 달려 있다는 것을 이해했습니다.

“증명 가능한 보안” 난수 생성기

룰렛 휠을 가지고 있다고 상상해 보세요. 진정으로 무작위인 룰렛 휠은 예측 불가능하여 공이 다음에 어디에 떨어질지 알 수 없게 합니다. 이것이 암호화 방식으로 안전한 난수 생성기의 아이디어입니다. 즉, 이상적인 룰렛 휠만큼 예측 불가능한 숫자를 생성해야 합니다.

Lenore Blum, Manuel Blum 및 Michael Shub가 개발한 BB&S 알고리즘은 그러한 생성기를 만드는 것을 목표로 했습니다. 그들은 단순히 “겉보기” 무작위성 이상을 원했습니다. 그들은 증명 가능한 보안을 원했습니다. 다음과 같이 생각해 보세요.

  • 일반 RNG: 무작위로 보이는 룰렛 휠과 같지만 공에 영향을 미치는 숨겨진 자석이 있을 수 있습니다.

  • BB&S RNG: 공개적으로 알려진 물리학으로 제작된 룰렛 휠과 같아서 수학적으로 편향되지 않았음을 증명할 수 있습니다.

주기 길이의 중요성

이제 룰렛 휠을 돌린다고 상상해 보세요. 결국, 그것이 정말로 무작위가 아니라면 동일한 일련의 숫자를 반복하기 시작할 수 있습니다. 그것이 주기입니다.

BB&S 논문은 이러한 주기의 길이를 계산하는 방법을 제공했습니다. 이것이 중요한 이유는 다음과 같습니다.

  • 짧은 주기: “무작위성”이 빠르게 소진되어 예측 가능한 룰렛 휠과 같습니다.

  • 긴 주기: 생성기는 훨씬 더 오랫동안 예측 불가능하게 유지됩니다.

Blum, Blum, Shub는 이 주기 길이를 확인하는 것을 믿었습니다. 그들은 오랫동안 제대로 회전하는지 확인하기 위해 룰렛 휠의 구조를 확인하는 것과 같다고 보았습니다.

현대 암호학의 입장

오늘날, 분야가 바뀌었습니다. BB&S는 존경받고 있지만, 주기 길이를 직접 계산하는 데 대한 강조는 줄었습니다. 현대 암호학은 엄격한 표준을 갖추고 있으며, 제대로 구현된 RNG에 대해 이 검증 단계를 불필요한 것으로 간주하는 경우가 많습니다.

BB&S의 장점:

  • 증명 가능한 보안: 많은 CSPRNG와 달리, BB&S의 보안은 큰 정수를 소인수 분해하는 계산적 어려움을 잘 연구한 것에 기반합니다. 이는 소인수 분해가 실제로 어렵다는 가정 하에 “증명 가능한 보안”을 제공합니다.
  • 주기 길이 검증: 원본 BB&S 논문은 생성기의 정확한 주기 길이를 계산하는 방법을 제공했습니다. 이를 통해 사용자는 선택한 시작 값(x[0])이 충분히 긴 주기를 생성하는지 확인할 수 있었고, 더 긴 기간 동안 무작위성을 보장했습니다.

BB&S의 단점:

  • 계산 비용: 다른 CSPRNG에 비해 BB&S는 모듈식 제곱 연산에 의존하기 때문에 비교적 느리며, 고속 난수 생성이 필요한 응용 프로그램에는 실용적이지 않습니다.
  • 주기 길이에 대한 현대적 관점: 원본 저자는 주기 길이 검증을 중요하게 생각했지만, 현대 암호학은 일반적으로 이를 불필요하게 간주합니다. 그 이유는 짧은 주기로 이어지는 시작 값을 무작위로 선택할 확률이 천문학적으로 작기 때문입니다. 따라서 대부분의 실제 응용 프로그램에서 검증의 추가 계산 비용은 정당화되지 않습니다.

결론: BB&S는 증명 가능한 보안 특성으로 인해 암호학 역사에서 중요한 자리를 차지하고 있지만, 최신 CSPRNG에 비해 계산 효율성이 떨어지고, 주기 길이의 중요성에 대한 이해가 발전하면서 현대 응용 프로그램에서 사용이 줄어들었습니다.