Misay's blog
0%

UCSCCTF2025

发表于 更新于 分类于
UCSCCTF-WP

1.XR4

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
import base64
import random
from secret import flag
import numpy as np
def init_sbox(key):
    s_box = list(range(256))
    j = 0
    for i in range(256):
        j = (j + s_box[i] + ord(key[i % len(key)])) % 256
        s_box[i], s_box[j] = s_box[j], s_box[i]
    return s_box
def decrypt(cipher, box):
    res = []
    i = j = 0
    cipher_bytes = base64.b64decode(cipher)
    for s in cipher_bytes:
        i = (i + 1) % 256
        j = (j + box[i]) % 256
        box[i], box[j] = box[j], box[i]
        t = (box[i] + box[j]) % 256
        k = box[t]
        res.append(chr(s ^ k))
    return (''.join(res))
def random_num(seed_num):
    random.seed(seed_num)
    for i in range(36):
        print(chr(int(str(random.random()*10000)[0:2]) ^ (data[i])))

if __name__ == '__main__':
    ciphertext = "MjM184anvdA="
    key = "XR4"
    box = init_sbox(key)
    a=decrypt(ciphertext, box)
    random_num(int(a))
# transposed_matrix=(data.reshape(6*6))^T
# transposed_matrix=[[  1 111  38 110  95  44]
#  [ 11  45  58  39  84   1]
#  [116  19 113  60  91 118]
#  [ 33  98  38  57  10  29]
#  [ 68  52 119  56  43 125]
#  [ 32  32   7  26  41  41]]

类似RC4的流密码，解密思路是用密钥XR4解密密文MjM184anvdA=还原出随机数种子，用来重置随机数生成器，再恢复矩阵，最后生成随机数流逐位异或就能得到答案，exp

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
import base64
import random
import numpy as np

# RC4初始化函数
def init_sbox(key):
    s_box = list(range(256))
    j = 0
    for i in range(256):
        j = (j + s_box[i] + ord(key[i % len(key)])) % 256
        s_box[i], s_box[j] = s_box[j], s_box[i]
    return s_box

# RC4解密函数
def decrypt(cipher, box):
    res = []
    i = j = 0
    cipher_bytes = base64.b64decode(cipher)
    for s in cipher_bytes:
        i = (i + 1) % 256
        j = (j + box[i]) % 256
        box[i], box[j] = box[j], box[i]
        t = (box[i] + box[j]) % 256
        k = box[t]
        res.append(s ^ k)
    return bytes(res)

if __name__ == '__main__':
    # 已知参数
    ciphertext = "MjM184anvdA="
    key = "XR4"
    transposed_matrix = np.array([
        [1, 111, 38, 110, 95, 44],
        [11, 45, 58, 39, 84, 1],
        [116, 19, 113, 60, 91, 118],
        [33, 98, 38, 57, 10, 29],
        [68, 52, 119, 56, 43, 125],
        [32, 32, 7, 26, 41, 41]
    ])

    # Step 1: 解密RC4获取种子
    box = init_sbox(key)
    seed_bytes = decrypt(ciphertext, box.copy())
    seed = int(seed_bytes.decode())
    print(f"[+] 解密种子值: {seed}") # 78910112

    # Step 2: 恢复原始矩阵
    original_matrix = transposed_matrix.T.reshape(-1)  # 转置恢复原始顺序
    
    # Step 3: 生成随机数序列
    random.seed(seed)
    flag_chars = []
    for num in original_matrix:
        rand_val = int(str(random.random() * 10000)[:2])  # 生成前两位数字
        flag_char = chr(rand_val ^ num)
        flag_chars.append(flag_char)

    # Step 4: 组合flag
    flag = ''.join(flag_chars)
    print(f"\n[+] 解密结果: {flag}") # c570ee41-8b09-11ef-ac4a-a4b1c1c5a2d2

flag{c570ee41-8b09-11ef-ac4a-a4b1c1c5a2d2}

2.essential

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
from Crypto.Util.number import *
import sympy
from flag import flag
a=getPrime(512)
p=sympy.nextprime(13*a)
q=sympy.prevprime(25*a)
number2=p*q

