ctfshow 密码挑战（上）-Toy模板网

这篇具有很好参考价值的文章主要介绍了ctfshow 密码挑战（上）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

由于题目有点小难，老攒着不发我很难受，拆成上下两篇我真聪明

真·Beginner

Lousy RSA

Not That Right Use

so Damn big e?

Hammingway

真·Beginner

assert(len(open('flag.txt', 'rb').read()) <= 50)
assert(str(int.from_bytes(open('flag.txt', 'rb').read(), byteorder='big') << 10000).endswith('1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576'))

给出了m<<10000的后175位

转换为数学公式

m*(2^10000)%(10^175)=c

自然想到

所以把2^10000求模逆乘到c上就可以了

一开始模位10^175算不出来模逆（有因数2），可以把10^175分解为(2*5)^175,

c=1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576
import gmpy2
mod=pow(5,175)
f=gmpy2.invert(pow(2,10000),mod)
from Crypto.Util.number import *
m=c*f%mod
print(long_to_bytes(m))

真·guessguess

from random import shuffle
from secret import secret_msg

ALPHABET = '0123456789abcdef'

class Cipher:
    def __init__(self, key):
        self.key = key
        self.n = len(self.key)
        self.s = 7

    def add(self, num1, num2):
        res = 0
        for i in range(4):
            res += (((num1 & 1) + (num2 & 1)) % 2) << i
            num1 >>= 1
            num2 >>= 1
        return res

    def encrypt(self, msg):
        key = self.key
        s = self.s
        ciphertext = ''
        for m_i in msg:
            c_i = key[self.add(key.index(m_i), s)]
            ciphertext += c_i
            s = key.index(m_i)
        return ciphertext

plaintext = b'The secret message is:'.hex() + secret_msg.hex()

key = list(ALPHABET)
shuffle(key)

cipher = Cipher(key)
ciphertext = cipher.encrypt(plaintext)
print(ciphertext)

# output:
# 85677bc8302bb20f3be728f99be0002ee88bc8fdc045b80e1dd22bc8fcc0034dd809e8f77023fbc83cd02ec8fbb11cc02cdbb62837677bc8f2277eeaaaabb1188bc998087bef3bcf40683cd02eef48f44aaee805b8045453a546815639e6592c173e4994e044a9084ea4000049e1e7e9873fc90ab9e1d4437fc9836aa80423cc2198882a

这道题太难了先不做了，受不了

Lousy RSA

from Crypto.Util.number import bytes_to_long, getStrongPrime
from math import gcd
from Crypto.Random import get_random_bytes

def encrypt(number):
    return pow(number,e,N)

def lousy_encrypt(a,m):
    return encrypt(pow(a,3,N)+(m << 24))

flag = open('flag.txt','r').read().encode()
out = open('output.txt','w')
e = 3
p = getStrongPrime(512)
q = getStrongPrime(512)

while (gcd(e,(p-1)*(q-1)) != 1):
    p = getStrongPrime(512)
    q = getStrongPrime(512)

N = p * q

out.write("N : " + str(N) + "\n")
out.write("e : " + str(e) + "\n")

r = bytes_to_long(get_random_bytes(64))

ct = []
ct.append(encrypt(r << 24))

for c in flag:
    ct.append(lousy_encrypt(c,r))

out.write(str(ct))

代码审计可以看出每次加密都涉及到了r<<24，列出式子不难看出类似short pad attack

c0=((r<<24))^3 (mod n)

c1=(a^3+(r<<24))^3 (mod n)

a3就是short pad，再开3次方得到a，也就是flag的第一位，以此类推；

# Franklin-Reiter attack against RSA.
# If two messages differ only by a known fixed difference between the two messages
# and are RSA encrypted under the same RSA modulus N
# then it is possible to recover both of them.
import gmpy2
# Inputs are modulus, known difference, ciphertext 1, ciphertext2.
# Ciphertext 1 corresponds to smaller of the two plaintexts. (The one without the fixed difference added to it)

def CoppersmithShortPadAttack(e,n,C1,C2,eps=1/30):
    """
    Coppersmith's Shortpad attack!
    Figured out from: https://en.wikipedia.org/wiki/Coppersmith's_attack#Coppersmith.E2.80.99s_short-pad_attack
    """
    import binascii
    P.<x,y> = PolynomialRing(ZZ)
    ZmodN = Zmod(n)
    g1 = x^e - C1
    g2 = (x+y)^e - C2
    res = g1.resultant(g2)
    P.<y> = PolynomialRing(ZmodN)
    # Convert Multivariate Polynomial Ring to Univariate Polynomial Ring
    rres = 0
    for i in range(len(res.coefficients())):
        rres += res.coefficients()[i]*(y^(res.exponents()[i][1]))

    diff = rres.small_roots(epsilon=eps)
    return diff


