↓跳过正文
1n1t-Flare Blog
  1. Writeups/

0xGame2023 Crypto

·1338 字·7 分钟·
CTF Crypto
目录

Week1
#

What’s CBC?
#

查询资料知CBC是一种分组加密算法。把明文分为等长的几组，用初始化向量对第一组明文进行xor运算，再进行另一种加密得到第一组密文。接下来用第一组密文作为向量加密第二组明文……依次类推。

注意到xor运算(⊕)的特殊性质： $$ A⊕0=A $$

$$ A⊕A=0 $$

如果两数xor后，对结果再xor这两个数中的一个，可以得到其中另一个数。 $$ (A⊕B)⊕B=A⊕(B⊕B)=A⊕0=A $$ 这样一来，解密就方便很多。但是最后的加密函数encrypt()中出现了未知的密钥key，所以首先要解出key。

image-20231007230516072

从 i ^ key 推测key是一个数而非bytes类型，而且对每一个i都进行了异或运算，理论上只要知道一个i就可以反推出来 (i ^ key ^i) 。我们已知flag的前七位是标准的 '0xGame{' 格式，题中每组明文或密文均为八位，于是再随便补一个字母凑成第一组明文，与iv异或后推key。

from Crypto.Util.number import *

f=b'0xGame{a'
iv = b'11111111'
enc=b"\x8e\xc6\xf9\xdf\xd3\xdb\xc5\x8e8q\x10f>7.5\x81\xcc\xae\x8d\x82\x8f\x92\xd9o'D6h8.d\xd6\x9a\xfc\xdb\xd3\xd1\x97\x96Q\x1d{\\TV\x10\x11"

def bytes_xor(a,b):
	a,b=bytes_to_long(a),bytes_to_long(b)
	return long_to_bytes(a^b)

k=bytes_xor(f,iv)   

for i in range(8):
  key=enc[i]^k[i]
  print(key)
    
'''
143
143
143
143
143
143
143
222
'''

忽略掉最后随便找的那个字母(222那个)，能得到key=143。利用xor的性质写出decrypt, Decrypt_CbC两个解密函数(与题目中的两个加密函数相对应，甚至几乎一样)，代入数据解出flag。

image-20231007201315198

from Crypto.Util.number import *

def bytes_xor(a,b):
	a,b=bytes_to_long(a),bytes_to_long(b)
	return long_to_bytes(a^b)

def decrypt(enc,key):
    result=b''
    for i in enc:
    	result += ((i^key)).to_bytes(1,'big')
    return result

