UCSC CTF 2025 WriteUp

前言

比赛时间：2025.4.20

USCS CTF 2025 的 WriteUp，基本ak，差了三道密码，已复现Ez_Calculate。

https://blog.csdn.net/2302_79344173/article/details/147375144

MERGE_ECC

题目：

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=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]}")
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)+"}"

output

N = 8186762541745429544201163537921168767557829030115874801599552603320381728161132002130533050721684554609459754424458805702284922582219134865036743485620797
a = 1495420997701481377470828570661032998514190598989197201754979317255564287604311958150666812378959018880028977121896929545639701195491870774156958755735447, b = 5991466901412408757938889677965118882508317970919705053385317474407117921506012065861844241307270755999163280442524251782766457119443496954015171881396147
P = (6053058761132539206566092359337778642106843252217768817197593657660613775577674830119685211727923302909194735842939382758409841779476679807381619373546323 : 7059796954840479182074296506322819844555365317950589431690683736872390418673951275875742138479119268529134101923865062199776716582160225918885119415223226 : 1)
cipher0 = (4408587937721811766304285221308758024881057826193901720202053016482471785595442728924925855745045433966244594468163087104593409425316538804577603801023861 : 5036207336371623412617556622231677184152618465739959524167001889273208946091746905245078901669335908442289383798546066844566618503786766455892065155724816 : 1)
cipher1 = (2656427748146837510897512086140712942840881743356863380855689945832188909581954790770797146584513962618190767634822273749569907212145053676352384889228875 : 4010263650619965046904980178893999473955022015118149348183137418914551275841596653682626506158128955577872592363930977349664669161585732323838763793957500 : 1)
cipher2 = (1836350123050832793309451054411760401335561429787905037706697802971381859410503854213212757333551949694177845513529651742217132039482986693213175074097638 : 1647556471109115097539227566131273446643532340029032358996281388864842086424490493200350147689138143951529796293632149050896423880108194903604646084656434 : 1)

-------------------------------------------
p =  839252355769732556552066312852886325703283133710701931092148932185749211043
a =  166868889451291853349533652847942310373752202024350091562181659031084638450
b =  168504858955716283284333002385667234985259576554000582655928538041193311381
P =  (547842233959736088159936218561804098153493246314301816190854370687622130932 : 259351987899983557442340376413545600148150183183773375317113786808135411950 : 1)
Q =  (52509027983019069214323702207915994504051708473855890224511139305828303028 : 520507172059483331872189759719244369795616990414416040196069632909579234481 : 1)

第一段，爆破

p = 8186762541745429544201163537921168767557829030115874801599552603320381728161132002130533050721684554609459754424458805702284922582219134865036743485620797
a = 1495420997701481377470828570661032998514190598989197201754979317255564287604311958150666812378959018880028977121896929545639701195491870774156958755735447
b = 5991466901412408757938889677965118882508317970919705053385317474407117921506012065861844241307270755999163280442524251782766457119443496954015171881396147
E = EllipticCurve(GF(p),[a,b])
# print(E.order())
P =  E(6053058761132539206566092359337778642106843252217768817197593657660613775577674830119685211727923302909194735842939382758409841779476679807381619373546323 , 7059796954840479182074296506322819844555365317950589431690683736872390418673951275875742138479119268529134101923865062199776716582160225918885119415223226)
Q1 = E(4408587937721811766304285221308758024881057826193901720202053016482471785595442728924925855745045433966244594468163087104593409425316538804577603801023861 , 5036207336371623412617556622231677184152618465739959524167001889273208946091746905245078901669335908442289383798546066844566618503786766455892065155724816)
Q2 = E(2656427748146837510897512086140712942840881743356863380855689945832188909581954790770797146584513962618190767634822273749569907212145053676352384889228875 , 4010263650619965046904980178893999473955022015118149348183137418914551275841596653682626506158128955577872592363930977349664669161585732323838763793957500)
Q3 = E(1836350123050832793309451054411760401335561429787905037706697802971381859410503854213212757333551949694177845513529651742217132039482986693213175074097638 , 1647556471109115097539227566131273446643532340029032358996281388864842086424490493200350147689138143951529796293632149050896423880108194903604646084656434)

Q0 = P * 114514
# key = []

# for i in range(2^20):
#     if i*P in [Q1, Q2, Q3, Q0]:
#         print(i)
#         key.append(i)
#         if len(key) == 4:
#             break
#     if i % 10000 == 0:
#         print(i)

#   651602 943532 1008061

print(1008061*P)
print(651602*P)
print(943532*P)

第二段，Smart攻击

from Crypto.Util.number import *


p =  839252355769732556552066312852886325703283133710701931092148932185749211043
a =  166868889451291853349533652847942310373752202024350091562181659031084638450
b =  168504858955716283284333002385667234985259576554000582655928538041193311381
E = EllipticCurve(GF(p),[a,b])
P =  E(547842233959736088159936218561804098153493246314301816190854370687622130932, 259351987899983557442340376413545600148150183183773375317113786808135411950, 1)
Q =  E(52509027983019069214323702207915994504051708473855890224511139305828303028, 520507172059483331872189759719244369795616990414416040196069632909579234481, 1)

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)

k = SmartAttack(P, Q, p)
print(k) # 7895892011
print(k*P==Q)

n = [1008061, 651602, 943532] 
part1=''.join([hex(i)[2:] for i in n])
part2=7895892011
flag="flag{"+str(part1)+"-"+str(part2)+"}"
print(flag)
# flag{f61bd9f152e65ac-7895892011}

essential

题目：

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

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

def crypto03(number1, number2, number3):
    number4 = crypto01(number3, number1, number2)
    return number4



def crypto05(number1,number2):
    return pow(number1,0xe18e,number2)






number1 = 6035830951309638186877554194461701691293718312181839424149825035972373443231514869488117139554688905904333169357086297500189578624512573983935412622898726797379658795547168254487169419193859102095920229216279737921183786260128443133977458414094572688077140538467216150378641116223616640713960883880973572260683
number2 = 20163906788220322201451577848491140709934459544530540491496316478863216041602438391240885798072944983762763612154204258364582429930908603435291338810293235475910630277814171079127000082991765275778402968190793371421104016122994314171387648385459262396767639666659583363742368765758097301899441819527512879933947

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
#204384474875628990804496315735508023717499220909413449050868658084284187670628949761107184746708810539920536825856744947995442111688188562682921193868294477052992835394998910706435735040133361347697720913541458302074252626700854595868437809272878960638744881154520946183933043843588964174947340240510756356766

一个密码题还跟我玩混淆？

就是两个RSA而已，只不过e不一样前者是number1，后者是0xE18E。

首先要找p跟q，显然，a越大，p和q就越大，这样我们就可以用二分法，在logn的时间下求出a即可。

用这个pq就直接出第一个了。

from Crypto.Util.number import *
import sympy

def func(a):
    p = sympy.nextprime(13 * a)
    q = sympy.prevprime(25 * a)
    N = p * q
    return N

def binary_search(target, low, high):
    while low <= high:
        mid = low + (high - low) // 2
        print(high - low)
        if target == func(mid):
            return mid
        elif target < func(mid):
            high = mid - 1
        else:
            low = mid + 1
    return -1  # 查找失败

N = 20163906788220322201451577848491140709934459544530540491496316478863216041602438391240885798072944983762763612154204258364582429930908603435291338810293235475910630277814171079127000082991765275778402968190793371421104016122994314171387648385459262396767639666659583363742368765758097301899441819527512879933947

# low = 1
# high = 2**512
# result = binary_search(N, low, high)
# if result != -1:
#     print(result)

# a = 7876724580534791771835430594434627088013471560469412207736963203935537053220379418645369259714178145931522503674390087394035229717461111762112820042426112
# p = sympy.nextprime(13 * a)
# q = sympy.prevprime(25 * a)
# print(f"p = {p}")
# print(f"q = {q}")
# assert N == p * q

