We was given 70 lines of text, each line had format (h, r, s), with h is SHA1 hash of a message m, and pair (r, s) is digital signature of message m using ElGamal signature scheme. And our task is to “sign” a message, “Mat3CtfDummyPKI“. At a glance we can easily recognize that r is repeated, it means that the signer use same random value k to sign every messages. This mistake can lead us to recover the random value k, and after that, the secret key x, so we can sign with our own message. After a few minutes searching, I had found something great. A guy answers this question on crypto.stackexchange.com and explains the method to solve this task very easy to understand.
Now it is easier, write a small script to solve it.