Aegis招新题-crypto-writeup

发表于2022-04-10更新于2022-04-10

Aegis招新题-crypto-writeup

Ccc

Kinoko的代码 I

源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from math import sqrt

def is_prime(n):
    if n < 2:
        return False
    for i in range(3, int(sqrt(n+1)+1), 2):
        if n % i == 0:
            return False
    return True


def next_prime(n):
    while True:
        if is_prime(n):
            print(n)
            return n
        n += 2


seed = 0x5eed
for i in range(64):
    seed <<= 16
    seed += 1
    seed = next_prime(seed)
print("Flag is Aegis{%s}" % (hex(seed)[-32:]))

读完代码后发现是让改进素数判别函数，降低时间复杂度，直接将原函数注释掉，调用gmpy2的is_prime函数即可（偷懒了，题目应该是想考察Miller-Rabin素性检测算法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from gmpy2 import is_prime


def next_prime(n):
    while True:
        if is_prime(n):
            print(n)
            return n
        n += 2


seed = 0x5eed
for i in range(64):
    seed <<= 16
    seed += 1
    seed = next_prime(seed)
print("Flag is Aegis{%s}" % (hex(seed)[-32:]))

Kinoko的代码 II

源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def phi(n):
	if n <= 1:
		return n
	for i in range(2, n + 1):
		if n % i == 0:
			ans = 1
			while n % i == 0:
				n //= i
				ans *= i
			ans //= i
			ans *= i - 1
			return ans * phi(n)


def common(x, y):
	if x > y:
		x, y = y, x
	i = 2
	ans = 1
	while i <= x:
		while x % i == 0 and y % i == 0:
			x //= i
			y //= i
			ans *= i
		i += 1
	return ans


def check(i, n):
	for j in range(1, phi(n)):
		if pow(i, j, n) == 1:
			return False
	return True


n = 67108934
total = 0
for i in range(n):
	if pow(i, phi(n), n) == 1 and common(i, n) == 1 and check(i, n):
		print(i)
		total += i

print ("Flag is Aegis{%d}" % (total))

首先分析代码：

1
2
3
phi(n)# 计算n的欧拉函数值
common(x, y)# 计算x, y的最大公因数
check(i, n)# 判断i是否是n的原根

分析完代码可以知道题目是让求$n = 67108934$的所有原根的和

这里需要用到原根的数学知识

最小原根是不大于 $\sqrt[4]{m}$ 级别的。

因此，不妨枚举$ [1, \sqrt[4]{m}] $的整数，得到最小原根 g。

再枚举 $g^s$ 的指数 $s$，若 $s$ 与 $φ(m)$ 互质，则$g^smodm$ 为一个原根。

由此可知，如果数 $m$ 存在原根，则原根的个数为 φ(φ(m))

首先枚举求得n最小的原根为7

然后遍历求和即可

1
2
3
4
5
6
7
8
9
from math import gcd

n = 67108934
total = 0
phin = 33554466
for i in range(1, phin):
    if gcd(i, phin) == 1:
        total += pow(7, i, n)
print("Flag is Aegis{%d}" % total)

Kinoko的代码 III

源代码：

1
2
3
4
5
6
7
8
9
P = 0x7fffffff
Q = 0x100
n = 0x100
a = [(i ** (i ** i)) % P for i in range(n)]
res = 0
for x in product(a, repeat=8):
    if reduce(add, x) % Q == 0:
        res += reduce(mul, x)
print("Flag is Aegis{%d}" % (res % (P * Q)))

尝试用快速幂计算出了a，后面的部分就没有思路了，感觉跟 $GF(2^m)$ 有关。

Kinoko的代码 IV

源代码：

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *

