# Crypto

# crypto091

# Problem

小 A 鼓起勇气向女神索要电话号码，但女神一定要考考他。女神说她最近刚看了一篇发表于安全顶会 USENIX Security 2021 的论文，论文发现苹果 AirDrop 隔空投送功能的漏洞，该漏洞可以向陌生人泄露 AirDrop 发起者或接收者的电话号码和电子邮箱。小 A 经过一番努力，获得了女神手机在 AirDrop 时传输的手机号哈希值，但再往下就不会了，你能继续帮助他吗？小 A 只记得女神手机号是 170 号段首批放号的联通号码。

Hash： c22a563acc2a587afbfaaaa6d67bc6e628872b00bd7e998873881f7c6fdc62fc

flag 格式：flag

# Solve

根据题目，在网上找到了 AirDrop 的哈希方式为 SHA256 ，并且号码开头是 $170$ ，号码是联通的，号码开头为 $1709$ ，并且是 $13$ 位号码，包含国家代码，中国的代码是 $86$ ，因此可以确定前 $6$ 个号码为 $861709$ ，剩下 $7$ 位直接爆破即可。

	from hashlib import sha256

	phone='861709'
	t='c22a563acc2a587afbfaaaa6d67bc6e628872b00bd7e998873881f7c6fdc62fc'
	ch=['0','1','2','3','4','5','6','7','8','9']
	n=[0,0,0,0,0]
	def dfs(dep,num):
	if dep==14:
	if(sha256(num.encode()).hexdigest()==t):
	print(num)
	return True
	else:
	return False
	for i in range(0,10):
	if dfs(dep+1,num+ch[i]):
	return True;
	return False

	dfs(6,phone)

flag{8617091733716}

# crypto405

# Problem

	from Crypto.Util.number import *
	from random import randrange
	from grassfield import flag

	p = getPrime(16)

	k = [randrange(1,p) for i in range(5)]

	for i in range(len(flag)):
	grasshopper = flag[i]
	for j in range(5):
	k[j] = grasshopper = grasshopper * k[j] % p
	print('Grasshopper#'+str(i).zfill(2)+':'+hex(grasshopper)[2:].zfill(4))

# Solve

假设第 $i$ 组的 $k$ 记作 $k_i$ ，那么可以得到

$grasshopper_i=flag_i\cdot k_{i-1,0}\cdot k_{i-1,1}\cdot k_{i-1,2}\cdot k_{i-1,3}\cdot k_{i-1,4}\mod{p}$

并且

$k_{i,n}=flag_i\cdot\prod_{j=0}^nk_{i-1,j}\mod{p}$

