-3
$\begingroup$

I am looking at an answer to a previous question and I would like more detail about how the answer was arrived at but I am not allowed to comment as I am a new user with low points.

I am therefore asking a new question based on an answer to a previous question. An answer was given but the details were not shown as to how the answer was derived. I have looked on line at methods of manipulating linear equations but they only show basic examples.

Could someone please show me step by step how the answer was arrived at.

This was the previous question. Is it possible to decrypt an ECDSA private key if the same nonce is used across different private keys?

In the answer there is a linear system of 4 equations in field Zp with 4 unknowns k1, k2, x1, x2. The other variables s, r and h are known.

What are the steps to get from:

s1k1 - r1x1 = h1 (mod p)

s2k1 - r1x2 = h2 (mod p)

s3k2 - r2x1 = h3 (mod p)

s4k2 - r2x2 = h4 (mod p)

(in the equations above h is congruent)

to:

X1 = (h1r2s2s3 - h2r2s1s3 -h3r1s1s4 + h4r1s1s3)/ r1r2(s1s4 - s2s3)

where operations including division are in the multiplicative group Z∗p.

$\endgroup$
0
$\begingroup$

Write $$\left(\matrix{-r_1&0&s_1&0\\ 0&-r_1&s_2&0\\ -r_2&0&0&s_3\\ 0&-r_2&0&s_4}\right)\left(\matrix{x_1\\x_2\\k_1\\k_2}\right)=\left(\matrix{h_1\\ h_2\\ h_3\\h_4}\right)$$ and apply Cramer’s rule (https://en.m.wikipedia.org/wiki/Cramer%27s_rule)

ETA: In other words $$x_1=\frac{\det\left(\matrix{ h_1&0&s_1&0\\ h_2&-r_1&s_2&0\\ h_3&0&0&s_3\\ h_4&-r_2&0&s_4}\right)}{\det\left(\matrix{-r_1&0&s_1&0\\ 0&-r_1&s_2&0\\ -r_2&0&0&s_3\\ 0&-r_2&0&s_4}\right)}$$ In both determinant calculations we can compute by taking the entries in the first column, multiply by the determinant of the minor formed by striking out the row and column of the entry and forming an alternating sum.

Thus the determinant in the numerator is $-h_1r_2s_2s_3+h_2r_2s_1s_3+h_3r_1s_1s_4-h_4r_1s_1s_4$ and the determinant in the denominator is $r_1r_2s_2s_3-r_2r_1s_1s_4$. Now gather terms and cancel signs.

$\endgroup$
4
  • $\begingroup$ Please provide a step by step solution $\endgroup$
    – cy424289
    Sep 13 at 21:28
  • $\begingroup$ @cy424289, the supplied answer uses standard undergraduate mathematics. Why dont you look up Cramer’s rule or matrix inversion in general? The keyword is linear modular equations. $\endgroup$
    – kodlu
    Sep 13 at 21:31
  • $\begingroup$ Thanks @Daniel S. I have accepted your answer it was very helpful. I would also like to know how this could be done using Gaussian Elimination. $\endgroup$
    – cy424289
    Sep 15 at 8:24
  • 1
    $\begingroup$ Also thanks for your help @kodlu $\endgroup$
    – cy424289
    Sep 15 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.