2024-SHCTF-week4-wp-crypto

前三周没有来得及写wp记录，就写了写第四周的。

[Week4] MT19937

题目：

import hashlib
import random
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import os
from my_own_flag import flag

def MT_19937(num,en_c):
    seed1 = os.urandom(16)
    random.seed(seed1)
    number = []
    for i in range(num):
        number.append(random.getrandbits(32))
    cal = 0
    for i in range(num,num+en_c):
        cal += random.getrandbits(32)
    return number,cal

def encrypt(cal,flag):
    key = hashlib.sha256(str(cal).encode()).digest()
    A = AES.new(key, AES.MODE_ECB)
    c = A.encrypt(pad(flag,16))
    return c

def main():
    LEN = len(flag)
    m1,m2 = flag[:LEN//2],flag[LEN//2:]

    Num = 624
    # encrypt m1
    K1 = MT_19937(Num,Num)
    c1 = encrypt(K1[1],m1)

    # encrypt m1
    K2 = MT_19937(Num, Num//4)
    c2 = encrypt(K2[1], m2)

    with open('data.txt','w') as f:
        f.write(str(K1[0])+'\n')
        f.write(str(K2[0][:600])+'\n')
        f.write(str(c1)+'\n')
        f.write(str(c2)+'\n')

if __name__ == '__main__':
    main()

题目基于MT19937，将flag分为两部分m1、m2，分别做如下加密

• 对于m1，生成624个32bit的随机数并全部给出，之后继续生成624个32bit的随机数，用这624个随机数的和的sha256值作为key加密m1
• 对于m2，生成624个32bit的随机数并给出前600个，之后继续生成156个32bit的随机数，用这156个随机数的和的sha256值作为key加密m2

m1很简单，由于完整的给出了前624个32bit的随机数，因此完全可以重建初始state，从而实现向后任意预测，这一部分直接用randcrack模块就好。

关键在于m2，m2只给出了前600个随机数，没有办法做完整的预测。然而了解MT19937算法的话可以知道，前624个随机数生成完毕之后，整个state会做一次twist，而twist代码是：

def twist(self):
    for i in range(0, 624):
        y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
        self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]

        if y % 2 != 0:
            self.mt[i] = self.mt[i] ^ 0x9908b0df

可以看出，state经过twist后，其第i个位置其实也只与原来state的三个位置有关，分别是：

$$s_i,s_{i+1},s_{i+397}$$

由于对于m2来讲，我们只需要预测twist过后的前156个数，所以只要有397+156=553个数字就足够了。而我们拥有前600个随机数，也就拥有state的前600个位置，绰绰有余。

而最简单的实现依然是用randcrack，由于它要求提交满624个32bit的数字才能预测，所以553-624之间的数字可以随便提交一些，不会影响加密m2的key值。

exp：

from randcrack import RandCrack
import hashlib
from random import *
from Crypto.Cipher import AES

t1 = 
t2 = 
c1 = b'\x04\xd6k\xe5:\x9a\xabu\xb3\r\x06\xd9\x8e\x04\x87\xc7\x10\xecv\x0bG,\x9c\xb5\xb5q\xd6\x9c\xb8\xb7\xb1d'
c2 = b'CT\x1a>\x12\x8ff"\x89\xde\x9a\x0f\xf4\xac\xa2\xe7\xd2%\x15\xdd`\x03\xf4?u\x07#\xf9\x03\xde\xd4\x97'


####################################################################################### part1 
rc1 = RandCrack()
for i in range(624):
    rc1.submit(t1[i])
 
cal = 0
for i in range(624):
    cal += rc1.predict_getrandbits(32)
key = hashlib.sha256(str(cal).encode()).digest()
A = AES.new(key, AES.MODE_ECB)
flag1 = A.decrypt(c1)
print(flag1)
#SHCTF{TH1s_1s_YoU5


####################################################################################### part1 
rc2 = RandCrack()
num1 = 553
for i in range(num1):
    rc2.submit(t2[i])
for i in range(624-num1):
    rc2.submit(getrandbits(32))
 
cal = 0
for i in range(624//4):
    cal += rc2.predict_getrandbits(32)
key = hashlib.sha256(str(cal).encode()).digest()
A = AES.new(key, AES.MODE_ECB)
flag2 = A.decrypt(c2)
print(flag2)


#SHCTF{TH1s_1s_YoU5_5TART_WAY_0F_CTF}

[Week4] baby_rsa

题目描述：

只有中间未知？

题目：

#https://github.com/jvdsn/crypto-attacks
n = 149172698687247343307484774427463947040435385939538317995577802933708356659744781308849658149199463270402946054959026247011496643609722381036883462993606208405454448793748282856217226973570288117498818638210423816294135228225752144034736417495450129714250843040389723696691326017062575682989124677170212774709
e = 117932126002671581139669626170313849654365346787524775666511151162210096339679521576248537514813055641658722582914817481701142826861992970974206985137736311670025047752207632786439134855261541672012123572997654885689727972923659090161642085293034838535696206768459211817851404605357080649176502772728128885161
c = 5560665954852260703690321742771294743847646190564920056638605621636133720600072404637746086157764356927591996611862975162275415163691292729424412545560091018172812509230401361899309377868998693154480684535377865697939714965280441927137203589475324582174585416573174423912557361267766810988676863548944796515
dm = 0x2498aa4c85de5a33d5766f28d879f0df7175f43dd71cd4ab56ab67bf76334e6e3dcb
dl = 0x4c21c14305c34ed8f5e8879452c4ce569ce0789e6b39
d_zj=???

以及一篇论文：

34940373.pdf (iacr.org)

已知的条件是d的高位和低位，这个条件和今年高校密码挑战赛的赛题五一致：

2024-高校密码挑战赛赛题一-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

但这个题目并没有告诉d是多少bit，盲猜一波是512bit，然后直接用当时的代码就打掉了。

exp：

from Crypto.Util.number import *
from tqdm import *
import itertools

#coppersmith
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficients_monomials()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

n = 149172698687247343307484774427463947040435385939538317995577802933708356659744781308849658149199463270402946054959026247011496643609722381036883462993606208405454448793748282856217226973570288117498818638210423816294135228225752144034736417495450129714250843040389723696691326017062575682989124677170212774709
e = 117932126002671581139669626170313849654365346787524775666511151162210096339679521576248537514813055641658722582914817481701142826861992970974206985137736311670025047752207632786439134855261541672012123572997654885689727972923659090161642085293034838535696206768459211817851404605357080649176502772728128885161
c = 5560665954852260703690321742771294743847646190564920056638605621636133720600072404637746086157764356927591996611862975162275415163691292729424412545560091018172812509230401361899309377868998693154480684535377865697939714965280441927137203589475324582174585416573174423912557361267766810988676863548944796515
dm = 0x2498aa4c85de5a33d5766f28d879f0df7175f43dd71cd4ab56ab67bf76334e6e3dcb
dl = 0x4c21c14305c34ed8f5e8879452c4ce569ce0789e6b39

leakh = 270
leakl = 175
dbits = 512
dh = dm * 2^(dbits-leakh)

k_ = e*dh // n

PR.<x,y> = PolynomialRing(Zmod(e*2^leakl))
f = 1 + (k_ + x) * ((n+1) - y) - e*dl

bounds = (2^(dbits - leakh),2^513)
res = small_roots(f,bounds,m=4,d=5)

from gmpy2 import *

pplusq = res[0][1]

pminusq = iroot(pplusq^2-4*n,2)[0]
p = (pplusq + pminusq) // 2
q = n // p

d = inverse(e,(p-1)*(q-1))

print("d =",d)
print("p =",p)
print("q =",q)
assert p*q == n
print(long_to_bytes(int(pow(c,d,n))))


#SHCTF{If_people_do_not_believe_that_mathematics_is_simple,it_is_only_because_they_do_not_realize_how_complicated_life_is.}

[Week4] siDH

题目：

#!/usr/bin/env sage

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
from flag import flag

def gen_param(B):
 while True:
  a = randint(B >> 1, B)
  b = randint(B >> 2, B >> 1)
  p = 2**a * 3**b - 1
  if is_prime(p):
   return a, b

def gen_dmap(E):
 return E.isogeny(E.lift_x(ZZ(1)), codomain = E)

def gen_tpt(E, a, b):
 P, Q = [((p + 1) // 2**a) * _ for _ in E.gens()]
 R, S = [((p + 1) // 3**b) * _ for _ in E.gens()]
 return P, Q, R, S

def keygen(EC, b, P, Q, R, S):
 skey = randint(1, 3**b)
 T = R + skey * S
 phi = EC.isogeny(T, algorithm = "factored")
 _phi_dom, _phi_P, _phi_Q = phi.codomain(), phi(P), phi(Q)
 return skey, _phi_dom, _phi_P, _phi_Q


a1,b1 = gen_param(350)
p1 = 2**a1 * 3**b1 - 1
F1.<x> = GF(p1^2, modulus = x**2 + 1)
EC1 = EllipticCurve(F1, [0, 6, 0, 1, 0])
P1, Q1, R1, S1 = gen_tpt(EC, a1, b1)
print(f'P1={P1.xy()}')
print(f'Q1={Q1.xy()}')
print(f'R1={R1.xy()}')
print(f'S1={S1.xy()}')

sk1, _phi1_dom, _phi1_P, _phi1_Q = keygen(EC, b1, P1, Q1, R1, S1)
print(f'EC1:{_phi1_dom}')
print(f'PB1={_phi1_P.xy()}')
print(f'QB2={_phi1_Q.xy()}')

a2,b2 = gen_param(610)
p2 = 2**a2 * 3**b2 - 1
F2.<x> = GF(p2^2, modulus = x**2 + 1)
EC2 = EllipticCurve(F2, [0, 6, 0, 1, 0])
P2, Q2, R2, S2 = gen_tpt(EC, a2, b2)
print(f'P2={P2.xy()}')
print(f'Q2={Q2.xy()}')
print(f'R2={R2.xy()}')
print(f'S2={S2.xy()}')
sk2, _phi2_dom, _phi2_P, _phi2_Q = keygen(EC, b2, P2, Q2, R2, S2)
print(f'EC2:{_phi2_dom}')
print(f'PB2={_phi1_P.xy()}')
print(f'QB2={_phi1_Q.xy()}')

key = md5(long_to_bytes(sk1)).digest()
iv = md5(str(sk2).encode()).digest()

cipher = AES.new(key, AES.MODE_CFB, iv=iv)
enc = cipher.encrypt(flag)

print(f'enc = {enc.hex()}')

代码总体上感觉有一点点乱，比如缩进，比如变量赋值有些地方还不太正确（实际上似乎是对的）：

sk2, _phi2_dom, _phi2_P, _phi2_Q = keygen(EC, b2, P2, Q2, R2, S2)
print(f'EC2:{_phi2_dom}')
print(f'PB2={_phi1_P.xy()}') #_phi2_P
print(f'QB2={_phi1_Q.xy()}') #_phi2_Q

不过实际就是SIDH的密钥交换过程，要求出两次SIDH的sk来解AES得到flag。

众所周知SIDH已经完蛋了XD，这个题实现没有其他地方的漏洞，所以直接调castryck decru attack求私钥就好：

GiacomoPope/Castryck-Decru-SageMath: A SageMath implementation of the Castryck-Decru Key Recovery attack on SIDH (github.com)

由于两个sk的哈希值分别是key和iv，照常来说是要两个sk都求出来才好。然而由于模式是CFB，所以求出第一个sk后已经可以得到除第一个分组以外的所有明文：

e of mathematics is its freedom.}

那么整个flag应该是：

SHCTF{**********e of mathematics is its freedom.}

第二个sk对应的曲线参数大不少，求sk需要花的时间也相对较长，而注意到这个明文显然有一定语义，搜索一下觉得可能应该是：

SHCTF{The essence of mathematics is its freedom.}

就很幸运地一次成功了。

[Week4] BabyHash1

题目描述：

Magic Hash : )

题目：

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os

FLAG = b"SHCTF{XXX_FAKE_FLAG_XXX}"
p = 334641907675981737343904379204876337859127829299172648068105540032137951559908027120450949854596026146898543
G = [random_matrix(GF(p), 2) for _ in range(64)]
I = identity_matrix(GF(p), 2)
save(G, "G.sobj")
key = os.urandom(8)

H = lambda m: prod([G[i%64] if int(j) else I for i,j in enumerate(bin(int(m.hex(), 16))[2:])])
Q = list(H(key))
c = AES.new(2*key, AES.MODE_ECB).encrypt(pad(FLAG,16)).hex()
print(f"{Q = }")
print(f"{c = }")
"""
Q = [(92408373140638310582912266568541040708090711689280871505631689622417484347016487049244869849344848494009962, 53959869712387349430336059834241967356744173550876450413296700728311848545577500067458604734684838108665050), (252347024205859090718692136370078190718071419535216876332667850755617010322625175614169994287981074023442001, 248109129148524862390611680382928105844063942809716627922076622327580907465285046951446750474905265881834033)]
c = 'bbf4e7820865cc2fa3739a1d86006d83015180776a3285d4c14f5ee95685ac1ef64122e0f3603a794b4f170ec827dbb1'
"""

先生成列表G，其中含64个模p下的随机二阶矩阵，之后随机生成8字节的key，定义哈希函数H为：

$$H(key) = \prod_{i=1}^{64}G_i^j$$

其中j是key的二进制对应比特。给出$Q = H(key)$，要求出key来解AES得到flag值。

第一个想法是mitm，由于key是8个字节，假设第一个字节用多进程来做的话，剩下7个字节对半分是2^28的复杂度，似乎可以接受。然而实际操作了一下发现建立好字典都要9h，所以不太现实。

之后测试了一下发现这个p-1可以完全分解，并且除了最后一个大因子以外都光滑，这代表着可以把矩阵乘法想办法做DLP转到数域上来。

我转化的方法是用行列式，先把整个哈希操作转到行列式下来

$$|Q| = \prod_{i=1}^{64}|G_i^j| \quad(mod\;p)$$

此时选择模p乘法群中的生成元$g=5$，那么对Q以及Gi的行列式求对5的DLP：

$$|Q| = g^c \quad(mod\;p)$$ $$|G_i| = g^{Gr_i} \quad(mod\;p)$$

之后就可以把整个式子转化到指数上：

$$c = \sum_{i=1}^{64}j \cdot Gr_i \quad(mod \;p-1)$$

实际上要去除p-1的那个大因子r来做DLP，所以这里模数应该是$\frac{p-1}{r}$

这就转化成了一个背包问题，所以可以BKZ解决。

exp：

G = load("G.sobj")
p = 334641907675981737343904379204876337859127829299172648068105540032137951559908027120450949854596026146898543
F = GF(p)
I = identity_matrix(F, 2)

Q = [(92408373140638310582912266568541040708090711689280871505631689622417484347016487049244869849344848494009962, 53959869712387349430336059834241967356744173550876450413296700728311848545577500067458604734684838108665050), (252347024205859090718692136370078190718071419535216876332667850755617010322625175614169994287981074023442001, 248109129148524862390611680382928105844063942809716627922076622327580907465285046951446750474905265881834033)]
Q = Matrix(F, Q)
r = 1327433362304639193864290941923656426545922990449

################################################################################ dlp
Gr = []
g = F(pow(5,r,p))
for i in range(64):
    Gr.append(discrete_log(G[i].det()^r,g))

c = discrete_log(Q.det()^r,g)

from Crypto.Util.number import *

K = (p-1)//r
L = block_matrix(ZZ,[
    [1,(Matrix(ZZ,Gr).T).stack(vector(ZZ,[-c]))],
    [0,K]
])
L[:,-1:] *= 2^10
res = L.BKZ()[0][:64]

key = long_to_bytes(int("".join(list(map(str,res))),2))

from Crypto.Cipher import AES

c = 'bbf4e7820865cc2fa3739a1d86006d83015180776a3285d4c14f5ee95685ac1ef64122e0f3603a794b4f170ec827dbb1'
flag = AES.new(2*key, AES.MODE_ECB).decrypt(bytes.fromhex(c))

print(flag)


#SHCTF{master_of_the_linear_algebra}

[Week4] BabyHash2

题目描述：

Magic Hash : )

题目：

FLAG = "SHCTF{XXX_FAKE_FLAG_XXX}"
p = 1167195242552699154956050457
A = matrix(Zmod(p), [[1, 1], [0, 1]])
B = matrix(Zmod(p), [[1, 0], [1, 1]])

H = lambda m: prod([A if int(i) else B for i in bin(int(m.hex(), 16))[2:]])
msg = bytes.fromhex(input("msg > "))
assert msg != b"$ Welcome to SHCTF!!! :)"
if H(msg) == H(b"$ Welcome to SHCTF!!! :)") and len(msg) < 100:
    print("Congrats", FLAG)

本题先给出模p下的两个矩阵：

$$A = \left(\begin{matrix} 1&1\\ 0&1\\ \end{matrix}\right) , B = \left(\begin{matrix} 1&0\\ 1&1\\ \end{matrix}\right)$$

定义一个消息m的哈希函数为：

H = lambda m: prod([A if int(i) else B for i in bin(int(m.hex(), 16))[2:]])

也就是消息当前bit为1则乘A，否则乘B。需要我们给出一个指定消息的哈希碰撞来得到flag，并且该消息长度要小于100才行。

要构造出这种哈希碰撞，最简单的思路就是利用A、B构造个单位阵，并附加在哈希矩阵之后，从而实现碰撞。

而第一个构造单位阵的思路就是利用$SL_2(F_p)$的群阶r，直接附加$A^r$在前面就能得到一个单位阵，然而这个思路明显不能满足消息长度小于100这个限制，所以要另寻他法。

自己想了很久没想出来，所以把思路转向了利用SL2，hash等关键词搜索，之后搜到math stackexchange上的一个回答：

cryptography - An “additive” cryptographic hash-function that allows calculating the hash of some data from the hashes of the parts of that data. - Mathematics Stack Exchange

这个回答指向了一篇论文：

3-540-48658-5_5.pdf (springer.com)

而这篇论文又指向了一篇论文：

Group-theoretic hash functions (springer.com)

而这篇论文的section3显然就是我们需要的attack了，他的基本思路在于构造一个ZZ上的二阶矩阵：

$$M = \left(\begin{matrix} 1+k_1p&k_2p\\ k_3p&1+k_4p\\ \end{matrix}\right)$$

这个矩阵显然在模p下是个单位阵，而对于$SL_2(Z)$上的矩阵来说，论文介绍了一种方式，用欧几里得算法就可以把它分解成$A,B$的乘积形式。

因此主要分为两个步骤，第一步是找到合适的$k_1,k_2,k_3,k_4$来构造矩阵$M$，第二步是把这个矩阵分解为$A,B$乘积，从而附加在消息后达到伪造效果。

构造矩阵M

由于$A,B$是$SL_2(Z)$的生成元，因此如果一个矩阵$M$能分解成$A,B$乘积的话，显然$M$也需要是$SL_2(Z)$的元素，也就是需要满足：

$$|M| = (1+k_1p)(1+k_4p) - k_2pk_3p = 1$$

展开一下就得到：

$$k_1p+ k_4p + k_1k_4p^2 = k_2k_3p^2$$ $$\rightarrow k_1 + k_4 = (k_2k_3 - k_1k_4)p$$

所以我们实际上是要找上面这个丢番图方程的解，从而得到$k_1,k_2,k_3,k_4$。

由上述等式显然有：

$$k_1 + k_4 = cp$$

这个丢番图方程显然有无数组整数解，而我们只需要构造出一组解即可，因此不妨任意取c，再令$k_3 = p’$，那么联立几个式子之后将会只剩下$k_1,k_2$：

$$cp = (k_2p' - k_1(cp-k_1))p$$

整理一下就是：

$$k_2p' - k_1cp+k_1^2 - c = 0$$

那么在模p’下就可以消去$k_2$，从而得到$k_1$的二次方程：

$$k_1^2 - k_1cp - c = 0 \quad(mod\;p')$$

解出$k_1$后代回去就能解得$k_2$了。

将M分解为A、B乘积

现在我们拥有了$SL_2(Z)$上的矩阵：

$$M = \left(\begin{matrix} 1+k_1p&k_2p\\ k_3p&1+k_4p\\ \end{matrix}\right)$$

要将他分解成$A,B$乘积形式，$A,B$分别为：

$$A = \left(\begin{matrix} 1&1\\ 0&1\\ \end{matrix}\right) , B = \left(\begin{matrix} 1&0\\ 1&1\\ \end{matrix}\right)$$

论文里有说用欧几里得算法即可，这里研究一下为什么可以这样做。首先可以发现$A,B$对应的是下列线性变换：

AS -> 将S的第二行加到第一行
BS -> 将S的第一行加到第二行
SA -> 将S的第一列加到第二列
SB -> 将S的第二列加到第一列

我们不妨就关注行的操作：

AS -> 将S的第二行加到第一行
BS -> 将S的第一行加到第二行

可以发现，一个二阶矩阵左乘$A,B$，其实就是这个矩阵的两个行向量在相互迭代增加，那么把这个过程反过来看，其实也就是两个行向量在相互约减！

这一点很关键，为了演示这个本质，我们不妨假设现有矩阵：

$$S = \left(\begin{matrix} a&b\\ c&d\\ \end{matrix}\right)$$

假设$c>a$，那么做带余除法有：

$$c = q_1a + r_1 \quad , \quad 0 \leq r < a$$

那么$S$就可以约减为：

$$\left(\begin{matrix} a&b\\ c&d\\ \end{matrix}\right) = B^{q_1} \left(\begin{matrix} a&b\\ {r_1}&d-{q_1}b\\ \end{matrix}\right)$$

此时有$a> r_1$，那么继续做带余除法：

$$a = q_2r_1 + r_2 \quad , \quad 0 \leq r_2 < r_1$$

所以继续约减得到：

$$\left(\begin{matrix} a&b\\ c&d\\ \end{matrix}\right) = B^{q_1}A^{q_2} \left(\begin{matrix} {r_2}&b-q_2(d-{q_1}b)\\ {r_1}&d-{q_1}b\\ \end{matrix}\right)$$

可以看出，约减过程其实是在对行向量的第一个值做辗转相除，那么在有限步骤后，根据步骤是奇数步还是偶数步分别会约减得到：

$$\left(\begin{matrix} a&b\\ c&d\\ \end{matrix}\right) = B^{q_1}A^{q_2}...B^{q_n} \left(\begin{matrix} x&y\\ 0&z\\ \end{matrix}\right) \quad , n = 2k+1$$ $$\left(\begin{matrix} a&b\\ c&d\\ \end{matrix}\right) = B^{q_1}A^{q_2}...A^{q_n} \left(\begin{matrix} 0&y\\ x&z\\ \end{matrix}\right) \quad , n = 2k$$

第二个情况显然不会是一个单位阵，我们考虑第一种情况，我们知道以下两点：

• 所有值都是正的且为整数

• 矩阵均为$SL_2(Z)$下的矩阵，也就有：

  $$|\left(\begin{matrix} a&b\\ c&d\\ \end{matrix}\right)| = |B^{q_1}||A^{q_2}|...|B^{q_n}| |\left(\begin{matrix} x&y\\ 0&z\\ \end{matrix}\right)| = 1$$

  这说明：

  $$|\left(\begin{matrix} x&y\\ 0&z\\ \end{matrix}\right)| = 1$$

结合上面两点，很容易得到：

$$x=z=1$$

既然$z=1$，那么如果$y \neq 0$的话，仍然可以做约减：

$$\left(\begin{matrix} 1&y\\ 0&1\\ \end{matrix}\right) = A^y \left(\begin{matrix} 1&0\\ 0&1\\ \end{matrix}\right)$$

这就最终得到了我们需要的单位阵了。

而我们需要$y$较小才行，因为$y$较小代表着最后一步约减的次数较少，才能使得消息长度较短。实际测试发现$y$的值实际上和最开始求丢番图方程时取的c有关：

$$k_1 + k_4 = cp$$

关系为：

$$y = 1 - c \quad(mod\;p)$$

这代表着取$c=1$，就恰好能在奇数步辗转相除之后就得到单位阵。

伪造

我们既然得到了$M$的分解，那么现在似乎只需要把这个分解对应的字节串附加在消息之后即可。

这里存在一个小问题：测试发现我们得到的这个分解序列长度模8只会是2或6，所以如果以字节形式附加在原始消息串后面的话，前面会补6个0或者2个0，从而导致实际上原始哈希矩阵右乘的矩阵不是单位阵，而是$B^6$或者$B^2$，因此只能附加二进制流在后面才行。

为啥只会是2或6我没太想明白

为什么不能附加在前面？因为附加在前面的话，msg最开始的很多个0在H函数里是会被忽略掉的，不会参与计算。

实际上如果msg开始是1的话就无所谓，附加在前面也可以，见最后的”其他“部分

成功率分析

论文提到，这个算法对于随机选择的c、p’本身只是概率性成功的，而对于这个题目而言则失败率更大，总结一下可能导致失败的地方在于：

• 二次方程在模p’下无解

  这等价于判别式$\Delta = c^2p^2 + 4c$不是模p’下的二次剩余

• 欧几里得算法步骤是偶数步

• 消息长度大于100

所以要简单爆破一下才行，不过也很快。为了保证p’大于p选用nextprime较好。

完整exp

from Crypto.Util.number import *
from gmpy2 import next_prime, invert, powmod
from random import getrandbits

H = lambda m: prod([A if int(i) else B for i in bin(int(m.hex(), 16))[2:]])

def Euclid(a,b):
    t = []
    while(1):
        t.append(a // b)
        a, b = b, a%b
        if(b == 0):
            return t

p = 1167195242552699154956050457
F = GF(p)
A = matrix(F, [[1, 1], [0, 1]])
B = matrix(F, [[1, 0], [1, 1]])
I = identity_matrix(F,2)

counts = 0
while(1):
    counts += 1
    p_ = next_prime(p + getrandbits(89))
    if(p_ % 4 == 1):
        continue
    c = 1
    a = c^2*p^2 + 4*c
    if(powmod(a,(p_-1)//2,p_) == 1):
        t1 = powmod(a,(p_+1)//4,p_)

        k1 = int((c*p+t1) * invert(2,p_) % p_)
        k2 = int(c + c*p*k1 - k1^2) // p_
        k3 = p_
        k4 = c*p - k1

        K = Matrix(ZZ,[
            [1+k1*p,k2*p],
            [k3*p,1+k4*p]
        ])

        aa,bb,cc,dd = K.list()
        T = Euclid(cc,aa)[::-1]
        if(len(T) % 2 == 0):
            continue

        if(0):
            L = I
            for i in range(len(T)):
                if(i % 2 == 0):
                    L = B^(T[i]) * L
                else:
                    L = A^(T[i]) * L
            assert I == L

        msg = ""
        for i in range(len(T)):
            if(i % 2 == 0):
                msg += "0"*T[i]
            else:
                msg += "1"*T[i]
        
        msg = bin(int(b"$ Welcome to SHCTF!!! :)".hex(), 16))[2:] + msg
        msg = long_to_bytes(int(msg,2))
        assert H(msg) == H(b"$ Welcome to SHCTF!!! :)")

        if(len(msg) > 1):
            print(counts)
            print(msg.hex())
            break

这里选择p’模4余3均仅仅是为了二次剩余计算方便，没有其他含义。

之后拿去交互就得到flag了：

from pwn import *

sh = remote("210.44.150.15",49545)
sh.interactive()

#SHCTF{ez_att@ck_2_th15_weak_hash}

其他

实际上取其他较小的c也完全可以在较少的步骤得到单位阵，可以自行推导。这里放一个示例：

from Crypto.Util.number import *
from gmpy2 import next_prime, invert, powmod
from random import getrandbits, randint

def Euclid(a,b):
    t = []
    while(1):
        t.append(a // b)
        a, b = b, a%b
        if(b == 0):
            return t
        
p = 1167195242552699154956050457
F = GF(p)
A = matrix(F, [[1, 1], [0, 1]])
B = matrix(F, [[1, 0], [1, 1]])
I = identity_matrix(F,2)

counts = 0
while(1):
    counts += 1
    p_ = next_prime(p + getrandbits(89))
    if(p_ % 4 == 1):
        continue
    c = randint(1,50)
    a = c^2*p^2 + 4*c
    try:
        if(powmod(a,(p_-1)//2,p_) == 1):
            t1 = powmod(a,(p_+1)//4,p_)

            k1 = int((c*p+t1) * invert(2,p_) % p_)
            k2 = int(c + c*p*k1 - k1^2) // p_
            k3 = p_
            k4 = c*p - k1

            K = Matrix(ZZ,[
                [1+k1*p,k2*p],
                [k3*p,1+k4*p]
            ])

            aa,bb,cc,dd = K.list()
            T = Euclid(cc,dd)[::-1]
            if(len(T) % 2 == 0):
                continue

            if(1):
                L = I
                for i in range(len(T)):
                    if(i % 2 == 0):
                        L *= A^(T[i])
                    else:
                        L *= B^(T[i])
                assert I == L

            msg = ""
            for i in range(len(T)):
                if(i % 2 == 0):
                    msg += "1"*T[i]
                else:
                    msg += "0"*T[i]
            
            msg = bin(int(b"$ Welcome to SHCTF!!! :)".hex(), 16))[2:] + msg
            msg = long_to_bytes(int(msg,2))
            assert H(msg) == H(b"$ Welcome to SHCTF!!! :)")

            if(len(msg) < 100):
                print(c, counts, msg.hex())
                break
    except:
        pass