HgameDiv3,4

Hgame Div 3,4题解

0.About

终于在接触CTF差不多大约6个月后，尝试打了一下杭州电子科大的CTF招新题（总体感觉只有4个字：我太菜了

只做了密码学，其他的题目不看，因为不是我研究的内容（

第3，4两周的题目确实难度变大了很多

#define huangx607087 feiwu

1. LikiPrime

#!/usr/bin/env python3
import random
from libnum import s2n
from secret import secrets, flag
def get_prime(secret):
    prime = 1
    for _ in range(secret):
        prime = prime << 1
    return prime - 1
random.shuffle(secrets)
m = s2n(flag)
p = get_prime(secrets[0])
q = get_prime(secrets[1])
n = p * q
e = 0x10001
c = pow(m, e, n)
print("n = {}.format(n)")
print("e = {}.format(e)")
print("c = {}.format(c)")

题目最后给出的是$n,e,c$的值。

通过简单地观察代码，我们可以发现，$p,q$都具有$2^k-1$的形式，并且都是素数。$n$的位数为$5072$位，因此我们可以通过枚举法枚举$p.q$的值。

枚举出$p,q$之后。之后就是正常的RSA解密了。

hgame{Mers3nne~Pr!Me^re4l1y_s0+5O-li7tle!}

2.HappyNewYear

题目描述：Liki 的朋友们在新年的时候给她发送了新年祝福。好家伙，一看就是群发的，有几个朋友发送的内容还是相同的

然后题目给出了很多$n,c$的值，并且$e=3$。不出意外应该是低指数广播攻击。因为提示有一样的，因此我们可以两两枚举，使用CRT求解。

from Crypto.Util.number import *
from gmpy2 import *
def crt2(m1,m2,r1,r2):
    M=m1*m2
    t1,t2=inverse(m2,m1),inverse(m1,m2)
    return (r1*t1*m2+r2*t2*m1)%M
f=open("data2.txt","r")
n,c=[],[]
a=[]
b=[]
for i in range(7):
    n.append(int(f.readline()))
    c.append(int(f.readline()))
for i in range(7):
    for j in range(i+1,7):
        now=crt2(n[i],n[j],c[i],c[j])
        if(now in a):
            if now not in b:
                b.append(now)
        else:
            a.append(now)
for i in b:
    c,d=iroot(i,3)
    if(d):
        print(long_to_bytes(c))

3.EncryptedChats

题目首先给出了两个人的对话，还有AES加密的过程。

1.Dialogue

Switch: 你好老伙汁
Million: 你好
Switch: 所以为什么这家伙在这里
Liki: 因为我是来记录你们谈话内容的
Million: 好吧
Million: 不过我可以提一个要求吗
Liki: ?
Million: 我们...换一个群聊
Switch: 好啊! 我看看, 就换到加法群聊吧!
Switch: 喂, 帮忙选一个质数 g 吧
Liki: ??, 12602983924735419868428783329859102652072837431735895060811258460532600319539509800915989811879506790207025505003183121812480524033163157114086741486989697
Million: 这位女士，可以劳烦您再为我们选择一个质数 p 吗
Liki: ???...那就,  30567260905179651419358486099834315837354102714690253338851161207042846254351374572818884286661092938876675032728700590336029243619773064402923830209873155153338320502164587381848849791304214084993139233581072431814555885408821184652544361671134564827265516331283076223247829980225591857643487356406284913560960657053777612115591241983729716542192518684003840806442329098770424504275465756739925434019460351138273272559738332984560095465809481270198689251655392941966835733947437503158486731906649716026200661065054914445245468517406404904444261196826370252359102324767986314473183183059212009545789665906197844518119 吧, 够大了吗?
Million: 好的, 我选好我的 a 了, 那么 A = 6407001517522031755461029087358686699246016691953286745456203144289666065160284103094131027888246726980488732095429549592118968601737506427099198442788626223019135982124788211819831979642738635150279126917220901861977041911299607913392143290015904211117118451848822390856596017775995010697100627886929406512483565105588306151304249791558742229557096175320767054998573953728418896571838697779621641522372719890056962681223595931519174265357487072296679757688238385898442549594049002467756836225770565740860731932911280385359763772064721179733418453824127593878917184915316616399071722555609838785743384947882543058635
# A = a ^ g % p = pow(g, a, p)
Switch: okay, b 也选好了, B = 5522084830673448802472379641008428434072040852768290130448235845195771339187395942646105104638930576247008845820145438300060808178610210847444428530002142556272450436372497461222761977462182452947513887074829637667167313239798703720635138224358712513217604569884276513251617003838008296082768599917178457307640326380587295666291524388123169244965414927588882003753247085026455845320527874258783530744522455308596065597902210653744845305271468086224187208396213207085588031362747352905905343508092625379341493584570041786625506585600322965052668481899375651376670219908567608009443985857358126335247278232020255467723
# B = b ^ g % p = pow(g, b, p)
Liki: ????
Million: {'iv': 'd3811beb5cd2a4e1e778207ab541082b', 'encrypted_flag': '059e9c216bcc14e5d6901bcf651bee361d9fe42f225bc0539935671926e6c092'}
Switch: {'iv': 'b4259ed79d050dabc7eab0c77590a6d0', 'encrypted_flag': 'af3fe410a6927cc227051f587a76132d668187e0de5ebf0608598a870a4bbc89'}
Million: 再见伙汁
Switch: 再见
Liki: ?????

