ECDSA is very popular recently...

ECSign

import hashlib
import random
from Crypto.Util.number import inverse, bytes_to_long, long_to_bytes
from Crypto.Random import get_random_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from ecdsa import NIST256p

from flag import FLAG

message = b"ECDSA prevents forging messages"

curve = NIST256p
G = curve.generator
n = curve.order

class Signature:
    def __init__(self):
        self.privkey = random.randrange(n)
        self.pubkey = self.privkey * G
        self.r = random.randrange(n)
        self.s = random.randrange(n)

    def sign(self, msg, k):
        hsh = int(hashlib.sha256(msg).hexdigest(), 16)
        p = k * G
        self.r = p.x() % n
        self.s = (inverse(k, n) * (hsh + (self.privkey * self.r) % n)) % n
        return (self.r, self.s)

    def f_sign(self, msg, k):
        hsh = int(hashlib.sha256(msg).hexdigest(), 16)
        self.s = (inverse(k, n) * (hsh + (self.privkey * self.r) % n)) % n
        return (self.r, self.s)

sig = Signature()
k = random.randrange(n)

sig1 = sig.sign(message, k)
sig2 = sig.f_sign(message, k^0xffffffff)
sig3 = sig.f_sign(message, k^0xffffffff00000000)

r = random.randrange(n)
pubkey2 = r*G
sharedkey = r*sig.pubkey

iv = get_random_bytes(16)
key = long_to_bytes(int(sharedkey.x()))
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = cipher.encrypt(pad(FLAG, 16))

print("pubkey="+ str((int(sig.pubkey.x()), int(sig.pubkey.y()))))
print("sig1=" + str(tuple(map(lambda x:int(x), sig1))))
print("sig2=" + str(tuple(map(lambda x:int(x), sig2))))
print("sig3=" + str(tuple(map(lambda x:int(x), sig3))))

print("pubkey2="+ str((int(pubkey2.x()), int(pubkey2.y()))))
print("iv=" + "0x"+str(iv.hex()))
print("ct=" + "0x"+str(ct.hex()))

pubkey=(38745398585592404989617041657020362138123363380468846963780930586996547144750, 13643061224989896432264609612335708262502935494164515568037402963951605264829)
sig1=(77834524933954296097833315313842984664992628710802286706422333910202549804044, 106047115067349115009621212644299274382951056066902044358604548248126784117113)
sig2=(77834524933954296097833315313842984664992628710802286706422333910202549804044, 77856639655128453708803009032309618307780628811843761077611198123911335033581)
sig3=(77834524933954296097833315313842984664992628710802286706422333910202549804044, 113246340396800206689440828533000149451101779708634101475318788958650261939751)
pubkey2=(18408891362196717436082197656011814689561019672942300120844335017129989755383, 89780168462818288492260141231746707551390283872983535472764708240708422195758)
iv=0x1d828a4a93bc2026ae1c8ab1711a1991
ct=0x8c5350234cf12b0f4da1d344124fe76e29906fbf5a1ed45cc8c7a29009dc078a31a6150b8ec5be75e1f7cef7665f634b

Solution

We are given three ECDSA signatures of the same message. The only thing that changes is the nonce, and it only changes slightly. To decrypt the flag, we need to recover the secret signing key used to sign these messages.

Recall that in ECDSA a message $m$ is signed by choosing a random nonce $k$ and then computing

r = (kG)_x \qquad s = k^{-1}(H(m) + rd)

where $d$ is the secret signing key. Computations are performed modulo $n$ , where $n$ is the curve order. The signature is $(r, s)$ .

In our case, the signatures all share the same $r$ value, but the $s$ values are different. We have

\begin{aligned} s_1 &= k^{-1} (H(m) + rd) \\ s_2 &= (k \oplus (2^{32} - 1)) (H(m) + rd) \\ s_3 &= (k \oplus (2^{64} - 2^{32})) (H(m) + rd) \end{aligned}

Since XOR is annoying to work with algebraically, we approximate the XOR operations with additions:

