duc21-powersign

from pwn import *

L, zz, m = 1024, 15, 3
def H(params, msg, u):
    K, m = params
    r, z = K.characteristic(), K.gens()[0]
    h = 0
    while msg > 0:
        h *= z
        h += msg % r
        msg //= r
    h += z*u
    for _ in range(m):
        h ^= r
    assert len(list(h)) != 0
    return int(h[0])
  
def sign(params, privkey, msg):
    p, q = privkey
    u = 1
    while True:
        c = H(params, msg, u) % (p*q)
        if legendre_symbol(c, p) == legendre_symbol(c, q) == 1:
            break
        u += 1
    xp = pow(c, (p+1)//4, p)
    xq = pow(c, (q+1)//4, q)
    x = crt([int(xp), int(xq)], [p, q])
    return x, u

s = remote("pwn-2021.duc.tf", 31912)
_ = s.recvline()
n = int(s.recvline().split()[1])
print(n)

r = next_prime(n)
F.<x> = PolynomialRing(GF(r))
K = F.quo(F.irreducible_element(zz))

R = Zmod(r^zz-1)
j = int(1/R(r)^m)

r, z = K.characteristic(), K.gens()[0]

ra = randint(1, n)

message = r^2*int(ra^2 % n) + 1
msg = message
h = 0
while msg > 0:
    h *= z
    h += msg % r
    msg //= r
hh = (h^j)
hh -= z*1
mm = int(sum(int(x)*int(r^i) for i,x in enumerate(list(hh)[::-1])))
c = H((K, m), mm, 1)

s.send(bytes(hex(mm).strip("0x") + "\n", "ascii"))
x = int(s.recvline().strip().split()[4])
u = int(s.recvline().strip().split()[1])

print("x =", x)
print("u =", u)
# should be 1 by assumption
if u == 1:
    c = H((K, m), mm, 1)

    print("Potential factors")
    p = gcd(x - ra, n)
    q = gcd(x + ra, n)
    
    if p < n and p > 1:
        q = n / p
    elif q < n and q > 1:
        p = n / q
    else:
        print("no cigar")
        s.close()
        raise
    
    print(p)
    print(q)
    
    new_message = int(s.recvline().strip().split()[2][2:], 16)
    print(new_message)
    x, u = sign((K, m), (p,q), new_message)
    print(x, u)
    s.send(bytes(str(x) + "\n", "ascii"))
    print(s.recvline())
    s.send(bytes(str(u) + "\n", "ascii"))
    print(s.recvline())
    print(s.recvline())
#s.close()