Rating:
# OSS Service (Easy) (crypto 100)
The task provides a [link](http://ctf.sharif.edu:8086/) where there is
a [file](OSS_Signature.pdf) with the description of
the Ong-Schnorr-Shamir (OSS) signature and the challenge,
which consists in a [known-plaintext attack](https://en.wikipedia.org/wiki/Known-plaintext_attack).
of the signature.
We are also provided a [verifier](verifier.py) to validate the signature.
So we have two equations, `x^2 + k*y^2 = m (mod n)` and `x'^2 + k*y'^2 = m' (mod n)`
where we know `x`, `y`, `x'`, `y'`, `m`, `m'`, `k` and `n`
and we need to generate valid `x''` and `y''` for `x''^2 + k*y''^2 = m * m' (mod n)`
In the 1984 paper _An Efficient Solution of the Congruence x^2 + k*y^2 = m (mod n)_,
Pollard and Schnorr explain that: `(x1^2 + k*y^1)(x^2 + k*y^2) (mod n)`
can be expressed as `X + k*Y (mod n)` where `X = x1*x2 + k* y1*y2 (mod n)`
and `Y = x1*y2 - y1*x2 (mod n)`.
So we just implement that:
```python
from verify import n, k, m1, x1, y1, m2, x2, y2, public, verify
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
x, y = mult(x1, y1, x2, y2, k)
print(verify(public, (m1 * m2) % n, (x, y)))
print('x: {}\ny: {}'.format(x, y))
```
and get the needed parameters:
```
> python solver.py
True
True
True
x: 3228192414578958851010842513154275809496752450843437198583166196901565071578144066800517210864829309956656172864622172889502523814134130877601254638400747755883616155295299435314390972047946113969350548381594633322779945307216665767237995638888452882989503186673207123359630734140939449837354851424900356484212983667331443801108560693455298625538140549843770730178132648956596007707374948190919655158210892858713252214782069457662864873988983041011930880072395421594443371267339482128681654521226571357238152202622389403367075320562466814355917951666554746996134626758309948472069549094989922908904448493268680406656
y: 518211291241825120181140993092343983770941887615321384844260199425792523199755041385119471907237849603159990373526771913427402452760004430627136113781638542767114113264285000466398106908417951520749203743404777034613190657137114341923476307793861309763818494314271906586789936425240207459021063361770273109412368272889165718779882091684440429454382783604840684421214437897887818039810429139216497093192387409059198251459001969178988926945417318424698086613437960638555659525583532581962406409400074841700047111118522735841781583725367240630089427247980009202413865204658013579671962256648081403159372023040686179602
```
Submitting the obtained parameters, we get the flag: `SharifCTF{aea9d91c12817a8f5a19b37ee9e1b1d6}`
