# Crypto

# littleRSA

题目

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

	m = bytes_to_long(flag)
	p = getPrime(512)
	q = getPrime(512)
	phi = (p-1)*(q-1)
	e = 65537
	n = p * q
	c = pow(m, e, n)

	s = getPrime(300)
	N = getPrime(2048)
	g = p * inverse(s,N)2 % (N2)
	print(N)
	print(g)
	print(n)
	print(c)

	'''
	19351301035801508116955552063316327463227928638319284082504070745230119792307421099534903837766317639913937954784857576991401214861067471772614753337821871108189780331081099041824669243928056765115068764246765680962348646383991303828426125303844394268682191775232611288039200316595279055408827296256289143602827525373267536643865729646353071637054367702218515803980122435811129935450486950137279824491461041391572264371799797200331838690523349105589985032730668315787318829244743317257793753147209875458127340875400367081865762286565978620979196410411241442894450955280237513249393612603560410291825805553536595543937
	101172011079013273946711882340439823149055809449035744718659818796135714101721641190114954130041477714466321498903210220694435354795744225843314447645623337668697058127975104586375292636080114347294697007231487782548846095107329445479367324424672776003899748234353857872627585595343736452088156885081907758727085723312506489549364721644636251780350312413098132506051531311685636921117457469745637347738336829350634994271419554741425590636953154753970902976959308323838617091060754826727417688836026597614894745348808019654100196615719730109909578899299246848916182034705259206906552769087038179288139086772719994577168184701096922291610523676039127012518100023765548552210944426749474888311751069936144583375194023227887848704267587915237057432609663328145608194550736074250822416779448467084842127165553649513397606464059847361880649213934069715996589751778384513724306521043255299443480482640183740131563318058454711913397533436985618182923646192481486120942073719321372236539019107909910597047133371708017755744495134116771999521953654596632221519266339372439452558083199640035069852530373510758859460350025736629801086757717838159774542506755335660607766677992105601518694405113552321342152041808586187181800679845672788746273313
	90106928919727272173474070618911951313216606598108495724382284361415375454490594410306345748069424740100772955015304592942129026096113424198209327375124576666577469761124470792842854884924199449996929134613382626394351988541980388358156143332979538058465890179760337315789398915560641465656968797050755849799
	51609249982849856103564442566936515708380814106997783395400669324617748952940831076546581735494963467680719842859574144530848473300102236821201997786375946601413660428461473204032985053128283751860315027843200214217715401391736262811016964783589439740884991543059175666298728428567481043422497862838127903980
	'''

$g=p*invese(s,N)^2\%(N^2)$

$g*s^2=p+k*N$

$g*s^2-k*N=p$

就是格

$\left| \begin{array}{lcr} 1 & g\\ 0 & N \end{array} \right|$

	from Crypto.Util.number import *
	N = 19351301035801508116955552063316327463227928638319284082504070745230119792307421099534903837766317639913937954784857576991401214861067471772614753337821871108189780331081099041824669243928056765115068764246765680962348646383991303828426125303844394268682191775232611288039200316595279055408827296256289143602827525373267536643865729646353071637054367702218515803980122435811129935450486950137279824491461041391572264371799797200331838690523349105589985032730668315787318829244743317257793753147209875458127340875400367081865762286565978620979196410411241442894450955280237513249393612603560410291825805553536595543937
	g = 101172011079013273946711882340439823149055809449035744718659818796135714101721641190114954130041477714466321498903210220694435354795744225843314447645623337668697058127975104586375292636080114347294697007231487782548846095107329445479367324424672776003899748234353857872627585595343736452088156885081907758727085723312506489549364721644636251780350312413098132506051531311685636921117457469745637347738336829350634994271419554741425590636953154753970902976959308323838617091060754826727417688836026597614894745348808019654100196615719730109909578899299246848916182034705259206906552769087038179288139086772719994577168184701096922291610523676039127012518100023765548552210944426749474888311751069936144583375194023227887848704267587915237057432609663328145608194550736074250822416779448467084842127165553649513397606464059847361880649213934069715996589751778384513724306521043255299443480482640183740131563318058454711913397533436985618182923646192481486120942073719321372236539019107909910597047133371708017755744495134116771999521953654596632221519266339372439452558083199640035069852530373510758859460350025736629801086757717838159774542506755335660607766677992105601518694405113552321342152041808586187181800679845672788746273313
	n = 90106928919727272173474070618911951313216606598108495724382284361415375454490594410306345748069424740100772955015304592942129026096113424198209327375124576666577469761124470792842854884924199449996929134613382626394351988541980388358156143332979538058465890179760337315789398915560641465656968797050755849799
	c = 51609249982849856103564442566936515708380814106997783395400669324617748952940831076546581735494963467680719842859574144530848473300102236821201997786375946601413660428461473204032985053128283751860315027843200214217715401391736262811016964783589439740884991543059175666298728428567481043422497862838127903980
	m=matrix([[1,g],[0,N]])
	e = 65537
	p=int(-m.LLL()[0][1])
	q=n//p
	phi=(p-1)*(q-1)
	d=inverse(e,phi)
	print(long_to_bytes(pow(c,d,n)))

