EE vs. CS

目录 IT杂谈, 读书

这是一篇很古老的文章,翻译得不好,大家将就着看。

固定链接:http://share.solrex.org/os/ee_vs_cs_cn.html

从前,在一个离这儿不远的国家,一个国王召来他的两个谋臣进行一项测试。国王给他们看了一个闪闪发光的金属盒,盒子上面有两个插槽,一个控制按钮和一个手柄,然后问道:“你们认为这是个什么东西?”

其中一个谋臣,电子工程师,抢先答道:“陛下,这是一个烤吐司机。”国王问他:“如果让你给它设计一个嵌入式计算机,你会怎么做?”这个工程师回答说:“利用一个4位的微控制器即可,我将写一个简单的程序读入亮度盘(译注:the darkness knob,不知道是什么东西),将其量化到从雪白到煤黑的 16 阶亮度水平上。这个程序将使用该亮度水平作为 16 个初始时间值表的索引,然后启动加热元件,用该亮度水平映射到的时间初始化计时器。在计时结束后,关掉加热元件,弹出烤好的吐司。如果您愿意的话,下星期我就能给您一个可以工作的原型。”

第二个谋臣,计算机科学家,立刻认识到了这种短视想法的危险。他说:“烤吐司机并不仅仅是用来把面包变成吐司的,它们同样会被用来加热冷冻华夫饼。在您面前所放置的其实是一个早餐厨具,当您的臣民变得越来越老练时,他们将需要它提供更多功能。他们会希望早餐厨具同样可以用来烤香肠、煎培根和炒鸡蛋,一个只能做吐司的烤吐司机将会很快被大众废弃。如果我们不未雨绸缪,在不远的几年后我们就不得不完全重新设计烤吐司机。”

“考虑到这一点,我们可以制定一个更好的解决方案。首先,创建一个早餐食品基类,特殊化这个基类到几个派生类:谷物、猪肉和禽肉。特殊化的过程可以重复进行下去,比如谷物可以派生出吐司、松饼、薄煎饼和华夫饼;猪肉可以派生出香肠、links和培根;禽肉可以派生出炒鸡蛋、煮鸡蛋、荷包蛋、煎鸡蛋和多种煎蛋卷类。”

“火腿奶酪煎蛋卷类尤其值得特别注意,它必须同时继承猪肉、奶制品和禽肉类的特点,除了使用多重继承,这个问题无法得到妥善解决。在运行时,该程序必须创建合适的对象,并发送消息到该对象:‘把自己弄熟。’当然,由于多态性,这条消息的语义取决于该对象的类型,所以它对于吐司对象和炒鸡蛋对象分别具有不同的含义。”

“回首目前我们的进程,可以看到,分析阶段揭露了一个基本的需求,那就是该厨具需要能做出任何种类的早餐。在设计阶段,我们发现了一些衍生的需求,特别是我们需要一个面向对象的、支持多重继承的语言。当然,没有哪个用户希望当煎培根时鸡蛋变凉了,所以并行处理能力也是必要的。”

“我们绝对不能忘记用户界面。用来控制食物的手柄缺乏通用性,亮度盘令人困惑。一个产品必须具有友好的图形界面,否则不会受到市场欢迎。当这个早餐厨具启动时,用户应该看到一个牛仔出现在屏幕上。用户点击它后,一条消息“正在启动 UNIX v.8.3”将显示在屏幕上。(当该产品推出时,Unix 8.3 应该已经发布了。)然后用户可以下拉菜单,点击他们想做的食品。”

“当在设计阶段做出首先规划软件的聪明决策之后,在实施阶段剩下的只是选择一个合适的硬件平台了。一个使用 Intel 80386 CPU,拥有 8 兆内存、30 兆硬盘和 VGA 显示器的机器应该足够了[1]。如果你选择了一个多任务、面向对象、支持多重继承且内建图形用户界面库的编程语言,写这样一个程序是件轻易而举的事情。想想如果我们傻乎乎地允许一个硬件优先、将我们锁定在一个 4 位微控制器上的愚蠢设计将会给我们带来多少困难!”

国王听完他这番话,作出了将这个计算机科学家斩首的英明决定。人们从此过上了幸福快乐的生活。

[1] 在这篇文章出现的当时,这应该算是挺先进的配置了。

Math in CS: 数论和公钥密码学

目录 安全, 数学, 社会, 算法

