# 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

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