def crypto01(number1, number2, number3):
    number4 = 1
    while number2 > 0:
        if number2 % 2: 
            number4 = (number4 * number1) % number3
        number1 = number1 ** 2 % number3
        number2 //= 2
    return number4
# n1^n2 mod n3

def crypto02(number1, number2):
    number3 = number1
    number4 = number2
    giao = 1
    giaogiao = 0
    while number4 > 0:
        number7 = number3 // number4
        giao, giaogiao = giaogiao, giao - giaogiao*number7
        number3, number4 = number4, number3 - number4*number7
    while giao<0:
        giao = giao + number2
    return giao
#pow(n1,-1,n2)

def crypto03(number1, number2, number3):
    number4 = crypto01(number3, number1, number2)
    return number4
# n3^n1 mod n2

def crypto05(number1,number2):
    return pow(number1,0xe18e,number2)
# n1^e mod n2

number2 = 20163906788220322201451577848491140709934459544530540491496316478863216041602438391240885798072944983762763612154204258364582429930908603435291338810293235475910630277814171079127000082991765275778402968190793371421104016122994314171387648385459262396767639666659583363742368765758097301899441819527512879933947
number1 = 6035830951309638186877554194461701691293718312181839424149825035972373443231514869488117139554688905904333169357086297500189578624512573983935412622898726797379658795547168254487169419193859102095920229216279737921183786260128443133977458414094572688077140538467216150378641116223616640713960883880973572260683

number3 = int.from_bytes(flag[0:19].encode("utf-8"), "big")
number4 = int.from_bytes(flag[19:39].encode("utf-8"), "big")

print(crypto03(number1, number2, number3))
print(crypto05(number4,number2))
#6624758244437183700228793390575387439910775985543869953485120951825790403986028668723069396276896827302706342862776605008038149721097476152863529945095435498809442643082504012461883786296234960634593997098236558840899107452647003306820097771301898479134315680273315445282673421302058215601162967617943836306076  p1
#204384474875628990804496315735508023717499220909413449050868658084284187670628949761107184746708810539920536825856744947995442111688188562682921193868294477052992835394998910706435735040133361347697720913541458302074252626700854595868437809272878960638744881154520946183933043843588964174947340240510756356766  p2

套层皮的RSA，crypto01计算的是

crypto02计算的是

crypto03计算的是

crypto05计算的是

这里给出了

