题目信息

附件中包含实现加密的Python脚本，与密文文件。

分析

有限域$GF(2^{n})$

构造有限域$GF(2^{n})$时，首先需要$GF(2)$上次数为n的本原多项式$g(x)$；对于$GF(2^{n})$上的每个元素$a$，都可以用一个次数不超过$n$的多项式$f_{a}$表示：$f_{a}(x)=\sum_{i=0}^{n-1}a_{i}\cdot x^{i}$，其中$a_{n-1}\cdots a_{0}$是$a$的二进制表示；从而$GF(2^{n})$上的四则运算定义如下：

  • 加法：对于$a,b\in GF(2^{n})$，它们的多项式表示分别为$f_{a},f_{b}$，记$f_{c}=f_{a}+f_{b}$(其中系数的加法为$GF(2)$上的加法，即异或运算)，则$c_{n-1}\cdots c_{0}$的二进制值$c$为$a+b$的值；

  • 减法：由于$GF(2)$上的加法与减法等价，因此对于$a,b\in GF(2^{n})$，$a+b=a-b$；

  • 乘法：同样地，$a,b$的多项式表示$f_{a},f_{b}$，记$f_c=f_{a}\cdot f_{b}\ \textrm{mod}\ g$，由于多项式$g$的次数为$n$，故多项式$f_{c}$的次数不超过$n$，则$c_{n-1}\cdots c_{0}$的二进制值$c$为$a\cdot b$的值；

  • 除法：先介绍(乘法)逆元，本原多项式是一种具有特殊性质的不可约多项式，对GF(2)上任意次数不超过$n$的多项式f，都存在$GF(2)$上次数不超过n的多项式$h$，使得$f\cdot h \equiv 1\ \textrm{mod}\ g$；与$f$作除法等价于与$f$的逆元$h$作乘法；

process(m,k)

考虑$t^{2},t\in GF(2^{256})$，构造$GF(2^{256})$的本原多项式为$g=x^{256}+x^{10}+x^{5}+x^{2}+1$，记$t$的二进制表示为$t_{n-1}\cdots t_{0}$，则$t$的多项式表示$f_{t}(x)=\sum_{i=0}^{n-1}t_{i}\cdot x^{i}=(((t_{n-1}\cdot x+t_{n-2})\cdot x+\cdots +t_{1})\cdot x+t_{0})$，考虑$t^{2}$：

$f_{t}^{2}\ \textrm{mod}\ g$

$=(((t_{n-1}\cdot x+t_{n-2})\cdot x+\cdots +t_{1})\cdot x+t_{0})\cdot f_{t}\ \textrm{mod}\ g$

$=((((t_{n-1}\cdot f_{t})\cdot x+t_{n-2}\cdot f_{t})\cdot x+\cdots +t_{1}\cdot f_{t})\cdot x+t_{0}\cdot f_{t})\ \textrm{mod}\ g$

$=((((((t_{n-1}\cdot f_{t})\cdot x+t_{n-2}\cdot f_{t})\ \textrm{mod}\ g)\cdot x+\cdots +t_{1}\cdot f_{t})\ \textrm{mod}\ g)\cdot x+t_{0}\cdot f_{t})\ \textrm{mod}\ g$

我们再来对比函数process(m,k)：

1
2
3
4
5
6
7
8
9
10
def process(m, k):
    tmp = m ^ k
    res = 0
    for i in bin(tmp)[2:]:
        res = res << 1;
        if (int(i)):
            res = res ^ tmp
        if (res >> 256):
            res = res ^ P
    return res

res=res<<1代表乘以x，多项式的系数全体左移一位；

if (int(i)):res^=tmp等价于res^=int(i)*tmp，代表$+t_{i}\cdot f_{t}$；

if (res>>256):res^=P代表模本原多项式g；

综上，process(m,k)实际上实现了$GF(2^256)$上的元素$m$与$k$之和的平方$(m+k)^{2}$；

解密过程

$k_{2}=(k_{1}+secret)^{2},k_{3}=(k_{2}+secret)^{2}$(在GF(2^256)上的运算)

$c_{1}=m_{1}\oplus k_{1},c_{2}=m_{2}\oplus k_{2},c_{3}=m_{3}\oplus k_{3}$，其中$c_{i}(i=1,2,3),m_{i}(i=1,2)$已知

则$k_{2}=m_{2}\oplus c_{2},k_{3}=m_{3}\oplus c_{3}$，可解出secret：$secret=k_{3}^{1/2}+k_{2}$(在GF(2^256)上的运算)

接下来解出$k_{1}$：$k_{1}=k_{2}^{1/2}+secret$(在GF(2^256)上的运算)

然后解出flag(即$m_{1}$)：$m_{1}=c_{1}\oplus k_{1}$

解题

实现的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
from Crypto.Util.number import bytes_to_long,long_to_bytes

K.<x>=GF(2L**256,modulus=x^256+x^10+x^5+x^2+1)

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)

def solve():
    cip1=polify(0xaf3fcc28377e7e983355096fd4f635856df82bbab61d2c50892d9ee5d913a07f)
    cip2=polify(0x630eb4dce274d29a16f86940f2f35253477665949170ed9e8c9e828794b5543c)
    cip3=polify(0xe913db07cbe4f433c7cdeaac549757d23651ebdccf69d7fbdfd5dc2829334d1b)
    msg2=polify(bytes_to_long('I_am_not_a_secret_so_you_know_me'))
    msg3=polify(bytes_to_long('feeddeadbeefcafefeeddeadbeefcafe'))
    secret=cip2+msg2+(cip3+msg3).sqrt()
    key1=(cip2+msg2).sqrt()+secret
    msg1=cip1+key1
    return long_to_bytes(unpolify(msg1))

if __name__=='__main__':
    print 'flag{'+solve()+'}'

程序运行结果如下：

1
2
$ sage solve.sage
flag{t0_B3_r4ndoM_en0Ugh_1s_nec3s5arY}