公钥安全机制与宫爆鸡丁的故事

你有没有在网上买过东西？没？什么？哦，怕不安全。
现在信息科技日新月异，貌似一转眼的功夫，交电话费、考试报名、逛图书馆、订购午饭都搬上了互联网。方不方便且不说，单说足不出户能叫到午饭，这要在以前那可都是科幻小说啊。只不过科幻小说里，主人公可能只须对机器人吩咐说，“来份宫爆鸡丁盖饭，外加一碗紫菜鸡蛋汤”，一切就搞定了——哪像现在这样，装五花八门的杀毒软件，还得随时小心钓鱼网站的陷阱。那现在的互联网真的如此危险么？先看看大宝的这次订餐经历，您再下结论也不迟。
话说大宝一日宅在家中，百无聊赖地度过了阴雨连绵的上午，忽然感觉腹中空虚，四肢无力——他明白了，原来自己是饿了。闲话少说，大宝奔到电脑前，准备给自己淘一顿午饭。
飘过了几家附近的餐馆之后，大宝决定在“啃的鸡”点一份宫爆鸡丁盖饭套餐。点完菜，服务员小姐礼貌地将大宝带到了收银台——这“啃的鸡”是先付帐、再上菜的。



（传说中的宫爆鸡丁。来源：

princeroy

， cc-by-2.0）
如果互联网上也可以用现金买单就好了，那么“啃的鸡”也不用再多花冤枉钱，聘用专业的银行交易专家来收银了。可惜现实往往跟理想相反，坐在收银台里的，正是传说中的银行交易专家：致富宝。“致富宝”作为专业的支付中介，能非常熟练地处理各种银行业务——不管是招行信用卡，还是农行借记卡，他都能应对自如。
就在这个时候，大宝忽然发现，带他来的服务员小姐溜回“啃的鸡”铺子里忙其它事儿去了，这“致富宝”原来是街边的一个小摊。再看这位摊主，正拿着宫爆鸡丁的单子，对着大宝得意地笑。大宝顿时惊出一身冷汗。
“糟糕！上当了！”
“大哥，这宫爆鸡丁儿不是你点哩？”摊主口音挺重。
“是倒是——你就是那个什么什么……银行交易专家？”大宝半信半疑。
“那能假了啊！你看看，工行农行中行建行……”摊主不高兴了。
“得得得，你要是个钓鱼的，也照样这么说。”大宝摆事实、讲道理，“营业执照给我看看，是真的就行。”

钓鱼

是指一些小商小贩，冒充自己是某支付平台或银行，骗取大众钱财的手段。
“俺哪敢掉你的鱼啊！”摊主边说，边从口袋里掏出一份证书，“你验验，这能假了不，这会儿打（假）的正严哩。”
这份证书可不是一般的营业执照。在数字世界里，光一个红红的公章印，说明不了什么问题。互联网上的电子证书，不仅包含一些基本信息如“摊主姓名”、“工作单位”、“邮政编码”等，还包含一把很重要的钥匙，和一个很重要的签名。
先说这把钥匙吧。其实这种钥匙是成对儿的，证书里面嵌的这把，叫做公钥；另一把由摊主保管，叫做——母钥？其实挺合理的，配对嘛——正确的叫法是私钥。从名字也可以看得出来，公钥是公开的，大家都可以拿来用；而私钥是个人保管的，比如摊主的这把私钥就由他个人保密持有，别人谁也拿不着。
这里，配对的两把钥匙之间是有数学相关性的，那这是怎样一种相关性的？用传说中的

RSA

算法举个例子吧，两把钥匙看上去是三个非常大（至少应该是，大的难破解嘛）的数字——私钥是 (7, 10)，公钥是 (3, 10)。
那这钥匙是怎么算出来的呢？
先选种子，随机选两个非常大的

质数

