[西湖论剑2020]BrokenSystems Writeup3 min read

给了三个文件。

message:

‘Ω?奟?ypG睉晜<U,.

W?盔敲m銖?.嗘7?s来薶只Z???’D?夞%莰}?~a,妄姷槢谏v}玊??#ad??$爝湆鄃0遀;#缮刜2?顪娪k+需?捨HD篹枒筡婌辆 赅?跌婊 CD瓦?3?h?V?p琙|黡UU沯?酟讵分b澾硲€}?~QJ?绫摪 偑鳕塖

?I骟?费JB_?O0&?髀

SxN岑y?

public.key:

—–BEGIN PUBLIC KEY—–
MIICITANBgkqhkiG9w0BAQEFAAOCAg4AMIICCQKCAQEAwgdFIj/1uUss2EEhZvco
iiHyGH4aQhRTkYyrA8gCU0USM+sb3CNjdEIoqoaUqMLLyDP4Dd9AgxpokBsjC4Pz
8P7Uty0LlCteld7ayNzABHoq+5DIHtctOtSbcvyL0NMWfd2qarUWfAWN82rxkLIW
CFu9nWIfm9I6CT5OPZzDh7YnTywznIjhstkIrLM/TiDmR6vuBxSjzORkbolilLeB
A9zJpNt+1oEWTG5sx/0zR24XSmxwcDeyUEkTZfnw63auq6B9svZi2IBIr5jIjHbG
cQ25ZY1J/KDK8fXNmdwH8YhDK0j4VXEWitEPyCS3toK61sql0S/28EySeGtzirGb
twKCAQAdLS8fFz+BzzaP7AbUDUf9kvhhXBLuwUFo8ohCeVK4z1pTj3C6M0G2oXOu
gDdalrDThNlyKxkUn3iUc3Xgoz315pPtq9Xk1Ez/qeUl6gFPP6SZtfeymyGdkLiN
pVquOghjczjXvtBW467Fdb5Wu95TSzVaLndX23rsqW541n8hUwt8PsJKxh+bR0qy
gyIN2VRRNdBlpyTOL49E4y5GDu9fmVgAnFivWVGT135ywl8MsBUFuZPBNTKLEbUA
3KvJVckXf4Od0ENYbiWjEzXn1UN9yebNbU6+yyk34WAmwnkuF0X0Tu1UEb6qtV7Q
kF25GYy9QxERvodGL0Y2njHRpGE/
—–END PUBLIC KEY—–

BrokenSystems.py:

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from secret import flag
import os
rsa = RSA.generate(2048)
public_key = rsa.publickey().exportKey()
f=open("public.key","w")
f.write(public_key.decode())
f.close()

rsakey=RSA.importKey(open("public.key","r").read())
rsa = PKCS1_OAEP.new(rsakey)
msg=rsa.encrypt(flag.encode())
f=open("message","wb")
f.write(msg)
f.close()

使用在线公钥解析网站可求得N和e：

N=0xC20745223FF5B94B2CD8412166F7288A21F2187E1A421453918CAB03C80253451233EB1BDC2363744228AA8694A8C2CBC833F80DDF40831A68901B230B83F3F0FED4B72D0B942B5E95DEDAC8DCC0047A2AFB90C81ED72D3AD49B72FC8BD0D3167DDDAA6AB5167C058DF36AF190B216085BBD9D621F9BD23A093E4E3D9CC387B6274F2C339C88E1B2D908ACB33F4E20E647ABEE0714A3CCE4646E896294B78103DCC9A4DB7ED681164C6E6CC7FD33476E174A6C707037B250491365F9F0EB76AEABA07DB2F662D88048AF98C88C76C6710DB9658D49FCA0CAF1F5CD99DC07F188432B48F85571168AD10FC824B7B682BAD6CAA5D12FF6F04C92786B738AB19BB7
e=3683191938452247871641914583009119792552938079110383367782698429399084083048335018186915282465581498846777124014232879019914546010406868697694661244001972931366227108140590201194336470785929194895915077935083045957890179080332615291089360169761324533970721460473221959270664692795701362942487885620152952927112838769014944652059440137350285198702402612151501564899791870051001152984815689187374906618917967106000628810361686645504356294175173529719443860140795170776862320812544438211122891112138748710073230404456268507750721647637959502454394140328030018450883598342764577147457231373121223878829298942493059211583

