Bleichenbacher 1998

if there's an oracle that give it $c$, it will tells you if the $m$'s highest two bytes is 0x0002 (PKCS#1).

let $2^{8(k-1)}\le n<2^{8k}$, $B=2^{8(k-2)}$, if the oracle tells $m$ is PKCS conforming, that means

$$2\cdot B\le m<3\cdot B$$

---

Algorithm

let $M_i$ be a set of intervals that $m_0\in M_i$

step 1

given an cipher $c$, randomly choose $s_0$ to let $(c{s_0}^e(\mathrm{mod}n))$'s plain is PKCS conforming, then set $c_0=c(s_0{)}^e(\mathrm{mod}n)$, $M_0=[2B,3B-1]$, $i=1$

step 2

if $i=1$, because for any $s_1\le \frac{n}{3B}$, $s_1{m}_0$ will not be PKCS conforming, so search for the smallest integer $s_1>\frac{n}{3B}$, let $s_1{m}_0$ is PKCS conforming.

if $i>1$ and the number of intervals in $M_{i-1}$ is at least 2, then search for the smallest integer $s_i>s_{i-1}$ let $s_i{m}_0$ is PKCS conforming.

if $i>1$ and $M_{i-1}=[a,b]$, then choose small integer $r_i,s_i$ such that

$$r_i\ge 2\frac{b{s}_{i-1}-2B}{n}$$

and

$$\frac{2B+r_{i}n}{b}\le s_i<\frac{3B+r_{i}n}{a}$$

because $a\le m_0\le b$, so

$$\frac{2B+r_{i}n}{b}\le \frac{2B+r_{i}n}{m_0}\le s_i\le \frac{3B-1+r_{i}n}{m_0}\le \frac{3B-1+r_{i}n}{a}$$

use these $s_i$ until $s_i{m}_0$ is PKCS conforming

step 3

after $s_i$ has been found, set

$$M_i=\bigcup _{[a,b]\in M_{i-1},r_i}\{[\max (a,\lceil \frac{2B+r_{i}n}{s_i}\rceil ),\min (b,\lfloor \frac{3B-1+r_{i}n}{s_i}\rfloor )]\}$$

and for $[a,b]\in M_{i-1}$

$$\frac{a{s}_i-3B+1}{n}\le r_i\le \frac{b{s}_i-2B}{n}$$

because

$$\begin{array}{rl}& 2B\le s_i{m}_0(\mathrm{mod}n)\le 3B-1\\ \Rightarrow & 2B\le s_i{m}_0-r_{i}n\le 3B-1\\ \Rightarrow & 2B+r_{i}n\le s_i{m}_0\le 3B-1+r_{i}n\\ \Rightarrow & \lceil \frac{2B+r_{i}n}{s_i}\rceil \le m_0\le \lfloor \frac{3B-1+r_{i}n}{s_i}\rfloor \end{array}$$

and for every $[a,b]\in M_{i-1}$, we know that $2B\le s_i{m}_0-r_{i}n\le 3B-1$, so

$$a{s}_i-(3B-1)\le r_{i}n\le b{s}_i-2B$$

$$M_i=\bigcup _{[a,b]\in M_{i-1},r_i}\{[\max (a,\lceil \frac{2B+r_{i}n}{s_i}\rceil ),\min (b,\lfloor \frac{3B-1+kn}{s_i}\rfloor )]\}$$

step 4

if $M_i$ contains only one interval and $M_i=[a,a]$, then $m_0=a$, $m\equiv {s_0}^{-1}a(\mathrm{mod}n)$, else go back to step 2

---

Code

def bleichenbacher_1998(n: int, e: int, c: int, oracle):
    """
    - input : `n (int)`, `e (int)`, `c (int)`, `oracle (func)` , `c` is PKCS#1 conforming
    - output : `m (int)` , `e`'s plain
    - oracle func : 
        - input : `c (int)`
        - output : `PKCS_conforming (bool)` , is `c` PKCS#1 conforming
    """

    assert oracle(c)
    B = 1 << (n.bit_length() // 8 - 1) * 8

    def bleichenbacher_orifind_s(lower_bound: int):
        si = lower_bound
        while True:
            new_c = (pow(si, e, n) * c) % n
            if oracle(new_c):
                return si
            si += 1

    def bleichenbacher_optfind_s(prev_si: int, a: int, b: int):
        ri = ceil_int(2 * (b * prev_si - 2 * B), n)
        while True:
            low_bound = ceil_int(2 * B + ri * n, b)
            high_bound = ceil_int(3 * B + ri * n, a)
            for si in range(low_bound, high_bound):
                new_c = (pow(si, e, n) * c) % n
                if oracle(new_c):
                    return si
            ri += 1

    def bleichenbacher_merge_M(si: int, M: list):
        new_M = []
        for [a, b] in M:
            r_low = ceil_int(a * si - 3 * B + 1, n)
            r_high = floor_int(b * si - 2 * B, n) + 1
            for ri in range(r_low, r_high):
                interval_low = max(a, ceil_int(2 * B + ri * n, si))
                interval_high = min(b, floor_int(3 * B + ri * n - 1, si))
                if interval_high >= interval_low:
                    new_M.append([interval_low, interval_high])
        return new_M

    s = bleichenbacher_orifind_s(ceil_int(n, 3 * B))
    M = bleichenbacher_merge_M(s, [[2 * B, 3 * B - 1]])
    print(s, M)

    while True:
        if len(M) > 1:
            s = bleichenbacher_orifind_s(s + 1)
        else:
            if M[0][0] == M[0][1]:
                return M[0][0]
            s = bleichenbacher_optfind_s(s, M[0][0], M[0][1])
        M = bleichenbacher_merge_M(s, M)
        print(s, M)