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.
    Apr 25 '20 at 17:29
  • $\begingroup$ Thanks alot, i will look into that one! $\endgroup$
    – FelRPI
    Apr 26 '20 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.