buuctf crypto部分刷题的记录，此文是第一部分。后续会继续更新。

0x1 救世捷径

其实是算法题，利用Dijkstra算法即可求出

0x2 [NCTF2019]childRSA

题目

def getPrime(bits):while True:n = 2while n.bit_length() < bits:n *= choice(primes)if isPrime(n + 1):return n + 1e = 0x10001
m = int.from_bytes(flag.encode(), 'big')
p, q = [getPrime(2048) for _ in range(2)]
n = p * q
c = pow(m, e, n)# n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
# c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108

特点：
p和q是由小素数相乘后加1而得 利用Pollard p-1方法解出p 和 q

$ py -m primefac -vs -m=p-1 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513

可以得到p和q. 接下来正常求解

0x3 [BJDCTF2020]rsa_output

共模攻击
题目

{21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111,2767}{21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111,3659}message1=20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599message2=11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227

共模攻击求解 s 和 t 的代码

gcd ,s , t  = gmpy2.gcdext(e1,e2) 
...
m = pow(c1,s,n)*pow(c2,t,n) % n

0x4 [BJDCTF2020]RSA

flag=open("flag","rb").read()p=getPrime(1024)
q=getPrime(1024)
assert(e<100000)
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
print c,n
print pow(294,e,n)p=getPrime(1024)
n=p*q
m=bytes_to_long("BJD"*32)
c=pow(m,e,n)
print c,n'''
output:
12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120  13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721  12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
'''

两个n求出公因数解出p 和 q ，对e爆破 ，求出私钥d解密rsa

0x5 [GWCTF 2019]BabyRSA

flag = 'GWHT{******}'
secret = '******'assert(len(flag) == 38)half = len(flag) / 2flag1 = flag[:half]
flag2 = flag[half:]secret_num = getPrime(1024) * bytes_to_long(secret)p = sympy.nextprime(secret_num)
q = sympy.nextprime(p)N = p * qe = 0x10001F1 = bytes_to_long(flag1)
F2 = bytes_to_long(flag2)c1 = F1 + F2
c2 = pow(F1, 3) + pow(F2, 3)
assert(c2 < N)m1 = pow(c1, e, N)
m2 = pow(c2, e, N)output = open('secret', 'w')
output.write('N=' + str(N) + '\n')
output.write('m1=' + str(m1) + '\n')
output.write('m2=' + str(m2) + '\n')
output.close()

p 和 q相差不大，可以分解
解出c1 和 c2 ，求解方程组即可。

0x6 坏蛋是雷宾

rabin密码
rabin解题代码

from gmpy2 import *
import hashlib
n=523798549
p=10663
q=49123
e=2
c=162853095
inv_p = invert(p, q)
inv_q = invert(q, p)mp = pow(c, (p + 1) / 4, p)
mq = pow(c, (q + 1) / 4, q)a = (inv_p * p * mq + inv_q * q * mp) % n
b = n - int(a)
c = (inv_p * p * mq - inv_q * q * mp) % n
d = n - int(c)for i in (a, b, c, d):print(bin(i)[2:])

0x7 nctf2019-babyrsa

def nextPrime(n):n += 2 if n & 1 else 1while not isPrime(n):n += 2return np = getPrime(1024)
q = nextPrime(p)
n = p * q
e = 0x10001
d = inverse(e, (p-1) * (q-1))
c = pow(bytes_to_long(flag.encode()), e, n)# d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
# c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804

已知e d，需要求出p和q

