Crypto

七七的欧拉

解题人：g0ubu1i
分解n后发现为某数的次方
image.png
根据欧拉定理，phi=p8 - p7，求得d解出题

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
from gmpy2 import *

e=8401285423075497989963572888601376313375827722858883767564499066473101615084214973041844878664837606157257039358849583049856161628241418012475432529735909
n=4321524416983780646994834778612486851863709339970595612409550086067211224407144019110798099401660010305645681548980160563216101786447875231976835115531375372678886339587480251211072894186558627897353793098608766868067029578667171419890150599640781594755080391489447462042167529203389236065727274166091741227068469987681083794139925327545810024038937132463518225611578727737940746784891867532498184642892826569777559107609493212332054559366409007685504768163376250281644004067745087899653778023414105973047620041288118404657934689253192043728590231618132716567084621670074256312939305265244486145758609971249077639085204680923108132415216543541472534580414274250979940330459551536830268428508217821060604260805109071534457808355664329902779603050878055690772430842865701249378096775899778255848773171108341331128673249899037133851535556515961699925809139476576825524135111237249709241579903807179252011010794867269715170739895392375920757559721516050680666658719990497863646989338960261844762127142439486275294670858114079687572243312184222126710967744971775585723045524467708387051034760208768956889939050498139189352842087278125173957182804116052402778416216669522309692266036094371308166663738284209615212016564171075874421472070422416318901926525719485991792111414333398004433143751908199358861514725313334333703539239414806773743941986164981642517673117412666430463318509571757766510835600758060976848374353352239044908034501477295696684294816091801944163877509558909040753907584672390823893991672246726026216973013330313971007514064831801564703364591696610900089228302936595848024616691878437618798864186634802647568239526771151323609650598156701595265876736712670677452013054393336294483452480213271032488201259990782289047132105989846972462094302132564809025802421057537091870932014884606863807260521123084423689494401900014232257381801590783735595575258160274248494498550583673688754220860142413631521279464318987425447302135444093663034598455694901199312497459228254746451233078954904159983269585883146959928222698672413648364391121696092287848931565798557217897678221379451042304811449415982434055522599829843482810025780349284547491767219221510351411192251236517341826619338084348136539121415210345488359563985046136632077665460793346345051213014836088333266911684271237227766588616771431226302155269893547077232087387411935345207081799500649921586279416751311277417949192360648342427657867424947189027886922112452681434778850977010752230391327878892161
c=1319666577538961333645698288755316431847498788803191213042970951363587036899021668814931340784440773619019635330248746606532233949080268712626456845590851812018539646705520729734738948568349756255640832936325965096602018372418260009779997764653043892043725224481361578258532294625476542003357969893609762981355267857532927948279737945466285738730414948695579002627741734690862181161919734547857550654813379550806374778412603233570494684223057004866601064851006909940259029023083838730497564657690493780040030061594915385886594845808342023634855913932575150487723897981518504381563064479784253539091893925934095008385592529031453149337783826491324308222762190756839839091742536583068791632135883271750510776330897598323339568926234205068941397524390446254057404779041850572848212437589629794980799894974937730065394307284096622814438575278571743516485062058882794531407454597341604166586040406867868323002258035737328450923576878935675998377134860357842547595516243737449809845708319003744144753130977649201725370898918939022097783844477196723482879094829249203949784703408369396219233552019108990900029123063369670129291960293576115301371071209198455299007327352602249399500334424934488528506773472420414119617828578424633182320749576697196936762283306228974126242434663703609495003656244194067493769815032134577138807799395279843708630774412341952691146906264694889245375545635688534662371202213660012977431598746482601668122679279419039288257069843297770840263002870206849857995148396439717143553611140228607531647245352254251824086797704561756363448681983654454393569932173970943157225527780067126895832370645456372127507057750232257828579628856504832975775855059816283684123444984393171125206440588627925736223222718784319209561804023835238526792966229582251575475514349566824846911411659740321154272534589694497411065971714157409318007179403833025337349924938487211920583780456897879801099476865645416182025930390267064170271613760577949655548949317295792361772032185463678410983568470647837758657058230086368185901572658482084202212103405161775243930901117532775865963215971025744893777631306256061896284125630451368067313753222195227231131526000755922331413457862253392530308284156400411897252674398583100198330007779643967156773216464341590817951828849769679134515304258819218015083183653130972243262400248230445031327719507314015062447355358100770763425336581258193908638241498461735819218673116282476452340137513156421147748432605954889277898079292196216
p = 90043967260093945222624152587689121936371930974666442796337497007806436220933640104101224556701782897110707124711581073042785835680900647501045466519201150330902139448582877574558481499349246396434566916237734745291901204887326075328782341527220826176727297933741479223587035887696689567725839887008586221103

phi = p**8 - p**7
d = gmpy2.invert(e,phi)
print(long_to_bytes(pow(c,d,n)))

image.png

夹里夹气