显然我们需要知道初始的 $5$ 个 $k_0$ 才可以往后计算，那么就需要 $5$ 个方程，而我们知道 flag 一定包含 flag{ 这 $5$ 个字符，所以就用这 $5$ 个字符计算得到的 grasshopper 来计算初始的 $k_0$

	flag=b'flag{'
	var('k0 k1 k2 k3 k4')
	k=[k0,k1,k2,k3,k4]
	equ=[]
	for i in flag:
	g=i
	for j in range(5):
	k[j]=g=g*k[j]
	equ.append(g)
	for i in equ:
	print(i)

得到 $5$ 个非线性方程

	102k0k1k2k3*k4
	1192407267456k0^5k1^4k2^3k3^2*k4
	1918196473060530916599580974905403195260928k0^15k1^10k2^6k3^3*k4
	56112321905504104058889432264614118677688107359359075763851172322711550767834986156510191423865157053692191440896k0^35k1^20k2^10k3^4*k4
	53396244662367707127856864007524389027579357260572582679744127850279999404450619312604004485139827409110793046460181646479623909080635340073160838110289140978788817626824929446784411034165296270303004366240008622426141394072733814130556872463873302593536k0^70k1^35k2^15k3^5*k4

但这不好解，我们还没考虑模数 $p$ ，所以换一种思路，以下均在模 $p$ 意义下

$k_{i,5}=data_i\\ k_{i,4}k_{i-1,5}=data_i\\ k_{i,3}k_{i-1,4}k_{i-1,5}=data_i\\ k_{i,2}k_{i-1,3}k_{i-1,4}k_{i-1,5}=data_i\\ k_{i,1}k_{i-1,2}k_{i-1,3}k_{i-1,4}k_{i-1,5}=data_i$

一开始我们可以知道所有 $k_{i,5}$ ， $k_{i,4}=k_{i-1,5}^{-1}data_i$ 也可以知道，同理 $k_{i,3},k_{i,2},k_{i,1}$ 也知道

然后flag_i=data_i(k_{i-1,1}k_{i-1,2}k_{i-1,3}k_{i-1,4}k_{i-1,5})^

发现 $p$ 最多只有 $16$ 位 (二进制下)，所以考虑爆破 $p$ 的值，然后求出每一个 $flag_i$ ，只需要判断最后一个符号是否是 } 即可

	from Crypto.Util.number import *
	from random import randrange
	import gmpy2

	data=[0x2066,0xa222,0xcbb1,0xdbb4,0xdeb4,0xb1c5,0x33a4,0xc051,0x3b79,0x6bf8,0x2131,0x2c40,0x91ba,0x7b44,0x5f25,0x0208,0x7edb,0x62b5,0xcec5,0x5ab3,0x3c46,0xc272,0x714b,0x9e0b,0x48ee,0x44cc,0x05a0,0x3da3,0x11b1,0x259f,0x899d,0xa130,0xe58f,0x23f3,0x5829,0x6beb,0x3681,0x0054,0xa189,0x2765,0xc63d,0xbc68]


	mx=max(data)

	k=[ 0 for i in range(250)]
	primes_db=[]
	for i in range(mx,pow(2,17)):
	if gmpy2.is_prime(i):
	primes_db.append(i)

	def decrypt(p):
	for i in range(0,42):
	k[i*5+5]=data[i]
	for i in range(1,42):
	k[i5+4]=data[i]gmpy2.invert(k[(i-1)*5+5],p)%p
	for i in range(2,42):
	k[i5+3]=data[i]gmpy2.invert(k[(i-1)5+5]k[(i-1)*5+4],p)%p
	for i in range(3,42):
	k[i5+2]=data[i]gmpy2.invert(k[(i-1)5+5]k[(i-1)5+4]k[(i-1)*5+3],p)%p
	for i in range(4,42):
	k[i5+1]=data[i]gmpy2.invert(k[(i-1)5+5]k[(i-1)5+4]k[(i-1)5+3]k[(i-1)*5+2],p)%p


	for p in primes_db:
	decrypt(p)
	for i in range(5,42):
	x=data[i]gmpy2.invert(k[(i-1)5+5]k[(i-1)5+4]k[(i-1)5+3]k[(i-1)5+2]k[(i-1)5+1],p)%p
	if x== ord('}'):
	flag='flag{'
	for i in range(5,42):
	x=data[i]gmpy2.invert(k[(i-1)5+5]k[(i-1)5+4]k[(i-1)5+3]k[(i-1)5+2]k[(i-1)5+1],p)%p
	flag+=chr(x)
	print(flag)

# crypto162