2.AES encryption

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
import os
from secret import shared_secret, FLAG
def encrypt_flag(shared_secret: int):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Encrypt flag
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    # Prepare data to send
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data
print(encrypt_flag(shared_secret))

3.Solution

很显然，看到两个人的对话，就知道这道题考点是数字签名。也就是著名的DH密钥交换算法。这个在我的DLP Notes 1里面有较为详细的介绍。

不过在这边有一个新的概念就是群：简单来说，群就是一个封闭的运算集合。在一个群$G$里面，使用的运算符号是$\mathrm{op}$。那么对于任意的$a,b,\in G$，满足交换律律$a \text{ op }b=b\text{ op }a$，结合律$a\text{ op }b\text{ op }c=a\text{ op }(b\text{ op }c)$。并且群中有一个中性元$e$，每个元素$a$都有一个逆元$a^{-1}$，使得$a\text{ op } a^{-1}=e$。当然，$a\text{ op }a$在群中可以记作$a^2$。

从上述对话中我们可以看到：这里使用的是加法群，因此$\mathrm{op}=+$，而表面上的指数，实际上应该是数学计算中的乘号。

根据DH密钥交换系统，最后共享密钥是群里面的$g^{ab}$。由于这里是加法群，因此共享内容是$gab$三者乘积模$p$的值。因此直接求个逆元就可以得到$a,b$。

至于AES部分，直接模仿他的加密过程构建密钥即可。

from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib
from os import urandom
from given import g,p,A,B
d=inverse(g,p)
a,b=A*d%p,B*d%p
S=g*a*b%p
sha1=hashlib.sha1()
sha1.update(str(S).encode('ascii'))
key=sha1.digest()[:16]
iv=[0xd3811beb5cd2a4e1e778207ab541082b,0xb4259ed79d050dabc7eab0c77590a6d0]
c=[0x059e9c216bcc14e5d6901bcf651bee361d9fe42f225bc0539935671926e6c092,0xaf3fe410a6927cc227051f587a76132d668187e0de5ebf0608598a870a4bbc89]
for i in range(2):
    iv[i]=long_to_bytes(iv[i])
    c[i]=long_to_bytes(c[i])
cipher1 = AES.new(key, AES.MODE_CBC, iv[0])
cipher2 = AES.new(key, AES.MODE_CBC, iv[1])
d1=cipher1.decrypt(c[0])
d2=cipher2.decrypt(c[1])
print(d1,d2)

4.夺宝大冒险1

Step 1：阅读题目，确定算法

还是先看一下题目：

