长亭-PWNHUB系列

sign_in_rsa

​ 给了五个friends的公钥，其中N都一样，e1-e5不同，推导有：

flag^(e1*e2*e3*e4*e5) mod N = c 

​ 由于还给了一组N,e,d，所以可以通过ed-1 // N 计算出k，而k+1 通常就是ed-1//phi,那么可以求出phi，最后只需要求出e1-e5的乘积对于phi的逆就可解密。

from Crypto.Util.number import *
import gmpy2

c = 2621668640772056420471560098924704127784856790481388457844412769822118088860174800889321751481674422274270598394172919656578632970378187564960846030071830293875552723490431731972841568891484366856527528595054839456764493791012121047269761236912586905892771816051261702781783915560998982829509529868080760864895962974173385898354122495270178096361803788632815673814331531474332060419597040425174040815031894440262657639509623993308964349172916870911290368660953787873798343194799625182081014696063160131605363197089825537641567810410348240587342655465209891653946637101421879415183319402455214734741851508514452049810
e = 0x10001
n = 15029760235374231085969639414731714595094502023579580515142415364576906256445975070594748351717296265506796113025536826427911733196972964855469386448087417878697745924349624863909303165292167253527223263941652633363973854290523602860560486258509324353520104509387932968280508674316342236523385959602558170958614970693493378178016898028008319433088550790771390116863660130486812753414200478905354927474330477084174838392457570478397763649784441576899752400739324537777431123697771882670997321209911034933464741353255233083149611904906129535499692359926063803373853328404277847957250932127456840832115242266989310408337
d = 6510060024132448812692374598562478938781873276826121917136087171433612126001066486549172550775880633671688073309060742661536694848138785012316851139079566219427085669995770343650050947604387625705743119055063449704794632066543990637391557798194976737161835401498317792553501071727695913273255675957670000137254200491232988916899437811704442351184491702933366588255664254218916419493613957433723990485119540500734398920034539046985131363424063852960232153505171116298416691316690158260663800875225380729824947022224315510290836013992740531252154869626076244458736535349817731705617890688617614422279803126347527748253
k = (e*d - 1)//n
print(k)
phi = (e*d - 1)//(k+1)
l =  [(15029760235374231085969639414731714595094502023579580515142415364576906256445975070594748351717296265506796113025536826427911733196972964855469386448087417878697745924349624863909303165292167253527223263941652633363973854290523602860560486258509324353520104509387932968280508674316342236523385959602558170958614970693493378178016898028008319433088550790771390116863660130486812753414200478905354927474330477084174838392457570478397763649784441576899752400739324537777431123697771882670997321209911034933464741353255233083149611904906129535499692359926063803373853328404277847957250932127456840832115242266989310408337, 107273), (15029760235374231085969639414731714595094502023579580515142415364576906256445975070594748351717296265506796113025536826427911733196972964855469386448087417878697745924349624863909303165292167253527223263941652633363973854290523602860560486258509324353520104509387932968280508674316342236523385959602558170958614970693493378178016898028008319433088550790771390116863660130486812753414200478905354927474330477084174838392457570478397763649784441576899752400739324537777431123697771882670997321209911034933464741353255233083149611904906129535499692359926063803373853328404277847957250932127456840832115242266989310408337, 80021), (15029760235374231085969639414731714595094502023579580515142415364576906256445975070594748351717296265506796113025536826427911733196972964855469386448087417878697745924349624863909303165292167253527223263941652633363973854290523602860560486258509324353520104509387932968280508674316342236523385959602558170958614970693493378178016898028008319433088550790771390116863660130486812753414200478905354927474330477084174838392457570478397763649784441576899752400739324537777431123697771882670997321209911034933464741353255233083149611904906129535499692359926063803373853328404277847957250932127456840832115242266989310408337, 110281), (15029760235374231085969639414731714595094502023579580515142415364576906256445975070594748351717296265506796113025536826427911733196972964855469386448087417878697745924349624863909303165292167253527223263941652633363973854290523602860560486258509324353520104509387932968280508674316342236523385959602558170958614970693493378178016898028008319433088550790771390116863660130486812753414200478905354927474330477084174838392457570478397763649784441576899752400739324537777431123697771882670997321209911034933464741353255233083149611904906129535499692359926063803373853328404277847957250932127456840832115242266989310408337, 125399), (15029760235374231085969639414731714595094502023579580515142415364576906256445975070594748351717296265506796113025536826427911733196972964855469386448087417878697745924349624863909303165292167253527223263941652633363973854290523602860560486258509324353520104509387932968280508674316342236523385959602558170958614970693493378178016898028008319433088550790771390116863660130486812753414200478905354927474330477084174838392457570478397763649784441576899752400739324537777431123697771882670997321209911034933464741353255233083149611904906129535499692359926063803373853328404277847957250932127456840832115242266989310408337, 77641)]
e_ = 1
for i in l:
    e_ = e_* i[1]
print(e_)
d_ = gmpy2.invert(e_,phi)
print(long_to_bytes(pow(c,d_,n)))
#flag{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y}

Luukaka

​ 解题分两部分：