# Problem

	from secret import flag
	from hashlib import md5,sha256
	from Crypto.Cipher import AES
	cof_t = [[353, -1162, 32767], [206, -8021, 42110], [262, -7088, 31882], [388, -6394, 21225], [295, -9469, 44468], [749, -3501, 40559], [528, -2690, 10210], [354, -5383, 18437], [491, -8467, 26892], [932, -6984, 20447], [731, -6281, 11340], [420, -5392, 44071], [685, -6555, 40938], [408, -8070, 47959], [182, -9857, 49477], [593, -3584, 49243], [929, -7410, 31929], [970, -4549, 17160], [141, -2435, 36408], [344, -3814, 18949], [291, -7457, 40587], [765, -7011, 32097], [700, -8534, 18013], [267, -2541, 33488], [249, -8934, 12321], [589, -9617, 41998], [840, -1166, 22814], [947, -5660, 41003], [206, -7195, 46261], [784, -9270, 28410], [338, -3690, 19608], [559, -2078, 44397], [534, -3438, 47830], [515, -2139, 39546], [603, -6460, 49953], [234, -6824, 12579], [805, -8793, 36465], [245, -5886, 21077], [190, -7658, 20396], [392, -7053, 19739], [609, -5399, 39959], [479, -8172, 45734], [321, -7102, 41224], [720, -4487, 11055], [208, -1897, 15237], [890, -4427, 35168], [513, -5106, 45849], [666, -1137, 23725], [755, -6732, 39995], [589, -6421, 43716], [866, -3265, 30017], [416, -6540, 34979], [840, -1305, 18242], [731, -6844, 13781], [561, -2728, 10298], [863, -5953, 23132], [204, -4208, 27492], [158, -8701, 12720], [802, -4740, 16628], [491, -6874, 29057], [531, -4829, 29205], [363, -4775, 41711], [319, -9206, 46164], [317, -9270, 18290], [680, -5136, 12009], [880, -2940, 34900], [162, -2587, 49881], [997, -5265, 20890], [485, -9395, 23048], [867, -1652, 18926], [691, -7844, 11180], [355, -5990, 13172], [923, -2018, 23110], [214, -4719, 23005], [921, -9528, 29351], [349, -7957, 20161], [470, -1889, 46170], [244, -6106, 23879], [419, -5440, 43576], [930, -1123, 29859], [151, -5759, 23405], [843, -6770, 36558], [574, -6171, 33778], [772, -1073, 44718], [932, -4037, 40088], [848, -5813, 27304], [194, -6016, 39770], [966, -6789, 14217], [219, -6849, 40922], [352, -6046, 18558], [794, -8254, 29748], [618, -5887, 15535], [202, -9288, 26590], [611, -4341, 46682], [155, -7909, 16654], [935, -5739, 39342], [998, -6538, 24363], [125, -5679, 36725], [507, -7074, 15475], [699, -5836, 47549]]



	def cal(i,cof):
	if i <3:
	return i+1
	else:
	return cof[2]cal(i-3,cof)+cof[1]cal(i-2,cof)+cof[0]*cal(i-1,cof)


	s = 0
	for i in range(100):
	s+= cal(200000,cof_t[i])


	s=str(s)[-2000:-1000]
	key = md5(s).hexdigest().decode('hex')
	check = sha256(key).hexdigest()
	verify = '2cf44ec396e3bb9ed0f2f3bdbe4fab6325ae9d9ec3107881308156069452a6d5'
	assert(check == verify)
	aes = AES.new(key,AES.MODE_ECB)
	data = flag + (16-len(flag)%16)*"\x00"
	print (aes.encrypt(data).encode('hex'))
	#4f12b3a3eadc4146386f4732266f02bd03114a404ba4cb2dabae213ecec451c9d52c70dc3d25154b5af8a304afafed87

# Solve

分析题目， 4f12b3a3eadc4146386f4732266f02bd03114a404ba4cb2dabae213ecec451c9d52c70dc3d25154b5af8a304afafed87 就是 flag 的 AES 加密，解密需要密钥 key ，而 key 是有一系列计算得到的 s 的 MD5 哈希得到的，所以最终是要求 s

根据题目很容易得到对于每一个数列 $cof[i]$ ，需要计算这样的递推式

$f_0=1,f_1=2,f_2=3\\ f_n=f_{n-3}\cdot cof[i][2]+f_{n-2}\cdot cof[i][1]+f_{n-1}\cdot cof[i][0]$

我们需要计算 $f_{200000}$ ，用递推来求是可以，但时间复杂度到达了 $10^7$ ，而 python 速度很慢，而这种线性递推的方式，常用的计算方法有两种：一是利用级数求出通项公式，二是利用矩阵快速幂 (类比斐波那契数列)。而在我本机上暴力跑跑不出来，而通项公式在手算之后发现很复杂，求出级数的函数表达式后，不容易再用级数表示，所以用矩阵快速幂，这里利用 Sage 来计算，什么都封装好了，比较容易实现

而根据常见套路 (学过 OI 的应该知道)

