secp.cairo

func ecdsa_raw_recover{range_check_ptr}(
        msg_hash : BigInt3, v : felt, r : BigInt3, s : BigInt3) -> (res : EcPoint):
    alloc_locals

    let gen_pt = EcPoint(
        BigInt3(0xe28d959f2815b16f81798, 0xa573a1c2c1c0a6ff36cb7, 0x79be667ef9dcbbac55a06),
        BigInt3(0x554199c47d08ffb10d4b8, 0x2ff0384422a3f45ed1229a, 0x483ada7726a3c4655da4f))

    # Compute y-coordinate of R
    %{
        from starkware.cairo.common.cairo_secp.secp_utils import pack
        from starkware.python.math_utils import sqrt
        P = 2**256 - 4294968273
        r = pack(ids.r, PRIME)
        R_y = sqrt(r**3 + 7, P)
        value = R_y = R_y if ids.v == 27 else -R_y
    %}
    let (R_y : BigInt3) = nondet_bigint3()

    # TODO: Check soundness
    #let (r_squared) = reduced_sqr(r)
    #let (r_cubed) = reduced_mul(r, r_squared)
    #let (R_y_squared) = reduced_sqr(R_y)
    #verify_zero(
    #    UnreducedBigInt3(
    #    d0=r_cubed_.d0 - R_y_squared_.d0 - 7,
    #    d1=r_cubed_.d1 - R_y_squared_.d1,
    #    d2=r_cubed_.d2 - R_y_squared_.d2))

    # Compute r^{-1}
    let (r_inv) = mul_s_inv(BigInt3(d0=1, d1=0, d2=0), r)
    #%{
    #    N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
    #    value = r_inv = pow(r, N-2, N)
    #%}
    #let (r_inv : BigInt3) = nondet_bigint3()
    #let (r_r_inv) = reduced_mul_N(r, r_inv) # Multiply modulo N
    #verify_zero(UnreducedBigInt3(
    #    d0=r_r_inv.d0 - 1,
    #    d1=r_r_inv.d1,
    #    d2=r_r_inv.d2))

    let R = EcPoint(r, R_y)
    let (x_1) = ec_mul(R, s)
    let (x_2) = ec_mul(gen_pt, msg_hash)
    let (x_2_neg) = ec_mul(x_2, BigInt3(N0-1, N1, N2)) # Compute -x_2
    let (x) = ec_add(x_1, x_2_neg) 
    let (Q) = ec_mul(x, r_inv)

    return (res=Q)
end