糖醋小鸡块的blog
0%

2023-网信柏鹭杯-wp-crypto

发表于 更新于 分类于 Valine：

因为队伍三个人全部忘记报名了，所以并没有参加这场比赛，但赛后有师傅问密码题，就做了一下。包含全三道题目的wp，但是第三道并不能百分百确定得到的flag正确，如有错误欢迎师傅提出！

fractrsa

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#python3
import sys 
sys.path.append("..") 
from Crypto.Util.number import *
from random import *
from sage.all import *
from  secret import flag1 as flag

num1 = 3
num2 = 5
while(num1<num2):
    num1 = getPrime(512)
    num2 = getPrime(512)
pt = bytes_to_long(flag) + num2

ring = RealField(1100)
num3 = ring(num1) / ring(num2)
print("num3 = ", num3)

while True:
    p = randint(2**511, num1)
    q = randint(2**511, num2)
    if isPrime(p) and isPrime(q) and p!=q:
        break
 
N = p*q
e = 65537
leak = pow(p-q, num1, num1*num2)
ct = pow(pt, e, N)

print("ct = ", ct)
print("N = ", N)
print("leak = ", leak)

"""
num3 = 1.23389923415003373900567515471436168841941584796842188964423737295914869304653496800649965063081353720701415762591488370228399019899893688681309320356016722276295236528757306976510687729729934668311830828756908988350841843676900575414367123810470585198055372776278588638204471298838884740198056387082949710435502826460830711429956
ct = 31011170589632318837149853165664224847925206003567781692767655474759523146503572164952138829336342836023903919700264739071138739105931471740973631326608186969523753119546323993892359278563753903149741128282349467136720827132122619177620866305659196267641453819504766216964516467658995724859657544518337771393
N = 61860727516406742636690805639158184396057779906729165734489212939937929906456706343476469874085504076991779041906401043694401076841639925611957258119417559980829238154105119701407722069260962772947894516879731956778127512764229384957918619863998939985369399189275568362193066167855420897196095587732512368673
leak = 23213363443983005040318061737977092634638640953366787443691593387275645092922646169818923792205696350020369122807136306157118385984272980615310163206933078119776935167207473544453080959202803743994251355133953187110546017667004996272367137522351606700447920805532616096125523674597551449412004735397779511371
"""

题目名明示了用连分数解题，正好前几天也有师傅问起过安洵杯的一道题目，其实就是用sage内置函数，将该高精度小数进行连分数展开，加上比特数及素数的限制就能找到精确的num1、num2。

找到num1、num2后，有两种办法解决下一个问题，问题形式是：

第一种方法，其实就是当作普通RSA解密就可以，因为num1、num2其实就是p、q，只是这里的e变成num1而已，本质解密一样。

第二种方法推导如下，由同余性质先转到模num1下：

然后费马小定理：

又因为 p-q 显然小于num1，那么直接将leak模num1就能得到p-q(当然如果p<q，那么得到的其实是p-q+num1，需要对应做一点小处理)。

然后解方程就能得到n的分解，进而解密密文，注意最后解密还要减掉一个num2。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from Crypto.Util.number import *
from gmpy2 import iroot

e = 65537
num3 = 1.23389923415003373900567515471436168841941584796842188964423737295914869304653496800649965063081353720701415762591488370228399019899893688681309320356016722276295236528757306976510687729729934668311830828756908988350841843676900575414367123810470585198055372776278588638204471298838884740198056387082949710435502826460830711429956
ct = 31011170589632318837149853165664224847925206003567781692767655474759523146503572164952138829336342836023903919700264739071138739105931471740973631326608186969523753119546323993892359278563753903149741128282349467136720827132122619177620866305659196267641453819504766216964516467658995724859657544518337771393
N = 61860727516406742636690805639158184396057779906729165734489212939937929906456706343476469874085504076991779041906401043694401076841639925611957258119417559980829238154105119701407722069260962772947894516879731956778127512764229384957918619863998939985369399189275568362193066167855420897196095587732512368673
leak = 23213363443983005040318061737977092634638640953366787443691593387275645092922646169818923792205696350020369122807136306157118385984272980615310163206933078119776935167207473544453080959202803743994251355133953187110546017667004996272367137522351606700447920805532616096125523674597551449412004735397779511371

c = continued_fraction(num3)
print(c)
 