msg = b'......'
g = 23
p = 335215034881592512312398694238485179340610060759881511231472142277527176340784432381542726029524727833039074808456839870641607412102746854257629226877248337002993023452385472058106944014653401647033456174126976474875859099023703472904735779212010820524934972736276889281087909166017427905825553503050645575935980580803899122224368875197728677516907272452047278523846912786938173456942568602502013001099009776563388736434564541041529106817380347284002060811645842312648498340150736573246893588079033524476111268686138924892091575797329915240849862827621736832883215569687974368499436632617425922744658912248644475097139485785819369867604176912652851123185884810544172785948158330991257118563772736929105360124222843930130347670027236797458715653361366862282591170630650344062377644570729478796795124594909835004189813214758026703689710017334501371279295621820181402191463184275851324378938021156631501330660825566054528793444353
x = bytes_to_long(msg)
h = pow(g,x,p)
print(h)
'''
179956689939799978686596162623009071834749620910632881129570185702597885675366053746660084250822996742213156358846254579536681385720261821941496018561712101559148720253943504890341017743734982584598207516433225345830605843249917382020797858837178839235576965252932584506546764681169682067451758822339982991607788445472451090172187831874941209496749224595861824389402308122683468407022055642183997505151642262281735659513608920324853368172095765041692780083964849712368477052130574239545836322863774186581648844719904538237553913580382934907373884521762228204915991345935021715751152215665694954681931730050491031883519789246541180580522272095192525557554130071875996891173839573092163026966683532806284169788149085982141065261043806380173094680150058915109078775560035635889930619074748416389716690011996098383845646464047453083163083103550738288711630170975733999017234569638947005463854359023927470291784650805324521819096823
'''

考察离散对数求解的知识，直接调用sage中的$discrete_log()$函数求解x，再转换为bytes即可

1
2
3
4
5
6
7
8
from Crypto.Util.number import *

c = 179956689939799978686596162623009071834749620910632881129570185702597885675366053746660084250822996742213156358846254579536681385720261821941496018561712101559148720253943504890341017743734982584598207516433225345830605843249917382020797858837178839235576965252932584506546764681169682067451758822339982991607788445472451090172187831874941209496749224595861824389402308122683468407022055642183997505151642262281735659513608920324853368172095765041692780083964849712368477052130574239545836322863774186581648844719904538237553913580382934907373884521762228204915991345935021715751152215665694954681931730050491031883519789246541180580522272095192525557554130071875996891173839573092163026966683532806284169788149085982141065261043806380173094680150058915109078775560035635889930619074748416389716690011996098383845646464047453083163083103550738288711630170975733999017234569638947005463854359023927470291784650805324521819096823
m = 23
n = 335215034881592512312398694238485179340610060759881511231472142277527176340784432381542726029524727833039074808456839870641607412102746854257629226877248337002993023452385472058106944014653401647033456174126976474875859099023703472904735779212010820524934972736276889281087909166017427905825553503050645575935980580803899122224368875197728677516907272452047278523846912786938173456942568602502013001099009776563388736434564541041529106817380347284002060811645842312648498340150736573246893588079033524476111268686138924892091575797329915240849862827621736832883215569687974368499436632617425922744658912248644475097139485785819369867604176912652851123185884810544172785948158330991257118563772736929105360124222843930130347670027236797458715653361366862282591170630650344062377644570729478796795124594909835004189813214758026703689710017334501371279295621820181402191463184275851324378938021156631501330660825566054528793444353
d=discrete_log(c,mod(m,n))
msg = long_to_bytes(d)
print(msg)

notRSA

源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import getPrime, bytes_to_long

p = getPrime(512)
q = getPrime(512)
n = p * q
flag = b'Aegis{......}'
m = bytes_to_long(flag)
c = pow(m, 2, n)
print(p**3+q**3)
print(p*q-p-q)
print(c)

# p = 9294245038014495018370025503838233837842445450717112861530019994089208464544256432365138864858019427603469395634623982915723003321692974199306043896395471
# q = 12342761514228429158263998414220938515337038241757334937761557332062702646597784278541920751268963691194708568191829119140194036616936954532285327408748239
#2683207403901766067825485634185601766409570143649318199140952968037512600470579376068383383524815864039841298998044483348310172352574406995610031363899276749157640097193160488032526253335175497216620520711500711141110234147693948098688349034232723537263489946840300271580577412796742296691684971450119145954769829625063379511509190333209177419150804570514746916533943674944751821667853376532291018641849933876951962902976903371221223111423718945634451076584248030
#114716649959013852657615268840231124447472690710601678501437134218521741792245535933871147569266364478277891322010833300443127314646898434178369690377612566380887447356076682596113975161733897245200003941284379586690945264751249879210669330319947878473291341185035678293547495739763970613403135670992913681859
#23588520303183909632881265716945062770267850520083979450971468612710595466903076931312046174728593508895307445955963477450821781428035995913285067064035796132808196500567866710084350514597397699053074465810242481186367241

