1
$\begingroup$

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?

$\endgroup$
0
2
$\begingroup$

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

$\endgroup$

Your Answer

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

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