密码学学习笔记之 CTF

Van1sh 密码小屋/ CTF CTF

创建时间:2020-12-18 00:00

字数:5k 阅读:

2020蓝帽杯-RSA
2021湖湘杯-firstot
2021-L3HCTF-EzECDSA
2021-西湖论剑-SpecialCurve2
2021-西湖论剑-FilterRandom

这里是对在CTF比赛中遇见到的自认为比较好的一些题目的收集。有一些在比赛小屋就已经做了分析的，这里可能只会提一手，主要是分析那些落单的但不错的题目。

2020祥云杯-more_calc

import gmpy2
from Crypto.Util.number import *


flag = b"flag{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}"


p = getStrongPrime(2048)
for i in range(1, (p+1)//2):
    s += pow(i, p-2, p)
s = s % p
q = gmpy2.next_prime(s)
n = p*q
e = 0x10001
c = pow(bytes_to_long(flag), e, n)
print(p)
print(c)

是魔改的奥数题(2012年新加坡数学奥林匹克)，可恶，欺负人。

已经有大佬做了预期解的分析了。

由于模数为素数p，所以阶为p-1，所以p-2其实就相当于-1，即题目要求计算

$1^{-1}+2^{-1}+\dots+(\frac{p-1}{2})^{-1} \pmod p $

然后由于一个组合数的性质$C^{2i}_p = \frac{p(p-1)(p-2)\dots(p-(2i-1))}{(2i)!}$

$\frac{2i}{p}C^{2i}_p = \frac{(p-1)(p-2)\dots(p-(2i-1))}{(2i-1)!}\equiv \frac{(-1)(-2)\dots(-(2i-1))}{(2i-1)!}\equiv -1 \pmod p$

所以有$\sum_\limits{i=1}^{\frac{p-1}{2}}i^{-1}=-\sum_\limits{i=1}^{\frac{p-1}{2}}i^{-1}\frac{2i}{p}C^{2i}_p=-\frac{2}{p}\sum_\limits{i=1}^{\frac{p-1}{2}}C^{2i}_p$

注意到$\sum_\limits{i=1}^{\frac{p-1}{2}}C^{2i}_p$从意义上代表从p个元素中取出偶数个元素的方法。由于p是奇数，所以从p个元素中取出偶数个元素的方法数等于从p个元素中取出奇数个元素的方法数，且二者之和为从p中取出元素的方法数$2 ^ p$（这我没证，不过随便测了下是这样的）。由于没有计算取出0个元素的情况，所以此处有$\sum_\limits{i=1}^{\frac{p-1}{2}}C^{2i}_p = 2^{p-1}-1$

即$\sum_\limits{i=1}^{\frac{p-1}{2}}i^{-1}\equiv -\frac{2}{p}(2^{p-1}-1)\equiv -(\frac{2^p-2}{p})\pmod p $

单单这么看会有个大问题，就是，模p的话，$2^{p}$不是等于2么，2-2=0，那么就是0除0了呀。

实际代码操作是这样的：s = p - (pow(2, p, p*p)-2)//p

这么去理解，式子的意思可以看成先运算(整除)，最后取余，但是如果真的去这么运算，由于p太大，从而导致$2^p$也过于巨大了，所以需要做一些优化。

我们可以类比到进制上，比如十进制，(看成p=10)，如果模100然后整除10，那么其实就是为了取得这个数十位上的数字，这等价于先整除10再模10，

再回到我们这里，先整除$p$，再模掉$p$，也即等价于，先模掉$p^2$，再整除$p$

所以最终预期解题代码

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
from sympy import nextprime

e = 65537
p = 
c = 

s = p - (pow(2, p, p*p)-2)//p
q = nextprime(s)
n = p*q
e = 0x10001
phi = (p-1)*(q-1)
d = inverse(e, phi)
print long_to_bytes(pow(c, d, n))

这道题的非预期好修复的，给flag做好padding，让flag>>p就好了。

（不如这个板块整成每日一题好了）

——记录于2020.12.18

2020蓝帽杯-RSA

#!/usr/bin/env python
from Crypto.Util.number import *
from secret import FLAG,HINT
assert len(HINT) < len(FLAG)
assert len(FLAG) == 38

p1 = getPrime(2048)
q1 = getPrime(2048)
n1 = p1*q1
e1 = 321959
e2 = 250261
c1 = pow(bytes_to_long(HINT),e1,n1)
c2 = pow(bytes_to_long(HINT),e2,n1)

print('n1={}'.format(n1))
print('c1={}'.format(c1))
print('c2={}'.format(c2))


p2 = getPrime(2048)
q2 = getPrime(2048)
n2 = p2*q2
e3 = 386321
e4 = 216437

flag = bytes_to_long(FLAG)*bytes_to_long(HINT)
c3 = pow(flag,e3,n2)
c4 = pow(flag,e4,n2)

print('n2={}'.format(n2))
print('c3={}'.format(c3))
print('c4={}'.format(c4))

这道题目比较简单，但也稍微有那么一点变型在里面。

首先是一个比较明显的共模攻击，但是这里还是需要对共模攻击以及$egcd$算法有一点理解，至少知道共模攻击的原理以及$egcd$算法的作用。

第一步如果跑正常的共模攻击的脚本的话，由于$gcd(e_1,e_2)=11$，所以得到的会是$hint^{11} \pmod n$，这里$hint^{11}$小于$n$，所以直接开11次根就好，拿到$hint$

然后第二步这里他的$flag$是$flag * hint$，同第一步一样，由于$gcd(e_3, e_4)=13$，这里用共模攻击得到会是$（flag * hint)^{13} \pmod n$ ，这里由于（$flag * hint) ^ {13} $大于$n$，所以直接开根就不能得到$flag * hint$。但这里因为我们已经知道$hint$的值了，我们可以先把结果乘以$hint^{13}$的逆，这样子得到的就是$flag^{13}$，最后给它开13次根就能得到$flag$了。

