4月29日，Scalers参加了第二届北京网络安全技术大赛。参加这个比赛其实是因为组队需要被拉去好玩的，纯粹作为体验，因为我以前没有玩过类似于这种叫做CTF的夺旗性质的比赛。CTF（Capture The Flag）中文一般译作夺旗赛，在网络安全领域中指的是网络安全技术人员之间进行技术竞技的一种比赛形式。大家别想到周大福（ChowTai Fook）了……夺旗的意思就是给你一些题，你要解出来，找到其中的答案，这个答案相当于就是旗子了。

三个人一组在比赛捣腾了一天，最后拿了个二等奖，现场发奖金钞票的感觉还是不错的，如果你在我的朋友圈里也能看到我发的得奖盛况。我做的是加密解密部分（Crypto）的题目，然后四道题全部做出来了，大概有1000多分。其实这也是挺意外的，一个是我大概有五年没有碰密码学了，很多只是凭借模糊的印象和直觉，二是，其中的一些思路正好也是碰巧对上于是就解开了，所以我觉得运气的成分还是有很多，就像赌场上新手一般好运一样。但是毕竟还是解开了，而且貌似是我是全场将近200名参赛选手中，第一个解出这部分所有题目的（不知道有没有第二个=-=），所以的确算是个惊喜吧。

我在成长会也和大家说过，对于参与过的活动，都要记录下来做复盘总结，一是强化已经做对的事情使其稳定，这样就减少蒙对的成分，二是总结不足之处，以期提高改进。今天就把这部分的题目做一个解析，还原一下我当时的解题过程、遇到的困难以及如何找到的方法。我其实不想让大家产生错误的印象，比如我有多么牛，因为这只是一个孤例（我只参加了一次），孤例是无法用于下结论的，因为不稳定。但是我想让大家知道的是，我的个人介绍里说的“游走在口译世界的IT从业者”，是因为我真的是IT从业者，我不是搞英语的，只是我平时英语口译类文章发的多一点而已了……所以下次不要问我专四和专八怎么备考了，因为贵专业不让我考……

最后做一个声明：我看历次的CTF都会有人把赛题和解题写出文章，这次比赛主办方也没有做赛题声明，虽然这是研究学习用，但我不知道会不会有什么版权的问题，如果涉及到侵权，请第一时间联系我。

题目1（118分）：公元前一百年，在罗马处上了一位对世界影响巨大的人物，他是当时罗马三巨头之一。在执政生涯中，传言他率先使用了一种简单的加密函，因此这种加密方法以他的名字命名。以下密文被解开后可以获得一个有意义的单词，你可以用这个相同的加密向量加密附件中的密文，作为答案进行提交：FRPHEVGL。答案为非常规形式。

附件中的字符串是ComeChina

题目解析：题中有一些错别字但是不影响解题，比如“附件中的密文”，应该是“明文”。这个题目一看似乎缺失信息，比如只知道密文没有密码怎么加密。其实密码分析里面有唯密文攻击，这个算一种形式。我们注意到“有意义的单词”其实是一个很有信息量的提示，利用了人们的常识和默认，但是你也得有一定的英文词汇量，否则你不认识单词也是白搭了……

那要怎么下手？当时在我脑海里的印象就是，对于经典密码学很普遍的一个手法就是移位，移位就是把明文里的字母向后移动一个统一的偏移量，比如a替换成e，b替换成f，这样偏移量就是4了。那z呢，你可以把字母表首尾相连，z于是替换成d了。这种首尾相连的形式，其实就是数论里面同余和模的概念了。（这是我在比赛时的思考，后面我再复盘审题发现了“因此这种加密方法以他的名字命名”，其实就是凯撒密码了，根本不要分析直接上手做啊。所以看清题目很有作用啊=-=不过好歹我是做出来了）

那这样于是就有0-25种移位的方法。我们可以用一个小程序计算FRPHEVGL的所有移位的情况，我是用的Python写的。最基本的想法就是取出字符串的每一个字符，对其ASCII码加上一个位移，但是有一个问题是，如果相加后的值超过了最后一个字母z，需要重新转接到a，所以你可以理解为这是一个循环队列。因此，只要对移位后，大于z的偏移量，减去26即可。用0-25种循环逐个遍历后，我们得到下列结果，为了可读我采用了小写输出：

0 frphevgl

1 gsqifwhm

2 htrjgxin

3 iuskhyjo

4 jvtlizkp

5 kwumjalq

6 lxvnkbmr

7 mywolcns

8 nzxpmdot

9 oayqnepu

10 pbzrofqv

11 qcaspgrw

12 rdbtqhsx

13 security

14 tfdvsjuz

15 ugewtkva

16 vhfxulwb

17 wigyvmxc

18 xjhzwnyd

19 ykiaxoze

20 zljbypaf

21 amkczqbg

22 bnldarch

23 comebsdi

24 dpnfctej

25 eqogdufk

看第13行，是一个有意义的单词，如果你这也不认识我就没有办法了。那么你就拿着13这个偏移，对ComeChina做移位操作，保持大小写一致，答案是PbzrPuvan。

题目2（158分）：密码学历史中，有两位知名的杰出人物，Alice和Bob。他们的爱情经过置换和轮加密也难以混淆，即使是没有身份认证也可以知根知底。就像在数学王国中的素数一样，孤傲又热情。下面是一个大整数:98554799767,请分解为两个素数，分解后，小的放前面，大的放后面，合成一个新的数字，进行md5的32位小写哈希，提交答案。

