文章目录
  1. 题目信息
  2. 分析
  3. 解题

题目信息

看名字也可以猜出来是oneTimePad的升级版。

分析

process1：GF(2^128)上的乘法操作；也是oneTimePad的唯一考点。

nextrand：将process2视为$\{(x_{1},x_{2},x_{3},x_{4})|x_{i}\in GF(2^{128})\}$上的乘法操作，则函数最后的tmp1就是$(A,B,0,1)^{N}$；而通过几次尝试，发现$(A,B,0,1)^{N}$有形式$(A^{N},A^{N-1}\cdot B+\cdots +A\cdot B+B,0,1)$，即$(A^{N},B(A^{N}-1)\cdot (A-1)^{-1},0,1)$而这可通过数学归纳法得到证明(证明很简单，此处略)。此外，$N$更新为$N^{2}$(乘法为GF(2^128)上的乘法操作)。从而得到密钥的更新迭代公式为：$k_{i+1}=k_{i}\cdot A^{N}+B(A^{N}-1)\cdot (A-1)^{-1}=(k_{i}+B\cdot (A-1)^{-1})\cdot A^{N}-B(A-1)^{-1}$，则$k_{i+1}+B\cdot (A-1)^{-1}=(k_{i}+B\cdot (A-1)^{-1})\cdot A^{N}$，记$f(k)=k+B\cdot (A-1)^{-1}$，则$A^{N}=f(k_{i+1})\cdot f(k_{i})^{-1}$。128位的离散对数问题sage还是可以搞定的！

而由于题目给了一定长度的明文，因此我们也就得到了一定数量的密钥(3个)，使用第2个和第3个密钥恢复出生成第3个密钥的$N$；得到$N$之后进行同样的操作来恢复出加密消息时的密钥流。

注：我恢复的是生成第3个密钥的$N$，需要更新($N\leftarrow N^{2}$)才能对接下来的密文(第4组起)解密！

解题

解题分为两步，第一步解出$N$，使用的sage脚本如下：

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
from binascii import unhexlify
from Crypto.Util.number import *

def polify(N):
    bN=list(bin(N)[2:])
    bN.reverse()
    return K(bN)

def unpolify(Poly):
    bN=Poly.polynomial().list()
    bN.reverse()
    return long(''.join([str(it) for it in bN]),2)

if __name__=='__main__':
    K.<x>=GF(2L^128,modulus=x^128+x^7+x^2+x+1)
    cipher='0da8e9e84a99d24d0f788c716ef9e99cc447c3cf12c716206dee92b9ce591dc0722d42462918621120ece68ac64e493a41ea3a70dd7fe2b1d116ac48f08dbf2b26bd63834fa5b4cb75e3c60d496760921b91df5e5e631e8e9e50c9d80350249c'
    cipher=unhexlify(cipher)
    cs=[bytes_to_long(cipher[ii:(ii+16)]) for ii in range(0,len(cipher),16)]
    pre="One-Time Pad is used here. You won't know that the flag is flag{"
    ps=[bytes_to_long(pre[ii:ii+16]) for ii in range(0,len(pre)-16,16)]
    ks=[p^^c for p,c in zip(ps,cs)]
    f=lambda k,a,b: k+b*(a-1)^-1
    A=0xc6a5777f4dc639d7d1a50d6521e79bfd
    B=0x2e18716441db24baf79ff92393735345
    KA,KB=polify(A),polify(B)
    Kks=[polify(t) for t in ks]
    tt=f(Kks[2],KA,KB)*f(Kks[1],KA,KB)^-1
    N=discrete_log(tt,KA)
    KN=polify(N)
    print unpolify(pow(KN,2))

脚本运行结果如下：
1
2
$ sage solve.sage
139066609048774629292054833219983607544

注：我最后做了更新操作，因此直接对第四组起的密文解密即可。

第二步，进行同样的操作来恢复出加密消息时的密钥流来解密密文，使用的Python脚本如下：

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
from binascii import unhexlify
from Crypto.Util.number import *
from oneTimePad2 import P,A,B
from oneTimePad2 import process1,process2

def nextrand(rand):
    global N, A, B
    tmp1 = [1, 0, 0, 1]
    tmp2 = [A, B, 0, 1]
    s = N
    N = process1(N, N)
    while s:
        if s % 2:
            tmp1 = process2(tmp2, tmp1)
        tmp2 = process2(tmp2, tmp2)
        s = s / 2
    return process1(rand, tmp1[0]) ^ tmp1[1]

def keygen():
    key = bytes_to_long(pre)^bytes_to_long(cipher[0:16])
    while True:
        yield key
        key = nextrand(key)

if __name__=='__main__':
    N=139066609048774629292054833219983607544
    cipher='0da8e9e84a99d24d0f788c716ef9e99cc447c3cf12c716206dee92b9ce591dc0722d42462918621120ece68ac64e493a41ea3a70dd7fe2b1d116ac48f08dbf2b26bd63834fa5b4cb75e3c60d496760921b91df5e5e631e8e9e50c9d80350249c'
    cipher=unhexlify(cipher[64:])
    pre="on't know that t"
    res=''
    for i, key in zip(range(0,64,16),keygen()):
        res+= long_to_bytes(bytes_to_long(cipher[i:i+16])^key)
    print res

注：为了复用P,A,B以及process1,process2，对oneTimePad2.py做了一定调整，P,A,B的定义放在全局，其他的除了函数定义全部放到if __name__ == '__main__':下。
运行脚本结果如下：

1
2
$ python solve.py
on't know that the flag is flag{LCG1sN3ver5aFe!!}.XXXX

注：后面的字符有不可打印字符因此用XXXX代替。