。在这个例子中，我选的是 2 和 5，但实际应用中应该越大、越没有规律越安全。这个时候，钥匙对中的公共部分 10 就算出来了：2 x 5 嘛。接着，3 也不难找——随便挑一个跟 (2 – 1) x (5 – 1) = 1 x 4 = 4

互质

的、且比 4 小的数就可以了—— 3 和 4 没法被同一个比 1 大的数除开，这样一来，我们的公钥 (3, 10) 就定下来了。接下来算私钥，这个稍微麻烦一点点，就是要找一个乘以 3 的积除以 4 的余数刚好等于 1 的数字——我选了 7，因为：7 x 3 mod 4 = 21 mod 4 = 1（这里的 4 还是前面 (2 – 1) x (5 – 1) 算出来的那个 4）。用数学点儿的话写下来，就是：
随机地选择两个非常大的质数 p 和 q，比如 2 和 5；
密钥对的公共部分就是 N = pq，就是例子中 N = 2 x 5 = 10；
算出一个中间数 M = (p – 1)(q – 1)，比如 M = (2 – 1) x (5 – 1) = 1 x 4 = 4；
选择一个小于 M，且与 M 互质的数 e，比如 e = 3；
根据 d x e mod M = 1 算出 d，比如 d = 7 因为 7 x 3 mod 4 = 1；
烧掉所有写着 p 和 q 的打草纸——因为“

不烧不专业

”嘛。
然后呢，公钥就是 (e, M)，或者简单说 3 也成，对应的私钥就是 7，而 10 是公共部分。
那这两把钥匙有什么用呢？我们还是先来做两道简单的数学题。
第一题，8 的 3 次方整除 10 的余数是多少？八八六十四，64 乘以 8，这个 64 乘以 8 ……不好算是吧，没事，这个例子可以偷点懒——只算个位数，反正不是要整除 10 么。8 x 8 = 64，4 x 8 = 32，结果就是 2 呗。
第二题，（用第一题的结果）2 的 7 次方整除 10 的余数是多少？2 x 2 = 4，4 x 2 = 8，8 x 2 = 16，6 x 2 = 12，2 x 2 = 4，4 x 2 = 8 ——数清楚了没，是 7 个不？结果正是 8。
没错，第二题的结果刚好是第一题里面的 8。这是一个巧合，还是一个愚人节玩笑？都不是，这是用数学方法证明过的（请见下面的分割线中间的部分），如果算出来不是 8 才是开玩笑呢。第一题中，我们其实用公钥 (3, 10) 把 8（我的银行卡密码，请勿模仿）给加密了——加密成了 2；第二题，我们又用私钥 (7, 10)，把加了密的密码给解出来了。



（二战德国所使用的的洛伦兹密码机。图片来源：

wikimedia

）
有那么点意思了，是吧。这样一来，我就可以用密文的 2 来代替明文的 8，放心地将密码告诉拥有私钥的人。即使密码中途被别人截获了，没有私钥的

骇客

