# 虎符杯

# RRSSAA

	from Crypto.Util.number import getPrime, inverse, GCD, bytes_to_long
	from random import randint
	from secret import hint, flag


	def seq(r, k):
	v = [r, 2]
	for i in range(1, k):
	v = [r * v[0] - v[1], v[0]]
	ret = v[0] if k != 0 else v[1]
	return ret


	def encrypt(m, e, n):
	while True:
	r = randint(1, n - 1)
	if r != 2 and r != n - 2 and GCD(r, n) == 1:
	break
	v = seq(r, e)
	print(r)
	return ((1 + m * n) * v) % n ** 2


	def go(beta, msg):
	nbits = 1024
	delta = 0.63

	p = getPrime(nbits // 2)
	q = next_prime(p + (1 << int(nbits * beta)))
	n = p * q
	phi = (p ** 2 - 1) * (q ** 2 - 1)

	while True:
	d = getPrime(int(nbits * delta))
	if GCD(d, phi) == 1:
	e = inverse(d, phi)
	if GCD(e, phi) == 1:
	break

	m = bytes_to_long(msg)
	c = int(encrypt(m, e, n))

	print(f"n = {n}")
	print(f"e = {e}")
	print(f"c = {c}")


	go(0.33, hint)
	go(0.44, flag)

	'''
	n = 122774778628333786198247673730199699244621671207929503475974934116435291656353398717362903500544713183492877018211738292001516168567879903073296829793548881467270228989482723510323780292947403861546283099122868428902480999485625751961457245487615479377459707992802193391975415447673215862245349068018710525679
	e = 7105408692393780974425936359246908629062633111464343215149184058052422839553782885999575538955213539904607968494147112651103116202742324255190616790664935322773999797774246994193641076154786429287567308416036562198486649223818741008968261111017589015617705905631979526370180766874051731174064076871339400470062519500450745667838729104568633808272577378699913068193645578675484681151593983853443489561431176000585296710615726640355782811266099023653898050647891425956485791437516020367967793814415345332943552405865306305448753989707540163585481006631816856260061985275944250758886027672221219132999488907097750048011
	c = 2593129589804979134490367446026701647048897831627696427897506570257238733858989741279626614121210703780002736667183915826429635213867589464112850355422817678245007337553349507744893376944140333333044928907283949731124795240808354521353751152149301719465724014407412256933045835977081658410026081895650068864922666975525001601181989114436054060461228877148361720945120260382962899756912493868467226822547185396096960560068874538680230073168773182775945272726468512949751672553541335307512429217493003429882831235199830121519272447634533018024087697385363918421438799206577619692685090186486444886371979602617584956259
	n = 59969098213446598961510550233718258878862148298191323654672950330070587404726715299685997489142290693126366408044603303463518341243526241117556011994804902686998166238333549719269703453450958140262475942580009981324936992976252832887660977703209225426388975233018602730303262439218292062822981478737257836581
	e = 970698965238639683403205181589498135440069660016843488485401994654202837058754446853559143754852628922125327583411039117445415303888796067576548626904070971514824878024057391507617988385537930417136322298476467215300995795105008488692961624917433064070351961856959734368784774555385603000155569897078026670993484466622344106374637350023474339105113172687604783395923403613555236693496567851779400707953027457705617050061193750124237055690801725151098972239120476113241310088089420901051617493693842562637896252448161948655455277146925913049354086353328749354876619287042077221173795354616472050669799421983520421287
	c = 2757297249371055260112176788534868300821961060153993508569437878576838431569949051806118959108641317578931985550844206475198216543139472405873345269094341570473142756599117266569746703013099627523306340748466413993624965897996985230542275127290795414763432332819334757831671028121489964563214463689614865416498886490980692515184662350519034273510244222407505570929178897273048405431658365659592815446583970229985655015539079874797518564867199632672678818617933927005198847206019475149998468493858071672920824599672525667187482558622701227716212254925837398813278836428805193481064316937182435285668656233017810444672
	'''

$p1*(p1+1<<nbits*0.33+x)=n2$

nextprime x 不大于 1500

所以可以直接爆破

	x=1<<1024*0.33
	for i in range(1500):
	y=iroot((x+i)*2+4n,2)#(x+i)^2+4(x+i)*p+4p^2
	while(y[1]):
	print(i)
	print(y[0])
	break
	p=(y-x-i)//2
	q=n//p
	#print(p*q==n)

分解完之后就没有然后了。。。

要求 m 就要求 v

然后我们看这个函数

	def seq(r, k):
	v = [r, 2]
	for i in range(1, k):
	v = [r * v[0] - v[1], v[0]]
	ret = v[0] if k != 0 else v[1]
	return ret

$f(n)=r*f(n-1)-f(n-2)$

那不就是求通项嘛

然后翻看 la 佬博客看到了矩阵快速幂但是不会用啊 die

学习一下. 矩阵快速幂

于是这个 seq 函数又可以写成

	def seq(r,k):
	A=matrix(Zmod(n*n),[r,-1][1,0])
	x=matrix(Zmod(n*n),[2],[r])
	return int((A*kx)[0,0])

我们可以发现转为矩阵后

seq(seq(r,e),e^{-1})=r\quad mod\quad n^

而

$v=c\quad mod\quad n$

所以

$r=seq(c,d)\quad mod \quad n$
代码

	from Crypto.Util.number import inverse, long_to_bytes

	p = 7743971733771153102128801312798743998017713722732925283466018690899116898707556486947918196848489007935614742583856884731087798825462330340492923214926391
	q = 7743971733771153105036156209981171560215008954284943420880584133648389139833517283670475349302080701240378945438911146974137885250527042074631329729385091
	n = p * q
	MOD = n * n
	phi = (p*2 - 1) (q**2 - 1)


	def seq(r, k):
	A = matrix(Zmod(MOD), [[r, -1], [1, 0]])
	x = matrix(Zmod(MOD), [[2], [r]])
	return int((A*k x)[0, 0])


	def L(x):
	return (x % MOD - 1) // n


	e = 970698965238639683403205181589498135440069660016843488485401994654202837058754446853559143754852628922125327583411039117445415303888796067576548626904070971514824878024057391507617988385537930417136322298476467215300995795105008488692961624917433064070351961856959734368784774555385603000155569897078026670993484466622344106374637350023474339105113172687604783395923403613555236693496567851779400707953027457705617050061193750124237055690801725151098972239120476113241310088089420901051617493693842562637896252448161948655455277146925913049354086353328749354876619287042077221173795354616472050669799421983520421287
	c = 2757297249371055260112176788534868300821961060153993508569437878576838431569949051806118959108641317578931985550844206475198216543139472405873345269094341570473142756599117266569746703013099627523306340748466413993624965897996985230542275127290795414763432332819334757831671028121489964563214463689614865416498886490980692515184662350519034273510244222407505570929178897273048405431658365659592815446583970229985655015539079874797518564867199632672678818617933927005198847206019475149998468493858071672920824599672525667187482558622701227716212254925837398813278836428805193481064316937182435285668656233017810444672

	d = inverse(e, phi)
	r = seq(c, d) % n
	v = seq(r, e)
	print(long_to_bytes(L(c * inverse(v, MOD))))

# 虎符杯

# RRSSAA

d^3ctf

文件上传