alist = c.convergents()
 
for i in alist:
    a = str(i).split('/')
    if len(a)>1 and gcd(int(a[0]),int(a[1])) == 1 and is_prime(int(a[0])) and is_prime(int(a[1])) and int(a[0]).bit_length()==512 and int(a[1]).bit_length()==512:
        num1 = int(a[0])
        num2 = int(a[1])

p_q = leak % num1
pplusq = iroot(p_q**2+4*N,2)[0]
p = (p_q + pplusq) // 2
q = N // p
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(int(pow(ct,d,N) - num2)))

#flag{ISEC-WeMu5tKe2pOn_70in5And#N3Ver@G1veUp!}



Vigenere2S

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# -*- coding: utf-8 -*-
# python2

import sys
sys.path.append("..") 
from secret import key,flag2 as flag

def _l(idx, s):
    return s[idx:] + s[:idx]
def mainProc(p, k1, k2):
    s = b"abcd07efghij89klmnopqr16stuvwxyz-_{}ABCDEFGHIJKL34MNOPQRST25VWXYZ"
    t = [[_l((i+j)%len(s), s) for j in range(len(s))] for i in range(len(s))]
    i1 = 0
    i2 = 0
    c = b""
    for a in p:
        c += t[s.find(a)][s.find(k1[i1])][s.find(k2[i2])]
        i1 = (i1 + 1) % len(k1)
        i2 = (i2 + 1) % len(k2)
    return c
res = mainProc(flag,key,key[::-1])
print(res)
#6JnsNxHKJ8mkvhS{rMO_c9apMfHDHObq80PMu{_ww_r{rq

题目名暗示是一种变种维吉尼亚，不过其实仔细看会发现变了个寂寞。

首先要发现，t表是能确定的，重要的在于这个加密过程怎么去理解：

1
c += t[s.find(a)][s.find(k1[i1])][s.find(k2[i2])]

不要被这个三重表吓到了，其实三层作用一模一样，都是将码表右移该字符在码表中对应位置的位数！再来多少层都是一样的。

什么意思呢？比如说，当前明文字符为”f”，在s中下标为7，假设k1[i1]当前为”a”，k2[i2]当前为”b”，下标分别是0、1，那其实加密过程做的事情，就是找s中，下标为(7+0+1)的字符作为密文字符。当然，这是循环右移的，因此要模上s的长度65。

其实很好理解，因为三层循环的每一层都是在当前移动位置上，再相对移动该字符在s中的绝对下标，注意是在s中的绝对下标！

也就是说，加密过程完全等价于：

1
c += long_to_bytes(s[(s.find(a) + s.find(k1[i1]) + s.find(k2[i2])) % 65])

看出来了吗？把后面的两个密钥之和当作一个完整的密钥，那么这其实就是一个在s码表上的维吉尼亚加密。

而我们现在已经有了flag头”flag{ISEC-}”，共十个字符，和密文相减就能得到十个密钥和，接下来的一点也很重要：我们只需要密钥和，而不需要两个密钥分别的值。

而密钥和是首尾相加的，那么假设密钥长度为10，会发生什么？

很显然，密钥和的前五个会和后五个呈对称形式。这是因为第一个密钥和由密钥的第1、10个字符相加得到，第二个密钥和由第2、9个字符相加得到，而你能想到，到第六个密钥和，他就会和第五个产生重复，而这种重复是我们能看出来的。

而实际上相减，得到的前十个密钥和序列如下：

1
[16, 30, 17, 16, 17, 50, 52, 6, 7, 45]

并没有产生对称，这说明什么呢？这说明密钥长度至少为19及以上(为什么能是19也很好想通)，那假设密钥长度为19，我们就能得到完整的密钥和序列：

1
[16, 30, 17, 16, 17, 50, 52, 6, 7, 45, 7, 6, 52, 50, 17, 16, 17, 30, 16]

然后拿去解密(解密就是相应的减去对应密钥和)，发现并不正确，那就重新试密钥长度为20，就能得到正确flag。

当然如果还不行，就得继续往下爆破，但由于密钥和的对称性，密钥长度即使到30左右，也是可以接受的爆破范围(因为只需要爆破几个未知的对称的密钥和，而非密钥本身)，也是可以实现的。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
import string 

def _l(idx, s):
    return s[idx:] + s[:idx]

