2023-DASCTFX0psu3十一月挑战赛-wp-crypto

包含四个赛题的题解。

GeneratePrime

题目描述：

尝试分解一下素数吧

题目：

from Crypto.Util.number import getPrime, isPrime, bytes_to_long
import os

def 0psu3_The_best(sz, d):
    while True:
        p = getPrime(sz)
        pp = sum([p**i for i in range(d)])
        if isPrime(pp):
            return p, pp


p, q = 0psu3_The_best(512, 5)
r = getPrime(512 * 5)
n = p * q * r
e = 65537
flag=open("flag.txt", "rb").read().strip()
flag1=flag+os.urandom(128)
m=bytes_to_long(flag1)

c = pow(m, e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")


#n=43090231453250894711427929679917165532091051269639380881822679198388872373018031295429558758883298138388596507242928145888959963579111847255588834248367032580980272245414738073179172684104908272069503607376171584936239696444309039211273376010193165083254209608051430794825261116490356392215410064858020176711199543381037420111454942356936721487016187240237683725310306748046587503625096246489043270381153251813360521583717685413070481576320194446237522118380283335294528606720928637529817170809666802598938788405154468683850385277659812316577873886708164549255359514776884765904417881419804464020855420288884972204146588152412816874161445668955639456202226751519881834234916642218078966066353317917939418964763844067220460513388433020071277477619189495465483910271310025371745344364984826481983188861624474015117761898377237745775289039922285111681410319016537270412509750339539020876501534842403407208957382830000761065368861209033791387480377889838737241326116532852335478193204425626487166234964754732945953080086117315162916374952094149599597509405176646068341218684523765974759907645226607364627690026025662221036766148813918691578120023886400197652148214238256715089883892069133754778609710846757189987335827693169644541734443763194942694587436469448973201513131503797898892822373949177030567791519349220158287318717788746060997955057747930375117780320371517616412423571775682868481089431670802944047375824503353609019686495670630728618082254293585479431369645935654024149490741245953271830453426444847467908952699660750809490650479987
#e=65537
#c=30862228874892553476569860337345503267926249096036551213683005116620750680365154103242717714230966827288361499342464202425467642950081816675486231250411347472976482409360391136808439034217688010072648722396312121758844966972323513456884732046270240934002095706243044210312663525491282667971502534420245427643076262414036655243117610886157895994101178663474990136516153062956803591842233732498519246731337518545018734984319536536205092573418457928952414660837594265802406473201400259189950484841504227372735345451459452313825309333631615286962304963039625162366186574440146535361888708570569938418676320446653266676364765870547213167058713058609788316647593834008151805692510044158607162858906528913516242904419457446211348504248317409844426309455978985314882123424453618672960876022996245213882467954521212481418830104602302179759479012618982228223244131619557639469872139485197176384683400796204681045965981417650462297978265085323342772310690638049411549216990505001950512428646871875659468885490055363436412364532718888124906227240501145227269727887236864060558999336443165765870556727793253297515155026234234422303238380776900105115890363548589834345888430695886678231459920101695996112312269637459823479947618045447071359886515163416153117176539752947700226596291435270282598638974889205601333097978743387412651687356072223691445472690647184292120882095587563356691450107194982597794937293154289560470269606300576216128045797481404606810315677962659136641943747123985144899464108823536597185386155005111274476874957827391438859327653936

题目是根据ImaginaryCTF 2023的sus题目改的，具体推导可以见我这一篇文章：

Crypto趣题-RSA(一) | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

在sus一题与本题中，q分别为：

$$q = 1 + p + p^2$$ $$q = 1 + p + p^2 + p^3 + p^4$$

而这其实并没有多大区别，因为他们分别满足如下因式分解：

$$p^3-1 = (p-1)(1 + p + p^2) = (p-1)q$$ $$p^5 - 1 = (p-1)(1 + p + p^2 + p^3 + p^4) = (p-1)q$$

所以推导过程可以说是完全一样的，参考上面那篇文章即可，而这个题目本身我觉得是非常有意思的，所以我强烈推荐弄明白原理。

exp：

from Crypto.Util.number import *

n=43090231453250894711427929679917165532091051269639380881822679198388872373018031295429558758883298138388596507242928145888959963579111847255588834248367032580980272245414738073179172684104908272069503607376171584936239696444309039211273376010193165083254209608051430794825261116490356392215410064858020176711199543381037420111454942356936721487016187240237683725310306748046587503625096246489043270381153251813360521583717685413070481576320194446237522118380283335294528606720928637529817170809666802598938788405154468683850385277659812316577873886708164549255359514776884765904417881419804464020855420288884972204146588152412816874161445668955639456202226751519881834234916642218078966066353317917939418964763844067220460513388433020071277477619189495465483910271310025371745344364984826481983188861624474015117761898377237745775289039922285111681410319016537270412509750339539020876501534842403407208957382830000761065368861209033791387480377889838737241326116532852335478193204425626487166234964754732945953080086117315162916374952094149599597509405176646068341218684523765974759907645226607364627690026025662221036766148813918691578120023886400197652148214238256715089883892069133754778609710846757189987335827693169644541734443763194942694587436469448973201513131503797898892822373949177030567791519349220158287318717788746060997955057747930375117780320371517616412423571775682868481089431670802944047375824503353609019686495670630728618082254293585479431369645935654024149490741245953271830453426444847467908952699660750809490650479987
e=65537
c=30862228874892553476569860337345503267926249096036551213683005116620750680365154103242717714230966827288361499342464202425467642950081816675486231250411347472976482409360391136808439034217688010072648722396312121758844966972323513456884732046270240934002095706243044210312663525491282667971502534420245427643076262414036655243117610886157895994101178663474990136516153062956803591842233732498519246731337518545018734984319536536205092573418457928952414660837594265802406473201400259189950484841504227372735345451459452313825309333631615286962304963039625162366186574440146535361888708570569938418676320446653266676364765870547213167058713058609788316647593834008151805692510044158607162858906528913516242904419457446211348504248317409844426309455978985314882123424453618672960876022996245213882467954521212481418830104602302179759479012618982228223244131619557639469872139485197176384683400796204681045965981417650462297978265085323342772310690638049411549216990505001950512428646871875659468885490055363436412364532718888124906227240501145227269727887236864060558999336443165765870556727793253297515155026234234422303238380776900105115890363548589834345888430695886678231459920101695996112312269637459823479947618045447071359886515163416153117176539752947700226596291435270282598638974889205601333097978743387412651687356072223691445472690647184292120882095587563356691450107194982597794937293154289560470269606300576216128045797481404606810315677962659136641943747123985144899464108823536597185386155005111274476874957827391438859327653936
k = 5

R = Zmod(n)["x"]
while True:
    Q = R.quo(R.random_element(k))
    pp = gcd(ZZ(list(Q.random_element() ^ n)[1]), n)
    if pp != 1:
        qq = sum([pp**i for i in range(k)])
        rr = n // (pp * qq)
        assert n == pp * qq * rr
        break
phi = (pp - 1) * (qq - 1) * (rr - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m)))

