Full solution for Baby Shark - OICC Qualifiers 2026

baby_shark_sol.py

from hashlib import sha256
from ecdsa import numbertheory
from fastecdsa import curve, ecdsa, keys
from sage.all import *

def msg_bytes(msg) -> bytes:
    if isinstance(msg, bytes):
        return msg
    elif isinstance(msg, str):
        return msg.encode()
    elif isinstance(msg, bytearray):
        return bytes(msg)

def recover_pubkey(r, s, msg):
    x = r
    e = int(sha256(msg_bytes(msg)).hexdigest(), 16)

    alpha = (pow(x, 3, p) + (a * x) + b) % p
    beta = numbertheory.square_root_mod_prime(alpha, p)
    y = beta if beta % 2 == 0 else p - beta

    # Compute the public key
    R1 = E(x, y)
    Q1 = pow(r, -1, n) * (s * R1 + (-e % n) * G)
    Pk1 = Q1

    # And the second solution
    R2 = E(x, -y)
    Q2 = pow(r, -1, n) * (s * R2 + (-e % n) * G)
    Pk2 = Q2

    return [Pk1, Pk2]

rses = [
    (
        317592827845276701472542781438267341993905486683854202514430757786256476671055,
        319439144266910876528216114805506754869023289531684705780545356292940752812048,
    ),
    (
        301445425113375294531479528737467515569036902461529371207581232088733240402283,
        40145234516922532151180947807207946759942404574914809929625632437698521476476,
    ),
]

msgs = ["Baby shark", "Doo doo doo doo doo doo"]

p = (3 << 256) - (3 << 128) + 1
a = 0
b = 22
gx = 3
gy = 7
n = p
h = 1

E = EllipticCurve(GF(p), [a, b])
G = E(gx, gy)

pubkey = None
potentials = []
for i in range(2):
    potentials.append(recover_pubkey(rses[i][0], rses[i][1], msgs[i]))
for key in potentials[0]:
    if key in potentials[1]:
        pubkey = key


def lift(P, E, p):
    # lift point P from old curve to a new curve
    Px, Py = map(ZZ, P.xy())
    for point in E.lift_x(Px, all=True):
        # take the matching one of the 2 points corresponding to this x on the p-adic curve
        _, y = map(ZZ, point.xy())
        if y % p == Py:
            return point


P = pubkey
E_adic = EllipticCurve(Qp(p), [a + p * 13, b + p * 37])
newG = p * lift(G, E_adic, p)
newP = p * lift(P, E_adic, p)

# Calculate discrete log
Gx, Gy = newG.xy()
Px, Py = newP.xy()
d = int(GF(p)((Px / Py) / (Gx / Gy)))
assert pubkey == d * G

z1 = int(sha256(msg_bytes(msgs[0])).hexdigest(), 16)
z2 = int(sha256(msg_bytes(msgs[1])).hexdigest(), 16)

r = -(z1 + z2) * pow(2 * d, -1, p) % p
R = E.lift_x(r)
Rx, Ry = (p * lift(R, E_adic, p)).xy()
k1 = ZZ(-(Rx / Ry) / -(Gx / Gy)) % p

r1 = (k1 * G).xy()[0] % p
s = pow(k1, -1, p) * (z1 + r1 * d) % p

print("(" + str(r1) + ", " + str(s) + ")")