import os
flag = "xxxx"
class Cxx1ff:
    c4ff1x = int.from_bytes(os.urandom(8),'big')
    c66f6 = int.from_bytes(os.urandom(8),'big')
    c4ff10 = int.from_bytes(os.urandom(8),'big')
    def __init__(self, seed):
        self.state = seed

    def next(self):
        self.state = (self.state * self.c4ff1x + self.c66f6) % self.c4ff10
        return self.state
class Cxx2ff:
    c4ff1x = int.from_bytes(os.urandom(8),'big')
    c66f6 = int.from_bytes(os.urandom(8),'big')
    c4ff10 = int.from_bytes(os.urandom(8),'big')
    def __init__(self, seed):
        self.state = seed

    def next(self):
        self.state = (self.state * self.c4ff1x + self.c66f6) % self.c4ff10
        return self.state
class Cxx3ff:
    c4ff1x = int.from_bytes(os.urandom(8),'big')
    c66f6 = int.from_bytes(os.urandom(8),'big')
    c4ff10 = int.from_bytes(os.urandom(8),'big')
    def __init__(self, seed):
        self.state = seed

    def next(self):
        self.state = (self.state * self.c4ff1x + self.c66f6) % self.c4ff10
        return self.state
def test1():
    gen = Cxx1ff(123) 
    print((Cxx1ff.c4ff1x,Cxx1ff.c4ff10))
    print(gen.next())
    print(gen.next())
    t1 = input()
    try:
        if int(t1.strip())==Cxx1ff.c66f6:
            return 1
    except:
        pass
    return 0
def test2():
    gen = Cxx2ff(123)
    print((Cxx2ff.c4ff10))
    print(gen.next())
    print(gen.next())
    print(gen.next())
    t1 = input()
    t2 = input()
    try:
        if (int(t1.strip())==Cxx2ff.c4ff1x) and (int(t2.strip())==Cxx2ff.c66f6):
            return 1
    except:
        pass
    return 0
def test3():
    gen = Cxx3ff(123)
    print(gen.next())
    print(gen.next())
    print(gen.next())
    print(gen.next())
    print(gen.next())
    print(gen.next())
    print(gen.next())
    t1 = input()
    try:
        if int(t1.strip())==Cxx3ff.c4ff10:
            return 1
    except:
        pass
    return 0
if __name__ == "__main__":
    ans = 0
    ans += test1()
    ans += test2()
    ans += test3()
    if ans>=3:
        print("win")
        print(flag)
    else:
        print("fail")

通过阅读代码可以发现，这道题实际上是线性同余生成器的一个题目。线性同余生成器就是通过递推式$X_{n+1}\equiv AX_{n}+B \pmod M$的计算来生成随机数，它包括一个线性函数$Ax+B$和模$M$运算。

而这道题，实际上分成了三个小问，当三个小问都答对的时候，服务器会直接给你flag，下面我们逐一解决这三小问。

Step 2: 分步解决问题，提出初步方案。

Question 1

第一问是已知$A,M,X_{0}=123,X_1,X_2$，求$B$。那么我们根据
$$
X_{1}\equiv AX_{0}+B \pmod M
$$
可以直接推出
$$
B\equiv X_{1}-AX_{0} \pmod M
$$
所以，第一问真正的计算只有一行代码（所有的数据都是我进行本地测试时使用的数据，服务器给出的数据可能不一样）。

a=3423853412712492282
m=17055887075354437978
x1=8976750431089074058
b=(x1-123*a)%m
print(b)

Question 2

第二问，已知$M,X_0=123,X_1,X_2,X_3$。要求出$A,B$那么我们根据$X_1\equiv AX_0+B \pmod M$、$X_2\equiv AX_1+B \pmod M$、$X_3\equiv AX_2+B \pmod M$。第二个式子减去第一个式子，第三个式子减去第二个式子，消去了$B$，就得到
$$
X_2-X_1\equiv A(X_1-X_0)\pmod M
$$

$$
X_3-X_2\equiv A(X_2-X_1)\pmod M
$$