#DASCTF{just_a_very_very_easy_task_with_your_talent_is_not}

FindPrime

题目描述：

利用你的所学知识看看这个素数有啥能分解的吧

题目：

from Crypto.Util.number import *
from gmpy2 import *
P=getPrime(int(512))
p_list=[]
for i in range(30):
    q=getPrime(1024)
    r=getPrime(450)
    l=q*P+r
    p_list.append(l)
path1="D:/CTF题目\密码\出题1/"
with open("output.txt",'w')as f1:
    for val in p_list:
        f1.write(str(val))
        f1.write("\n")


Q=getPrime(512)
N=P*Q
e=e1*e2
m=bytes_to_long(flag2)
c=pow(m,e,N)
assert m<N
print("N=",N)
print("e=",e)
print("c=",c)


#N=68770027076980723946939075792572969610228738501865973895618044035550466673326811210718966610231582633896160130057212343512606374318082678735227998163020559923237005947682357783487924911009663067842443440348588088325506801639924926097944176357432282915587075930988972621730524537492705984723766652062305363027
#e=30899846873
#c=46935517038224473812546067305866276864169387205589347201858550096671613860700878462369638807831295923952343159795466895818221029692119135003812788250010552362110290387383510093277209478665971066986914981717774698233220968427990066291572377851164878122374241804989577737820368814455456808941766309324614067608

output.txt：