,注意到a就512位，且考虑到质数分步在500多位下都很密集，p应该很接近13a，q很接近25a，那么就可以对n1除去13*25再开根，得到一个a的初步估计，再尝试搜索出p,q的值，脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def find_a(n):
    a_approx = gmpy2.isqrt(n // 325)
    for delta in range(-1000, 1000):  # 搜索偏移范围
        a_candidate = int(a_approx) + delta
        p = sympy.nextprime(13 * a_candidate)
        q = sympy.prevprime(25 * a_candidate)
        if p * q == n:
            return a_candidate, p, q
    return None

a, p, q = find_a(n)
print(f"[+] Found a: {a}")
print(f"p = {p}\nq = {q}")

```
[+] Found a: 7876724580534791771835430594434627088013471560469412207736963203935537053220379418645369259714178145931522503674390087394035229717461111762112820042426110
p = 102397419546952293033860597727650152144175130286102358700580521651161981691864932442389800376284315897109792547767071136122457986326994452907466660551539601
q = 196918114513369794295885764860865677200336789011735305193424080098388426330509485466134231492854453648288062591859752184850880742936527794052820501060652747
```

有了p,q之后就是很基础的RSA解明文了，注意到e与phi不互素，但是gcd很小，先试着用e//2算，实在不行再尝试有限域开根，所幸这里直接就算出来了,exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
p = 102397419546952293033860597727650152144175130286102358700580521651161981691864932442389800376284315897109792547767071136122457986326994452907466660551539601
q = 196918114513369794295885764860865677200336789011735305193424080098388426330509485466134231492854453648288062591859752184850880742936527794052820501060652747

number2 = 20163906788220322201451577848491140709934459544530540491496316478863216041602438391240885798072944983762763612154204258364582429930908603435291338810293235475910630277814171079127000082991765275778402968190793371421104016122994314171387648385459262396767639666659583363742368765758097301899441819527512879933947
number1 = 6035830951309638186877554194461701691293718312181839424149825035972373443231514869488117139554688905904333169357086297500189578624512573983935412622898726797379658795547168254487169419193859102095920229216279737921183786260128443133977458414094572688077140538467216150378641116223616640713960883880973572260683
c1 = 6624758244437183700228793390575387439910775985543869953485120951825790403986028668723069396276896827302706342862776605008038149721097476152863529945095435498809442643082504012461883786296234960634593997098236558840899107452647003306820097771301898479134315680273315445282673421302058215601162967617943836306076
c2 = 204384474875628990804496315735508023717499220909413449050868658084284187670628949761107184746708810539920536825856744947995442111688188562682921193868294477052992835394998910706435735040133361347697720913541458302074252626700854595868437809272878960638744881154520946183933043843588964174947340240510756356766

e=0xe18e
phi = (p-1)*(q-1)
print(GCD(number1,phi))
d1 = inverse(number1,phi)
m1 = pow(c1,d1,number2)
d2 = inverse(e//2,phi)
M2 = pow(c2,d2,number2)
m2 = int(gmpy2.iroot(M2,2)[0])
print(long_to_bytes(m1)+long_to_bytes(m2))

#b'flag{75811c6d95770d56092817b75f15df05}'

flag{75811c6d95770d56092817b75f15df05}

3.EZ-calculate

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
from Crypto.Util.number import *
from random import randint
from hashlib import md5

flag1 = b'xxx'
flag2 = b'xxx'
Flags = 'flag{' + md5(flag1+flag2).hexdigest()[::-1] + '}'

def backpack_encrypt_flag(flag_bytes, M, group_len):
    bits = []
    for byte in flag_bytes:
        bits.extend([int(b) for b in format(byte, "08b")])

    while len(bits) % group_len != 0:
        bits.append(0)

    S_list = []
    for i in range(0, len(bits), group_len):
        group = bits[i:i + group_len]
        S = sum(bit * m for bit, m in zip(group, M))
        S_list.append(S)
    return S_list

def backpack(flag_bytes):
    R = [10]
    while len(R) < 8:
        next_val = randint(2 * R[-1], 3 * R[-1])
        R.append(next_val)
    B = randint(2 * R[-1] + 1, 3 * R[-1])
    A = getPrime(100)
    M = [A * ri % B for ri in R]
    S_list = backpack_encrypt_flag(flag_bytes, M, len(M))
    return R, A, B, M, S_list

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 0x10000
m = bytes_to_long(flag1)
k = randint(1, 999)
problem1 = (pow(p,e,n)-pow(q,e,n)) % n
problem2 = pow(p-q,e,n)*pow(e,k,n)
c = pow(m,e,n)

R, A, B, M, S_list = backpack(flag2)

with open(r"C:\Users\Rebirth\Desktop\data.txt", "w") as f:
    f.write(f"problem1 = {problem1}\n")
    f.write(f"problem2 = {problem2}\n")
    f.write(f"n = {n}\n")
    f.write(f"c = {c}\n")
    f.write("-------------------------\n")
    f.write(f"R = {R}\n")
    f.write(f"A = {A}\n")
    f.write(f"B = {B}\n")
    f.write(f"M = {M}\n")
    f.write(f"S_list = {S_list}\n")
    f.write("-------------------------\n")
    f.write(f"What you need to submit is Flags!\n")

  • part1

    RSA,题目给出的是

这里我们的思路是枚举k的取值，计算出pow(e,k,n)之后用p2来除它，得到P，那么由二项式定理

上下相加，容易得到

同样的方法我们也能枚举出q，再用位数和正负号作为制约就能爆破出p,q的值，脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
problem1 = 24819077530766367166035941051823834496451802693325219476153953490742162231345380863781267094224914358021972805811737102184859249919313532073566493054398702269142565372985584818560322911207851760003915310535736092154713396343146403645986926080307669092998175883480679019195392639696872929250699367519967334248
problem2 = 20047847761237831029338089120460407946040166929398007572321747488189673799484690384806832406317298893135216999267808940360773991216254295946086409441877930687132524014042802810607804699235064733393301861594858928571425025486900981252230771735969897010173299098677357738890813870488373321839371734457780977243838253195895485537023584305192701526016
n = 86262122894918669428795269753754618836562727502569381672630582848166228286806362453183099819771689423205156909662196526762880078792845161061353312693752568577607175166060900619163231849790003982326663277243409696279313372337685740601191870965951317590823292785776887874472943335746122798330609540525922467021
c = 74962027356320017542746842438347279031419999636985213695851878703229715143667648659071242394028952959096683055640906478244974899784491598741415530787571499313545501736858104610426804890565497123850685161829628373760791083545457573498600656412030353579510452843445377415943924958414311373173951242344875240776
e=65536

for i in range(1,1000):
    k = pow(e,i,n)
    Pr2 = problem2//k
    # print(isinstance(Pr2,int))
    sum = problem1+Pr2
    sub = Pr2 - problem1
    if sub>0 :
        q = GCD(sub,n)
        print(q)
# 爆破p q
#p = 9586253455468582613875015189854230646329578628731744411408644831684238720919107792959420247980417763684885397749546095133107188260274536708721056484419031
#q = 8998523072192453101232205847855618180700579235012899613083663121402246420191771909612939404791268078655630846054784775118256720627970477420936836352759291

然后这里e是65536，不和phi互素，gcd是4，就考虑有限域开根然后用crt算可能的解了，脚本如下

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
from Crypto.Util.number import *
from math import gcd
from sage.all import *

# 给定参数
p = 9586253455468582613875015189854230646329578628731744411408644831684238720919107792959420247980417763684885397749546095133107188260274536708721056484419031
q = 8998523072192453101232205847855618180700579235012899613083663121402246420191771909612939404791268078655630846054784775118256720627970477420936836352759291
n = p * q
e = 65536
c = 74962027356320017542746842438347279031419999636985213695851878703229715143667648659071242394028952959096683055640906478244974899784491598741415530787571499313545501736858104610426804890565497123850685161829628373760791083545457573498600656412030353579510452843445377415943924958414311373173951242344875240776
possible_m = []
def decrypt_rsa_with_coprime_e(p, q, e, c):
    # 计算模p和模q的c值
    c_p = c % p
    c_q = c % q

    # 处理模p下的解
    s_p = (p - 1) // 2  # 因为p-1的2的指数为1
    d_p = pow(e, -1, s_p)
    m_p = pow(c_p, d_p, p)
    solutions_p = [m_p, (-m_p) % p]

    # 处理模q下的解
    s_q = (q - 1) // 2  # q-1的2的指数为1
    d_q = pow(e, -1, s_q)
    m_q = pow(c_q, d_q, q)
    solutions_q = [m_q, (-m_q) % q]

    # 使用CRT组合所有可能的解
    from itertools import product
    possible_m = []
    for mp, mq in product(solutions_p, solutions_q):
        m = CRT([mp, mq], [p, q])
        possible_m.append(m)

    return possible_m
    
# 执行解密
possible_m = decrypt_rsa_with_coprime_e(p, q, e, c)
for m in possible_m:
    print(long_to_bytes(m))
# b'CRYPTO_ALGORIT'

不过跑出来b’CRYPTO_ALGORIT’就是第一个，有可能开根也能做呢

  • part2

    背包加密，不过该给的都给了，按照加密过程反过来写很快就能搞出来

    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
    from Crypto.Util.number import long_to_bytes
    import math

    # 已知参数
    R = [10, 29, 83, 227, 506, 1372, 3042, 6163]
    A = 1253412688290469788410859162653
    B = 16036
    M = [10294, 12213, 10071, 4359, 1310, 4376, 7622, 14783]
    S_list = [13523, 32682, 38977, 44663, 43353, 31372, 17899, 17899, 44663, 16589, 40304, 25521, 31372]

    def backpack_decrypt(S_list, A, B, M):
        # 1. 验证A与B互质
        assert math.gcd(A, B) == 1, "A and B must be coprime"
        
        # 2. 计算A的模逆元
        inv_A = pow(A, -1, B)
        
        # 3. 恢复超递增序列R
        R_recovered = [(m * inv_A) % B for m in M]
        print("恢复的R:", R_recovered)  # 应等于原始R
        
        # 4. 解密每个S值
        bits = []
        for S in S_list:
            # 将S转换为超递增背包问题
            S_prime = (S * inv_A) % B
            
            # 贪心算法解背包
            group = []
            remaining = S_prime
            for r in reversed(R_recovered):
                if remaining >= r:
                    group.append(1)
                    remaining -= r
                else:
                    group.append(0)
            bits.extend(group[::-1])  # 反转后加入
        
        # 5. 转换二进制为字节
        bytes_data = b''
        for i in range(0, len(bits), 8):
            byte_bits = bits[i:i+8]
            if len(byte_bits) < 8:
                byte_bits += [0]*(8 - len(byte_bits))
            byte = int(''.join(map(str, byte_bits)), 2)
            bytes_data += bytes([byte])
        
        # 6. 去除填充的零
        return bytes_data.rstrip(b'\x00')

    # 执行解密
    flag2 = backpack_decrypt(S_list, A, B, M)
    print("解密结果:", flag2.decode())
    # HMS_WELL_DONE

    最后对两个flag拼接之后取md5，flag{64f67374264b7621650b1de4dbc5f924}

4.merge_ECC

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
#t.sage
import random
from sympy import nextprime
def part1():
    p = random_prime(2^512, 2^513)
    a = random.randint(0, p-1)
    b = random.randint(0, p-1)
    while (4 * a**3 + 27 * b**2) % p == 0:
        a = random.randint(0, p-1)
        b = random.randint(0, p-1)

    E = EllipticCurve(GF(p), [a, b])#构造一个模p环下的关于a,b的椭圆曲线

    P=E.random_point()#曲线上的随机一个点

    n = [random.randint(1, 2**20) for _ in range(3)] #随机的一个点
    assert part1=''.join([hex(i)[2:] for i in n])
    cipher = [n[i] * P for i in range(3)]

    print(f"N = {p}")
    print(f"a = {a}, b = {b}")
    print(f"P = {P}")
    for i in range(3):
        print(f"cipher{i} = {cipher[i]}")
# CRT


def part2():
    p =  839252355769732556552066312852886325703283133710701931092148932185749211043
    a =  166868889451291853349533652847942310373752202024350091562181659031084638450
    b =  168504858955716283284333002385667234985259576554000582655928538041193311381
    P = E.random_point()
    Q = key*P
    print("p = ",p)
    print("a = ",a)
    print("b = ",b)
    print("P = ",P)
    print("Q = ",Q)
    assert part2=key
part1()
print("-------------------------------------------")
part2()
assert flag="flag{"+str(part1)+"-"+str(part2)+"}"


考察的是有关ECC的两种特殊攻击方法

  • part1

    攻击的思路是Pohlig-Hellman攻击，要求是曲线的阶有小因数，这里E.order计算出来是512位，丢yafu分解之后发现有7个因子，其中5个比较小，且全部乘起来之后是比要大的，因此我们就可以取小的5个因子来进行攻击，脚本如下

    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
    from sage.all import *
    from Crypto.Util.number import *
    n = 8186762541745429544201163537921168767557829030115874801599552603320381728161178278432652391299286759969365150578265902315058515370390070500719061057476940
    print(n.bit_length())
    # 2*2*5*11*499*683*124696170958113532210068667*875618937758378886905025632349007870524674918888468835522805095350653442872611049093102429356717528012933133846029979343
    # 椭圆曲线参数
    p = 8186762541745429544201163537921168767557829030115874801599552603320381728161132002130533050721684554609459754424458805702284922582219134865036743485620797
    a = 1495420997701481377470828570661032998514190598989197201754979317255564287604311958150666812378959018880028977121896929545639701195491870774156958755735447
    b = 5991466901412408757938889677965118882508317970919705053385317474407117921506012065861844241307270755999163280442524251782766457119443496954015171881396147
    E = EllipticCurve(GF(p), [a, b])

    # 生成元和密文点
    P = E(
        6053058761132539206566092359337778642106843252217768817197593657660613775577674830119685211727923302909194735842939382758409841779476679807381619373546323,
        7059796954840479182074296506322819844555365317950589431690683736872390418673951275875742138479119268529134101923865062199776716582160225918885119415223226
    )

    cipher0 = E(
        4408587937721811766304285221308758024881057826193901720202053016482471785595442728924925855745045433966244594468163087104593409425316538804577603801023861,
        5036207336371623412617556622231677184152618465739959524167001889273208946091746905245078901669335908442289383798546066844566618503786766455892065155724816
    )

    cipher1 = E(
        2656427748146837510897512086140712942840881743356863380855689945832188909581954790770797146584513962618190767634822273749569907212145053676352384889228875,
        4010263650619965046904980178893999473955022015118149348183137418914551275841596653682626506158128955577872592363930977349664669161585732323838763793957500
    )

    cipher2 = E(
        1836350123050832793309451054411760401335561429787905037706697802971381859410503854213212757333551949694177845513529651742217132039482986693213175074097638,
        1647556471109115097539227566131273446643532340029032358996281388864842086424490493200350147689138143951529796293632149050896423880108194903604646084656434
    )

    # 已知阶的分解（排除最后两个大因子）
    primes = [4, 5, 11, 499, 683]  # 2^2, 5, 11, 499, 683

    def pohlig_hellman(P, Q, primes):
        dlogs = []
        for fac in primes:
            t = P.order() // fac
            PP = t * P
            QQ = t * Q
            dlog = PP.discrete_log(QQ)  # 自动选择最佳算法
            dlogs.append(dlog)
            print(f"Factor: {fac}, Discrete Log: {dlog}")
        return crt(dlogs, primes)

    # 计算三个离散对数
    print("计算n0:")
    n0 = pohlig_hellman(P, cipher0, primes)

    print("\n计算n1:")
    n1 = pohlig_hellman(P, cipher1, primes)

    print("\n计算n2:")
    n2 = pohlig_hellman(P, cipher2, primes)

    # 验证结果
    assert cipher0 == n0 * P
    assert cipher1 == n1 * P
    assert cipher2 == n2 * P

    # 拼接结果
    part1 = hex(n0)[2:] + hex(n1)[2:] + hex(n2)[2:]
    print("\n解密结果:", part1)
    # f61bd9f152e65ac

    • part2

      smart攻击，这里曲线计算出来阶和模数相同，脚本如下

      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
      from sage.all import *
      from Crypto.Util.number import *
      from gmpy2 import *

      p =  839252355769732556552066312852886325703283133710701931092148932185749211043
      a =  166868889451291853349533652847942310373752202024350091562181659031084638450
      b =  168504858955716283284333002385667234985259576554000582655928538041193311381
      E = EllipticCurve(GF(p), [a, b])
      r = E.order()
      # 839252355769732556552066312852886325703283133710701931092148932185749211043
      print(r)
      P =  E(547842233959736088159936218561804098153493246314301816190854370687622130932 , 259351987899983557442340376413545600148150183183773375317113786808135411950 )
      Q =  E(52509027983019069214323702207915994504051708473855890224511139305828303028 , 520507172059483331872189759719244369795616990414416040196069632909579234481 )

      def SmartAttack(P,Q,p):
          E = P.curve()
          Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

          P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
          for P_Qp in P_Qps:
              if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
                  break

          Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
          for Q_Qp in Q_Qps:
              if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
                  break

          p_times_P = p*P_Qp
          p_times_Q = p*Q_Qp

          x_P,y_P = p_times_P.xy()
          x_Q,y_Q = p_times_Q.xy()

          phi_P = -(x_P/y_P)
          phi_Q = -(x_Q/y_Q)
          k = phi_Q/phi_P
          return ZZ(k)

      r = SmartAttack(P, Q, p)
      print(r)

      # 7895892011

      flag{f61bd9f152e65ac-7895892011}

*5.logos

2023赣政杯原题，这里是别的师傅写的博客2023赣政杯 —- Crypto_赣政杯2023-CSDN博客

还在被sagemath各种环境问题折磨，就暂时不细写了