N = 172586324912059174647797531942031674711062691226058731710862001986640410691620689926009640793233539886361506818340977365593314281428521170793513104344345576781891061238291873583640097499046814240386537106373333197503030272709902722983392299884944974941816177444412015348511294873131429689212919672185181176739
e = 3
cs=[168658334421213747232847656238302466254027669293023358756047398504395075576853993580836429942561627595059657040563934993331562761575412947149005227828675214114274816764496716869598003987368818327391320987709721845655617940389376768491183236521932201125503469968304456151571520009788402749700581671789421599700, 87012761805827854950529922566538549606177263407420031116570756279931559642457228346664149700124517850407143911202777450625814236398958349496369494136458500250193008844236303242315107883490156995640566236967188309531645693985966559019761764176417760587063236657830687375926188492118445452473699198976972165500, 111548883148367424778054394538387230488843004925006317961746779937856635559595513304212793246768039691377488719760030000128556408835969531939733818049127427754838704205697110344848254405595158931279287221612400395137438808373216334005704913597988621735479678779088160336712618279931118880359277607359635289655, 54337580735823551352448926706484672981176289464246742998268734777798609249682391166379365056169103518156960987282198367831006211110449441679856453870263125551304026490561180766185081255849023100044869719217710392656901074214458795892344678637347180482288059175091923814306535428745144919129925554385676065003, 84363133277653661421686784932963659833143615738047162273199110785576858362121374456379732293356439234869625427863882359060391641427144057065928481146148048257792776146715569851028060383001431483497544078554315619586785736679785494124476939202773686625599987669409474951814072189235095272904272428328730999665, 27562250846464528855042460811879754139827659078668732615035806147890005998720652600600618901186196670864267676429322770820987614896030099194237316173160866971994524011212849441771128538926292602043119488179878662714258949094382679237147963534229897418654114256014785045354109993967673103335653154937320135423, 172094685159802241269136365078483894825027988873211243839338773032891098684592982271810562573979118688354743378363081455680604968530086432190616819154865718440594158580872854093148089674817385073818159561212398784458721904407395847895131280574464420035530961839317386490700038008515282794345633748208420540102, 138134245968854241776629921551406556197559268184017437869171642565749009236559784172767211673526920558692527607188051009768810457781469145557093520217943366347778092132811335818636173771716908298216531517138724361401185857577240147616380734139192934708174676458929926406254188268574190878449532926249814629130, 21671467597307554422003093431961880973848617981784201389487380172788585297957554862183774899454873330144790280242954771711298071440114770596404876345872032423262225235587538976584339188102784589405905725053270291635530211449159122989117026640563062597457840872445182873691334137403721426252919934587872474870, 46501787140502988592924357583055445400507064798139574467036314296920260603694612075273271335991599656470878272440607061648171766874466712164248410228816187391123179622441500045042272870898138951868669484014892359404832396788580553943887548329019463175957264266483069029584613678878727559052645197741394732292, 129448033360362698104647315317245667900869831612971689024563199211501890543134739717555748463235506243740045017754486294818576583061924871711625625216443270413592707425568899469558504989802005845110092930514018199978626550916311717776388240889891163453525882588978544494344264602566016656648550802585757352773, 129448033360362698104647315317245667900869831612971689024563199211501890543134739717555748463235506243740045017754486294818576583061924871711625625216443270413592707425568899469558504989802005845110092930514018199978626550916311717776388240889891163453525882588978544494344264602566016656648550802585757352773, 133419265496213325442311993561770868011844576794257507926819829779146424353823666174552607693723841555589227383193965906620745412357704898094804955206970799360374681932109079928355915040966430086978268502785775735841502255047616779224276687463012013897782758029589477115919515010259655806996166433283617869964, 133419265496213325442311993561770868011844576794257507926819829779146424353823666174552607693723841555589227383193965906620745412357704898094804955206970799360374681932109079928355915040966430086978268502785775735841502255047616779224276687463012013897782758029589477115919515010259655806996166433283617869964, 42387050932619524810811012215389847866794717649644399381135767728540244510363146294520691881654627032382944204953261822433312726633821639034697641611206960431277235199287455247911548270198320915118896060481597086591899574985449379328338491051077295507332529361988818809055492767277333323493951128201637307844, 21303814415506877388638099076744346592122662591842457016794191106473141046169574984942869427577217842743442053183541935864841775433448597942050930289903924786302038604537625704379664918486303806527966404988355903566500132232764530628762432626904296843536467910468672242362697283635641861499872372600324760776, 52828730438721404045086995989608094895904815563980126416431883771629425077646851165269353850397176085139046346821159906227025395203016215868152624831595572141001002267152921180062740394001875635739247387228795355301839471887571062693197963476532870495249064908163077049419104696633258081091477626242516259048, 144004311024968075997572529721866223603290995148534921634291198250219393163328895132617949120459274144124329065828538503676459278093675040012043245911331123912312444597841067612342556532950758042016400046475008447028132699015871606550382430008904422837656100377648510808817848479858499200117032423661538836761, 52828730438721404045086995989608094895904815563980126416431883771629425077646851165269353850397176085139046346821159906227025395203016215868152624831595572141001002267152921180062740394001875635739247387228795355301839471887571062693197963476532870495249064908163077049419104696633258081091477626242516259048, 133419265496213325442311993561770868011844576794257507926819829779146424353823666174552607693723841555589227383193965906620745412357704898094804955206970799360374681932109079928355915040966430086978268502785775735841502255047616779224276687463012013897782758029589477115919515010259655806996166433283617869964, 133419265496213325442311993561770868011844576794257507926819829779146424353823666174552607693723841555589227383193965906620745412357704898094804955206970799360374681932109079928355915040966430086978268502785775735841502255047616779224276687463012013897782758029589477115919515010259655806996166433283617869964, 12905654793609802395780458084680650463077041728554164701894310016160973602555624501290806879562950343152016250815033138558187324943541832227860454234482259480283072190435842386847159911679509626328488245574815764392557222938635854936060868691283488953762625943413673583120702727315562967226066808763249553851, 144004311024968075997572529721866223603290995148534921634291198250219393163328895132617949120459274144124329065828538503676459278093675040012043245911331123912312444597841067612342556532950758042016400046475008447028132699015871606550382430008904422837656100377648510808817848479858499200117032423661538836761, 129448033360362698104647315317245667900869831612971689024563199211501890543134739717555748463235506243740045017754486294818576583061924871711625625216443270413592707425568899469558504989802005845110092930514018199978626550916311717776388240889891163453525882588978544494344264602566016656648550802585757352773, 42387050932619524810811012215389847866794717649644399381135767728540244510363146294520691881654627032382944204953261822433312726633821639034697641611206960431277235199287455247911548270198320915118896060481597086591899574985449379328338491051077295507332529361988818809055492767277333323493951128201637307844, 122698320100155825267494592423289070277381902418924120435195614490328690206252637210078080782902962845072870261899769510213159478118750074361554899217508214231284217172243364170662839325747243573796168625006619240694817423525690615889947763889390300644222020209693520468969872192423238120037100320094807425415, 54337580735823551352448926706484672981176289464246742998268734777798609249682391166379365056169103518156960987282198367831006211110449441679856453870263125551304026490561180766185081255849023100044869719217710392656901074214458795892344678637347180482288059175091923814306535428745144919129925554385676065003, 144004311024968075997572529721866223603290995148534921634291198250219393163328895132617949120459274144124329065828538503676459278093675040012043245911331123912312444597841067612342556532950758042016400046475008447028132699015871606550382430008904422837656100377648510808817848479858499200117032423661538836761, 42387050932619524810811012215389847866794717649644399381135767728540244510363146294520691881654627032382944204953261822433312726633821639034697641611206960431277235199287455247911548270198320915118896060481597086591899574985449379328338491051077295507332529361988818809055492767277333323493951128201637307844, 68368118695434613855488776894095051626076470782472234467489353194279515318871317835105131219821947666172743391918044124330222375810428968533025532643001309282465671583738592340355835062902402320841991974320998731421688371182390557475940070364632102988335172738193050702368011980193677964167722191323435405999, 21303814415506877388638099076744346592122662591842457016794191106473141046169574984942869427577217842743442053183541935864841775433448597942050930289903924786302038604537625704379664918486303806527966404988355903566500132232764530628762432626904296843536467910468672242362697283635641861499872372600324760776, 13041554660912552015337323063067092606093297749610138486047156833905738940621424507699992363648396465133271689474656937910059393446526513722298376667197321299342006540334508080884676751015158918194925830309383027360373822785208522012728047878901624273958755833863179668583053332179600464815203514730515632659, 144004311024968075997572529721866223603290995148534921634291198250219393163328895132617949120459274144124329065828538503676459278093675040012043245911331123912312444597841067612342556532950758042016400046475008447028132699015871606550382430008904422837656100377648510808817848479858499200117032423661538836761, 56961814319740957529790223867401660390145190084213910201779636226795975804394042078236460663331007096110339176673158443362133426849260407296326558529067046657013056614323872173653800019685003167998648556509445068719261112779917955816544452796462965211116982827479763464513115302495386328923132455376524262361, 133419265496213325442311993561770868011844576794257507926819829779146424353823666174552607693723841555589227383193965906620745412357704898094804955206970799360374681932109079928355915040966430086978268502785775735841502255047616779224276687463012013897782758029589477115919515010259655806996166433283617869964, 148147231581244801693210321706480693316570720848282857068643020719469468934810071772844129103502653937297683172968814962003488170141820558995030608464151832202948397227735893036498052343501508887940365339782714889637840385638515193533575400309281235193055166196168214862908435305102813407120649871550955080196, 87012761805827854950529922566538549606177263407420031116570756279931559642457228346664149700124517850407143911202777450625814236398958349496369494136458500250193008844236303242315107883490156995640566236967188309531645693985966559019761764176417760587063236657830687375926188492118445452473699198976972165500, 13041554660912552015337323063067092606093297749610138486047156833905738940621424507699992363648396465133271689474656937910059393446526513722298376667197321299342006540334508080884676751015158918194925830309383027360373822785208522012728047878901624273958755833863179668583053332179600464815203514730515632659, 129448033360362698104647315317245667900869831612971689024563199211501890543134739717555748463235506243740045017754486294818576583061924871711625625216443270413592707425568899469558504989802005845110092930514018199978626550916311717776388240889891163453525882588978544494344264602566016656648550802585757352773, 21303814415506877388638099076744346592122662591842457016794191106473141046169574984942869427577217842743442053183541935864841775433448597942050930289903924786302038604537625704379664918486303806527966404988355903566500132232764530628762432626904296843536467910468672242362697283635641861499872372600324760776, 52828730438721404045086995989608094895904815563980126416431883771629425077646851165269353850397176085139046346821159906227025395203016215868152624831595572141001002267152921180062740394001875635739247387228795355301839471887571062693197963476532870495249064908163077049419104696633258081091477626242516259048, 42387050932619524810811012215389847866794717649644399381135767728540244510363146294520691881654627032382944204953261822433312726633821639034697641611206960431277235199287455247911548270198320915118896060481597086591899574985449379328338491051077295507332529361988818809055492767277333323493951128201637307844, 67886471467372617010478807736199832478730966963863588858164458169479163918642755815885725034424301213138827294675599424646838450064602719169572755878245897082935916421535087482438869655744231376119562456922969612142545061319245684269963694752916270334015126579024360980090266203732577293202146744636527481366, 87012761805827854950529922566538549606177263407420031116570756279931559642457228346664149700124517850407143911202777450625814236398958349496369494136458500250193008844236303242315107883490156995640566236967188309531645693985966559019761764176417760587063236657830687375926188492118445452473699198976972165500, 133419265496213325442311993561770868011844576794257507926819829779146424353823666174552607693723841555589227383193965906620745412357704898094804955206970799360374681932109079928355915040966430086978268502785775735841502255047616779224276687463012013897782758029589477115919515010259655806996166433283617869964, 50277537687808915187321556792873891743465320453382608818835270204485821264861362165795188527652462179852016717005639583656155911139261052815901804233067611263369496043519565138551200510192466143087807690228003107236841785427109466969071037867357310961604114991659880166263663294415303891877998812061963183637, 65167429278788828829113877172654592296237234769405369012686791552119870472800740363654055138135506582630165138513798774791198077665002612776209766253629118972328585507965584639810664981780631521482308408856487138825515416578034752275410508091092025883558570517662743797951185334923605238982568065703213177496]
flag=''
for i in range(1,len(cs)):
    diff=CoppersmithShortPadAttack(e,N,cs[0],cs[i],eps=1/30)
    m=gmpy2.iroot(int(diff[0]),3)[0]
    flag+=chr(m)