c1 = 6624758244437183700228793390575387439910775985543869953485120951825790403986028668723069396276896827302706342862776605008038149721097476152863529945095435498809442643082504012461883786296234960634593997098236558840899107452647003306820097771301898479134315680273315445282673421302058215601162967617943836306076
c2 = 204384474875628990804496315735508023717499220909413449050868658084284187670628949761107184746708810539920536825856744947995442111688188562682921193868294477052992835394998910706435735040133361347697720913541458302074252626700854595868437809272878960638744881154520946183933043843588964174947340240510756356766

p = 102397419546952293033860597727650152144175130286102358700580521651161981691864932442389800376284315897109792547767071136122457986326994452907466660551539601
q = 196918114513369794295885764860865677200336789011735305193424080098388426330509485466134231492854453648288062591859752184850880742936527794052820501060652747

e1 = 6035830951309638186877554194461701691293718312181839424149825035972373443231514869488117139554688905904333169357086297500189578624512573983935412622898726797379658795547168254487169419193859102095920229216279737921183786260128443133977458414094572688077140538467216150378641116223616640713960883880973572260683
e2 = 0xE18E

phi = (p - 1) * (q - 1)

d = inverse(e1, phi)
m = pow(c1, d, N)
print(long_to_bytes(m))
# b'flag{75811c6d95770d'
# flag{75811c6d95770d56092817b75f15df05}

第二个是phi和e不互素，用我以前的脚本套一下。

from Crypto.Util.number import *
import gmpy2

def part_roots(n, c, e, p):
    # 将e约简到可逆，g为余下的因数
    def div_e(e, p):
        g = GCD(e, (p - 1))
        while GCD(e, (p - 1)) != 1:
            e //= GCD(e, (p - 1))
            g *= GCD(e, (p - 1))
        return e, g
    
    # 约简e，便于开根
    e, g = div_e(e, p)
    d = inverse(e, p - 1)
    M = pow(c, d, p)
    
    # 在有限域内开根
    R.<x> = Zmod(p)[]
    f = x ^ g - M
    return [int(i[0]) for i in f.monic().roots()]


c = 204384474875628990804496315735508023717499220909413449050868658084284187670628949761107184746708810539920536825856744947995442111688188562682921193868294477052992835394998910706435735040133361347697720913541458302074252626700854595868437809272878960638744881154520946183933043843588964174947340240510756356766

p = 102397419546952293033860597727650152144175130286102358700580521651161981691864932442389800376284315897109792547767071136122457986326994452907466660551539601
q = 196918114513369794295885764860865677200336789011735305193424080098388426330509485466134231492854453648288062591859752184850880742936527794052820501060652747
n = p*q
e = 0xE18E

res1 = part_roots(n, c, e, p)
res2 = part_roots(n, c, e, q)

for i in res1:
    for j in res2:
        m = crt([i, j], [p, q])
#         print(long_to_bytes(m))
        try:
            print(long_to_bytes(m).decode())
        except:
            pass

# 56092817b75f15df05}

flag{75811c6d95770d56092817b75f15df05}

XR4

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]]

异或加密，直接把data抄一遍就解出来了

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

Ez_Calculate | Review

题目：

task.py

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")

data.txt

problem1 = 24819077530766367166035941051823834496451802693325219476153953490742162231345380863781267094224914358021972805811737102184859249919313532073566493054398702269142565372985584818560322911207851760003915310535736092154713396343146403645986926080307669092998175883480679019195392639696872929250699367519967334248
problem2 = 20047847761237831029338089120460407946040166929398007572321747488189673799484690384806832406317298893135216999267808940360773991216254295946086409441877930687132524014042802810607804699235064733393301861594858928571425025486900981252230771735969897010173299098677357738890813870488373321839371734457780977243838253195895485537023584305192701526016
n = 86262122894918669428795269753754618836562727502569381672630582848166228286806362453183099819771689423205156909662196526762880078792845161061353312693752568577607175166060900619163231849790003982326663277243409696279313372337685740601191870965951317590823292785776887874472943335746122798330609540525922467021
c = 74962027356320017542746842438347279031419999636985213695851878703229715143667648659071242394028952959096683055640906478244974899784491598741415530787571499313545501736858104610426804890565497123850685161829628373760791083545457573498600656412030353579510452843445377415943924958414311373173951242344875240776
-------------------------
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]
-------------------------
What you need to submit is Flags!

Part1

k可以爆破，二项式分解得到 pow(p-q,e,n) == (pow(p,e,n)+pow(q,e,n))，两式相加即可得到 pow(p,e,n)。

k = randint(1, 999)
problem1 = (pow(p,e,n)-pow(q,e,n)) % n
problem2 = pow(p-q,e,n)*pow(e,k,n)

取gcd即可得到p

from Crypto.Util.number import *

problem1 = 24819077530766367166035941051823834496451802693325219476153953490742162231345380863781267094224914358021972805811737102184859249919313532073566493054398702269142565372985584818560322911207851760003915310535736092154713396343146403645986926080307669092998175883480679019195392639696872929250699367519967334248
problem2 = 20047847761237831029338089120460407946040166929398007572321747488189673799484690384806832406317298893135216999267808940360773991216254295946086409441877930687132524014042802810607804699235064733393301861594858928571425025486900981252230771735969897010173299098677357738890813870488373321839371734457780977243838253195895485537023584305192701526016
n = 86262122894918669428795269753754618836562727502569381672630582848166228286806362453183099819771689423205156909662196526762880078792845161061353312693752568577607175166060900619163231849790003982326663277243409696279313372337685740601191870965951317590823292785776887874472943335746122798330609540525922467021
c = 74962027356320017542746842438347279031419999636985213695851878703229715143667648659071242394028952959096683055640906478244974899784491598741415530787571499313545501736858104610426804890565497123850685161829628373760791083545457573498600656412030353579510452843445377415943924958414311373173951242344875240776

e = 0x10000

for k in range(1000):
    try:
        x = inverse(pow(e, k, n), n)
    except:
        continue
    p = GCD((problem1 + problem2 * x) % n, n)
    # print(p)
    if p == 1:
        continue
    q = n // p
    print(f"p = {p}")
    print(f"q = {q}")
    break

p = 9586253455468582613875015189854230646329578628731744411408644831684238720919107792959420247980417763684885397749546095133107188260274536708721056484419031
q = 8998523072192453101232205847855618180700579235012899613083663121402246420191771909612939404791268078655630846054784775118256720627970477420936836352759291
# CRYPTO_ALGORIT

e与phi不互素，套脚本：