# easysign

题目

	from Crypto.Util.number import *
	import libnum
	from random import randint
	from secret import flag

	p = getPrime(512)
	d = getPrime(40)
	m = libnum.s2n(flag)
	a = randint(2,p)
	b = randint(2,p)
	c = randint(2,p)
	g = d

	for i in range(10):
	g = (cd2 + bg + a)%p
	a = (a*b - c) % p
	b = (b*c - a) % p
	c = (c*a - b) % p

	t = (m+d)**2 %p

	print('p=',p)
	print('a=',a)
	print('b=',b)
	print('c=',c)
	print('g=',g)
	print('t=',t)

	'''
	p= 7591656713055743077369340861541583433090841738590989539280316533530045331013958613146671718809022799047779468311222607020894006899032327866283558110087799
	a= 4392865163304254999527172406061971162689920565151840813033448791785156740502864894051809689255751412382468345217962713758808061870635744521996229554057672
	b= 2119856022628544669301306700581535843188073099896481101405665476192582614655960576092254118367775147735092457551317887281026710342124525625026559538165667
	c= 3370586754351688470908526079815435343732016329743637661764947106415792049906966624513736208696137655804912688128186282852926377345819134856707156640355705
	g= 2221154642536617375933147254663757148609834736621720750750043572054496685087600339999953459509198087870095805651320901316659013390557077204194753685935362
	t= 6426975621182152052236088849377616252912408340750729257254509090637526282051064469268808395760737262115678691330037039061905028548054911000486882481093832
	'''

往回可以逆出 a,b,c

方程求解即可得 d

	from Crypto.Util.number import *

	p= 7591656713055743077369340861541583433090841738590989539280316533530045331013958613146671718809022799047779468311222607020894006899032327866283558110087799
	a= 4392865163304254999527172406061971162689920565151840813033448791785156740502864894051809689255751412382468345217962713758808061870635744521996229554057672
	b= 2119856022628544669301306700581535843188073099896481101405665476192582614655960576092254118367775147735092457551317887281026710342124525625026559538165667
	c= 3370586754351688470908526079815435343732016329743637661764947106415792049906966624513736208696137655804912688128186282852926377345819134856707156640355705
	g= 2221154642536617375933147254663757148609834736621720750750043572054496685087600339999953459509198087870095805651320901316659013390557077204194753685935362
	t= 6426975621182152052236088849377616252912408340750729257254509090637526282051064469268808395760737262115678691330037039061905028548054911000486882481093832
	P.<d>=Zmod(p)[]


	for i in range(10):
	c = (c + b) * inverse(a, p) % p
	b = (b + a) * inverse(c, p) % p
	a = (a + c) * inverse(b, p) % p
	g = (g - a - c * d ** 2) * int(inverse(b, p))



	res=(g-d).roots()
	P.<md>=Zmod(p)[]
	f=md^2-t
	mmm=f.roots()
	for i in mmm:
	for j in res:
	print(long_to_bytes(i[0]-j[0]))