print(flag)

Not That Right Use

from Crypto.Util.number import *
from secret import flag
import gmpy2
import random

length_bit = 8192
def generate_key(length_bit = 8192):
	q = getPrime(length_bit)
	f = random.getrandbits(length_bit//2)
	while True:
		g = random.getrandbits(length_bit*3//8)
		if gmpy2.gcd(f,g) == 1:
			break
	h = gmpy2.invert(f, q)*g % q
	return h,q,f,g

def encrypt(m,h,q):
	m = bytes_to_long(m)
	r = random.getrandbits(length_bit//2)
	enc = (r*h + m) % q
	return long_to_bytes(enc)

def decrypt(enc,f,g,h,q):
	a = f*enc % q
	b = gmpy2.invert(f,g)*a % g
	return long_to_bytes(b)

h,q,f,g = generate_key()
pub = open("pub.key","w")
pub.write(str(h)+"\n")
pub.write(str(q))
pub.close()

enc = open("enc","wb")
enc.write(encrypt(flag,h,q))
enc.close()

注意h q f g 的生成方式

所以对任意整数k，有公式 h*f=k*q+g

注意到h与q的阶数应该大致相同，那么f、g与k阶数近似，

构造二维格

f*(h,1)+(-k)*(q,0)=(f*h-k*q,f)=(g,f)

找到(h,1)(q,0)的最短向量，就找到了g f，有关最短向量的问题，可搜索LLL算法或高斯晶格规约

h=140641654480309646661460752259009805238822983063359975743381261932998899184657124924009078027641660038632664812668296524565206464727520596895026388236060597071386726013858963646501909196012396523837136988240197784437301120862384415682149940533848605250394303113175634035415167283080872735105912832870108712880945146080491825953020939705109174820916829051689692620946211242161384869371254560708250183882247373951211750966153182266054977202080568980091991771341013245919227004891065056914748466875350300140600531409616529059949886077689971297827093124675618542008989955575344877827824040946659512030038751389893253831481412516711878799875665224067139882771597407869970351450430459419948729296146331395877370686156516399740856252014616811497494914814385899755904538139847880089751542568309978231883094168561891730860752672873293261989147250409991608262872830092259084716940417114648971958597960369718849774615105540721662399447525067048358560864789407380815740563275439433805528298375095604942955338684305941359986487934315953665121858289306142097815651312478757549908167872661314913947544946927600211726850023950066392630122882839485809938848969950265325406399686586314459280991301825054645472425674527422929972887391753238816923298623579429710609368219213051797207053195961056438004296815009848196702292268936140424621874190909040512919014723673109665119192714879264861148038121817069654007213479519085780137202965768316745672909214544256962033590044776596987318613883438618931569568770820849164854311957684349997002160055168894414227617344006000575498315925335544219161846832480926999315432632883472713932971843620942616934646926067124395446944817779007843821815929039660037988200894593303504735755586137601186627884346462317235217848459593022989695194335576580395608745533282003408295857616739627596114657034449337931786787816708834202430301485318191988716906057312812712966166482682666772164391035856970600473354659224228523748418482322369646074712031322484015675331188701826840899169239647159728457797185599341417975052131005330363975351239128277681330549494029848264189699117329464205714708985625181438636031578843174246581394478846033426716126183473299468283652853483151156325335551346299229916621899845783802680366480774960939565022117840145287070125249514544755884841252084725187489065017117288468998533234739167462719883594746485521270177090828004405816695890424237068837967556932724183111259469809936198958551342439901421853536441105951848942732141671755288
q=721062963295306780224288865760990406705513413320561732579234627711939010604916641502092203177136835588541554259063811291724295326953780525988898494239189350240494500021294136439018702342345820168271819324239839692861840016935631311071537166467243301000506704801343901587217940601797154207151921328887191874341607566625648510662958547199740852292999143208619354521973490573519876933142879407979683083573289638308100864165321388700902121078266071026038820486271316744664851483993423823069500303784383402304857035906448474159407085076020845226366206779141953496917489352476217054101214862066665066280950745072263325003643813350410844887077930774020933179459662916264650762216248605817745559194567515555850407282821340092531175262602702689180998414973022172701379180086212961061419818399053186026560842353748858519340974555352846705106500626664423314580198973011348673520120756781149651665967392752894792766334085124576134896850861070432338086277928670454001217670204592159022929789345510699644329966648502723120607881524783034562999715359179899943667274544446186555535385342026523507272796317613533963130150740855860225218332454607928768586519196388270192942980483940301171902740523758767325732435445754037509355869523812180653852667149772589024163493166632487347370811001485499960660824873526525919202671251942237597925764302445772724119412342705274451132940388410843886761306608395515200717447949626428049390906934269615447989583695806837918559467964483511193999073458761627082013487166837347281447834645376827978448760118048190148555572650537226385951360112553300387850015554277302469446739321719203700104354051152513702957057612668569467778263927730960518541792141873558358570677673100354450667297984686325175580976679505813813087110507883692083480127292287072406007262614228999824198116147220636799150068583032192358361413551877727766941745214486818182944108269772327140216300601094319506495541728100804461508755639873982377181607116052192238012365235618004165882010754149050486945338325383652930339212117826439488162732673179327060653649674194138447978815851287502201747481323578543139551676130822000071019318961666705089853728546154158421964235939702012776690925139910891383388310243996693561285917954515846454468095240887216321982651836906224349855624967761406539747280802571696734421390708879090880910004109042791548443392008271506467298812179909867611515314534888779065371104453531718962387778109331723060221708419208865118130890948962620930751351862376780409
c=588529356965030272025601048861282065021017902423164264957441586920595872039895404577255060274952541620315018969680195236465977272648652287926496543780173650574305499297716276827858805927298162208072303645283316405452651523836300258701988005355462277459875749978643895956961980467177804300387767414485993724320752395808791573881273230913748801373284405366594883666020631291276729848223537472276347125889834098129339716781471747034001410355814674928405649297961406796494833489565097910117203986219593353105481771936122718520536309366303961744867901990013705583165049702866175649386129367497873297054880401873031133188695262882654806285250254062236029461999697492837693504031022413406804330735094841148426551764288094879463057233019026422469014402428741654099663670413177889700803143516686274186664290312914022712001020975681794284476755306982329761414416554633826317934023660554506240542417335582689320936413929582635040851938378673355395047591192878234906774517888492511273362194115721382787428142413514396337877140039660775671326039060700550442211666812163244332762784047751975372230479416550318062822478588883067886438254695396783950270796813646987304649115877778929479117735381509546765888903982084857084146199858327966366481894960817384939327571190145773428855235037692518669027348557875061654802806227997673990112539114617853746089796693008271617776258890685231202093199769390648648724394621369070381058697619434434832764604338681140468898430273958259274423206535125100012671267337454233857407519190779123591857743660990034703847602695635498882322688596411189459783776748556641094779989138912494831839398857272788856710386704790450677690265116557152577245683557633429067370300903617226202997324638833015986591267108399829799306550735742117392415154266621030491837810396414282733584581932559949197413360798641627400507259389841455683789600794101460317701439910041563732131818865623789707908194392983359341050463836331965882104965958953776930066271528305080002935616971821352074253274211712644496549129601236468590933739942097889191987452132024182362123132201878709183393780456917565933067892953248097550146353078515168723528393603206246180698646597545792807716410931432281068936474760372741067644411320258900899808020539775178893382637068507862640029652464833884426244030678683387274373604759929344023706613753521672136720742565422001830029817188207010482846041392439542661849175431101244019020590777117194607762930230409875058098534619014803651392511587270579935
from Crypto.Util.number import *
mt=Matrix(ZZ,[[h,1],[q,0]])
g,f=mt.LLL().rows()[0]

def decrypt(enc,f,g,h,q):
	a = f*enc % q
	b = gmpy2.invert(f,g)*a % g
	return long_to_bytes(b)

print(decrypt(c,f,g,h,q))

so Damn big e?

n1 = 0x7e503bdb2d037da083601c2945b668bbad980789cb4671b20fee013295319cc43a5b4defca704474c793fa2bd86eacd5552da0f0dc37a42eafd379d9216c0f3a1687ca42c5aa40500435374495fa0ebce37340bf6f98046c58443497457e4e442206a322ecfb60ee846f7aeb1e72f6804609a194ba9e28d6449a0e06d214525ce043afffd96eb9cb8e09b16722153ba5198bce185b5ad24b845b39a0940e5b9a7ad896c3e472b5d49cdb5956b91ef069d81fe399fcf5f3f02f465896bbf4ecbde7ba9cda0c510f14ba2b0673173c7916c284bf7a63613225ece3563a6d843ef06d731d0404646b97a4bc4a3ec4e77751d3c5fd280bf8b0277ae1cade8b1fbdf9
e1 = 0x45a1ee446ca0df0720f77b576f8c197a5033f5cefec5bc8a2ddd9da021ff389d8991e1822abbe9efe60204094c252195f6a4c898ce4f4ee0ef726bd0fcfe7741749bd9cc1cbbec83cc133743d4c746c2736da2452bfeaea1d031f10719f33fa4ef3b8878951b2b70cead75a608d883968a17cd04f19eb3a58e5d55e01790658248a0a26404131a070d3b3c9cb4a1d9d98eadc392199300fbf5ee472296e36dccef2e796b9b51e6693767d40336875ab62c41231ea9fb90bcad4df203b4459abb8d0e402de474cd802e2bfbc01d3b2d55f96b44ceec56ad6c4f3809cfa30b102bc5edc1607c613734571e1dbdb13ace896d1931a53fc9088ead61d78bc30fe78d
c1 = 0x5b4331a4de52d57c7ff77ae03a75b96629c76509d0fd003c27966ca0bd8a7e1a835eee6fe9b02afe78507b43e9efdb9c13f7cbdacd5d18d45ca98ab5538fbf6500a9b314e7e260bab673ae8a38c41b056bea895953ad7257cf30b9a1ba598a1ef01b251964feb2a63e09d8b699a14f1bf3d464809dab3c514fe7c6f59be9c434a694215ebafe547035323f90a661b9c5c73208ef0cbc21c0e9abbdaa65cc4bbaf8c2c47841aefcabd89bbaa3a6f2a9df6d3d8a0eedbec7c28c94fb369b426449b7d6ec5daed4d07df92d057e02cacbfdda0c94afce396dda307c8cc6ecd51c084fa2cfe3a31edde97018ba0de31b8cdeabe34f51ceebdf8834340605d5d71279
n2 = 0x878717447ff85bff1c360384309b5731edffd0ade56117d3b8b72b2ab9296633437e3f5fb09c57e8658c1dc1de5d7a9ba003923d3e9d8e124afe71c6fd0c9985988961198c5c21ed46dfad45399ec9d4c6a6a0ca793e5c721333db2ceed863bc919544024a2a630e9788e9f5afadbd3a291bbda804ed70c6e9b9a599cb3a4d14ed9325000c19d988a79af2e44ff1e14766a0465837125107a9c2cf7a76980d6f86aaf9f926ea0e46d641d3478112de0824bf9c5e726a7d5b7c92cbc1906d3d778e9a612290e043e2b3afd4f0a806254640772fd25980b009b4136d685e52725482ac61e1b679d13eb0d2b06df080fffc677a1b9afbcf327fba6a3ed8fbc7e22d
e2 = 0x837ebb33e9bbb4a5662d484099db6a435c68d630acdfe317aed1a089fcb9deb4df3c328a36c8f1f14045374e8cd4a75e6480bc04489fbf86a1d324b6c2c31ce11dd50d6cb75f9be5b01d2b756aac22f3c7c17f42b47b9bba52575912faa482214158c935ea1d943d62f2a5242c00771a983b1428edbefbe43b8bcad116e6a110ebc3305f622fe131596889450b16a69b8567086939f7f4766f3cb93c1cc63c0ee1f6b2a4ce0de084b760e1f7dd3d5542a4f958969f0b17f5268eddb78b68d3348ef0e6be831c3846325985170f06ad25f5af5a04ada0f2aa3c93ad8c940966248698e72d6f029b0af9af91634aae13319faf985ce77ec4c35b416a8100050c7d
c2 = 0x26049d5d64a85ad3e89d7933a0d296651d566d71314485d2c4c74e8fa462f0c95d43daca9bbbc2557efd7441286e5de65b6067f9df6eb6b9ece0439f7ce7b0ee5e97607b3de1f7e591461469482975e9e2161e5ef1664b44d994c2d294884e0ddaab5c19a1a292d057dc517c9b4cb2dbdcfdbab02972cfd0a7d00f34320c4bc887ea2531ecf188e50e0f33995770b54affe30ebbce85bff955aa66c8e28e5708b0f3d3f52f07dbe5bf155968a65deb94f877ae7904b3dbc848e29d465452a07c373799a30452985e5b9933a57ca2d5227c40fed42e9537435c9f3221749db451c3861bbf57a4901f81d6794d0ad10ba882e8ba99e320cb12edd0b8c7194ded33
n3 = 0xd0a6712277676e497a6c09871e09ca7e87a0a09cc9c7a402ff12617eb2da499651724c4bfc4bdee713062c93ac852d627954cd59ed95b97d4ace621d8b86b867b9ff4b58c45c83f51fb4dcb12a15eaba0bf7370c29b1178a1bee585c4263ac7c1f0846bf4b5d2e8be1ec7bbaa023a8439deaaeeebd04d1188692a2223820c447606662e27af3f1fc45332dcea5214b05946d65e73bc8e9a17dc5093a2b0241b5166e6310e9bd0e1a20f9a5cb0f1925ba00b71bff78b058a167ee5dcadf428e1d3e4c077710dc073025a7813160fe825c8e3c81ef5e5070226b5d89a1ce86e91b3ce7cf3b5d590fa467a8defb2f96083291a74996dff53dfc44883a6a1c2e4651
e3 = 0x25b452f7ef6177efeb93d117aa856ca788713ff813af2f577246ed3a0a8cf244032197abd38c42677a0b7a3693108207b71ac7c934cc96d8cfafbe27e1a3ecda72796f0c09d9308e14f62be5bd913bb28afb6f92dc7a362e871d0f8667b9f44ffa2bcd240c554da99fe159599d68a9f7c4aa869b44edb382315b3ffb75bd2b12ba60f7ac667551756d13cb88e2be3f9959ab99fc4a063b8b53d208950f6db139d486f5f7351fa75010ad5177c07e4b2226298678518dd5145be36d4901c69949800f5e63be0b9fd7297eb204d76fd8c87217ea30a5495add4b5d901caabc929ee72de78d6ed3ae760c985ff58703f46046352d17926db6bcd57839c0a3ca9cfd
c3 = 0x874354398f60a93239229e47157f12c2c5b34886cacfe9b236ec545a5dc503c9e5cd38552eeb024d7562fed842368bde2e1744b222aa5f857684de402924a1b493c715a679ad17ab2251c1ad8e92fa83f45c4fb33154e09de088704acd4f14a4d3f8099aba4e2e2a4bc3baf35f32485ca67de3338cf0fd2276af6eb35751b0378709cb2aaff033146bc5d2f94fde12cb2286173af2f582b1841db9fb136667f2f90aca690f6041ad84380ecb86b443949d05bee5a08305b26f3efd53d0ae6e2e9cae6c4b4c36b2ae7d826117512e4c1d12dcce75b35d55b737970e3dc809c04b5aa309583e6a9650bd58415805be3c8175bf9546b24c8ce833a402f9b5d2ef35

给出三组nec，提示d相等，不用尝试owiner之类的，我已经试过了QAQ

论文链接：

https://eprint.iacr.org/2014/549.pdf 找到里面的The First Attack on k RSA Moduli

论文描述：

^quxjg$c4f50026962365276bf35b4124ca7acfbd1636c6c^quxjg$c4f50026962365276,密码,密码学,python

可以看出来， x是k个式子公用的，也就是d（当然我只是说这里的x应该是d，更好的理解式子，而不是说要求x），复现攻击如下：

import gmpy2
from Crypto.Util.number import *
n1 = 0x7e503bdb2d037da083601c2945b668bbad980789cb4671b20fee013295319cc43a5b4defca704474c793fa2bd86eacd5552da0f0dc37a42eafd379d9216c0f3a1687ca42c5aa40500435374495fa0ebce37340bf6f98046c58443497457e4e442206a322ecfb60ee846f7aeb1e72f6804609a194ba9e28d6449a0e06d214525ce043afffd96eb9cb8e09b16722153ba5198bce185b5ad24b845b39a0940e5b9a7ad896c3e472b5d49cdb5956b91ef069d81fe399fcf5f3f02f465896bbf4ecbde7ba9cda0c510f14ba2b0673173c7916c284bf7a63613225ece3563a6d843ef06d731d0404646b97a4bc4a3ec4e77751d3c5fd280bf8b0277ae1cade8b1fbdf9
e1 = 0x45a1ee446ca0df0720f77b576f8c197a5033f5cefec5bc8a2ddd9da021ff389d8991e1822abbe9efe60204094c252195f6a4c898ce4f4ee0ef726bd0fcfe7741749bd9cc1cbbec83cc133743d4c746c2736da2452bfeaea1d031f10719f33fa4ef3b8878951b2b70cead75a608d883968a17cd04f19eb3a58e5d55e01790658248a0a26404131a070d3b3c9cb4a1d9d98eadc392199300fbf5ee472296e36dccef2e796b9b51e6693767d40336875ab62c41231ea9fb90bcad4df203b4459abb8d0e402de474cd802e2bfbc01d3b2d55f96b44ceec56ad6c4f3809cfa30b102bc5edc1607c613734571e1dbdb13ace896d1931a53fc9088ead61d78bc30fe78d
c1 = 0x5b4331a4de52d57c7ff77ae03a75b96629c76509d0fd003c27966ca0bd8a7e1a835eee6fe9b02afe78507b43e9efdb9c13f7cbdacd5d18d45ca98ab5538fbf6500a9b314e7e260bab673ae8a38c41b056bea895953ad7257cf30b9a1ba598a1ef01b251964feb2a63e09d8b699a14f1bf3d464809dab3c514fe7c6f59be9c434a694215ebafe547035323f90a661b9c5c73208ef0cbc21c0e9abbdaa65cc4bbaf8c2c47841aefcabd89bbaa3a6f2a9df6d3d8a0eedbec7c28c94fb369b426449b7d6ec5daed4d07df92d057e02cacbfdda0c94afce396dda307c8cc6ecd51c084fa2cfe3a31edde97018ba0de31b8cdeabe34f51ceebdf8834340605d5d71279
n2 = 0x878717447ff85bff1c360384309b5731edffd0ade56117d3b8b72b2ab9296633437e3f5fb09c57e8658c1dc1de5d7a9ba003923d3e9d8e124afe71c6fd0c9985988961198c5c21ed46dfad45399ec9d4c6a6a0ca793e5c721333db2ceed863bc919544024a2a630e9788e9f5afadbd3a291bbda804ed70c6e9b9a599cb3a4d14ed9325000c19d988a79af2e44ff1e14766a0465837125107a9c2cf7a76980d6f86aaf9f926ea0e46d641d3478112de0824bf9c5e726a7d5b7c92cbc1906d3d778e9a612290e043e2b3afd4f0a806254640772fd25980b009b4136d685e52725482ac61e1b679d13eb0d2b06df080fffc677a1b9afbcf327fba6a3ed8fbc7e22d
e2 = 0x837ebb33e9bbb4a5662d484099db6a435c68d630acdfe317aed1a089fcb9deb4df3c328a36c8f1f14045374e8cd4a75e6480bc04489fbf86a1d324b6c2c31ce11dd50d6cb75f9be5b01d2b756aac22f3c7c17f42b47b9bba52575912faa482214158c935ea1d943d62f2a5242c00771a983b1428edbefbe43b8bcad116e6a110ebc3305f622fe131596889450b16a69b8567086939f7f4766f3cb93c1cc63c0ee1f6b2a4ce0de084b760e1f7dd3d5542a4f958969f0b17f5268eddb78b68d3348ef0e6be831c3846325985170f06ad25f5af5a04ada0f2aa3c93ad8c940966248698e72d6f029b0af9af91634aae13319faf985ce77ec4c35b416a8100050c7d
c2 = 0x26049d5d64a85ad3e89d7933a0d296651d566d71314485d2c4c74e8fa462f0c95d43daca9bbbc2557efd7441286e5de65b6067f9df6eb6b9ece0439f7ce7b0ee5e97607b3de1f7e591461469482975e9e2161e5ef1664b44d994c2d294884e0ddaab5c19a1a292d057dc517c9b4cb2dbdcfdbab02972cfd0a7d00f34320c4bc887ea2531ecf188e50e0f33995770b54affe30ebbce85bff955aa66c8e28e5708b0f3d3f52f07dbe5bf155968a65deb94f877ae7904b3dbc848e29d465452a07c373799a30452985e5b9933a57ca2d5227c40fed42e9537435c9f3221749db451c3861bbf57a4901f81d6794d0ad10ba882e8ba99e320cb12edd0b8c7194ded33
n3 = 0xd0a6712277676e497a6c09871e09ca7e87a0a09cc9c7a402ff12617eb2da499651724c4bfc4bdee713062c93ac852d627954cd59ed95b97d4ace621d8b86b867b9ff4b58c45c83f51fb4dcb12a15eaba0bf7370c29b1178a1bee585c4263ac7c1f0846bf4b5d2e8be1ec7bbaa023a8439deaaeeebd04d1188692a2223820c447606662e27af3f1fc45332dcea5214b05946d65e73bc8e9a17dc5093a2b0241b5166e6310e9bd0e1a20f9a5cb0f1925ba00b71bff78b058a167ee5dcadf428e1d3e4c077710dc073025a7813160fe825c8e3c81ef5e5070226b5d89a1ce86e91b3ce7cf3b5d590fa467a8defb2f96083291a74996dff53dfc44883a6a1c2e4651
e3 = 0x25b452f7ef6177efeb93d117aa856ca788713ff813af2f577246ed3a0a8cf244032197abd38c42677a0b7a3693108207b71ac7c934cc96d8cfafbe27e1a3ecda72796f0c09d9308e14f62be5bd913bb28afb6f92dc7a362e871d0f8667b9f44ffa2bcd240c554da99fe159599d68a9f7c4aa869b44edb382315b3ffb75bd2b12ba60f7ac667551756d13cb88e2be3f9959ab99fc4a063b8b53d208950f6db139d486f5f7351fa75010ad5177c07e4b2226298678518dd5145be36d4901c69949800f5e63be0b9fd7297eb204d76fd8c87217ea30a5495add4b5d901caabc929ee72de78d6ed3ae760c985ff58703f46046352d17926db6bcd57839c0a3ca9cfd
c3 = 0x874354398f60a93239229e47157f12c2c5b34886cacfe9b236ec545a5dc503c9e5cd38552eeb024d7562fed842368bde2e1744b222aa5f857684de402924a1b493c715a679ad17ab2251c1ad8e92fa83f45c4fb33154e09de088704acd4f14a4d3f8099aba4e2e2a4bc3baf35f32485ca67de3338cf0fd2276af6eb35751b0378709cb2aaff033146bc5d2f94fde12cb2286173af2f582b1841db9fb136667f2f90aca690f6041ad84380ecb86b443949d05bee5a08305b26f3efd53d0ae6e2e9cae6c4b4c36b2ae7d826117512e4c1d12dcce75b35d55b737970e3dc809c04b5aa309583e6a9650bd58415805be3c8175bf9546b24c8ce833a402f9b5d2ef35

ns=[n1,n2,n3]
es=[e1,e2,e3]
cs=[c1,c2,c3]

N=max(n1,n2,n3)
k=3
delt=0.375
epsilon=sqrt(5)*N^(delt-1/2)

n=k

C=int(3^(n+1)*2^((n+1)*(n-4)/4)*epsilon^(-n-1))
#print(C)


M =Matrix(ZZ,  [[1, -int(C * e1 / (n1 + 1)), -int(C * e2 / (n2 + 1)), -int(C * e3 / (n3 + 1))],
                [0, C, 0, 0],
                [0, 0, C, 0],
                [0, 0, 0, C]])


K=M.LLL()

first_row=K*M^-1
#print(first_row)
x,y1,y2,y3=-first_row[0]
ys=[y1,y2,y3]

Ss=[abs(int(ns[i]+1-es[i]*x/ys[i])) for i in range(k)]
Ds=[int(sqrt(Ss[i]^2-4*ns[i])) for i in range(k)]
Pas=[int((Ss[i]+Ds[i])/2) for i in range(k)]

P=[]
for i in range(3):
    PR.<x>=PolynomialRing(Zmod(ns[i]))
    pf=Pas[i]>>200<<200
    #print(pf)
    f=pf+x
    x0=f.small_roots(X=2^200,beta=0.4)
    P.append(int(x0[0]+pf))

for i in range(3):
    q=ns[i]//P[i]
    d=gmpy2.invert(es[i],(P[i]-1)*(q-1))
    m=pow(cs[i],d,ns[i])
    print(long_to_bytes(int(m)))

Hammingway

import random
from functools import reduce

flag = open("flag", "r").read()

flag = "".join(str(format(ord(c), '08b')) for c in flag)
flag = [[int(j) for j in flag[i:i+11]] for i in range(0, len(flag), 11)]
code = []
for i in flag:
    for j in range(4):
        i.insert(2**j-1, 0)  #0,1,3,7位被插入0,也就是插入校验码
    parity = reduce(lambda a, b: a^b, [j+1 for j, bit in enumerate(i) if bit])
    parity = list(reversed(list(str(format(parity, "04b")))))

    for j in range(4):#确定校验码的值
        if parity[j] == "1":
            i[2**j-1] = 1
    
    ind = random.randint(0, len(i)-1) #随机一位取反
    i[ind] = int(not i[ind])
    code.extend(i)

enc = "".join([str(i) for i in code])
open("enc", "w").write(enc)

根据题目可知本次考察的是海明码，代码就是海明码的编码原理，但是写的比较抽象，学习一下海明码的原理和纠错可直接进行纠错

参考：

简单理解海明校验码

海明码编码计算和纠错、CRC校检码计算文章来源地址https://www.toymoban.com/news/detail-541038.html

c="110011000111011001111000011000000110101101110101011110110100101000010100001010101100110101101001110101001011001011101110010001110001010101011011011000101100100011110011110001000011110001110001111111001100001000101110010001110110000001110010010010000100011000000001001101111110010111110011111010110111000101000011001101000101000001011011001001011111111000100000110101110000000101011111011101011101101101100110111110110100111010010100110110001111111001111011100000100110011000100001110001010000011101011111"

cc=[]
for i in range(0,len(c),15):#15个一组分组
    cc.append(c[i:i+15])

a=''
for ct in cc:
    f=[]
    for i in ct:
        f.append(int(i))
    num=0
    try:#因为最后不足15位会报错，鉴于我盲猜最后一个“}”符号，就不管它了,用try pass掉最后一个
        if(f[2]^f[4]^f[6]^f[8]^f[10]^f[12]^f[14]!=f[0]):#海明码校验
            num+=1
        if(f[2]^f[5]^f[6]^f[9]^f[10]^f[13]^f[14]!=f[1]):
            num+=2
        if(f[4]^f[5]^f[6]^f[11]^f[12]^f[13]^f[14]!=f[3]):
            num+=4
        if(f[8]^f[9]^f[10]^f[11]^f[12]^f[13]^f[14]!=f[7]):
            num+=8
        num-=1
        f[num]=int(not f[num])#找到发生错误的位置并修改
        for k in range(len(f)):
            if k==0 or k==1 or k==3 or k==7:
                continue
            else:
                a+=str(f[k])#将修改后并去掉校验码的字符保存
    except:
        pass
from Crypto.Util.number import *
mm=[]
#print(a)
for i in range(0,len(a),8):#每8个二进制组成一个int
    mm.append(a[i:i+8])

flag=[]
for i in mm:
    flag.append(int(i,2))
for i in flag:
    print(chr(i),end='')
print('}')

到了这里，关于ctfshow 密码挑战（上）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！