解题人：dmw
b489aa1f37a1f079f0c1ebcfa9008b59.png
题目提示摩斯密码，看摩斯密码表
143dc4b5d5ee47edf8e766e16f7eaa26.png
根据flag外壳可以推断
嘤嘤？=. 嘤嘤嘤=-
得到
9a8afff99834cc6f54adcb9a9810ce86.png
解密得到flag：ISCTF{HSBDH_SFJ_JDNFJ_DJNFJDM}
a165f1b0cfaf5c2b1921dde084ed1e69.png

easy_rsa

解题人：g0ubu1i
获取附件后nc连接，得到pqec，编写脚本求m

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import *
from gmpy2 import *

p=167561191404321668748830155982148128078094297761744585473561597817468679161266224937726777063364341455943741358249714181954186947851755403287400313044668068915799453457253339629929712548154901350977293977396925064084110789695911728228292958713708869220389929513985054498626193204179190043233878936508865839033
q=158850164670351411226854199870571072891191250008284001651273515387478727731321002321763694826236623788860130822650234773829136028319501896718021031170321199126229125742927056311652861918625254681349069189136573855288383606649620226798427177954527952663485539668001819685952435682898253076761435373461926046137
e=65537
c=4242413297580463331572289283614465576920321904916668533268592047566389769615853283522402653147881010365969562119872301345718233952127637191547842532720861202915213183417888317518184193386552827375852739915676012379130542280256557996822960648308856834792396590872307646080450688311758622439062833141968275861674897506922516574551903131353406719045301549179127740987746392700068342699602004118628459557889230235166487708932077823995407170566299934821909316066022781254941124247363837047877775106189816885421001854139347246364493895035678034310316567263582591786939062838380261769117834938911059384946629475006205178429

d = inverse(e, (p-1)*(q-1))
print(long_to_bytes(pow(c, d, p*q)))

得到flag
image.png

rsa_d

解题人：g0ubu1i
nc连接靶机后要求计算d
写脚本

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *
from gmpy2 import *

p=43625867
q=5050993
e=65537

d = inverse(e, (p-1)*(q-1))
print(d)

image.png

ezRSA(τ)

解题人：g0ubu1i

step1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def step1(m):
	p,q = getPrime(1024),getPrime(1024)
	n=p*q
	e=getPrime(512)
	phi = (p-1)*(q-1)
	while gcd(e,phi) != 1:
		e=getPrime(512)
	d = pow(e,-1,phi)
	k = randint(800,1500)
	f = factor(k)
	# print(f"\n\n\n\n{k=}\n\n\n\n")
	leak = (pow(e, 2) + (e*d - 1)*f)*getPrime(256) + k 	# (e**2 + (e*d-1)*k!)*x + k 
	print(f"{n=}")
	print(f"{leak=}")
	e = 65537
	c = pow(m,e,n)
	return c

根据output.txt我们有n，c，leak，而leak等于
![](D:\blog\hexo-blog\source_posts\ISCTF-Crypto-WP\3011dd7c7fb1be06026dcfd5f4dd1514.svg#card=math&code=leak %3D (pow(e%2C2)%2B(e^d - 1)f)getPrime(256) %2B k&id=ReRjY)
且phi = ed - 1，f为k的阶乘
由于给定的k的范围比较小，所以可以爆破k。
给leak%f后得到


由此确定e2s为1280位且不是素数
由推导

由此确定e**2s为1280位且不是素数
由上述条件可得到确定e的条件，写代码

1
2
3
4
5
6
7
8
9
for k in range(800, 1042):
    f = int(factor(k))
    e2_s = (leak-k) % int(f)
    phis = (leak -k - e2_s) // f 

    s = GCD(tphi,e2_s)
    if e2s.bit_length() == 1280 and isPrime(e2s)==False and s.bit_length()>=255:
        print(k)
        print(s)

即可得到k，s，继续推导可得到phi与e

由此解出第一部分

step2：

首先考察LCG算法，由LCG算法恢复出p

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from Crypto.Util.number import *
from random import randint,getrandbits
from sympy import factorial as factor
from gmpy2 import is_prime as is_strongPrime
from gmpy2 import gcd
from libnum import s2n

from Crypto.Util.number import *
def gcd(a,b): 
    if(b==0): 
        return a 
    else: 
        return gcd(b,a%b) 
leak2 =  [362437850887271063413256292444148642949623196635276044583204094265607936120337004605360832421011, 1932915843524327487337992118762711929552569713433223514001673251237692307587356544615955431611435994003602897830069566867051943572065473955405337889221398, 11222178024143398739150445814520244630341642052876364179793404105841311693968292227072031763726153574031884490677131749512430325919668649359617953965112844, 5408933876805830533113961512210040977462510675785228477646978801328722923647434079128879371684477664804744431834418916837956820965870203842552250165916773, 1447143741705069323823257922715038721270982554690635708441585728089036094805730054505696492295730683300002193478561819037345041940787115528445592303142510, 3707657531268843465369646969917923274507341341483950204025637357600814449263032574496424566705812439915548150679438579110456264431525526309588664326456861, 9263925820149827740182684692442727161206242182976684575667062235695526783971703826794731732152445051579616121306722939129265340347908823003172137299057843, 207494591333501391015462321304802957885928775185602834554977737560856036337667840127810136802887548047878444936730742505483927963807357904024967768148122, 7052936859446617933917872361389151092893299250603966165472023802877016733939957851026719428770748111897050866474067880613419756475700748999497496482278608, 1169538791889404037461397919075674424569430764451305755000680272926397357803359328850780774937432248011264334398346178303234064891680342161511829008635621]
t = []
for i in range(9):
    t.append(leak2[i]-leak2[i-1]) 
all_n = []
for i in range(7):
    all_n.append(gcd((t[i+1]*t[i-1]-t[i]*t[i]), (t[i+2]*t[i]-t[i+1]*t[i+1]))) 

MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] #逆元计算
for p in all_n:
    p=abs(p)
    if p==1:
        continue
    a=(leak2[2]-leak2[1])*MMI((leak2[1]-leak2[0]),p)%p
    ani=MMI(a,p)
    b=(leak2[1]-a*leak2[0])%p
    seed = (ani*(leak2[0]-b))%p
    plaintext=seed
    q = n // p
    if plaintext.bit_length() >= 63 and leak1-p-q==0:
        #continue
        print(a)
        print(b)
        print(p)
        print(seed)

