PoliCTF 2012 Crypto 500

Hensel and Gretel are looking for their new house, but the twisted seller who sold it to them decided to provide the coordinates to their new love nest only after ensuring that the couple is Smart enough to earn them.
Thus, the seller provides them with the following map and leaves Hensel and Gretel to their sorry fate.
Can you help Hensel and Gretel to reach their house providing them with the street number?
(submit the street number as a large decimal number,plain ASCII encoded so Hensel and Gretel won’t get mad trying to figure out where they should head to :) )

Map

Summary: ECDLP on anomalous curve

From picture we can quickly get Elliptic Curve parameters:

PrimeMod:
730750818665451459112596905638433048232067471723
 
Curve:
y ^ 2 = x^3 + 425706413842211054102700238164133538302169176474 * x +
            + 203362936548826936673264444982866339953265530166
 
Generator point:
(125270202464411072778547771568975423382990845665,
 440970603958123875213441435758390311809187352362)
 
Final point:
(296939092187233862778999244256460019221379646447,
 650021996391906816753000782344884033217784284632)

If you google curve parameters, you can quickly find it’s anomalous – it’s order is equal to p. Let’s check:

sage: p = 730750818665451459112596905638433048232067471723                                                                                                     
sage: E = EllipticCurve(GF(p),[425706413842211054102700238164133538302169176474,203362936548826936673264444982866339953265530166])
sage: order(E)
730750818665451459112596905638433048232067471723
sage: p
730750818665451459112596905638433048232067471723

Indeed! There are some papers on attacking anomalous curves. I think this one is very informative: Attacking the Elliptic Curve Discrete Logarithm Problem by Matthew Musson (pages 69-75) (thx to @kyprizel). There is an example there.

Here’s my script to implement the attack:

from sage.all import *
 
p = 730750818665451459112596905638433048232067471723
E = EllipticCurve(GF(p), [
        425706413842211054102700238164133538302169176474,
        203362936548826936673264444982866339953265530166
])
 
g = E(125270202464411072778547771568975423382990845665, 440970603958123875213441435758390311809187352362)
v = E(296939092187233862778999244256460019221379646447, 650021996391906816753000782344884033217784284632)
 
def hensel_lift(curve, p, point):
    A, B = map(long, (E.a4(), E.a6()))
    x, y = map(long, point.xy())
 
    fr = y**2 - (x**3 + A*x + B)
    t = (- fr / p) % p 
    t *= inverse_mod(2 * y, p)  # (y**2)' = 2 * y
    t %= p
    new_y = y + p * t
    return x, new_y
 
# lift points
x1, y1 = g.xy()
x2, y2 = v.xy()
if 0:
    # Hensel lift can preserve the curve
    x1, y1 = hensel_lift(E, p, g)
    x2, y2 = hensel_lift(E, p, v)
else:
    # we can calso lift by adding random multiple of p
    # just need to compute new curve
    x1 = int(x1)
    x2 = int(x2)
    y1 = int(y1)+p
    y2 = int(y2)+p
 
# calculate new A, B (actually, they will be the same here)
mod = p ** 2
 
A2 = y2**2 - y1**2 - (x2**3 - x1**3)
A2 = A2 * inverse_mod(x2 - x1, mod)
A2 %= mod
 
B2 = y1**2 - x1**3 - A2 * x1
B2 %= mod
 
# new curve
E2 = EllipticCurve(IntegerModRing(p**2), [A2, B2])
 
# calculate dlog
g2s = (p - 1) * E2(x1, y1)
v2s = (p - 1) * E2(x2, y2)
 
x1s, y1s = map(long, g2s.xy())
x2s, y2s = map(long, v2s.xy())
 
assert (x1s - x1) % p == 0
assert (x2s - x2) % p == 0
dx1 = (x1s - x1) / p
dx2 = (x2s - x2) / p
dy1 = (y1s - y1)
dy2 = (y2s - y2)
 
m = dy1 * inverse_mod(dx1, p) * dx2 * inverse_mod(dy2, p)
m %= p
 
print m
$ sage solve.py 
4242424280918329413309219711238286120942424242

The flag: 4242424280918329413309219711238286120942424242

Leave a Reply

Your email address will not be published.