p = 12567387145159119014524309071236701639759988903138784984758783651292440613056150667165602473478042486784826835732833001151645545259394365039352263846276073 q = 12716692565364681652614824033831497167911028027478195947187437474380470205859949692107216740030921664273595734808349540612759651241456765149114895216695451 c = 108691165922055382844520116328228845767222921196922506468663428855093343772017986225285637996980678749662049989519029385165514816621011058462841314243727826941569954125384522233795629521155389745713798246071907492365062512521474965012924607857440577856404307124237116387085337087671914959900909379028727767057 e = 65537 n = p*q phi = (p-1)*(q-1) d = inverse(e,phi) m = pow(c,d,n) print(long_to_bytes(m)) #b'LitCTF{it_is_easy_to_solve_question_when_you_know_p_and_q}'
p = 7221289171488727827673517139597844534869368289455419695964957239047692699919030405800116133805855968123601433247022090070114331842771417566928809956044421 q = n // p phi = (p-1)*(q-1) d = inverse(e,phi) m = pow(flag,d,n) print(long_to_bytes(m))
flag = b'4A5A4C564B36434E4B5241544B5432454E4E32465552324E47424758534D44594C4657564336534D4B5241584F574C4B4B463245365643424F35485649534C584A5A56454B4D4B5049354E47593D3D3D' from base64 import * flag=b64decode(b32decode(b16decode(flag))) print(flag)
顺序反过来解码就行了
8.Big RSA
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
from Crypto.Util.number import * from flag import *
n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061 n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073 e = 65537 m = bytes_to_long(flag) c = pow(m, e, n1) c = pow(c, e, n2)
print("c = %d" % c)
# output # c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264
import re import string from collections import Counter
# 英文自然语言频率 ENGLISH_FREQ = [ 0.08167,0.01492,0.02782,0.04253,0.12702,0.02228, 0.02015,0.06094,0.06966,0.00153,0.00772,0.04025, 0.02406,0.06749,0.07507,0.01929,0.00095,0.05987, 0.06327,0.09056,0.02758,0.00978,0.02360,0.00150, 0.01974,0.00074 ] ALPHABET = string.ascii_uppercase ciphertext = ''' ''' cip = re.sub('[^A-Z]',"",ciphertext.upper()) # print(cip) defIC(group): fre = [0]*26 for i inrange(len(group)): fre[ALPHABET.index(group[i])] +=1 sum = 0 for i in fre: sum += i*(i-1) IC = sum / (len(group)*(len(group)-1)) return IC ic = [] for keylen inrange(1,15): if1: groups = [[] for _ inrange(keylen)] for i inrange(len(cip)): groups[i%keylen].append(cip[i]) ic.append((abs(sum([IC(groups[i]) for i inrange(len(groups))]) / len(groups)-0.065),keylen,groups)) ic.sort() #按ic最接近0.065排序,第一个就是最可能的长度 defchi(exp,fac): chi = 0 for i,j inzip(exp,fac): chi += (i-j)**2 / i return chi defCeasar(plain,key): ciphertext = '' for i inrange(len(plain)): ciphertext += ALPHABET[(ALPHABET.index(plain[i])-key)%26] return ciphertext print("最有可能的密钥长度",ic[0][1]) key = [] for groups in ic[0][2]: candidate = [] for shift inrange(26): plain = Ceasar(groups,shift) fre = [0for i inrange(26)] for j inrange(len(plain)): #卡方分布最接近英语的,就是密钥 fre[ALPHABET.index(plain[j])] +=1 /len(plain) candidate.append(chi(ENGLISH_FREQ,fre)) key.append(ALPHABET[candidate.index(min(candidate))]) print("最有可能的密钥","".join(key))
e = 65537 n = 87924348264132406875276140514499937145050893665602592992418171647042491658461 c = 87677652386897749300638591365341016390128692783949277305987828177045932576708
比较低质量的题,直接factorb分解
p=275127860351348928173285174381581152299
q = n//p
略
14.yafu
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
from Crypto.Util.number import * from secret import flag
m = bytes_to_long(flag) n = 1 for i inrange(15): n *=getPrime(32) e = 65537 c = pow(m,e,n) print(f'n = {n}') print(f'c = {c}') ''' n = 15241208217768849887180010139590210767831431018204645415681695749294131435566140166245881287131522331092026252879324931622292179726764214435307 c = 12608550100856399369399391849907846147170257754920996952259023159548789970041433744454761458030776176806265496305629236559551086998780836655717 '''
比较低质量,sage factor直接做
1 2 3 4 5 6 7 8 9 10 11 12
from Crypto.Util.number import * n=15241208217768849887180010139590210767831431018204645415681695749294131435566140166245881287131522331092026252879324931622292179726764214435307 p = list(factor(n)) p = [ fac[0] for fac in p] phi = 1 for prime in p: phi *= prime -1 c = 12608550100856399369399391849907846147170257754920996952259023159548789970041433744454761458030776176806265496305629236559551086998780836655717 e = 65537 d = inverse(e,phi) m = long_to_bytes(pow(c,d,n)) print(m)
from Crypto.Util.number import * e=74 p= 86053582917386343422567174764040471033234388106968488834872953625339458483149 q= 72031998384560188060716696553519973198388628004850270102102972862328770104493 n=p*q c= 3939634105073614197573473825268995321781553470182462454724181094897309933627076266632153551522332244941496491385911139566998817961371516587764621395810123 P.<x> = PolynomialRing(Zmod(p)) f = x^e - c m = f.monic().roots() m1 = [int(i[0]) for i in m] P.<x> = PolynomialRing(Zmod(q)) f = x^e - c m = f.monic().roots() m2 = [int(i[0]) for i in m] for x1 in m1: for x2 in m2: m = CRT([x1,x2],[p,q]) print(long_to_bytes(m)) b'vZ.\x9eG\t\xac\x06\x109\x8e\xff\x16\xf4F\x7f^\xf3\xfe\x9e\x8b\xf6\xa4\x85ew\xfb\xd2\xeb%\xfd\xa4W\x00\xb4\x99\xf7\x91\xf2\xa3a\x1d\xef\xb3.\xe9+\x9db\x82( b\xae\x84\xf7\xdb\xc6\xe0%\xed\xd9x\x0c' b'B1\x0b\x0b\xa0\xc6\x9cu\x99\xfb\x82a\xaf?TU\x02F\x8b2\xe1\x15\xef\x07\x85\xb6\x9fw\xba\xb1g\xe1\xf8,\x83\x13\x82\x83\x80zJ3\r\x95K\xa3\x91\xb1\xc6\xe8\xec)\xcb\x94\x88\x8f\x9f\x1e54\x83\xd0Ep' b'4)#\x92\xa6C\x0f\x90v>\x0c\x9dg\xb4\xf2*\\\xadsk\xaa\xe0\xb5}\xdf\xc1\\[0t\x95\xc2^\xd41\x86u\x0er)cTVa7\x8c\x15P\xfa\xca\xafV\x05Jp\xc7}\x07\xfbc\xd3v\x98\x19' b'LitCTF{e_1s_n0t_@_Prime}'
from random import choice from Crypto.Util.number import isPrime, sieve_base as primes from flag import flag
defgetPrime(bits): whileTrue: n = 2 while n.bit_length() < bits: n *= choice(primes) if isPrime(n + 1): return n + 1
e = 0x10001 m = int.from_bytes(flag.encode(), 'big') p, q = [getPrime(2048) for _ inrange(2)] n = p * q c = pow(m, e, n)
# n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513 # c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
n非常大,但是p-1,q-1都光滑,用Pollard攻击轻松解决
1 2 3 4 5 6 7 8 9 10
defPollard(N): B = 2 x = 2 whileTrue: x = pow(x, B, N) p = gmpy2.gcd(x-1, N) if p notin [1,N]: q = N // p return [p,q] B += 1
from Crypto.Util.number import * from gmpy2 import * import random c1= 463634070971821449698012827631572665302589213868521491855038966879005784397309389922926838028598122795187584361359142761652619958273094398420314927073008031088375892957173280915904309949716842152249806486027920136603248454946737961650252641668562626310035983343018705370077783879047584582817271215517599531278507300104564011142229942160380563527291388260832749808727470291331902902518196932928128107067117198707209620169906575791373793854773799564060536121390593687449884988936522369331738199522700261116496965863870682295858957952661531894477603953742494526632841396338388879198270913523572980574440793543571757278020533565628285714358815083303489096524318164071888139412436112963845619981511061231001617406815056986634680975142352197476024575809514978857034477688443230263761729039797859697947454810551009108031457294164840611157524719173343259485881089252938664456637673337362424443150013961181619441267926981848009107466576314685961478748352388452114042115892243272514245081604607798243817586737546663059737344687130881861357423084448027959893402445303299089606081931041217035955143939567456782107203447898345284731038150377722447329202078375870541529539840051415759436083384408203659613313535094343772238691393447475364806171594 c2= 130959534275704453216282334815034647265875632781798750901627773826812657339274362406246297925411291822193191483409847323315110393729020700526946712786793380991675008128561863631081095222226285788412970362518398757423705216112313533155390315204875516645459370629706277876211656753247984282379731850770447978537855070379324935282789327428625259945250066774049650951465043700088958965762054418615838049340724639373351248933494355591934236360506778496741051064156771092798005112534162050165095430065000827916096893408569751085550379620558282942254606978819033885539221416335848319082054806148859427713144286777516251724474319613960327799643723278205969253636514684757409059003348229151341200451785288395596484563480261212963114071064979559812327582474674812225260616757099890896900340007990585501470484762752362734968297532533654846190900571017635959385883945858334995884341767905619567505341752047589731815868489295690574109758825021386698440670611361127170896689015108432408490763723594673299472336065575301681055583084547847733168801030191262122130369687497236959760366874106043801542493392227424890925595734150487586757484304609945827925762382889592743709682485229267604771944535469557860120878491329984792448597107256325783346904408 N= 609305637099654478882754880905638123124918364116173050874864700996165096776233155524277418132679727857702738043786588380577485490575591029930152718828075976000078971987922107645530323356525126496562423491563365836491753476840795804040219013880969539154444387313029522565456897962200817021423704204077133003361140660038327458057898764857872645377236870759691588009666047187685654297678987435769051762120388537868493789773766688347724903911796741124237476823452505450704989455260077833828660552130714794889208291939055406292476845194489525212129635173284301782141617878483740788532998492403101324795726865866661786740345862631916793208037250277376942046905892342213663197755010315060990871143919384283302925469309777769989798197913048813940747488087191697903624669415774198027063997058701217124640082074789591591494106726857376728759663074734040755438623372683762856958888826373151815914621262862750497078245369680378038995425628467728412953392359090775734440671874387905724083226246587924716226512631671786591611586774947156657178654343092123117255372954798131265566301316033414311712092913492774989048057650627801991277862963173961355088082419091848569675686058581383542877982979697235829206442087786927939745804017455244315305118437 e1e2 = 3087 e = list(factor(e1e2)) from itertools import product
defall_divisors(e): primes = [i[0] for i in e] values = [i[1] for i in e] exponents = [range(e+1) for e in values] divisors = [] for powers in product(*exponents): d = 1 for p, k inzip(primes, powers): d *= p**k divisors.append(d) returnsorted(divisors) for e1 in all_divisors(e): e2 = e1e2 // e1 e,x,y = gcdext(e1,e2) print(f'e={e}') mpow = pow(c1,x,N)*pow(c2,y,N) % N for k inrange(2**22): if iroot(mpow+k*N,e)[1]: m = iroot(mpow+k*N,e)[0] print(f'k={k}') print(long_to_bytes(m)) break
from pwn import * from re import * from tqdm import * p = remote("node4.anna.nssctf.cn",28511) p.recvuntil("Good luck & Have fun!\n") for _ in trange(100): cal = p.recvline().decode() cal = re.search(r"(\d+\s*[+\-*/]\s*\d+)",cal) r = cal.group(1) p.send(str(eval(r)).encode()) p.recvline() p.interactive()