通过得到的a，b，seed重新计算seed

1
2
3
4
5
6
7
a = 77103936782340200964969557381530979461498267151335748569651214009683718895787
b = 80415964905483336441916158760498483436647287707097172421898625062076211518999
seed = 4700640019334050676
leak2 = []
for i in range(10):
    leak2.append(seed := (seed * a + b) % p)
seed = (seed * a + b) % p

接着爆破key得到key

1
2
3
4
for key in trange(60000000+1,10**8 //2+1,-2):
    if is_prime(key) and not is_strongPrime(key):
        print(key)
        break

拿到key后可求得base，通过final求得c，求解c得到后半段密文

1
2
3
4
5
6
7
8
9
10
11
key = 56052361
base = key ^ seed
e=0x10001
d = inverse(e,(p-1)*(q-1))
final = [2268617516274900905319941795987877533673889507146326516564545408684476960310333170888941124460992562245780101836116975666368936099249664924148379487909122, 1445275952377746701088629016221431744592935398639655895336779954310077866709012082302847692239730041591520169244063854849129773530127510048494782550102381, 7]
c = 0
u = 0
for i in final:
    c += final * (base ** u)
    u += 1
print(long_to_bytes(pow(c,d,n)))

image.png

signin

解题人：g0ubu1i
考点：Schmidt-Samoa密码系统

1
2
3
4
5
6
7
8
from Crypto.Util.number import *

c = 29897791365314067508830838449733707533227957127276785142837008063510003132596050393885548439564070678838696563164574990811756434599732001622138564176327233154381380717648392357672642893142367607369679906940371540867456654151408884171467638060523066406441697453971996011548195499549200103123841556085936672833238264876038160712793697159776332101536779874757463509294968879216810485825310481778472384531442206034564488532399171243463881900578407746982324779260941957792455217641883334131366614310644607114128868153897806362954456585661855569432513785225453501792356175649676419772626548071916379318631677869452985829916084336045071072493567871623113923140668031380684940109024609167449291380675124701557542736834722898328082888430566229322840781411336263268594978558564310744076581639469210462567543585251718744340216155557606004995449505782302864725856877289388008819135023371948017425832082773421030256964953984562211638060
N = 3231913372897424708803097969843687520868057190788284975066875241636436021279559026753076528399891936983240045179193386905918743759145596242896507856007669217275515235051689758768735530529408948098860529277921046146065473333357110158008648799207873976745048714516868561754202543130629713461365314627535982379718931633528922076268531363809414255082933615667770491818402126891370106045838695484124212397783571579791558324350069782623908757815983802849109451590357380624488436968737140312471089662428308113246310588336044438265822574558816510054763215983649467009345458480077882624118620789015758507736272402998721366662352794082495441303895025585316667229865533166614969641012195668280586477033200418153345241668242651407009849656745509386158276185301334443855737552801531617549980843398648751032649895403939319648954908487619711555700124294191702406981128355348449748466449951568451135718146828444185238617155432417897711198169
d = 220908195398117048628110042133057032501548264225985823161565460390793825899523662424732910718579350524590368287207857059670558852106434615134645183432670023784725430385048028248108677670095524205518013647694485975996499747580966911259433184798952372110628624294686853944766950244209186984164963987120416687012811346656498861438432610431705868541829977481875385468143747334359481673214618931159403123892213161430602430294790913847722073762999311674428134241956293914716183107414340330449465142849402354034926378025006749405210014879947411570380433942279355488861684317611066949685697268714760755591128598654573304969
l = pow(2,N*d,N)-2
x=GCD(N,pow(2,l))
print(long_to_bytes(pow(c,d,x)))

得到flag
image.png