def Decrypt_CbC(enc,iv,key):
    result=b''
    block=[enc[k*8:(k+1)*8] for k in range(len(enc)//8)]
    for i in block:
    	text = decrypt(i,key)
    	plain = bytes_xor(iv,text)
		iv=i
    	result += plain
	return result

enc = b"\x8e\xc6\xf9\xdf\xd3\xdb\xc5\x8e8q\x10f>7.5\x81\xcc\xae\x8d\x82\x8f\x92\xd9o'D6h8.d\xd6\x9a\xfc\xdb\xd3\xd1\x97\x96Q\x1d{\\TV\x10\x11"
iv = b'11111111'
key = 143
flag = Decrypt_CbC(enc,iv,key)
print(flag)

密码，觅码，先有*再密
#

把flag切成四份，每份用不同的方法加密。只要判断出每份是如何加密，逐个击破即可。

image-20231006143508458

  • c1：Crypto.Util.number中的bytes_to_long()函数，把bytes转化成整数，用对应的long_to_bytes()解密。但还有个小细节，c1输出时变成自身的5次方，我们需要开五次方根还原c1。这里如果用pow(c1,0.2)会有精度的问题，所以采用gmpy2模块的iroot函数

  • c2：把bytes中每个字节取二进制并连在一起，解密时等距离拆分还原为bytes

  • c3：常见的base64编码，用对应的b64decode()函数

  • c4：十六进制与bytes互化

还有一个要注意的地方是flag内部是汉字，用utf-8解码

image-20231006143439687

from base64 import b64decode
from Crypto.Util.number import*
from gmpy2 import iroot

c1a=2607076237872456265701394408859286660368327415582106508683648834772020887801353062171214554351749058553609022833985773083200356284531601339221590756213276590896143894954053902973407638214851164171968630602313844022016135428560081844499356672695981757804756591891049233334352061975924028218309004551
c2='10010000100001101110100010100111101000111110010010111010100001101110010010111111101000011110011010000001101011111110011010011000101011111110010110100110100000101110010010111101100101011110011110111100'
c3 = b'lueggeeahO+8jOmCo+S5iOW8gOWni+aIkQ=='
c4 = 'e4bbace79a8443727970746fe68c91e68898e590a72121217d'


c1 = iroot(c1a,5)
f1 = long_to_bytes(int(c1[0]))
f = [c2[i*8:(i+1)*8] for i in range(len(c2)//8)]
f2 = ''.join([hex(int('0b'+k,base=0))[2:] for k in f])
f2=bytes.fromhex(f2)
f3 = b64decode(c3)
f4=bytes.fromhex(c4)

flag=(f1+f2+f3+f4).decode('utf-8')
print(flag)

Take my bag!
#

赛后复现补充：背包dp，动态规划，这下真手撕算法了orz

没看出是什么加密，也没找到标准的解密方式，就当成算法题做了。

分析一下我的思路：

image-20231008123925612

题中的加密函数把明文转为二进制并逆序处理，init是给出的一个数表，关键在init[i] * int(m[i]) % n这个表达式。我们知道二进制中只会出现0和1，相应地，表达式也只会出现两种结果：

  1. int(m[i]) = 0，表达式等于0

  2. int(m[i]) = 1，init[i] * int(m[i]) % n = init[i] % n，而init中元素已经对n取过模，不会大于n。故表达式等于init[i]

即密文c是列表init中特定项的和，这些项的索引与得到的逆序二进制数中“1”对应。解密的思路很直接，遍历所有元素并找出和刚好为c的项，就可以反推二进制数，乃至flag。

说起来容易，但程序如果这么实现，时间复杂度还是很高的。对思路重新优化，我们可以先把c视为若干项的和，在init中逐一找到各项并从c中减去。如果这一过程能完全进行那么c会被减到0，此时这些被减去的项就是我们要求的。按这个思路编写脚本，选取 [ c减去init某一项的剩余值，在过程不成立时表示回溯情况的偏移量，被减项的索引 ] 作为关键数据保存在栈（列表memory）中，最后剩余值=0时就可以从栈中得到各所求项的索引。（一开始没发现，后来flag交了之后想起来这有点像深度优先搜索算法?）

接下来按照索引求出二进制数，逆序还原，再转为bytes就看到flag了。

from Crypto.Util.number import *

w=16221818045491479713
n=9702074289348763131102174377899883904548584105641045150269763589431293826913348632496775173099776917930517270317586740686008539085898910110442820776001061
c=4795969289572314590787467990865205548430190921556722879891721107719262822789483863742356553249935437004378475661668768893462652103739250038700528111
init = [w*pow(3, i) % n for i in range(512)]

memory = []             #记录上一次操作时的[剩余值,偏移量,在init中对应的索引位置]

def find(p):			#找到在init中小于给定数p的最大元素索引
	for i in range(512):
    	if init[i]<=p and init[i+1]>p:
        	return i
    	if p==0:
        	return 0

def forward(num,move,index):#保存上一次操作数据，更新偏移量=0，计算剩余值
    datas=[num,move,index]
    memory.append(datas)
    move=0
    return num - init[index-move]

num,move,index=c,0, find(c)#初始化

while True:
    
  	if num==0:
        break

  	elif (num - init[index - move]>= init[0] or num == init[index - move]) and move<=index:
    	num=forward(num,move, index)
    	index=find(num)

  	else:
    	num,move,index=memory[-1]
    	move+=1
    	memory.pop()		#回溯到上一次操作，向左偏移+1

m=['0']*512
for k in memory:
  	m[k[2]]='1'
m=''.join(m)[::-1]

flag=long_to_bytes(int(m,2))
print(flag)

BabyRSA
#

RSA在密码学领域是常见的非对称加密算法，破解的难度在于从公钥推出私钥，核心是超大整数的质因数分解。

image-20231005203125446

在一般的RSA加密中，m表示明文，n是一个超大整数，e为与φ(n)互素的任意整数，(e,n)作为公钥加密明文，得到密文c。解密需要私钥(d,n)，其中d是e关于模φ(n)的乘法逆元。要从密文c中解出明文m，只需要求出n的欧拉函数，为此需要将n质因数分解。

不同于传统的n=p*q这种只有两个质因数，本题的getN()函数直接给出了16个大质数相乘的超大数n，正常的分解因数算法肯定不好使了。在查找资料的过程中发现了名叫yafu的工具，顺利的分解了n。果然是整齐的16个质数

这样一来，就可以利用欧拉函数的性质，把各个因数减一再全部相乘，求出φ(n)，进而得到密钥去解密

image-20231005211459986

image-20231005211552255

还要注意求得的结果是m*mask，要再除以mask并用long_to_bytes()还原为字符串，才能得到正确的flag。

from Crypto.Util.number import *
import gmpy2

n=93099494899964317992000886585964221136368777219322402558083737546844067074234332564205970300159140111778084916162471993849233358306940868232157447540597
e = 65537
c=54352122428332145724828674757308827564883974087400720449151348825082737474080849774814293027988784740602148317713402758353653028988960687525211635107801
mask = 54257528450885974256117108479579183871895740052660152544049844968621224899247

factors=[3479527847,2864469667,3561068417,2770441151,
    	 4134768233,3281340371,3111632101,2821163021,
   		 3978177241,3267547559,2329990801,3162958289,
         2995527113,4160088337,2732757047,2436711469]

phi=1
for p in factors:
  phi *= (p-1)      #欧拉函数

d=gmpy2.invert(e,phi)    #通过乘法逆元找到私钥d
m=pow(c,d,n)        #解密
result=gmpy2.c_div(m,mask)
flag=long_to_bytes(result)
print(flag)

猜谜
#

已知部分明文攻击

题目还蛮善良的，给出加密enc()函数的同时还送上了解密的dec()函数，对密文进行第一次解密如下:

c = b'IPxYIYPYXPAn3nXX3IXA3YIAPn3xAYnYnPIIPAYYIA3nxxInXAYnIPAIxnXYYYIXIIPAXn3XYXIYAA3AXnx='
print(dec(c))
#b'gWM\x84u\xe4N\x05x=a}\xe5\xb2-a}\x9f\x82\xf6C\xde[\\1\x89\xd4\xb1\xd0\x10\x9f'

然而第二层加密就不好办了，又又出现了未知的key。题目的意思是把key猜出来?

image-20231006173512624

分析代码，i%7 这段给了启示。无论len(key)有多大，只有前7位能发挥作用。不妨猜key就是7位的bytes。恰好我们知道flag的前七位是标准格式 '0xGame{' ，再利用xor运算的性质反推key成功。同样用xor解出flag

key=b''
flag=''
flagformat=b'0xGame{'
text=b'gWM\x84u\xe4N\x05X=a}\xe5\xb2-a}\x9f\x82\xf6C\xde[\\l\x89\xd4\xb1\xd0\x10\x9f'

for i in range(7):
  key += (text[i] ^ (flagformat[i]+i)).to_bytes(1,'big')
for j in range(len(text)):
   flag += chr((text[j] ^ key[j%7])-j)

print(flag)

Vigenere
#

完全没见过的加密方式，百度搜索给出的解释是“使用一系列凯撒密码组成密码字母表的加密算法，属于多表密码的一种简单形式”。

直接找在线解密工具，摸索后发现解密需要密钥，而且只会对字母进行改变。查阅资料发现以下要点：

1.明文中的所有字母都在字母表上向后偏移某个数目后被替换成密文，偏移量与密钥相对应。

2.密钥若长度不够可以继续重复。

现在只需要得到密钥就可以破解flag，题目没有给出密钥的任何信息（也可以暴力破解？），但结合密文：0dGmqk{79ap4i0522g0a67m6i196he52357q60f}，猜测0dGmqk与0xGame 相对应，分析各字母前后的偏移量：6，0，12，4，6。对应g,a,m,e,g ,考虑到密钥的可重复性，取game作为密钥（看起来很靠谱），放到网站解密得到flag。

image-20231005175425302

Week2
#

EzLFSR
#

LFSR，又是很陌生的算法。

查了好几天资料，大概理解的差不多了。作为流密码的关键成分，LSFR也就是线性反馈移位寄存器，能够不断输出随机而长周期的序列。由此它可以作为流密钥产生器的线性驱动部分。寄存器的容量有限，当其中的数据整体左(右)移一位时，最左(右)面的数会溢出（输出）而最右(左)面会留出空位。为了有持续的输出，LSFR通过某种线性反馈函数计算出一个数补到空位，依次循环，源源不断。

image-20231014234348483

题中给出了初始状态和256位输出，根据移位寄存器的原理，我们可以用initState[i:]+outputState[:i]来表示第i组状态，同时给出计算补充右边空位数字的方法lfsr()，但其中mask未知。即不完全知道LFSR的反馈函数，但已知其级数n=128。而且明文中不包括0xGame{}，不能取巧反推反馈函数。

注意到反馈函数中有异或运算，state和mask中元素只能取0或1。可以把mask[i]理解为寄存器第i位的数是否参与到异或运算中（抽头）。用 \(x_i\) 表示mask[i]， \(k_i\) 至 \(k_{i+127}\) 表示第i组状态下寄存器各位数字，从数学角度可得到异或方程组： $$ \begin{cases} \quad k_{1}x_1\oplus k_{2}x_2 \oplus\cdots\oplus k_{128}x_{128} = k_{129} \\ \quad k_{2}x_1\oplus k_{3}x_2 \oplus\cdots\oplus k_{129}x_{128} = k_{130} \\ \quad k_{3}x_1\oplus k_{4}x_2 \oplus\cdots\oplus k_{130}x_{128} = k_{131} \\ \quad\quad\quad\quad\quad\quad\quad\enspace\cdots \\ k_{128}x_1\oplus k_{129}x_2 \oplus\cdots\oplus k_{255}x_{128} = k_{256} \\ \end{cases} $$ 由于异或有“半加”的性质，用线性(加法)方程组类比异或方程组，上式等价于： $$ \begin{cases} \quad k_{1}x_1+ k_{2}x_2 +\cdots+ k_{128}x_{128} \equiv k_{129}(\bmod2)\\ \quad k_{2}x_1+ k_{3}x_2 +\cdots+ k_{129}x_{128} \equiv k_{130}(\bmod2)\\ \quad k_{3}x_1+ k_{4}x_2 +\cdots+ k_{130}x_{128} \equiv k_{131}(\bmod2)\\ \quad\quad\quad\quad\quad\quad\quad\enspace\cdots\\ k_{128}x_1+ k_{129}x_2 +\cdots+ k_{255}x_{128} \equiv k_{256}(\bmod2)\\ \end{cases} $$ 矩阵表示为： $$ \begin{bmatrix} k_1 & k_2 & k_3 & \cdots & k_{128}\\ k_2 & k_3 & k_4 & \cdots & k_{129}\\ k_3 & k_4 & k_5 & \cdots & k_{130}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ k_{128} & k_{129} & k_{130} & \cdots & k_{255} \end{bmatrix}X=\begin{bmatrix} k_{129}\\ k_{130}\\ k_{131}\\ \vdots\\ k_{256}\\ \end{bmatrix} $$ 借助软件Sage函数solve_right()，在有限环Zmod(2)中求解矩阵方程得到mask，转换为secret就可以得到flag

#SageMath
from Crypto.Util.number import *

def string2bits(s):
    return [int(b) for b in s]
def bits2string(bs):
    s = [str(b) for b in bs]
    return ''.join(s)

initState = [0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0]
outputState = '1101111111011101100001000011111101001000111000110100010011110111010011100110100100111001101010110110101110000011110101000110010010000011111111001111000110111001100111101110010100100001101001111110001010000100111101011011100010000000100000100000100111010110'
outputState = string2bits(outputState)

States_Array=[initState[i:]+outputState[:i] for i in range(128)]
states=matrix(Zmod(2),States_Array)
output=matrix(Zmod(2),outputState[:128])
output=output.transpose()

mask=states.solve_right(output)
mask=[i[0] for i in (mask)]
secret=bits2string(mask)
secret=long_to_bytes(int(secret,2))

flag = '0xGame{'+secret.decode('utf-8')+'}'
print(flag)

中间的那个人
#

image-20231015123026520

题目模拟了Alice和Bob两人的加密通信场景，二人使用对称加密的CBC算法。因为未事先商量好密钥，所以加密一方要想办法把密文和特殊处理的密钥一并发送给对方，这里涉及DH密钥交换算法。我们作为“中间的那个人”，通过各种方式截获了二人通信的数据如下： $$ P(A)\equiv Alice\equiv g^A (\bmod\ p) $$

$$ P(B)\equiv Bob\equiv g^B(\bmod\ p) $$

$$ key\equiv P(A)^B\equiv P(B)^A\equiv g^{AB}(\bmod\ p) $$

由数学关系我们可反推：\(A\equiv \log_gP(A)\ (\bmod \ p)\) 和\(B\equiv \log_gP(B)\ \ (\bmod \ p)\)。即只需要计算其中一个离散对数，得到A或B的值，就可以计算出密钥key。

借助SageMath计算mod 2下的离散对数：

#SageMath
p=250858685680234165065801734515633434653
G=GF(p)
g=G(2)
Bob=G(33067794433420687511728239091450927373)
B = discrete_log(Bob,g)

再用python计算key，用题中给出的密文和初始化向量 $iv$ 解密，得到flag（其实可以放在Sage里面一步到位，但是我的Sage里面Crypto.Cipher库出了点小问题，就分开写了）

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
g=2
p=    250858685680234165065801734515633434653
Bob=  33067794433420687511728239091450927373
Alice=235866450680721760403251513646370485539
enc=b's\x04\xbc\x8bT6\x846\xd9\xd6\x83 y\xaah\xde@\xc9\x17\xdc\x04v\x18\xef\xcf\xef\xc5\xfd|\x0e\xca\n\xbd#\x94{\x8e[.\xe8\xe1GU\xfa?\xda\x11w'
iv = b"0xGame0xGameGAME"
B = 1620639479

key = pow(Alice,B,p)
key = sha256(long_to_bytes(key)).digest()
aes = AES.new(key, AES.MODE_CBC, iv)
flag = aes.decrypt(enc)
print(flag)

Week3
#

EzECC
#

ECC 即 EllipseCurve Cryptography，是一种基于椭圆曲线的公钥密码。在数学上椭圆曲线用 $$ y^2+axy+by=x^3+cx^2+dx+e $$ 来表示，而密码学中常取\(a=b=c=0\),得到椭圆曲线的一般形式 $$ y^2=x^3+dx+e $$

image-20231021220547269

密码学椭圆曲线一般定义在有限域GF(p)上。定义了二元运算：点与点的加法“ + ”，包括不同点相加以及点的自加（数乘）两种情况，与题中给出的 add() 函数和 mul() 函数相对应。同时，椭圆曲线上所有点（包括无穷远点\(O\)）与“ + ”运算构成abel群，满足封闭性，有限次运算后的结果依然在曲线上。

不同于数学中光滑连续的曲线，GF(p)上的椭圆曲线只包含离散而有限的整数点以及特殊的无穷远点，点的总数称为曲线的阶\(n\) ,若用 \(G\) 表示该曲线的生成元，则满足 \(nG = O\)。

曲线上两点满足 \(Q=mP\) ,则称 \(m\) 为椭圆曲线的离散对数，即 \(m=log_PQ\) 。ECC密码体系建立在离散对数求解难题的基础上。

根据以上性质，我们可以分析ECC的加密过程：首先接受方确定私钥 \(k\) 并选择椭圆曲线E(a,b)上基点 \(G\) ，计算出公钥 \(K=kG\)。将除私钥外的信息公开给发送方。发送方将明文编码成椭圆曲线上一点 \(M\)（但本题并没有这样做），随机选一个整数 \(r\) 计算出密文｛\(M+rK,rG\)｝即题中的 {C_1,C_2}。解密的思路比较直接，注意到数学关系 $$ \begin{cases} C_1=M+rK=M+rkG\\ C_2=rG\\ C_1-kC_2=M+rkG-krG=M \end{cases} $$ 只要求出私钥 \(k=log_GK\) 就可以求出 \(M\)，难题在于求解离散对数，还好SageMath有内置的求解函数。下图是利用discrete_log()函数求出 \(r\) 和 \(k\) 的过程：

image-20231020214551087

另外还有一种思路是求出 \(r=log_GC_2\) ，再根据\(M=C_1-rK\)求出明文，同样关键在离散对数。但从上图不难发现 \(r\) 是一个比较小的数，也可以爆破 \(r\) 来规避这一难题。（好像有师傅是这么做的）

求出 \(k\) 或 \(r\) 离flag就不远了。脚本求解：

from Crypto.Util.number import *
q=1139075593950729137191297
a=930515656721155210883162
b=631258792856205568553568
G = (641322496020493855620384, 437819621961768591577606)
K = (781988559490437792081406, 76709224526706154630278)
C_1=(55568609433135042994738, 626496338010773913984218)
C_2=(508425841918584868754821, 816040882076938893064041)

def add(P,Q):
	if P[0] != Q[0] and P[1] != Q[1]:
		t = ((Q[1]-P[1]) * inverse(Q[0]-P[0],q)) %q
	else:
		t = ((3*P[0]*P[0]+a) * inverse(2*P[1],q))%q

	x3 = t*t - P[0] - Q[0]
	y3 = t*(P[0] - x3) - P[1]
	return (x3%q, y3%q)

def mul(t, A, B=0):
    if not t: return B
    return mul(t//2, add(A,A), B if not t&1 else add(B,A) if B else A)

r=10077
k=12515237792257199894
h=mul(r,K)
H=(h[0],q-h[1])
m1,m2=add(C_1,H)
flag = b'0xGame{' + long_to_bytes(m1)+long_to_bytes(m2) + b'}'
print(flag.decode('utf8'))

LLL-FirstBlood
#

初识LLL一头雾水，找了点格密码的资料看了看。实话说也没有理解透，但是发现题里给的MakeMask()函数很有意思。它会生成一个有限域GF(p)内的n阶方阵，各个位置的元素完全随机，但方阵的行列式恒为1。资料中称这样的矩阵为“幺模矩阵”，同时提到了格的一个性质：对于格的一组基 \(v_1,v_2,\cdots,v_n\) 可以进行如下三种变换，得到新的一组基与原来的基等价。

​ 1.交换若干个基向量的顺序

​ 2.对基向量取负 \(v_i\rightarrow-v_i\)

​ 3.把某一基向量的k倍加到另一基向量上 \(v_i+kv_j\)

如果把基表示成矩阵 \(B_i\) 的形式，其中列向量为基向量，那么以上三种对基的变换可以写成 \(B_iU\) ，这里 \(U\) 为幺模矩阵。

换句话说，我们有基 \(B_1\)，而且 \(B_2=B_1U\) ，此时 \(B_1\) 与 \(B_2\) 等价，都会生成相同的格。

image-20231022002907661

题中M是第一行为编码后的密文、其余位置是随机数的4阶方阵，A是随机生成的幺模矩阵。C是M与A相乘的结果。把M看成格，与幺模矩阵A相乘后得到的格C与M等价，即\( M \sim C\)。根据这种等价关系，我们尝试对C进行格基规约（LLL）化简为M。

这里设使用LLL算法得到的格基为K，其第一行的四个元素即为被切成四份的flag，用long_to_bytes() 转化一下在拼一起就好了。

（PS：其实不太确定 C.LLL() 得到的到底是不是M，毕竟只是试了下就出flag了，第一行肯定没问题，但是时间很紧其他行没有验证）

#Sage
from Crypto.Util.number import *
p=198880159035681668071031460916089145469
c=[[1528140902799730745476264672501768332416990282355490479242339131918301176698899635154781328839496210200676497333428,2081687444435007467807250373278513114045272585243815458840083487459795021302180077490134099644993120009567147202772,3080873409460299046339495750746632185307246572817534784703936044874106809413620470006445984962733721029566440253675,3491734341995174183626991907292607070252197520631412767989879432598743851171175369180080355977574296558734415823458], [2359409535809048127331244699867147546817134802610067329431135227991488324148374065940238308147500809599395748756798,3191196199160821446351036460385791985682645040446022512790815348810555748825420237291839170774872264097466183208742,4665346530155386457242345394284286198347336281451530670818113876767736288089400119492317775648206643242839430899283,5369350746042850276067380638571565496087948799720968959426256192923852197959381101839484196445995828389461004495917], 
[1641407111066265429602929560264443103285908072677065498760570514577412905392260182334706635555256537745902283191251,2190536173399177167068153351271988931232272884028569669242062395087922275021628334797729266560930040116807133977244,3127556759140845426132305699421707182108351516931881411928719802847628408656887897596425133523782526561471050447359,3707239956529200159380870618471703921011276020439315706352183576289925263316580408968092016782483770373121972835410], 
[9883814543195849013523934427451407019514807606993414569626142656857168165339,13190422499129347541373922929251088892868361241120937213742340947017395215646,18832738552342488056498211782604832513006649329982003661701684946590064734701,22323329751908690611034666068697427811613727429398087082295754189068333861152]]

C=Matrix(ZZ,c)
K=C.LLL()
flag=b''
for i in K[0]:
    flag+=long_to_bytes(-i)
print(flag)

LLL-SecondBlood
#

image-20231022175051415

题中通过encrypt()函数向noise_ 和 mask_ 两个列表各添加4个大质数，并将(mask*m + noise) % p 的结果添加到列表 c_ 中。m是我们要找出的明文。理论上我们只要在有限域GF(q)中解出至少一组形如 mask_[i] * m+noise_[i]=c_[i] 的方程就可以求出m。但本题最大的困难在于 noise 完全未知。注意到mask是511位的超大质数，再与m相乘的结果必然更大，而noise只是50位的质数，显然mask*m 远大于 noise ，我们可以把问题转化为已知高位的HNP问题，进一步，HNP问题可以在格上转化为CVP问题。

由于对格理论了解的不够充分，解题时借鉴了CVP - CTF Wiki (ctf-wiki.org)上的部分思路和方法。 令向量 \(M\)=mask ,\(C\)=c_ , 数量阵\(P=pE\) ,参数\(l\approx log^\frac{1}{2}p\) (这里没弄懂底数是几，我按lg算的)。我们构造用如下矩阵表示的格 $$ \begin{bmatrix} P&0\\ M&\frac{1}{2^{l+1}} \end{bmatrix} $$ 目标是在这个格上找到与已知向量 \(C\) 最近的向量 \(C’\)，恰好这里 \(C’=mM\) ，我们就可以求出m。

利用最近平面算法（Babai’s nearest plane algorithm）求解CVP，得到flag，脚本如下（借鉴了一点点）

#Sage
from math import *
from Crypto.Util.number import *

q = 9342426601783650861020119568565656404715236059903009041977149778244153930435908024696666887269890479558473622355346816236972767736577737332173213722012253
mask = [6237128445236992920577225644858662677575951126467888858782461334057970069468925833844231116647406833999142659751374620280213290736114576089069396331226747, 6368031389213953889417545256750169233725975229197446803885029159767701479445576860704561593200907482372690851152126782391126462547524526631934408981070841, 5106473460982791188578285397420642137630347289252852045044021197988607082777231839839730169682158507822078412449827976663385282021916120837408192506341443, 6318090842950331228033349517542810123596316850353637421587264886413877142612686177796023049304908696413386218992511112752788640732410845589679820003047667]
c_ = [3823539664720029027586933152478492780438595004453489251844133830947165342839393878831914879334660250621422877333022321117120398528430519794109624186204492, 1721659645750224819953244995460589691120672649732560768435214608167861246790136217219349234604724148039910656573436663379375048145045443527267790379816425, 668633520079344839648950502380059311916108468801009386138810324259146523323704014491547148973835774917331333581475920804677395949854411894556705238578896, 497860586379981076499130281851986010889356253371192266267220334713415782402939318483926418213877341511996918189750595755372560345085899109305344338944066]

def babai(A, w):
    A = A.LLL(delta=0.75)
    G = A.gram_schmidt()[0]
    t = w
    for i in reversed(range(A.nrows())):
        c = ((t * G[i]) / (G[i] * G[i])).round()
        t -= A[i] * c
    return w - t

M = Matrix(QQ, 5, 5)
for i in range(4):
    M[i, i] = q
    M[4, i] = mask[i]
M[4, 4] = 1 / (2 ** (l + 1))
closest = babai(M, vector(c_ + [0]))
m=(closest[-1] * (2 ** (l + 1))) % q
flag=long_to_bytes(404417766109752774365993311026206252937822359426120081323087457724287886115277329019989616964477)
print(flag)

Week4
#

Normal ECC
#

又是一道ECC题，根据上周解题经验直接求 \(k=log_GK\)，但是数太大了，尝试跑了几个小时sage毫无作用。

暴力求 \(k\) 肯定是行不通的，这里只好换种思路。Hint中给出了 ord(E)==p 这样一个很特殊的条件，据此上网查照了若干资料，发现具有这种特殊性质的曲线有一个专属名称 “异常曲线” 即 anomalous curve，还有专门的攻击方法 “Smart‘s Attack ” 来求解离散对数。

  • 将 \(P, Q\) 扩充成 \(E(Q_p)\) 下的点 \(P^′, Q^′\)。原来的离散对数是找到 \(n\) 使得 \(Q=nP\) 且 \(P,Q \in E(F_p) \)，现在只需先把 \(P, Q\) 拓展成 \(P^′, Q^′\)，然后找到 \(n\) 满足 \(Q^′−nP^′=O^′\)，其中 \(O^′\)是某个非整数点。

  • 找到函数 \(ϕ:\mathbb{Q}→\mathbb{Q}\) 使得 \(Q=nP⇔ϕ(Q)=nϕ(P)\)。把椭圆曲线的加法「转换」成正常的加法，也就使离散对数问题变成简单的除法： $$ n=\frac{ϕ(P)}{ϕ(Q)} $$

  • 为了套上 \(ϕ\)，我们把式子乘上 \(p\) 倍，得到 \(pO^′=pQ^′−npP^′\)。套上 \(ϕ\) 函数得到: $$ n≡\frac{ϕ(pQ^′)}{ϕ(pP^′)}(\bmod\ p) $$

这里引用了资料（Smart’s Attack | Utaha’s CTF Note）中的一些分析，也比较幸运地找到了smart’s attack的代码。直接放到脚本里求出 \(k\)，再按常规思路解密 \(M\) 即可。

image-20231029155829848

完整的SageMath代码如下：

#sage
from hashlib import md5

def MD5(m):return md5(str(m).encode()).hexdigest()

def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)

p=11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
a=490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671
b=7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466
E=EllipticCurve(GF(p),[a,b])
G=E(4045939664332192284605924284905750194599514115248885617006435833400516258314135019849306107002566248677228498859069119557284134574413164612914441502516162, 2847794627838984866808853730797794758944159239755903652092146137932959816137006954045318821531984715562135134681256836794735388745354065994745661832926404)
K=E(9857925495630886472871072848615069766635115253576843197716242339068269151167072057478472997523547299286363591371734837904400286993818976404285783613138603, 9981865329938877904579306200429599690480093951555010258809210740458120586507638100468722807717390033784290215217185921690103757911870933497240578867679716)
C1=E(4349662787973529188741615503085571493571434812105745603868205005885464592782536198234863020839759214118594741734453731681116610298272107088387481605173124, 10835708302355425798729392993451337162773253000440566333611610633234929294159743316615308778168947697567386109223430056006489876900001115634567822674333770)
C2=E(5193866657417498376737132473732737330916570240569047910293144235752602489388092937375844109374780050061859498276712695321973801207620914447727053101524592, 684299154840371832195648774293174908478389728255128448106858267664482339440737099810868633906297465450436417091302739473407943955874648486647511119341978)
assert E.order() == p

k=SmartAttack(G,K,p)
M=C1-k*C2
flag='0xGame{'+MD5( M.xy()[0] )+'}'
print(flag)