elliptic curve small subgroup attack

small_subgroup_attack.sage

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
F = GF(p)
# E = EllipticCurve(F, [0,0,0,0,4]) # y^2 = x^3 + 4
E = EllipticCurve(F, (0, 4))
G = E(0x17F1D3A73197D7942695638C4FA9AC0FC3688C4F9774B905A14E3A3F171BAC586C55E83FF97A1AEFFB3AF00ADB22C6BB,
      0x08B3F481E3AAA0F1A09E30ED741D8AE4FCF5E095D5D00AF600DB18CB2C04B3EDD03CC744A2888AE40CAA232946C5E7E1)

r = 0x73EDA753299D7D483339D80809A1D80553BDA402FFFE5BFEFFFFFFFF00000001
cofactor = 0x396c8c005555e1568c00aaab0000aaab
print("cofactor:", factor(cofactor))

E.set_order(r * cofactor)

print("G:")
print("0x" + hex(G.x())[2:].zfill(96) + hex(G.y())[2:].zfill(96))

Fr = GF(r)

# order = r
# while True:
#     P = E.random_point()
#     Q = P * r
#     if not Q.is_zero():
#         if Q.order() < order:
#             print("Found small-subgroup point:")
#             order = Q.order()
#             print(Q)
#             print(f"New order: {hex(order)} ({factor(order)})")
#       #   break

Q = E(772702414606270888997538293093830770986795216668658989561603495682988321473440422108936719279769822036741481617153,
      2943931115976296910004855385285780707336853443322576281720331395559921853094696448284094198095652926659033956507880)
print("Q order:", factor(Q.order()))
R = Q * 10177 * 859267 * 52437899
print("R order:", factor(R.order()))

print("==========================")
print("\nSmaller curve")
E = EllipticCurve(GF(929), (0, 4))
order = E.order()
print(f"Curve order: {order} ({factor(order)})\n")

# print("Finding small-subgroup point...")
# point_order = order
# while True:
#     P = E.random_point()
#     if not P.is_zero():
#         if P.order() < point_order:
#             print("New point:", P)
#             point_order = P.order()
#             print(f"order: {point_order} ({factor(point_order)})\n")

P = E(868, 295)
factors = factor(P.order())
print("factors:", factors)
print(
    f"P * {factors[0][0]}: {P * factors[0][0]}, order: {(P * factors[0][0]).order()}", )
print(
    f"P * {factors[1][0]}: {P * factors[1][0]}, order: {(P * factors[1][0]).order()}", )