Have you by any chance read this?
https://eprint.iacr.org/2019/023.pdfIt describes methods which let us compute private keys if we have multiple signatures but using the same nonce. So maybe we can take the stuff there and apply it to the case we have a bunch of signatures with k and k+1 nonces. And by extension, k + constant M nonces.
First off it says if we know k then we can just get the private key with d
A = (sk - h)r
-1 mod n. But here we have two signature that use k and k+1. I suppose we can do some sort of attack with this by discovering the k of one signature and then "assuming" that for a large list of (r,s) signatures, that some of them have k+1, k+2, ... or k+M nonces.
It also gives the case of two signatures having the same nonce, where you can recover the private key by doing d
A = (h
1 - h
2)(s
1 - s
2)
-1 mod -n.
Now we have s
1 = k
1-1(h
1 + d
Ar
1) mod n and s
2 = k
2-1(h
2 + d
Ar
2) mod n.
That means d
A = (s
1k
1 - h
1)r
1-1 mod n = (s
2k
2 - h
2)r
2-1 mod n. We have r
1 = r
2 because k is not used to calculate it. This simplifies things further to (s
1k
1 - h
1) mod n = (s
2(k
1 + M) - h
2) mod n
(s
1k
1 - h
1) mod n = (s
2k
1 + s
2M - h
2) mod n.
Let's take this last equation and use algebra to move k
1 to the left.
(s
1k
1 - s
2k
1) mod n = (s
2M - h
2 + h
1) mod n
k
1(s
1 - s
2) mod n = (s
2M - h
2 + h
1) mod n
k1 = (s2M + h1 - h2)(s1 - s2)-1 mod n (I just reordered h1 in front of h2 which doesn't change the equation)
Where M =1 if you are using k,k+1 and M=2 if you have k,k+2, etc. and it works for M=0 and negative M as well (which you'd use for k,k-1, k,k-2, and so on.
EDIT: If we plug Nk + M instead of just k + M, following the proof derivation above (which I can repost for this particular case if you want) gives us k
1 = (s
2M + h
1 - h
2)(s
1 - s
2N)
-1 mod n. I'm sure there's a formula for k
2 being an arbitrary polynomial of k
1, I'm still trying to find one for that.
EDIT2: for k,k
2+M we have k
1(s
1 - s
2) + s
2k
12 mod n = (s
2M - h
2 + h
1) mod n. So at this point it seems that you have to
calculate terms of a series find the root of this polynomial if you want an solve for arbitrary k2 = a + bk1 + ck1^2 + ...