依然无法取得我的密码。
有兴趣的话，您可以把公私钥匙调个个儿，再用相同的办法算一遍——也就是用 7 加密、用 3 解密，结果是一样可以还原的。但是反过来之后，如果我还是加密银行卡密码的话，我的智商就值得研究了——作为公钥的 3 是所有人都知道的，也就是说所有人都能解密得到原文，我根本用不着费事算来算去，直接把密码告诉大家就得了呗。这么做真的没有意义么？非也，这其实正是签名和验证。比如说，用 (3, 10) 是无法正确解密（验证）一段用 (5, 17) 加密（签名）的数据的，也就是说，“解铃仍须系铃人”，要想验证一个签名，只能用跟“签名用的私钥”对应的那一把公钥。而从理论上来说，私钥是个人保密持有的，所以我们可以通过解密的测试，来验证一段信息确实是原原本本地来自拥有私钥的人，而这个人也无法抵赖说“根本没这么回事儿”。
除非他把私钥弄丢了，别人捡了去。这一般情况下是有补救措施的——挂失嘛，钥匙丢了换锁呗。但是如果你根本不知道钥匙丢了，那就没辙儿了。比如说，既然 3 和 10 大家都知道了，如果什么人背地里偷偷算出了这个 7，那岂不是千里之堤，溃于蚁穴？
不必担心。
问题就在于，这个梁上君子打算怎么把 7 算出来。最直接也是最容易想到的办法，就是先将 10 分解成两个质因数 2 和 5，然后照前面的算法来算 7。这是唯一的办法吗？很遗憾，目前还没有人从数学上证明这是唯一的办法。为什么有人会去试图证明，这是唯一的办法？因为，他们还没找到其它更好的办法。恰巧，这个分解质因数的办法非常难。
因为打草纸烧掉了，所以理论上说，暂时没有别人知道 10 是由哪两个质数相乘得到的，一般情况下，算这个题的人（或是机器）也会很快忘掉这两个质数。虽然要破解前面的例子简单了点，但是有种你口算个一百来位的试试，呵呵。这也被相信是 RSA 算法的安全保障——对于非常大的数字，分解出两个质因数是非常困难的。这个结论目前还没有人证明，但也没有人证明它不困难。尽管大家说法不一，但是有一点是肯定的——数字越大越难算。有多难呢？

1999 年计算机花了五个月的时间

，解出了一个并不算很大的（512 bit）N 的两个质因数；而当 N 成倍增长时，破解的时间能到成百上千年——等到破解出来的时候，加密保护的信息可能早就不是秘密了。据说有人证明用量子计算机，可以在可观的时间里，破解更大的数字。看来一旦量子计算机成为现实，RSA 就要下课了——可惜眼下量子计算机还行不通，再加上我们选用的数字非常大，所以想简单地“把 10 分解成 2 x 5”，那是不可能的。
于是，要根据公钥 3 算出私钥 7 来，就几乎是不可能的了。所以，摊主可以安心地将公钥嵌在证书里，公之于众。例子中的 RSA 看似牢不可破，但现实中还需要许多的辅助手段，来进一步保证它的安全性。况且世界上也不是就 RSA 一家呀，所以嘛，这种公钥加密算法还是挺让人放心的。
总结一下了：“解铃仍须系铃人，系铃定是解铃人”（下半句我瞎掰的）。公钥、私钥都是一对儿一对儿的；要解密由公钥加密的数据，仅可以用对应的私钥；要验证由私钥签名的数据，仅可以用对应的公钥。这种“一个加密另一个解”的算法，一般就被形象地叫做“非对称加密算法”，这俩把密钥也被叫做“非对称密钥”。
如果这还没有满足您浓厚的数学兴趣的话，您可以继续阅读下面这段。（摘自维基百科，

RSA加密算法的操作

——不过貌似英文版更详细一点点）
==========哦美丽的分割线==========
公钥和私钥的产生
假设

Alice

想要通过一个不可靠的媒体接收

Bob

的一条私人讯息。她可以用以下的方式来产生一个公钥和一个密钥：
随意选择两个大的

质数

p和q，p不等于q，计算N=pq。
根据

欧拉函数

，不大于N且与N互质的整数个数为（p-1）(q-1)
选择一个整数e与（p-1）（q-1）互质，并且e小于（p-1）(q-1)
用以下这个公式计算d：d× e ≡ 1 (mod (p-1)(q-1))
将p和q的记录销毁。
e是公钥，d是私钥。d是秘密的，而N是公众都知道的。Alice将她的公钥传给Bob，而将她的私钥藏起来。
加密消息
假设Bob想给Alice送一个消息m，他知道Alice产生的N和e。他使用起先与Alice约好的格式将m转换为一个小于N的整数n，比如他可以将每一个字转换为这个字的

Unicode

码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为n。用下面这个公式他可以将n加密为c：



