duksctf

Bunch of sec. enthusiasts who sometimes play CTF

BlackAlps 2019 - Schnorr

Schnorr signature with a Blum-Blum-Schub PRNG to generate the nonce. Since the quadratic equation can be solved in the prime group the private key can be recover from two consecutive signatures.

Description

An apprentice cryptographer decided to implement the Schnorr signature based on what he could read on Wikipedia.

Knowing that randomness is a critical component of Schnorr signatures, he decided to use and improve the Blum-Blum-Schub provably secure PRNG to generate randomness for signing.

You are given two consecutive signatures. The flag is hidden inside the secret key.

Author: Alexandre Duc

Details

Points: 400

Category: Crypto

Solution

The PRNG was given:

#PRNG initially based on the provably secure BlumBlumShub PRNG. 
#Improved to make it even more secure and more efficient. 
#q is reused from Schnorr. It does not affect the security of the system
#r has to be a random prime number for the security proof to hold. 
def BlumBlumShub(seed, r, q):
    n = r*q
    return (pow(seed,2,n) + 2041*seed + 125)%n

As well as the parameters and two signatures:

p=11354821474068432448781088658925769089942262052492176911159145294614070565823651286293031376249291592372010121532367277047783330177517525191691692679609588994273170102573923175498072488475243086164453824784015024965831927574606549505482453151194968443619022898128537270653908101799461877175223151865737017706606910794098282193587012221895574003056105395032884664491604314170070549892345496174749893404409800494766306880932092622764671423653474372374467519485884622586290396130747886745583378206131995694632733623421886624382843330228686054793
q=572156407871896365511901114975216570393314889392720208096942688507966755120286519809169097
g=5574030578425995852347018776949350647797404891144700535846063285373847243050742195266604928099650295829841450171685065963427241819806737053177918304931329744526999213038118857349881673298873935654535365004383047860588199904864368957698991553618480203079249307017153046037144903664337773520632103167869602394350824178446678871690039864957571252278888675700929967210478372731269855538550660019512864773991864726863377657430184373137242042827800857538306846685368056656766635813056158480078121733190110412456091152108340586732091202814832395649
y=1302064652106120540591455669744918598912180127945547332820568085657757915418891353546741658531571543834359096864837598318932353117841399047530357264868697967684828173623493749674820397778180334312186802162498484373499213589669465086073572034808055890600153754294513520414147214915277791982218242108282472595977447873259754267985756686859151211332253888240703732797016283234944506058880767221813931135334602116033266358897129058776480192951940507572840153150631029293192856658960098994428668986190899631093861500235157282362462737614975550203

(s1,e1) = (444490141183918605123295561253971131255085954584610229585367281139870776740150637047636091, 102110058127261311389659710844857123602442947476844523271866378317865779717941)

(s2,e2) = (196039357254500202482847472390602792559927913500085718055042604432787316443058365700890688, 101276696144102062023436237077674567981954023536843878958158437487050712337249)

From the definition of Schnorr algorithm we have:

\[s_1=k_1-x e_1\] \[s_2=k_2-x e_2\]

Where $x$ is the private key and $k_1$ and $k_2$ the nonces. Since the nonces are generetated from the Blum-Blum-Schub PRNG we have that:

\[k_2 = k_1^2 + 2041 k_1 + 125\]

Thus if we replace properly in the previous equations we have:

\[k_1 = s_1 + x e_1\] \[s_2 = k_1^2 + 2041 k_1 + 125 - x e_2 = (s_1 + x e_1)^2 + 2041 (s_1 + x e_1) + 125 - x e_2\]

Since it is a quadratic equation and we know everything except $x$, we can solve it with sage:

sage: K = GF(q)
sage: P = PolynomialRing(K)
sage: x = P.gen()
sage: f = (s1+x*e1)^2 + 2041*(s1+x*e1)+125-x*e2-s2
sage: s = f.roots()

One of the solutions is the private key and the flag is the private key.

sage: unhexlify("{0:x}".format(int(s[1][0])))
'BA19{Schn0rr1sL1keECDSA}'
Written on November 8, 2019