Search code examples
pythonrsabisection

In Python RSA broadcast attack, why am I using bit length in this binary search for the cube root?

https://stackoverflow.com/a/23622115/9481613

Shows this function:

def find_cube_root(n):
    lo = 0
    hi = 1 << ((n.bit_length() + 2) // 3)
    while lo < hi:
        mid = (lo+hi)//2
        if mid**3 < n:
            lo = mid+1
        else:
            hi = mid
    return lo

My input for the function is m3 the message cubed so that is why I need this function. The len(n) turns out to be 454 vs. 1507 for bit length.

I kept trying to cap high at num // 2 or num // 3 which was not working but this works. Why does bit length work here?

Solution

  • The algorithm attempts to compute the cubic root of integer n using bisection. The context is the final step of Håstad's broadcast attack, in which n can be thousands of bits, and is expected to be exactly the cube of an integer if all went well beforehand.

    Why does bit length work here?

    The expression

    hi = 1 << ((n.bit_length() + 2) // 3)

    yields a rough approximation of the desired result, by taking the logarithm to base 2, dividing by 3 (with some offset), and exponentiating to base 2. Let's prove the result is always by excess:

    1. For integer n >= 0, by specification of int.bit_length(), n.bit_length() is the smallest non-negative integer x such that n < 2**x.
    2. For every non-negative integer x, if holds x <= ((x + 2) // 3) * 3
    3. The function which for input x yields 2**x (that is two to the xth power) is nondecreasing
    4. Therefore n < 2**(((x + 2) // 3) * 3)
    5. By a standard property of powers, 2**(((x + 2) // 3) * 3)is (2**((x + 2) // 3))**3
    6. For every non-negative integer i, it holds (1 << i) == (2**i)
    7. Therefore the initial value of hi is such that n < hi**3 and hi >= 0.

    The loop invariant condition of the bisection algorithm

    lo <= hi  and  (lo-1)**3 < n  and  n <= hi**3

    is now easily established by induction: it hold before the while loop, and is maintained by the changes made in the loop (the proof uses that the function which for input x yields x**3 is nondecreasing), hence is valid on exit. Bisection narrows the gap between lo and hi by a factor about 2 at each loop, and terminates with lo >= hi. It follows that on output the function returns the smallest integer lo such that lo**3 >= n, which is the integer cubic root of n by excess.