计算c并不复杂。Bob算出c后就可以将它传递给Alice。
解密消息
Alice得到Bob的消息c后就可以利用她的密钥d来解码。她可以用以下这个公式来将c转换为n：



得到n后，她可以将原来的信息m重新复原。
解码的原理是



以及ed ≡ 1 (mod p-1)和ed ≡ 1 (mod q-1)。

费马小定理

证明



???? 和????



这说明（因为p和q是不同的质数）



==========哦快乐的分割线==========
好了，回到我们饥肠辘辘的大宝的故事来吧。
“我现在验证一段话，如果你能解出来，就算这营业执照是你的吧。”大宝说着掏出一张白纸，背着摊主在纸上胡乱写下几个字——“戈壁滩上打酱油”。
大宝从证书中取出钥匙——也就是公钥了，再在纸上这么一比划，“戈壁滩上打酱油”几个字儿顿时被加密成 0101110…（篇幅所限，此处略去上千个 0、1）…1010101。
“给你，试试吧。”
“我说是我的就是我的，”摊主从怀里摸出一把旧钥匙（私钥，当然要藏好了），又在纸上一比划，“那还能错的了了！”
0 和 1 渐渐隐去，“戈壁滩上打酱油”几个字儿又冒了出来——解密验证成功，大宝无言以对，只得承认证书里的公钥的确是摊主本人的，除非摊主从真所有者那里抢的私钥。
“好吧，就算这证书是你的吧。那你凭什么说，你就是证书上写的，”大宝撇了一眼营业执照，“什么致富宝什么的？”
大宝说的没错，每个人都可以伪造证书，就算这公钥确实属于他又能何如。
“这买卖真难做！我不干了！”摊主这回真的急了。
“你不干了，我还要吃饭呢！”大宝也急了，二话不说把摊主拉到了工商局——

颁发营业执照的公信机构

。（可见，吃饭对大宝来说是多么重要）
到了工商局，办事员业务非常熟悉。
“证书真伪辨别是么，请出示证书。”
办事员拿着手持式扫描仪一扫，证书复印件就叮叮当当地出现在一旁的打印机中。只见他操起一把大剪刀，对着复印件“咔嚓”就是一刀，将证书拷贝一份为二。要不说他业务熟悉么，这一刀不偏不倚，刚刚好把前面提到过的电子签名部分剪了下来。
要说这电子签名是啥，还得先说这证书是怎么签发的。



（证书是怎样炼成的——最右边 OK 的那个。图片来源：OpenClipart.org，GFDL）
当初“致富宝”开道创业的时候，写过一份营业执照申请函，内容就是现在这剪下的两半中，比较大的那一半——电子签名是小半。工商局在评审了申请函之后，准予营业，于是签署了这一份证书，而证书中的电子签名正是官方签署的证据。
这到底还是公钥和私钥的讨论。话说工商局自己也有一对儿密钥，专门用来签署营业执照。当申请函得到批准的时候，办事员用工商局专用私钥在申请函上一比划，这申请函就被“加密”成了一段电子签名，也可以说，工商局在申请函上签名批准了。请注意，这申请函里到底包含什么呢？正如前面提到过，基本信息是必须有的，另外一个很重要的部分就是申请者——或者叫摊主——的公钥。毕竟公钥也是一种数据嘛，当作申请函数据的一部分来加密了。别弄浑了哦，办事员用工商局的私钥，加密了包含有摊主公钥的申请函，制作成了摊主证书的电子签名部分。这工商局的私钥可是公信机构独有的，平常要锁在很大的保险柜里的，所以签署出来的证书才是真的。
那我们就看看下一步，办事员怎么来辨别真伪吧。
“这是我们工商局的公钥，大家可以免费索取的。”办事员从柜台里搬出一箱子钥匙，说。
“那照这么说，有了这个，”大宝捡起一枚钥匙说，“我自己也能辨别真伪咯。”
“没错。”办事员也拿起一枚钥匙，在电子签名那一半上一比划，龙飞凤舞的电子签名乎的一下，变成了一份申请函的模样。
“哎哟，好像不对哦。”办事员拿过剪下的大半，跟刚解密出来的申请函一比，“这哪是致富宝啊，明明写的是致富堡嘛。”
大宝四下一看，那山寨摊主早溜之大吉了。真是虚惊一场，好歹大宝没有把钱给了那钓鱼的山寨摊主。
理论上，假的电子签名是不可能解密成跟原文仅一字之差的——实际上是什么都解不出来的，只有真的签名才能解出原文来。另外为了减小数据量和其它考虑，原文在签名之前，做过摘要处理。故事中做了一些简化，特此声明。另外，虽然说两种密钥都可以加解密，但专业地来说，公钥是用来做加密和验证的，私钥是用来做解密和签名的。
如果您拥有一份“个人电子证书”，那么您也可以用您的私钥签署数据——比如发电子邮件，那么收到信的人都可以用您证书中的公钥进行验证，以确认信件肯定是您亲笔签署的；反之，如果您的朋友有一份电子证书，那么您就可以很放心地用公钥加密一些只有您朋友可以阅读的数据，然后安全地通过您不信任的传播媒体——比如互联网——传递到您朋友的手中。电子签名在一定程度上，还保证了数据的完整性和不可抵赖性。