所以，以第一个式子两边除以$X_1-X_0$，我们就可以得到：
$$
(X_2-X_1)(X_1-X_0)^{-1}\equiv A \pmod M
$$
当然，我们也可以用第二个式子
$$
(X_3-X_2)(X_2-X_1)^{-1}\equiv A \pmod M
$$
$A$求出来之后，那么我们根据
$$
AX_0+B\equiv X_1\pmod M
$$
可以得到
$$
B\equiv X_1-AX_0 \pmod M
$$
这样题目就得出了解。

上一下第二问的代码

from Crypto.Util.number import *
def G(d1,d2,m):
    return (d2)*inverse(d1,m)%m
m=17339855340627587175
x0=123
x1=11280784678567285991
x2=16229269394156588360
x3=12807800121938543462
detla1,detla2,detla3=x1-x0,x2-x1,x3-x2
a=G(detla1,detla2,m)
b=(x1-123*a)%m
print(a,b)

Question 3

第三问，已知$X_0$到$X_7$的值，要求出模数$M$。

根据我们知道的$X_0$到$X_7$的递推式，我们依然想到了消元。

根据第二问我们已经获得的两个式子：
$$
(X_2-X_1)(X_1-X_0)^{-1}\equiv A \pmod M
$$

$$
(X_3-X_2)(X_2-X_1)^{-1}\equiv A \pmod M
$$

联立这两个式子，我们可以得到
$$
(X_2-X_1)(X_1-X_0)^{-1}\equiv(X_3-X_2)(X_2-X_1)^{-1} \pmod M
$$
干脆把分母也去了吧
$$
(X_2-X_1)^2\equiv(X_3-X_2)(X_1-X_0) \pmod M
$$
然后把同余号也去了吧（
$$
(X_2-X_1)^2=(X_3-X_2)(X_1-X_0)+k_2M
$$
最后移项
$$
(X_2-X_1)^2-(X_3-X_2)(X_1-X_0)=+k_2M
$$
同理可得：
$$
(X_3-X_2)^2-(X_4-X_3)(X_2-X_1)=+k_3M
$$
我们可以通过这一手段获得$k_2M,k_3M,k_4M,k_5M,k_6M$的值，然后直接求GCD就可以了。

上一下第三问的代码

from Crypto.Util.number import *i
x0=123
x1=9994867626161635096
x2=5753461374688204354
x3=11648048026234191592
x4=1202418284492042518
x5=10468479901118246086
x6=8754702082052904382
x7=4553263904866307968
detla1,detla2,detla3,detla4,detla5=x1-x0,x2-x1,x3-x2,x4-x3,x5-x4
detla6,detla7=x6-x5,x7-x6
P2=detla2**2-detla3*detla1
P3=detla3**2-detla4*detla2
P4=detla4**2-detla5*detla3
P5=detla5**2-detla6*detla4
P6=detla6**2-detla7*detla5
P2,P3,P4,P5,P6=abs(P2),abs(P3),abs(P4),abs(P5),abs(P6)
E=GCD(P2,P3)
E=GCD(E,P4)
E=GCD(E,P5)
E=GCD(E,P6)
print(E)

Step 3.回顾并完善方案

内测的时候，这三个代码都能够得出正确答案，但都是概率性正确（也就是总是会出错），原因可能如下：

第一问的$M>A$且$\gcd(A,M)\not =1$的时候，大概有$70\text{percent}$的概率会出现第一问的错误。因为两边的模是不能月的，之前就提出过$2x\equiv2 \pmod 6$的解是$x_1=1$和$x_2=4$。

第二问可能同时出现$\gcd (X_1-X_0,M)\not =1$和$\gcd (X_2-X_1,M)\not =1$，此时逆元无法求出，解题会非常麻烦。

第三问可能会出现$M$的比特位长$≥65$的情况，因为最后求$\gcd$的时候，$M$前面的系数没有消成$1$。

总之，这些问题处理起来，会非常麻烦，但在数据比较好的情况下，这三个做法都能做出来。

所以，如果最后搞不出来，那就干脆重连算了。比如说，在第二问$\gcd$全部不等于$1$的时候程序自动raise ValueError，第三问解出的数字比特位长于$64$也raise一个ValueError。第三问解决出来后把服务器的反馈全盘接受，一旦出现fail自动重连，因此只要我们最后接收到的字符串的长度大于$5$，就说明我们获得了flag，然后直接输出就行了。

