USTCHackergame2018之“加密解密算法”

题目

加密算法和解密算法

提示：本题中使用的 base64 编码，采用已被广泛应用于各种场合的 RFC 4648 §5 标准。

小赵听到自己成为了信息安全大赛的创始人后感到非常吃惊：“我一个少院学生会的干事，怎么就成信息安全大赛的创始人了呢？”这也难怪，毕竟小赵后来成为了物理学院的学生。物理和信息安全，通常情况下可都是八杆子打不着的呢。

当然了，小赵作为物理学院的学生，和其他物理学院的学生一样，身上的浮躁劲儿可一点都不少，常常因为一点小成就而沾沾自喜。这不，因为个人安全上的不重视，小赵的某个学弟小郑，很快从小赵暗恋的女孩子手里拿到了小赵和她交流的加密算法的程序。小赵在得知此事后反而没有尽可能地息事宁人，反而公开宣称，由于解密算法目前没有公开，所以拿到了加密算法也没有什么用。看来小赵对于现代密码学，根本没什么全面深入的了解啊。

不过，即使小赵使用的是对称加密算法，分析出解密算法也并非易事——小赵对程序进行了混淆，而混淆的方法是使用 BrainFuck 虚拟机——这也正是小赵的底气所在。现在的任务是分析并读懂一段 BrainFuck 程序，从而将一段密文还原。小郑拿到的密文是：

JzRVPiVpqo4iDM8celyueIs4ff4DKeG3EMKihzuH

现在小郑将这一任务交给了跃跃欲试的你。快来挖掘小赵的黑历史吧！

FLAG 格式

以下是两条示例原文和密文：

QUICK_BROWN_FOXES_JUMP_OVER_THE_LAZY_DOG => aMRKoll07lcf49SIuPrNg8v5bMctTkfrQmchaEkF
quick-brown-foxes-jump-over-the-lazy-dog => p9dJ4Jsrj3oDy_KxMJ1N750NvUBtXVUGNPVALq5l

• 假设密文是 p9dJ4Jsrj3oDy_KxMJ1N750NvUBtXVUGNPVALq5l
• 最后解得原文是 quick-brown-foxes-jump-over-the-lazy-dog
• 则 FLAG 格式为 flag{quick-brown-foxes-jump-over-the-lazy-dog}

下面的输入输出框可以帮助测试原文是否已成功匹配加密过的 FLAG：

输入（合法）	输出（匹配）
	JzRVPiVpqo4iDM8celyueIs4ff4DKeG3EMKihzuH

编码与解码

本题使用的 BrainFuck 解释器所使用的内存空间可视为长度无限，每一个 Cell 的大小为 256，同时加减是循环的（即 255 加一为 0，反之 0 减一为 255），此外所有合法的八个程序字符外的字符将会被忽略。原文需要编码转换为输入 BrainFuck 解释器的格式，解释器的输出同样需要解码转换才能输出密文。下面以QUICK_BROWN_FOXES_JUMP_OVER_THE_LAZY_DOG为例。

编码过程如下：

• 将原文分为四段，每段长度为十： [QUICK_BROW, N_FOXES_JU, MP_OVER_TH, E_LAZY_DOG]
• 每一段按 Base64 的顺序映射到 0 和 63 之间的数字：
  • 第一段映射后结果为： [16, 20, 8, 2, 10, 63, 1, 17, 14, 22]
  • 第二段映射后结果为： [13, 63, 5, 14, 23, 4, 18, 63, 9, 20]
  • 依此类推
• 将十个为一组的数字输入 BrainFuck 解释器

解码过程如下：

• BrainFuck 解释器一次输出十个数字：
  • 第一段输出后结果为： [154, 76, 209, 202, 232, 37, 165, 180, 251, 165]
  • 第二段输出后结果为： [28, 159, 248, 253, 146, 136, 174, 207, 171, 141]
  • 依此类推
• 每一段的每一个数字对 64 取模：
  • 第一段取模后结果为： [26, 12, 17, 10, 40, 37, 37, 52, 59, 37]
  • 第二段取模后结果为： [28, 31, 56, 61, 18, 8, 46, 15, 43, 13]
  • 依此类推
• 每一段按 Base64 的顺序映射后拼接在一起： [aMRKoll07l, cf49SIuPrN, g8v5bMctTk, frQmchaEkF]
• 将四段拼接后得到密文

