OSS Service (Hard) (crypto 500)
Tagged as en, crypto, ctf, sharif, writeup, math
Written on 2018-02-04
The task provides a link (and a mirror).
As in a previous easy task, we are asked to provide a valid OSS signature on a given message. The difference is that we don't have any plaintext/ciphertext pair here to use (so no known-plaintext attack in this case.)
The OSS scheme is a cryptosystem proposed by Ong, Schnorr and Shamir
in the 1984 paper An Efficient Signature Scheme Based on Quadratic Equations,
based on the difficulty of solving equations of the kind ¡x^2 + ky^2 -= m mod n¡,
where n = p*q, m is the message and k is the public key.
In the 1984 paper An Efficient Solution of the Congruence x^2 + k*y^2 = m (mod n), Pollard and Schnorr describes an algorithm to efficiently forge valid signatures in the OSS scheme.
An explanation of both the scheme and the algorithm can also be found here.
To solve this task we need to implement this algorithm:
def mult(x1, y1, x2, y2, k):
"""(x1^2 + ky^1)(x^2 + ky^2)"""
return (x1 * x2 + k*y1*y2) % n, (x1 * y2 - y1 * x2) % n
def pollard(k, m):
# Generate a valid prime m0 < m and x0
while True:
while True:
u = randrange(n)
v = randrange(n)
m0 = m*(u*u+k*v*v)%n
if m0 % 4 == 3: break
x0 = pow(-k, (m0 + 1)/4, m0)
if pow(x0, 2, m0) == -k % m0:
break
xx = [0,Integer(x0)]
mm = [0,m0]
# Generate the series x_i, m_i, till m_I
while not (xx[-2] <= mm[-1] <= mm[-2]):
mm.append((xx[-1] * xx[-1] + k) / mm[-1] % n)
xx.append(min(xx[-1] % mm[-1], (mm[-1] - xx[-1]) % mm[-1]) % n)
# Multiply all the equations to get s0, t0
s, t = xx[1], 1
for x in xx[2:-1]:
s, t = s * x-k * t, s + x*t
# Get s1, t1 from s0, t0
M = mul(mm[2:]) % n
s1 = s * inverse_mod(M, n) % n
t1 = t * inverse_mod(M, n) % n
# Get s2, t2 either trivially or recursivelly
if is_square(mm[-1]):
s2, t2 = sqrt(mm[-1]), 0
elif mm[-1] == k:
s2, t2 = 0, 1
else:
# Change variables and solve recursively
s22, t22 = pollard(Integer(-mm[-1]), -k)
# Change variables back
t2 = inverse_mod(t22, n)
s2 = s22 * t2
# Get s4, t4 multiplying previous solutions
s3, t3 = mult(u, v, s1, t1, k)
s4, t4 = mult(s3, t3, s2, t2, k)
# Obtain the solution to the original problem
m0inv = inverse_mod(Integer(m0), n)
return s4 * m * m0inv % n, t4 * m * m0inv % n
n = 108504503412454373447900779392896455789182908920252767679102572784833248190682207737154598741166656146295499891768592408962529857168166275863130804227243036676846199142906617137007877378696363607314850559328607693669984310189715960464177540321389050644453028598966277046571994650300388605135199566812211180551
k = 96418402323876864512491639972930583881318685814783562179751981420110811774390896080021079024657494752001051891183358590923934531389848653055409236592228196204683162829359099715583891741617111941684481041179057606706801620321693724317614343290846702947941240579335556736392623484157714059707148044213280632330
m = 9045418907335068770268779849124564950219260545189341826614770092040336019517687130751801431148236418688112027601673969058529643735762961447504773552645699712014099935774980274016297241177481291819364059206708658744657881196289540965565219550846730216720833999741328972855594202081834339846728109
x, y = pollard(k, m)
print "x: {}\ny: {}".format(x, y)
We run it and get the solution:
> sage solver.sage
x: 63529753037555481965244240104691579686392772673138938065103394856530784845394743428903187478097312384543963104438879065037978748707698498113362141669721393568828502881982856333309982914482481662067028113639848300092073241270357323990241939477115325790712729055169284516564246412118823260609799738306684831760
y: 74805395127516819966704889276362136024857356851501240398398980500143494513618966041174091066259991598046113332187073518661925429346683018250229451111296702693871856911648077711968545214215767245149082303579904010415922455467218345679407157611674377154762184397511303797003665476864511934951139156102616514906
We add it to the provide verifier:
def verify(public, m, sigma):
n = public[0]
k = public[1]
x = sigma[0]
y = sigma[1]
return (x**2 + k*y**2 - m) % n == 0
# public key
n = 108504503412454373447900779392896455789182908920252767679102572784833248190682207737154598741166656146295499891768592408962529857168166275863130804227243036676846199142906617137007877378696363607314850559328607693669984310189715960464177540321389050644453028598966277046571994650300388605135199566812211180551
k = 96418402323876864512491639972930583881318685814783562179751981420110811774390896080021079024657494752001051891183358590923934531389848653055409236592228196204683162829359099715583891741617111941684481041179057606706801620321693724317614343290846702947941240579335556736392623484157714059707148044213280632330
public = (n, k)
# message
m = 9045418907335068770268779849124564950219260545189341826614770092040336019517687130751801431148236418688112027601673969058529643735762961447504773552645699712014099935774980274016297241177481291819364059206708658744657881196289540965565219550846730216720833999741328972855594202081834339846728109
s1 = 63529753037555481965244240104691579686392772673138938065103394856530784845394743428903187478097312384543963104438879065037978748707698498113362141669721393568828502881982856333309982914482481662067028113639848300092073241270357323990241939477115325790712729055169284516564246412118823260609799738306684831760
s2 = 74805395127516819966704889276362136024857356851501240398398980500143494513618966041174091066259991598046113332187073518661925429346683018250229451111296702693871856911648077711968545214215767245149082303579904010415922455467218345679407157611674377154762184397511303797003665476864511934951139156102616514906
print(verify(public, m, (s1, s2)))
and check that it's valid:
> python verify.py
True
Submitting the values, we get the flag: SharifCTF{f5b773a1bd527761a26aaee333d62d3c}
You can get the files at github.
Unless otherwise credited all material 
by Alfredo Beaumont 