OSS Service (Hard) (crypto 500)
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 + k*y^2 = m (mod n),
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.