833477371577037248671393488796841448323259324097064076319628420817885469255000583369058481944985769427996156459681454706589776988919309994624061437098895355604275125815197436256702258179251584180213654099283298392635474661213568306075241588048132336078444076126820420463425993589637558750777268224105474567279804292533669526701194763687939785229766307504441712413449981891561774806156665751819904294472651269669748332928431198159353146128591296262185405972439546
1417152335984227895861976535021216841448579442747465060823276117342707242036009501153174353498039264338222617085495976550068103477774948724127741741708784215760734847758354594318769717406990462644647262705257356458710337592960428524874926699201316728348581862499570079314933543886720367661160716082695676780397728399987054072186527533287843688129609522799869815936639832013954440499639010333786645953413907919333585387641086968778447914208830518647808481101744324
825367446328428514387697995916336764546268230407927332717623008352471527800278723584639057096612354365560873809150001125278412400474409061202793883535179571174914202587885962179015715680607289928464406578658800580951213697647205960790337310924484411796444362107897902280992396479162688010814408461729223033123136202693070960903215433774294632728389327422670143968868682620853783857921514241013093770504123459537458692492751810710800714011831621269113360518146466
1117038639337471846829376079962481193398932800977268229076827506371401256669800316726321224468793029294472485026921632948383102312056921521024306059345938460478459700466054808539783394230282753938588089881925678699530435751913189427180282771396540962548369034354743885813399454493710302493578739515264505177658100751453455496774147005531958801283461861649229880608818211044433598649395832661445740364729368315801371639810397211894031768657378216033361397549366256
789053897304615315337175819738966271887736346682171450497097040086498239540377384986209739979046088390348561630505449064375395941971263831832121567291403546039845417362378013959087178137950071886621154078491546369789131036116261508976173752711978857719619406789313307878001096869325696238380891433568872331290007330722088030578583205858796182940602367954524757711316167615101597446309984571234377671932653365183502569671856918490864417200211766344072222998027822
966501879970742600511208788258526900344376522075501649104033255633597034935664368131875660642155019813129246919011772829055632548744997359467600623938236900630865127499099427610462066513843467274429222012089690015994012152596196816130406746915460387848239967901760618640583349703983484157317741929002569740058587411590431911493390093995968210910735353154523490679129412378481195890371227907180147669889684430126196556931405955478955081021596778423861644605413220
1016206715544805616785448447890465545186987897028556564304636789980188990657954923931006415294723182820924206335074345389566219429933493040648600433401610217090975900023234793427998610379251762559967019400728297780551725015583666086666516418087030343203101010021703209197523343693860658825737224551153658921423547727162107463031046748406971820610714074184196091161013509824451242098842170379050555049206021603159062400839577538179369013207264237775294267243450954
1404676392176442693280296127342987494550957043392635386494042054010991321501621533741338727100112185013038167221974051488817482793170202879408486718454210845858736679832294483147175210110615257817394064543261586158156967750121198092580348602468647683129797260957074060274292680433931960236168813016297052791985451576121114558772154532080435223066720081665556076765698304139098057592135203163250240567852578238243023714328048303989363646868600166520437611843612270
1059935376878480441729492697632030905525885607048323279059128530919559830128835302912470726619568501417529071921932168803344700381721474676777308027068110306949314839450395796653187838326332784828777724424199917441151240196726745672383847672313980284416050202584142927770763591075702102605031237345472147341910472151710788810979403340565238113975573870517570875437842746448994428058467668823003473072579180637652269984142354411576575917646079583753495367912839960
1005093213315393709159231593860148335197371021667176710985282901155843124491374058148746111824100113560244085276326910991515846365967838636201323200445828413058675197551700929939472848246171263835605578862722270129746740782455909536537801517982606803080616613461318236425458449709297715347210050402550612702295502040273916918213837452195992544090277434980077570231118874818252862234141519024564669607765367582670314778517944498054666016737330861609379025113166836
1150913477976579544984692837814166801393210199102413166293610666053242980149249488331633577850447467218914394901012296132704736775926309440233035822531930858429680280993777507984535655970890119429824895156920369805049543936219472734491318222718258425842787941873957417289878296856278156476011010315934177086137347319511037491948179006778146455912868593940481149704105685035076511248645882008350000735358430584727064929886184048893752594473105588170689002436016108
857193622046369532956303858593915920091597899231114606099376840455498815291882249441316031657223227886408063256997935928852293829363958674748941423482637958097945036015119524003003529012562728663880039779300828455495173066579528840884504820474127764155580431575882153799727366954172244998949884163037173049989089510830676034565100786578569157931828330719618855553013985973380333255988458270286090135439085358705855985243464480891415621448009851959125608913493532
1419578626166241608187446985031580512168477481811085359150685095484793334202527830547034879761867782041173504320112039187155606674603450932756995974373876322714100270829493513464972910926435502039913170224956912694142741662642933933999326460268175383410342841997236283906971159882088557842024632266062183163485549556384032497107858373981463088429364943651132002706286010784023366937866234587219007880761583742149766841528701425809927531187141310911172872261081554
1423307551896161786512215827022870175063222208925704901852746235904119084039916057601838636424593528597732181049081326600492333908289646434972432345182913892750533744008053671953421431434597081933354887626263497175824523966651302503840039576819802476809108477323831817268200363982401889960974708148391285217560833905198935711219683992300641182176074206804052011439366948577435309990620316268332718916966656229306271202312539205394104903494149703983927691925961516
1069265966773937257631872597134275941869000423525218346298953174309119163656802514364762827970811943823322783323544774161909912819104162037918592559755759727802379584211756666220390164620318222455038057141982239560186314721987573168524609661531811062780873728149065735480981514675551011108026831374118214638064879015553515680470205182650594449751838511561327123626559699654094872484543517115161758221449091000937429591410504791574788100186059349155083786419613988
831148147986562981791013717502074816164601486662234983507966683328069824638956245030085039811926151437560846491877574422999497174702970871296076127174453588302182188721507427887567381409439635539917087082067644108875952649408453213360856014406755455108299274821574752919390362497642562228427600660772449168728269926257473086706554589045581733254050007519858892294855483686774455623885320336684432867276583162311340077829209990043173980972300187928518697070468996
1060215801514866437791578461943164279568483386789993575867096166399913145757365274111449830143103702894903474975107260334611369797180083953487741737332574140747385704887635319337486677976105307482884560294301804144637587975284507874965537158616927633258097477908378619667507726945262801827614898172498864286618016886780599217315916737039861994816080123912315759399718579272542333762041003203117571903424905897895075980290484851700374387581704764700965380523937384
781091525507779642711326285949957135768416312540473458004826675463286165819993139313925660301906465620702047089275138672820378421253204240781265329432875735662337192627962915666835147070204317859550070788071012843576716384257903873190222648029535907200699656878148226246737118274387636720703171556741875336295000147639281610425042988056231377739897286002888061410424070947134810253831248291474809964810500480145096273639189318730677716644586929346741481028849444
1000420794160323381465286272924907081961177232118898862965676160439914918853816569540590330975399562542538562217824507501553504589733186132049002465442973481767435841400506558652776030791348947276372954395223847310907860192022126889997704182301444242825957397694694175288178630795916340670104158948380603567806637680418989366332578973787776100772021232347138831066306752739345057342554253191209826039573536968306043954523568935672995825503153742080761151720958080
1390016626099589721822437523076448285233691358379392393624472327387856568209362766591898878685863618557197554162328337468229522280514039414396633848448296586219419765849020276433023903652652412492851487848312684816496638349984873821757508758697182082304973747729555560960228384420607427506098293404730536234563973694006283617426627569010655455194337811387636304887127393676532817790742243125362945418311906880230114221372499795708508332449178073693991253458082484
1122288214684138128045560504834990165115198801984427072594181143306901500950590187776379574689495482136096068249216028920952710651644889210417742065718895811780497758959877358223202667478525949518062312582242750630096329784082213922579901068453269279004979747616755939107868519324046403154579862061083838756607314620110166338539041798180260555261874058608020379554468792976830979136219822396526295418332356089431286982911441215127244346866155288164625077359308004
854219930286542650194778372394729765545724795545625499667712705396741231238154066225715320705089120454428253483326821962608884433030674113396036505205901904590975146903798466233732562408855582658923922888851843457352917824900907468283044606105085633454999350372446346717104937912248079085945481290350047046401131197624600858115042151578988645720195101597908767427980099015460999299497664803069451020989406603431092460240575099805048212121659198359430888560420530
1261246726587000362729848817491358224445427130674846683109855771271784258738270381893062012086287925404579042835019929714007922138797108267615062424106738007375969588556945028273292357534874334394559105897377313432215150380276038982361813917606245227819396956432322423539752376843139826022256376073193508742877189060653254866350843737326176879196191475635611541907034926709247231688084402947052579795253419078171522152205668769459934912444378065643336984512256510
780005508238107005510509836164223921044666224377795828300947099004376047921297990104219560023931231544557425302962325823558355900892882299464095079477243512600395329393929433066337627770466856971216745972567107777542454459794788994082656375517952090947435032095975802440249446822905679764921479374476012984113061606729178052755920566745765263071374238824807176195606628435580933430936024369686481134598592521694905828278700764250389138158322517166164903110462066
834799737552815677831798522362625860596892201502022185844378591082958406477419172921654896757875405183086406434404225150230262695935863148513479885969629873319695009143111892260623329502065862550214444719008796670081827784609604579428514248627354706668126809110671124178198186811125900071655584768626832096925022227356630218156381176772308734257457537817001018805235898378868627574202721946548461064601775049784378572171485995538251505183100361230932774104113886
1230354787119889904130004260312617342046984097670154079163135854064969865113190324348119675476237316262686294350627172354890689274930817167624993628390737307161796902310467648048386829948452708247676789045543782438901802270769347272010191682095244937698392905818612050761277135396311948902097043823148956081626916920627192798739825601839432604187237055718281674145748307536137649013956588543777095899224536339005889759573853087326251934159121656192827774098420940
1505535414534190519011469998285555000238244986597578956112990806890571190453736860174536272278446860616858845440508028155234910705669527551829296796080027218571688908621955909972704725652740860021573473274351639662540234966346159883709126580826995877842546489458754554203501599927945093781077874845767570010299166664000368788758489425472501371633784295879764995261886049824765928665855217956032386533213447186797947009285536832189249090672043664338787191516222120
1108608754874636819606953570379050124347612193212871087598239782497649261015061942949326283639937696469385672493423787042424357528691789815826436103378090788068218845067894058320662612843530270943740973098392758144983074073402148927374612245493513909739508460186786819413110394835403394504084365191534631972095994805201815972552250717633204430679782393268400868097740091447107412703287949906822406811035970720756685565762862913129733272075332752340578144448720784
1131647287528070724203713102778052490316099871590834868624734105618338848313087840928325888054073846131653868923766386491093594772565755900508543864529795874036311465143137316619735289760162754882929413472373067876900610363336052337922039206955881985467787893431759390247420924718719504483973516607450198508745716692746495798702835409095202216367012138474718689897382066678960480816075024508154560762120732187038314684780936340478907270415029703147268421316351874
830497759980729705914224051104334162195664514518858237593098625409691796348328838055145107246075750180679786726928482494826051254000298370330008697134860935299858341071632392187887898796558384238650778286360693065159921427410587126453021406241902512144392153147013515487170166739678977696280729438759368787150359599597145133628344404040467791698202996366424396693955985890540382037841163140927737324582659777001878325588502674474406848265729886219896148230970980