读代码后发现 $e=2$, 很明显的 $Rabin$ 加密，利用题目中给出的 $p^3+q^3$ 和 $pq-p-q$ 联立方程解出 $p, q$ 即可

公式推导如下：

求解 $p, q$ 的代码如下：（此处设$a = p^3+q^3,b = pq-p-q$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sympy as sp
a = 2683207403901766067825485634185601766409570143649318199140952968037512600470579376068383383524815864039841298998044483348310172352574406995610031363899276749157640097193160488032526253335175497216620520711500711141110234147693948098688349034232723537263489946840300271580577412796742296691684971450119145954769829625063379511509190333209177419150804570514746916533943674944751821667853376532291018641849933876951962902976903371221223111423718945634451076584248030
b = 114716649959013852657615268840231124447472690710601678501437134218521741792245535933871147569266364478277891322010833300443127314646898434178369690377612566380887447356076682596113975161733897245200003941284379586690945264751249879210669330319947878473291341185035678293547495739763970613403135670992913681859
p = [1, -3, -3*b, -a]

x = sp.Symbol('x')
f = x**3 + p[1]*x**2 + p[2]*x + p[3]
s = sp.solve(f)
# print(s[0])

pq = s[0]+b
q = [1, -s[0], pq]
y = sp.Symbol('y')
g = y**2 + q[1]*y + q[2]
solve = sp.solve(g)
print('p = ' + str(solve[0]))
print('q = ' + str(solve[1]))

运行后解出$p,q$

1
2
p = 9294245038014495018370025503838233837842445450717112861530019994089208464544256432365138864858019427603469395634623982915723003321692974199306043896395471
q = 12342761514228429158263998414220938515337038241757334937761557332062702646597784278541920751268963691194708568191829119140194036616936954532285327408748239

接下来将 $p,q$ 代入进行 $Rabin$ 解密即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import long_to_bytes
import gmpy2