d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804
e=0x10001
src=d*e-1
i=2**15
while True:if(src%i==0):if((src//i)>=2**2046 and (src//i)<=2**2048):phi=src//iq_1=iroot(phi,2)[0]      #开平方q=nextprime(q_1)     #下一个素数if(phi%(q-1)==0):     #验证是否成立p_1=phi//(q-1)p=p_1+1if(isprime(p)):print(p,q)#(143193611591752210918770476402384783351740028841763223236102885221839966637073188462808195974548579833368313904083095786906479416347681923731100260359652426441593107755892485944809419189348311956308456459523437459969713060653432909873986596042482699670451716296743727525586437248462432327423361080811225075839L, 143193611591752210918770476402384783351740028841763223236102885221839966637073188462808195974548579833368313904083095786906479416347681923731100260359652426441593107755892485944809419189348311956308456459523437459969713060653432909873986596042482699670451716296743727525586437248462432327423361080811225076497L)breaki+=1if((src//i)<2**2046):print 0break
n=p*q
m=pow(c,d,n)

0x8 [AFCTF2018]Single

替换密码
直接用quipqiup网站解密即可

0x9 [De1CTF2019]xorz

用到了汉明距离、频率分析
代码(转自官方wp)

def getKeyPool(cipher, stepSet, plainSet, keySet):''' 传入的密文串、明文字符集、密钥字符集、密钥长度范围均作为数字列表处理.形如[0x11,0x22,0x33]返回一个字典，以可能的密钥长度为键，以对应的每一字节的密钥字符集构成的列表为值，密钥字符集为数字列表。形如{1:[[0x11]],3:[[0x11,0x33,0x46],[0x22,0x58],[0x33]]}'''keyPool = dict()for step in stepSet:maybe = [None] * stepfor pos in xrange(step):maybe[pos] = []for k in keySet:flag = 1for c in cipher[pos::step]:if c ^ k not in plainSet:flag = 0if flag:maybe[pos].append(k)for posPool in maybe:if len(posPool) == 0:maybe = []breakif len(maybe) != 0:keyPool[step] = maybereturn keyPooldef calCorrelation(cpool):'''传入字典，形如{'e':2,'p':3}返回可能性，0~1,值越大可能性越大(correlation between the decrypted column letter frequencies andthe relative letter frequencies for normal English text)'''frequencies = {"e": 0.12702, "t": 0.09056, "a": 0.08167, "o": 0.07507, "i": 0.06966,"n": 0.06749, "s": 0.06327, "h": 0.06094, "r": 0.05987, "d": 0.04253,"l": 0.04025, "c": 0.02782, "u": 0.02758, "m": 0.02406, "w": 0.02360,"f": 0.02228, "g": 0.02015, "y": 0.01974, "p": 0.01929, "b": 0.01492,"v": 0.00978, "k": 0.00772, "j": 0.00153, "x": 0.00150, "q": 0.00095,"z": 0.00074}relative = 0.0total = 0fpool = 'etaoinshrdlcumwfgypbvkjxqz'total = sum(cpool.values())  # 总和应包括字母和其他可见字符for i in cpool.keys():if i in fpool:relative += frequencies[i] * cpool[i] / totalreturn relativedef analyseFrequency(cfreq):key = []for posFreq in cfreq:mostRelative = 0for keyChr in posFreq.keys():r = calCorrelation(posFreq[keyChr])if r > mostRelative:mostRelative = rkeychar = keyChrkey.append(keychar)return keydef getFrequency(cipher, keyPoolList):''' 传入的密文作为数字列表处理传入密钥的字符集应为列表，依次包含各字节字符集。形如[[0x11,0x12],[0x22]]返回字频列表，依次为各字节字符集中每一字符作为密钥组成部分时对应的明文字频形如[{0x11:{'a':2,'b':3},0x12:{'e':6}},{0x22:{'g':1}}]'''freqList = []keyLen = len(keyPoolList)for i in xrange(keyLen):posFreq = dict()for k in keyPoolList[i]:posFreq[k] = dict()for c in cipher[i::keyLen]:p = chr(k ^ c)posFreq[k][p] = posFreq[k][p] + 1 if p in posFreq[k] else 1freqList.append(posFreq)return freqListdef vigenereDecrypt(cipher, key):plain = ''cur = 0ll = len(key)for c in cipher:plain += chr(c ^ key[cur])cur = (cur + 1) % llreturn plaindef main():ps = []ks = []ss = []ps.extend(xrange(32, 127))ks.extend(xrange(0xff + 1))ss.extend(xrange(38))cipher = getCipher(c)keyPool = getKeyPool(cipher=cipher, stepSet=ss, plainSet=ps, keySet=ks)for i in keyPool:freq = getFrequency(cipher, keyPool[i])key = analyseFrequency(freq)plain = vigenereDecrypt(cipher, key)print plain,"\n"print ''.join(map(chr,key))if __name__ == '__main__':main()

0x10 afctf2018-magicnum

浮点数转ascii字符

72065910510177138000000000000000.000000
71863209670811371000000.000000
18489682625412760000000000000000.000000
72723257588050687000000.000000
4674659167469766200000000.000000
19061698837499292000000000000000000000.000000

c代码（来自博客）

#include <stdio.h>int main()
{   float i = 72065910510177138000000000000000.000000;char *p = &i;printf("%c\n",*(p));printf("%c\n",*(p+1));printf("%c\n",*(p+2));printf("%c\n",*(p+3));return 0;
}