picoMini by redpwn writeup triple-secure

triple-secure (Cryptography)

To get the flag, you must break RSA not once, but three times!

添付ファイル
・public-key.txt
・encrypt.py

encrypt.pyを見ると、n1~3で3回暗号化(RSA)されていた。n1~3は互いに素数p,q,rを約数に持っているようだ。n1=p*q、n2=p*rであるから、n1とn2の最大公約数がpとなる。このように、素数p,q,rを求める。
素数が判明するとed≡1 (mod (p-1)*(q-1))となる秘密鍵dを求める。RSAの復号は、平文をmとしてc^d≡m (mod n)であるから、これをnとdを逆順に変えつつ3回繰り返すとフラグが得られる。
以下、実行コード。

from math import gcd
from gmpy2 import invert
from Crypto.Util.number import long_to_bytes

n1=15192492059814175574941055248891268822162533520576381643453916855435310880285336743521199057138647926712835561752909538944229702432795423884081992987060760867003375755338557996965825324749221386675061886921763747311599846248565297387814717840084998677273427776535730840343260681623323972936404815862969684384733188827100528542007213405382537935243645704237369770300643318878176739181891072725262069278646319502747718264711249767568106460533935904219027313131270918072460753061248221785076571054217566164086518459844527639082962818865640864990672033657423448004651989761933295878220596871163544315057550871764431562609
n2=15896482259608901559307142941940447232781986632502572991096358742354276347180855512281737388865155342941898447990281534875563129451327818848218781669275420292448483501384399236235069545630630803245125324540747189305877026874280373084005881976783826855683894679886076284892158862128016644725623200756074647449586448311069649515124968073653962156220351541159266665209363921681260367806445996085898841723209546021525012849575330252109081102034217511126192041193752164593519033112893785698509908066978411804133407757110693612926897693360335062446358344787945536573595254027237186626524339635916646549827668224103778645691
n3=16866741024290909515057727275216398505732182398866918550484373905882517578053919415558082579015872872951000794941027637288054371559194213756955947899010737036612882434425333227722062177363502202508368233645194979635011153509966453453939567651558628538264913958577698775210185802686516291658717434986786180150155217870273053289491069438118831268852205061142773994943387097417127660301519478434586738321776681183207796708047183864564628638795241493797850819727510884955449295504241048877759144706319821139891894102191791380663609673212846473456961724455481378829090944739778647230176360232323776623751623188480059886131
e=65537
c=5527557130549486626868355638343164556636640645975070563878791684872084568660950949839392805902757480207470630636669246237037694811318758082850684387745430679902248681495009593699928689084754915870981630249821819243308794164014262751330197659053593094226287631278905866187610594268602850237495796773397013150811502709453828013939726304717253858072813654392558403246468440154864433527550991691477685788311857169847773031859714215539719699781912119479668386111728900692806809163838659848295346731226661208367992168348253106720454566346143578242135426677554444162371330348888185625323879290902076363791018691228620744490

p=gcd(n1, n2)
q=gcd(n1, n3)
r=gcd(n2, n3)

ph1=(p-1)*(q-1)
ph2=(p-1)*(r-1)
ph3=(q-1)*(r-1)

d1=invert(e, ph1)
d2=invert(e, ph2)
d3=invert(e, ph3)

key=[(d3,n3),(d2,n2),(d1,n1)]

for d,n in key:
  c = pow(c, d, n)

print(long_to_bytes(c))

picoCTF{1_gu3ss_tr1pl3_rs4_1snt_tr1pl3_s3cur3!!!!!!}

ちなみに、n1~3を式変形することでも素数p,q,rを求めることができる。
n2=p*r → r=n2/p
n3=q*r → n3=n2/p*q
n1=p*q → n1=n3/n2*p^2 → p^2=n1*n2/n3
これを、最大公約数を求める代わりに計算する。
以下、実行コード。

p=iroot(n1*n2//n3,2)[0]
q=n1//p
r=n2//p