Here I have attempted to implement Bleichenbacher's attack on ECDSA signatures created with biased nonces. The attack has been shown to work against signatures with single-bit nonce biases and it has been speculated that the attack is effective against fractional-bit nonce biases. My implementation follows the pseudocode presented in algorithm 2 of [1]. It uses NTL for big integer arithmetic, FFTW for discrete Fourier transforms, and OpenMP for parallelized sorting. A toy example of my code in action can be found in the example folder. For a detailed explanation of why the algorithm works, see [2].
Unfortunately I lack the recourses to fully test my code, so my work may contain some bugs. If you need to exploit a small nonce bias it is my hope that my work will, at the very least, save you some time.
[1] Diego Aranha, Pierre-Alain Fouque, Benoit Gérard, Jean-Gabriel Kammerer, Mehdi Tibouchi, et al.. GLV/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures with Single-Bit Nonce Bias. Palash Sarkar, Tetsu Iwata. Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Dec 2014, Kaoshiung, Taiwan. Springer, Advances in Cryptologie - ASIACRYPT 2014, 8873, pp.262-281, 2014, Lecture Notes in Computer Science.
[2] Mulder ED, Hutter M, Marson ME, Pearson P (2014) Using Bleichenbacher’s solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA: extended version. Journal of Cryptographic Engineering 4:33–45.