（一封给大宝的签名信，计算机可以验证其中的

PGP

签名）
后面发生的事情，就是大宝跟他验过真身的“致富宝”隔着一条河交易的过程了。没错，我是说隔着一条河——这个城市似乎忘记修桥了，大宝只能扯着嗓子喊，把他的银行卡密码告诉“致富宝”才行。现在互联网啊，真是危机四伏，你说那个路由节点上没趴着三五成群的嗅探器的（夸张手法，请保留意见）。要是大宝真个把密码喊出来，那没等他吃完饭，卡里的钱就全没了。所以咧，大宝就跟“致富宝”商量了一个办法。
这个办法当然就是加密咯。大宝想用对方的公钥加密自己的密码，然后“喊”过去，对方解密出来就搞定了。但问题是，大宝的数学实在是太差了，要算乘方的话，手指头根本不够他掰的。况且，要加密的也不仅仅只是 6 位密码，还有像“中国农业银行青岛市分行麦岛支行”这样的银行名，还有很长的银行卡号，更是还有大宝的大名——大卫／阿基米德／宝兰德／罗纳尔迪尼柯夫斯基。要让他把这些都加密算出来，非把他饿死不可，非对称加密算法并不适合于大批量的数据加密。所以，大宝想出了另一个办法——

对称加密算法

。
说白了，就是用同一个，也是唯一一个密钥做加密解密的算法。原因么，简单呗。比如说，银行卡密码还是 8，那么加密就是 8 x 9 = 72，解密就是 72 / 9 = 8，这里的 9 就是对称密钥。
这种办法的缺点很明显，在双方进行加密通信之前，必须得先商量好一个对称密钥。并且一旦这个对称密钥丢了，那么所有数据都不安全了。像大宝这样隔着一条河，大声地告诉对方“喂～密钥是 9！你除以 9 就行了！”，无异于直接把密码告诉守在一旁的骇客。
大宝也不笨。9 作为对称密钥，不也是串儿数据么，反正也不长，用刚才想用的“非对称加密算法”，加密了再喊过去就是了呗，问题解决。
但是，这单单一个 9 实在是太好猜了，骇客只须认得九九表，就能一个一个地试出来。相比于用成百上千年才能破解的“非对称密钥”，数到九九八十一简直就是一眨眼的功夫。
不过要么怎么说“魔高一尺，道高一丈”呢，大宝有的是锦囊妙计。他把密码、银行名、卡号、持卡人姓名拼在一起，再随机分成一小份儿一小份儿的，然后用不同的对称密钥，分别加密。这样就增加了破解的难度，即使骇客破解出其中的一部分，也无法得到足够的信息去盗取钱财。而实际中，还有更多的锦囊来保证信息的安全。
于是，我们就看到大宝为了买到他的宫爆鸡丁，开始了 0 和 1 的传输。他先随便定下了一个对称密钥，然后用“致富宝”证书的公钥对其加密并传给对方；等对方解密出同一个对称密钥之后，大宝开始用对称算法加密传输数据；过了 1 分钟，暂停传输，重新定一个新的对称密钥，重复上述过程，直至数据全部传输完成。顺便说一句，这种为了安全和效率的综合考虑，混合使用对称算法和非对称算法的方法，叫做“数字信封”机制，像

