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 :) )
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
