密码学学习笔记 之 CTF

admin 2024年8月24日23:37:02评论11 views字数 15753阅读52分30秒阅读模式

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

2020祥云杯-more_calc

1234567891011121314151617
import gmpy2from 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 % pq = gmpy2.next_prime(s)n = p*qe = 0x10001c = 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$

所以最终预期解题代码

12345678910111213141516
#!/usr/bin/env python# -*- coding: utf-8 -*-from Crypto.Util.number import *from sympy import nextprimee = 65537p = c = s = p - (pow(2, p, p*p)-2)//pq = nextprime(s)n = p*qe = 0x10001phi = (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

1234567891011121314151617181920212223242526272829303132
#!/usr/bin/env pythonfrom Crypto.Util.number import *from secret import FLAG,HINTassert len(HINT) < len(FLAG)assert len(FLAG) == 38p1 = getPrime(2048)q1 = getPrime(2048)n1 = p1*q1e1 = 321959e2 = 250261c1 = 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*q2e3 = 386321e4 = 216437flag = 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

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133
#!/usr/bin/env python2.7from libnum import n2s, s2n, xgcdfrom random import getrandbitsfrom Crypto.Util.number import getPrimefrom Crypto.Cipher import AESfrom hashlib import sha256import SocketServer#from secret import flagflag=b"vanish"pad = lambda x: x + '$' * (16 - len(x) % 16) if len(x) % 16 else xnbits = 128MASK = 2 ** nbits - 1def 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, d2def 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, k1def 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, ans1def generate_k():    cur = getrandbits(128)    while cur < 2 ** 127:        cur = getrandbits(128)    return curdef 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):    passclass 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)

密码学学习笔记 之 CTF

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

密码学学习笔记 之 CTF

首先会接受一个你的信息,然后用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,

123456
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

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122
import hashlibimport socketserverimport os,random,stringfrom hashlib import sha256from Crypto.Util.number import *#from SECRET import FLAGFLAG = b"vanish"p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2fa = 0b = 7xG = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798yG = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141h = 1zero = (0,0)G = (xG, yG)kbits = 8def 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 rdef 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):    passif __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了。

核心代码如下:

123456789101112
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)/nM[len(alist)+1 , len(alist)+1] = 2**(256-8)tmpM=M.LLL() dA = tmpM[1][-2] * n / 2^(256-8) % n

2021-西湖论剑-SpecialCurve2

12345678910111213141516171819202122232425262728293031323334353637383940414243
from Crypto.Util.number import *#from flag import flagimport randomdef 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 Qdef getMyPrime():    while True:        q=getPrime(88)        p=2*q+1        if isPrime(p):            return pe=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

1234567891011121314151617181920212223242526272829303132333435363738
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 outputdef my_filter(c1,c2):    if random.random()>0.1:        return str(c1)    else:        return str(c2)N=64mask1=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是正确的。

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859
from tqdm import tqdmmask1 = output = N = 64class 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 outputdef diff(a,b):    flag = 0    for (i,j) in zip(a,b):        if i == j:            flag+=1    return float(flag / len(a))# construct transfer matrix1a=[]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$ 的最后一行向量做系数,以此类推,直接起飞!

123456789101112131415161718192021222324252627282930313233343536
init1 = 15401137114601469828l1 = lfsr(init1,mask1,N)lioutput = ''.join(str(l1.next()) for _ in range(2048))diff_idx = []# choose bits of l2for idx in range(2048):    if lioutput[idx] != output[idx]:        diff_idx.append(idx)mask2=     # construct transfer matrix2a=[]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 Equationsfor 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 \ b2init2 = int(''.join(str(i) for i in init2),2)#11256716742701089092

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081,也可以邮件至 [email protected] - source:Van1sh的小屋

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2024年8月24日23:37:02
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   密码学学习笔记 之 CTFhttps://cn-sec.com/archives/3093519.html

发表评论

匿名网友 填写信息