这个题目就没太多可说的了，第一部分AGCD，第二部分AMM或者有限域开根后CRT组合就好。

exp：

from Crypto.Util.number import *

N=68770027076980723946939075792572969610228738501865973895618044035550466673326811210718966610231582633896160130057212343512606374318082678735227998163020559923237005947682357783487924911009663067842443440348588088325506801639924926097944176357432282915587075930988972621730524537492705984723766652062305363027
e=30899846873
c=46935517038224473812546067305866276864169387205589347201858550096671613860700878462369638807831295923952343159795466895818221029692119135003812788250010552362110290387383510093277209478665971066986914981717774698233220968427990066291572377851164878122374241804989577737820368814455456808941766309324614067608
tempc = []
with open(r"E:\题\DASCTF X 0psu3十一月挑战赛\FindPrime\output.txt","r") as f:
    for i in range(30):
        tempc.append(int(f.readline()))

#AGCD
pbits = 512

L = Matrix(ZZ,29,29)
L[0,0] = 2^450
for i in range(1,29):
    L[0,i] = tempc[i]
    L[i,i] = tempc[0]
res = L.LLL()
k0 = abs(res[0][0]) // L[0,0]
p = abs(tempc[0]) // k0
q = N // p

e = [7,191,23111329]

d1 = inverse(e[2],(p-1)*(q-1))
c = pow(c,d1,N)