\begin{aligned} s_1 &= k^{-1} (H(m) + rd) \\ s_2 &= (k + t_2) (H(m) + rd) \\ s_3 &= (k + t_3) (H(m) + rd) \end{aligned}

where $|t_2| < 2^{32}$ and $|t_3| < 2^{64}$ . Note that because we do not know $k$ , we do not immediately know $t_2$ and $t_3$ . However, they are small values (compared to the curve order), and LLL is magical.

At the moment, we have three equations in four unknowns $k, t_2, t_3, d$ . We can combine these to get one equation in two unknowns. We choose to eliminate $k$ and $d$ so that we get a relation containing only $t_2$ and $t_3$ . It turns out we get the equation

\begin{aligned} c_2 t_2 + c_3 t_3 &\equiv 0 \pmod n \\ \implies c_2 t_2 + c_3 t_3 &= bn \end{aligned}

For some coefficients $c_2$ and $c_3$ and some integer $b$ . And since the unknowns are small compared to $n$ , we have the perfect setting to use lattice techniques.

Consider the lattice generated by the rows of the following matrix:

M = \begin{bmatrix} c_2 & 1 & 0 \\ c_3 & 0 & 1 \\ n & 0 & 0 \end{bmatrix}

Denote by $r_i$ the $i$ th row. Note that $t_2 r_0 + t_3 r_1 - bn = 0$ , so $(0, t_2, t_3)$ is a short vector in this lattice. We can find this exact vector by using the LLL algorithm and looking for a vector with $0$ in the first entry. This gives us the values of $t_2$ and $t_3$ .

Once we have recovered $t_2$ and $t_3$ , we can substitute them into the expressions for $s_1, s_2$ and $s_3$ . We are then left with three equations and two unknowns. It is easy to solve for the private key $d$ , e.g. with Gröbner bases, resultants, rearranging by hand, etc.

import hashlib
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

from sage.matrix.matrix2 import Matrix
def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))

h = int(hashlib.sha256(b'ECDSA prevents forging messages').hexdigest(), 16)
pubkey = (38745398585592404989617041657020362138123363380468846963780930586996547144750, 13643061224989896432264609612335708262502935494164515568037402963951605264829)
r = 77834524933954296097833315313842984664992628710802286706422333910202549804044
s1 = 106047115067349115009621212644299274382951056066902044358604548248126784117113
s2 = 77856639655128453708803009032309618307780628811843761077611198123911335033581
s3 = 113246340396800206689440828533000149451101779708634101475318788958650261939751
pubkey2 = (18408891362196717436082197656011814689561019672942300120844335017129989755383, 89780168462818288492260141231746707551390283872983535472764708240708422195758)
iv = bytes.fromhex('1d828a4a93bc2026ae1c8ab1711a1991')
ct = bytes.fromhex('8c5350234cf12b0f4da1d344124fe76e29906fbf5a1ed45cc8c7a29009dc078a31a6150b8ec5be75e1f7cef7665f634b')

n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
P.<k,t2,t3,d> = PolynomialRing(Integers(n))

f1 = s1*k - h - r*d
f2 = s2*(k+t2) - h - r*d
f3 = s3*(k+t3) - h - r*d
h1 = resultant(f1, f2, d)
h2 = resultant(f1, f3, d)
g1 = resultant(h1, h2, k)

c2, c3 = map(ZZ, g1.coefficients())
M = matrix(ZZ, [
    [c2, 1, 0],
    [c3, 0, 1],
    [n, 0, 0]
])
M = M.LLL()
t2_ = M[0][1]
t3_ = M[0][2]

f2 = f2.subs({ t2: t2_ })
f3 = f3.subs({ t3: t3_ })
h1 = resultant(f2, f3, k)
d = h1.univariate_polynomial().roots()[0][0]

p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a = -3
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
E = EllipticCurve(GF(p), [a, b])
sharedkey = int(d)*E(*pubkey2)

key = long_to_bytes(int(sharedkey.xy()[0]))
cipher = AES.new(key, AES.MODE_CBC, iv)
pt = unpad(cipher.decrypt(ct), 16)
print(pt.decode())