本题目内置了一个使用 JavaScript 编写的 BrainFuck 解释器（当然了，性能堪忧，不过一次加密还是很快的）。相关的文件位于bf.js中。BrainFuck 源代码位于encrypt.bf中。

encrypt.bf的BrainFuck代码如下

/* author: @ustc_zzzz */ call(`,[->>+++++++>>+++++>>+++>>++>>++++>++++++<<+++<<+++++++++<<++++++++<<
++++++<<++++++++<]>[->>+++++>>+++++++++>>+++++++++>>++>>++++<+++++++++<<++++<<++++<<++<<++<]<,[->>++
+++>>++++++++>>++++++>>+++++++>>+++++++>++++++<<++++++<<++++++++<<+++<<+++<<++++++++<]>[->>++++++++>
>+++>>+++++++>>++++>>+++++++++<++++++<<+++++++++<<++<<+++++++++<<++++++++<]<,[->>++++++++>>+++++++>>
++>>++>>+++++++++>+++<<++++<<+++<<+++++<<++++++++<<++++++++<]>[->>++++>>++++++++>>++++++>>++++++>>++
+++<++++<<+++++++++<<++++++++<<+++++++<<++++<]<,[->>+++++>>+++++++++>>+++>>++++>>++++>+++<<++++++++<
<++++++<<+++++<<++++++<<++++++++<]>[->>++++++>>++++++>>+++++>>++++++++>>+++++++<++++++++<<++++++<<++
+++<<+++<<+++++++<]<,[->>+++++++>>++++>>++++>>+++>>+++++++>+++++++<<+++++++++<<+++++<<+++++<<+++++++
<<++++++++<]>[->>+++>>++++>>++++>>+++++>>++++++<++++<<+++<<++++++++<<+++++++<<+++++<]<,[->>+++++>>++
>>++++>>+++>>++++++>++<<+++++++<<++++<<+++++++++<<+++++++<<++++++++<]>[->>++>>+++++++++>>+++++>>++++
++++>>+++++++++<+++++++<<++<<++++<<+++<<++<]<,[->>++++++>>+++++++>>+++>>++++++>>++++++++>++<<++++<<+
++<<++++++++<<++++++<<++++++++<]>[->>++++++>>++>>+++++++++>>++++>>++++++<+++++<<++++<<++++++++<<++++
<<+++++++<]<,[->>+++++++++>>++++++++>>++++++>>+++++++>>+++++++++>++<<++++++++<<+++++<<+++++<<+++<<++
++++++<]>[->>+++++++++>>+++++++>>+++++++++>>++++>>++<+++++++<<+++++++++<<++<<+++<<++++++++<]<,[->>++
>>++++++++>>++>>++++++>>+++++>++++<<++++<<+++++++<<+++++++<<++++++++<<++++++++<]>[->>+++++++>>++>>++
++++++>>+++++++>>++++<++<<+++<<+++++++<<+++++<<++<]<,[->>+++++++++>>+++++++>>+++++>>++++>>++>+++++<<
+++++<<++<<++<<+++++<<++++++++<]>[->>++++++++>>++++++>>++>>+++++>>+++++++++<++++++++<<++++++++<<++++
<<++++<<+++++++++<]>++.>++++++.>++++++++.>++++++++.>+++.>+++++.>+++++.>+++++++.>++++.>+++++++++.`)

解题

学习一下BrainFuck语法

Brainfuck是一种极小化的计算机语言，它是由Urban Müller在1993年创建的。由于fuck在英语中是脏话，这种语言有时被称为brainf*ck或brainf**k，甚至被简称为BF。