HTTPS

、

SSH

/SFTP，以及选择使用

SSL/TLS

的

IRC

、

IMAP

等协议，都是采用类似的这种机制实现的。
密码正确，确认付款，大宝终于吃到了他的宫爆鸡丁，故事也到此告一段落了。但是现实生活中，如果您在网上交易的时候，应该怎么做，才能保证数据的安全呢？
首先，您可以仔细观察浏览器的地址栏，如果是像“https://fantix.org”这样以 https 打头的地址，那么您可以相信，至少这个地址采用了上述公钥办法做验证，并且所有数据都是加密传输的；否则如果是像“http://fantix.org”这样的 http（没有 s）打头的，就完全没有公钥私钥这一说，更没有身份验证的机制（只是说传输协议上没有保证，不代表不通过其他方法进行加密或验证），并且，发送未加密的数据就如同在互联网上“喊”一样，相当危险。



（我的网站已经加密，但貌似我的证书不是那么可信……）
其次，一般浏览器像

FireFox

，都会自动验证服务器证书的真伪，比如域名是否相符，是否在有效期内等。并且一般浏览器内嵌了很多公信机构 CA 的证书（公钥），您不需要自己跑到工商局去，浏览器会搞定的。一旦发现有冒名顶替者，必然会弹出大字儿，提醒您不要上了钓鱼网站的当。（广告！FireFox 还可以辨识钓鱼网站，如您不慎勿入其中，则 FireFox 将用醒目的红字儿来警示您。）
在 FireFox 3 中，如果您浏览的页面被公信机构验证是货真价实的，证书合法有效，那么地址栏中“https”前面应该是

绿色的

，点击它可以看到经营者信息；如果数据仅仅是加密过，不会被第三方窃听到的话，“https”前面的图标背景是蓝色的（如上图）；而对于普通的“http”协议，背景是没有特殊警示颜色的，比如在我的

Ubuntu

中，它是灰扑扑的。
补充说明，我们只谈了公钥安全机制，但并不是说绿色的标志就一定安全——比如说一些木马就是最大的威胁。所以，如果您使用木马和病毒比较多的操作系统——比如说 Microsoft Windows 的话（尤其是怕

黑屏

，没有及时更新的盗版系统），我还是建议您，不要因为 FireFox 3 的绿色标志，就把杀毒软件、杀木马软件卸载掉。
这就是公钥安全机制与宫爆鸡丁的故事了，更流行的叫法是

PKI

（Public-key Infrastructure, 公钥基础设施），包括一沓子算法、协议，还有一整套公信机构 CA（Certificate Authority，身份认证机构）的官僚体系。没准过不了多久，我们就会人手一份个人电子证书，连身份证都免了。
版本历史：
2009.4.14 – 修改了靠后面，前后不一致的一点点。添加图片、链接。排版。
2009.4.13 – 整理细节。
2009.4.7 – 替换了说理的那段，整理了一下逻辑，完善了论据。
2009.4.3 – 用真正的例子，替换掉了原来一个很白痴的例子。其他有微小改动。
2009.4.2 – 初稿完成。