2024长城杯决赛cry

发表于

比初赛简单，然而还是没做出来，经大佬指点才有思路。

原题：

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
# sage -pip install pycryptodome
 
from Crypto.Util.number import * 
from sympy import nextprime
import os
from gmpy2 import*
'''
Too next maybe.
'''
class MyRSA():
    def __init__(self,flag:bytes,nbits:int):
        self.n, self.phi = self.GetMyModulus()
        self.e = 0x10001
        self.d = inverse(self.e,self.phi)
        self.flag = self.pad_pkcs77(flag,nbits)
    def GetMyModulus(self):
        u = getPrime(1024)
        u = (u >> 414) << 414
        p = nextprime(u)
        q = getPrime(326)
        n = p^5*q
        phi = p^4*(p-1)*(q-1)
        return n, phi
    
    def pad(self,flag,nbits:int):
        flag = flag + os.urandom(1)*(nbits//8 - len(flag))
        return flag
    
    def pad_pkcs77(self,flag:bytes,nbits:int)->bytes:
        pad_len = (nbits - len(flag)) % 256 
        return flag + bytes([pad_len]*pad_len)
    def Encrypt(self,flag:bytes)->int:
        return pow(bytes_to_long(flag),self.e,self.n)
    
    def Decrypt(self,c:int)->bytes:
        return long_to_bytes(pow(c,self.d,self.n))
    
    def GetPublicKey(self)->tuple:
        return self.e,self.n
    
R = MyRSA(flag,4096)
e,n = R.GetPublicKey()
c = R.Encrypt(R.flag)
assert flag in R.Decrypt(c)
print(f'n = {n}')
print(f'c = {c}')
print(f'e = {e}')

观察可知，q是一个326位素数，p是1024位素数低414位置0的数的nextprime。感觉这题思路与前两天的basectf “没有n啊”有共通之处，都涉及到二项式定理的活用。

对于p，我们设其高位部分为a，低位部分为b，这样就有

p = a*（2^414）+b

那么对于 n= (p^5)*q

有：n=(（a*（2^414）+b）^5 )*q

到这里我们注意到，若对整体进行mod 2^414，即有：

b^5 * q= n mod 2^414

因为p是u低位414置0的下一个素数，说明b的值应该很小。由于q为326位，可以推测b^5 * q的值本身就小于414位，所以不会因为模操作被截断。因此，我们只需尝试b的不同值进行爆破即可求出原本的q。

求出q后就简单了，n整除q求出p^5，然后开方即可。

实际运行过程中发现有多个符合条件的b，q值，所以要注意q同时要能被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
from Crypto.Util.number import * 
from sympy import nextprime
import os
from gmpy2 import*
 
n = 10823775490240073819631917849117225946287891171185101059838012738590942083286491895086451201330121282239112048818281379201392391711081928618707509066233928638187019201160301050490769069075313289908655264579328149828347872699697195230421390529843974340674990548004216615592682491515978442178349653549929465663244023757359796216867165844075976331191951027290725012210177449053555588254681079976280745286908897416681478813013297839608241067674026010720343633012556240553683175172988624633735387588606867666858001973089190528295159219227069810517454677330841359125440162677002725561779009788936368150290859696939093099879034996630579194814736517706689658051035296730348668338031728823161338125653461172596730500445378167749498084676295147743704190979584713779480154941790026465774118720519452568935866964502632734126766023547271771741522485702708564882312127253470312413231358374856453986812653197218096126488261909815753848184984064628112603870471377689973632577669755803660286519111642490140982595789903748438781184726565551753915521681764875126384100543905139578572437448873221310081171658381184510994313626085298420060720405712211118973379978497950555404038223284628782496353636937575849667836726918752652643522916609808294676912772669709626282702678281989896980713944961023191040866155298213017019008276602607515680628655918406129027549335549388661763175355900965439242125850380340787177957488885171013738475994880288387184114946910361655893886743701515443028478684376198033356669188403171941244027967567591761268196312412901508832292242743552450482860690493244338059935380601338109164461877746510598646182450038161334450878692284043867773
c = 10660090497301432537437820885848286020311835935260034549173484275959379310864520958356152878610641549326516182239849660339867147213565561569490658510864241912091951711562645132218482839920377179333386420114391233630515012393090359381717875467071280927583120692784917275074532993409388122061004854178182661632604182150765151482558156183912422898613209559942234127025063687928879910292952039316531554812705081695248540209866005563219806997627684236587554109286831877006896470109805219447282525518519161097673276492456094713735029038771812376330352652393029164468202357817665724369560583349301558861453705718562711798522554316893417360531922795446452749685308492123451575279293644339041629468390133378328145993285368218775498976282596017084494092950586275565868969964447619034372770452127643594002885530340353730337577609060573094563836165559288998090805166088888016631981190567474132421889397451224492478175286707362679459528061705122579238644392225558752144211463152201143723558678398331677420261413849490732610210418705205396485108198008618730081560787598535809656356334449123152662358838247968331030455386114998823400263422044625507507829935684490654252473089135735147481428318393546785418776661158864450118169388804900558540117140348002680864998171847298229035444536926030071973643938958868695657994095200366957439503117930474161132984898344356321926977383591037057394861749532205998932840557833372993944408083463060446903121200107227041538939713625198024076302549803852074630498649236538622458710733295489005936281570737839438843387492079285997225293361642946364581369251919661240027265549956890265107036578709824437885345581015267152770
e = 65537
 
 
 
nn =  n%(2**414)
x=2
q=nn//(x**5)
while (1):
    x+=1
    q=nn//(x**5)
    if(q*(x**5)==nn):
        p5=n//q
        if(p5*q==n):
            break
p=gmpy2.iroot(p5,5)[0]
phi=(q-1)*(p-1)*p**4
d = inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))