可以看到e很大，想到使用维纳攻击求得d：

d=1779217788383673416690068487595062922771414230914791138743960472798057054853883175313487137767631446949382388070798609545617543049566741624609996040273727

求解p和q：

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import *
import gmpy2
import random

pk = RSA.importKey(open("public.key","r").read())
n = pk.n
e = pk.e

def getpq(n,e,d):
    while True:
        k = e * d - 1
        g = random.randint(1, n)
        while k%2==0:
            k=k//2
            temp=gmpy2.powmod(g,k,n)-1
            if gmpy2.gcd(temp,n)>1 and temp!=0:
                return gmpy2.gcd(temp,n)

p = int(getpq(n,e,d))
q = int(n//p)
print(p)
print(q)

可得p和q：

p=149604112324264915811376746906108325951188179904814259006959765070266946659481820938211689946210254302179197289522748397160602946376246768419310765669852537378426700376878745285639531531077237124655345323906476180103106894642043615024716862503414785057646920410083538192951872861366496901158348770066798098371

q=163724217068973025857079545677048587508164102644298632911494474022224582218067057349189211462632427829087720476013052665037199232658015194718500750961261016558605363103092187533086949903145449057015220561698195502163792192055762108803714387175594231859738263839090338762578040513451585421537323416472060788989

from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA

n = 0xC20745223FF5B94B2CD8412166F7288A21F2187E1A421453918CAB03C80253451233EB1BDC2363744228AA8694A8C2CBC833F80DDF40831A68901B230B83F3F0FED4B72D0B942B5E95DEDAC8DCC0047A2AFB90C81ED72D3AD49B72FC8BD0D3167DDDAA6AB5167C058DF36AF190B216085BBD9D621F9BD23A093E4E3D9CC387B6274F2C339C88E1B2D908ACB33F4E20E647ABEE0714A3CCE4646E896294B78103DCC9A4DB7ED681164C6E6CC7FD33476E174A6C707037B250491365F9F0EB76AEABA07DB2F662D88048AF98C88C76C6710DB9658D49FCA0CAF1F5CD99DC07F188432B48F85571168AD10FC824B7B682BAD6CAA5D12FF6F04C92786B738AB19BB7
e = 3683191938452247871641914583009119792552938079110383367782698429399084083048335018186915282465581498846777124014232879019914546010406868697694661244001972931366227108140590201194336470785929194895915077935083045957890179080332615291089360169761324533970721460473221959270664692795701362942487885620152952927112838769014944652059440137350285198702402612151501564899791870051001152984815689187374906618917967106000628810361686645504356294175173529719443860140795170776862320812544438211122891112138748710073230404456268507750721647637959502454394140328030018450883598342764577147457231373121223878829298942493059211583
d = 1779217788383673416690068487595062922771414230914791138743960472798057054853883175313487137767631446949382388070798609545617543049566741624609996040273727
p = 149604112324264915811376746906108325951188179904814259006959765070266946659481820938211689946210254302179197289522748397160602946376246768419310765669852537378426700376878745285639531531077237124655345323906476180103106894642043615024716862503414785057646920410083538192951872861366496901158348770066798098371
q = 163724217068973025857079545677048587508164102644298632911494474022224582218067057349189211462632427829087720476013052665037199232658015194718500750961261016558605363103092187533086949903145449057015220561698195502163792192055762108803714387175594231859738263839090338762578040513451585421537323416472060788989

key=RSA.construct((n, e, d, p, q))
cipher = PKCS1_OAEP.new(key)

with open("message","rb") as f:
    f = f.read()
    flag = cipher.decrypt(f)
    print(flag)

运行可得flag。

DASCTF{ce02347b86167f2d3519251b9a8a5ba8}