I'm trying to understand the Bleichenbacher 1998 attack, but I am having trouble wrapping my head around the bounds-part.

So as far as I understand, the idea is the following:

We have a ciphertext $c = m^e \bmod n$ and we are trying to find the message $m$. So we want to make use of the fact that: $s^e \cdot c \bmod n = s^{e} \times m^e \bmod n = (s \times m)^e \bmod n$, which decrypts to $m \cdot s$. Say our new modified ciphertext $c'$ decrypts to $ms$, knowing $s$, we can then extract $m$ by calculating $m = ms \cdot s^{-1}$.

So we try out a bunch of different $s$ until we find one so that $ms$ is PKCS compliant. Now we know that $ms$ starts with 00 02, but it doesn't tell us anything about the rest of the decrypted message.

I do not really understand the concept of trying different bounds and ranges and how we can obtain the whole $ms$ message from it and thus extract $m$.

Can someone please explain to me the concept of how we gain more information on $ms$ by modifying $s$ ?

  • 2
    $\begingroup$ For me the improved attack from Crypto 2012 was easier to understand than the original. There is also a tutorial by one of the authors. See also the answer to this question. $\endgroup$
    – j.p.
    Commented Apr 25, 2020 at 17:29
  • $\begingroup$ Thanks alot, i will look into that one! $\endgroup$
    – FelRPI
    Commented Apr 26, 2020 at 8:16


Your Answer

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

Browse other questions tagged or ask your own question.