from Crypto.Util.number import getRandomNBitInteger, isPrime # extended gcd def egcd(a, b): old_x, new_x = 1, 0 old_y, new_y = 0, 1 while a != 0: q, a, b = b // a, b % a, a new_x, old_x = old_x, new_x - q * old_x new_y, old_y = old_y, new_y - q * old_y return b, new_x, new_y # multiplicative modular inverse def modinv(a, m): g, x, _ = egcd(a % m, m) if g != 1: return None return x % m # a class to represent a point on elliptic curve class ec_point: def __init__(self, x, y, z=1): self.x = x self.y = y self.z = z def __repr__(self): if self.z == 0: return "<ORIGIN>" return f"<x={self.x}, y={self.y}>" # a class to init an elliptic curve class ec_curve: def __init__(self, p, r, a, b): self.p = p self.r = r self.a = a self.b = b assert isPrime(p) and isPrime(r) def __repr__(self): return f"elliptic curve y^2 = x^3 + {self.a}*x + {self.b} of order {self.r} over GF({self.p})" def is_origin(self, pt): return pt.z == 0 # elliptic curve addition def add(self, pt1, pt2): if self.is_origin(pt1): return pt2 if self.is_origin(pt2): return pt1 if (pt1.y + pt2.y) % self.p == 0 and pt1.x == pt2.x: return self.origin() if pt1.x == pt2.x and pt1.y == pt2.y: temp = (((3 * pt1.x * pt1.x) + self.a) * modinv(2 * pt1.y, self.p)) % self.p else: temp = ((pt2.y - pt1.y) * modinv(pt2.x - pt1.x, self.p)) % self.p x = (temp * temp - pt1.x - pt2.x) % self.p y = (temp * (pt1.x - x) - pt1.y) % self.p return self(x, y) # multiplication using double and add def multiply(self, n, pt): if n == 0: return self.origin() curr_mult = pt res = self.origin() while n > 0: if n & 1: res = self.add(res, curr_mult) curr_mult = self.add(curr_mult, curr_mult) n = n >> 1 return res # init a point on this curve # Usage: # curve = ec_curve(*params) # point = curve_name(x, y[, z]) def __call__(self, x, y, z=1): res = ec_point(x % self.p, y % self.p, z) return res @staticmethod def origin(): return ec_point(0, 1, 0) if __name__ == "__main__": p = 115792089210356248762697446949407573530086143415290314195533631308867097853951 r = 115792089210356248762697446949407573529996955224135760342422259061068512044369 a = 115792089210356248762697446949407573530086143415290314195533631308867097853948 b = 41058363725152142129326129780047268409114441015993725554835256314039467401291 curve = ec_curve(p=p, r=r, a=a, b=b) print(curve) multiplier = getRandomNBitInteger(250) print("Because I am soo confident, I'll even let you make multiple public keys") print("Send points to multiply, or send <0,0> to move on:") try: for _ in range(10): x = int(input(">>> x coord => ")) y = int(input(">>> y coord => ")) if x == 0 and y == 0: break print(curve.multiply(multiplier, curve(x, y))) guess = int(input("multiplier => ")) if guess == multiplier: print(open("flag.txt", "r").read()) else: print("Never gonna give you up") except: print("Never gonna let you down")
EllipticCurveを独自していたら疑うべきはInvalid Curve Attack
ということで InvalidCurveAttackやるだけ
ただしなんか失敗する↓
# p = 115792089210356248762697446949407573530086143415290314195533631308867097853951 # # r = 115792089210356248762697446949407573529996955224135760342422259061068512044369 # a = 115792089210356248762697446949407573530086143415290314195533631308867097853948 # # b = 41058363725152142129326129780047268409114441015993725554835256314039467401291 p = random_prime(1 << 200) a = randint(0, p) L = 100000 X = 2**10 Y = 2**15 curves = [] used_factors = set() for b in range(10000): try: alarm(5) EC = EllipticCurve(GF(p), [a, b]) order = EC.order() factors = factor(order, limit=L) cancel_alarm() except (AlarmInterrupt): continue x = prod([f for f, _ in factors if f < L and f not in used_factors]) if Y > x > X: print(x) G = EC.random_point() P = (order // x) * G curves.append(( b, x, P.xy(), )) for f, _ in factors: used_factors.add(f) if len(curves) >= 10: break print(curves) d = randint(0, p) points = [] ds = [] modulus = [] for i in range(len(curves)): print(i) b, order, (x, y) = curves[i] EC = EllipticCurve(GF(p), [a, b]) P = EC(x,y) Q = d * P dd = P.discrete_log(Q) points.append((P, Q)) ds.append(dd) modulus.append(order) for i in range(2**10): dds = [d if ((i >> j) & 1) == 0 else -d % modulus[j] for j, d in enumerate(ds)] try: dx = CRT_list(dds, modulus) for j in range(10): P = points[j][0] Q = points[j][1] assert dx * P == Q print(dx) except (ValueError, AssertionError): pass print(d) # zs = [] # ms = [] # factors = factor(order, limit=L) # factors= [p**e for p, e in factors if p < L] # for f in factors: # Pi = (order // f) * P # Qi = (order // f) * Q # z = Pi.discrete_log(Qi) # zs.append(z) # ms.append(f) # dd = CRT_list(zs, ms) # ds.append(dd) # os.append
from ptrlib import Socket params = [(0, 115792089210356248762697446949407573530086143415290314195533631308867097853952, (94221425137494848354317683743579139117998767969631342334762324923935819622856, 21784820764097404034344283507442832401728106769975052421274503177825898604358)), (1, 115792089210356248762697446949407573529578712231346505346655645343696123459399, (40331453749798362648663787985623261433456835683935416825395738513146648313031, 95667740768585298077767978320104122113750733811010113321227658194150363286443)), (6, 115792089210356248762697446949407573530340799317467530668592248339896581177420, (11148253708499394365428414747687742778442232568803356365071467940156567103728, 28189714283887589485277221734376718356803766901104218815846759647244282574595)), (9, 115792089210356248762697446949407573530163879961279855411837001182999286566116, (94933847939256946054129521029532375763728497886034931040582568364112955451169, 46365329434255256231123689068392336461695851466774643536016878827225294086361)), (12, 115792089210356248762697446949407573530699579586905262219465699816639947608325, (27667241307257752959919731522674512648497224272812873768926610938473922672623, 39904219669702034082787797288580837076653098600306576358800966100682522346700)), (38, 115792089210356248762697446949407573529682635014837957215254038647769424497808, (31497047233414732533736140286477492946435758160419419714970434335362847196506, 2696512586129195065108550066604286223725671052002493690789746782471294227468)), (39, 115792089210356248762697446949407573529877514543602365144288105139307540173051, (109191598546602334679498912431860031164614828982105358606287993072322289346879, 33448304389715918822292738211623655329631666104484355735801264203594629876303)), (76, 115792089210356248762697446949407573530614242591588133746001882673826528014192, (54737346359762671496587108501844480682830235674512011248457548997621366152569, 32071816028300156643946257750920617755893693601354905632771437570469357492777)), (91, 115792089210356248762697446949407573530031069619938078367690973570893419659520, (45266471300780905801694624544594462233484639342889940909166747749227956271326, 12915988871264489174259490182203225084590936589886421736734855142478583925017)), (92, 115792089210356248762697446949407573529855040961872541806737649499571504696312, (55637609510829952393043877496464283165436970574766063896495170577818372920060, 112355085474761323298860567393998747428181899351536004684767255218152978598186))] p = 115792089210356248762697446949407573530086143415290314195533631308867097853951 a = 115792089210356248762697446949407573530086143415290314195533631308867097853948 F = GF(p) r = 115792089210356248762697446949407573529996955224135760342422259061068512044369 sock = Socket("nc 34.121.95.29 1337") ds = [] os = [] for i in range(1, 10): print("{}/10".format(i+1)) b, order, (x, y) = params[i] EC = EllipticCurve(F, [a, b]) sock.sendlineafter("x coord => ", str(x)) sock.sendlineafter("y coord => ", str(y)) qx, qy = [int(v) for v in sock.recvregex(r"x=(\d+), y=(\d+)")] P = EC(( x, y )) Q = EC(( qx, qy )) L = 500000 factors = factor(order, limit=L) factors= [p**e for p, e in factors if p < L] zs = [] ms = [] for f in factors: Pi = (order // f) * P Qi = (order // f) * Q z = Pi.discrete_log(Qi) zs.append(z) ms.append(f) d = CRT_list(zs, ms) print(d) try: x = CRT_list(ds + [d], os + [order]) print(x) ds.append(Integer(d)) os.append(Integer(order)) except ValueError: pass x = CRT_list(ds, os) % r print("x = {}".format(x)) sock.sendlineafter("multiplier => ", str(x)) sock.interactive()
