为什么出题人的rsa总是ez

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
#part 1

def pad(flag, bits=1024):
    pad = os.urandom(bits//8 - len(flag))
    return int.from_bytes(flag + pad, "big")

p = random_prime(2**1024)
q = random_prime(2**1024)
a = randint(0, 2**1024)
b = randint(0, 2**1024)
n = p * q
e = 0x10001
flag = b''
m = pad(flag)
assert m < n

c = pow(m, e, n)

print(f"c={c}")
print(f"n={n}")
print(f"h1={p + b * q}")
print(f"h2={a * p + q}")

# c=13148687178480196374316468746303529314940770955906554155276099558796308164996908275540972246587924459788286109602343699872884525600948529446071271042497049233796074202353913271513295267105242313572798635502497823862563815696165512523074252855130556615141836416629657088666030382516860597286299687178449351241568084947058615139183249169425517358363928345728230233160550711153414555500038906881581637368920188681358625561539325485686180307359210958952213244628802673969397681634295345372096628997329630862000359069425551673474533426265702926675667531063902318865506356674927615264099404032793467912541801255735763704043

# n=13718277507497477508850292481640653320398820265455820215511251843542886373380880887850571647060788265498378060163112689840208264538965960596605641194331300743676780910818492860412739541418029075802834265712602393103809065720527365081016381358333378953245379751008531500896923727040455566953960991908174586311899809864209624888469263612475732913062035036254077225370843701146080145441104733074178115602425412116325647598625157922655504918118208783230138448694045386019901732846478340735331718476554208157393418221315041837392020742062275999319586357229583509788489495876723122993592623230858393165458733055504467513549

# h1=6992022576367328281523272055384380182550712894467837916200781058620282657859189270338635886912232754034211897894637971546032107000253692739473463119025570291091085702056938901846349325941043398928197991115231668917435951127329817379935880511925882734157491821315858319170121031835598580384038723788681860763814776365440362143661999054338470989558459179388468943933975861549233231199667742564080001256192881732567616103760815633265325456143601649393547666835326272408622540044065067528568675569233240785553062685974593620235466519632833169291153478793523397788719000334929715524989845012633742964209311952378479134661

# h2=16731800146050995761642066586565348732313856101572403535951688869814016691871958158137790504490910445304384109605408840493227057830017039824412834989258703833576252634055087138315434304691218949240382395879124201923060510497916818961571111218224960267593032380037212325935576750663442553781924370849537501656957488833521657563900462052017695599020610911371304659875887924695896434699048696392210066253577839887826292569913713802634067508141124685789817330268562127695548527522031774601654778934513355315628270319037043809972087930951609429846675450469414212384044849089372435124609387061864545559812994515828333828939

#part 2

from Crypto.Util.number import *
from gmpy2 import *
a = random_prime()
b = random_prime()
g = random_prime()
h = 2*g*a*b+a+b
while not is_prime(h):
    a = random_prime()
    b = random_prime()
    g = random_prime()
    h = 2*g*a*b+a+b
N = 2*h*g+1
e from part1's flag
flag=b''
c=pow(bytes_to_long(flag),e,N)
print(N)
print(g)
print(c)
#N=10244621233521168199001177069337072125430662416754674144307553476569744623474797179990380824494968546110022341144527766891662229403969035901337876527595841503498459533492730326942662450786522178313517616168650624224723066308178042783540825899502172432884573844850572330970359712379107318586435848029783774998269247992706770665069866338710349292941829996807892349030660021792813986069535854445874069535737849684959397062724387110903918355074327499675776518032266136930264621047345474782910332154803497103199598761422179303240476950271702406633802957400888398042773978322395227920699611001956973796492459398737390290487
#g=2296316201623391483093360819129167852633963112610999269673854449302228853625418585609211427788830598219647604923279054340009043347798635222302374950707
#c=7522161394702437062976246147354737122573350166270857493289161875402286558096915490526439656281083416286224205494418845652940140144292045338308479237214749282932144020368779474518032067934302376430305635297260147830918089492765917640581392606559936829974748692299762475615766076425088306609448483657623795178727831373194757182797030376302086360751637238867384469269953187938304369668436238848537646544257504724753333177938997524154486602644412199535102323238852958634746165559537630341890450666170836721803871120344373143081664567068672230842855208267929484000179260292518351155693154372172449820053764896414799137097

题目分为两个部分，在第一部分中我可以得到第二部分所需要的e

这里我们发现p,q,a,b的数量级是相同的

现有等式 h1 = p + b * q

h2 = a * p + q

现对等式做如下变换 h1 * h2 − p * h1 − q * h2 ≡ 0 mod  n

h1 * h2 − p * h1 − q * h2 = kn

现在我们知道h1,h2

这里造格去打即可

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

c=13148687178480196374316468746303529314940770955906554155276099558796308164996908275540972246587924459788286109602343699872884525600948529446071271042497049233796074202353913271513295267105242313572798635502497823862563815696165512523074252855130556615141836416629657088666030382516860597286299687178449351241568084947058615139183249169425517358363928345728230233160550711153414555500038906881581637368920188681358625561539325485686180307359210958952213244628802673969397681634295345372096628997329630862000359069425551673474533426265702926675667531063902318865506356674927615264099404032793467912541801255735763704043

n=13718277507497477508850292481640653320398820265455820215511251843542886373380880887850571647060788265498378060163112689840208264538965960596605641194331300743676780910818492860412739541418029075802834265712602393103809065720527365081016381358333378953245379751008531500896923727040455566953960991908174586311899809864209624888469263612475732913062035036254077225370843701146080145441104733074178115602425412116325647598625157922655504918118208783230138448694045386019901732846478340735331718476554208157393418221315041837392020742062275999319586357229583509788489495876723122993592623230858393165458733055504467513549

t1=6992022576367328281523272055384380182550712894467837916200781058620282657859189270338635886912232754034211897894637971546032107000253692739473463119025570291091085702056938901846349325941043398928197991115231668917435951127329817379935880511925882734157491821315858319170121031835598580384038723788681860763814776365440362143661999054338470989558459179388468943933975861549233231199667742564080001256192881732567616103760815633265325456143601649393547666835326272408622540044065067528568675569233240785553062685974593620235466519632833169291153478793523397788719000334929715524989845012633742964209311952378479134661

t2=16731800146050995761642066586565348732313856101572403535951688869814016691871958158137790504490910445304384109605408840493227057830017039824412834989258703833576252634055087138315434304691218949240382395879124201923060510497916818961571111218224960267593032380037212325935576750663442553781924370849537501656957488833521657563900462052017695599020610911371304659875887924695896434699048696392210066253577839887826292569913713802634067508141124685789817330268562127695548527522031774601654778934513355315628270319037043809972087930951609429846675450469414212384044849089372435124609387061864545559812994515828333828939

brute = 2

for i in range(2^brute):

  for j in range(2^brute):

    L = Matrix(ZZ, [

      [1,0,0,2^brute*t1],

      [0,1,0,2^brute*t2],

      [0,0,2^(1024-brute),t1*i+t2*j-t1*t2],

      [0,0,0,n]

    ])

    L[:,-1:] *= n

    res = L.LLL()[0]

    p = 2^brute*abs(res[0])+i

    if(n % p == 0):

      q=n//p

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

      d=inverse(65537,phi)

      print(long_to_bytes(pow(c,d,n)))

      print(pow(c,d,n))

这样就得到了

1
b'flag{e_is_xevaf-cityf-fisof-ketaf-metaf-disef-nuvaf-cysuf-dosuf-getuf-cysuf-dasix,bubbleBabble}

这里e还需要用BubbleBabble解码（刚开始做的时候以为括号中的就是e导致一直没做出来╥﹏╥，感觉还是太急了）

1
e=81733668723981020451323

这一部分其实是有原题的的，在maple神的博客中有

看到第二部分

很明显的Common Prime RSA

通过分析，我们知道 p = 2 * g * a + 1

q = 2 * g * b + 1

其中 g ≈ n0.244 用脚本直接打就好

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
N=10244621233521168199001177069337072125430662416754674144307553476569744623474797179990380824494968546110022341144527766891662229403969035901337876527595841503498459533492730326942662450786522178313517616168650624224723066308178042783540825899502172432884573844850572330970359712379107318586435848029783774998269247992706770665069866338710349292941829996807892349030660021792813986069535854445874069535737849684959397062724387110903918355074327499675776518032266136930264621047345474782910332154803497103199598761422179303240476950271702406633802957400888398042773978322395227920699611001956973796492459398737390290487

g=2296316201623391483093360819129167852633963112610999269673854449302228853625418585609211427788830598219647604923279054340009043347798635222302374950707

e = 81733668723981020451323

enc=7522161394702437062976246147354737122573350166270857493289161875402286558096915490526439656281083416286224205494418845652940140144292045338308479237214749282932144020368779474518032067934302376430305635297260147830918089492765917640581392606559936829974748692299762475615766076425088306609448483657623795178727831373194757182797030376302086360751637238867384469269953187938304369668436238848537646544257504724753333177938997524154486602644412199535102323238852958634746165559537630341890450666170836721803871120344373143081664567068672230842855208267929484000179260292518351155693154372172449820053764896414799137097

gamma = 500/(1024*2)

cbits = ceil(nbits * (0.5 - 2 * gamma))

M = (N - 1) // (2 * g)

u = M // (2 * g)

v = M - 2 * g * u

GF = Zmod(N)

x = GF.random_element()

y = x ^ (2 * g)

\# c的范围大概与N^(0.5-2*gamma)很接近

c = bsgs(y, y ^ u, (2**(cbits-1), 2**(cbits+1)), operation='*')

\#(a, b, bounds, operation='*', identity=None, inverse=None, op=None)

ab = u - c

apb = v + 2 * g * c

P.<x> = ZZ[]

f = x ^ 2 - apb * x + ab

a = f.roots()

if a:

  a, b = a[0][0], a[1][0]

  p = 2 * g * a + 1

  q = 2 * g * b + 1

  assert p * q == N

from Crypto.Util.number import *

print(long_to_bytes(int(pow(enc,inverse(e,(p-1)*(q-1)),N))))
#b'flag{I wish you success in your cryptography career}'
#b'H&NCTF{I wish you success in your cryptography career}'

其中bsgs那一行可能是sage版本问题会报错，需要自己修改参数

这题目是改强网杯的，基本上就是原题，所以找强网杯的板子也可以打掉

哈基coke

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
import matplotlib.pyplot as plt
import cv2
import numpy as np
from PIL import Image
def arnold_encode(image, shuffle_times, a, b):
    """ Arnold shuffle for rgb image
    Args:
        image: input original rgb image
        shuffle_times: how many times to shuffle
    Returns:
        Arnold encode image
    """
    arnold_image = np.zeros(shape=image.shape)

    h, w = image.shape[0], image.shape[1]
    N = h
    
    for time in range(shuffle_times):
        for ori_x in range(h):
            for ori_y in range(w):
    
                new_x = (1*ori_x + b*ori_y)% N
                new_y = (a*ori_x + (a*b+1)*ori_y) % N
    
                arnold_image[new_x, new_y, :] = image[ori_x, ori_y, :]
    
        image = np.copy(arnold_image)
    
    cv2.imwrite('en_flag.png', arnold_image, [int(cv2.IMWRITE_PNG_COMPRESSION), 0])
    return arnold_image

img = cv2.imread('coke.png')
arnold_encode(img,6,9,1)

考察的是Arnold变换，比赛中有非常多的解，那么gpt肯定是梭出来的，也可以参考这篇博客和这篇

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
import cv2

import numpy as np

def arnold_decode(image, shuffle_times, a, b):

  """Arnold 逆置乱解密 (支持 RGB 图像)"""

  h, w = image.shape[0], image.shape[1]

  N = h

  decoded_image = np.zeros_like(image)

  for _ in range(shuffle_times):

    for new_x in range(h):

      for new_y in range(w):

        \# 逆向 Arnold 公式

        ori_x = ((a*b + 1) * new_x - b * new_y) % N

        ori_y = (-a * new_x + 1 * new_y) % N

        decoded_image[ori_x, ori_y, :] = image[new_x, new_y, :]

    image = np.copy(decoded_image)

  cv2.imwrite('decoded_flag.png', decoded_image)

  return decoded_image

lcgp

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 *

import gmpy2

random = [

  11250327355112956284720719987943941825496074893551827972877616718074592862130806975889275745497426515405562887727117008818863728803549848574821067056997423443681347885027000632462241968640893471352200125748453396098854283137158609264944692129301617338233670002547470932851350750870478630955328653729176440142198779254117385657086615711880537380965161180532127926250520546846863536247569437, 

  1289730679860726245234376434590068355673648326448223956572444944595048952808106413165882424967688302988257332835229651422892728384363094065438370663362237241013242843898967355558977974152917458085812489310623200114007728021151551927660975648884448177346441902806386690751359848832912607313329587047853601875294089502467524598036474193845319703759478494109845743765770254308199331552085163360820459311523382612948322756700518669154345145757700392164795583041949318636, 

  147853940073845086740348793965278392144198492906678575722238097853659884813579087132349845941828785238545905768867483183634111847434793587821166882679621234634787376562998606494582491550592596838027522285263597247798608351871499848571767008878373891341861704004755752362146031951465205665840079918938797056361771851047994530311215961536936283541887169156535180878864233663699607369701462321037824218572445283037132205269900255514050653933970174340553425147148993214797622395988788709572605943994223528210919230924346860415844639247799805670459, 

  7426988179463569301750073197586782838200202717435911385357661153208197570200804485303362695962843396307030986052311117232622043073376409347836815567322367321085387874196758434280075897513536063432730099103786733447352512984165432175254784494400699821500026196293994318206774720213317148132311223050562359314735977091536842516316149049281012797103790472349557847649282356393682360276814293256129426440381745354969522053841093229320186679875177247919985804406150542514337515002645320320069788390314900121917747534146857716743377658436154645197488134340819076585888700553005062311578963869641978771532330577371974731136, 

  10389979373355413148376869524987139791217158307590828693700943753512488757973725227850725013905113587408391654379552713436220790487026223039058296951420273907725324214990441639760825661323514381671141482079783647253661594138658677104054180912818864005556386671430082941396497098166887200556959866845325602873713813206312644590812141400536476615405444030140762980665885244721798105034497461675317071497925846844396796854201566038890503298824928152263774446268093725702310124363765630370263370678902342200494544961012407826314577564991676315451785987248633724138137813024481818431889574317602521878974976264742037227074

]

n = n=604805773885048132038788501528078428693141138274580426531445179173412328238102786863592612653315029009606622583856638282837864213048342883583286440071990592001905867027978355755042060684149344414810835371740304319571184567860694439564098306766474576403800046937218588251809179787769286393579687694925268985445059

d1 = random[1] - random[0]

d2 = random[2] - random[1]

d3 = random[3] - random[2]

d4 = random[4] - random[3]

T1 = d2^2 - d3*d1

T2 = d3^2 - d4*d2

m = gcd(T1, T2)

print("m bits:", m.nbits())  

print("is prime?", is_prime(m)) 

a = (random[2] - random[1]) * inverse_mod(random[1] - random[0], m) % m

b = (random[1] - a * random[0]) % m

assert (a * random[0] + b) % m == random[1]

assert (a * random[1] + b) % m == random[2]

c = (random[0] - b) * inverse_mod(a, m) % m

e = 2024

F = Zmod(n)

flag = discrete_log(F(c), F(e))

from Crypto.Util.number import long_to_bytes

flag_bytes = long_to_bytes(flag)

print("Flag:", flag_bytes)

考察的是lcg和离散对数

我们要先通过LCG求出c

这里给了我们五个seed的状态要我们恢复C

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

import gmpy2

output =  [11250327355112956284720719987943941825496074893551827972877616718074592862130806975889275745497426515405562887727117008818863728803549848574821067056997423443681347885027000632462241968640893471352200125748453396098854283137158609264944692129301617338233670002547470932851350750870478630955328653729176440142198779254117385657086615711880537380965161180532127926250520546846863536247569437, 1289730679860726245234376434590068355673648326448223956572444944595048952808106413165882424967688302988257332835229651422892728384363094065438370663362237241013242843898967355558977974152917458085812489310623200114007728021151551927660975648884448177346441902806386690751359848832912607313329587047853601875294089502467524598036474193845319703759478494109845743765770254308199331552085163360820459311523382612948322756700518669154345145757700392164795583041949318636, 147853940073845086740348793965278392144198492906678575722238097853659884813579087132349845941828785238545905768867483183634111847434793587821166882679621234634787376562998606494582491550592596838027522285263597247798608351871499848571767008878373891341861704004755752362146031951465205665840079918938797056361771851047994530311215961536936283541887169156535180878864233663699607369701462321037824218572445283037132205269900255514050653933970174340553425147148993214797622395988788709572605943994223528210919230924346860415844639247799805670459, 7426988179463569301750073197586782838200202717435911385357661153208197570200804485303362695962843396307030986052311117232622043073376409347836815567322367321085387874196758434280075897513536063432730099103786733447352512984165432175254784494400699821500026196293994318206774720213317148132311223050562359314735977091536842516316149049281012797103790472349557847649282356393682360276814293256129426440381745354969522053841093229320186679875177247919985804406150542514337515002645320320069788390314900121917747534146857716743377658436154645197488134340819076585888700553005062311578963869641978771532330577371974731136, 10389979373355413148376869524987139791217158307590828693700943753512488757973725227850725013905113587408391654379552713436220790487026223039058296951420273907725324214990441639760825661323514381671141482079783647253661594138658677104054180912818864005556386671430082941396497098166887200556959866845325602873713813206312644590812141400536476615405444030140762980665885244721798105034497461675317071497925846844396796854201566038890503298824928152263774446268093725702310124363765630370263370678902342200494544961012407826314577564991676315451785987248633724138137813024481818431889574317602521878974976264742037227074]

t = []

for i in range(1,len(output)):

  t.append(output[i]-output[i-1])

T = []

for i in range(1,len(t)-1):

  T.append(t[i+1]*t[i-1] - t[i]**2)

N = []

for i in range(len(T)-1):

  n = gmpy2.gcd(T[i],T[i+1])

  N.append(int(n))

for n in N:

  try:

    a = gmpy2.invert(t[0],n) * t[1] % n

    b = output[1] - a*output[0] % n

    a_ = gmpy2.invert(a,n)

    seed = a_ * (output[0] - b) % n

    flag = long_to_bytes(seed)

    print(seed)

    

    

  except:

    pass

得到c之后就是简单解个离散对数了

1
2
3
4
5
6
7
8
9
10
11
12
13
c=98136663393066487319477131255488756533037186459124433869847045986870213783395243380337142782779765255670853582334927187474123853371504168896312528278296763527266828907487342102002206806408616944398694810398049626860321901229014612541564249969665358849039818103044159048535403863928440335143886672949700153798350

m = 2024

n = 604805773885048132038788501528078428693141138274580426531445179173412328238102786863592612653315029009606622583856638282837864213048342883583286440071990592001905867027978355755042060684149344414810835371740304319571184567860694439564098306766474576403800046937218588251809179787769286393579687694925268985445059

 

g = Mod(m,n)

flag = discrete_log(c,g)

print(long_to_bytes(flag))

数据处理

拿到三血

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

import random

flag = b"H&NCTF{}"

btl = str(bytes_to_long(flag))

lowercase = '0123456789' 

uppercase = '7***4****5' 

table = ''.maketrans(lowercase, uppercase) 

new_flag = btl.translate(table)

n = 2 ** 512

m = random.randint(2, n - 1) | 1

c = pow(m, int(new_flag), n)

print('m = ' + str(m))

print('c = ' + str(c))

# m = 5084057673176634704877325918195984684237263100965172410645544705367004138917087081637515846739933954602106965103289595670550636402101057955537123475521383

# c = 2989443482952171039348896269189568991072039347099986172010150242445491605115276953489889364577445582220903996856271544149424805812495293211539024953331399

还是一样的，我们要先解离散对数

1
2
3
4
5
n = 2^512
m = 3097502164103987164323080671192386511065857410221288153061140622970224914473224807053016180200525552838404973541878618391348653867355109392070344210878871
c = 7575520525465161327133831389027121519268752255113564686585808502942641702897542584106400374391419523883832010238676747853882832409855139906428435538853383
e = discrete_log(c, Mod(m, n))
print(e)

后面就是全排列的爆破

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 itertools

new_flag = "3282248010524512146638712359816289396373430161050484501341123570760619381019795910712610762203934445754701"
lowercase = '0123456789'


unknown_positions = [1, 2, 3, 5, 6, 7, 8]  # 这些位置的字符未知（索引从0开始）
known_chars = ['7', '', '', '', '4', '', '', '', '', '5']  # 已知字符的位置



# 填充未知位置

unknown_positions = [1, 2, 3, 5, 6, 7, 8]  # 7 个未知位置
for digits in itertools.product('0123456789', repeat=7):
    uppercase = [''] * 10
    uppercase[0] = '7'
    uppercase[4] = '4'
    uppercase[9] = '5'

    for i, pos in enumerate(unknown_positions):
        uppercase[pos] = digits[i]

    uppercase_str = ''.join(uppercase)

    # 其余代码不变


    # 创建替换表（反向，因为我们要从new_flag还原到btl）

    reverse_table = str.maketrans(uppercase_str, lowercase)

    try:

        # 尝试反向替换

        btl_str = new_flag.translate(reverse_table)
        btl = int(btl_str)


        flag_bytes = long_to_bytes(btl)


        if b'H&NCTF{' in flag_bytes:
            print(uppercase_str)
            print(flag_bytes)
            

    except (ValueError, UnicodeDecodeError):

        # 转换失败，跳过

        continue

ez-factor

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 Crypto.Util.number import *

import uuid

rbits = 248

Nbits = 1024

p = getPrime(Nbits // 2)

q = getPrime(Nbits // 2)

N = p * q

r = getPrime(rbits)

hint = getPrime(Nbits // 2) * p + r

R = 2^rbits

e=0x10001

n=p*q

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

flag = b'H&NCTF{' + str(uuid.uuid4()).encode() + b'}'

m=bytes_to_long(flag)

c=pow(m,e,n)

print("N=",N)

print("hint=",hint)

print(c)

N= 155296910351777777627285876776027672037304214686081903889658107735147953235249881743173605221986234177656859035013052546413190754332500394269777193023877978003355429490308124928931570682439681040003000706677272854316717486111569389104048561440718904998206734429111757045421158512642953817797000794436498517023

hint= 128897771799394706729823046048701824275008016021807110909858536932196768365642942957519868584739269771824527061163774807292614556912712491005558619713483097387272219068456556103195796986984219731534200739471016634325466080225824620962675943991114643524066815621081841013085256358885072412548162291376467189508

c=32491252910483344435013657252642812908631157928805388324401451221153787566144288668394161348411375877874802225033713208225889209706188963141818204000519335320453645771183991984871397145401449116355563131852618397832704991151874545202796217273448326885185155844071725702118012339804747838515195046843936285308

看到加密等式 hint = k * p + r 移项 hint − r = 0 mod  p 看到这里不难想到用cooper来打，因为r是我们的小根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N = 155296910351777777627285876776027672037304214686081903889658107735147953235249881743173605221986234177656859035013052546413190754332500394269777193023877978003355429490308124928931570682439681040003000706677272854316717486111569389104048561440718904998206734429111757045421158512642953817797000794436498517023

hint = 128897771799394706729823046048701824275008016021807110909858536932196768365642942957519868584739269771824527061163774807292614556912712491005558619713483097387272219068456556103195796986984219731534200739471016634325466080225824620962675943991114643524066815621081841013085256358885072412548162291376467189508

c = 32491252910483344435013657252642812908631157928805388324401451221153787566144288668394161348411375877874802225033713208225889209706188963141818204000519335320453645771183991984871397145401449116355563131852618397832704991151874545202796217273448326885185155844071725702118012339804747838515195046843936285308

e = 0x10001

R = 2^248 # r 的上界

P.<x> = PolynomialRing(Zmod(N))

f = hint - x

f = f.monic()

r = f.small_roots(X=R, beta=0.4, epsilon=0.01)

if r!=[]:

  print(r)

这里要注意参数，大概20秒左右能抛出结果，也可以使用flatter来加速

现在我只需要用gcd求出p即可

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

N= 155296910351777777627285876776027672037304214686081903889658107735147953235249881743173605221986234177656859035013052546413190754332500394269777193023877978003355429490308124928931570682439681040003000706677272854316717486111569389104048561440718904998206734429111757045421158512642953817797000794436498517023

hint= 128897771799394706729823046048701824275008016021807110909858536932196768365642942957519868584739269771824527061163774807292614556912712491005558619713483097387272219068456556103195796986984219731534200739471016634325466080225824620962675943991114643524066815621081841013085256358885072412548162291376467189508

c=32491252910483344435013657252642812908631157928805388324401451221153787566144288668394161348411375877874802225033713208225889209706188963141818204000519335320453645771183991984871397145401449116355563131852618397832704991151874545202796217273448326885185155844071725702118012339804747838515195046843936285308

e=65537

r=310384729555967603261671853388867753979360895944109353196595111340924855459

p=GCD(hint-r,N)

q=N//p

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

print(long_to_bytes(pow(c,inverse(e,phi),N)))

这里我觉得可以看成ACD的问题来做感觉可以用正交格，当时比赛的时候就是一直往这方面上想但是没做出来

ez-factor-pro

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

from Crypto.Util.Padding import *

from gmssl.sm4 import CryptSM4, SM4_ENCRYPT

from hashlib import sha256

from random import *

import uuid

rbits = 252

Nbits = 1024

p = getPrime(Nbits//2)

q = getPrime(Nbits//2)

N = p*q

r = getPrime(rbits)

hint = getPrime(Nbits// 2)*p+r

R = 2^rbits

flag = b'H&NCTF{'+str(uuid.uuid4()).encode()+b'}'

leak=p*q*r

r_bytes = long_to_bytes(leak)

iv = r_bytes[:16] if len(r_bytes) >= 16 else r_bytes + b'\0'*(16-len(r_bytes))

key = sha256(str(p + q + r).encode()).digest()[:16] 

crypt_sm4 = CryptSM4()

crypt_sm4.set_key(key, SM4_ENCRYPT)

padded_flag = pad(flag, 16)

c = crypt_sm4.crypt_cbc(iv, padded_flag)

print("N=",N)

print("hint=",hint)

print(c)

#N = 133196604547992363575584257705624404667968600447626367604523982016247386106677898877957513177151872429736948168642977575860754686097638795690422242542292618145151312000412007125887631130667228632902437183933840195380816196093162319293698836053406176957297330716990340998802156803899579713165154526610395279999

#hint = 88154421894117450591552142051149160480833170266148800195422578353703847455418496231944089437130332162458102290491849331143073163240148813116171275432632366729218612063176137204570648617681911344674042091585091104687596255488609263266272373788618920171331355912434290259151350333219719321509782517693267379786

#c = 476922b694c764725338cca99d99c7471ec448d6bf60de797eb7cc6e71253221035eb577075f9658ac7f1a40747778ac261787baad21ee567256872fa9400c37

和上题一样还是需要求出r先，但是不同的地方在于这里的rbits = 252，所以我们爆破四位

这里参考其它师傅的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
from Crypto.Util.number import*

from sage.all import *

from tqdm import*

N = 133196604547992363575584257705624404667968600447626367604523982016247386106677898877957513177151872429736948168642977575860754686097638795690422242542292618145151312000412007125887631130667228632902437183933840195380816196093162319293698836053406176957297330716990340998802156803899579713165154526610395279999

hint = 88154421894117450591552142051149160480833170266148800195422578353703847455418496231944089437130332162458102290491849331143073163240148813116171275432632366729218612063176137204570648617681911344674042091585091104687596255488609263266272373788618920171331355912434290259151350333219719321509782517693267379786

rbits = 252

Nbits = 1024

R = 2^rbits

high=12

for r in trange(2^high,-1,-1):

  rh=r<<(rbits-high)

  PR.<x> = PolynomialRing(Zmod(N))

  f=hint-(rh+x)

  f=f.monic()

  roots=f.small_roots(X=2^(rbits-high)-1,beta=0.495,epsilon=0.03)

  if roots:

    rl=roots[0]

    print(rh+rl)

    break


得到r之后解sm4即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
import gmpy2
from hashlib import sha256
from gmssl.sm4 import CryptSM4, SM4_ENCRYPT, SM4_DECRYPT

N = 133196604547992363575584257705624404667968600447626367604523982016247386106677898877957513177151872429736948168642977575860754686097638795690422242542292618145151312000412007125887631130667228632902437183933840195380816196093162319293698836053406176957297330716990340998802156803899579713165154526610395279999
hint = 88154421894117450591552142051149160480833170266148800195422578353703847455418496231944089437130332162458102290491849331143073163240148813116171275432632366729218612063176137204570648617681911344674042091585091104687596255488609263266272373788618920171331355912434290259151350333219719321509782517693267379786
c = '476922b694c764725338cca99d99c7471ec448d6bf60de797eb7cc6e71253221035eb577075f9658ac7f1a40747778ac261787baad21ee567256872fa9400c37'
c = bytes.fromhex(c)

r = 7166351305785506670352015492214713707534657162937963088592442157834795391917

p = gmpy2.gcd(int(hint - r), int(N))
q = int(N)// p
leak = p*q*r
r_bytes = long_to_bytes(leak)
iv = r_bytes[:16] if len(r_bytes) >= 16 else r_bytes + b'\0'*(16-len(r_bytes))
key = sha256(str(p + q + r).encode()).digest()[:16] 
crypt_sm4 = CryptSM4()
crypt_sm4.set_key(key, SM4_DECRYPT)
decrypted = crypt_sm4.crypt_cbc(iv, c)
print(decrypted)

three vertical lines

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from secret import flag
from rsa.prime import getprime
while(1):
    p=getprime(256)
    q=getprime(256)
    if isPrime(3*p**5+4*q**5):
        print(3*p**5+4*q**5)
        break

e = 65537
print(pow(bytes_to_long(flag), e, p * q))
#72063558451087451183203801132459543552092564094711815404066471440396765744526854383117910805713050240067432476705168314622044706081669935956972031037827580519320550326077291392722314265758802332280697884744792689996718961355845963752788234205565249205191648439412084543163083032775054018324646541875754706761793307667356964825613429368358849530455220484128264690354330356861777561511117
#2864901454060087890623075705953001126417241189889895476561381971868301515757296100356013797346138819690091860054965586977737630238293536281745826901578223

这里从其它师傅那里学习了很多姿势

ax^n + by^n, 都可以用格解决

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
from sage.all import Zmod, ZZ, matrix, inverse_mod, GF

from functools import reduce

import Crypto.Util.number as cun

r=72063558451087451183203801132459543552092564094711815404066471440396765744526854383117910805713050240067432476705168314622044706081669935956972031037827580519320550326077291392722314265758802332280697884744792689996718961355845963752788234205565249205191648439412084543163083032775054018324646541875754706761793307667356964825613429368358849530455220484128264690354330356861777561511117

ct=2864901454060087890623075705953001126417241189889895476561381971868301515757296100356013797346138819690091860054965586977737630238293536281745826901578223

e = 65537

R = Zmod(r)["x"]

x = R.gen()

f = 3*x**5 + 4

root = f.roots()[0][0]

M = matrix(ZZ, [[1, root], [0, r]])

b, a = map(abs, M.LLL()[0])

b, a = [int(i) for i in [a, b]]

print(f"a = {a}\nb = {b}")

print(f"{cun.isPrime(a) = }, {cun.isPrime(b) = }")

phi =(a-1)*(b-1)

n = a * b 

d = cun.inverse(e, phi)

m = pow(ct, d, n)

print(f"{m = }")

print(cun.long_to_bytes((m)))

还有种办法是通过数学变化来用最常见的格求

首先我们有 3p5 + 4q5 = k

$$ p^{5}\equiv -\frac{3}{4} q^{5} \bmod k $$

对式子进行降幂，开五次方，令前面常数开完五次方后为t p ≡ t * q mod  k 现在需要求t,也就是在模k下计算$-\frac{3}{4}$的逆元，然后找到一个t使得它的五次方等于这个值

求出t后 p = k − t * q 造格 $$ \begin{pmatrix} 1 && p \end{pmatrix}\begin{pmatrix} 1& t\\ 0&k \end{pmatrix}=\begin{pmatrix} p && q \end{pmatrix} $$

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

n = 72063558451087451183203801132459543552092564094711815404066471440396765744526854383117910805713050240067432476705168314622044706081669935956972031037827580519320550326077291392722314265758802332280697884744792689996718961355845963752788234205565249205191648439412084543163083032775054018324646541875754706761793307667356964825613429368358849530455220484128264690354330356861777561511117
ciphertext = 2864901454060087890623075705953001126417241189889895476561381971868301515757296100356013797346138819690091860054965586977737630238293536281745826901578223
e = 65537

# 计算 -4/3 mod n

c = (-4) * inverse_mod(3, n) % n

# 在模n下寻找五次方根

R = Zmod(n)
roots = []
try:
    roots = R(c).nth_root(5, all=True)
except ValueError:
    print("No fifth roots found.")
    exit()

found = False
for t in roots:
    t = int(t)
    # 构造格
    M = matrix(ZZ, [[1, t], [0, n]])
    L = M.LLL()
    

    # 检查每一行向量
    for row in L:
        q, p = row
        # 取绝对值处理可能的负值
        q_abs = abs(q)
        p_abs = abs(p)
        if q_abs == 0 or p_abs == 0:
            continue
        # 检查是否为素数且满足方程
        if is_prime(q_abs) and is_prime(p_abs) and 3*p_abs**5 + 4*q_abs**5 == n:
            print(f"Found p = {p_abs}, q = {q_abs}")
            found = True
            break
    if found:
        break

if not found:
    print("Failed to find p and q.")
    exit()

N = p_abs * q_abs
phi = (p_abs - 1) * (q_abs - 1)
d = inverse_mod(e, phi)
plaintext = pow(ciphertext, d, N)
print("flag:", long_to_bytes(plaintext))