#p
dp1 = inverse(191,p-1)
cp = pow(c,dp1,p)
PR.<x> = Zmod(p)[]
f = x^7 - cp
resp = f.roots()

#q
PR.<x> = Zmod(q)[]
f = x^(191*7) - c
resq = f.roots()

from sympy.ntheory.modular import crt
#M = crt(n,c)[0]
for i in resp:
    for j in resq:
        ti = int(i[0])
        tj = int(j[0])
        n = [p,q]
        c = [ti,tj]
        m = crt(n,c)[0]
        if(b"DASCTF" in long_to_bytes(int(m))):
            print(long_to_bytes(int(m)))

#DASCTF{VERY_VERY_EASY_AND_TAKE_THE_NEXT_TIME}

MathFactor1

题目描述：

简单利用你的知识观察即可

题目：

from Crypto.Util.number import *
p=getPrime(512)
q=getPrime(512)
n=p*q
d=(p**21+q**17)
d1=d&(2**300-1)

flag=open("flag.txt").read().strip()
import os

flag=flag+os.urandom(60)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")



#n=89049581381915401856270440494182068395799559452947499744642830361236578373835725708887668528820916651578050248209041339369091828040992115394942524278397293747808840107939504743946806866214713225533666120894844131211241905215662457238793580469827973839976134854993162976454283311566973255659612267446150515233
#e=65537
#c=16305239798028293699632813396005973660370581911030264211210444559974188415332021689054795983319112132645051076901780239982290095820283651929773925636804434706351474493000010749679965744672518110692104573489299874390925347271040454693791271882869477780584606934066152476594086178041874762147934091597942667138
#d1=1253867202722198232827428701701674148965306906567632781415318063046179456643047348348144258

题目要求分解RSA的公钥n，为此给了我们一个额外信息：

$$d = p^{21} + q^{17}$$

但是这个额外信息并不是完整的，而只给了我们低300位。利用这个信息推导的过程如下，首先同乘p^17：

$$p^{17}d = p^{17}(p^{21} + q^{17}) = p^{38} + n^{17}$$

那么在模2^300的意义下就有：

$$d_1p^{17} \equiv p^{38} + n^{17} \quad(mod \; 2^{300})$$

那么解这个模方程就能解出可能的p的低300位，然后copper高位恢复p就有n的分解。

exp：

from Crypto.Util.number import *