由于我们不能预估这些概率，所以我打算多次连接（，脚本如下。

from Crypto.Util.number import *
from pwn import *
def s1(a,m,x1,x2):
    return (x1-123*a)%m
def s2(m,x1,x2,x3):
    def G(d1,d2,m):
        #print(GCD(d1,m))
        assert GCD(d1,m)==1
        return (d2)*inverse(d1,m)%m
    x0=123
    detla1,detla2,detla3=x1-x0,x2-x1,x3-x2
    try:
        a=G(detla1,detla2,m)
        b=(x1-123*a)%m
        #print(a.bit_length(),b.bit_length())
        return(a,b)
    except:
        try:
            a=G(detla2,detla3,m)
            b=(x1-123*a)%m
            #print(a.bit_length(),b.bit_length())
            return(a,b)
        except:
            raise ValueError
def s3(x1,x2,x3,x4,x5,x6,x7):
    x0=123
    detla1,detla2,detla3,detla4,detla5=x1-x0,x2-x1,x3-x2,x4-x3,x5-x4
    detla6,detla7=x6-x5,x7-x6
    P2=detla2**2-detla3*detla1
    P3=detla3**2-detla4*detla2
    P4=detla4**2-detla5*detla3
    P5=detla5**2-detla6*detla4
    P6=detla6**2-detla7*detla5
    P2,P3,P4,P5,P6=abs(P2),abs(P3),abs(P4),abs(P5),abs(P6)
    E=GCD(P2,P3)
    E=GCD(E,P4)
    E=GCD(E,P5)
    E=GCD(E,P6)
    #print(E.bit_length())
    if E.bit_length()>64:
        raise ValueError
    return E
def getamin1(s1):
    arr,now,ind=[],0,0
    for i in s1:
        if ord(i) in range(48,58):
            ind,now=1,now*10+ord(i)-48
        else:
            if ind:
                arr.append(now)
                now,ind=0,0
    assert len(arr)==2
    return arr[0],arr[1]
#---------------RUN BELOW-------------------#
#get 1
def run():
    sh=remote("182.92.108.71",30641)
    so1=sh.recvline(keepends=False)
    x1=sh.recvline(keepends=False)
    x2=sh.recvline(keepends=False)
    a,m=getamin1(so1)
    x1,x2=int(x1),int(x2)
    ans1=s1(a,m,x1,x2)
    print(ans1.bit_length())
    sh.sendline(str(ans1))
    #get 2
    m=int(sh.recvline(keepends=False))
    x1=int(sh.recvline(keepends=False))
    x2=int(sh.recvline(keepends=False))
    x3=int(sh.recvline(keepends=False))
    a,b=s2(m,x1,x2,x3)
    sh.sendline(str(a))
    sh.sendline(str(b))
    #get 3
    x1=int(sh.recvline(keepends=False))
    x2=int(sh.recvline(keepends=False))
    x3=int(sh.recvline(keepends=False))
    x4=int(sh.recvline(keepends=False))
    x5=int(sh.recvline(keepends=False))
    x6=int(sh.recvline(keepends=False))
    x7=int(sh.recvline(keepends=False))
    ans=s3(x1,x2,x3,x4,x5,x6,x7)
    sh.sendline(str(ans))
    final=sh.recvall()
    sh.close()
    return final
#------------------MAIN BELOW------------------#
T,F=1,""
while True:
    print(str(T)+'th time trying')
    F=""
    try:
        F=run()
    except:
        pass
    if len(F)>6:
        print(F)
        print('with using'+str(T)+'times to get the flag')
        break
    else:
        T+=1

运行截图，这里是用了$24$次，多测了几次，最好的一次重置$3$次获得flag，最坏的一次重置了$91$次。

Step 4 Reference

不知道为什么出题人生成模数的时候不使用getPrime(64)而是使用bytes_to_long(urandom(8))，是大E了还是另有想法，只能坐等官方的week4的wp了。这说明自己还是太菜了（

