2014年公开课计划

整个寒假都没有可以跟的课,老外果然都过圣诞节去了。新的一年有三门课非常给力:Convex Optimization、Statistical Learning和Networks, Crowds and Markets。

Convex Optimization的老师是经典教材《Convex Optimization》的作者Stephen Boyd。

Statistical Learning,老师是Trevor Hastie和Rob Tibshirani,俩人都是大名鼎鼎的《The Elements of Statistical Learning》、《An Introduction to Statistical Learning, with Applications in R》作者之一。《The Elements of Statistical Learning》的另一个作者Jerome Friedman发明了Gradient Boosting。

edX上Networks, Crowds and Markets在3月3日开课,这门课的老师也很强大:Cornell的Jon Kleinberg, David Easley, Eva Tardos。Jon Kleinberg是社交网络研究的神牛,2013年还拿了ACM SIGKDD 2013 Innovation Award。David Easley和Jon Kleinberg合著了《Networks, Crowds and Markets》;Eva Tardos和Jon Kleinberg合著了《Algorithm Design》的作者。这两本都是我比较喜欢的教材。《Networks, Crowds and Markets》之前读到一半,正好这次可以跟着课把书读完。

椭圆曲线和Dual_EC_DRBG后门

这两天爆出NSA收买RSA将NSA推荐的算法,Dual_EC_DRBG,设置为BSafe中默认的随机数生成算法。为了推广这种算法,其实早在2007年NSA就执意将其写入了NIST(美国国家标准技术管理委员会)的确定性随机数生成器推荐标准(Special Publication 800-90,SP800-90),即使它速度极慢。同年Dual_EC_DRBG就在Crypto 2007会议上被指出存在被植入后门的可能,但不能认定算法设计者是否知道后门的参数,也不能认定NIST有意在算法中植入后门。2013年9月Edward Snowden泄漏的内部备忘录显示NSA曾向某加密算法植入后门,再到12月路透社爆出RSA被收买,现在看起来是NSA精心选取参数值下后门。有意思的是,比特币也使用了ECC来生成随机数,但是比特币神秘创始人中本聪在2009年发明比特币的时采用了小众的secp256k1的曲线参数而不是有问题的secp256r1(NIST P-256),神奇地躲过了密码学子弹。
那么Dual_EC_DRBG漏洞在哪,为什么随机数生成器的漏洞会让加密算法被攻破?先要从椭圆曲线和随机数生成器说起。

椭圆曲线
椭圆曲线密码学(Elliptic curve cryptography,ECC)由Koblitz和Miller分别独立提出,是迄今为止安全性最高的一种公钥密码算法。椭圆曲线E的形式是:

y^2=x^3+ax+b, a,b \in F_p

有限域Fq,q一般是2的m次方或大素数p,也可以是某素数p的m次方。参数a,b确定椭圆曲线E。
它的安全性基于有限域椭圆曲线离散对数问题(Elliptic Curve Discrete Logarithm Problem,ECDLP)的难解性:
给定素数p和椭圆曲线E,对Q=dG,在已知G,Q的情况下求出小于p的正整数d。可以证明由d和G计算Q容易,而由Q和G计算d则是指数级的难度。
G对应为椭圆曲线E的基点,d为私钥由自己选择,然后生成对应公钥Q=dG,得到密钥对(d, Q),私钥自己保存,(p, a, b, G, Q)是已知的,但是由p和G计算私钥d很难,保证了加密算法的强度。
还有2种公钥密码体制分别基于大整数分解问题(Integer Factorization Problem,IFP)的难解性,如RSA,和有限域离散对数问题(Discrete Logarithm Problem,DLP)的难解性,如Diffie-Hellman、ElGamal。但是ECC问题要比DLP问题更难解,并且ECC用更少的密钥长度提供相同的加密强度。
这次出问题的Dual_EC_DRBG,全称Dual Elliptic Curve Deterministic Random Bit Generation,是基于椭圆曲线的确定性随机数生成器。

随机数生成器
随机数在密码学中具有十分重要的地位,被广泛用于密钥产生、初始化向量、时间戳、认证挑战码、密钥协商、大素数产生等等方面。随机数产生器用于产生随机数,分为非确定性随机数生成器和确定性随机数生成器两类:
非确定性随机数生成器(NRBG)基于完全不可预测的物理过程。确定性随机数生成器(伪随机数生成器,DRBG)在指定初始种子之后,利用某些算法产生一个确定的比特序列,“确定性”因此得名。如果种子是保密的而且算法设计得很完善,那么可以认为输出的比特序列是不可预测的。
加密算法需要高度随机性的“种子”来生成密钥,因此随机数生成器会直接影响加密强度和安全性,脆弱的随机数生成器被攻破会击溃整个加密算法,比如Android随机生成数字串安全密钥中的漏洞就导致了部分比特币的失窃。

