1
$\begingroup$

I am currently studying cryptography. I came across this problem:

I had an exercise that as a vulnerability had that k is generated every 10 seconds:

class DSA:
    def __init__(self):
        self.q = 0x926c99d24bd4d5b47adb75bd9933de8be5932f4b
        self.p = 0x80000000000001cda6f403d8a752a4e7976173ebfcd2acf69a29f4bada1ca3178b56131c2c1f00cf7875a2e7c497b10fea66b26436e40b7b73952081319e26603810a558f871d6d256fddbec5933b77fa7d1d0d75267dcae1f24ea7cc57b3a30f8ea09310772440f016c13e08b56b1196a687d6a5e5de864068f3fd936a361c5
        self.h = random.randint(2,self.p-2)
        self.g = pow(self.h, (self.p-1)//self.q, self.p)
        self.x = random.randint(1, self.p-1)
        self.y = pow(self.g, self.x, self.p)

    def sign(self, m):
        H = bytes_to_long(sha1(m).digest())
        k = int(time.time())//10
        r = pow(self.g, k, self.p) % self.q
        s = (inverse(k, self.q)*(H + self.x*r)) % self.q
        assert(s != 0)
        return hex(r)[2:].rjust(40,'0') + hex(s)[2:].rjust(40,'0')

    def verify(self, m, sig):
        r, s = int(sig[:40],16), int(sig[40:],16)
        a = pow(self.g, (bytes_to_long(sha1(m).digest())*inverse(s,self.q)) % self.q, self.p)
        b = pow(self.y, (r*inverse(s, self.q)) % self.q, self.p)
        return (a*b % self.p) % self.q == r

Now I have a similar problem:

class DSA:
    def __init__(self):
        self.q = 0x926c99d24bd4d5b47adb75bd9933de8be5932f4b
        self.p = 0x80000000000001cda6f403d8a752a4e7976173ebfcd2acf69a29f4bada1ca3178b56131c2c1f00cf7875a2e7c497b10fea66b26436e40b7b73952081319e26603810a558f871d6d256fddbec5933b77fa7d1d0d75267dcae1f24ea7cc57b3a30f8ea09310772440f016c13e08b56b1196a687d6a5e5de864068f3fd936a361c5
        self.h = random.randint(2,self.p-2)
        self.g = pow(self.h, (self.p-1)//self.q, self.p)
        self.x = random.randint(1, self.p-1)
        print(self.x%self.q, file=sys.stderr)
        self.y = pow(self.g, self.x, self.p)
        self.k = random.randint(1, self.q-1)

    def sign(self, m):
        self.k += 1337
        print(self.k%self.q, file=sys.stderr)
        H = bytes_to_long(sha1(m).digest())
        r = pow(self.g, self.k, self.p) % self.q
        s = (inverse(self.k, self.q)*(H + self.x*r)) % self.q
        assert(s != 0)
        return hex(r)[2:].rjust(40,'0') + hex(s)[2:].rjust(40,'0')

    def verify(self, m, sig):
        r, s = int(sig[:40],16), int(sig[40:],16)
        a = pow(self.g, (bytes_to_long(sha1(m).digest())*inverse(s,self.q)) % self.q, self.p)
        b = pow(self.y, (r*inverse(s, self.q)) % self.q, self.p)
        return (a*b % self.p) % self.q == r

If I can see the standard error I implemented the function to trace back to k, but without these printouts is it possible to get k somehow? Because looking at it this way it looks like a standard implementation except now k+1337.

I saw this post but i cannot find a way to do it. In the other post k increases by 1 but here by 1337

I tried to do:

import sympy as sp

def solve_for_k_x(s1, s2, r1, r2, h1, h2, q):

    k, x = sp.symbols('k x', integer=True)


    k_expr = (h2 - s2 - h1 * r2 / r1) / (s2 - s1 * r2 / r1) % q 
    x_expr = (s1 * k_expr / r1 - h1 / r1) % q  

    k_value = sp.simplify(k_expr)
    x_value = sp.simplify(x_expr)

    return k_value, x_value

# Valori di esempio per s1, s2, r1, r2, h1, h2, q
s1_val = 64882725248190278368163852092620798333110668672
s2_val = 282411680651513963724325965713579882843144194333
r1_val = 367250667907884668700248717503315476068112824538
r2_val = 573986818728218651349078202408414870449989474241
h1_val = 846233849201412402092198193498282831578689296025
h2_val = 821280535791308016431709783329123666416004372059
q_val = 0x926c99d24bd4d5b47adb75bd9933de8be5932f4b


k_result, x_result = solve_for_k_x(s1_val, s2_val, r1_val, r2_val, h1_val, h2_val, q_val)
print("k =", k_result)
print("x =", x_result)
$\endgroup$
2
  • 1
    $\begingroup$ There's 2 term known: the message hash, and k, and 1 unknown but static term: x. And generate 2 signature-message pairs, you get 2 equations that can be reduced to linear form. $\endgroup$
    – DannyNiu
    Commented Apr 30 at 4:10
  • $\begingroup$ Can you help me with the equation please? Thank you $\endgroup$
    – Edoardo
    Commented Apr 30 at 8:04

1 Answer 1

1
$\begingroup$

Let's start by prettify the formula first,

$$r = g^k \pmod q$$ $$s = {{h+xr}\over{k}}$$

The variables $r$ and $s$ are signature components, $x$ is private key, $h$ is message hash.

Now 2 signatures:

$$s_1 = {{h_1+xr}\over{k}}$$ $$s_2 = {{h_2+xr}\over{k}}$$

Multiply both sides by k:

$$s_1k = h_1+xr$$ $$s_2k = h_2+xr$$

Move unknowns to the left side, and constants to the right side:

$$s_1k-xr = h_1$$ $$s_2k-xr = h_2$$

Compare this with:

$$ax+by = c$$ $$dx+ey = f$$

Use the same method you'd use to get $x$ $y$ to get $k$ and $x$.

$\endgroup$
5
  • $\begingroup$ yes but from the two signatures I have r1 and r2 and k1 and k2 = k1 + 1337 $\endgroup$
    – Edoardo
    Commented Apr 30 at 9:30
  • $\begingroup$ The rewrite the 2nd equation as $s_2(k_1+1337)-xr_2=h_2$, expand the parentheses, and move the constant terms to the right, then Bob's your uncle. $\endgroup$
    – DannyNiu
    Commented Apr 30 at 11:09
  • $\begingroup$ @moderators, this should be our canonical Q for step-by-step analysis of biased $k$ discrete-logarithm signature forgery guide. $\endgroup$
    – DannyNiu
    Commented Apr 30 at 11:10
  • $\begingroup$ Yes, but then how are the two equations connected to each other? Do I have to calculate them at the same time? $\endgroup$
    – Edoardo
    Commented Apr 30 at 12:00
  • $\begingroup$ @Edoardo I don't know about your place, but solving linear equation systems is middle-school level stuff in my national compulsory education curriculum. If you forgot all of those, or teacher haven't told you about it, you can look it up on various tutorial websites, such GeeksForGeeks, MathIsFun, etc. $\endgroup$
    – DannyNiu
    Commented Apr 30 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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