Results tagged “cryptography”

周三下午完成了《密码学》这门课的期末考试之后，我就有种想法想写这篇文章。可是接着有周五要交的《专家系统》学期项目要赶，所以这两天一直没有机会，当时的想法也淡忘了许多。

对于密码学这门课本身，我感觉是处在了一个比较尴尬的地位。首先是这门课的面向，在我们学校的课程中属于 4000 等级的课，也就是说一般是给大四的学生来学的。密码学本身有一部分数学相关的知识需要理解，又不是每个人日常都必须了解的，因此放在 4000 等级，意思是不需要每个人都学这门课，如果学生对于这个领域有兴趣的话，可以修这门课。因此我们这门课上的同学并不算多。另一个方面是这门课的难度，我们在这学期学了以下几个部分：基础密码（比如 substitution cipher，affine cipher 等）的加密与破解、信息论与 block cipher、DES 与 AES、RSA 加密、Hash 函数。这些部分需要用到的数学知识其实并没有许多，除了一般的加减乘除外，有限域的知识（就是取余数）比较常用外，极限之类的东西就用得非常少了。学完了这门课之后，我觉得一个大学二年级毕业的学生，离散数学合格毕业的学生完全可以学这门课程，根本不需要等到大四去学。

在做期末考试卷子的时候，我有股感慨，为什么这门课不能开卷考试呢？很多相关的东西，我们考察的都是对于定理和公式的背诵。我想，将来在实际的应用当中，我们需要把这些公式全都背过吗？尤其是如果不从事密码学领域的钻研的话更是如此。日常写个程序，首先是当前的算法已经有很多公开的代码可以直接使用，而且就算要自己重新写，也可以找论文来参考再实现。而一个程序员把加密解密的定理公式都熟记于心的话，是不是不是很现实呢？

我在尤其是来加拿大之后，就有感觉记忆力下降的趋势。过去初中时看两眼就能背诵的东西，到了高中时可能就要看两天了，而到了大学后就要看更多的时间，而且一段时间后就忘记了。特别是英文的资料，死记硬背的话更是不容易。

我觉得密码学是一门实践性质的课，给你一段密码，用某种解密方法来揭开，如果能有一个这个方法的实施表格，这样做起来应该会很容易。可是如果加上了记忆这一步，对于一个记忆力不好的学生来说就不是那么简单了。

另外，我们的老师在给我们上课的时候，也是拿着自己的笔记在往白板上抄写。我不是说老师一定要与学生公平，但是否老师能按照要求学生的要求来要求自己呢？如果在考试的时候，给学生一些记忆方面的题，那么自己能否同样做到呢？而且，这门课对最让我们觉得不满的是，在最后考试前不画范围。老师说我们需要了解期中考试前和期中考试后的所有内容，这样的话还干什么需要期中考试呢？我们有这么多东西要背诵，能否把量减少一些呢？

总结起一个学期的课来，我觉得我作业部分做得还不错，这是为什么呢？还不是因为开卷。这样作为一个密码学课程的结业要求来说是不是正常呢？这门课如果没有期末考试的话，是不是可以单从作业就可以判断出学生对课程内容的领悟呢？

今天早上上完了《密码学》的最后一堂课。标题里说“无聊的听课”，意思是“密码学”本身并不无聊，但我们老师的讲课实在是让人觉得难以恭维啊。

我印象里似乎之前写过文章说过这个老师，但刚才找了一下没找到，就再写一次。这个老师有一摞厚度大约一厘米的讲义（我觉得用“笔记”一词更适合一些）打印稿，也不知道是他之前自己写的还是前一任老师留下的。每次上课就按照讲义来讲，主要是把讲义的内容写在白板上，然后我们在下面记录下来了事。有的时候他还会把讲义抄错，让我感到很纳闷，难道老师就是抄笔记的工具吗？当然老师本身的知识能力应该是无可厚非的，至少对我们来说都绰绰有余了，但讲课的水平和理念都让人感到不解。今天是最后一节课，老师还在讲内容，最后还说这些内容可能会出现在期末考试上。而且还坚持不给我们区分考试范围，意思是从学期开始到结束的每一堂课都有可能考到，这样期中考试还有什么用？

其实对这门课的考试内容，我觉得很值得商榷。比如说从期中考试看来，很多公式、定理都需要记住。而在实际应用中，难道要求一个密码领域工作者记住所有的公式吗？老师自己在讲课的时候不也是要对着笔记来抄吗？我感觉考那些内容都是一种折磨。

密码学这门课在我们专业属于 4000 等级的课，也就是一般放在最后学习。听上去挺吓人，可到了最后回顾一学期的内容，我却发现很多东西都是非常明显的，看指定的教科书就能很容易看懂，更好的方法是老师直接把自己的讲义整理成教材，我们连买书的钱都省了（书价换算成人民币可不便宜）。我的想法是，老师在课堂上不应该重复我们可以从书上（尤其是教科书）看到的内容，延伸一下、展示一些例子、甚至讲一些课程相关的八卦（密码学领域里有不少）也比纯粹抄书好。

举例来说，有一次他给了我们一个算法，输入三个数 y、b、n，返回 y ** b % n，用指数奇偶的优化方法。在教科书上也给了这么一个算法，老师竟然也在白板上重复了一遍。其实这么个算法只要两分钟一提就可以了，最多最多告诉学生在书上的编号就行了，毕竟是 4000 等级的课。

老师经过了一个学期，总算在最后一天讲完了课程内容，其实根本不必那么多时间。到了课程的最后，同学们更想听听考试的范围，老师竟然也绝口不提，只让我们复习笔记和作业。