Dual_EC_DRBG后门
这个后门的发现可以追溯到六年前,NIST在2007年发布了确定性随机数产生器推荐标准SP800-90修订版。这是一个推荐性的标准,描述了一些产生随机比特流的方法,这些随机比特流可能被用于直接或者间接的产生随机数,并用于相关使用密码学的应用中。NIST SP800-90提供了4种标准算法:Hash_DRBG(基于SHA系列算法)、HMAC_DRBG(基于HMAC函数)、CTR_DRBG(基于分组密码函数AES)、Dual_EC_DRBG(基于椭圆曲线)。
在4个月后的Crypto 2007会议上,Dan Shumow和Niels Fergusonsuo作了一个报告,宣称标准中的Dual_EC_DRBG设计存在严重漏洞,具体可以参看报告On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng...智商不够用了,我的理解是:
P, Q是ECC上两个基点,且满足eQ=P,点Q常量可以确定万能钥匙。如果攻击者知道私钥d满足Q=dP,计算eQ=P是容易的,存在a*e=1 mod p。反过来如果攻击者知道e,以及一些已知的随机值,攻击者可以计算出点G,然后可能能确定DRBG的内部状态,并预测DRBG后来的输出。一个“局外人”可能并不知道这种特殊关系的存在,但是如果知道了P和Q之间关系的“密钥”,攻击者可以利用Dual_EC_DRBG存在的后门得到该算法后续所有的随机数值,从而破坏不可预测的性质,预测其使用的密钥,进而攻破整个加密算法。

DES S-BOX的传说
DES中S盒来路不明是密码学届的一个著名的谜团,也和NSA有关。1975,IBM刚搞出DES(Data Encryption Standard)时候,NSA就对S-Box做了修改,并将密钥长度由128bit缩减为56bit,但未说明原因,直到80年代差分分析被公开学术界发现后,人们发现针对DES16轮的差分攻击效率甚至不如穷举,于是怀疑在设计DES的S盒和加密轮数时,差分攻击的方法就已经被发现了,而NSA那个修改证明是为了对抗可能的差分分析。

神经网络与数据压缩

神经网络除了用于Regreesion和Classification,还可以与用于数据压缩Data Compression。自联想神经网络Auto-Associative Neural Network是三层BP网络,它的特点是输出是对输入的一种重构,即输出等于输入或者允许输入输出有一定的误差存在。如果中间层Hidden Layer节点少于输入层Input Layer,中间层可以用更少节点表示输入层的数据同时可以在输出层重构出输入层数据,这就是数据压缩和解压的过程。

从另一个角度来看,中间层提取出数据中最重要的特征,用更少维度表示输入数据。如果我们在网络中不使用sigmoid函数,而使用线性函数,这就是主成分分析PCA模型。

在深度学习中,上述结构被称作自编码神经网络Autoencoder Neural Network。

PhantomJS+CasperJS备份微博

备份微博通常调用新浪微博提供的API就可以了,但是我并不关注文本数据,更需要得到一条微博原原本本的显示内容,就像archive.org对网站进行备份一样,可以将微博截图快照下来。

对于网页快照,可以使用PhantomJS进行截图。PhantomJS是一个支持JavaScript API的无界面、运行于服务端的WebKit环境(Headless WebKit with JavaScript API),Headless这里的意思是渲染页面在后台完成。PhantomJS可以用来进行前端自动化测试、网络状况监控、网页渲染后自动截图等。但是微博快照和网页快照不同,微博快照在网页渲染后,只是截取页面上指定的区域(DOM),依赖于PhantomJS的CasperJS提供了更强大的函数封装、方法和语法糖,可以完成定义排序浏览器导航步骤、填充提交表单、点击跟踪链接、指定DOM元素区域截图等任务,当然也可以实现备份微博。

首先使用CasperJS模拟用户登陆微博过程,填写用户名密码并提交表单。

var casper = require("casper").create();
casper.start('http://www.weibo.com/login.php', function() {
    this.fill('div[class="W_login"]', {'loginname':'YOURUSERNAME'}, false);
    this.fill('div[class="W_login"]', {'password':'YOURPASSWORD'}, false);
    this.click('a[class="W_btn_d"]');
});

用CasperJS给页面上指定的区域(DOM)截图非常简单:调用captureSelector,给页面中'.WB_feed_type'选择器匹配的元素截图,输出的文件名为微博的mid号。

casper.thenOpen('http://weibo.com/u/UID',function() {
    mid=this.getElementAttribute(".WB_feed_type", "mid");
    this.captureSelector(mid+'.png',".WB_feed_type");
});

最后获得的微博截图效果如下,加入cron定时任务就能自动备份。现在个人微博首页只显示5条最新微博,可以每次将5条微博全部备份,同时设定合理的更新间隔时间,可以避免只备份最新微博但是在更新间隔时间里新增了多条微博的问题。类似的,稍加改动还可以应用于备份twitter豆瓣的timeline。

weibo_capture

close