# babyrsa

通过

$2^e\quad mod\quad n=c$

可以分解 n 得到 p 和 q

n=4513855932190587780512692251070948513905472536079140708186519998265613363916408288602023081671609336332823271976169443708346965729874135535872958782973382975364993581165018591335971709648749814573285241290480406050308656233944927823668976933579733318618949138978777831374262042028072274386196484449175052332019377

k=pow(2,1049)

c=k-n

因为 $2^e-c$ 为 n 的倍数

所以 p 跟 q 就是后面两个数

然后先解密得到 M

这一段可以想到威尔逊定理

	for i in range(1,p-q):
	m = m*i%n

若 p 为素数

则（p-1)! % p=-1,(p-2)!% p=1

所以我们构造

	for i in range(p-q,p-1):
	m=m*i%n

使 M=m*(p-2)!% n

最后只要 M% p 就能求得 m 了

exp

	from gmpy2 import *



	p=170229264879724117919007372149468684565431232721075153274808454126426741324966131188484635914814926870341378228417496808202497615585946352638507704855332363766887139815236730403246238633855524068161116748612090155595549964229654262432946553891601975628848891407847198187453488358420350203927771308228162321231
	q=34211
	print(p.bit_length())
	c=3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270
	d=invert(1049,(p-1)*(q-1))
	n=p*q
	m=pow(c,d,p*q)
	from Crypto.Util.number import *
	for i in range(p-q,p-1):
	m=m*i%n
	print(long_to_bytes(m%p))

	#PCL{7h3_73rr1b13_7h1ng_15_7h47_7h3_p457_c4n'7_b3_70rn_0u7_by_175_r0075}

# easy_rsa

三段加密一段一段解

第一段

e 和 phi 不互素，g=gcd (e,phi)=2

$m^e\quad mod\quad n=c$