e = 2
c = 23588520303183909632881265716945062770267850520083979450971468612710595466903076931312046174728593508895307445955963477450821781428035995913285067064035796132808196500567866710084350514597397699053074465810242481186367241
p = 9294245038014495018370025503838233837842445450717112861530019994089208464544256432365138864858019427603469395634623982915723003321692974199306043896395471
q = 12342761514228429158263998414220938515337038241757334937761557332062702646597784278541920751268963691194708568191829119140194036616936954532285327408748239
n = p*q
u = pow(c, (p+1)//4, p)
v = pow(c, (q+1)//4, q)
#   sp+tq=1
s = gmpy2.invert(p, q)   # (p^-1) mod q
t = gmpy2.invert(q, p)   # (q^-1) mod p
x = (t*q*u+s*p*v) % n
y = (t*q*u-s*p*v) % n

print(b'm1 = ' + long_to_bytes(x % n))
print(b'm2 = ' + long_to_bytes((-x) % n))
print(b'm3 = ' + long_to_bytes(y % n))
print(b'm4 = ' + long_to_bytes((-y) % n))

得到结果如下，m3即为flag

1
2
3
4
b'm1 = kg\xe1\xe8u\x8b\x8b\xda\x04>\xd8z<l\xeby\xd9,1<\x81\xc4\x1d0\x1e\xd8=\x82k\x1cr\x8bzP\x03S\xa1)\xf6\xf2\xdf\x87\xa8\x92\xfd\xf00\xfc\xf5(\xb3\x9e\xa3N\x87~\xf2\xab\xcdr\x1e\x04\xac\xaa\xdc\x90U\x0c\xdeC\x00\xe5oy\xb9\xc9\x1e~\xa5\x01=2\x86O\xbd}\xc4\x1f8\x04g\x8c\xc2\x7f\xae\xf2 wX\xb1\xda#\\\xce\xb0\xde[\xf4\xd0\xe9MN\xb8\x93\xc4\xef\x17%g\xaf\x96I*\xdd\x9a\xc2\x8ec'
b'm2 = 7\xf4\xc5\xad!6\x99\x9dO\xd6\xd6\xce?\x89\x02\xdc\xa8\x11\xb11\xb6Lga\xee\x89\x18n\xd8\x845\xb5\x922\x81\xa3\x01\x81\xbe3X\xd5E*\x1b\xc1o\xe4\x00\x04W\xfe\x88\xb8$\xadO\xd7\x9d\xc4\xcb\xee\xcd\x9a\xf0T\xc4\x18\x10\xc9#\x95f\xb01\xe9}\x0b\x80u\xf4g\xd9\x92\xf0\x1bl\x8bd\xde\xcay\xc2Hj\xdb\x11}[\xa1\xef\x86\xbf\xa2\xd3\xdf\xb5\x99\xe7\x13\rg\xe9\xc0*\xefO~\x87\x84\xf4V6\xef\x04\xbd\x8c\xfe'
b'm3 = Aegis{This_is_RABIN_not_RSA_though_similarity}'
b'm4 = \xa3\\\xa7\x95\x96\xc2%wT\x15\xafH{\xf5\xeeV\x81=\xe2n8\x10\x84\x92\raU\xf1C\xa0\xa8A\x0c\x82\x84\xf6\xa2\xab\xb5&8\\\xed\xbd\x19\xb1\xa0\xe0\xf5-\x0b\x9d,\x06\xac,B\x83k6\xe9\xf3zE\xcc\xe5\x19$\xef\x0c$z\xd6)\xeb\xb2\x9b\x8a%w1\x9a\x1e}F/\xbd/Hz\xc8\x93%^\xa6m\xdf\xb3r\n{J\xae\x02\x10^\xbf;v\x9c\xe6N2\xde\x88v\x070\x85\xc7!3\x00Z6\x0b\xa1\xe4'

LFSR

源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
flag = b"Aegis{????????????????????????}"
assert(len(flag)) == 31


def parity(x):  # 检验二进制x中1的个数，奇为1，偶为0
    res = 0
    while x:
        x -= x & (-x)
        res ^= 1
    return res


class LFSR:
    def __init__(self, init, mask, length):
        assert((mask & (1 << (length - 1))) != 0)
        self.init = init
        self.length = length
        self.lengthmask = 2 ** length - 1
        self.mask = mask & self.lengthmask

    def next(self):
        nextdata = (self.init << 1) & self.lengthmask
        output = parity(self.init & self.mask)
        nextdata ^= output
        self.init = nextdata
        return output


secret = flag[6:-1]
l = LFSR(int(secret[:12], 16), int(secret[12:], 16), 48)
outstream = 0
for i in range(96):
    outstream <<= 1
    outstream |= l.next()
print(hex(outstream)[2:])  # 9375392d53d805407156b455

常规的LFSR题目，分析代码可知 $init$ 和 $mask$ 均为 $48bit$

而结果所给的 $outstream$ 为 $96bit$ ，恰好为两轮加密的长度

①前 $48bit$ 为 $init$ 加密经过一轮加密所得

②后 $ 48bit$ 为前 $48bit$ 再经过一轮加密所得

利用第②点加密前后均已知我们可以求得 $mask$ ，sage代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def test(outstream):
    s = [int(x) for x in outstream]

    M = matrix(GF(2), 48, 48)
    T = vector(GF(2), 48)

    for i in range(len(s) - 48):
        M[i] = s[i: i + 48]
        T[i] = s[i + 48]
    try:
        mask = M.inverse() * T
        return hex(int(''.join(map(str, (mask))), base=2))
    except:
        return


outstream = 0x9375392d53d805407156b455
mask = test(bin(outstream)[2:])
print('mask = ' + mask)

运行结果：

1
mask = 0xffbeefc0ff3e

解得 $mask$ 后代入第①点即可解出 $init$ ，将 $init$ 和 $mask$ 拼起来即可得到flag，sage代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import itertools, hashlib, numpy as np


def int2bin(a, n):
    assert 0 <= n and a < 2 ** n
    res = np.zeros(n, dtype=int)

    for x in range(n):
        res[n - x - 1] = a % 2
        a = a // 2
    return res.tolist()


def bin2int(a):
    return reduce(lambda x, y: x * 2 + y, a)


def bitAnd(a, b):
    assert len(a) == len(b)
    return list(map(lambda x, y: int(x) & int(y), a, b))


def test(outstream):
    s = [int(x) for x in outstream]

    M = matrix(GF(2), 48, 48)
    T = vector(GF(2), 48)

    for i in range(len(s) - 48):
        M[i] = s[i: i + 48]
        T[i] = s[i + 48]
    try:
        mask = M.inverse() * T
        print('mask = ' + hex(int(''.join(map(str, (mask))), base=2)))
    except:
        return

    suf = []
    for i in range(48):
        if bitAnd([0] + suf + s[0:47 - i], mask).count(1) % 2 == s[47 - i]:
            suf = [0] + suf
        else:
            suf = [1] + suf

    key = hex(bin2int(suf))[2:]

    print('init = ' + key)
    print('The flag is Aegis{' + key + hex(int(''.join(map(str, (mask))), base=2)) + '}')


outstream = 0x9375392d53d805407156b455
test(bin(outstream)[2:])

运行结果：

1
2
3
mask = 0xffbeefc0ff3e
init = a11ceb0bff0f
The flag is Aegis{a11ceb0bff0f0xffbeefc0ff3e}

ezECC

源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
from Crypto.Cipher import AES
from Crypto.Util.number import inverse
from Crypto.Util.Padding import pad, unpad
from collections import namedtuple
from random import randint
import hashlib
import os

Point = namedtuple("Point", "x y")

O = 'Origin'

FLAG = b'Aegis{......}'


def check_point(P: tuple):
    if P == O:
        return True
    else:
        return (P.y**2 - (P.x**3 + a*P.x + b)) % p == 0 and 0 <= P.x < p and 0 <= P.y < p


def point_inverse(P: tuple):
    if P == O:
        return P
    return Point(P.x, -P.y % p)


def point_addition(P: tuple, Q: tuple):
    if P == O:
        return Q
    elif Q == O:
        return P
    elif Q == point_inverse(P):
        return O
    else:
        if P == Q:
            lam = (3*P.x**2 + a)*inverse(2*P.y, p)
            lam %= p
        else:
            lam = (Q.y - P.y) * inverse((Q.x - P.x), p)
            lam %= p
    Rx = (lam**2 - P.x - Q.x) % p
    Ry = (lam*(P.x - Rx) - P.y) % p
    R = Point(Rx, Ry)
    assert check_point(R)
    return R


def double_and_add(P: tuple, n: int):
    Q = P
    R = O
    while n > 0:
        if n % 2 == 1:
            R = point_addition(R, Q)
        Q = point_addition(Q, Q)
        n = n // 2
    assert check_point(R)
    return R


def gen_shared_secret(Q: tuple, n: int):
    S = double_and_add(Q, n)
    return S.x


def encrypt_flag(shared_secret: int):
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data


p = 310717010502520989590157367261876774703
a = 2
b = 3

g_x = 179210853392303317793440285562762725654
g_y = 105268671499942631758568591033409611165
G = Point(g_x, g_y)

n = randint(1, p)

public = double_and_add(G, n)
print(public)

b_x = 272640099140026426377756188075937988094
b_y = 51062462309521034358726608268084433317
B = Point(b_x, b_y)

shared_secret = gen_shared_secret(B, n)

ciphertext = encrypt_flag(shared_secret)
print(ciphertext)

分析代码知道这是一道 ECC 加 AES 的题目，首先解决ECC得到 $shared_secret$ ，然后再代入AES解密即可，下面是具体解决步骤

首先利用Pollig_Hellman算法求出n：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
p = 310717010502520989590157367261876774703
a = 2
b = 3
E = EllipticCurve(GF(p), [a, b])
K = (260053855577519367767956057258891222403, 179596564645843970846404853116641598439)
G = (179210853392303317793440285562762725654, 105268671499942631758568591033409611165)
K = E.point(K)
G = E.point(G)

# primes中为点G的阶的质因数分解
primes = [2, 3**7, 139, 165229, 31850531, 270778799, 179317983307]
dlogs = []
for fac in primes:
    t = int(G.order()) // int(fac)
    dlog = discrete_log(t*K, t*G, operation='+')
    dlogs += [dlog]
    print(str(fac) + ',' + str(dlog))
n = crt(dlogs, primes)
print('n = ' + str(n))
1
n = 1735615609077661663789047116578013247

再利用求出的 $ n $ 计算 $nB$ 得到 $shared_secret$ ：

1
2
3
4
5
b_x = 272640099140026426377756188075937988094
b_y = 51062462309521034358726608268084433317
B = Point(b_x, b_y)
shared_secret = gen_shared_secret(B, n)
print("shared_secret = " + str(shared_secret))
1
shared_secret = 80834286993107767130878144281867395240

得到 $shared_secret$ 后可以得到AES加密中的key，结合所给的iv，将 $ciphertext$ 解密即可得到 $flag$ ：

1
2
3
4
5
6
7
8
9
10
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]

iv = bytes.fromhex('45879e81ea63153f4dbc94603cbf6ebc')

cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = bytes.fromhex('db9741d44b9d1718bb9e47b7584795e1f09169119a6d5bafe6fe6a6b950e5669f64ec7057f21711c4e896d4a65de20af')
flag = unpad(cipher.decrypt(plaintext), 16)
print(flag)
1
b'Aegis{07e2628b590095a5e332d397b8a59aa7}'

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
from Crypto.Cipher import AES
from Crypto.Util.number import inverse
from Crypto.Util.Padding import pad, unpad
from collections import namedtuple
from random import randint
import hashlib
import os

Point = namedtuple("Point", "x y")

O = 'Origin'

def check_point(P: tuple):
    if P == O:
        return True
    else:
        return (P.y**2 - (P.x**3 + a*P.x + b)) % p == 0 and 0 <= P.x < p and 0 <= P.y < p


def point_inverse(P: tuple):
    if P == O:
        return P
    return Point(P.x, -P.y % p)


def point_addition(P: tuple, Q: tuple):
    if P == O:
        return Q
    elif Q == O:
        return P
    elif Q == point_inverse(P):
        return O
    else:
        if P == Q:
            lam = (3*P.x**2 + a)*inverse(2*P.y, p)
            lam %= p
        else:
            lam = (Q.y - P.y) * inverse((Q.x - P.x), p)
            lam %= p
    Rx = (lam**2 - P.x - Q.x) % p
    Ry = (lam*(P.x - Rx) - P.y) % p
    R = Point(Rx, Ry)
    assert check_point(R)
    return R


def double_and_add(P: tuple, n: int):
    Q = P
    R = O
    while n > 0:
        if n % 2 == 1:
            R = point_addition(R, Q)
        Q = point_addition(Q, Q)
        n = n // 2
    assert check_point(R)
    return R


def gen_shared_secret(Q: tuple, n: int):
    S = double_and_add(Q, n)
    return S.x


p = 310717010502520989590157367261876774703
a = 2
b = 3
E = EllipticCurve(GF(p), [a, b])
K = (260053855577519367767956057258891222403, 179596564645843970846404853116641598439)
G = (179210853392303317793440285562762725654, 105268671499942631758568591033409611165)
K = E.point(K)
G = E.point(G)

primes = [2, 3**7, 139, 165229, 31850531, 270778799, 179317983307]
dlogs = []
for fac in primes:
    t = int(G.order()) // int(fac)
    dlog = discrete_log(t*K, t*G, operation='+')
    dlogs += [dlog]
    print(str(fac) + ',' + str(dlog))
n = crt(dlogs, primes)

b_x = 272640099140026426377756188075937988094
b_y = 51062462309521034358726608268084433317
B = Point(b_x, b_y)
shared_secret = gen_shared_secret(B, n)

sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]

iv = bytes.fromhex('45879e81ea63153f4dbc94603cbf6ebc')

cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = bytes.fromhex('db9741d44b9d1718bb9e47b7584795e1f09169119a6d5bafe6fe6a6b950e5669f64ec7057f21711c4e896d4a65de20af')
flag = unpad(cipher.decrypt(plaintext), 16)
print(flag)