#length = 65
s = b"abcd07efghij89klmnopqr16stuvwxyz-_{}ABCDEFGHIJKL34MNOPQRST25VWXYZ"
temp = b""
t = [[_l((i+j)%len(s), s) for j in range(len(s))] for i in range(len(s))]

c = b"6JnsNxHKJ8mkvhS{rMO_c9apMfHDHObq80PMu{_ww_r{rq"
tt1 = [s.find(i) for i in c]
m = b"flag{ISEC-"
tt2 = [s.find(i) for i in m]

k = []
for i in range(len(tt2)):
    k.append((tt1[i] - tt2[i]) % 65)
k = k + k[::-1]
for i in range(len(c)):
    print(chr(s[(s.find(c[i]) - k[i%len(k)]) % 65]),end = "")

#flag{ISEC-Afr1en7_1nN33d_1S_Afr9end_ind88d0o0}



Stream

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#python2
import sys 
sys.path.append("..") 
from secret import Encode_Base64,plain,flag3 as flag

assert flag.startswith("flag{ISEC-")
assert flag.endswith("}")
assert len(flag)==32

def lfsr(R,mask):
    output = (R << 1) & 0xfffffff
    i = (R&mask)&0xfffffff
    lastbit = 0
    while i!=0:
        lastbit ^= (i&1)
        i = i>>1
    output ^= lastbit
    return (output,lastbit)


def single_round(R1,R1_mask,R2,R2_mask,R3,R3_mask):
    (R1_NEW,x1) = lfsr(R1,R1_mask)
    (R2_NEW,x2) = lfsr(R2,R2_mask)
    (R3_NEW,x3) = lfsr(R3,R3_mask)
    return (R1_NEW,R2_NEW,R3_NEW,(x1*x2)^((x2^1)*x3))

R1=int(flag[10:16],16)
R2=int(flag[16:25],16)
R3=int(flag[25:31],16)
assert len(bin(R1)[2:])==19
assert len(bin(R2)[2:])==26
assert len(bin(R3)[2:])==21
R1_mask = 0x4100c
R2_mask = 0x2000023
R3_mask = 0x100002

tmp1kb = ""
for j in range(100):
    tmp=0
    for k in range(8):
        (R1,R2,R3,out)=single_round(R1,R1_mask,R2,R2_mask,R3,R3_mask)
        tmp = (tmp << 1) ^ out
    tmp1kb += chr(tmp)

encode1 = Encode_Base64(plain)
encode2 = Encode_Base64(tmp1kb)

with open("result.txt","w") as f:
    f.write("plain:  " + plain + "\n")
    f.write("EnText: " + encode1 + "\n\n")
    f.write("CipherText:\n" + encode2)

#输出：
plain:  I Try not to become a man of success but rather try to become a man of value.
EnText: rrgtYXkcVD91HCqvHBIFSN9pTrgdHB2dVegvTegzZRKjToKzHBI2ZhgxSoqEToHcZCI7HCqvHBIFSN9pTrgdHB2dVegvTegNSRW2Tr6=

CipherText:
AqMY/UnTRJnJk1iwDQrJ/ahALlOcA8Qp5AEgmJjNyffSdoN2i7SLpOiAYlC+CEDfEXJCfng5CogfXQ5sJjEg0CtIHvDaeBh/qkaZlGWjJVC50MCJ9o5I3gdlUrS8yinnfaxbwP==

梳理一下题目加密流程：

  • 从secret中导入flag串、plain以及一个自定义的base64加密
  • 将题目中的flag串去除首尾，并拆分为三节，作为三个不同LFSR的流密钥种子
  • 将三个LFSR结合，生成一段长度为800比特位的密文(如何结合的一会儿会展开说一下)。然后将这段密文用自定义的base64加密，并给出密文
  • 同时，给出了一段已知明文的自定义base64加密结果

那么该怎么还原flag串呢？首先知道，flag串被拆分成三段，作为三个LFSR的种子，那么要想通过LFSR恢复这些种子，就要先知道LFSR的密文，也就是先解决自定义的base64，把Ciphertext段还原回原比特串。

那么接下来开始题目分析：

base64

题目给了一段明文plain，如果正常进行base64加密，结果如下面第一行，第二行是题目自定义的base64加密结果：