1940年,英国数学家哈代在他的一本小书《一个数学家的辩白》(A Mathematician's Apology)中说:“如果有用的知识是这样的知识(我们暂时同意这样说):它大概会在现在或相对不远的未来,为人类在物质上的享受方面作出贡献,因而,它是否在单纯的智力上满足人们乃是无关紧要的,那么,大量更高级的数学就是无用的。现代几何和代数、数论、集合论和函数论、相对论、量子力学——没有一种比其它的更经得住这种检验,也没有真正的数学家的生涯可以在这个基础上被证明是有价值的。”但是我们会看到,哈代这个断定在当时“不远的未来”几乎被一一证明是错误的,数论就是其中一个。

在 1970 年代以前,人们所知道的密码学都是对称密码学,就是在加密和解密过程中需要使用同一个密钥。在那个时代,一些密码算法已经能保证足够的安全性,比如数据加密标准 DES。但是人类的需求是很难完全得到满足的,他们为每次密钥交换的复杂度而苦恼,比如在战时如果密码本被敌方获得,就必须重新向无线电收发员分发密码本,这个工作量和代价是相当大的;还有一个需求就是数字签名,能不能用加密实现对数字文件的签名,像手写的签名一样,确保该文件出自谁人之手?

上述问题,就是 Whitfield Diffie 和 Martin Hellman 1976 年在他们那篇划时代的论文《密码学的新方向》(New Directions in Cryptography)中提出的,他们也给出了其中一个问题的解决办法,那就是 Deffie-Hellman 密钥交换算法(后来被改为 Deffie-Hellman-Merkle 密钥交换算法,里面还有一段小故事。)。但是 DH 没做完的功课,仅仅在一年后就被 RSA 解决了,那就是 Ron Rivest, Adi Shamir, 和 Leonard Adleman 的 "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems"。RSA 的加密和解密使用的是不同的密钥,即公钥和私钥,你可以将你的公钥扔到世界上任何一个位置,我用你的公钥加密一段信息,除了你用自己的私钥解密,没有别的人能从中得到原始消息。就相当于你把打开了的箱子扔的满世界都是,但箱子一旦锁上,就只有你能再打开。

RSA 算法自其诞生之日起就成为被广泛接受且被实现的通用公钥算法,但是 RSA 算法还带来一个另外的意义,那就是:数论知识从未像现在这样被广泛地使用着。RSA 程序的普及率要远远大于 Windows,因为每台 Windows 上都装配着 RSA 算法程序,但 RSA 并不仅仅装配 Windows。每当你登录邮箱、网上银行、聊天软件、安全终端,你都在使用着数论带来的好处。而且相比之前密码学的字母替换和置换,混淆和扩散,DH 和 RSA 使用的东西更有资格说自己是数学。

大概也是由于其基于数学的简洁性,RSA 和 DH 算法描述要比 DES, AES 简练许多,我在这篇小文中都能写完。

RSA

RSA 用到了数论中的三个基本定理:费马小定理、欧拉定理和中国剩余定理(几乎处处都在),和一个古典难题:大整数分解问题。如果你是数学系的学生,对这些概念一定不会陌生。

费马小定理:若 p 是素数,a 是正整数且不能被 p 整除,则: ap-1 = 1(mod p)。或者另一种形式:ap=a(mod p),这种形式不要求 a 与 p 互素。

欧拉定理:对任意互素的 a 和 n,有 aΦ(n) = 1(mod n)。其中,Φ(n)是欧拉函数,即小于 n 且与 n 互素的正整数的个数。

大整数分解问题:将两个整数乘起来是简单的,但是将一个整数分解为几个整数的乘积是困难的,尤其是当这个数比较大的时候。迄今为止没有有效的算法来解决这个问题,甚至我们连这个问题的计算复杂度量级是多少都不知道。

那么 RSA 算法是什么样的呢?

密钥的产生:
1. 选择两个素数 p 和 q.
2. 计算 n = p*q.
3. 计算 Φ(n) = (p-1)(q-1) (这是欧拉函数的性质)
4. 选择 e<Φ(n) 并使得其与 Φ(n) 互素。
5. 确定 d<Φ(n) 并使得 d*e = 1(mod Φ(n))。
6. 这时候,私钥就是{d, n},公钥就是{e, n}。
加密算法:
假设 M 是明文(M<n),那么密文就是 C = Memod n。(为什么明文是数字?在计算机科学里任何数据最终表示都是数字。)
解密算法:
假设 C 是密文,那么明文就是 M = Cd mod n。

我们来证明一下算法是否正确,由于 Cd = Me*d = Mk*Φ(n)+1 (mod n)。

如果 M 和 n 是互素的,显然直接由欧拉定理我们就能得到:
Cd = Mk*Φ(n)*M1 = M (mod n) = M
说明算法是正确的;
如果 M 和 n 不互素,由于 n 是两个素数 p 和 q 的乘积且 M<n,那么 M 要么是 p 的倍数,要么是 q 的倍数,由 e*d = 1(mod Φ(n)) = 1(mod (p-1)(q-1)) 我们可得:
e*d = 1(mod (p-1)) 且 e*d = 1(mod (q-1))
则 e*d 可以写成: e*d = k*(p-1)+1, e*d = h*(p-1)+1
由费马小定理,我们有:Me*d = Mk*(p-1)+1 = M(mod p) 和 Me*d = Mh*(q-1)+1 = M(mod q)。
由于 p 和 q 均为素数,且 p, q 均整除 Me*d-M,所以我们有:
Cd = Me*d = M (mod p*q) = M (mod n) = M

从上面我们可以看到 RSA 算法实现了加密和解密使用不同密钥,而且证明了这个算法的正确性。但 RSA 算法要想实用,光有正确性还不够,最重要的一点是安全性,即从公钥{e, n}无法推导出私钥{d, n}。在 RSA 算法中我们可以看到,关键要知道 Φ(n),知道了 Φ(n),使用欧几里德算法就能求出 e 的逆元,就得到了用户的私钥{d, n}。要求出 Φ(n),就必须知道 p,q,但 p,q 是不公开的,仅仅知道 p,q 的乘积 n 去求 p,q,根据大整数分解古典难题,当 n 比较大时其分解在计算上是不可行的。这就保证了 RSA 算法的安全性。

而且 RSA 算法是可逆的,所以它就有能力同时实现加密和签名的功能。由于公钥是公开的,每个人都可以用你的公钥加密一段信息发给我,而私钥是保密的,所以只有你能看到别人用你的公钥加密的消息;而也因为可逆性,如果你用私钥解密一段明文(实际是加密),所有人都可以用你的公钥加密它来得到明文(实际是解密),因为私钥只有你一个人知道,这个消息只有可能是你发出的,就相当于你对这段明文做了一个签名。

DH 密钥交换算法

DH 密钥交换算法较 RSA 算法更为简单,它也是基于数论中的一个古典难题:离散对数问题。

离散对数问题:若 p 是素数,p 已知,考虑方程 y = gx mod p,给定 g,x 求 y 是简单的,但给定 y,g 求 x,即求 x = logg,py mod p,在计算上是不可行的。

DH 密钥交换算法的描述如下:
已知公开的素数 p 和 p 的本原根 α
1. 用户 A 选择秘密的 Xa<p,计算 Ya = αXa mod p,将其发送给 B。
2. 用户 B 选择秘密的 Xb<p,计算 Yb = αXb mod p,将其发送给 A。
3. A 和 B 分别计算 Ka = (Yb)Xa mod p 和 Kb = (Ya)Xb mod p,就同时得到了共享的密钥 K=Ka=Kb,然后就可以用 K 进行加密传输了。

DH 密钥交换算法的优点在于:双方在通信前不需要知道任何共享的密钥,而是通过公开的 p 和 α 协商出一个密钥来进行加密通信。

先看一下算法的正确性,Ka = Kb 是否成立:
Ka = (Yb)Xa = (αXb)Xa = αXa*Xb (mod p)
Kb = (Ya)Xb = (αXa)Xb = αXa*Xb (mod p)
Bingo! Ka 和 Kb 是相同的。

再来看一下算法的安全性,就是能否从公开的信息推导出 K 来:
由于密钥是 K = αXa*Xb,那么攻击者必须知道 Xa 和 Xb 才能得到共享的密钥 K,而公开的信息只有 Ya 和 Yb,由离散对数问题,从 Ya,Yb 求出 Xa,Xb 在计算上是不可行的,就保证了算法的安全性。

从上面两个算法我们可以看出,数论在公钥密码学中的重要地位,恐怕哈代当时怎么也想不到三十多年后人人都在使用他所认为在实际生活中毫无用处的数论吧!

薄弱的算法基础

目录 算法

这几日复习累时,翻出来 MIT 的《算法导论》课程录像来看,发现一个非常沮丧的事实:我对算法知道的真少。

仅仅看了 3 节课,就听到了几个我不懂的东西。比如计算递归算法复杂度的 master method,计算 Fibonacci 数列的复杂度为 θ(lg(n)) 的算法,计算矩阵相乘的复杂度为 θ(nlog2(7)) 的 Strassen 算法。这些东西我以前都没听说过,真是孤陋寡闻啊!

那本《算法导论》大概在我的书架上已经摆了两年了,两年我仅仅看了六七十页。我太懒是最主要的原因,但还有一个原因是从头开始看激发不了兴趣,前面讲的一些算法都是数据结构书上看过的东西,不是很有吸引力,看着看着就觉得索然无味,扔一边了。

不过我也从来没自诩过算法好,逛 BBS 时我主要在电脑技术版转,在其它的版都敢指手画脚一番,唯有在算法版老老实实潜水。计算机科学就是这样,知识层次不如别人,那就根本插不上话。这也是我极少在 pongba 兄的 TopLanguage 讨论组发言的一个原因,因为里面我感兴趣的话题主要是算法相关,而算法问题我又插不上嘴,只好默默潜水。

我的算法知识,大概仅限于我现在都不知道扔哪儿的一本《数据结构》书了。不是科班出身,也没正儿八经听过算法课,所以现在就有系统地学习算法知识的打算了,把存在电脑里好久的算法导论视频翻了出来。Charles Leiserson 讲的很不错,单就趣味性来说,《算法导论》的课程录像可比书要有意思多了。我想在最近的这段时间里,我应该至少能把录像看完。

另外,我在博客分类里添加了 Algorithm 一项,我将看看,在过一段日子后,我对算法的使用和理解能力能否有一些提高。