n=89049581381915401856270440494182068395799559452947499744642830361236578373835725708887668528820916651578050248209041339369091828040992115394942524278397293747808840107939504743946806866214713225533666120894844131211241905215662457238793580469827973839976134854993162976454283311566973255659612267446150515233
e=65537
c=16305239798028293699632813396005973660370581911030264211210444559974188415332021689054795983319112132645051076901780239982290095820283651929773925636804434706351474493000010749679965744672518110692104573489299874390925347271040454693791271882869477780584606934066152476594086178041874762147934091597942667138
d1=1253867202722198232827428701701674148965306906567632781415318063046179456643047348348144258

maybe_p = []
p = var('p')
p0 = solve_mod([p^38 - d1*p^17 + n^17  == 0], 2^300)

for i in p0:
    PR.<x> = PolynomialRing(Zmod(n))
    f = x*2^300 + int(i[0])
    f = f.monic()
    res = f.small_roots(X = 2^215,beta=0.4)
    if(res != []):
        p = int(int(res[0])*2^300 + int(i[0]))
        break
q = n // p

phi = (p-1)*(q-1)
d = inverse(65537,phi)
flag = pow(c,d,n)
print(long_to_bytes(int(flag)))

#DASCTF{0psu3_is_the_most_Greatest_army}

MathFactor

题目描述：

尝试利用你学过的知识来解决吧

题目：

from random import randint
from Crypto.Util.number import *
from secret import flag
def encrypt(key, message, mask):
    return pow(64901, message^^mask, key)
def get_Prime_leak(bits,t1):
    x,y=0,1
    while True:
        
        u=randint(1,200)
        v=randint(1,200)
        x,y=u*x+t1*v*y,v*x-u*y
        if int(x).bit_length()<=bits//2:
            p=x^2+t1*y^2|1
            if isPrime(int(p)) and int(p).bit_length()>=bits:
                return p
        else:
            x,y=0,1
t1=getPrime(16)
print(f"t1={t1}")
p=get_Prime_leak(512,t1)
q=get_Prime_leak(512,t1)
assert p>q
n=p*q
print(f"n={n}")
flag=bytes_to_long(flag)
messages = [getRandomNBitInteger(flag.bit_length()) for i in range(200)]
enc = [encrypt(p, message, flag) for message in messages]

with open("output.txt",'w')as f2:
    f2.write(f'message = {messages}\n')
    f2.write(f'enc = {enc}')

#t1=39041
#n=31757681951092898377241647622353350811555571588021442714393002561722357855033517882719102833176105251763057313366942759802483366389547670310504898517419619177075155149247837212852121269080431969095421646338619498652624131319645919876504536274428562199882910834700167991957991646691071345200388502034841600000001

output.txt太长了，需要的师傅可以找我要。

回到题目，题目分为两部分，第一部分基于一个奇怪的get_Prime_leak函数生成了两个大素数p、q；第二部分将flag放在指数上，然后做一个有掩码的加密。这也就是说，第一部分应该是让我们获得素数p，从而能够求解第二部分的离散对数问题。

但是其实第二部分是N1CTF的e2D1p一题，在这个题目中是可以直接用第二部分恢复p的，详细推导可以见：

Crypto趣题-Lattice | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

我也是直接从第二部分尝试入手的。但实际实施会发现，这个题目中flag有183比特，但是e2D1p中仅有159比特，而就是这样一个flag的比特长度差异，导致我们需要的左核中规约出的短向量长度依然很大，没有办法在有限时间内进行幂乘运算(不太明白我在说什么的师傅可以先去看看e2D1p我的题解)。具体来说，e2D1p中规约出的短向量数量级是下面这样：

(-28, -58, -136, -183, 73, 41, -45, -37, -75, 129, 89, -14, 23, 31, -31, 6, 46, -79, 15, 53, 82, 16, -10, 6, -8, 102, 114, -58, 7, 90, 51, 62, 21, -49, -140, 209, 21, 90, 17, -27, 60, -123, -64, -65, 72, -159, -124, 72, -88, 101, -64, -11, -139, 169, -18, -93, -49, -66, 27, -2, 111, -68, -87, 41, -103, 2, -176, 61, -41, 93, -92, -60, -64, 38, -40, 156, 79, 141, 103, -12, 25, 1, 158, -18, -36, 8, 63, 164, 15, -101, -160, 64, -66, 23, 105, -70, 71, -38, 41, 37, 2, -85, 72, -107, -41, -77, -117, 77, -250, -55, 13, -148, -34, -36, -119, -44, -117, 98, -101, 23, 154, 32, -11, -17, -52, -29, 81, 182, 26, 45, 162, -29, 71, 114, 44, -21, 11, -37, 6, -119, 19, -22, -76, -41, -41, 17, 146, 73, -82, 41, -52, -91, 130, -25, -6, 24, -2, -39, 16, -76, -59, 15, 64, -118, 40, -155, 141, -32, 143, -67, 78, -43, -58, 18, 131, 55, -34, -24, 27, -20, 128, -172, -3, -3, 38, 14, 189, 128, 158, -164, 107, -53, 70, -67, -32, 4, 18, 36, -81, -117)

