Where does the range of possible values in Bleichenbacher's attack against PKCS #1 come from?

Question

In Bleichenbacher's paper on his attack against PKCS #1, we find:

If the oracle says that $c'$ is PKCS conforming, then the attacker knows that the first two bytes of $ms$ are $\mathtt{00}$ and $\mathtt{02}$. For convenience, let $$B = 2^{8(k−2)}.$$ Recall that $k$ is the length of $n$ in bytes. Hence, that $ms$ is PKCS conforming implies that $$2B \ \leq\ ms \bmod n \ <\ 3B$$

I know that if $c'$ is PKCS conforming, that means that $2 \times 16^{k-2} \leq c' < 3 \times 16^{k-2}$ (because the two most significant bytes of $c'$ are $\mathtt{00}$ and $\mathtt{02}$). I clearly understand why the size of the range from above is $2^{8(k−2)}$, but I don't see where the lower bound come from. Can someone please explain?

Answer 1

if $c'$ is PKCS conforming, that means that $2 \times 16^{k-2} \leq c' < 3 \times 16^{k-2}$

Uh, no. $k$ is the number of bytes, not hexadecimal nibbles. That must be made $$2 \times 256^{k-2} \leq c' < 3 \times 256^{k-2}$$ where $256=2^8$ because a byte holds 8 bits. And then it comes $$2 \times {(2^8)}^{k-2} \leq c' < 3 \times {(2^8)}^{k-2}$$ and from that $$2\times2^{8(k-2)} \leq c' < 3\times2^{8(k-2)}$$

Finally, with $B\ =\ 2^{8(k−2)}$ and $c'\ =\ ms\bmod n$ it comes $$2\times B \ \leq\ ms \bmod n \ <\ 3\times B$$ which is the intended meaning of $$2B \ \leq\ ms \bmod n \ <\ 3B$$