Myriachan · January 1, 2017 06:52
diff --git a/sighax-optimization.txt b/sighax-optimization.txt
 Myria 2016-12-31

 I have some ideas for improving the sighax brute-force algorithm, but I have not yet implemented them to measure the difference in performance.

 The first optimization relates to the "mod" operation.  We are always mod-ing by the same number, the modulus.  We might be able to take advantage of this by using Barrett reduction to turn the mod into a multiplication, shift right, and subtract.  I don't know whether this would improve performance over GMP's mpz_mod.

 The second and third optimizations are mutually-exclusive.

 The second optimization is instead of multiplying by random values to the 65537th power, square the current number.  Squaring a number is faster than multiplying two different numbers.  (((x^2)^2)^2...)^65537 = (((x^65537)^2)^2)^2..., so this works.  To get the base value, count how many squares have been done and apply them to x.  Reset this procedure every million attempts or so, so that recovering x once a possibility is found doesn't take just as long as finding it.  Negatives still work as a second value with this design if you do it right.

 The current algorithm is based on (x^65537)*(y^65537) = (x*y)^65537.  Each time we multiply by a number whose 65537th root is known or easy to calculate.  But why must the number we multiply by be random?

 In addition to being able to find "random" values by taking a number to the 65537th power, we also know a few other numbers and their 65537th roots: the existing FIRM signatures are pairs x and y such that x^65537 = y.

 The third optimization relates to the PKCS #1 padding format.  PKCS #1 signatures are 0001FFFFFFFFFFFFFFFF...FFFF003031300D...  That is, they are 000200000000...0000 minus some ~408-bit number.  We can multiply by this number by doing a 2048x408-bit multiply, some bit shifting and subtracting.  This might be faster than a full 2048x2048-bit multiply.
	Myria 2016-12-31

	I have some ideas for improving the sighax brute-force algorithm, but I have not yet implemented them to measure the difference in performance.

	The first optimization relates to the "mod" operation. We are always mod-ing by the same number, the modulus. We might be able to take advantage of this by using Barrett reduction to turn the mod into a multiplication, shift right, and subtract. I don't know whether this would improve performance over GMP's mpz_mod.

	The second and third optimizations are mutually-exclusive.

	The second optimization is instead of multiplying by random values to the 65537th power, square the current number. Squaring a number is faster than multiplying two different numbers. (((x^2)^2)^2...)^65537 = (((x^65537)^2)^2)^2..., so this works. To get the base value, count how many squares have been done and apply them to x. Reset this procedure every million attempts or so, so that recovering x once a possibility is found doesn't take just as long as finding it. Negatives still work as a second value with this design if you do it right.

	The current algorithm is based on (x^65537)(y^65537) = (xy)^65537. Each time we multiply by a number whose 65537th root is known or easy to calculate. But why must the number we multiply by be random?

	In addition to being able to find "random" values by taking a number to the 65537th power, we also know a few other numbers and their 65537th roots: the existing FIRM signatures are pairs x and y such that x^65537 = y.

	The third optimization relates to the PKCS #1 padding format. PKCS #1 signatures are 0001FFFFFFFFFFFFFFFF...FFFF003031300D... That is, they are 000200000000...0000 minus some ~408-bit number. We can multiply by this number by doing a 2048x408-bit multiply, some bit shifting and subtracting. This might be faster than a full 2048x2048-bit multiply.
No results found