Bleichenbacher 1998 "Million message attack" on RSA I have been reading Bleichenbacher's 1998 paper on a forged message attack on RSA. The paper assumes access to an Oracle that takes a ciphertext $c$ and will check the decrypted text for valid PKCS #1 padding and returns the validity of the padding. This side-channel can be used for an attack since we can send a forged ciphertext by selecting random integers $s$ and compute:

$c' = cs^{e}\, \mbox{mod}\, n$

If $c'$ is PKCS conforming we know that the two most significant bytes of $ ms = c'^{d} \mbox{mod}\,n$ were equal to 0x00 0x02.
If we define

$B=2^{8(k-2)}$

where $k$ is the length of $n$ in bytes, then we know

$2B\leq ms\,\mbox{mod}\,n&lt;3B $

Now we have a range $M_{0}$ in which we know $ms$ to lie:

$M_{0} = {[2B, 3B-1]}$

The attack now proceeds by iteratively generating more valid forged ciphertexts for integers $s_{i}$ and with the gained knowledge reduce the range of $M_{i}$

I am having trouble understanding Step 3 in the paper which deals with narrowing the set of solutions:

$M_{i} \leftarrow \cup_{a, b, r} \lbrace [\mbox{max}(a, [\frac{2B+rn}{s_{i}}]), \mbox{min}(b, [\frac{3B-1+rn}{s_{i}}])]\rbrace$

for all $[a,b] \in M_{i-1}$ and $\frac{as_{i}-3B+1}{n}\leq r&lt; \frac{bs_{i}-2B}{n}$

How would this be implemented in code? It looks to me that we would need to compute each range for every $r$ within the specified bounds e.g.:

for (r=r_min; r&lt;r_max; ++r)
    max(a, x);
    min(b, y);


However this seems to be intractable to me and I think I am making an error in trying to convert the math to code. Anyone maybe see where I am going wrong?
I implemented this padding oracle attack some time ago in Python and remember this part being a bit confusing to wrap my head around, my code is as follows:

newM = []
for (a, b) in M:
    # util.ceiling rounds arg1 / arg2 to the next highest integer
    rlow = util.ceiling((a*s - 3*B + 1), n)
    rhigh = (b*s - 2*B) / n

    for r in range(rlow, rhigh + 1):
        newa = max(a, util.ceiling(2*B + r*n, s))
        newb = min(b, (3*B - 1 + r*n) / s)
        newM.append((newa, newb))

M = list(set(newM))


So basically for each (a, b) pair in the set M you have to calculate the range of possible r values and create a new pair for each r. Since the pairs (a, b) are such that a &lt;= b, calling max for the first element and min for the second element ensures that for any (a, b) the new value of a can only increase and b can only decrease. Said another way, you never increase the range, you are always narrowing it down. So while the amount of pairs in M does increase for a while it eventually does decrease back down to one pair (a, b) where a = b.

Hope that is somewhat helpful. :)