def quick_rooting(n: int, r: int, p: int, all: bool = False):
    """
    在特定条件下，快速求解有限域下的n次方根
    
    参数:
        delta (int): 待开根数
        r (int): 开根的次数，要满足r能整除q
        q (int): 模数，为质数
        all (int): 是否返回所有解，默认为False，返回一个根。
    """
    if pow(n, (p - 1) // gcd(p - 1, r), p) != 1:
        raise Exception(f"{n}不是{r}次剩余")
        
    if (p + r - 1) % (r ** 2) != 0:
        raise Exception("快速开根需要满足r^2整除p+r-1")
    
    root = pow(n, (p+r-1)//(r**2), p)
    
    if not all:
        return root
    
    roots = [int(root)]
    while len(roots) < r:
        a = randint(2, p - 1)
        res = pow(a, (p - 1) // r, p) * root % p
        if res not in roots:
            roots.append(int(res))
    return roots
    

def rooting(c, e, p):
    # 将e约简到可逆，e_为余下的因数。
    e_ = 1
    while GCD(e, (p - 1)) != 1:
        e_ *= GCD(e, (p - 1))
        e //= GCD(e, (p - 1))
    
    d = inverse(e, p-1)
    c = pow(c, d, p)
    
    # 分解e_，简化计算
    expanded_factors = []
    for prime, exponent in factor(e_):
        expanded_factors.extend([prime] * exponent)
    
    cs = [c]
    ms = []
    for r in expanded_factors:
        ms = []
        for c in cs:
            # 检查c是否为r次剩余
            if pow(c, (p - 1) // gcd(p - 1, r), p) == 1:
                if (p+r-1)%(r**2) == 0:
                    ms += quick_rooting(c, r, p, True)
                else:
                    ms += AMM(c, r, p, True)
        cs = ms
            
    return sorted(ms)

p = 9586253455468582613875015189854230646329578628731744411408644831684238720919107792959420247980417763684885397749546095133107188260274536708721056484419031
q = 8998523072192453101232205847855618180700579235012899613083663121402246420191771909612939404791268078655630846054784775118256720627970477420936836352759291
n = 86262122894918669428795269753754618836562727502569381672630582848166228286806362453183099819771689423205156909662196526762880078792845161061353312693752568577607175166060900619163231849790003982326663277243409696279313372337685740601191870965951317590823292785776887874472943335746122798330609540525922467021
c = 74962027356320017542746842438347279031419999636985213695851878703229715143667648659071242394028952959096683055640906478244974899784491598741415530787571499313545501736858104610426804890565497123850685161829628373760791083545457573498600656412030353579510452843445377415943924958414311373173951242344875240776
e = 0x10000

res1 = rooting(c, e, p)
res2 = rooting(c, e, q)
for i in res1:
    for j in res2:
        m = crt([i, j], [p, q])
        try:
            print(long_to_bytes(m).decode())
        except:
            pass
# CRYPTO_ALGORIT

Part2

背包加密，但是私钥给了。

from Crypto.Util.number import *
from random import randint
from hashlib import md5

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 decrypt(c):
    byte = 0
    bit_array = []
    for r in reversed(R):
        if c >= r:
            bit_array.append(1)
            c -= r
        else:
            bit_array.append(0)
    bit_array = bit_array[::-1]
    num = int("".join(str(bit) for bit in bit_array), 2)

    return bytes([num])


A_ = inverse(A, B)
m = b""
for s in S_list:
    m += decrypt((A_ * s) % B)

print(m)

# CRYPTO_ALGORIT
# HMS_WELL_DONE
flag1 = b"CRYPTO_ALGORIT"
flag2 = b"HMS_WELL_DONE"

flag = "flag{" + md5(flag1 + flag2).hexdigest()[::-1] + "}"
print(flag)
# flag{64f67374264b7621650b1de4dbc5f924}

Logos | Review

题目是三道离散对数：

from Crypto.Cipher import AES
from hashlib import sha256
from Crypto.Util.number import *
from Crypto.Util.Padding import pad

message = b'xxxxxx'
flag = 'flag{' + sha256(message).hexdigest()[32:][::-1] + '}'

n = getPrime(1024) * getPrime(1024)
part1 = getPrime(50)
m1 = b'zzz'
m2 = b':\x98\xf6\xe0\x82$'
m3 = b'\x1c\x08\xeey\x8a\xaa+-('
c1 = pow(bytes_to_long(m1),part1,n)
c2 = pow(bytes_to_long(m2),part1,n)
c3 = pow(bytes_to_long(m3),part1,n)
print("c1 = ",c1)
print("c2 = ",c2)
print("c3 = ",c3)
print('-------')

part2 = getPrime(80)
mod = getPrime(16)

R.<x> = PolynomialRing(GF(mod))
N = 25084*x^255 + 32363*x^254 + 21665*x^253 + 24571*x^252 + 20587*x^251 + 17472*x^250 + 30654*x^249 + 31322*x^248 + 23385*x^247 + 14049*x^246 + 27853*x^245 + 18183*x^244 + 33130*x^243 + 29218*x^242 + 3412*x^241 + 28875*x^240 + 1551*x^239 + 15231*x^238 + 32794*x^237 + 8541*x^236 + 23025*x^235 + 21145*x^234 + 11858*x^233 + 34388*x^232 + 21092*x^231 + 22355*x^230 + 1768*x^229 + 5868*x^228 + 1502*x^227 + 30644*x^226 + 24646*x^225 + 32356*x^224 + 27350*x^223 + 34810*x^222 + 27676*x^221 + 24351*x^220 + 9218*x^219 + 27073*x^218 + 21176*x^217 + 2139*x^216 + 8244*x^215 + 1887*x^214 + 3854*x^213 + 24362*x^212 + 10981*x^211 + 14237*x^210 + 28663*x^209 + 32272*x^208 + 29911*x^207 + 13575*x^206 + 15955*x^205 + 5367*x^204 + 34844*x^203 + 15036*x^202 + 7662*x^201 + 16816*x^200 + 1051*x^199 + 16540*x^198 + 17738*x^197 + 10212*x^196 + 4180*x^195 + 33126*x^194 + 13014*x^193 + 16584*x^192 + 10139*x^191 + 27520*x^190 + 116*x^189 + 28197*x^188 + 31755*x^187 + 10917*x^186 + 28271*x^185 + 1152*x^184 + 6118*x^183 + 27171*x^182 + 14265*x^181 + 905*x^180 + 13776*x^179 + 854*x^178 + 5397*x^177 + 14898*x^176 + 1388*x^175 + 14058*x^174 + 6871*x^173 + 13508*x^172 + 3102*x^171 + 20438*x^170 + 29122*x^169 + 17072*x^168 + 23021*x^167 + 29879*x^166 + 28424*x^165 + 8616*x^164 + 21771*x^163 + 31878*x^162 + 33793*x^161 + 9238*x^160 + 23751*x^159 + 24157*x^158 + 17665*x^157 + 34015*x^156 + 9925*x^155 + 2981*x^154 + 24715*x^153 + 13223*x^152 + 1492*x^151 + 7548*x^150 + 13335*x^149 + 24773*x^148 + 15147*x^147 + 25234*x^146 + 24394*x^145 + 27742*x^144 + 29033*x^143 + 10247*x^142 + 22010*x^141 + 18634*x^140 + 27877*x^139 + 27754*x^138 + 13972*x^137 + 31376*x^136 + 17211*x^135 + 21233*x^134 + 5378*x^133 + 27022*x^132 + 5107*x^131 + 15833*x^130 + 27650*x^129 + 26776*x^128 + 7420*x^127 + 20235*x^126 + 2767*x^125 + 2708*x^124 + 31540*x^123 + 16736*x^122 + 30955*x^121 + 14959*x^120 + 13171*x^119 + 5450*x^118 + 20204*x^117 + 18833*x^116 + 33989*x^115 + 25970*x^114 + 767*x^113 + 16400*x^112 + 34931*x^111 + 7923*x^110 + 33965*x^109 + 12199*x^108 + 11788*x^107 + 19343*x^106 + 33039*x^105 + 13475*x^104 + 15822*x^103 + 20921*x^102 + 25100*x^101 + 9771*x^100 + 5272*x^99 + 34002*x^98 + 16026*x^97 + 23104*x^96 + 33331*x^95 + 11944*x^94 + 5428*x^93 + 11838*x^92 + 30854*x^91 + 18595*x^90 + 5226*x^89 + 23614*x^88 + 5611*x^87 + 34572*x^86 + 17035*x^85 + 16199*x^84 + 26755*x^83 + 10270*x^82 + 25206*x^81 + 30800*x^80 + 21714*x^79 + 2088*x^78 + 3785*x^77 + 9626*x^76 + 25706*x^75 + 24807*x^74 + 31605*x^73 + 5292*x^72 + 17836*x^71 + 32529*x^70 + 33088*x^69 + 16369*x^68 + 18195*x^67 + 22227*x^66 + 8839*x^65 + 27975*x^64 + 10464*x^63 + 29788*x^62 + 15770*x^61 + 31095*x^60 + 276*x^59 + 25968*x^58 + 14891*x^57 + 23490*x^56 + 34563*x^55 + 29778*x^54 + 26719*x^53 + 28611*x^52 + 1633*x^51 + 28335*x^50 + 18278*x^49 + 33901*x^48 + 13451*x^47 + 30759*x^46 + 19192*x^45 + 31002*x^44 + 11733*x^43 + 29274*x^42 + 11756*x^41 + 6880*x^40 + 11492*x^39 + 7151*x^38 + 28624*x^37 + 29566*x^36 + 33986*x^35 + 5726*x^34 + 5040*x^33 + 14730*x^32 + 7443*x^31 + 12168*x^30 + 24201*x^29 + 20390*x^28 + 15087*x^27 + 18193*x^26 + 19796*x^25 + 32514*x^24 + 25252*x^23 + 15090*x^22 + 2653*x^21 + 29310*x^20 + 4037*x^19 + 6440*x^18 + 16780*x^17 + 1891*x^16 + 20592*x^15 + 11890*x^14 + 25769*x^13 + 29259*x^12 + 23814*x^11 + 17565*x^10 + 16797*x^9 + 34151*x^8 + 20893*x^7 + 2807*x^6 + 209*x^5 + 3217*x^4 + 8801*x^3 + 21964*x^2 + 16286*x + 1207

S.<x> = R.quotient(N)
g = x
c = g ^ part2
print("mod = ",mod)
print("c = ",c)
print('-------')

A =  [
     [1287397632974625907369332145667695136576732725719,  999149001044306271168727399637009399486427921379,   1046504160269652701583906344218556291030141088947,  724446625683754938181565321149725788430461092168,    1071845980147173642753960259602135592110139561915],
     [947603660931904341080240982051313712707367037453,   312289846563741934103580532543082761760226637905,   494739786803547247505263837170488583876166831850,   680540462980071181450018491798299105995449257198,    2602258415762368797405060707505977243346704576],
     [996213673531855992829525358578006610606634622631,   1025711294257038288640877971869685565227647136954,  1432432135773706484846126533752827108541355741973,  1238541870126055576875033883691918425137600727481,   1130938956963588695293783764965618873887596017827],
     [1320933266015680090206505704792362493057963931979,  1151746112645644166669332171392580649376526147475,  117512451110908867093773368598681106589771485221,   78071463743800894350883457304401524272336187149,     350437511649326676405126284689545814008237687775],
     [438339253001275654203062260777687750937184662400,   372483950165136927369598298270629892810999203086,   859008773869616460027135965589262417694174453098,   1174526536643808668299968641952541506024584582818,   13201859260259503932772826643483081858286638179]
    ]

p = 1461501637330902918203684832716283019655932542983
A=Matrix(GF(p),A)
part3=randint(1,p-1)
enc=A ^ part3
print(enc)
print('-------')

All = part1 + part2 + part3
key = md5(str(All).encode()).hexdigest()[:16]
cipher = AES.new(key.encode(),AES.MODE_ECB)
CiperText = cipher.encrypt(pad(message,16))
print("CiperText =",CiperText)
print('What you need to submit is flag!')



'''
c1 = 1790064029876341976237307392954303240683485154655604205702671802338084953503431714871972122706034874742568072261191119160763863137961475625002894844004891260697595019907465755278638262147762379394415601861969179328855097462092631535981296001537399551639314331857176486214166299414062589768890263443278044795056175271819593655383503567679594909946112809736720406543448907122361577115534036883997133013430910162633465469329414746934054773560341062981310424264474787644557966610302754961777570611276912565113137718226850416211606074094264178783078305184709084902846670288088184932348269365506181921773002330580679734918
c2 = 17225757435575450389818088399433095156697021573983807106939124691102393835731406576540737759268850620280271361657087639901664008137854522875110325269252629052534860844747481251299546880445923665167570042341188891834337386413163198062248198462483926604076945786774091543309003786342127373409686595299934993139942352031396769039365555320211251090663701937628135476848609501115621384642389611313117199736967190795765167440771370922150598580998931016742537348664293083640407386888452849713466310048608615223994959668995233158600361723621126320585856609763844794654347576059465336943945067547715844981502578084903841428173
c3 = 6127501106046614276456935443305216078919479284921436149700502985365827297723002319904262457562294621244877794577751091983493467924877003070506852982421104959014095295275838345680174716500487745058844786649396734458375692717731311227458816076330431556974809846475830035624319565838255507062053820557011587735952469535859804356636312852847577634117557915374639542142876241686212680612046651342956091409853542776232386505921847772358725001821126108481098669654725854622292299844253696513046953513069393536282920810525837541811955323956831934298727480562864749898968182001537192475368582272947583927642428256534191002062
-------
mod = 60901
c = 30973*x^254 + 30844*x^253 + 7870*x^252 + 4082*x^251 + 18592*x^250 + 34047*x^249 + 53996*x^248 + 58679*x^247 + 57655*x^246 + 13454*x^245 + 30443*x^244 + 48856*x^243 + 23838*x^242 + 30886*x^241 + 48589*x^240 + 50619*x^239 + 42639*x^238 + 54735*x^237 + 54955*x^236 + 52741*x^235 + 41220*x^234 + 36173*x^233 + 9481*x^232 + 26002*x^231 + 28583*x^230 + 43331*x^229 + 14233*x^228 + 13795*x^227 + 11776*x^226 + 45901*x^225 + 23086*x^224 + 70*x^223 + 57985*x^222 + 52714*x^221 + 43922*x^220 + 49897*x^219 + 60845*x^218 + 22310*x^217 + 42708*x^216 + 57808*x^215 + 10614*x^214 + 30350*x^213 + 292*x^212 + 55663*x^211 + 50583*x^210 + 59438*x^209 + 57063*x^208 + 42842*x^207 + 20579*x^206 + 35796*x^205 + 42287*x^204 + 51707*x^203 + 25546*x^202 + 42414*x^201 + 48261*x^200 + 24008*x^199 + 55811*x^198 + 8913*x^197 + 58858*x^196 + 23767*x^195 + 59525*x^194 + 27750*x^193 + 4283*x^192 + 2737*x^191 + 39854*x^190 + 55954*x^189 + 50942*x^188 + 29950*x^187 + 38369*x^186 + 35469*x^185 + 32119*x^184 + 49311*x^183 + 12714*x^182 + 56593*x^181 + 57898*x^180 + 10885*x^179 + 11148*x^178 + 31621*x^177 + 45545*x^176 + 26021*x^175 + 35169*x^174 + 52724*x^173 + 60068*x^172 + 46585*x^171 + 56041*x^170 + 39233*x^169 + 49111*x^168 + 34393*x^167 + 31721*x^166 + 22836*x^165 + 31842*x^164 + 32651*x^163 + 56840*x^162 + 29985*x^161 + 39397*x^160 + 32411*x^159 + 12326*x^158 + 35303*x^157 + 36163*x^156 + 53507*x^155 + 37721*x^154 + 11967*x^153 + 17944*x^152 + 11907*x^151 + 22737*x^150 + 18174*x^149 + 29759*x^148 + 39971*x^147 + 43901*x^146 + 43588*x^145 + 23780*x^144 + 46281*x^143 + 39243*x^142 + 60028*x^141 + 11114*x^140 + 12727*x^139 + 45561*x^138 + 56668*x^137 + 55869*x^136 + 18422*x^135 + 34872*x^134 + 14945*x^133 + 17324*x^132 + 33915*x^131 + 41226*x^130 + 3845*x^129 + 38559*x^128 + 4456*x^127 + 7698*x^126 + 13557*x^125 + 50698*x^124 + 43608*x^123 + 34467*x^122 + 49204*x^121 + 43371*x^120 + 9099*x^119 + 41268*x^118 + 48971*x^117 + 6915*x^116 + 5040*x^115 + 32017*x^114 + 24391*x^113 + 52984*x^112 + 47532*x^111 + 56022*x^110 + 28678*x^109 + 5349*x^108 + 24013*x^107 + 59749*x^106 + 9908*x^105 + 14074*x^104 + 4281*x^103 + 47732*x^102 + 52807*x^101 + 11229*x^100 + 51198*x^99 + 18953*x^98 + 39935*x^97 + 20141*x^96 + 16426*x^95 + 1731*x^94 + 27518*x^93 + 46175*x^92 + 52067*x^91 + 3097*x^90 + 48882*x^89 + 36760*x^88 + 11227*x^87 + 31334*x^86 + 26083*x^85 + 2212*x^84 + 33391*x^83 + 13452*x^82 + 22866*x^81 + 59087*x^80 + 29840*x^79 + 45797*x^78 + 55257*x^77 + 6147*x^76 + 42650*x^75 + 45858*x^74 + 35593*x^73 + 12980*x^72 + 7094*x^71 + 26326*x^70 + 36941*x^69 + 38665*x^68 + 24926*x^67 + 49624*x^66 + 57611*x^65 + 19907*x^64 + 25569*x^63 + 26082*x^62 + 25232*x^61 + 49743*x^60 + 5299*x^59 + 20453*x^58 + 14107*x^57 + 26463*x^56 + 27491*x^55 + 41071*x^54 + 49263*x^53 + 56277*x^52 + 38917*x^51 + 24792*x^50 + 51915*x^49 + 41877*x^48 + 47022*x^47 + 46105*x^46 + 56256*x^45 + 51426*x^44 + 46176*x^43 + 54895*x^42 + 36054*x^41 + 1196*x^40 + 47104*x^39 + 3037*x^38 + 19154*x^37 + 49011*x^36 + 34506*x^35 + 42205*x^34 + 4275*x^33 + 49958*x^32 + 40629*x^31 + 32093*x^30 + 51447*x^29 + 26866*x^28 + 26439*x^27 + 40618*x^26 + 29193*x^25 + 37794*x^24 + 21065*x^23 + 20790*x^22 + 42873*x^21 + 44153*x^20 + 15265*x^19 + 31199*x^18 + 34847*x^17 + 22036*x^16 + 21321*x^15 + 28901*x^14 + 606*x^13 + 8767*x^12 + 20990*x^11 + 37318*x^10 + 23961*x^9 + 42977*x^8 + 41805*x^7 + 17314*x^6 + 44256*x^5 + 8873*x^4 + 36862*x^3 + 18983*x^2 + 3678*x + 20257
-------
[1137231678649111986418426323705488757362052256248 1275754870226546368142822180985385195928528472654  557214834104097871640664204909994937052450001975  145023493602872260881347708055585443650046405883 1283775394766152537214910003858987990641686322701]
[  24415365646755646195923685875204038532042541292 1086865496975097236094977923939666531485988223762  264094572819537749834323988580892885749606164559  124894655851287206231281210808920274920094831556  805696500662130854264198837242747230244197497780]
[ 636006128467308856088758448583963669099165463947 1237371300833477443312465203816697781387842264162  604255884531384974902659027005713172746665109930  817218249105281370168272878970454269414272716916 1171583331700722572405309782163554543142354039203]
[ 781666471957305023083056789896602008387817162830 1017674048051642313127046068977583159908007389751  719490009837934718274681654903158194668681130231 1198403822627688285330051549565405965877125490562  952841098005275617732494903412498336078112455711]
[ 989519235306974935468589452384626792088752492129  791819020512220835032324102003950629519764822776  698519597848113226815005327846800302301395708484 1265902948669118247882299269136507266567345180542  889147071870110758089365859462562765264413376867]
-------
CiperText = b"~\x8f\x8b>u\x94\x89F\x93\xf1x\x97\x8cp\x02\xfc\x99C\xc6\x0e\xf1L\xff#GM'^1\xca\xa3\x1a"
What you need to submit is flag!
'''

message = b'xxxxxx'
flag = 'flag{' + sha256(message).hexdigest()[32:][::-1] + '}'

All = part1 + part2 + part3
key = md5(str(All).encode()).hexdigest()[:16]
cipher = AES.new(key.encode(),AES.MODE_ECB)
CiperText = cipher.encrypt(pad(message,16))
print("CiperText =",CiperText)
print('What you need to submit is flag!')
'''
CiperText = b"~\x8f\x8b>u\x94\x89F\x93\xf1x\x97\x8cp\x02\xfc\x99C\xc6\x0e\xf1L\xff#GM'^1\xca\xa3\x1a"
What you need to submit is flag!
'''

Part1

n = getPrime(1024) * getPrime(1024)
part1 = getPrime(50)
m1 = b'zzz'
m2 = b':\x98\xf6\xe0\x82$'
m3 = b'\x1c\x08\xeey\x8a\xaa+-('
c1 = pow(bytes_to_long(m1),part1,n)
c2 = pow(bytes_to_long(m2),part1,n)
c3 = pow(bytes_to_long(m3),part1,n)
print("c1 = ",c1)
print("c2 = ",c2)
print("c3 = ",c3)

'''
c1 = 1790064029876341976237307392954303240683485154655604205702671802338084953503431714871972122706034874742568072261191119160763863137961475625002894844004891260697595019907465755278638262147762379394415601861969179328855097462092631535981296001537399551639314331857176486214166299414062589768890263443278044795056175271819593655383503567679594909946112809736720406543448907122361577115534036883997133013430910162633465469329414746934054773560341062981310424264474787644557966610302754961777570611276912565113137718226850416211606074094264178783078305184709084902846670288088184932348269365506181921773002330580679734918
c2 = 17225757435575450389818088399433095156697021573983807106939124691102393835731406576540737759268850620280271361657087639901664008137854522875110325269252629052534860844747481251299546880445923665167570042341188891834337386413163198062248198462483926604076945786774091543309003786342127373409686595299934993139942352031396769039365555320211251090663701937628135476848609501115621384642389611313117199736967190795765167440771370922150598580998931016742537348664293083640407386888452849713466310048608615223994959668995233158600361723621126320585856609763844794654347576059465336943945067547715844981502578084903841428173
c3 = 6127501106046614276456935443305216078919479284921436149700502985365827297723002319904262457562294621244877794577751091983493467924877003070506852982421104959014095295275838345680174716500487745058844786649396734458375692717731311227458816076330431556974809846475830035624319565838255507062053820557011587735952469535859804356636312852847577634117557915374639542142876241686212680612046651342956091409853542776232386505921847772358725001821126108481098669654725854622292299844253696513046953513069393536282920810525837541811955323956831934298727480562864749898968182001537192475368582272947583927642428256534191002062
'''

注意到m1、m2、m3可能存在规律，发现m2是m1的平方，m3为三次方。

from Crypto.Cipher import AES
from hashlib import sha256
from Crypto.Util.number import *
from Crypto.Util.Padding import pad

m1 = b"zzz"
m2 = b":\x98\xf6\xe0\x82$"
m3 = b"\x1c\x08\xeey\x8a\xaa+-("

print(bytes_to_long(m1))
print(bytes_to_long(m2))
print(bytes_to_long(m3))
print(pow(bytes_to_long(m1), 2))
print(pow(bytes_to_long(m1), 3))

'''
8026746
64428651348516
517152419497095408936
64428651348516
517152419497095408936
'''

可以求得n，接下来就是一个离散对数问题

n = gcd(pow(c1, 2) - c2, pow(c1, 3) - c3)
print(n)

由题意可知要求离散对数的范围(1, 2**50)，于是采用 discrete_log_lambda

discrete_log_lambda(mod(c1, n), mod(m1, n), (1, 2**50))
# 768287583817231

解出part1

Part2

part2 = getPrime(80)
mod = getPrime(16)

R.<x> = PolynomialRing(GF(mod))
N = 25084*x^255 + 32363*x^254 + 21665*x^253 + 24571*x^252 + 20587*x^251 + 17472*x^250 + 30654*x^249 + 31322*x^248 + 23385*x^247 + 14049*x^246 + 27853*x^245 + 18183*x^244 + 33130*x^243 + 29218*x^242 + 3412*x^241 + 28875*x^240 + 1551*x^239 + 15231*x^238 + 32794*x^237 + 8541*x^236 + 23025*x^235 + 21145*x^234 + 11858*x^233 + 34388*x^232 + 21092*x^231 + 22355*x^230 + 1768*x^229 + 5868*x^228 + 1502*x^227 + 30644*x^226 + 24646*x^225 + 32356*x^224 + 27350*x^223 + 34810*x^222 + 27676*x^221 + 24351*x^220 + 9218*x^219 + 27073*x^218 + 21176*x^217 + 2139*x^216 + 8244*x^215 + 1887*x^214 + 3854*x^213 + 24362*x^212 + 10981*x^211 + 14237*x^210 + 28663*x^209 + 32272*x^208 + 29911*x^207 + 13575*x^206 + 15955*x^205 + 5367*x^204 + 34844*x^203 + 15036*x^202 + 7662*x^201 + 16816*x^200 + 1051*x^199 + 16540*x^198 + 17738*x^197 + 10212*x^196 + 4180*x^195 + 33126*x^194 + 13014*x^193 + 16584*x^192 + 10139*x^191 + 27520*x^190 + 116*x^189 + 28197*x^188 + 31755*x^187 + 10917*x^186 + 28271*x^185 + 1152*x^184 + 6118*x^183 + 27171*x^182 + 14265*x^181 + 905*x^180 + 13776*x^179 + 854*x^178 + 5397*x^177 + 14898*x^176 + 1388*x^175 + 14058*x^174 + 6871*x^173 + 13508*x^172 + 3102*x^171 + 20438*x^170 + 29122*x^169 + 17072*x^168 + 23021*x^167 + 29879*x^166 + 28424*x^165 + 8616*x^164 + 21771*x^163 + 31878*x^162 + 33793*x^161 + 9238*x^160 + 23751*x^159 + 24157*x^158 + 17665*x^157 + 34015*x^156 + 9925*x^155 + 2981*x^154 + 24715*x^153 + 13223*x^152 + 1492*x^151 + 7548*x^150 + 13335*x^149 + 24773*x^148 + 15147*x^147 + 25234*x^146 + 24394*x^145 + 27742*x^144 + 29033*x^143 + 10247*x^142 + 22010*x^141 + 18634*x^140 + 27877*x^139 + 27754*x^138 + 13972*x^137 + 31376*x^136 + 17211*x^135 + 21233*x^134 + 5378*x^133 + 27022*x^132 + 5107*x^131 + 15833*x^130 + 27650*x^129 + 26776*x^128 + 7420*x^127 + 20235*x^126 + 2767*x^125 + 2708*x^124 + 31540*x^123 + 16736*x^122 + 30955*x^121 + 14959*x^120 + 13171*x^119 + 5450*x^118 + 20204*x^117 + 18833*x^116 + 33989*x^115 + 25970*x^114 + 767*x^113 + 16400*x^112 + 34931*x^111 + 7923*x^110 + 33965*x^109 + 12199*x^108 + 11788*x^107 + 19343*x^106 + 33039*x^105 + 13475*x^104 + 15822*x^103 + 20921*x^102 + 25100*x^101 + 9771*x^100 + 5272*x^99 + 34002*x^98 + 16026*x^97 + 23104*x^96 + 33331*x^95 + 11944*x^94 + 5428*x^93 + 11838*x^92 + 30854*x^91 + 18595*x^90 + 5226*x^89 + 23614*x^88 + 5611*x^87 + 34572*x^86 + 17035*x^85 + 16199*x^84 + 26755*x^83 + 10270*x^82 + 25206*x^81 + 30800*x^80 + 21714*x^79 + 2088*x^78 + 3785*x^77 + 9626*x^76 + 25706*x^75 + 24807*x^74 + 31605*x^73 + 5292*x^72 + 17836*x^71 + 32529*x^70 + 33088*x^69 + 16369*x^68 + 18195*x^67 + 22227*x^66 + 8839*x^65 + 27975*x^64 + 10464*x^63 + 29788*x^62 + 15770*x^61 + 31095*x^60 + 276*x^59 + 25968*x^58 + 14891*x^57 + 23490*x^56 + 34563*x^55 + 29778*x^54 + 26719*x^53 + 28611*x^52 + 1633*x^51 + 28335*x^50 + 18278*x^49 + 33901*x^48 + 13451*x^47 + 30759*x^46 + 19192*x^45 + 31002*x^44 + 11733*x^43 + 29274*x^42 + 11756*x^41 + 6880*x^40 + 11492*x^39 + 7151*x^38 + 28624*x^37 + 29566*x^36 + 33986*x^35 + 5726*x^34 + 5040*x^33 + 14730*x^32 + 7443*x^31 + 12168*x^30 + 24201*x^29 + 20390*x^28 + 15087*x^27 + 18193*x^26 + 19796*x^25 + 32514*x^24 + 25252*x^23 + 15090*x^22 + 2653*x^21 + 29310*x^20 + 4037*x^19 + 6440*x^18 + 16780*x^17 + 1891*x^16 + 20592*x^15 + 11890*x^14 + 25769*x^13 + 29259*x^12 + 23814*x^11 + 17565*x^10 + 16797*x^9 + 34151*x^8 + 20893*x^7 + 2807*x^6 + 209*x^5 + 3217*x^4 + 8801*x^3 + 21964*x^2 + 16286*x + 1207

S.<x> = R.quotient(N)
g = x
c = g ^ part2
print("mod = ",mod)
print("c = ",c)
'''

mod = 60901
c = 30973*x^254 + 30844*x^253 + 7870*x^252 + 4082*x^251 + 18592*x^250 + 34047*x^249 + 53996*x^248 + 58679*x^247 + 57655*x^246 + 13454*x^245 + 30443*x^244 + 48856*x^243 + 23838*x^242 + 30886*x^241 + 48589*x^240 + 50619*x^239 + 42639*x^238 + 54735*x^237 + 54955*x^236 + 52741*x^235 + 41220*x^234 + 36173*x^233 + 9481*x^232 + 26002*x^231 + 28583*x^230 + 43331*x^229 + 14233*x^228 + 13795*x^227 + 11776*x^226 + 45901*x^225 + 23086*x^224 + 70*x^223 + 57985*x^222 + 52714*x^221 + 43922*x^220 + 49897*x^219 + 60845*x^218 + 22310*x^217 + 42708*x^216 + 57808*x^215 + 10614*x^214 + 30350*x^213 + 292*x^212 + 55663*x^211 + 50583*x^210 + 59438*x^209 + 57063*x^208 + 42842*x^207 + 20579*x^206 + 35796*x^205 + 42287*x^204 + 51707*x^203 + 25546*x^202 + 42414*x^201 + 48261*x^200 + 24008*x^199 + 55811*x^198 + 8913*x^197 + 58858*x^196 + 23767*x^195 + 59525*x^194 + 27750*x^193 + 4283*x^192 + 2737*x^191 + 39854*x^190 + 55954*x^189 + 50942*x^188 + 29950*x^187 + 38369*x^186 + 35469*x^185 + 32119*x^184 + 49311*x^183 + 12714*x^182 + 56593*x^181 + 57898*x^180 + 10885*x^179 + 11148*x^178 + 31621*x^177 + 45545*x^176 + 26021*x^175 + 35169*x^174 + 52724*x^173 + 60068*x^172 + 46585*x^171 + 56041*x^170 + 39233*x^169 + 49111*x^168 + 34393*x^167 + 31721*x^166 + 22836*x^165 + 31842*x^164 + 32651*x^163 + 56840*x^162 + 29985*x^161 + 39397*x^160 + 32411*x^159 + 12326*x^158 + 35303*x^157 + 36163*x^156 + 53507*x^155 + 37721*x^154 + 11967*x^153 + 17944*x^152 + 11907*x^151 + 22737*x^150 + 18174*x^149 + 29759*x^148 + 39971*x^147 + 43901*x^146 + 43588*x^145 + 23780*x^144 + 46281*x^143 + 39243*x^142 + 60028*x^141 + 11114*x^140 + 12727*x^139 + 45561*x^138 + 56668*x^137 + 55869*x^136 + 18422*x^135 + 34872*x^134 + 14945*x^133 + 17324*x^132 + 33915*x^131 + 41226*x^130 + 3845*x^129 + 38559*x^128 + 4456*x^127 + 7698*x^126 + 13557*x^125 + 50698*x^124 + 43608*x^123 + 34467*x^122 + 49204*x^121 + 43371*x^120 + 9099*x^119 + 41268*x^118 + 48971*x^117 + 6915*x^116 + 5040*x^115 + 32017*x^114 + 24391*x^113 + 52984*x^112 + 47532*x^111 + 56022*x^110 + 28678*x^109 + 5349*x^108 + 24013*x^107 + 59749*x^106 + 9908*x^105 + 14074*x^104 + 4281*x^103 + 47732*x^102 + 52807*x^101 + 11229*x^100 + 51198*x^99 + 18953*x^98 + 39935*x^97 + 20141*x^96 + 16426*x^95 + 1731*x^94 + 27518*x^93 + 46175*x^92 + 52067*x^91 + 3097*x^90 + 48882*x^89 + 36760*x^88 + 11227*x^87 + 31334*x^86 + 26083*x^85 + 2212*x^84 + 33391*x^83 + 13452*x^82 + 22866*x^81 + 59087*x^80 + 29840*x^79 + 45797*x^78 + 55257*x^77 + 6147*x^76 + 42650*x^75 + 45858*x^74 + 35593*x^73 + 12980*x^72 + 7094*x^71 + 26326*x^70 + 36941*x^69 + 38665*x^68 + 24926*x^67 + 49624*x^66 + 57611*x^65 + 19907*x^64 + 25569*x^63 + 26082*x^62 + 25232*x^61 + 49743*x^60 + 5299*x^59 + 20453*x^58 + 14107*x^57 + 26463*x^56 + 27491*x^55 + 41071*x^54 + 49263*x^53 + 56277*x^52 + 38917*x^51 + 24792*x^50 + 51915*x^49 + 41877*x^48 + 47022*x^47 + 46105*x^46 + 56256*x^45 + 51426*x^44 + 46176*x^43 + 54895*x^42 + 36054*x^41 + 1196*x^40 + 47104*x^39 + 3037*x^38 + 19154*x^37 + 49011*x^36 + 34506*x^35 + 42205*x^34 + 4275*x^33 + 49958*x^32 + 40629*x^31 + 32093*x^30 + 51447*x^29 + 26866*x^28 + 26439*x^27 + 40618*x^26 + 29193*x^25 + 37794*x^24 + 21065*x^23 + 20790*x^22 + 42873*x^21 + 44153*x^20 + 15265*x^19 + 31199*x^18 + 34847*x^17 + 22036*x^16 + 21321*x^15 + 28901*x^14 + 606*x^13 + 8767*x^12 + 20990*x^11 + 37318*x^10 + 23961*x^9 + 42977*x^8 + 41805*x^7 + 17314*x^6 + 44256*x^5 + 8873*x^4 + 36862*x^3 + 18983*x^2 + 3678*x + 20257
'''

多项式DLP问题，思路是通过分解多项式，计算出多项式的阶。

p = 60901
P = PolynomialRing(Zmod(p), name='x')
x = P.gen()

n = ...

c = ...
g = x
# print(g)

nfactors = n.factor()

s = 1
# print(nfactors)
for i in nfactors:
	s *= p**(i[0].degree()) - 1
    
print(s)

利用pohlig_hellman算法思想，利用阶，从原来的多项式环找出若干组阶数较小的子群。

在阶数较小的子群里，可以使用暴力破解直接找出在该模下的解。

这里的factors需要乘积大于x，质因数的次数均为1

def brute_dlp(gi, ci, n, lim):
    bi = gi
    for i in range(1, lim+1):
        if bi == ci:
            return i
        bi = (bi * gi) % n
    print("[-] NOT in the range")
    print("[-] Something's Wrong, you gotta check the range", lim)

def pohlig_hellman(g, c, s, n, factors):
    res = []
    modulus = []
    for q in factors:
        assert pow(g, s//q, n) != 1
        gi = pow(g, s//q, n)
        ci = pow(c, s//q, n)
        dlogi = brute_dlp(gi, ci, n, q)
        print("[+] dlog modulo {0} == {1}".format(q, dlogi))
        res.append(dlogi)
        modulus.append(q)
    print("\n[*] res = ", res)
    print("[*] modulus = ", modulus)
    dlog = CRT(res, modulus)
    print("\n[+] dlog modulo {0} == {1}".format(prod(modulus), dlog))
    return dlog


qe = [1249, 2281, 3121, 7489, 7937, 8009, 57809]
x = pohlig_hellman(g, c, s, n, qe)
print(x)
print(pow(g, x, n) == c)

Part3

A =  [
     [1287397632974625907369332145667695136576732725719,  999149001044306271168727399637009399486427921379,   1046504160269652701583906344218556291030141088947,  724446625683754938181565321149725788430461092168,    1071845980147173642753960259602135592110139561915],
     [947603660931904341080240982051313712707367037453,   312289846563741934103580532543082761760226637905,   494739786803547247505263837170488583876166831850,   680540462980071181450018491798299105995449257198,    2602258415762368797405060707505977243346704576],
     [996213673531855992829525358578006610606634622631,   1025711294257038288640877971869685565227647136954,  1432432135773706484846126533752827108541355741973,  1238541870126055576875033883691918425137600727481,   1130938956963588695293783764965618873887596017827],
     [1320933266015680090206505704792362493057963931979,  1151746112645644166669332171392580649376526147475,  117512451110908867093773368598681106589771485221,   78071463743800894350883457304401524272336187149,     350437511649326676405126284689545814008237687775],
     [438339253001275654203062260777687750937184662400,   372483950165136927369598298270629892810999203086,   859008773869616460027135965589262417694174453098,   1174526536643808668299968641952541506024584582818,   13201859260259503932772826643483081858286638179]
    ]

p = 1461501637330902918203684832716283019655932542983
A=Matrix(GF(p),A)
part3=randint(1,p-1)
enc=A ^ part3
print(enc)
'''
[1137231678649111986418426323705488757362052256248 1275754870226546368142822180985385195928528472654  557214834104097871640664204909994937052450001975  145023493602872260881347708055585443650046405883 1283775394766152537214910003858987990641686322701]
[  24415365646755646195923685875204038532042541292 1086865496975097236094977923939666531485988223762  264094572819537749834323988580892885749606164559  124894655851287206231281210808920274920094831556  805696500662130854264198837242747230244197497780]
[ 636006128467308856088758448583963669099165463947 1237371300833477443312465203816697781387842264162  604255884531384974902659027005713172746665109930  817218249105281370168272878970454269414272716916 1171583331700722572405309782163554543142354039203]
[ 781666471957305023083056789896602008387817162830 1017674048051642313127046068977583159908007389751  719490009837934718274681654903158194668681130231 1198403822627688285330051549565405965877125490562  952841098005275617732494903412498336078112455711]
[ 989519235306974935468589452384626792088752492129  791819020512220835032324102003950629519764822776  698519597848113226815005327846800302301395708484 1265902948669118247882299269136507266567345180542  889147071870110758089365859462562765264413376867]
'''

矩阵DLP问题，先把两个矩阵化为Jordan 标准型，一定有 G_Jor ^ k == H_Jor 。

n = 5
p = 1461501637330902918203684832716283019655932542983
A =  [
     [1287397632974625907369332145667695136576732725719,  999149001044306271168727399637009399486427921379,   1046504160269652701583906344218556291030141088947,  724446625683754938181565321149725788430461092168,    1071845980147173642753960259602135592110139561915],
     [947603660931904341080240982051313712707367037453,   312289846563741934103580532543082761760226637905,   494739786803547247505263837170488583876166831850,   680540462980071181450018491798299105995449257198,    2602258415762368797405060707505977243346704576],
     [996213673531855992829525358578006610606634622631,   1025711294257038288640877971869685565227647136954,  1432432135773706484846126533752827108541355741973,  1238541870126055576875033883691918425137600727481,   1130938956963588695293783764965618873887596017827],
     [1320933266015680090206505704792362493057963931979,  1151746112645644166669332171392580649376526147475,  117512451110908867093773368598681106589771485221,   78071463743800894350883457304401524272336187149,     350437511649326676405126284689545814008237687775],
     [438339253001275654203062260777687750937184662400,   372483950165136927369598298270629892810999203086,   859008773869616460027135965589262417694174453098,   1174526536643808668299968641952541506024584582818,   13201859260259503932772826643483081858286638179]
    ]
B = [
[1137231678649111986418426323705488757362052256248, 1275754870226546368142822180985385195928528472654,  557214834104097871640664204909994937052450001975,  145023493602872260881347708055585443650046405883, 1283775394766152537214910003858987990641686322701],
[  24415365646755646195923685875204038532042541292, 1086865496975097236094977923939666531485988223762,  264094572819537749834323988580892885749606164559,  124894655851287206231281210808920274920094831556,  805696500662130854264198837242747230244197497780],
[ 636006128467308856088758448583963669099165463947, 1237371300833477443312465203816697781387842264162,  604255884531384974902659027005713172746665109930,  817218249105281370168272878970454269414272716916, 1171583331700722572405309782163554543142354039203],
[ 781666471957305023083056789896602008387817162830, 1017674048051642313127046068977583159908007389751,  719490009837934718274681654903158194668681130231, 1198403822627688285330051549565405965877125490562,  952841098005275617732494903412498336078112455711],
[ 989519235306974935468589452384626792088752492129, 791819020512220835032324102003950629519764822776,  698519597848113226815005327846800302301395708484, 1265902948669118247882299269136507266567345180542,  889147071870110758089365859462562765264413376867],

]

G = matrix(GF(p), n, n, A)
H = matrix(GF(p), n, n, B)

G_Jor, P = G.jordan_form(transformation=True)
H_Jor = ~P * H * P

print(G_Jor, H_Jor)

根据Jordan矩阵幂的性质，有：

用 $\lambda ^k$​ 来计算的话，就转化成一个普通的离散对数问题，但这里p是质数，这样求解是不现实的。

观察到有二阶的Jordan块，可以这样计算：${\lambda \cdot k\lambda^{k-1} \over \lambda^k} = k$

print(559183611339497876626274395346600310434790450166*1445999247258403517429869962132770504989666494386//mod(89296138619835417622440666671100399525276976255,p))
# 1349606217237476689412459921843213653413245493841

Lunz | Review

题目：

from gmpy2 import *
from hashlib import md5
from Crypto.Util.number import *
from sympy import *

message= xxxxxx
flag = 'flag{'+md5(message).hexdigest()+'}'
p = getPrime(250)
q = getPrime(250)
assert p > q
n = p * q
e = 65537
phi = (p - 1) * (q - 1)
m = bytes_to_long(message)

Rod = getPrime(5)
I = Rod + len(str(Rod))
k = pow(p, Rod)
N = pow(p, I) * q
d1 = getPrime(2000)
d2 = nextprime(d1 + getPrime(1000))
e_1 = inverse(d1, (k * phi))
e_2 = inverse(d2, (k * phi))
c = pow(m,e,n)

print(f'e_1 = {e_1}')
print(f'e_2 = {e_2}')
print(f'N = {N}')
print(f'c = {c}')

'''
e_1 = 82194997342022315294741053886738801755778309600541058857582819748504178218029586817329075468608972333546628374485521400184402963163262742655834395020461909318434218408759432963056836775067368883981421937545474418669913878385887094077169817430600727448380867839881006626945685264795847634981886115304993041631628136473851886823203348581719499157160024911445745322632851807430667833753655691308910924573857543244114539188236171668917232064732826943767269915781685149029139160527731493869032783128334745336285887381730339030076359989916068723957137190717453844444310295759587221150214466448941257886222442167236946023762817554259376632788561021978493693907106048112804092814216335115732687289796860118449346995430040021434986438850327164942720764221862901423771813050035009824215701858655762362015399936372902250977067504212727000797315107722305123781901826260372964003794563854743545219568742418110422688701046616021356858226697543841486497087747712657259451317463305606428176259820286737051441530790573789113667728829662206604792772338461257413364281114387773723898692579006356294992480087943719304524239180738165046907648518521903103759650135544600045989005073217092319548855826667005381517104701733412698272841877137931516982117218225608581665569186933249196741845018511834844544414981555035250852425593826008902095047544747578876223640919793897386377693043508302048480183187157844710880574283128792866376629738280715200563980387359301445057462967819370931652504737823852714734612238853018373314636405639783626927974956276625788802184920232287559681505649010715237855787297487
e_2 = 64122187727334478098553301791077235625639260906174457891776938537038285044681517044012845849048601736428558240533921438302916819425025934973225885809211818189790751616476236608428883939142567650575711490758442310747755441704935369315756941517913927278315834043578627420785342974067333803699662844555926254529237244727534375719868122571102263698948560568991199459140903113110377348187789154257211144174068313381527709568528353000832605802816221054845418024982904708393369173181282816476354486665784983515352482857444378869032220101634114432689862478394556055683821860859875850463810707089022600492091988900749494653834344183398165673450567322248851844656051853665140912370242501422363643802099433464075348279168351216470702507184763811726619347630962848378345030258733023745716937574829941575439968121681130680029035679914270839488865298630191761404554917682318359040105408094069383752609384033750252033273237367286348132901330911746731313028201201829666439171480126966221386235253378104056860492430887542911057069064922503106602377697366238713631664125691688326647247196130005020196785674542444226248879704053916958067659235282907317204189657563756472135321212749728394030855236171882022720575781530559713342982915738876377997138645803111586794930317674671418213235709512822108628762122163509180516396190714181745562401480690794695504357318149941173322387551473154391773590129902904460707063967175869896093589115072753154541601856678428639567972972389015662258203030116017981880452852617106573566546377979964809041695581443921846407962542002308657128638193946859286314988046797
N = 102656930531199322819741252140491678150105419351766529874538711748132275448564771307360722552171375537683026622007355914428283082151916898177289187070426072926291492106641465649627537434157794722917637260699145843389666840049543908412560095077959882211825589332132276599874303904283043025693548669833873341870047913912621999637061842614129757738747471830515353303238598879492119215053598915979966987713596972485340880154399968932115163217865869501900443280198904159123615920434314722813266331356594627291390991620917101278912357563179937601640979627848865210601775650344306736790660313701201486095040763386101953164215547418558711931427566991637431502571542506126879340718877092334161213153414264305178444441322105028075272279719803323772887474280200116446155546883207025336629510198040921223947383148351118538936955587960864699371195348577704440637074984902582268297801426869733610791961700442325884107928801102939917348485659494161445611191032702931411943373025507028646608480404465118888160612254835642636918338195945924532076785555869644175634740376183788776866070595763835540459363210791067561851748019066365740696901460972148810521955774439455698118188397251439004448479552774584082231580786287223325608043496702909467028213189269213006257671486253673702248484360808080232590794281657899229350170579208321802542550971074214257670667703073786809404057399870771729816128206631959677706575636288453480381200130995605281214558104790905688084300620250244986530313845558200328099836053926424927054258719918440283781321096404237444926632626277340511034942882920173700503615281267616906850831057065875864766486942097938244757579499498498158569941529737537
c = 111039757154994940584340532334116972416069873553536764934313111792022839617044953410289031679957972488548299616330346859773349403234979916275715896896
'''

对e的两个同余方程变换可得 e1*e2*x-(e1-e2)=0 mod p^Rod，用coppersmith攻击可以获得一个符合条件的x

e1 = ...
e2 = ...
N = ...
c = ...

PR.<x> = PolynomialRing(Zmod(N))
f=e1*e2*x-(e1-e2)
f=f.monic()
f.small_roots(beta = 0.5, epsilon = 0.4, X = 2^1000)

此时的 gcd(e1*e2*x-(e1-e2), N) 为p的幂次，可以解出p和q

x = ...
factor(gcd(e1*e2*x-(e1-e2), N))
p = 1236684400644913665223349603970861082164187774906247864790683861970484371887
q = N // pow(p, 21)
assert N == pow(p, 21) * q
e = 65537
d = inverse(e, (p-1)*(q-1))
n = p*q
m = pow(c, d, n)
print(m)

message= long_to_bytes(int(m))
print(message)
from hashlib import md5
flag = 'flag{'+md5(message).hexdigest()+'}'
print(flag)