字符	含义
>	指针加一
<	指针减一
+	指针指向的字节的值加一
-	指针指向的字节的值减一
.	输出指针指向的单元内容（ASCⅡ码）
,	输入内容到指针指向的单元（ASCⅡ码）
[	如果指针指向的单元值为零，向后跳转到对应的]指令的次一指令处
]	如果指针指向的单元值不为零，向前跳转到对应的[指令的次一指令处

Brainfuck程序可以用下面的替换方法翻译成C语言（假设ptr是char*类型）：

Brainfuck	C
>	++ptr;
<	–ptr;
+	++*ptr;
-	–*ptr;
.	putchar(*ptr);
,	*ptr =getch();
[	while (*ptr) {
]	}

当前位置清零

[-] 将当前指针的值归零

之前位置清零

[[-]<] 将当前指针以及之前的指针归零

字符I/O

,. 从键盘读取一个字符并输出到屏幕上。

简单的循环

,[.,] 这是一个连续从键盘读取字符并回显到屏幕上的循环。注意，这里假定0表示输入结束，事实上有些系统并非如此。以-1和”未改变”作为判断依据的程序代码分别是”,+[-.,+]”和”,[.[-],]”。

指针维护

>,[.>,] 通过移动指针保存所有的输入，供后面的程序使用。

加法

[->+<]

把当前位置的值加到后面的单元中（破坏性的加，它导致左边的单元被归零）。

观察原来的代码，发现是很多个循环

分行一下比较清楚，对第一个循环注释一下

, 
//a[0]=k;
[->>+++++++>>+++++>>+++>>++>>++++>++++++<<+++<<+++++++++<<++++++++<<++++++<<++++++++<] 
//a[0]--; a[2]=7; a[4]=5; a[6]=3; a[8]=2; a[10]=4; a[11]=6; a[9]=3; a[7]=9; a[5]=8; a[3]=6; a[1]=8;
//a[0-11]*k
>
[->>+++++>>+++++++++>>+++++++++>>++>>++++<+++++++++<<++++<<++++<<++<<++<]
//a[1]--; 
<
,
[->>+++++>>++++++++>>++++++>>+++++++>>+++++++>++++++<<++++++<<++++++++<<+++<<+++<<++++++++<]
>
[->>++++++++>>+++>>+++++++>>++++>>+++++++++<++++++<<+++++++++<<++<<+++++++++<<++++++++<]
<
,
[->>++++++++>>+++++++>>++>>++>>+++++++++>+++<<++++<<+++<<+++++<<++++++++<<++++++++<]
>
[->>++++>>++++++++>>++++++>>++++++>>+++++<++++<<+++++++++<<++++++++<<+++++++<<++++<]
<
,
[->>+++++>>+++++++++>>+++>>++++>>++++>+++<<++++++++<<++++++<<+++++<<++++++<<++++++++<]
>
[->>++++++>>++++++>>+++++>>++++++++>>+++++++<++++++++<<++++++<<+++++<<+++<<+++++++<]
<
,
[->>+++++++>>++++>>++++>>+++>>+++++++>+++++++<<+++++++++<<+++++<<+++++<<+++++++<<++++++++<]
>
[->>+++>>++++>>++++>>+++++>>++++++<++++<<+++<<++++++++<<+++++++<<+++++<]
<
,
[->>+++++>>++>>++++>>+++>>++++++>++<<+++++++<<++++<<+++++++++<<+++++++<<++++++++<]
>
[->>++>>+++++++++>>+++++>>++++++++>>+++++++++<+++++++<<++<<++++<<+++<<++<]
<
,
[->>++++++>>+++++++>>+++>>++++++>>++++++++>++<<++++<<+++<<++++++++<<++++++<<++++++++<]
>
[->>++++++>>++>>+++++++++>>++++>>++++++<+++++<<++++<<++++++++<<++++<<+++++++<]
<
,
[->>+++++++++>>++++++++>>++++++>>+++++++>>+++++++++>++<<++++++++<<+++++<<+++++<<+++<<++++++++<]
>
[->>+++++++++>>+++++++>>+++++++++>>++++>>++<+++++++<<+++++++++<<++<<+++<<++++++++<]
<
,
[->>++>>++++++++>>++>>++++++>>+++++>++++<<++++<<+++++++<<+++++++<<++++++++<<++++++++<]
>
[->>+++++++>>++>>++++++++>>+++++++>>++++<++<<+++<<+++++++<<+++++<<++<]
<
,
[->>+++++++++>>+++++++>>+++++>>++++>>++>+++++<<+++++<<++<<++<<+++++<<++++++++<]
>
[->>++++++++>>++++++>>++>>+++++>>+++++++++<++++++++<<++++++++<<++++<<++++<<+++++++++<]
>
++.>++++++.>++++++++.>++++++++.>+++.>+++++.>+++++.>+++++++.>++++.>+++++++++.

每组都是两个循环，先输入a[0]，

进行a[0]次循环，每次循环给a[1-11]各加一个定值（等于加号个数），其中a[1]+=8，

然后进行a[1]=8*a[0]次循环，每次循环给a[2-11]各加一个定值

用C语言有针对性地把上面代码转为伪代码，并获得每个加号的个数

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int tmp1[10];

void pflist(){
    printf("{");
    for(int i=0;i<10;i++) printf("%d,",tmp1[i]);
    printf("\b}\n");
    memset(tmp1,0,sizeof(tmp1));
}

int main(){
    FILE *fp=fopen("encrypt.bf","r");
    char ch;
    int p=0;
    int a[20];
    int in_while;
    int in_add;
    int add_times=0;
    while((ch=fgetc(fp))!=EOF){
        //printf("%c",ch);
        if(ch!='+' && in_add){in_add=0;if(p>=2){tmp1[p-2]+=add_times;};printf("%d\n",add_times);add_times=0;}
        switch(ch){
            case (int)'>': {p++;break;}
            case (int)'<': {p--;break;}
            case (int)'[': {in_while=1;printf("while(a[%d]){\n",p);break;}
            case (int)']': {in_while=0;pflist();printf("}\n");break;}
            case (int)'+': {if(!in_add){in_add=1;add_times++;printf("a[%d]+=",p);}else{add_times++;}break;}
            case (int)',': {printf("a[%d]=in()\n",p);break;}
            case (int)'.': {printf("out(a[%d])\n",p);break;}
            default: {break;}
        }

    }
    return 0;
}

得到每个循环中的各个定值，原BrainFuck编写的加密程序可等效地转为如下C代码

#include <stdio.h>
int arr[10]={};
int a[10][10]={{7,6,5,8,3,9,2,3,4,6},{5,3,8,3,6,8,7,6,7,6},{8,8,7,5,2,3,2,4,9,3},{5,6,9,5,3,6,4,8,4,3},{7,7,4,5,4,5,3,9,7,7},{5,7,2,9,4,4,3,7,6,2},{6,6,7,8,3,3,6,4,8,2},{9,3,8,5,6,5,7,8,9,2},{2,8,8,7,2,7,6,4,5,4},{9,5,7,2,5,2,4,5,2,5}};
int b[10][10]={{2,5,2,9,4,9,4,2,9,4},{8,8,9,3,2,7,9,4,6,9},{4,4,7,8,8,6,9,6,4,5},{7,6,3,6,5,5,6,8,8,7},{5,3,7,4,8,4,3,5,4,6},{2,2,3,9,4,5,2,8,7,9},{7,6,4,2,8,9,4,4,5,6},{8,9,3,7,2,9,9,4,7,2},{2,7,5,2,7,8,3,7,2,4},{9,8,4,6,4,2,8,5,8,9}};
int c[10]={2,6,8,8,3,5,5,7,4,9};
int main(){
    int t;
    for(int i=0;i<10;i++){
        scanf("%d",&t);
        //printf("%d\n",t);
        for(int j=0;j<10;j++){
            arr[j]+=(a[i][j]*t);
            arr[j]+=(b[i][j]*8*t);
        }
    }
    for(int j=0;j<10;j++) printf("%d ",(arr[j]+c[j])%256);
    return 0;
}

题目给的是base64映射后的字符串JzRVPiVpqo4iDM8celyueIs4ff4DKeG3EMKihzuH

写如下Python代码转换回去

bmap="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_"
def encode(l):
    s=""
    for i in l:
        s=s+bmap[i]
    return s

def decode(s):
    l=[]
    for ch in s:
        for i in range(64):
            if bmap[i]==ch:
                l.append(i)
    return l

#print(decode("QUICK_BROWN_FOXES_JUMP_OVER_THE_LAZY_DOG"))
s="JzRVPiVpqo4iDM8celyueIs4ff4DKeG3EMKihzuH"
print(decode(s))

输出如下

[9, 51, 17, 21, 15, 34, 21, 41, 42, 40, 56, 34, 3, 12, 60, 28, 30, 37, 50, 46, 30, 8, 44, 56, 31, 31, 56, 3, 10, 30, 6, 55, 4, 12, 10, 34, 33, 51, 46, 7]

分为4组

[9, 51, 17, 21, 15, 34, 21, 41, 42, 40]
[56, 34, 3, 12, 60, 28, 30, 37, 50, 46]
[30, 8, 44, 56, 31, 31, 56, 3, 10, 30]
[6, 55, 4, 12, 10, 34, 33, 51, 46, 7]

这4组就是原4组数列经过加密程序所得到的，现在就是要求原来的数列，相当于解方程组，当然是在模64情况下（加密过程是模256的，但输出序列要进过base64之前又被模64了），

用Mathematica写如下代码

a={{7,6,5,8,3,9,2,3,4,6},{5,3,8,3,6,8,7,6,7,6},{8,8,7,5,2,3,2,4,9,3},{5,6,9,5,3,6,4,8,4,3},{7,7,4,5,4,5,3,9,7,7},{5,7,2,9,4,4,3,7,6,2},{6,6,7,8,3,3,6,4,8,2},{9,3,8,5,6,5,7,8,9,2},{2,8,8,7,2,7,6,4,5,4},{9,5,7,2,5,2,4,5,2,5}}
b={{2,5,2,9,4,9,4,2,9,4},{8,8,9,3,2,7,9,4,6,9},{4,4,7,8,8,6,9,6,4,5},{7,6,3,6,5,5,6,8,8,7},{5,3,7,4,8,4,3,5,4,6},{2,2,3,9,4,5,2,8,7,9},{7,6,4,2,8,9,4,4,5,6},{8,9,3,7,2,9,9,4,7,2},{2,7,5,2,7,8,3,7,2,4},{9,8,4,6,4,2,8,5,8,9}}
c={2,6,8,8,3,5,5,7,4,9}
d=a+8*b


s={9, 51, 17, 21, 15, 34, 21, 41, 42, 40}
x={x1,x2,x3,x4,x5,x6,x7,x8,x9,x10}

NSolve[Mod[Dot[x,d]+c,64]==s,x,Integers]

对于第一组，可得

{{x1 -> ConditionalExpression[
    33 + 64 C[1], (C[1] | C[2] | C[3] | C[4] | C[5] | C[6] | C[7] | 
       C[8] | C[9] | C[10]) \[Element] Integers], 
  x2 -> ConditionalExpression[
    53 + 64 C[2], (C[1] | C[2] | C[3] | C[4] | C[5] | C[6] | C[7] | 
       C[8] | C[9] | C[10]) \[Element] Integers], 
  x3 -> ConditionalExpression[
    37 + 64 C[3], (C[1] | C[2] | C[3] | C[4] | C[5] | C[6] | C[7] | 
       C[8] | C[9] | C[10]) \[Element] Integers], 
  x4 -> ConditionalExpression[
    37 + 64 C[4], (C[1] | C[2] | C[3] | C[4] | C[5] | C[6] | C[7] | 
       C[8] | C[9] | C[10]) \[Element] Integers], 
  x5 -> ConditionalExpression[
    62 + 64 C[5], (C[1] | C[2] | C[3] | C[4] | C[5] | C[6] | C[7] | 
       C[8] | C[9] | C[10]) \[Element] Integers], 
  x6 -> ConditionalExpression[
    28 + 64 C[6], (C[1] | C[2] | C[3] | C[4] | C[5] | C[6] | C[7] | 
       C[8] | C[9] | C[10]) \[Element] Integers], 
  x7 -> ConditionalExpression[
    53 + 64 C[7], (C[1] | C[2] | C[3] | C[4] | C[5] | C[6] | C[7] | 
       C[8] | C[9] | C[10]) \[Element] Integers], 
  x8 -> ConditionalExpression[
    41 + 64 C[8], (C[1] | C[2] | C[3] | C[4] | C[5] | C[6] | C[7] | 
       C[8] | C[9] | C[10]) \[Element] Integers], 
  x9 -> ConditionalExpression[
    33 + 64 C[9], (C[1] | C[2] | C[3] | C[4] | C[5] | C[6] | C[7] | 
       C[8] | C[9] | C[10]) \[Element] Integers], 
  x10 -> ConditionalExpression[
    55 + 64 C[10], (C[1] | C[2] | C[3] | C[4] | C[5] | C[6] | C[7] | 
       C[8] | C[9] | C[10]) \[Element] Integers]}}

直接取

33,53,37,37,62,28,53,41,33,55

类似地对其他3组用Mathematica求解，然后利用上面的Python代码进行base64映射

print(encode([33,53,37,37,62,28,53,41,33,55]))
print(encode([43,62,48,53,45,33,62,53,52,49]))
print(encode([53,52,62,43,55,47,55,43,44,53]))
print(encode([27,37,55,62,38,26,45,43,53,49]))

得

h1ll-c1ph3
r-w1th-10x
10-r3v3rs1
bl3-matr1x

则有flag{h1ll-c1ph3r-w1th-10x10-r3v3rs1bl3-matr1x}

答案正确！