但是本题规约出的是下面这样：

(615531, 820840, 1843883, -988269, 1428114, 1582152, 1858592, 416398, 1347348, -1249922, 493164, -13983, 1130024, 1207762, -83772, -1709002, -3710981, 1039779, -3519123, 907341, -2290927, 1126688, -1249423, -628301, 1916755, 521537, 73886, -186219, -219367, -1906389, 1594946, -120368, 166749, -1244087, 134738, -538176, -668121, -1056203, -559497, -34191, 2611364, 4432570, -1553761, -2032445, -1084508, 10039, -3117250, 1811906, -2528854, -1267546, 723272, 209526, 518286, -131043, -2547708, -1392536, -3286900, 1086367, 559683, -3090238, 3206757, 697813, 2242044, -371728, -957366, 3591511, 3179698, -879907, -3571962, -69278, -2108676, -244744, -808858, -628418, 992696, -1803330, -803533, -1487603, 1611449, -2704640, -2402337, -210044, 3150751, -32136, -255605, 1362843, -218480, 1148073, -1481245, 1778748, 3009486, -2402629, -2055140, -233379, 475049, 190266, -2005899, -196650, 770396, 979739, 3141171, -491714, -146091, -128110, -1281062, 260650, -380974, -39241, -1018453, 47184, 597919, 2378194, -105102, -56783, 1635534, -2230566, -684866, 649656, -909431, 412454, -2314462, -173275, -516860, 6333941, -968605, -398729, -754797, 352076, 1182197, -539564, -152936, 384461, 143728, -2349008, -1065335, -2770792, 2956471, -720375, 874597, -1971207, -2306567, -2043739, -3030757, 3705855, 3554038, -188858, -880846, -1461827, 776425, -1640892, -2061636, 1561268, 447146, 1784411, 800767, 590142, 1506176, -885787, 186370, -3483445, 3071150, -1020290, -1274281, -756202, -1208553, 616290, 432768, 2234865, 3184408, -1384911, 1993714, 1300044, -2446183, 1265363, -542953, 142733, 1177658, 1691082, 578373, -798776, 2288770, 355350, 2204661, 536178, 1373409, 1436493, -254000, -704253, 2164140, -3300946, -376660, 459460, -1819436, 2012068, -846015, 1651051, 1783145, 2637474, -1493120, -3108069)

所以直接从第二部分恢复p的尝试就宣告破产了，因此还是要从第一部分入手。

然后看第一部分素数p的产生过程，其实可以发现他的产生过程其实是一个线性的迭代，因此都可以写成矩阵形式。具体来说，第一次迭代为：

$$\left( \begin{matrix} x_1 \\ y_1 \\ \end{matrix} \right) = \left( \begin{matrix} u_1 & 39041v_1\\ v_1 & -u_1 \\ \end{matrix} \right) \left( \begin{matrix} 0 \\ 1 \\ \end{matrix} \right)$$

第二次迭代就是：

$$\left( \begin{matrix} x_2 \\ y_2 \\ \end{matrix} \right) = \left( \begin{matrix} u_2 & 39041v_2\\ v_2 & -u_2 \\ \end{matrix} \right) \left( \begin{matrix} x_1 \\ y_1 \\ \end{matrix} \right) = \left( \begin{matrix} u_2 & 39041v_2\\ v_2 & -u_2 \\ \end{matrix} \right) \left( \begin{matrix} u_1 & 39041v_1\\ v_1 & -u_1 \\ \end{matrix} \right) \left( \begin{matrix} 0 \\ 1 \\ \end{matrix} \right)$$

其实就可以发现规律了，不妨令：

$$L_i = \left( \begin{matrix} u_i & 39041v_i\\ v_i & -u_i \\ \end{matrix} \right)$$

那么其实n次迭代后得到的xn，yn其实就是：

$$\left( \begin{matrix} x_n \\ y_n \\ \end{matrix} \right) = \prod_{i=1}^{n}L_i \left( \begin{matrix} 0 \\ 1 \\ \end{matrix} \right)$$

而根据数量级或者测试可以知道，要生成512bit的素数，题目一共会进行18次迭代，所以最后得到的p其实是：

$$p = (x_{18}^2 + 39041y_{18}^2) \;|\; 1$$

那么问题就在于如何由刚才的矩阵表示形式推出p的值，我们简单观察一下前几次累乘矩阵得到的结果：