1.lucas序列求fake_p，题目给的代码可以求出一个和p的高位相同的fake_p，低64位是随机生成的，那么可以用copper求出真实的p。

#sage脚本，copper求p
def Function(times, a, b):  # lucas序列
    F = [2, a]
    for i in range(times):
        F.append(a * F[-1] - b * F[-2])
    return F

a = Integer(0b11011101110111110)
b = Integer(0x11011101110)
s = (Function(77, a, b)[-1])
while 1:
    if is_prime(s):
        break
    else:
        s = s >> 1
tmp = (s << 64) + getrandbits(64)

while 1:
    if is_prime(tmp):
        s = tmp
        break
    else:
        tmp = tmp + 1
p = tmp

n = 14228073730190667444265758569232998545834341711432864414441434537856457554226009751489033431705491278975339077931622009743639467631071474363151300487078680100432725518596365988395929461561533250434031486424245896944629925135857622729999223390971276553928997508637911376545709237354833737994060265750787364825469605787468954601744025244062927831728713075259243916071854001703095748019042346899025896785151209455462423075169662092252456008356019267117214041106983803825784779879133738561202953888980952580302263891778856965344625783352907638953070740712616009213478262015624504889618788466893252102409611427088945902084609824939158090273141699828781599
p_fake = p
pbits = p_fake.nbits()
kbits = 64  # p失去的低位
pbar = p_fake & (2 ^ pbits - 2 ^ kbits)
PR. < x > = PolynomialRing(Zmod(n))
f = x + pbar

x0 = f.small_roots(X=2 ^ kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.3
p = x0 + pbar
print(p)

2.已知p，q求Paillier的私钥r，u解密（关于这个算法应该博客有记录）。

#求解Paillier加密
from gmpy2 import *
from Crypto.Util.number import *

n = 14228073730190667444265758569232998545834341711432864414441434537856457554226009751489033431705491278975339077931622009743639467631071474363151300487078680100432725518596365988395929461561533250434031486424245896944629925135857622729999223390971276553928997508637911376545709237354833737994060265750787364825469605787468954601744025244062927831728713075259243916071854001703095748019042346899025896785151209455462423075169662092252456008356019267117214041106983803825784779879133738561202953888980952580302263891778856965344625783352907638953070740712616009213478262015624504889618788466893252102409611427088945902084609824939158090273141699828781599
p = 89993381987137506011679842153708782600347540345541532955617801526876380951385052938276977563645108845230982081550367480695643488174519956646559392653544017312457803311443093956372962621108795325336827097398138660534143621582730017517058772398513495619577181034288859950414446489334860611610502414840411291040940750561767344688920500749873731
#print(gcd(n,p))
q = n//p
c = 110337660867664870668618596423399170421957516047679509225588623376743804308910177330738477934885576296064264107955132608068039716915229141255177656762910257465732348532323965821043865294553028096906547082618551373641823894294345439394320458729379584778338791447390149190354594056272453424922259417177887790371636260596466767307663828504719149380793176963386400546201890745560501746937761750771953027692686082999321908948997715677766808897936775024313229131624361695754073181908392043158729516103179521695533235615975097099246881718801578279171894214275303379728310998576306972004917364359907184627898803582606166064132907209594129554305783857639940803580780162589238990527574402229360311452329673309294811095686032780187382402401244208403608246186488287045631870185466768772070155917361936402870757098225660585142716834782054689740016959635568917565989361153748200711957665416078406041043067068946260735419003117885045170538814091969325447811589483805740159257095544507862038022099086715866062568327078082077714811272019367066364077835278254199402087714107154020099620284929159828186078676335901409411843708088949544768400190126243155520427016805835963333341089705359758522086506203013124445829394093909811080012839871046714948018821673486671778352056836826280481951815377888832291151086485700501159
g = 104756338318355948567384664103742452654286797799572772265848233334512623038814223410545840475708213491580933168492941525415723077772925906306730070567912467752229764629077391411738146979960676773739966985033493353135734679863468554065367379641641877776732166787383073606968314307988023048157536642389004806055502363198290047464507135522056378518722299068757453041609390692043233878813029502849305103895304519202811596850440711557164909395610847550061798126016783826231721060875732764619258276319683759960874598610474526487116193287935726659807081799695149604873036088612391197272153090414815760539467909235655538189612951075972603409435247362402276881345593351325034626085319241822974931255362490361433247117438845892276212349225050480473723922773661650238241659376681125743246319687880452040595990284620390242076959726572663250706701440702801135388505126093218792766996298711732747845811266552028107611595554772334895684283839272384369606543632542613172335294487221561323491737934377355876532240725521412046012357801914284413206938819420564131912564088387486730018108094449689965565218873981804619434009206386324135567769774069088701758230799594812616518042137489600048047478571983854027089251082355287707549749663822654965131297650047047655863594589307878048709000265824696160267631742318727023504
r = lcm(p-1,q-1)
u = invert((pow(g,r,n**2) - 1)//n,n)
m = (pow(c,r,n**2) - 1)//n * u %n
print(long_to_bytes(m))
#flag{P4ll13r&C0pP3r5m17h_m4y_b3_g00d_Fr13nds~}