（水了一题，略略~）

——记录于2020.12.19

哈哈哈哈，笑死我了，没想到这里直接是咕咕咕了快一年才想起来还有这码子事，主要还是自己太懒了。

2021湖湘杯-firstot

#!/usr/bin/env python2.7
from libnum import n2s, s2n, xgcd
from random import getrandbits
from Crypto.Util.number import getPrime
from Crypto.Cipher import AES
from hashlib import sha256
import SocketServer
#from secret import flag
flag=b"vanish"

pad = lambda x: x + '$' * (16 - len(x) % 16) if len(x) % 16 else x
nbits = 128
MASK = 2 ** nbits - 1


def generate_key(nbits):
    e1 = 65537
    e2 = 92431
    p = getPrime(nbits // 2)
    q = getPrime(nbits // 2)
    while abs(p - q) < p >> 2:
        p = getPrime(nbits // 2)
        q = getPrime(nbits // 2)
    n = p * q
    phi = (p - 1) * (q - 1)
    d1 = xgcd(e1, phi)[0] % phi
    d2 = xgcd(e2, phi)[0] % phi
    return n, d1, d2


def decrypt(data, ski):
    if data.bit_length() < 128:
        exit(1)
    n, d0, d1 = ski
    k0 = pow(data, d0, n)
    k1 = pow(data, d1, n)

    return k0, k1


def verify(data, pubkey):
    if data.bit_length() < 128:
       exit(1)
    n, e0, e1 = pubkey
    ans0, ans1 = pow(data, e0, n), pow(data, e1, n)
    return ans0, ans1


def generate_k():
    cur = getrandbits(128)
    while cur < 2 ** 127:
        cur = getrandbits(128)

    return cur


def add(x, y):
    if y.bit_length() < 128:
        exit(1)
    return (x + y) ^ (x >> 53)


def xor(x, y):
    if y.bit_length() < 128:
        exit(1)
    return (x ^ y) ^ (x >> 53)


class ThreadedTCPServer(SocketServer.ThreadingMixIn, SocketServer.TCPServer):
    pass


class EncHandler(SocketServer.BaseRequestHandler):
    def handle(self):
        primate_key = generate_k()
        secret_key = generate_key(2048)
        n = secret_key[0]
        public_key = n, 65537, 92431

        self.request.sendall("Welcome to our OT system\n")
        self.request.sendall("Now you can choose what you wanna do\n")
        self.request.sendall("1. get a message from the two\n2. encrypt flag with your own data\n3. encrypt in another way\n")

        self.request.sendall("Your pubkey is: " + hex(n) + "\n")
        
        for _ in range(580):
            self.request.sendall('Input your choice\n')
            self.request.sendall("choice>")
            choice = self.request.recv(16).strip()
            if choice == '1':
                m = []
                for _ in range(8):
                    cur = getrandbits(32)
                    m.append(cur)
                m0 = (m[0] << 96) ^ (m[1] << 64) ^ (m[2] << 32) ^ m[3]
                m1 = (m[4] << 96) ^ (m[5] << 64) ^ (m[6] << 32) ^ m[7]
                self.request.sendall('If you wanna get mi, encrypt your key with ei\n')
                enc_key = int(self.request.recv(1024).strip(), 16)
                print(enc_key)
            
                t0, t1 = decrypt(enc_key, secret_key)
                ms = t0 ^ m0, t1 ^ m1
                self.request.sendall('Your message is ' + str(ms) + '\n')
                self.request.sendall("Don't worry, I don't know which message you have got!\n")
            
            elif choice == '2':
                self.request.sendall('Input your data.\n')
                data = int(self.request.recv(1024).strip(), 16)
                t = verify(data, public_key)
                cur_rand = getrandbits(128)
                cur_k = t[cur_rand & 1] ^ cur_rand
                key = sha256(n2s(add(primate_key, cur_k))).digest()[:16]
                aes = AES.new(key, AES.MODE_ECB)
                cipher = aes.encrypt(pad(flag)).encode('hex')
                self.request.sendall("Your cipher is: " + cipher + '\n')
            
            elif choice == '3':
                self.request.sendall('Input your data.\n')
                data = int(self.request.recv(1024).strip(), 16)
                t = verify(data, public_key)
                cur_rand = getrandbits(128)
                cur_k = t[cur_rand & 1] ^ cur_rand
                key = sha256(n2s(xor(primate_key, cur_k))).digest()[:16]
                aes = AES.new(key, AES.MODE_ECB)
                cipher = aes.encrypt(pad(flag)).encode('hex')
                self.request.sendall("Your cipher is: " + cipher + '\n')
            


if __name__ == "__main__":
    HOST, PORT = "0.0.0.0", 9999
    server = ThreadedTCPServer((HOST, PORT), EncHandler)
    server.serve_forever()

代码还蛮长的，大致描述的确实是一个ot（oblivious transfer）不经意传输。

整个流程大致如下图（其中data不能小于128bit）

然后我们看看怎么能拿到flag，

首先会接受一个你的信息，然后用public_key，调用verify函数，verify函数就是用两个公钥分别对你的这个小心进行加密，然后根据cur_rand的lsb去选择一条密文和cur_rand异或得到cur_k，cur_k和私钥primate_key走一个add函数，再hash一下作为aes的key去加密flag。

这里的cur_rand是getrandbits(128)，primate_key看到上面generate_k，

def generate_k():
    cur = getrandbits(128)
    while cur < 2 ** 127:
        cur = getrandbits(128)

    return cur

其实也是getrandbits(128)，再加上m0，m1也都是getrandbits(128)，所以这道题的做法显而易见了。

攻击这个OT来同时获取m0，m1，需要总共 624 * 32 / 128 / 2 = 78 次交互，然后我们就可以恢复当前MT19937的状态。

然后往前生成128bit（注意拼接顺序）得到primate_key，往后生成128bit得到cur_rand，啥都知道了，那就可以生成相应的aes_key，然后解密就好了。

至于同时获取m0，m1呢？原本打算发送0过去的，这样c就是0，t1,t2也都是0，直接就能把m0,m1都发送回来了。但是这里检查了data必须不小于128bit，那就发送n过去呗。EZ。

jio本就不写了，好麻烦哦，而且写出来应该也没法复用，下一题！

2021-L3HCTF-EzECDSA

import hashlib
import socketserver
import os,random,string
from hashlib import sha256
from Crypto.Util.number import *

#from SECRET import FLAG
FLAG = b"vanish"
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
a = 0
b = 7
xG = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
yG = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
h = 1
zero = (0,0)
G = (xG, yG)
kbits = 8

def add(p1, p2):
    if p1 == zero:
        return p2
    if p2 == zero:
        return p1
    (p1x,p1y),(p2x,p2y) = p1,p2
    if p1x == p2x and (p1y != p2y or p1y == 0):
        return zero
    if p1x == p2x:
        tmp = (3 * p1x * p1x + a) * inverse(2 * p1y , p) % p
    else:
        tmp = (p2y - p1y) * inverse(p2x - p1x , p) % p
    x = (tmp * tmp - p1x - p2x) % p
    y = (tmp * (p1x - x) - p1y) % p
    return (int(x),int(y))

def mul(n, p):
    r = zero
    tmp = p
    while 0 < n:
        if n & 1 == 1:
            r = add(r,tmp)
        n, tmp = n >> 1, add(tmp,tmp)
    return r

def sha256(raw_message):
    return hashlib.sha256(raw_message).hexdigest().encode()

def _sha256(raw_message):
    return bytes_to_long(hashlib.sha256(raw_message).digest())

class Task(socketserver.BaseRequestHandler):
    def proof_of_work(self):
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)]).encode()
        digest = sha256(proof)
        self.request.send(b"sha256(XXXX+%b) == %b\n" % (proof[4:],digest))
        self.request.send(b'Give me XXXX:')
        x = self.request.recv(10)
        x = x.strip()
        if len(x) != 4 or sha256(x+proof[4:]) != digest: 
            return False
        return True
    
    def recvall(self, sz):
        try:
            r = sz
            res = ""
            while r > 0:
                res += self.request.recv(r).decode()
                if res.endswith("\n"):
                    r = 0
                else:
                    r = sz - len(res)
            res = res.strip()
        except:
            res = ""
        return res.strip("\n")

    def dosend(self, msg):
        self.request.sendall(msg)

    def handle(self):
        try:
            #if not self.proof_of_work():
                #return

            dA = random.randrange(n)
            Public_key = mul(dA, G)
            self.dosend(str(Public_key).encode() + b'\n')
            
            for _ in range(100):
                self.dosend(b"Give me your message:\n")
                msg = self.recvall(100)
                hash = _sha256(msg.encode())
                k = random.randrange(n)
                kp = k % (2 ** kbits)
                P = mul(k, G)
                r_sig = P[0]
                k_inv = inverse(k, n)
                s_sig = (k_inv * (hash + r_sig * dA)) % n
                self.dosend(b"r = " + str(r_sig).encode() + b'\n')
                self.dosend(b"s = " + str(s_sig).encode() + b'\n')
                self.dosend(b"kp = " + str(kp).encode() + b'\n')
                self.dosend(b"hash = " + str(hash).encode() + b'\n')
            
            self.dosend(b"Give me dA\n")
            private_key = self.recvall(300)
            if int(private_key) == dA:
                self.dosend(FLAG)

        except:
            self.dosend(b"Something error!\n")
            self.request.close()

class ForkingServer(socketserver.ForkingTCPServer, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 23333
    server = ForkingServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

整个代码看下来，嗯，就是实现了一个ecdsa的签名算法，然后获取flag的方式是猜出他的私钥dA。提供的功能是一百次的签名服务，然后会给出每一次用的临时密钥的低8位。嗷，那就是一个HNP问题了。巧了，去年就是因为HNP问题第一次接触的格。也是XCTF的，XCTF2020-高校战役-NHP

那次用的是DSA，这次是ECDSA，大差不大的。那次的公式是 $k_i \equiv s_i^{-1}r_i \cdot x + s_i^{-1}H(m) \pmod{q}$

设$A_i = s_i^{-1}r_i,B_i = s_i^{-1}H(m)$，构造的格是$M = \begin{bmatrix} q & & & & & & \newline & q & & & & & \newline & &\ddots& & & & \newline & & & q & & & \newline A_1&A_2&\dots & A_t&K/q& & \newline B_1&B_2&\dots & B_t& & K & \newline \end{bmatrix}$

ECDSA和DSA的签名公式大差不大的，但这次给了k的低位kp,那么设高位为$k_i$，所以 $k_i \cdot 256 + kp \equiv s_i^{-1}r_i \cdot x + s_i^{-1}H(m) \pmod{n}$

设$A_i = 256^{-1} \cdot s_i^{-1}r_i,B_i = 256^{-1} \cdot [s_i^{-1}H(m)-kp]$

构造格$M = \begin{bmatrix} n \newline & n \newline & &\ddots\newline & & & n\newline A_1&A_2&\dots & A_t&K/n& & \newline B_1&B_2&\dots & B_t& & K & \newline \end{bmatrix}$，总体和上面一样，这里的$K = 2^{256-8}$

我们期望规约后的矩阵的第一行向量为 $\begin{bmatrix} k_1 & k_2 & \cdots & k_t & Kx/q & K \end{bmatrix}$，但是在经过题目的测试，发现规约后第一行的向量是$\begin{bmatrix} 0 & 0 & \cdots & 0 & K & 0 \end{bmatrix}$（它确实短，也确实存在于这个格中，没办法），于是我们看到第二行向量，发现第二行向量的最后一个值为$K$,那么这应该就是我们的目标向量。于是我们利用该向量倒数第二个值，乘以n，除以K，即可得到x，如果顺利的话。我们会发现，这个值有时候会是负数，我本地看了下，是负数的时候，x都大于n/2，所以大概规约的时候是规约出了-x，这样模长会再稍稍小一些。那我们再取个模n就能得到正确的x了。

核心代码如下：

alist = [...]
blist = [...]
M = Matrix(QQ , len(alist)+2 , len(alist)+2)
for i in range(len(alist)):
    M[i , i] = n
    M[len(alist) , i] = alist[i]
    M[len(alist)+1 , i] = blist[i]
M[len(alist) , len(alist)] = 2**(256-8)/n
M[len(alist)+1 , len(alist)+1] = 2**(256-8)
tmpM=M.LLL() 

dA = tmpM[1][-2] * n / 2^(256-8) % n

2021-西湖论剑-SpecialCurve2

from Crypto.Util.number import *
#from flag import flag
import random

def add(P1,P2):
    x1,y1=P1
    x2,y2=P2
    x3=(x1*x2-y1*y2)%n
    y3=(x1*y2+x2*y1)%n
    return (x3,y3)

def mul(P,k):
    assert k>=0
    Q=(1,0)
    while k>0:
        if k%2:
            k-=1
            Q=add(P,Q)
        else:
            k//=2
            P=add(P,P)
    return Q

def getMyPrime():
    while True:
        q=getPrime(88)
        p=2*q+1
        if isPrime(p):
            return p

e=getPrime(256)
n=getMyPrime()*getMyPrime()*getMyPrime()
print('n=%d'%n)

G=(1,1)
HINT=mul(G,e)
print('HINT=%s'%str(HINT))

x=bytes_to_long(flag[7:39])
y=bytes_to_long(flag[39:-1])
M=(x,y)
C=mul(M,e)
print('C=%s'%str(C))

这题直接上春哥的知乎吧，写的很详细了。

主要是一个$|z_2| = |z_1^e| = |z_1|^e => e\cdot G \equiv 2^e \pmod n$

然后用sagemath的log函数给e梭出来（n能分解）

接着是这个群的阶是$p^2-1$，春哥的知乎有详细证明。

有了阶，有了e，那就能算相应的d去解C获得flag了。

2021-西湖论剑-FilterRandom

import random
#from secret import init1,init2,flag
#assert flag==b'DASCTF{%d-%d}'%(init1,init2)

class lfsr():
    def __init__(self, init, mask, length):
        self.init = init
        self.mask = mask
        self.lengthmask = 2**length-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 my_filter(c1,c2):
    if random.random()>0.1:
        return str(c1)
    else:
        return str(c2)

N=64
mask1=random.getrandbits(N)
mask2=random.getrandbits(N)
print(mask1)
print(mask2)
l1=lfsr(init1,mask1,N)
l2=lfsr(init2,mask2,N)
output=''
for i in range(2048):
    output+=my_filter(l1.next(),l2.next())
print(output)

这个题还挺有意思的，算是对LFSR的认识又深刻了一丢丢。

之前一直以为觉得lfsr是把头输出，把计算出来的往后拼。原来是把计算出来的输出，并且往后拼（其实差别也不大，就是前者会把seed输出出来，后者不会。）

看到这一题，可以看作是有两个随机数生成器l1，l2。两个随机数生成器生成对应的流，然后最终得输出是以不等得概率去从这两条流里面去选。这个不等得概率就比较关键了。这里选择l1的概率是0.9，选择2的概率是0.1。如果我们能有连续的64bit来自于l1的输出我们就能恢复init1了。算一下概率是0.9^64 = 0.1%，这概率也太小了。但其实不应该这么去算。我们并不需要说64bit全部来自于l1，其实只要64bit与l1相等就可以了。那么，这里还有0.1的概率选到l2，我们认为l2和l1相同的概率是50%，那么我们又能加0.05，所以概率从0.9来到了0.95，再算一下0.95^64 = 3.7%，那么这个概率就蛮大了。一共有2048bit的输出，连续的64bit块有2048-64 = 1984块，3.7%的概率来一块不算过分叭。

我们对每一块进行尝试，计算其init1，然后生成2048bit的流，与output对比，如果相似度达到95%左右，那么我们就断定这个init1是正确的。

from tqdm import tqdm

mask1 = 
output = 
N = 64

class lfsr():
    def __init__(self, init, mask, length):
        self.init = init
        self.mask = mask
        self.lengthmask = 2**length-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 diff(a,b):
    flag = 0
    for (i,j) in zip(a,b):
        if i == j:
            flag+=1
    return float(flag / len(a))

# construct transfer matrix1
a=[]
for i in range(63):
    b=[]
	for j in range(64):
        if j==i+1:
            b.append(1)
        else:
            b.append(0)
    a.append(b)
a.append(mask1.bits()[::-1])
M = Matrix(GF(2),a)

# find the continuous 64bits of l1 and recover the init1 
for i in tqdm(range(len(output)-64)):
    try:
        block = output[i:i+64]
        init1 = M^(i+64) \ vector(GF(2),[int(each) for each in list(output[i:i+64])])
        init1 = int(''.join(str(i) for i in init1),2)
        tryl1 = lfsr(init1,mask1,N)
        tryoutput = ''.join(str(tryl1.next()) for _ in range(2048))
        match = diff(tryoutput,output)
        if match > 0.9:
            print("yes",init1,match)
            break
    except Exception as e:
        print(str(e))

#init1 = 15401137114601469828

有了init1后，我们就知道了l1的流，从而找出其与output的差异就能确定哪些bit是肯定来自于l2的了。只要有64个，我们就能构建线性方程组，解个方程就能获取到init2了。具体这个方程怎么构建，就需要一点点对lfsr和线性代数性质的理解了。

我们知道，这个lfsr一次输出一bit，然后会拼在这个state的后面，然后state原来的头部的bit就会被丢掉，有点像队列的机制。我们呢，可以把这个state看作是很多个状态机，比如这道题就是64个状态机，每一次输出，都伴随着状态转移，前面的状态机继承后面的状态机的状态，最后一个状态机的状态由之前的状态机和mask决定。既然是状态转移，那么我们就能构造出一个状态转移矩阵。这个矩阵长这样。

$\begin{bmatrix} 0&1 &0&0&\cdots&0\newline 0 & 0& 1 & 0 &\cdots & 0 \newline 0&0&0&1&\cdots & 0 \newline \vdots & \vdots &\vdots &\vdots &\ddots& \vdots & \newline 0 & 0&0&0&\cdots &1\newline mask_0 &mask_1 &mask_2 &mask_3 &\cdots &mask_n &\end{bmatrix}$

我们的用状态矩阵M 乘以初始向量init（$M \cdot init$），那么就是一次状态转移，会获得一个输出（状态）。新的state向量（状态向量）再左乘一下状态矩阵（$M \cdot state = M \cdot M \cdot init$），则又是一次状态转移，再获得一个新的输出（状态）那么这里如果我们先将两个矩阵相乘，我们如下形式的矩阵

$\begin{bmatrix} 0&0&1&0&\cdots&0\newline 0 & 0& 0 & 1 &\cdots & 0 \newline 0&0&0&0&\cdots & 0 \newline \vdots & \vdots &\vdots &\vdots &\ddots& \vdots & \newline mask_0 &mask_1 &mask_2 &mask_3 &\cdots &mask_n \newline x_0 & x_1&x_2&x_3&\cdots &x_n\end{bmatrix}$

这里我们有个新的一组x向量。

再看看，初始mask向量乘以初始状态能够得到第一个输出，而这个x乘以初始状态向量则可以得到第二个输出。（所以我们是否可以把这个x向量看作是类mask向量）

所以针对本题我们就用64个类mask向量和64个输出，构造64条方程组。这些输出不必连续，只要我们知道其是第几个输出就好。如果是第1个输出，我们就取M的最后一行向量做系数，如果是第4个输出，我们就取 $M^4$ 的最后一行向量做系数，以此类推，直接起飞！

init1 = 15401137114601469828
l1 = lfsr(init1,mask1,N)
lioutput = ''.join(str(l1.next()) for _ in range(2048))
diff_idx = []
# choose bits of l2
for idx in range(2048):
    if lioutput[idx] != output[idx]:
        diff_idx.append(idx)

mask2=     
# construct transfer matrix2
a=[]
for i in range(63):
    b=[]
    for j in range(64):
        if j==i+1:
            b.append(1)
        else:
            b.append(0)
    a.append(b)
a.append(mask2.bits()[::-1])
M2 = Matrix(GF(2),a)        
a2=[]
b2=[]

# construct matrix to solve Equations
for idx in diff_idx:
    a2.append((M2^(idx+1))[-1])
    b2.append(output[idx])
M3 = Matrix(GF(2),a2)
b2 = vector(GF(2),b2)

init2 = M3 \ b2
init2 = int(''.join(str(i) for i in init2),2)

#11256716742701089092

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com

密码学学习笔记 之 CTF