$\left[ \begin{matrix} f_n & f_{n-1} & f_{n-2}\\ \end{matrix} \right]= \left[ \begin{matrix} f_{n-1} & f_{n-2} & f_{n-3}\\ \end{matrix} \right] \left[ \begin{matrix} cof[i][0] & 1 & 0\\ cof[i][1] & 0 & 1 \\ cof[i][2] & 0 & 0 \end{matrix} \right]$

	cof_t = [[353, -1162, 32767], [206, -8021, 42110], [262, -7088, 31882], [388, -6394, 21225], [295, -9469, 44468], [749, -3501, 40559], [528, -2690, 10210], [354, -5383, 18437], [491, -8467, 26892], [932, -6984, 20447], [731, -6281, 11340], [420, -5392, 44071], [685, -6555, 40938], [408, -8070, 47959], [182, -9857, 49477], [593, -3584, 49243], [929, -7410, 31929], [970, -4549, 17160], [141, -2435, 36408], [344, -3814, 18949], [291, -7457, 40587], [765, -7011, 32097], [700, -8534, 18013], [267, -2541, 33488], [249, -8934, 12321], [589, -9617, 41998], [840, -1166, 22814], [947, -5660, 41003], [206, -7195, 46261], [784, -9270, 28410], [338, -3690, 19608], [559, -2078, 44397], [534, -3438, 47830], [515, -2139, 39546], [603, -6460, 49953], [234, -6824, 12579], [805, -8793, 36465], [245, -5886, 21077], [190, -7658, 20396], [392, -7053, 19739], [609, -5399, 39959], [479, -8172, 45734], [321, -7102, 41224], [720, -4487, 11055], [208, -1897, 15237], [890, -4427, 35168], [513, -5106, 45849], [666, -1137, 23725], [755, -6732, 39995], [589, -6421, 43716], [866, -3265, 30017], [416, -6540, 34979], [840, -1305, 18242], [731, -6844, 13781], [561, -2728, 10298], [863, -5953, 23132], [204, -4208, 27492], [158, -8701, 12720], [802, -4740, 16628], [491, -6874, 29057], [531, -4829, 29205], [363, -4775, 41711], [319, -9206, 46164], [317, -9270, 18290], [680, -5136, 12009], [880, -2940, 34900], [162, -2587, 49881], [997, -5265, 20890], [485, -9395, 23048], [867, -1652, 18926], [691, -7844, 11180], [355, -5990, 13172], [923, -2018, 23110], [214, -4719, 23005], [921, -9528, 29351], [349, -7957, 20161], [470, -1889, 46170], [244, -6106, 23879], [419, -5440, 43576], [930, -1123, 29859], [151, -5759, 23405], [843, -6770, 36558], [574, -6171, 33778], [772, -1073, 44718], [932, -4037, 40088], [848, -5813, 27304], [194, -6016, 39770], [966, -6789, 14217], [219, -6849, 40922], [352, -6046, 18558], [794, -8254, 29748], [618, -5887, 15535], [202, -9288, 26590], [611, -4341, 46682], [155, -7909, 16654], [935, -5739, 39342], [998, -6538, 24363], [125, -5679, 36725], [507, -7074, 15475], [699, -5836, 47549]]

	s=0
	for i in range(100):
	M=Matrix(ZZ,[[cof_t[i][0],1,0],[cof_t[i][1],0,1],[cof_t[i][2],0,0]])
	f=Matrix(ZZ,[3,2,1])
	f=f*(M^(200000-2))
	s+=int(f[0,0])
	s=str(s)
	print(s)

得到 s 之后就是抄代码解密即可

	s=str(s)[-2000:-1000]
	key = bytes.fromhex(md5(s.encode()).hexdigest())
	check = sha256(key).hexdigest()
	verify = '2cf44ec396e3bb9ed0f2f3bdbe4fab6325ae9d9ec3107881308156069452a6d5'

	aes = AES.new(key,AES.MODE_ECB)
	c='4f12b3a3eadc4146386f4732266f02bd03114a404ba4cb2dabae213ecec451c9d52c70dc3d25154b5af8a304afafed87'
	c=bytes.fromhex(c)
	print(aes.decrypt(c))

注意由于 python3 没有 decode('hex') ，所以用 bytes_fromhex 函数

flag{519427b3-d104-4c34-a29d-5a7c128031ff}