Update 2021.7.12

当时打完了之后问了一下作者。实际上是打完不久，但4个半月后才想起来Update，此处实际上使用的是重复攻击意识，因为有的时候由于各种数据的原因，虽然算法是对的，但有可能也做不出最终结果。因此遇到这种情况的时候可以多试几次，就可以得出正确答案

5.夺宝大冒险2

看一下题目，是lfsr求种子和随机数。

class LXFIQNN():
    def __init__(self, init, mask, length):
        self.init = init
        self.mask = mask
        self.lengthmask = 2**(length+1)-1

    def next(self):
        nextdata = (self.init << 1) & self.lengthmask 
        i = self.init & self.mask & self.lengthmask 
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        nextdata ^= output
        self.init = nextdata
        return output

    def random(self, nbit):
        output = 0
        for _ in range(nbit):
            output <<= 1
            output |= self.next()
        return output
from secret import init, FLAG
"""secret.py
import os
init = int.from_bytes(os.urandom(5), 'big')
FLAG = 'hgame{xxx}'
"""
prng = LXFIQNN(init, 0b1011001010001010000100001000111011110101, 40)
score = 0
for r in range(100):
    print(f"round {r} :: score {score}")
    try:
        guess = int(input("guess: "))
    except:
        break
    secret = prng.random(4)
    if secret == guess:
        print("Right")
        score += 1
    else:
        print(f"Wrong, the secret is {secret}")
if score >= 80:
    print(FLAG)

CTFWIKI上说过，一个$n$位的lfsr，在知道掩码mask的情况下，只需要知道$n$位的输出，就可以恢复种子值，而如果在连mask也不知道的情况下，如果知道了$2n$位的输出，那么可以先通过矩阵运算得到mask的值，然后求个逆矩阵就可以得到种子的值了。

具体内容见自己博客的**Lfsr Notes[2021.1.27]**相关内容，下面直接上一下做题脚本。相关内容的构造可以直接模仿题目给出的方法。

from Crypto.Util.number import *
from pwn import *
class LXFIQNN():
    def __init__(self, init, mask, length):
        self.init = init
        self.mask = mask
        self.lengthmask = 2**(length+1)-1
    def next(self):
        nextdata = (self.init << 1) & self.lengthmask 
        i = self.init & self.mask & self.lengthmask 
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        nextdata ^= output
        self.init = nextdata
        return output
    def random(self, nbit):
        output = 0
        for _ in range(nbit):
            output <<= 1
            output |= self.next()
        return output
def padbin(x,b):
    s=bin(x)[2:]
    s='0'*(b-len(s))+s
    return s
#------MAIN---BELOW------#
sh=remote("182.92.108.71",30607)
arr=[]
lj=[5,22,23]
for i in range(10):
    sh.recvuntil("guess: ")
    sh.sendline('0')
    judge=sh.recvline(keepends=False)
    assert len(judge) in lj
    if len(judge)==5:
        arr.append(0)
    else:
        arr.append(int(judge[21:]))
print(arr)
mask = 0xb28a108ef5
N = 40
key = ''
for i in arr:
    key+=padbin(i,4)
idx = 0
ans = ""
key = key[39] + key[:40]
while idx < 40:
    tmp = 0
    for i in range(40):
        if mask >> i & 1:
            tmp ^= int(key[39 - i])
    ans = str(tmp) + ans
    idx += 1
    key = key[39] + str(tmp) + key[1:39]
num = int(ans, 2)
print(hex(num))
prng=LXFIQNN(num, mask, 40)
anses=[]
for i in range(300):
    anses.append(prng.random(4))
assert anses[0:10]==arr
for i in range(10,100):
    tr1=sh.recvline(keepends=False)
    print(str1)
    sh.recvuntil("guess: ")
    sh.sendline(str(anses[i]))
    str1=sh.recvline(keepends=False)
    print(str1)
flag=sh.recvline(keepends=False)
print(flag)
#hgame{lfsr_121a111y^use-in&crypto}