1
2
SSBUcnkgbm90IHRvIGJlY29tZSBhIG1hbiBvZiBzdWNjZXNzIGJ1dCByYXRoZXIgdHJ5IHRvIGJlY29tZSBhIG1hbiBvZiB2YWx1ZS4=
rrgtYXkcVD91HCqvHBIFSN9pTrgdHB2dVegvTegzZRKjToKzHBI2ZhgxSoqEToHcZCI7HCqvHBIFSN9pTrgdHB2dVegvTegNSRW2Tr6=

可以看出，实际上是进行了一次单表代换，那么我们可以打印出正常base64表与自定义base64表的对应关系：

1
2
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=
*gh***BCHI***K***qr*t*RoST*VYZ**cdejkFDXE****p*v*Wxz12N*67***9**=

星号代表该字符无法通过已知的明密文对进行对应，这样的话，我们一共找出了38组对应关系。然而，给出的Ciphertext有59种不同字符，因此我们已知的明密文对关系完全不够我们还原Ciphertext，并且爆破的复杂度也是不可接受的。那么该怎么处理呢？

base64的分析就先到这里，一会儿会接着说。

LFSR

题目中，由三个不同的掩码mask，定义了三个不同的LFSR，具体来说，三个LFSR可以写作：

1
2
3
4
5
6
7
8
9
10
11
12
13
#LFSR
R1_mask = 0x4100c
R2_mask = 0x2000023
R3_mask = 0x100002

def lfsr1(R):
    return ((R >> 2) & 1) ^ ((R >> 3) & 1) ^ ((R >> 12) & 1) ^ ((R >> 18) & 1)

def lfsr2(R):
    return (R & 1) ^ ((R >> 1) & 1) ^ ((R >> 5) & 1) ^ ((R >> 25) & 1)

def lfsr3(R):
    return ((R >> 1) & 1) ^ ((R >> 20) & 1)

而密文的比特串流是怎么产生的呢？每一个密文比特位ci，都需要三个LFSR分别生成一位比特位，分别记作x1,x2,x3，然后ci就由如下方式产生：

1
ci = (x1*x2)^((x2^1)*x3)

也就是说，三个LFSR在同时进行递推，生成自己的新的比特位，但是密文是由三个LFSR的各自的新的比特位，用上述方式生成的。

那么如果已知密文流，如何还原三个种子呢？z3可以直接搞定，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def lfsr1(R):
    return ((R >> 2) & 1) ^ ((R >> 3) & 1) ^ ((R >> 12) & 1) ^ ((R >> 18) & 1)

def lfsr2(R):
    return (R & 1) ^ ((R >> 1) & 1) ^ ((R >> 5) & 1) ^ ((R >> 25) & 1)

def lfsr3(R):
    return ((R >> 1) & 1) ^ ((R >> 20) & 1)

def z3_sol():
    R1 = BitVec('R1',28)
    R2 = BitVec('R2',28)
    R3 = BitVec('R3',28)
    sol = Solver()
    sol.add(R1 >> 18 == 1)
    sol.add(R2 >> 25 == 1)
    sol.add(R3 >> 20 == 1)    
    for i in range(200):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    if(sol.check() == sat):
        print(sol.model())

z3_sol()

可以自己生成几组数据验证一下，比如我这里选定 R1 = 373763; R2 = 62865560; R3 = 1502599，满足题目要求，然后用题目给的加密函数进行加密(不进行base64换表)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#python2

def lfsr(R,mask):
    output = (R << 1) & 0xfffffff
    i = (R&mask)&0xfffffff
    lastbit = 0
    while i!=0:
        lastbit ^= (i&1)
        i = i>>1
    output ^= lastbit
    return (output,lastbit)


def single_round(R1,R1_mask,R2,R2_mask,R3,R3_mask):
    (R1_NEW,x1) = lfsr(R1,R1_mask)
    (R2_NEW,x2) = lfsr(R2,R2_mask)
    (R3_NEW,x3) = lfsr(R3,R3_mask)
    return (R1_NEW,R2_NEW,R3_NEW,(x1*x2)^((x2^1)*x3))

R2 = 62865560; R1 = 373763; R3 = 1502599
assert len(bin(R1)[2:])==19
assert len(bin(R2)[2:])==26
assert len(bin(R3)[2:])==21
R1_mask = 0x4100c
R2_mask = 0x2000023
R3_mask = 0x100002

