Tags: p-adics crypto discrete-log smarts-attack elliptic-curve
Rating:
The challenge asks to do discrete log on elliptic curve over $Q_p$. Similar to $Z_{P^n}$, I guess the order of the curve is $kp^7$, where $k$ is the order of the curve over something like $Z_p$. So I use some small primes to find the $k$ and surpringly find that $k\in \\{p-1,p,p+1\\}$ (I don't know why). And the idea of Smart Attack is to lift $F_p$ to $Q_p$, it is reasonable to guess Smart Attack works here for the $p^7$ part. So I find a prime such that $p+1$ and $p-1$ are smooth.
In fact, even the $p^7$ part is enough to pass the challenge because the secret is $2^{1600}$, but $p$ is only required to larger than $2^{200}$.
```python
#!/usr/bin/env sage
from flag import flag
from pwn import *
import secrets
import sys, os
from base64 import b64encode, b64decode
from tqdm import trange
from sage.misc.persist import SagePickler, SageUnpickler
QUERY_NUM = 250
PREC = 8
PRIME_BITS = 200
# p = int(input("Send your prime: "))
# p = 2606427573325551742423779721798571211719097220082369699679901
p = 344360697810972986109972173343700822544940495675251456359287217
factors0 = (p+1).factor(algorithm='qsieve')
factors1 = (p-1).factor(algorithm='qsieve')
raw_p = ZZ(p)
assert p.bit_length() >= PRIME_BITS and is_prime(p)
k = Qp(p,PREC)
R = k.integer_ring()
p = k(p)
k3 = Qp(p,3)
def sage_encode(obj):
return b64encode(SagePickler.dumps(obj)).decode('ascii')
def sage_decode(s):
return SageUnpickler.loads(b64decode(s.encode('ascii')))
def smart_attack(ec, G, Q, n):
GX, GY = (G*(raw_p**(n-1))).xy()
PX, PY = (Q*(raw_p**(n-1))).xy()
l = ZZ((PX / PY)/(GX / GY))%raw_p
for i in range(1, n):
Pi = Q - l*G
if Pi.is_zero():
break
PX, PY = (Pi*(raw_p**(n-i-1))).xy()
GX, GY = (G*(raw_p**(n-i-1))).xy()
l0 = ZZ((PX / PY)/(GX / GY))%(raw_p**(i+1))
l = l0 + l
# assert (Q-l*G).is_zero()
return l
def solve_ecdlp(ec, P, Q, secret=None):
T = P*(raw_p**7)
O = T*raw_p*(raw_p**2-1)
# print(T*(raw_p-1))
# print(T*raw_p)
# print(T*(raw_p+1))
if (T*(raw_p)).is_zero():
print("type 1")
return smart_attack(ec, P, Q, 8)
if (T*(raw_p+1)).is_zero():
print("type 2")
ord = (raw_p**7*(raw_p+1))
lp = smart_attack(ec, P*(raw_p+1), Q*(raw_p+1), 7)
mods = [(lp, raw_p**7)]
ec3 = EllipticCurve(k3, [k3(a) for a in ec.a_invariants()])
P = ec3(P)
Q = ec3(Q)
for fac, deg in factors0:
PP = P*(ord//fac)
QQ = Q*(ord//fac)
r = discrete_log(QQ, PP, operation='+', ord=fac)
# assert QQ == r*PP
mods.append((r, fac))
rs, ms = zip(*mods)
rs = list(rs)
ms = list(ms)
l = crt(rs, ms)
return l
if (T*(raw_p-1)).is_zero():
print("type 0")
ord = (raw_p**7*(raw_p-1))
lp = smart_attack(ec, P*(raw_p-1), Q*(raw_p-1), 7)
mods = [(lp, raw_p**7)]
ec3 = EllipticCurve(k3, [k3(a) for a in ec.a_invariants()])
P = ec3(P)
Q = ec3(Q)
for fac, deg in factors1:
uu = fac ** deg
PP = P*(ord//uu)
if (P*(ord//fac)).is_zero():
continue
QQ = Q*(ord//uu)
r = discrete_log(QQ, PP, operation='+', ord=uu)
# assert QQ == r*PP
mods.append((r, uu))
if prod(list(zip(*mods))[1]).bit_length() > 1602:
break
rs, ms = zip(*mods)
rs = list(rs)
ms = list(ms)
l = crt(rs, ms)
return l
def solve(ec_str, P_str, Q_str, secret):
ec = sage_decode(ec_str)
P = sage_decode(P_str)
Q = sage_decode(Q_str)
return solve_ecdlp(ec, P, Q, secret)
def online():
# nc 34.146.145.253 16180
io = remote('34.146.145.253', 16180)
io.recvuntil(b"Submit the token generated by")
cmd = io.recvline().decode().split("`")[1]
print(cmd)
pow = process(cmd, shell=True)
pow.recvuntil(b"hashcash token: ")
ret = pow.recvline().strip()
print(ret)
io.sendline(ret)
io.recvuntil(b"Send your prime:")
io.sendline(str(raw_p).encode())
for i in trange(QUERY_NUM):
print(i)
ec = sage_decode(io.recvline().strip().decode())
P = sage_decode(io.recvline().strip().decode())
Q = sage_decode(io.recvline().strip().decode())
ans = solve_ecdlp(ec, P, Q)
# assert Q == ans*P
print(ans)
io.recvuntil(b"Send your answer:")
io.sendline(str(ans).encode())
io.interactive()
cnt = [0,0,0]
def offline():
for i in range(QUERY_NUM):
print(i)
while True:
try:
j = k.random_element()
j *= p**(-j.valuation()+secrets.choice([-3,-2,-2]))
ec = EllipticCurve_from_j(j)
break
except ArithmeticError:
pass
while True:
try:
g = k.random_element()
P = ec.lift_x(g**2)
secret = secrets.randbelow(int(2**(PRIME_BITS*PREC)))
# secret = 12314659852525460146474879879665924587545887942531695352950199944792921598773177699787932568721563973358936830584609429884978133833934213410600630993215639733589368305846094298849781338339342134106006304999312435089182411208918241453467215639733589368305846094298849781338339342134106006309931208918241890265782943
Q = secret*P
break
except ValueError:
pass
# print(sage_encode(ec))
# print(sage_encode(P))
# print(sage_encode(Q))
import time
start = time.time()
ans = solve(sage_encode(ec), sage_encode(P), sage_encode(Q), secret)
print("time cost:", time.time()-start)
# if (P*(raw_p**8)).is_zero():
# cnt[1] += 1
# elif (P*(raw_p**7)*(raw_p+1)).is_zero():
# cnt[2] += 1
# elif (P*(raw_p**7)*(raw_p-1)).is_zero():
# cnt[0] += 1
# else:
# print("error")
# sys.exit(1)
# continue
# ans = int(input("Send your answer: "))
if ans*P != Q:
print("Wrong answer, bye...")
sys.exit(1)
online()
# offline()
```
