Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Do you gain any advantage by knowing the factorization of $M$ (over just knowing $M$ itself) in the Blum Blum Shub generator?

The only advantage I see is being able to calculate the $i$-th number directly, as opposed to iterating to it. This doesn't seem like a very large gain to me.

share|improve this question
3  
Using CRT to speed up the computation? –  mikeazo May 20 at 12:55
1  
@mikeazo: actually, I think you have something, even if we're just computing the next output. If $p$ and $q$ are both $n$ bits, then doing BBS naively uses a $2n$-bit modular multiplication; with CRT, we end up with 3 $n$-bit modular multiplications (plus some additions/subtractions); if we assume a standard $O(N^2)$ multiplication algorithm, this is a win. –  poncho May 20 at 14:26
add comment

2 Answers 2

up vote 4 down vote accepted

Short answer: knowing $p$ and $q$ allows building a more efficient generator, including one with random access. Further, for an adversary, at least if $p-1$ and $q-1$ can be factored, that allows finding a period, and at least if the generator allows random access past that, building a distinguisher.


With secret seed $x_0$, the Blum Blum Shub generator computes output $f(x_i)$ for $i\ge1$, where $x_i$ is defined by the recurrence $x_{i+1}={x_i}^2\bmod M$, and $f()$ is some function [such as extraction of the low bit, or eXclusive-OR or all bits], and $M=p\cdot q$ with $p$ and $q$ large distinct primes with $p\equiv q\equiv 3\pmod4$.

That implies $x_i={x_0}^{(2^i)}\bmod M$, but direct evaluation of that expression has cost $\mathcal O(i)$, and is equivalent to directly applying the recurrence.

With knowledge of the factorization $M=p\cdot q$, we can compute the output for large $i$ directly and efficiently [in time $\mathcal O(\log(i))$], by computing ${x_0}^{2^i\bmod(p-1)}\bmod p$ and ${x_0}^{2^i\bmod(q-1)}\bmod q$, then using the Chineese Remainder Theorem to combine them into $x_i$. The CRT may also slightly speed up a generator proceeding using the recurrence, as pointed my mikeaso and made quantitative by poncho in comments (computation time can be reduced by up to $1/4$ with textbook multiplication algorithms).

An adversary (with no access to the full internal state of the generator) knowing the factorization of $M=p\cdot q$, and also able to factor $p-1$ and $q-1$, can compute $u=\lambda(p-1)$ and $v=\lambda(q-1)$ where $\lambda()$ is Carmichael's function [or $u=\varphi(p-1)$ and $v=\varphi(q-1)$ where $\varphi()$ is Euler's totient function], then $\operatorname{lcm}(u,v)$ which is a multiple of the period of the BBS generator, because for all $x$, $x^{(2^u)}\equiv x\pmod p$ and $x^{(2^v)}\equiv x\pmod q$. From that it is trivial to build a distinguisher between

  • a BBS black box accepting $i>0$ and returning the output of index $i$ in the BBS sequence for some fixed unknown random seed $x$;
  • a random oracle black box accepting $i>0$ and returning random output if that $i$ was not previously submitted, else returning its previous output for this $i$.

The distinguisher works by submitting $i=1$ and $i=\operatorname{lcm}(u,v)+1$, bets on BBS if the answers are equal, and on random oracle otherwise.

When

  • the BBS black box only outputs sequentially,
  • or proceeds sequentially by squaring modulo $M$,
  • or otherwise bounds $i$ to remain small,
  • or was built without knowledge of the factorization of $M$,
  • or $p-1$ or $q-1$ are hard to factor,

then I fail to exhibit a distinguisher (but would no be all that surprised if one could be devised).

share|improve this answer
add comment

Finding square roots modulo $M$ is difficult when $M$ is not prime. However, knowing the factors of $M$ lets one take the short cut of finding the roots modulo $p$ and $q$ (fast because they are prime), then using the Chinese Remainder Theorem to combine those to find roots modulo $M$.

I'm not sure how/whether that breaks Blum Blum Shub, though.

share|improve this answer
    
I believe the question was "what advantage would the legitimate generator have in retaining $p$ and $q$", not "if an adversary learned $p$ and $q$, how can they attack it" –  poncho May 20 at 14:35
    
Ok, my answer was rather off topic in that case. –  otus May 20 at 16:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.