How to extract message in Bleichenbacher 1998 attack

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$$ ?

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