# Reverse

# re694

给了一个 64 位的 exe 文件并且加了壳，一开始用脱壳软件一直脱不掉，后来手动脱壳，虽然似乎成功了，但可读性有点差。拉近 010editor 一看，发现 UPX 被改成了 FUK ，怪不得无法脱壳，直接改回来导出文件再脱壳即可。积累一个阻止脱壳的小方法.

# re693

challenge 文件是一个二进制文件，用 010 打开，发现是 go 文件， go 语言爱好者狂喜。这这题实事上是一个查找题

根据题目，先把主函数和相关函数复制下来运行，有 $2$ 句话

Input the first function, which has 6 parameters and the third named gLIhR: 
Input the second function, which has 3 callers and invokes the function named cHZv5op8rOmlAkb6:

对应两个输入，第一个要求输入一个这个 go 文件里面的函数名，满足有 $6$ 个参数并且第 $3$ 个参数名是 gLIhR ；第二个输入的函数名要求调用函数 cHZv5op8rOmlAkb6 并且被有 $3$ 个函数调用它。

直接在 010editor 里面慢慢找就好了，过程很折磨

第一个符合的函数是 ZlXDJkH3OZN4Mayd ，第二个符合的函数是 UhnCm82SDGE0zLYO ，然后把相关函数复制下来运行即可。