tmp1kb = ""
for j in range(100):
    tmp=0
    for k in range(8):
        (R1,R2,R3,out)=single_round(R1,R1_mask,R2,R2_mask,R3,R3_mask)
        tmp = (tmp << 1) ^ out
    tmp1kb += str(bin(tmp)[2:].zfill(8))

print(tmp1kb)

然后试试刚才写的解密函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from Crypto.Util.number import *
from z3 import *

#用他给的LFSR，将R1、R2、R3加密得到的二进制串
cipher = "01101100011100101001001011010010110101011100110010101000100001011100100010010011011001111010000010100011110011110010111110111110001111000110001100010010010001111000010111101001111010011100100100010110110110101100000000101010010100110111101101001000001111001110001011011111001011010011010111010100110011011111000011000111011100010100011110001101111100111100010110000010100010111111101100101011001010010101010011100101110010001000000110010101101010101110011101101001001010110100001111100000101011111010011001110011001100000110100010111001111101100111101111111101110010101000010110100111110010010001110000110000110111110101111000001111001001111111100000010001101011010110000111010110101010001100010001010000101101110101011010010011000100100010111011100101111010111101000110011000001110111011111110100101"

def lfsr1(R):
    return ((R >> 2) & 1) ^ ((R >> 3) & 1) ^ ((R >> 12) & 1) ^ ((R >> 18) & 1)

def lfsr2(R):
    return (R & 1) ^ ((R >> 1) & 1) ^ ((R >> 5) & 1) ^ ((R >> 25) & 1)

def lfsr3(R):
    return ((R >> 1) & 1) ^ ((R >> 20) & 1)

def z3_sol():
    R1 = BitVec('R1',28)
    R2 = BitVec('R2',28)
    R3 = BitVec('R3',28)
    sol = Solver()
    sol.add(R1 >> 18 == 1)
    sol.add(R2 >> 25 == 1)
    sol.add(R3 >> 20 == 1)    
    for i in range(200):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    if(sol.check() == sat):
        print(sol.model())

z3_sol()

你会发现确实可以正确解密，那么LFSR的这一部分我们就解决了。也就是说，只要我们能得到密文流，我们就能用z3还原出明文。

那么又回到了刚才的问题，也就是如何解决换表的base64。

综合分析

实际上，仔细看刚才的LFSR解密函数，你可以发现，它实际上只使用了密文的两百个比特位就能完全正确的解密。而不管base64换不换表，其一个字符都对应6比特位，也就是说，给定的Ciphertext远远超过了我们需要的数量，所以我们其实并不需要完全还原Ciphertext，只需要前一部分就好了。

但其实经过我的测试，都不需要200比特位，实际上只要有78个密文比特位，就能很精确地还原出三个种子。也就是说，我们只需要还原Ciphertext其中的13个base64字符就能反推出种子，这就又很大程度减少了工作量。我们把Ciphertext前面一小段中已知的换表给代换回去，未知的用星号表示，可以发现他长这样：

1
*R*c***ZW***k0**m*S***C****g***t**oB

如何处理呢？其实我们直接把未知的跳过，只添加确定部分作为约束就好了，就像下面这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
def z3_sol(cipher):
    R1 = BitVec('R1',28)
    R2 = BitVec('R2',28)
    R3 = BitVec('R3',28)
    sol = Solver()
    sol.add(R1 >> 18 == 1)
    sol.add(R2 >> 25 == 1)
    sol.add(R3 >> 20 == 1)
    for i in range(6):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(6):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+6])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(6):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(6):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+18])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(18):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(12):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+42])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(18):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(12):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+72])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(12):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(6):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+96])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(6):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(6):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+108])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(18):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(6):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+132])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(24):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(6):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+162])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(18):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(6):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+186])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(12):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(12):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+204])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)    
    if(sol.check() == sat):
        print(sol.model())

这样就能求解出唯一一组符合要求的解，也就是种子。有了种子后，十六进制恢复就行，当然要注意填充的0。

但是解出的flag并不是一个有意义的字符串，只是个十六进制串，怎么验证其正确性呢？其实简单，把求出的三个种子用题目给定的加密方式加密一遍，然后再将已知部分换表即可，验证函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
def lfsr(R,mask):
    output = (R << 1) & 0xfffffff
    i = (R&mask)&0xfffffff
    lastbit = 0
    while i!=0:
        lastbit ^= (i&1)
        i = i>>1
    output ^= lastbit
    return (output,lastbit)


