Get generator order easily! #7

New Issue

2023-05-27T22:27:28+02:00

CONIGUERO commented

2023-05-27 22:27:28 +02:00

(Migrated from github.com)

Here's a SageMath script to get the ECDLP solver ready (not mine, all credit goes to sk00ter)

#!/usr/bin/env sage
import sys

def warnx(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

with open(sys.argv[1], 'rb') as f:
    bink = f.read()[4:] # skip res ID

    def btoi(bb):
        n = 0
        for b in reversed(bb): # little-endian
            n = n << 8
            n |= b
        return n

    offs = 4 * int.from_bytes(bink[0x04:0x08], 'little') # offset to curve params in words
    nb = 4 * int.from_bytes(bink[0x10:0x14], 'little') # size of curve params in words
    pkScalarBits = int.from_bytes(bink[0x18:0x1c], 'little')
    warnx("pkScalarBits = %d" % pkScalarBits)
    p = btoi(bink[offs:offs+nb])
    warnx("offs = %d, nb = %d, p = %x" % (offs, nb, p))
    F = GF(p)
    a = F(btoi(bink[offs+nb:offs+2*nb]))
    b = F(btoi(bink[offs+2*nb:offs+3*nb]))
    Bx = F(btoi(bink[offs+3*nb:offs+4*nb]))
    By = F(btoi(bink[offs+4*nb:offs+5*nb]))
    Kx = F(btoi(bink[offs+5*nb:offs+6*nb]))
    Ky = F(btoi(bink[offs+6*nb:offs+7*nb]))

E = EllipticCurve(F, [0, 0, 0, a, b])
warnx(E)
B = E(Bx, By)
K = E(Kx, Ky)

# If we get here, we know B and K are on the curve.
# Now get the order of the curve and then factorize it.

n = E.order()
warnx("n = %d, now factoring..." % n)
# Find L by just trying if any of the factors in f yield the point at infinity
factors = []
def rfactor(m):
    digits = len('%d' % (2^pkScalarBits - 1))
    ff = ecm.find_factor(m, factor_digits=digits) # Try to find a good candidate
    for f in ff:
        if f > 2 and f.is_prime() and not f * B:
            warnx("ok for %d" % f)
            return True, [f]
    else:
        warnx("bad run: %s" % ff)
        return False, ff

ok, values = rfactor(n)
while not ok:
    for value in values:
        ok, nl = rfactor(value)
        if ok:
            L = nl[0]
            break
        values.extend(nl)

factors = [n // L, L]
warnx(factors)
warnx("Reduce the result of ECDLP Solver modulo %d" % L)

warnx("\n\njob input:\n\n")
print("GF := GF(%d);" % p)
print("E := EllipticCurve([GF|%d,%d]);" % (a, b))
print("G := E![%d,%d];" % (Bx, By))
print("K := E![%d,%d];" % (Kx, Ky))
print("/*")
print("FactorCount:=%d;" % len(factors))
for f in factors:
    print("%d;" % f)
print("*/")

Here's a SageMath script to get the ECDLP solver ready (not mine, all credit goes to sk00ter) ```python #!/usr/bin/env sage import sys def warnx(*args, **kwargs): print(*args, file=sys.stderr, **kwargs) with open(sys.argv[1], 'rb') as f: bink = f.read()[4:] # skip res ID def btoi(bb): n = 0 for b in reversed(bb): # little-endian n = n << 8 n |= b return n offs = 4 * int.from_bytes(bink[0x04:0x08], 'little') # offset to curve params in words nb = 4 * int.from_bytes(bink[0x10:0x14], 'little') # size of curve params in words pkScalarBits = int.from_bytes(bink[0x18:0x1c], 'little') warnx("pkScalarBits = %d" % pkScalarBits) p = btoi(bink[offs:offs+nb]) warnx("offs = %d, nb = %d, p = %x" % (offs, nb, p)) F = GF(p) a = F(btoi(bink[offs+nb:offs+2*nb])) b = F(btoi(bink[offs+2*nb:offs+3*nb])) Bx = F(btoi(bink[offs+3*nb:offs+4*nb])) By = F(btoi(bink[offs+4*nb:offs+5*nb])) Kx = F(btoi(bink[offs+5*nb:offs+6*nb])) Ky = F(btoi(bink[offs+6*nb:offs+7*nb])) E = EllipticCurve(F, [0, 0, 0, a, b]) warnx(E) B = E(Bx, By) K = E(Kx, Ky) # If we get here, we know B and K are on the curve. # Now get the order of the curve and then factorize it. n = E.order() warnx("n = %d, now factoring..." % n) # Find L by just trying if any of the factors in f yield the point at infinity factors = [] def rfactor(m): digits = len('%d' % (2^pkScalarBits - 1)) ff = ecm.find_factor(m, factor_digits=digits) # Try to find a good candidate for f in ff: if f > 2 and f.is_prime() and not f * B: warnx("ok for %d" % f) return True, [f] else: warnx("bad run: %s" % ff) return False, ff ok, values = rfactor(n) while not ok: for value in values: ok, nl = rfactor(value) if ok: L = nl[0] break values.extend(nl) factors = [n // L, L] warnx(factors) warnx("Reduce the result of ECDLP Solver modulo %d" % L) warnx("\n\njob input:\n\n") print("GF := GF(%d);" % p) print("E := EllipticCurve([GF|%d,%d]);" % (a, b)) print("G := E![%d,%d];" % (Bx, By)) print("K := E![%d,%d];" % (Kx, Ky)) print("/*") print("FactorCount:=%d;" % len(factors)) for f in factors: print("%d;" % f) print("*/") ```

CONIGUERO commented

2023-05-27 23:39:58 +02:00

(Migrated from github.com)

Nevermind. This just sets up the ECDLP solver, it doesn't output the order.

Endermanch commented

2023-05-28 17:56:00 +02:00

(Migrated from github.com)

Useful nonetheless. Noted

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: endermanch/XPKeygen#7