BBS 생성기가 내부적으로 생성하는 각 Xn에 대해 최하위 비트 또는 패리티 비트를 출력한다는 사실에 대한 이유는 무엇입니까? 즉, 그것이 생성하는 전체 Xn을 출력한다면, 진정한 무작위 함수와 구별 할 수있는 방법이 있습니까?
답변
이 유형의 질문에 대한 일반적인 대답 (왜 가장 낮은 차수의 N 비트 만 사용 하는가?)은 PRNG의 내부 상태에 대해 너무 많은 정보가 유출되는 것을 방지한다는 것입니다.
두 개의 연속 된 상태에서 공격자에게 완전한 X_n 상태를 제공하면 그들은 쉽게 계수를 결정할 수있어 PRNG의 모든 미래 상태를 계산할 수 있습니다.
즉, a = X_n 및 b = X_ (n + 1) 값이 주어지면 공격자는 b = a ^ 2 mod M이되도록 M을 찾을 필요가 있습니다. ^ 2가 M보다 큰 한 할 수 있어야합니다. M이 a ^ 2보다 크면 b = a ^ 2이고 공격자는 모듈이 작동 할 때까지 계속 숫자를 요구해야합니다.