# easyRSA

题目

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

	bitlen = 512
	p = getPrime(bitlen)
	q = getPrime(bitlen)
	r = getPrime(bitlen)

	assert p != q and q != r and p != r

	n = pqr
	phi = (p-1)(q-1)(r-1)

	while 1:
	d = getPrime(256)
	try:
	e = int(gmpy2.invert(d,phi))
	except:
	continue
	if gmpy2.gcd(e,phi) == 1 :
	break

	assert flag.startswith(b'CBCTF{')
	m = bytes_to_long(flag)
	c = pow(m,e,n)
	print('c =',c)
	print('e =',e)
	print('n =',n)

	'''
	c = 262857004135341325365954795119195630698138090729973647118817900621693212191529885499646534515610526918027363734446577563494752228693708806585707918542489830672358210151020370518277425565514835701391091303404848540885538503732425887366285924392127448359616405690101810030200914619945580943356783421516140571033192987307744023953015589089516394737132984255621681367783910322351237287242642322145388520883300325056201966188529192590458358240120864932085960411656176
	e = 543692319895782434793586873362429927694979810701836714789970907812484502410531778466160541800747280593649956771388714635910591027174563094783670038038010184716677689452322851994224499684261265932205144517234930255520680863639225944193081925826378155392210125821339725503707170148367775432197885080200905199759978521133059068268880934032358791127722994561887633750878103807550657534488433148655178897962564751738161286704558463757099712005140968975623690058829135
	n = 836627566032090527121140632018409744681773229395209292887236112065366141357802504651617810307617423900626216577416313395633967979093729729146808472187283672097414226162248255028374822667730942095319401316780150886857701380015637144123656111055773881542557503200322153966380830297951374202391216434278247679934469711771381749572937777892991364186158273504206025260342916835148914378411684678800808038832601224951586507845486535271925600310647409016210737881912119
	'''

维纳攻击用不了，看了 wp

好像是维纳扩展

	import libnum

	c = 262857004135341325365954795119195630698138090729973647118817900621693212191529885499646534515610526918027363734446577563494752228693708806585707918542489830672358210151020370518277425565514835701391091303404848540885538503732425887366285924392127448359616405690101810030200914619945580943356783421516140571033192987307744023953015589089516394737132984255621681367783910322351237287242642322145388520883300325056201966188529192590458358240120864932085960411656176
	e = 543692319895782434793586873362429927694979810701836714789970907812484502410531778466160541800747280593649956771388714635910591027174563094783670038038010184716677689452322851994224499684261265932205144517234930255520680863639225944193081925826378155392210125821339725503707170148367775432197885080200905199759978521133059068268880934032358791127722994561887633750878103807550657534488433148655178897962564751738161286704558463757099712005140968975623690058829135
	n = 836627566032090527121140632018409744681773229395209292887236112065366141357802504651617810307617423900626216577416313395633967979093729729146808472187283672097414226162248255028374822667730942095319401316780150886857701380015637144123656111055773881542557503200322153966380830297951374202391216434278247679934469711771381749572937777892991364186158273504206025260342916835148914378411684678800808038832601224951586507845486535271925600310647409016210737881912119


	def plus(e, n):
	m = 2
	c = pow(m, e, n)
	q0 = 1

	list1 = continued_fraction(Integer(e) / Integer(n))
	conv = list1.convergents()
	for i in conv:
	k = i.numerator()
	# print(k)
	q1 = i.denominator()
	# print(q1)

	for r in range(20):
	for s in range(20):
	d = r * q1 + s * q0
	m1 = pow(c, d, n)
	if m1 == m:
	print(r, s)
	return d

	q0 = q1


	d = plus(e, n)
	print(d)
	print(libnum.n2s(int(pow(c, d, n))))

# Crypto

# littleRSA

# easysign

# easyRSA

2022浙江省赛

DASCTF X GFCTF 2022十月挑战赛