长城杯一些crypto随笔

        最近在做一些misc的训练，做累了，回归老本行放松一下

高低位爆破

# sage -pip install pycryptodome
 
from Crypto.Util.number import * 
from sympy import nextprime
import os
from gmpy2 import*
 

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}')
n = 10823775490240073819631917849117225946287891171185101059838012738590942083286491895086451201330121282239112048818281379201392391711081928618707509066233928638187019201160301050490769069075313289908655264579328149828347872699697195230421390529843974340674990548004216615592682491515978442178349653549929465663244023757359796216867165844075976331191951027290725012210177449053555588254681079976280745286908897416681478813013297839608241067674026010720343633012556240553683175172988624633735387588606867666858001973089190528295159219227069810517454677330841359125440162677002725561779009788936368150290859696939093099879034996630579194814736517706689658051035296730348668338031728823161338125653461172596730500445378167749498084676295147743704190979584713779480154941790026465774118720519452568935866964502632734126766023547271771741522485702708564882312127253470312413231358374856453986812653197218096126488261909815753848184984064628112603870471377689973632577669755803660286519111642490140982595789903748438781184726565551753915521681764875126384100543905139578572437448873221310081171658381184510994313626085298420060720405712211118973379978497950555404038223284628782496353636937575849667836726918752652643522916609808294676912772669709626282702678281989896980713944961023191040866155298213017019008276602607515680628655918406129027549335549388661763175355900965439242125850380340787177957488885171013738475994880288387184114946910361655893886743701515443028478684376198033356669188403171941244027967567591761268196312412901508832292242743552450482860690493244338059935380601338109164461877746510598646182450038161334450878692284043867773
c = 10660090497301432537437820885848286020311835935260034549173484275959379310864520958356152878610641549326516182239849660339867147213565561569490658510864241912091951711562645132218482839920377179333386420114391233630515012393090359381717875467071280927583120692784917275074532993409388122061004854178182661632604182150765151482558156183912422898613209559942234127025063687928879910292952039316531554812705081695248540209866005563219806997627684236587554109286831877006896470109805219447282525518519161097673276492456094713735029038771812376330352652393029164468202357817665724369560583349301558861453705718562711798522554316893417360531922795446452749685308492123451575279293644339041629468390133378328145993285368218775498976282596017084494092950586275565868969964447619034372770452127643594002885530340353730337577609060573094563836165559288998090805166088888016631981190567474132421889397451224492478175286707362679459528061705122579238644392225558752144211463152201143723558678398331677420261413849490732610210418705205396485108198008618730081560787598535809656356334449123152662358838247968331030455386114998823400263422044625507507829935684490654252473089135735147481428318393546785418776661158864450118169388804900558540117140348002680864998171847298229035444536926030071973643938958868695657994095200366957439503117930474161132984898344356321926977383591037057394861749532205998932840557833372993944408083463060446903121200107227041538939713625198024076302549803852074630498649236538622458710733295489005936281570737839438843387492079285997225293361642946364581369251919661240027265549956890265107036578709824437885345581015267152770
e = 65537

首先是早上碰巧看到的这道RSA，启发了我一些高低位攻击的思路，可以将高低位分别设出，在模低位的过程中可以消掉低位，从而进一步推导。看代码，一些乱七八糟的辅助函数都可以省略，直接看p，q的生成过程。 u，随机1024位素数，u>>414,将低414位全部置0，p，u低位置0后的下一个素数，q，326位的素数，n=p^5*q,不妨设p的低位是b，高位是a，即p=b+a*2^414，因为p是低位全0的下一个素数，所以b一定很小，

from Crypto.Util.number import *
from sympy import *
from tqdm import tqdm
from libnum import *
from string import *
from hashlib import *
import os
from gmpy2 import *
# sage -pip install pycryptodome
n = 10823775490240073819631917849117225946287891171185101059838012738590942083286491895086451201330121282239112048818281379201392391711081928618707509066233928638187019201160301050490769069075313289908655264579328149828347872699697195230421390529843974340674990548004216615592682491515978442178349653549929465663244023757359796216867165844075976331191951027290725012210177449053555588254681079976280745286908897416681478813013297839608241067674026010720343633012556240553683175172988624633735387588606867666858001973089190528295159219227069810517454677330841359125440162677002725561779009788936368150290859696939093099879034996630579194814736517706689658051035296730348668338031728823161338125653461172596730500445378167749498084676295147743704190979584713779480154941790026465774118720519452568935866964502632734126766023547271771741522485702708564882312127253470312413231358374856453986812653197218096126488261909815753848184984064628112603870471377689973632577669755803660286519111642490140982595789903748438781184726565551753915521681764875126384100543905139578572437448873221310081171658381184510994313626085298420060720405712211118973379978497950555404038223284628782496353636937575849667836726918752652643522916609808294676912772669709626282702678281989896980713944961023191040866155298213017019008276602607515680628655918406129027549335549388661763175355900965439242125850380340787177957488885171013738475994880288387184114946910361655893886743701515443028478684376198033356669188403171941244027967567591761268196312412901508832292242743552450482860690493244338059935380601338109164461877746510598646182450038161334450878692284043867773
c = 10660090497301432537437820885848286020311835935260034549173484275959379310864520958356152878610641549326516182239849660339867147213565561569490658510864241912091951711562645132218482839920377179333386420114391233630515012393090359381717875467071280927583120692784917275074532993409388122061004854178182661632604182150765151482558156183912422898613209559942234127025063687928879910292952039316531554812705081695248540209866005563219806997627684236587554109286831877006896470109805219447282525518519161097673276492456094713735029038771812376330352652393029164468202357817665724369560583349301558861453705718562711798522554316893417360531922795446452749685308492123451575279293644339041629468390133378328145993285368218775498976282596017084494092950586275565868969964447619034372770452127643594002885530340353730337577609060573094563836165559288998090805166088888016631981190567474132421889397451224492478175286707362679459528061705122579238644392225558752144211463152201143723558678398331677420261413849490732610210418705205396485108198008618730081560787598535809656356334449123152662358838247968331030455386114998823400263422044625507507829935684490654252473089135735147481428318393546785418776661158864450118169388804900558540117140348002680864998171847298229035444536926030071973643938958868695657994095200366957439503117930474161132984898344356321926977383591037057394861749532205998932840557833372993944408083463060446903121200107227041538939713625198024076302549803852074630498649236538622458710733295489005936281570737839438843387492079285997225293361642946364581369251919661240027265549956890265107036578709824437885345581015267152770
e = 65537
nn=n%(2**414)
x=1
while(1):
    x+=1
    q=nn//(x**5)
    if q*(x**5)==nn:
        p5=n//q
        if p5*q==n:
            break
p=iroot(p5,5)[0]
phi=(p**4)*(p-1)*(q-1)
d=invmod(e,phi)
print(long_to_bytes(pow(c,d,n)))