Score:0

Cryptography (DSA) Get Value of k and private Key

ng flag

i am on a task in cryptography and need a hint (PLEASE NO SOLUTION).

The Task is:

I can send Messages (Digital Numbers) to a Docker Container. The response are the values p,q,g,z1,s,r and hashvalue(m+z1). So... when i enter the number 1 i get the DSA values used for signing.

Unknown is the value of k, z2 and x (the private key)

Known is that p,q,g,z1,z2 are fixed for every message. So they are the same everytime.

Known is, that the value of k is calculated:

k = g^(hashvalue + z2) mod q

so - in my understanding: To find out the value of k i have to find 2 messages which are using the same k. If i succeded i can calculate key with

k = (M1 - M2) / (s1 - s2)

But how can i find out, that 2 messages use the same k with the given values?

What i am actually doing:

I wrote a Python Programm which iterates through every message, starting from message = 0. Then Calculating k with the formula and ignoring z2 (which is absolutely wrong i think...). Saving the values from calculated k in an array. Then raising message += 1 and doing the same. After that im comparing k from actual message with saved values from messages before if its the same. But im now at message 2000000. So - i think im doing the wrong things.

Am i totally on the wrong way?

I can pull more values with other messages if needed. Can someone help me?

fgrieu avatar
ng flag
It's unclear what the question's z1 and z2 are. [Actual DSA](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf#page=28) hashes the message, not the concatenation of the message and some z1 (much less the result of an addition). And the result is not called z2. Recommendation: first find what's what by checking the signatures you obtain.
mangohost

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.