5
$\begingroup$

I'm currently attempting to recover an ECDSA key.

I have $m$, $m'$ and signatures $(r, s)$, $(r', s')$, and I know that $k$ is constant, the curve is NIST P-192 and the hash function of the. As such, I'm attempting to compute $d_A$ as shown on the wikipedia page for ECDSA.

However, after recovering $k$ (on the stage where I am computing $d_A$), I get a floating point result for $d_A$. Is this to be expected? If not, what would be the correct way of handling it?

My code, if it helps:

#!/usr/bin/python
import hashlib
import ecdsa.util
import ecdsa
import sys
import base64

n = 6277101735386680763835789423176059013767194773182842284081
r1, s1 = ecdsa.util.sigdecode_string(open("sig1.bin", "rb").read(), n)
r2, s2 = ecdsa.util.sigdecode_string(open("sig2.bin", "rb").read(), n)
hash1 = hashlib.sha1('iSsuZJOq1FNKMuK4wm88UEkr21wgsypW'.encode('utf-8')).digest()
hash1 = ecdsa.util.string_to_number(hash1)
hash2 = hashlib.sha1('x3wqOnaetBPO66TrBaMyr3NQIDbhvK0w'.encode('utf-8')).digest()
hash2 = ecdsa.util.string_to_number(hash2)
print(r1 == r2)
#Much modulo N. Such wow.
#This totally didn't bite me in the ass for quite a while or anything <.<
top = (hash1 - hash2) % n
bottom = (s1 - s2) % n
print((top / bottom) % n)
k = int((top / bottom) % n)
print("Common constant k=0x%x" % k)
secret = (s1 * k) % n
secret = (top - hash1) % n
secret = (top / r1) % n
print(secret)

And the output:

True
6.337358414243492
Common constant k=0x6
50.34135291546233
$\endgroup$
10
$\begingroup$

This is not correct, the private key $d_A$ must always be an integer. Your mistake is that you are doing modular division e.g. $\frac{a}{b} \text{ mod } n$ incorrectly. You cannot simply divide the integers and then reduce by the modulus. The correct way to do this is to compute the modular inverse of $b$ i.e. $b^{-1} \text{ mod } n$ and then compute $a*b^{-1} \text{ mod } n$.

$\endgroup$

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.