$m^{g*e//g}\quad mod\quad n=c$

$d'=inverse(e//g,phi)$

$M=c^{d'}\quad mod\quad n=m^g\quad mod\quad n=m^2$

直接开方就行

	c=0x27455f081e4858790c6503580dad3302ae359c9fb46dc601eee98f05142128404e95377324720adbbdebf428549008bcd1b670f6749592a171b30316ab707004b9999f3b80de32843afdfd30505b1f4166a03cee9fc48902b74b6e850cfd268e6917c5d84e64f7e7cd0e4a30bfe5903fb5d821d27fdc817d9c4536a8e7aea55af266abcae857a8ffff2f741901baba1b44091a137c69c471c123ab0b80e250e055959c468e6e37c005105ecd7c8b48c659024e5e251df3eeff5da7b3d561cd98150da3575a16bee5f2524d2795fd4879487018345c1e96efc085ed45fb5f02c027aee5bca3aad0eb3e23376c0cd18b02fb05a1ff8fb1af0a3ce4bb671599894e
	p=0xbb602e402b68a5cfcc5cfcc63cc82e362e98cb7043817e3421599a4bb8755777c362813742852dad4fec7ec33f1faec04926f0c253f56ab4c4dde6d71627fbc9ef42425b70e5ecd55314e744aa66653103b7d1ba86d1e0e21920a0bfe7d598bd09c3c377a3268928b953005450857c6cfea5bfdd7c16305baed0f0a31ad688bd
	q=0xbb8d1ea24a3462ae6ec28e79f96a95770d726144afc95ffffa19c7c3a3786a6acc3309820ba7b1a28a4f111082e69e558b27405613e115139b38e799c723ab7fdd7be14b330b118ae60e3b44483a4c94a556e810ab94bbb102286d0100d7c20e7494e20e0c1030e016603bd2a06c1f6e92998ab68e2d420faf47f3ee687fb6d1
	e=0x292
	from Crypto.Util.number import *
	from gmpy2 import *
	print(gcd(e,(p-1)*(q-1)))
	print(e//2)
	d=inverse(e//2,(p-1)*(q-1))
	m=pow(c,d,p*q)
	print(long_to_bytes(iroot(m,2)[0]))
	#b'PCL{16745c3b'

第二段

高位 p 已知

一把梭

	from sage.all import *
	n = 0x841a5a012c104e600eca17b451d5fd37c063ad347707a2e88f36a07e9ad4687302790466e99f35b11580cbe8b0a212e6709686c464a6393c5895b1f97885f23ea12d2069eb6dc3cb4199fb8c6e80a4a94561c6c3499c3c02d9dc9cf216c0f44dc91701a6d9ec89981f261a139500420a51014492f1da588a26e761439dd5739b32540ca6dc1ec3b035043bc535304a06ccb489f72fcd1aa856e1cffe195039176937f9a16bd19030d1e00095f1fd977cf4f23e47b55650ca4712d1eb089d92df032e5180d05311c938a44decc6070cd01af4c6144cdab2526e5cb919a1828bec6a4f3332bf1fa4f1c9d3516fbb158fd4fbcf8b0e67eff944efa97f5b24f9aa65
	p4 = 0xa9cb9e2eb43f17ad6734356db18ad744600d0c19449fc62b25db7291f24c480217d60a7f87252d890b97a38cc6943740ac344233446eea4084c1ba7ea5b7cf2399d42650b2a3f0302bab81295abfd7cacf248de62d3c63482c5ea8ab6b25cdbebc83eae855c1d07a8cf0408c2b721e43c4ac53262bf9aaf7a
	#p 去 0 的剩余位

	e = 65537
	pbits = 1024
	kbits = pbits - p4.nbits()
	print(p4.nbits())
	p4 = p4 << kbits
	PR.<x> = PolynomialRing(Zmod(n))
	f = x + p4
	roots = f.small_roots(X=2^kbits, beta=0.4)
	#经过以上一些函数处理后，n 和 p 已经被转化为 10 进制
	if roots:
	p = p4+int(roots[0])
	print("n: "+str(n))
	print("p: "+str(p))
	print("q: "+str(n//p))



	p=119234372387564173916926418564504307771905987823894721284221707768770334474240277144999791051191061404002537779694672314673997030282474914206610847346023297970473719280866108677835517943804329212840618914863288766846702119011361533150365876285203805100986025166317939702179911918098037294325448226481818486521
	q=139862779248852876780236838155351435339041528333485708458669785004897778564234874018135441729896017420539905517964705602836874055417791439544162777504181482765029478481701166935117795286988835104239238153206137155845327225155932803904032184502243017645538314995056944419185855910939481260886933456330514972109
	e=0x10001
	c=0x3a80caebcee814e74a9d3d81b08b1130bed6edde2c0161799e1116ab837424fbc1a234b9765edfc47a9d634e1868105d4458c9b9a0d399b870adbaa2337ac62940ade08daa8a7492cdedf854d4d3a05705db3651211a1ec623a10bd60596e891ccc7b9364fbf2e306404aa2392f5598694dec0b8f7efc66e94e3f8a6f372d833941a2235ebf2fc77c163abcac274836380045b63cc9904d9b13c0935040eda6462b99dd01e8230fdfe2871124306e7bca5b356d16796351db37ec4e574137c926a4e07a2bfe76b9cbbfa4b5b010d678804df3e2f23b4ec42b8c8433fa4811bf1dc231855bea4225683529fad54a9b539fe824931b4fdafab67034e57338217f
	d=inverse(e,(p-1)*(q-1))
	m=pow(c,d,p*q)
	print(long_to_bytes(m))

	#b'0c134c83b74f'

第三段

$M=2022*m*1011*p$

p=gcd(M,n)

	c=0x1bd2a47a5d275ba6356e1e2bd10d6c870693be540e9318c746e807a7672f3a75cc63841170126d7dba52d7f6f9cf0f8dce9705fc1785cc670b2658b05d4b24d8918f95594844bfa920c8ffe73160c2c313b3fdbc4541ec19828165e34afa7d05271cc6fd59d08138b88c11677e6ac3b39cff525dcb19694b0388d895f53805a5e5bd8cfb947080e4855aaf83ebd85a397526f7d76d26031386900cb44a2e4bd121412bcee7a6c1e9af411e234f130e68a428596265d3ec647e50f65cb81393f4bd38389a2b9010fd715582506b9054dc235aced50757462b77a5606f116853af0c1ea3c7cf0d304f885d86081f8bac8b67b0625122f75448c5b6eb8f1cc8a0df
	n=0xc2b17c86a8950f6dafe0a633890e4271cfb20c5ffda2d6b3d035afa655ed05ec16c67b18832ed887f2cea83056af079cc75c2ce43c90cce3ed02c2e07d256f240344f1734adeee6dc2b3b4bbf6dcfc68518d0a74e3e66f1865db95ef4204457e6471903c2321ac97f3b8e3d8d935896e9fc9145a30a3e24e7c320490a9944c1e94d301c8388445532699e6189f4aa6a86f67f1d9b8fb0de4225e005bd27594cd33e36622b2cd8eb2781f0c24d33267d9f29309158942b681aab81f39d1b4a73bd17431b46a89a0e4c2c58b1e24e850355c63b72392600d3fff7a16f6ef80ea515709da3ef1d28782882b0dd2f76bf609590db31979c5d1fd03f75d9d8f1c5069
	e=0x10001
	p=gcd(n,c)
	q=n//p
	d=inverse(e,(p-1)*(q-1))
	print(long_to_bytes(pow(c,d,n)//2022//p//1011))

	#b'977260aae9b5}'

# babyrsa

# easy_rsa

BUU刷题

ECC刷题