题目解析：这题比较简单，大数分解。如果你不用各种素因子分解的算法，直接用循环也能做的，循环的上限只要做到98554799767的平方根就行了，开根号是313934。我用的Python，这个长度没有受到限制。然后得到两个素因子分别是101999 和966233，所以答案就是对101999966233求得MD5值为d450209323a847c8d01c6be47c81811a。这里我在做题的时候，把尾部的换行符复制进去了，一开始提交失败，后面才发现，于是我是第四个解出本题的。

题目3（300分）二战时期，某国军官与一个音乐家情妇相好，然而自从那时起，他屡战屡败，敌人似乎料事如神。他也有怀疑过他的情妇，但是他经过24小时观察他的情妇，发现她每天都只是作曲，然后弹奏给战地电台，为士兵们鼓气，并未有任何逾越。那么，间谍到底是谁？这张曲谱是否有猫腻？ (答案为一个明文字符串，提交获得的有意义语句通顺字符串即可)

题目解析：这道题目第一眼看我基本上愣了，因为我不好意思地说，我不识谱。但是我发现图片是用软件生成的谱，也就是说，出题者可能其实没有主动利用谱的信息，比如节拍或者曲调，更多是为了把数字放在一起。

然后我就想有没有可能是竖排，但是又不是完全对齐。然后我发现里面歌词的提示，就往ASCII码方向想。于是我先横着把数字全部写下来，111114157166145123145143165162151164171126145162171115165143150，题目提到了八进制，于是用八进制试试看。

因为1位数字对应的ASCII太小，于是试两位，两位的结果是一堆不可见的符号，于是试一下每三位八进制取出来，作为值转换成十进制，再通过ASCII值转换成字符，于是得到结果ILoveSecurityVeryMuch。

这是个有意义的词组，搞定。300分啊……

题目4（500分）老牌刺客之王混进了女王的住所。一天，女王得到了一个匿名举报，说她的侍卫里有一个刺客，叫做Rabin，而他的信息就在一份文件里，文件中有附带一个Pk，是523798549，密文是162853095，校验码二进制值是110001，根据说明是放在明文后一起加密的，明文与密文长度相同。加密算法和这位老牌刺客同名。快拯救女王，答案是求得的明文，进行32位md5小写哈希字符串，提交即可。

题目解析：PK是公钥的意思。所以这是一道和公钥体制有关系的题目。公钥的算法有很多，比如RSA，比如ECC。Rabin算法也是一种，这个在大学时代是学过的。但是我第一反应是Miller-Rabin算法，这是一个基于概率的素数测试算法。其中的Rabin是指Michael O. Rabin，他是哈佛大学教授。我09年在清华还见过他，听过他的报告。但是还有一个Rabin公钥体制，我差点忘记了……这里花了一些纠结的时间。

其实Rabin的公钥密码体制和RSA有点类似，公钥n=p*q，私钥就是p和q。加密过程由明文m在平方后与n求模得到c，其次就是二次同余的过程。解密的时候就求出密文的平方根在两个私钥模值（p或者q）下的同余即可。

由于本题中的数不大，所以直接用程序暴力破解也可以。即找到一个数，使得其平方值与密文对于模值n同余，由于是平方，而且n不是素数，所以一共会得到四个解：115739001、408059548、214318436、309480113。

然后我们再看题目的信息，校验码的二进制值是二进制值是110001，我们看一下四个解中，偶数可以直接排除了，然后转换一下剩下的两个奇数解，得到309480113的二进制码“10010011100100100101010110001”，这后面六位和校验码是一致的。

那剩下的部分就是明文了，即“10010011100100100101010”，转换成十进制为4835626，求MD5值为ca5cec442b2734735406d78c88e90f35，得到答案。

这题500分。我刷完这道的时候发现竟然是第一个做出来的。这对我一个初次参加比赛的菜鸟来说感到很意外……然后发现做出这个后已经是第二名了……

总结感悟：

我开始以为密码学的题目有很多，刷完四道题后发现竟然通关了。然后我发现这些题目的得分还是挺多的，比如500分能让队伍提升将近十个名次，于是本来打酱油的心态就竟然对结果有一些期待。

但是如果你看我上面的分析，这些题目其实不是很难，而且需要绕的弯子也不多。所以我写这个总结不是说我水平有多高，而是想说这些题目不难，而且我也纯粹属于运气好，正好尝试的几个方向正好对上了。我上次研究密码学是在2010年，所以已经有5年没有怎么接触相关的文章了，去年也只是整理过一篇可证明安全的文章。

其实如果CTF的加解密部分要往难出还是非常容易的，比如在第三题，我一度的猜想是不是采用了Vigenère cypher（维吉尼亚密码），而如果如此，那就需要用卡西斯基试验（Kasiski examination）以及重合指数（index of coincidence）来做计算，那样难度就增加了很多。对于第四题，如果需要分解的大数长度再增加一些，引入一些手工计算的模块那也会出的很难。然后对于公钥部分，如果不用素数分解系列的公钥，引用椭圆曲线的公钥密码体制，出离散对数的问题，也能提高难度。

但是综观本次比赛，我一个感性方面的感受就是，我在五年前研究密码学的时候各种痛苦纠结，觉得这玩意太高深根本没法派上实用，谁能想到五年后一场无意的比赛，能把我这些忘记得差不多的知识变现，还是很欣慰的。所以结论就是，我们手头的事情，如果是你正要做的，那不妨努力把它做好，投入总是不会吃亏的，因为有的投资回报期会比较长，比如五年十年，而有的甚至更长，比如一生。

本文原文在http://scalerstalk.com/487-ctf-crypto ，首发ScalersTalk

=========
本文作者Scalers，游走在口译世界的IT从业者。微信公众号ScalersTalk，网站ScalersTalk.com
如需要转载请联系授权，否则将被公开谴责并追究法律责任。

ScalersTalk成长会回复“VIP”查看.口译100小时训练计划群B 433686569