不过要注意 flag 的第一部分只是把第一个函数名传递给另一个函数得到的，而不是调用第一个函数，第二部分才是调用第二个函数得到的

	package main

	import (
	"encoding/hex"
	"fmt"
	)
	type dIWKr func() string
	func MPyt9GWTRfAFNvb1(gfqOc []byte) string {
	mYxFI := make([]byte, 80)
	spVwk := [78]byte{
	108, 39, 231, 242, 53, 26, 133, 50, 68, 118, 33, 64, 20, 130, 161, 202, 37, 229, 229, 119, 4, 255, 70, 105, 178, 219, 208, 145, 113, 226, 32, 96, 59, 239, 213, 204, 117, 50, 163, 5, 41, 71, 62, 246, 92, 43, 157, 2, 200, 50, 141, 75, 224, 151, 46, 194, 233, 141, 244, 12, 170, 251, 84, 188, 249, 135, 67, 245, 230, 93, 84, 254, 32, 221, 178, 202, 252}

	for i := 0; i < 77; i++ {
	mYxFI[i] = spVwk[i] ^ gfqOc[i]
	}

	return string(mYxFI)
	}
	func kZ2BFvOxepd5ALDR(Gm7TC []byte) string {
	Z1anw := make([]byte, 100)
	jutvH := [98]byte{
	246, 226, 2, 128, 250, 23, 202, 118, 196, 50, 187, 98, 118, 84, 127, 72, 2, 211, 24, 26, 241, 229, 212, 43, 224, 93, 32, 86, 70, 209, 118, 73, 98, 11, 29, 212, 233, 107, 165, 119, 178, 47, 233, 159, 76, 111, 170, 132, 7, 2, 93, 21, 190, 194, 93, 249, 38, 84, 23, 132, 135, 174, 198, 232, 97, 52, 174, 111, 233, 231, 249, 172, 176, 61, 245, 100, 186, 170, 157, 190, 133, 150, 217, 78, 76, 146, 207, 2, 17, 36, 198, 69, 137, 39, 26, 60, 255}

	for i := 0; i < 97; i++ {
	Z1anw[i] = jutvH[i] ^ Gm7TC[i]
	}

	return string(Z1anw)
	}
	func GwSqNHQ7dPXpIG64(cJPTR string) string {
	YrXQd := hex.EncodeToString([]byte(cJPTR))
	return fmt.Sprintf("%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c", YrXQd[22], YrXQd[19], YrXQd[20], YrXQd[21], YrXQd[28], YrXQd[10], YrXQd[20], YrXQd[7], YrXQd[29], YrXQd[14], YrXQd[0], YrXQd[18], YrXQd[3], YrXQd[24], YrXQd[27], YrXQd[31])
	}


	func ZlXDJkH3OZN4Mayd(swlvV []byte, S5aOL string, gLIhR string, QIErK string, mxqoA string, hTBet string) string {
	eBS9X := make([]byte, 20)
	WX5YT := [16]byte{
	169, 43, 100, 115, 202, 185, 130, 174, 238, 233, 147, 43, 149, 7, 229, 119}
	for i := 0; i < 16; i++ {
	eBS9X[i] += WX5YT[i] ^ swlvV[i]
	}

	return string(eBS9X)
	}

	func cHZv5op8rOmlAkb6(HIGXt []byte, VGvny string, ZOkKV string, eU0uD string) string {
	QTk4l := make([]byte, 20)
	Ek08m := [16]byte{
	167, 238, 45, 89, 160, 95, 34, 175, 158, 169, 20, 217, 68, 137, 231, 54}
	for i := 0; i < 16; i++ {
	QTk4l[i] += Ek08m[i] ^ HIGXt[i]
	}
	return string(QTk4l)
	}
	func UhnCm82SDGE0zLYO() string {
	SythK := []byte{
	159, 141, 72, 106, 196, 62, 16, 205, 170, 159, 36, 232, 125, 239, 208, 3}
	var Vw2mJ, Nij87, zVclR string
	return cHZv5op8rOmlAkb6(SythK, Vw2mJ, Nij87, zVclR)
	}

	func main() {
	jjxXf := []byte{
	37, 73, 151, 135, 65, 58, 241, 90, 33, 86, 71, 41, 102, 241, 213, 234, 67, 144, 139, 20, 112, 150, 41, 7, 158, 251, 167, 249, 24, 129, 72, 64, 83, 142, 166, 236, 67, 18, 211, 100, 91, 38, 83, 147, 40, 78, 239, 113, 232, 83, 227, 47, 192, 227, 70, 167, 201, 249, 156, 101, 216, 159, 116, 210, 152, 234, 38, 145, 198, 58, 24, 183, 72, 143, 136, 234, 246}
	KdlaH := []byte{
	191, 140, 114, 245, 142, 55, 190, 30, 161, 18, 200, 7, 21, 59, 17, 44, 34, 181, 109, 116, 146, 145, 189, 68, 142, 113, 0, 33, 46, 184, 21, 33, 66, 99, 124, 167, 201, 88, 133, 20, 211, 67, 133, 250, 62, 28, 138, 229, 105, 102, 125, 124, 208, 180, 50, 146, 67, 39, 55, 240, 239, 203, 230, 142, 20, 90, 205, 27, 128, 136, 151, 140, 222, 92, 152, 1, 222, 138, 254, 246, 223, 224, 236, 33, 60, 170, 189, 77, 124, 72, 135, 46, 235, 17, 32, 28, 245}
	fmt.Print(MPyt9GWTRfAFNvb1(jjxXf))
	//fmt.Scanf("%20s", &nFAzj)
	fmt.Print(kZ2BFvOxepd5ALDR(KdlaH))
	//fmt.Scanf("%20s", &CuSkl)
	/*
	vNvUO := GwSqNHQ7dPXpIG64(nFAzj)
	YJCya := ""
	mvOxK := YI3z8ZxOKhfLmTPC(CuSkl)
	if mvOxK != nil {
	YJCya = mvOxK()
	}

	if YJCya != "" && vNvUO != "" {
	fmt.Printf("flag

	102k0k1k2k3*k4
	1192407267456k0^5k1^4k2^3k3^2*k4
	1918196473060530916599580974905403195260928k0^15k1^10k2^6k3^3*k4
	56112321905504104058889432264614118677688107359359075763851172322711550767834986156510191423865157053692191440896k0^35k1^20k2^10k3^4*k4
	53396244662367707127856864007524389027579357260572582679744127850279999404450619312604004485139827409110793046460181646479623909080635340073160838110289140978788817626824929446784411034165296270303004366240008622426141394072733814130556872463873302593536k0^70k1^35k2^15k3^5*k4

# Crypto

# crypto091

# Problem

# Solve

# crypto405

# Problem

# Solve

# crypto162

# Problem

# Solve

# Reverse

# re694

# re693

长城杯Crypto

i春秋勇者之巅Crypto学习