Score:-3

Crypto

Show me all the steps and methods used to get from a system of 4 linear equations to solve for X1 and X2

cy424289

1/13/23, 8:22 PM

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.

0 + 0

elliptic-curves

signature

Score:0

Crypto

Daniel S

1/13/23, 9:05 PM

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.

0 + 0

cy424289

1/13/23, 9:28 PM

Please provide a step by step solution

kodlu

1/13/23, 9:31 PM

@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.

cy424289

1/15/23, 8:24 AM

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.

cy424289

1/15/23, 8:25 AM

Also thanks for your help @kodlu

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Show me all the steps and methods used to get from a system of 4 linear equations to solve for X1 and X2

TH: แสดงขั้นตอนและวิธีการทั้งหมดที่ใช้ในการแก้สมการเชิงเส้น 4 ตัวจากระบบสมการ X1 และ X2

RO: Arată-mi toți pașii și metodele folosite pentru a obține dintr-un sistem de 4 ecuații liniare pentru a rezolva pentru X1 și X2

RU: Покажите мне все шаги и методы, используемые для решения системы 4 линейных уравнений для X1 и X2.

VI: Chỉ cho tôi tất cả các bước và phương pháp được sử dụng để chuyển từ một hệ 4 phương trình tuyến tính để giải cho X1 và X2

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.