$$\left( \begin{matrix} u_2 & 39041v_2\\ v_2 & -u_2 \\ \end{matrix} \right) \left( \begin{matrix} u_1 & 39041v_1\\ v_1 & -u_1 \\ \end{matrix} \right) = \left( \begin{matrix} u_1u_2 + 39041v_1v_2 & 39041v_1u_2 - 39041v_2u_1\\ u_1v_2-v_1u_2 & 39041v_1v_2 + u_1u_2 \\ \end{matrix} \right)$$

有没有发现什么，我们可以把这个结果矩阵写成如下形式：

$$\prod_{i=1}^{2}L_i = \left( \begin{matrix} A & 39041B\\ -B & A \\ \end{matrix} \right) = \left( \begin{matrix} u_1u_2 + 39041v_1v_2 & 39041v_1u_2 - 39041v_2u_1\\ u_1v_2-v_1u_2 & 39041v_1v_2 + u_1u_2 \\ \end{matrix} \right)$$

而如果再进行一次迭代，累乘矩阵的符号又会变成如下形式：

$$\prod_{i=1}^{3}L_i = \left( \begin{matrix} A' & 39041B'\\ B' & -A' \\ \end{matrix} \right)$$

因此，18次迭代后，累乘矩阵的符号表示为：

$$\prod_{i=1}^{18}L_i = \left( \begin{matrix} A'' & 39041B''\\ -B'' & A'' \\ \end{matrix} \right)$$

所以有：

$$\left( \begin{matrix} x_{18} \\ y_{18} \\ \end{matrix} \right) = \left( \begin{matrix} A'' & 39041B''\\ -B'' & A'' \\ \end{matrix} \right) \left( \begin{matrix} 0 \\ 1 \\ \end{matrix} \right) = \left( \begin{matrix} 39041B'' \\ A'' \\ \end{matrix} \right)$$

所以p就等于：

$$p = ((39041B'')^2 + 39041A''^2) \;|\; 1$$

而接下来就是最重要的一点就是注意到：

$$A''^2 + 39041B''^2 = det(\prod_{i=1}^{18}L_i)$$

而累乘矩阵的行列式又等于每个矩阵的行列式乘积，所以就有：

$$A''^2 + 39041B''^2 = |\prod_{i=1}^{18}det(L_i)|$$

这个时候你应该明白了，这其实说的就是A’’^2 + 39041B’’^2是由若干个如下的小因子组成的：

$$det(L_i) = u_i^2 + 39041v_i^2$$

这其实还说明了一个信息，就是p的表达式的末尾的或运算其实只能写成：

$$p = ((39041B'')^2 + 39041A''^2) + 1 = 39041(A''^2 + 39041B''^2) + 1$$

否则p一定不是一个素数，因为如果不加1，前面这一部分肯定是一个合数。

那么题目就很显然了：p-1是一个光滑数，并且他的所有可能的因子就只有一个39041以及：

$$u_i^2 + 39041v_i^2$$

所以我们把所有这样的因子乘起来，就可能可以覆盖所有p-1和q-1的因子，也就是说我们就拥有了kphi，然后就可以用kphi分解n了，而之所以说是可能可以覆盖所有p-1和q-1的因子，是因为只乘一遍的话，若有因子重复可能会覆盖不到。但是这种情况可以想到概率非常低，因为其实素数p和q的生成过程是从200x200种组合中随机抽取了18+18个，所以这36种组合均不相同的概率是很大的。

得到n的分解后，其实第二部分已经没有难度了，因为p-1是光滑数所以可以直接选一组求dlp后与message异或得到flag，而并不需要像N1CTF那道题目一样逐比特恢复。

from Crypto.Util.number import *
from gmpy2 import powmod
from tqdm import *
from output import message,enc

t1=39041
n=31757681951092898377241647622353350811555571588021442714393002561722357855033517882719102833176105251763057313366942759802483366389547670310504898517419619177075155149247837212852121269080431969095421646338619498652624131319645919876504536274428562199882910834700167991957991646691071345200388502034841600000001

#get p
if(1):
    possible_factors = []
    for i in range(1,201):
        for j in range(1,201):
            possible_factors.append((i**2 + t1*j**2))

    t = prod(possible_factors)*t1
    s = 0

    while t % 2 == 0:
        s += 1
        t //= 2
    found = False

    for i in range(1, s):
        c1 = powmod(2, powmod(2, i-1, n)*t, n)
        c2 = powmod(2, powmod(2, i, n)*t, n)
        if c1 != 1 and c1 != (-1 % n) and c2 == 1:
            p = GCD(c1 - 1, n)
            q = n // p
            if(p < q):
                p = q
            break
#p = 851426256549592873082727423545889441110074820054059061952308788642530493828078879678106440812002682564381088139664528922266220966196398184854034841600000001

x=discrete_log(mod(enc[0],p),mod(64901,p))
flag = x ^^ message[0]
print(long_to_bytes(flag))


#DASCTF{0psu3G0d3Best_%}