def single_round(R1,R1_mask,R2,R2_mask,R3,R3_mask):
    (R1_NEW,x1) = lfsr(R1,R1_mask)
    (R2_NEW,x2) = lfsr(R2,R2_mask)
    (R3_NEW,x3) = lfsr(R3,R3_mask)
    return (R1_NEW,R2_NEW,R3_NEW,(x1*x2)^((x2^1)*x3))

R2 = 49589048;R1 = 381342; R3 = 1862135
assert len(bin(R1)[2:])==19
assert len(bin(R2)[2:])==26
assert len(bin(R3)[2:])==21
R1_mask = 0x4100c
R2_mask = 0x2000023
R3_mask = 0x100002

tmp1kb = ""
for j in range(100):
    tmp=0
    for k in range(8):
        (R1,R2,R3,out)=single_round(R1,R1_mask,R2,R2_mask,R3,R3_mask)
        tmp = (tmp << 1) ^ out
    tmp1kb += str(bin(tmp)[2:].zfill(8))

print(tmp1kb)
en_64 = "rrgtYXkcVD91HCqvHBIFSN9pTrgdHB2dVegvTegzZRKjToKzHBI2ZhgxSoqEToHcZCI7HCqvHBIFSN9pTrgdHB2dVegvTegNSRW2Tr6="
pl_64 = "SSBUcnkgbm90IHRvIGJlY29tZSBhIG1hbiBvZiBzdWNjZXNzIGJ1dCByYXRoZXIgdHJ5IHRvIGJlY29tZSBhIG1hbiBvZiB2YWx1ZS4="
dic = {}
for i in range(len(pl_64)):
    dic[pl_64[i]] = en_64[i]
t4ble = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
for i in range(len(tmp1kb) // 6):
    try:
        print(dic[t4ble[int(tmp1kb[6*i:6*i+6],2)]],end = "")
    except:
        print("*",end = "")
print()

tt = "AqMY/UnTRJnJk1iwDQrJ/ahALlOcA8Qp5AEgmJjNyffSdoN2i7SLpOiAYlC+CEDfEXJCfng5CogfXQ5sJjEg0CtIHvDaeBh/qkaZlGWjJVC50MCJ9o5I3gdlUrS8yinnfaxbwP=="
print(tt)

结果如下：

1
2
*q*Y***TR***k1**D*r***h****c***p**Eg**jN***SdoN2*7S*p***Y*C*CED*EX*C**g*Cog*X****jEg*CtIHvD*eBh*qk*Z**Wj*VC***C*9o*I*gd**rS*******x**
AqMY/UnTRJnJk1iwDQrJ/ahALlOcA8Qp5AEgmJjNyffSdoN2i7SLpOiAYlC+CEDfEXJCfng5CogfXQ5sJjEg0CtIHvDaeBh/qkaZlGWjJVC50MCJ9o5I3gdlUrS8yinnfaxbwP==

可以看到，对应位置的换表是完全对的上的，包括我们没有用到的后半部分，因此flag应该是正确了。

完整exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
from Crypto.Util.number import *
from z3 import *

#用他给的LFSR，将R1、R2、R3加密得到的二进制串
#cipher = "01101100011100101001001011010010110101011100110010101000100001011100100010010011011001111010000010100011110011110010111110111110001111000110001100010010010001111000010111101001111010011100100100010110110110101100000000101010010100110111101101001000001111001110001011011111001011010011010111010100110011011111000011000111011100010100011110001101111100111100010110000010100010111111101100101011001010010101010011100101110010001000000110010101101010101110011101101001001010110100001111100000101011111010011001110011001100000110100010111001111101100111101111111101110010101000010110100111110010010001110000110000110111110101111000001111001001111111100000010001101011010110000111010110101010001100010001010000101101110101011010010011000100100010111011100101111010111101000110011000001110111011111110100101"

def lfsr1(R):
    return ((R >> 2) & 1) ^ ((R >> 3) & 1) ^ ((R >> 12) & 1) ^ ((R >> 18) & 1)

def lfsr2(R):
    return (R & 1) ^ ((R >> 1) & 1) ^ ((R >> 5) & 1) ^ ((R >> 25) & 1)

def lfsr3(R):
    return ((R >> 1) & 1) ^ ((R >> 20) & 1)

def z3_sol(cipher):
    R1 = BitVec('R1',28)
    R2 = BitVec('R2',28)
    R3 = BitVec('R3',28)
    sol = Solver()
    sol.add(R1 >> 18 == 1)
    sol.add(R2 >> 25 == 1)
    sol.add(R3 >> 20 == 1)
    for i in range(6):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(6):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+6])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(6):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(6):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+18])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(18):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(12):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+42])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(18):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(12):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+72])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(12):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(6):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+96])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(6):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(6):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+108])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(18):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(6):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+132])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(24):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(6):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+162])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(18):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(6):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+186])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    for i in range(12):
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)   
    for i in range(12):
        sol.add((lfsr1(R1)*lfsr2(R2))^((lfsr2(R2)^1)*lfsr3(R3)) == cipher[i+204])
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)    
    if(sol.check() == sat):
        print(sol.model())

