这里是对在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)
然后我们看看怎么能拿到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,
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的小屋
- 左青龙
- 微信扫一扫
- 右白虎
- 微信扫一扫
评论