Anyhow, the number of equations will be always less than the number of variables, so I doubt that any CAS can really solve it. Also, if one wants to find possible values of s, will it be necessary to factorize all those big numbers before x's (which is hard as well)?
i see i made a few little mistakes in the description. actually you end up with two different x.
v1 = (x1 - h1) s mod q
v2 = (x2 - h2) s mod q
while h1 and 2 are known. so in fact you would have to collect a few more signatures. you will always end up with one variable more than you have equations.
so you have collected 10 equations, you have 11 unknown variables meaning all the x1...x10 plus s.
i have not yet managed to get this to work efficiently, but i am pretty sure that this is not much of a problem. i am really thinking, working, rethinking and hopefully i get it.
from the mathematical point of view, there is nothing that would prevent us solving a set of 10 linear equations with 11 variables for example. you would have a result in form of a linear congruence which you would then efficiently could cycle through.
its still all in the beginning phase, but i am working hard.
OK, I'm waiting for the math then. But have to confess that I didn't get you main idea so far. This q is supposed to be very large so that you cannot go through a cycle of length q in practice, right? So you'll need to prove that the size of the set of possible solutions decreases a lot as you increase the number of equations, and, for now, I don't see why should this be true.
well the key idea is, that you end up with solutions like this:
or something, for some random factors,
plus you get a few boundary conditions like the known ranges for s and x, which could make it even easier.
at the moment i am not even sure if you have to cycle through anything at all, or if a CAS can spit out the solution right away. i will need some more time to make it solid. but the fact is, that the linearity in the signing process is bad at all.
thats why ecdsa uses the modular inverse, and dsa uses exponentiation.
reverting exponentiation in a finite field is the unsolvable NP hard discrete logarithm problem.
solving linear equations in a finite field is no tough science at all.
i am not sure if factorizing is really necessary here.
lets make an easier example, we work on the galois field GF(6131) so we have 6131 elements in our space. the galois field GF(q) is much bigger but lets stick to the easy example for the moment.
Now let us say we have signed two messages:
message1: x=576 h=272 s=12345
so v=(576-272)*12345 mod 6131 = 708
message2: x=616 h=888 s=12345
so v=(616-888)*12345 mod 6131 = 1948
now we only know v and h, and we can create a first linear set of equations:
708 = (x1
1948 = (x2
reorganize equations: ($$)
1/s = (x1
1/s = (x2
-888)/1948note that the division operation is in fact a multiplication with invmod(x,6131)
once again (**)
-272)/708 = (x2
resulting congruence is when calculation over whole R:
= 177*n + 95
= 487*n + 401
now just find an n so that the euqation from above (marked **) fulfills equality in the finite field.
this should be doable on every calculator
if you have it, you get the n which will give you (once inserted in one of the formulas marked $$) the value of 1/s.
Inverse it, and you have the private key.
forgive me any mistakes, i just did this out of my head and this has to be verified by the devs first. but i have big concers due to the linearity and i hope we can jointly work on verifying (or denying) such thoughts as a community. i really hope i get accepted here.