Shallow yyds !!! 被shallow讲的直接就一下就出来了太棒了!emmm我太菜了...阅读能力真弱...
# Strange_GCD :
题目描述上讲了 Approximate GCD Problem . Reffered on https://martinralbrecht.wordpress.com/2020/03/21/the-approximate-gcd-problem/.
这种 AGCD 问题对于解题主要是一种 LWE 的思想去做题.... 我一开始查到也是大概就是 LWE 的思想,但是自己造格子造不出来,就没做了..emm 接下来开始分析一下题目 p 444 位,q 666 位,r 333 位
可以知道他给的所有 Ni 都是掺杂着 扰动东西 ri ,我们可以得知这确实很像 LWE 的内容。但是格子该怎么去造呢?继续看
可以得到
同时我们知道 如果
或者
于是我们
我们就可以计算
并且
并且 , 所以 就使用这条我们就可以去构造一个向量 以及一个格子
于是得到的目标向量 接着我们对这个向量进行观察, 都出来了,同时 r 是 333 位的 我们如果 N 整除了 q 得到的就刚好是 p , 检验一下 成立 ,那么我们就可以去解密了。
exp:
from Crypto.Util.number import inverse, isPrime, long_to_bytes | |
from gmpy2 import* | |
N = [8321077117329356263954581766837194016859681833859374146551469738742553789565498761528408178000096341991081753628879035591190841107228873036782248755852096597317053559269854941020999105514186022112075838112491499884564745335454966665835001848999256218403570429047541524272647861099813598603292295695775504244505874838019009730562620216, 9663141503982563384103774905603769762205667685102275298721284964403449121449261483138514307090449027807047697811539118959328065885920230514670112839967221129701708335087378871176539521374006686377418843364889059913595942583737991465545688834167085579154677350865488342245644093471665857007588133415608450554035129609049971856915687905, 7080633525505006454857949889380886258474613936169915325357991912983821798902257837234148311383635716165386646093418183743215120431715933036921480432793786600194625124412063608565640368381660643929081066605712749838630092722581230189543696229548387666046034403406721477818265752443487173947232032487026509033018565048660685068628813900, 6348260112940191945095264085450804431350547836448100928568733296493334845533262312663784701113046746633754397388581143523779371919889446537883618910341310362947454041409541741124231406605654693961025815677260091930522280737378333554694234586235628097018111636491016261274584391201625445101930372416766825601778759258114504767453644116, 5453076441876067965962987075376616480678826248967242473452690159966124023105342358461519279607336831463834252487811766366887983597918775466645199024629945952612311092154451713992362747056489054444283302530500475646346968235522866557033556131387030809018889094871163097069588840212411234716020934787724757538389436231926479459435139729, 8539092301764573132139384894241535432591998166686651428176862041680365196821019488767353225937458669267710968146783359781905669306801237140282934737328995064410005908343087032652676207615356474601039341695241288937409773110450995503958663731870314493254162942656333393836208952363635746218345484752702086447693272390570444229475023063, 6519174659211289290465989985638494640591837577268694359892571134942820094011179335155100770258746122812579164176239810640710311061280175847537113068566174335469669480601670136633042879486860594176408555229541384726863069317134887988109513500264430505092783429319336134768414472691544453196941818593187717904852926051114502346647888426, 6961711680362025924587083752271982856615461409839316941574792747717174299272141804413488210456939607971950020060573061131683587521057101549266612028332060247289306929784809695126285828514889617483817766102136513569391338432827451306976412448973958662677599051104723480081915666230391091496248279567627159875132838397868850500912784991, 5464727156582411007360377345208743900616053705663005668786499961992377236151787056734059201141143278419642045996194426551642956434137382420547801325331080754615348522599387497424727626522195285281557448617564720973185851757117201639221059630112719699600469361046245232476531622290326229811709079901764559526124144866364301870192468062] | |
M = N[:] | |
M[0] = 2**334 | |
''' | |
L = Matrix(ZZ,[ | |
M, | |
[0,N[0],0,0,0,0,0,0,0], | |
[0,0,N[0],0,0,0,0,0,0], | |
[0,0,0,N[0],0,0,0,0,0], | |
[0,0,0,0,N[0],0,0,0,0], | |
[0,0,0,0,0,N[0],0,0,0], | |
[0,0,0,0,0,0,N[0],0,0], | |
[0,0,0,0,0,0,0,N[0],0], | |
[0,0,0,0,0,0,0,0,N[0]], | |
]) | |
P=L.LLL()[0] | |
''' | |
e = 0x1337 | |
P = (9198383558649454145266329742592651804417531074705208606546350510907008625231001966812954022871638810611704119348096876032201336180492815698993817487634671245603146146272244377218492738092114522582641697639688837841786461196752729903611725131373737251243910142850547018441698749894323950503164083437568, 104098035638581595369723778375711537486830709046687306114704921816239533823901066113680320504395210089789340199402154288158599251547931748565815387310900885326892681968536308019715590493310968628489043723240348362149053110811668282038727688689374505928586075094912392544924601844136642390813222425809, 1102834391862716869946827309486981604079530638763397950737361315055931768373793498250981455412829162997772327814660070857951309312894092377859437366989526531813223828179941289064128320123411973263239142716310770401174174815638810202859450962632995611863799694649198457635953086959463939627719575381012, 753994729336183961852361196205654448289304004519434287316796470222521627865083763102251102951626213588497716067551706990220346381353586508856365765536744873026409087910505560761761024675350156647185336440841519838638415417607956807382719719007131540587566462617043290548957627028678429439567176392108, -71708524916293121808333775279085691365967960919759775147913431698619192878017855212957980666806523648996086462040461850162074426038300683815953081712090679643498963889027587516137252350693864785830427057530016147319149926968346502476418390469709928547235995568090970863872980806983047965126211827423, -1031944069356990593465028628753183012193322903943969718261363844383250576817774501764794204795605186147444430878687291921605373814843580367545369212301939780213941922732623750390324618190490307261983930269957183493345355165692496865409582827167136484989492550271511982793001065621702409883049993239817, -1960547215826715829528682564527292643865866291188443591530567078511330848396016229325567425830200701694380104625201031396661972809519249893882531604307311435727272867042265335921514343841646164420771255718802644103398765492144311189111408831887333483581772033575516358581006829893858562536866631199694, -1402335387560657499009395932180425308829816453818907356038567333645529829409747360872073366794556975860774421104509218449157997408918101385420918273310166387609041772539330599075043569860214109051067579537008367501834723009929827486300772678346407596106869832512579102180928086682172345775047825906065, 6492859743402427013224957526773612476031280993044690607784160057686880229209831538939045987606076773313125546427811186808795218860181360435151657439459135171731642225975056613348164819235317913083153227881911185574679170305638348499347070097938480392885289493284095645409615468925393679398090634630) | |
C = [800378461059400239726680783421062702546581299113618553895453491207714321944554499622887232532612118204284779120928524046451494597619154079853122057618867592408424421335915888671560524092660578952242621890439766919785431411789789232309134048322721650012432166587969915464252995890054635969469155870141839815222805619769926841873928532, 8685468246369062574820183134847029157229023858170863526469628501966638181721681547114662091162797572149161013458000532984909663639626346493828947027439012131912176125653717020650233650230608573276523862941298063827867869000918623143520066067119099918633173584693454642685133071154989133688921507896223776765538029556643440655490373815, 4635611296372235589362291842711945807825964919968727011796279830725567747087132786100965922682161492876463568645940638975728831156672106717718242995621775763972524561170035488180440169190421072680121175269363490806991700969253196228364471655905426168859215651384013432550900570720981720919343406680667172355882395426739478340888619526, 742099161415136628218807400531862454374875770332166710320711769923774839345990297388615457974047093967700994503615622499139058644697776431451063778211507061619987487339659448529973693084099004007650792690143707738139278995489030445825999666762580518420739517354868021396496747289677543653758101688499365196709600349831855157276274803, 4273006447766599851029197343910625305964779588947130545729882009677080459892767902139074897266046998378948193319329776150920821074305998905666368175737032487336505440974393061632257356697260043478850055918798196360043557336723402834256592984312957607731622934368169520289756716653736422872196593367101920308166527352079412344590114695, 1337615323422531101514598853478737615483725265103339849469231329210692205474781484172946466402355800190175297435923447189337380569240535257395618353403524999296122247241720498058900285176383928871155893061316083476812641934026019749574784965397208046520128690081232283708190247657782663414534596381371506499151016470118707739609022847, 6153442337491399463730666360630451953223069596225489087488144486112604050064388945200405772892415725900338512969888610774357818442533883395713661512978158729825590405567077341407532331228257558692149544940358814513930330757334104407683768945074261746314376336567331685071086776886141587264981001140113933152084084711732651014186070962, 3604640305526232611907645024550062043296875756707299105733076926046725900367109300556792007038226350415916164581084668832286944703572581980333135146219609212135443758296278947833224676930513359604019639508959092586550129343133801670578311053639151186604019506764426302411065588655525183584977810609190948096510237056027272167828516985, 2085633143403792178757363870459578017278494765962824809917819295576034993395441252397370078671500834434293581806342828037037877739374959864038090394888141183851040814572501861997433316552606005140700519616064369570511427453278726929921212633252656552135711332324923683242632912449218888750151556281762432994484741408165895663710356342] | |
p0 = 9198383558649454145266329742592651804417531074705208606546350510907008625231001966812954022871638810611704119348096876032201336180492815698993817487634671245603146146272244377218492738092114522582641697639688837841786461196752729903611725131373737251243910142850547018441698749894323950503164083437568//(2**334) | |
Q = [p0] | |
for i in range(1,9): | |
Q.append(-(P[i]-p0*N[i])//N[0]) | |
P = [] | |
for i in range(len(Q)): | |
P.append(N[i]//Q[i]) | |
D = [] | |
flag = b'' | |
for i in range(len(Q)): | |
D.append(inverse(e,(P[i]-1)*(Q[i]-1))) | |
flag = flag + long_to_bytes(pow(C[i],D[i],P[i]*Q[i]))[-5:] | |
print(flag) |
# nomore:
这道题主要就是 python3 中 y+1/x 能实现 那必然是整除,python2 中 “/” 就是整除 好家伙... 并且 k 也得小才能去爆破出来解 同时 x 也给了个上界。
,带入式子 A 发现他是单调递增的,我们就可以去二分法求得 x ,但是 我们得知道 k 是一个小的数 ,那么就二分法去爆破 k , x ,于是就得到了 x , y , 带入 secret 中得到 secret。我们再看看 secret 以及 secret 的大小,发现是奇数,那么 e 也是奇数,开个三次根,发现也不是很大,但是是在 190w 左右 ,并没有题目中给出那么大的界,就直接去爆破 e , p , q 其中使用一种中间相遇的思想 仍然是个三次的数,就可以直接出来了。
exp :
from Crypto.Util.number import* | |
from gmpy2 import* | |
def bruteforce(secret,primes): | |
for e in range(9001,10000,2): | |
for p in primes: | |
if iroot(secret-(e**3)-(p**3),3)[1]==0: | |
continue | |
else: | |
return (e,p,iroot(secret-(e**3)-(p**3),3)[0]) | |
A = 2235930885430590738951770802593215586722001521194365487273377655750584443688709547709496531484159367793509666612116139038917661713102981488722293426038029073850795986080412124312908732573382156365974821471629333126275130148211145598662897276781331183691743094904957217401055325352877284530068805608962270139656431076370452327497416723045785664344412694060886085511378779487559306015113302658964110922621164879307182468690182325142055960562810349297544601157473985262796723316777380726315782859115449976700612343978057140270903396910431420116573138154719798955123904805279320166126412714788508008881174164656203605409187705643395043643983135944514470267283183175620492198093264226038082725867230101096344723124629565311122528005863046865164876192248803940590219355154176343702897505891392317123983475290611327887699795851456183931854177169939743970260837586185988111368384484356413787993370384262996486824251003884057486063787194241555190688935624792041028246639984544749568167915235629185515957106136630401960066317998226671344793061752525215496195839080165952892472180997564802474095868944184005854120238623750555477937802107959321257495435617363809377093354132077991399603767147974592666019334636208414969819333321639542282741932229892501074615920120228860717401055433206357806353717291748096464569063777964784860874773660469621546777686833078007220613545223169043960754010332944526795605043595879174073360317477199909570141202125189377475655277483919081658123820105695508771837612756891055031293872293977244105248233915807603916034288916844336329883443200123825714530812637709561686224468031953278836676202928878535091578725509651544544672494980806630321114490828976895602038151224026672265830787863940762596976124958000977955469148027648603199590311852993367450800166591526272653355552342455506908317529193196174849749103073968182002498580115241030154502931088245539152380579199202750010140022979979488971008874424439325749039212427088023136971891092490697689178097172878439007028844083681030357488034860471042630885195387680286557424780235116405464735985082715745087677866688657626763753940919966662710093619034074861812080778855241391731006 | |
for k in range(100): | |
r = 4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 | |
l = 0 | |
for i in range(1021): | |
x = (r+l)//2 | |
v = (x -1)**7+(k*x-1)**5+k | |
if (v == A): | |
print(x) | |
print(k) | |
if (v < A): | |
l = x | |
else: | |
r = x | |
x = 3009497962071627970325880719364587885671010480057866287334251735956364570350347087026477982283392009667042015682364869764534877202626872343001563490279098970253786309533656152965171286503259912849977668331206169132653702870703716072003169079329188859516303445545911170476352380900189590650131003576924340724 | |
c = 693282726315 | |
k = 84 | |
y = k*x-1 | |
secret = (x + y) % 7754486886526049041 + 210729175671163973 | |
jie = iroot(secret,3)[0] | |
primes = [] | |
for i in range(1000001,jie,2): | |
if isPrime(i) == 1: | |
primes.append(i) | |
print("done") | |
e,p,q=bruteforce(secret,primes) | |
c = 693282726315 | |
n = p*q | |
phi = (p-1)*(q-1) | |
d = inverse(e,phi) | |
print(b'MRCTF{'+long_to_bytes(pow(c,d,n))+b'}') |
# Common_Prime_RSA
这道题 emmm..... 从多元 Copper -> BSGS 解题思维.... 真尼玛放缩题... 如同浙江高考数学最后一题导数放缩?(xs Reffered on https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.1333&rep=rep1&type=pdf
先分析题目,给出了一个 明文 +g1 + 明文 段的内容,我们可以想到 CopperSmith 的解法。只要换成了首一多项式 在 sage 里跑就可以得到了
n = 0x48b11209b62c5bc580d00fc94886272b92814ce35fcd265b2915c6917a299bc54c2c0603c41f8bf7c8f6f2a545eb03d38f99ec995bf6658bb1a2d23056ee21c7230caa2decec688ea9ee00b0d50b39e8cd23eb2c3ddeb20f5ab26777b80052c171f47b716e72f6aee9cece92776fc65119046f9a1ad92c40e2094d7ed7526d49 | |
e = 3 | |
c = 0x27d8d7249643668ffc115be8b61775c60596e51f6313b47ad5af8493526922f5e10026a2cdaef74e22c3eec959dd8771abe3495b18d19f97623f5a3f65f22ff8fc294fc37ceb3b43ebbbf8a9bcf622922e22c5520dbd523483b9dc54fdffcd1a1b3f02ca1f53b75413fb79399ca00034f2acf108ac9a01bd24d2b9df6e27d156 | |
m_low = 12174832913272944860601983973507591320681689815583717341813397700955082069528318044500277669230782878838402371536356670567072055281703856945#464 位 | |
m_high = 43068805484541415698874685945122116488177521029738607414688723817811466178438704211475601610458271809578314787221337437676782823427096603325480109722746064453605749460332117411578252753615112132108843194498669812000013922027642492460715110657531599266817556380763143511900612854154688377602965504 | |
PR.<x> = PolynomialRing(Zmod(n)) | |
f = (m_low+m_high+x*2**464)^e - c | |
f = f.monic() | |
g1 = f.small_roots(X=2**232,beta=0.4,epsilon=0.04)[0] |
在观察这道题目,已知 g1 , 但是要求我们去求 a 和 b ,才能够求得 n1 的因子 emmm 这道题 考点就在这了... 看上面参考的那篇论文 我们设 beta=2g1 , s =(n-1)//beta ,那么我们可以推导
我们只要得到 c 是多少就能够得到 x 和 y 分别是多少了
通过 v 去变换得到 ,观察这个式子我们发现: beta 和 v 都已经知道了,那么接下去我们看 , 并且题目中给出了 则可以得到 那么接下去,我们可以知道 发现这是个对勾函数 , 接下去我们就可以发现他的大概范围中 ,同时 关于对勾函数的性质 我们可以知道 ,于是我们就得到了 c 的大概界 为
接下去得到 c 的界为:
g1 = 1328458990599515056771144217738449144496664370133586446617480019409757 | |
n = 0x48b11209b62c5bc580d00fc94886272b92814ce35fcd265b2915c6917a299bc54c2c0603c41f8bf7c8f6f2a545eb03d38f99ec995bf6658bb1a2d23056ee21c7230caa2decec688ea9ee00b0d50b39e8cd23eb2c3ddeb20f5ab26777b80052c171f47b716e72f6aee9cece92776fc65119046f9a1ad92c40e2094d7ed7526d49 | |
beta = 2*g1 | |
s = (n-1)//beta | |
u = s//beta | |
v = s% beta | |
left = (2*int(sqrt(n))//beta-2-v)//beta | |
right = (3*int(sqrt(2)*sqrt(n))//(2*beta) - 2 - v )//beta | |
print(left) | |
print(right) | |
print(right-left) | |
print(iroot(right-left,2)) |
因此 用 BSGS 方式 爆破得到 ,
D = iroot(right - left , 2)[0] + 1 | |
b = pow(2 , beta, n) | |
dic = {} | |
base = pow(b , left , n) | |
diff = pow(b , D , n) | |
for i in range(D+1): | |
temp = base & 0xfffffffffff | |
if temp in dic: | |
print(i) | |
dic[temp] = i | |
base *= diff | |
base %= n | |
print('baby step done') | |
base = pow(b , u , n) | |
diff = invert(b , n) | |
for i in range(D + 1): | |
temp = base & 0xfffffffffff | |
if temp in dic: | |
print(i , dic[temp]) | |
base *= diff | |
base %= n | |
#5980588 698170 |
那么就可以得到 x,y 于是得到 p,q
xy = u - c | |
x_y = v + c * beta | |
temp = iroot(x_y**2 - 4 * xy , 2)[0] | |
x = (x_y +temp) // 2 | |
y = (x_y - temp) //2 | |
p = x * beta + 1 | |
q = y * beta + 1 |
后面直接用解,并且知道 后面是 0.3247,同时而且能看到了他是整除之后可以直接得到这些东西。
c = 0xeaf06b9050a809659f962251b14d6b93009a7010f0e8d8f0fa4d71591757e98243b8ff50ec98a4e140fd8a63bbb4b8bb0a6d302a48845b8b09d1e40874fcb586ddccbb0bbf86d21540ec6c15c1d2bf925942f6f384fdc1baae7f8e06150ccd9459eb65d0f07eea16a911fa0a17e876a145dbfec83537ca2bee4641897b9f7f5 | |
e = 65537 | |
phi = (p-1)*(q-1) | |
g2 = pow(c , invert(e , phi) , p*q) | |
n2 = 0x6d457110d6044472d786936acbd3cd93c7728daa3343b35ccaa5c55eba6b35c28c831bb245b8cdd8fc8cb67a72f57e62a0e1259f5e804c487a8478f6895b302d39277bd73947598a5f8ec0a535be9e9a4d34df91df948ee44cc3d13d14e23b9651089e4767c7f0e7245df55619c92fe24483225d35f5f3ee6f74375065766ffd | |
c2 = 0x15be2b0eaef8837a753587c47d3f31696a7d239d88837a9b7d903cd0d0648ef8e225ea555402693a23f305d19e7e13905be61b44c651dba5b26614bcf876234e765a724e0ed8af4a4e408e6a233c48ab9cc63e9c552ef9cd1999512aa0aca830fe6cbcbcc3c6bb354903124a2c3a12d442cdbdefdae6576f4bbc1515051b7111 | |
beta = 2*g2 | |
s = (n2-1)//beta | |
xy = s//beta | |
x_y = s% beta | |
temp = iroot(x_y**2 - 4 * xy , 2)[0] | |
x = (x_y +temp) // 2 | |
y = (x_y - temp) //2 | |
p = x *beta + 1 | |
q = y * beta + 1 | |
e = 65537 | |
assert p * q == n2 | |
phi = (p-1)*(q-1) | |
flag = pow(c2 , invert(e , phi) , p*q) | |
print(long_to_bytes(flag)) |
# Strange_CRT :
可恶可恶可恶!第一次论文看下来都看得懂。结果因为出结果的时候把 dq 当成 k ,k 当成 dq 去算 导致我花了一个晚上时间.... 调大维度.... 甚至去实现第五点的内容,结果也没有成效...ri ... 群里问 wp 看一眼造的格子 不尼玛一模一样... 害 卑微...
贴个 Link :https://link.springer.com/content/pdf/10.1007%2F3-540-45708-9_16.pdf 主要还是多元 Coppersmith 把.
先看题目中 给出的 生成 d 的条件这么长,你推阿推啊推... 发现最后退出来结果还是就这 b 样就是 d=dp%(p-1),d=dq%(q-1) ,那接下去看论文内部,直接看第三块 。我们可以构造出
接下去我们可以通过这个式子得到一个多项式
在这个构造当中,我们有 因为 所以可以推导出
那么我们设两个上界 然后我们可以得知这个 fp 多项式 在界内存在小根 ,接下来我们就可以看到模块 4 了 ,只需要 时,我们使用 coppersmith 中提到过的 方法去构造多项式
这同时也存在着 ,我们可以通过构造格子 n = 4 , m = 2 的格子
并且满足这个格子的 目标向量 的模 小于 ,推导一下为什么这样
计算一下 这个刚刚好位数一模一样... 那就直接用这个,接着主要在扩大一下界的范围 (可能不需要 x)
于是格基规约格子之后得到的第一行向量,拿来直接使用,构造出多项式 然后再去因式分解这个多项式,接着我们就可以看到一个只有一个 x 和只有一个 y 的一个因式,那么没错 其中一个就是 另外一个就是 k-1, 没错这里的是 我也不知道为什么.... 离谱... 我拿 k+1 算就错了。改了一下就对了 ,emmm 大概是因为 k 出来的其实是 负号 前面我们对多项式操作是已经把他取了一次相反数 因此这得到的 是 -k-1 .
贴个 EXp:
from Crypto.Util.number import* | |
from gmpy2 import* | |
beta = 0.34 | |
delta = 0.02 | |
amplification = 2048 | |
p_bits = int(beta * amplification)#696 | |
q_bits = int((1 - beta)* amplification)#1351 | |
dp_bits = int((beta-delta) * amplification)#655 | |
dq_bits = int(delta * amplification)#40 | |
N = 7194944829894746935571965271122989443610702698015123026500274312320541540511952275333536082176132102091625202863345739074691901574020649953130369453360247690506566827078013306825941200018330639608298539682191482947557146237487451707849833303794107411686130468587672820352641436722348277258977791778239539008852841749667581869688275892813664557078043533743669277649148468667399393518112220602616186358353262921270486781426670131125521444335280904901224934061164334131460273779473387748722008412594372005590209919098686472153912130124772089012962023984089123929555594332030502775588070235834837667605812843128059372243 | |
e = 5872666789397408936685003821802975734744078884385553897196686533187747297681714766542317071546532454504513425295170366015384657690105523240363850101369048640430719519784564240908244756652800934680608667950183962226340288720771217107508516125044088043789281574833079766048266075717484676158307477384862873719462770774288252074344824446884295300603035728339571606659365040029505127532956295163195257002051007447197735267997104725561159289832252522298457628452222155625714679911912616173849423059919537353814530280736653541415686756485413316581322357887750268983241858913704388088485132644523120028234659344174431547087 | |
''' | |
X = int(pow(N,delta)*5/2) | |
Y = int(pow(N,(delta+beta))*5/2) | |
L = Matrix(ZZ,[[N**2*X**3,0,0,0],[e*N*X**3,-N*X**2*Y,0,0],[e**2*X**3,-2*e*X**2*Y,X*Y**2,0],[e**3*X**3,-3*e**2*X**2*Y,3*e*X*Y**2,-Y**3]]) | |
A = L.LLL()[0] | |
p = [] | |
p.append(A[0]//(X**3)) | |
p.append(A[1]//(X^2*Y)) | |
p.append(A[2]//(X*Y^2)) | |
p.append(A[3]//(Y^3)) | |
R.<x,y> = ZZ[] | |
f = x**3*p[0] + x**2*y*p[1] + x*y**2*p[2] + y**3*p[3] | |
f.factor() | |
(144242809483056840663075735623298553029680437297789965222541248349475437890222709450048997656976387390752105996145725490546933534602744908786700426835710727511955799912350818546609860818884274334936799981304721460528637717*x + 636751972323*y) | |
''' | |
k = 144242809483056840663075735623298553029680437297789965222541248349475437890222709450048997656976387390752105996145725490546933534602744908786700426835710727511955799912350818546609860818884274334936799981304721460528637717 | |
dq = 636751972323 | |
c = 6601667269134560091452287214083525217696007424340765571114688738279264700361513951309195757650152324371826111195352731779137577044473630747863137747356695892337017953751159248388157498368915463745769509485009626774902347006319659852239932231921393353157319713540010424345134411781723171111939891127671029064626426950125001347122070491553845919803891156107693973027238705710354919725550360159383455222982999904576805089837067774838194257113022653159325313574447189639317397889065351340828031907571541750274329094240472180870714728295651611160552345500801797030280900507979459558944006193012524181456837126192865748097 | |
k = k+1 | |
q = (e*dq-1)//k+1 | |
p = N//q | |
d = inverse(e,(p-1)*(q-1)) | |
print(long_to_bytes(pow(c,d,N))) |
学习到好多好多东西!出题人煞费苦心~