cc = "*R*c***ZW***k0**m*S***C****g***t**oB" 
t4ble = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
cipher = ""
for k in cc:
    if(k in t4ble):
        cipher += bin(t4ble.index(k))[2:].zfill(6)
    else:
        cipher += "000000"
z3_sol(cipher)

#R2 = 49589048, R1 = 381342, R3 = 1862135
R2 = 49589048;R1 = 381342; R3 = 1862135
print("flag{ISEC-",end = "")
print("0" + hex(R1)[2:],end = "")
print("00" + hex(R2)[2:],end = "")
print(hex(R3)[2:],end = "")
print("}")



#以下为验证部分
'''
def lfsr(R,mask):
    output = (R << 1) & 0xfffffff
    i = (R&mask)&0xfffffff
    lastbit = 0
    while i!=0:
        lastbit ^= (i&1)
        i = i>>1
    output ^= lastbit
    return (output,lastbit)


def single_round(R1,R1_mask,R2,R2_mask,R3,R3_mask):
    (R1_NEW,x1) = lfsr(R1,R1_mask)
    (R2_NEW,x2) = lfsr(R2,R2_mask)
    (R3_NEW,x3) = lfsr(R3,R3_mask)
    return (R1_NEW,R2_NEW,R3_NEW,(x1*x2)^((x2^1)*x3))

R2 = 49589048;R1 = 381342; R3 = 1862135
assert len(bin(R1)[2:])==19
assert len(bin(R2)[2:])==26
assert len(bin(R3)[2:])==21
R1_mask = 0x4100c
R2_mask = 0x2000023
R3_mask = 0x100002

tmp1kb = ""
for j in range(100):
    tmp=0
    for k in range(8):
        (R1,R2,R3,out)=single_round(R1,R1_mask,R2,R2_mask,R3,R3_mask)
        tmp = (tmp << 1) ^ out
    tmp1kb += str(bin(tmp)[2:].zfill(8))

print(tmp1kb)
en_64 = "rrgtYXkcVD91HCqvHBIFSN9pTrgdHB2dVegvTegzZRKjToKzHBI2ZhgxSoqEToHcZCI7HCqvHBIFSN9pTrgdHB2dVegvTegNSRW2Tr6="
pl_64 = "SSBUcnkgbm90IHRvIGJlY29tZSBhIG1hbiBvZiBzdWNjZXNzIGJ1dCByYXRoZXIgdHJ5IHRvIGJlY29tZSBhIG1hbiBvZiB2YWx1ZS4="
dic = {}
for i in range(len(pl_64)):
    dic[pl_64[i]] = en_64[i]
t4ble = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
for i in range(len(tmp1kb) // 6):
    try:
        print(dic[t4ble[int(tmp1kb[6*i:6*i+6],2)]],end = "")
    except:
        print("*",end = "")
print()

tt = "AqMY/UnTRJnJk1iwDQrJ/ahALlOcA8Qp5AEgmJjNyffSdoN2i7SLpOiAYlC+CEDfEXJCfng5CogfXQ5sJjEg0CtIHvDaeBh/qkaZlGWjJVC50MCJ9o5I3gdlUrS8yinnfaxbwP=="
print(tt)
'''

#flag{ISEC-05d19e002f4ab381c69f7}

如果各位师傅发现解法中的错误，可以随时联系我，同时各位师傅有其他任何问题也欢迎与我交流！