这个学期中我在这门课上用 ConTeXt 来记笔记、写作业，熟练了一些用法，也算是功德一件。当中有一位同学拷贝了我的一些笔记，也算是认识了新朋友。今天最后一课上万，竟然有两人向我要笔记。第一位有两天没来，留下了邮箱地址请我发给他。第二位上来给我搭话，我就知道要干什么了。他问我要整个学期的笔记，说是用一杯咖啡来换。我说不用，直接把笔记给你就是了，但他坚持给了我 20 加元，也算是意外之喜吧。

从回来之前就在家里看《Programming Ruby》，想尽快把这门语言入门。我以前也说过，对我来说，过去的知识常常会阻碍我接受新知识。过去学Python的时候是这样，现在学Ruby的时候也是一样。其实这类语法类似的脚本语言，它们的语法我早就基本掌握了，欠缺的就是解决某类问题的经验，以及对相应库的了解程度。这些就与实际编程的经验有关了。

为此，我最近写一些程序都是用的Ruby。就算用其它语言可以很快解决的，我也尽量用Ruby完成。我们密码学的第一次作业中的一道题，很简单，给一串密文：

TQLEQ TCDEJ ZFOZY EDFNN PPOEC JECJL RLTYX

而且告诉了它是用shift cipher（就是每个字母都换成了字母表中牌子后面的字母，如abc被加密成了def，就是字母被换成字母表中排在后面3位的字母了）来加密的。让我们从1到26，用穷举来列出每种情况，然后再判断原文是什么。

本来计划是用Ruby来写的。像这种不算复杂的算法类程序，又是与字符串相关的，用这种脚本语言最合适了──不用写与问题本身无关的冗余代码。题目的要求是用C、C++、Java或Pascal这些语言来写，其它语言需要教授批准。为了这个，我还专门找了教授，问他能不能用Perl、Python、Ruby这种script languages来做。后来他同意后，我就开始用Ruby来写。

结果花了我几乎半天的时间，我的结果简直可以用“惨不忍睹”来形容了。我把字符串放在数组里面，每次调用.next!来改变当前的字母。但由于Ruby的引用策略的关系，导致我的修改无法返回原数组去。因此总是出一些奇奇怪怪的错误。

本来打算再找时间研究一下的，但昨天上午的《计算机网络》这门课的实验课，要我们用C语言写socket程序。服务器端读取公交车的到站时间，客户端发送目前时间和公交车的车次，服务器端返回下一个到站的时间。自从学了脚本语言后，我越来越少用C语言认真的写程序了。主要是字符串那些东西，经常出错，远不如脚本语言方便，就连Java也比C语言方便不少。因此看到实验要求，我虽然有点怕，但还是硬写下去。结果竟然被我写出来了。

有了实验作业给我的底气，我觉得用C来完成密码学作业也不是太难了，就试着用C来写。结果让我意外的是，不到半小时这个程序就像模像样了。总共也不过30多行，比我之前用Ruby写的半成品多不了几行。

经过这件事，我开始反思我在这几年是不是对写程序不那么严肃了。如果让我评价对几种语言的喜好程度，我一定觉得脚本语言胜过C之类的语言。我花在Python上的时间比较多，而除了Java外，C语言和C++语言我几乎没有怎么“涉猎”。是不是有点避重就轻？是不是应该在平时多花一点时间在低级语言上呢？希望我在这个学期内可以有所改善。

我们的密码学课程的作业之一就是老师给你一段字母拼成的文字，单词已经划分好了，每个字母都代表另外一个字母，让你翻译成原文。翻译的方法是通过找出一些特殊的部分，不如两个相同字母结尾的单词、单字母单词之类的，来找出更多的字母。对于这种方法的难处，我在之前的文章里有过描述。其中也说了我要写个工具来帮我干这个事情。今天用Ruby简单的写了这么一个。放在了这里。

经过测试，程序能按照我的想法来做事。比如那篇文章里说的SKYQD一词，我有了arge结尾后，怎么也想不到large这个词。有了这个工具，运行match.rb SKYQD | grep arge就可以了返回large了，应该会给我的工作有很大帮助。程序的原理也很简单：对于SKYQD，先把它处理成一个标准的模式──ABCDE（更好的例子是HYTOOW，处理成标准模式后是ABCDDE）。然后再从保存了处理成标准模式的英文单词的Hash中查找就可以了。我是Ruby初学者，因此写的代码也没有什么优化，应该也挺罗唆。

目前这个程序有几个问题。

一是程序中上来先把我之前获得的英文单词都处理成我要的模式，这样每次运行都来一遍，应该挺废时间。我在想说不定把处理完毕的Hash保存起来可能会更有效率。

二是我目前的单词列表非常不够。我目前的单词列表是在这篇文章里说的，通过一个小程序在一个网站上抓取的所谓“常用单词3000字”。有很多单词都却是，因此我得到的常常就是Not Found。我无法在网上找到非常全面的单词列表，因此可能要写个程序从网络上解析网页抓单词。因为我们的这些句子经常是老师从Winnipeg Free Press上得到的，如果能把这个网站上用到的单词都作为程序的基础，那么破解起来应该会更方便。

第三点就有点提高了。目前这个程序只是按照我的要求来寻找合适的单词，并不能更进一步帮助我。如果能把我的单词列表中的单词都配上一些属性，通过人工智能上的一些技术来做进一步的筛选的话，应该会更方便。我在一年前学《人工智能》的时候，有一项作业是用Prolog来写一个检验一句话是否符合日本俳句的标准。如果能结合这两点，让程序帮忙整句的筛选，那就更理想了。