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}'