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 Creative Commons License by Alfredo Beaumont