# How to solve this Baby Bleichenbacher Attack?

I am trying to solve this problem from https://toc.cryptobook.us/book.pdf. I am having trouble with this question :

(Baby Bleichenbacher attack). Consider an RSA public key (n, e), where n is an RSA modulus, and e is an encryption exponent. For x ∈ Zn, consider the predicate Px : Zn → {0, 1} defined as:

Show that by querying the predicate Px at about log2 n points, it is possible to learn the value of x.

• Hint: assume $x<n/2$. What do you learn when submitting $r=2$?
– fgrieu
Commented Nov 10, 2022 at 6:32
• @fgrieu Assuming x < n/2, if x \in [0, n/4] then P_x(r) will return 0, else it will return 1. I am getting that we are reducing range for possible values of x (we can use something like binary search), but how do we actually learn value of x? Commented Nov 10, 2022 at 7:36

By definition the starting knowledge is that x is in (0, n) interval. Then you test each power of 2 (incl. zero) as r. Each test tells you the new boundary for the interval to which x belong. If y eq. 1 -- we should drop lower half of the current interval, if it's eq. 0 then we drop upper bound. Let's imagine that for $$2^0$$ it returns 1, so we know that x is in ($$n/2$$, n). For the next step ($$2^1$$) if it returns 0, then x is in ($$n/2$$, $$3n/4$$). And so on.
As $$P_x(0)$$ tells us half of {Z_n} where x belongs, doubling of x let us iteratively calculate the interval (with length 1 in the end of the process) to which x will be wrapping around after each doubling.