2
$\begingroup$

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:

enter image description here

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

Improve this question
$\endgroup$
2
  • $\begingroup$ Hint: assume $x<n/2$. What do you learn when submitting $r=2$? $\endgroup$
    – fgrieu ♦
    Commented Nov 10, 2022 at 6:32
  • 1
    $\begingroup$ @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? $\endgroup$
    – Lightening
    Commented Nov 10, 2022 at 7:36

1 Answer 1

Reset to default
1
$\begingroup$

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.

PS Never heard term "Baby Bleichenbacher", but it doesn't differs in essence from "RSA parity oracle", which is easy to get a lot of examples, descriptions and discussions around.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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