liveBook · Manning

Bisection method

As explained in Hacking Cryptography

A root-finding technique that repeatedly halves an interval according to whether a candidate is below or above the target.

The bisection method finds a target by repeatedly halving a bounded search interval. Compare each guess with the target, discard the impossible half, and continue until the answer or a sufficiently close result is reached. section 9.6.3

Cube-root search in a signature forgery

To search from 1 through 1,000, try 500 first. If the target is greater, try 750; otherwise continue in the lower half. The technique finds a prefix cube root for a Bleichenbacher e = 3 signature forgery, where the cubed candidate matches the target's leading bytes while unrelated trailing bytes are tolerated. A Go implementation adjusts the guess according to the comparison, halves the step, and tests the resulting cube. section 9.6.3

How Hacking Cryptography covers it

How deep it goes
Explains interval updates and implements comparison-driven step halving, but does not develop general convergence analysis.
Examples
Uses a 1–1,000 guessing scenario, a numerical cube-root example, and Go tests matching cubed prefixes.
What it assumes
Assumes basic comparison, integer arithmetic, cube roots, and RSA public-exponent notation.
What you can do after
Build it from scratch by implementing and testing a comparison-driven cube-root prefix search in Go.
How it connects
Connects bisection search with cube roots, RSA, PKCS #1 v1.5 padding, and Bleichenbacher signature forgery.
Cover of Hacking Cryptography
liveBookmanning.com
Read Hacking Cryptography on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Hacking Cryptography. The section links point to the parts of the book it draws on.