Nice! I like that you appreciate how the linearity helps to make it a one-liner.
You could explain it more for others if you like :)
Discussion
Sure. Schnorr signatures take a nonce `k` and a challenge `e` and produce a signature by computing:
s = k + e*a
, where a is the private key of the signer and the number we want to find.
The problem gave 2 signatures, which give a ssytem of linear congruences:
s_1 = k_1 + e_1*a (mod p)
s_2 = k_2 + e_2*a (mod p)
Since we know that the difference between k_2 and k_1 is 7, the system is suddenly determined and we can subtract equation 2 from equation 1:
s_2 - s_1 = k_2 - k_1 + e_2*a - e_1*a (mod p)
Now we know k_2-k_1 so:
s_2 - s_1 = k_delta + e_2*a - e_1*a (mod p)
And solve for a:
a = (s_2-s_1 - k_delta) * (e_2-e_1)^-1 (mod p)
Where ^-1 is the modular inverse.
nostr:nprofile1qqsxwkuyle67y94tj378gw8w2xw2wa6nwmwlqhddlwnz0z7sztsaw2qn2rdgc anotther fun challenge could be cracking the private key when the k are given by a predictable random number generator!
Yeah. That even might be one of the matasano (now cryptopals) challenges. Like Mersenne twister.
A bit much for a "quiz" perhaps. This simple example at least disabuses people of the mistaken belief that it's only nonce *reuse* that's dangerous (although, who that is helping I could not tell you š).
This simple quiz really helped me clear up some still-fresh concepts Iāve been studying, so thank you both. More #cryptostr is welcome in my feed :)
Been wondering about this harder version. If itās simple to state or link, would appreciate it.
I have a vague sense that n+1 txns using a polynomial would likely leak a key, but canāt see how a complex permutation of the scalar field could be cracked without knowing some properties about it. Quick google didnāt yield any results
Thanks for posting. I used similar approach but somehow got formula wrong