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

你有没有在网上买过东西?没?什么?哦,怕不安全。

现在信息科技日新月异,貌似一转眼的功夫,交电话费、考试报名、逛图书馆、订购午饭都搬上了互联网。方不方便且不说,单说足不出户能叫到午饭,这要在以前那可都是科幻小说啊。只不过科幻小说里,主人公可能只须对机器人吩咐说,“来份宫爆鸡丁盖饭,外加一碗紫菜鸡蛋汤”,一切就搞定了——哪像现在这样,装五花八门的杀毒软件,还得随时小心钓鱼网站的陷阱。那现在的互联网真的如此危险么?先看看大宝的这次订餐经历,您再下结论也不迟。

话说大宝一日宅在家中,百无聊赖地度过了阴雨连绵的上午,忽然感觉腹中空虚,四肢无力——他明白了,原来自己是饿了。闲话少说,大宝奔到电脑前,准备给自己淘一顿午饭。

飘过了几家附近的餐馆之后,大宝决定在“啃的鸡”点一份宫爆鸡丁盖饭套餐。点完菜,服务员小姐礼貌地将大宝带到了收银台——这“啃的鸡”是先付帐、再上菜的。

dcmmcm3k_94ghmzw5ds_b

(传说中的宫爆鸡丁。来源: 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)。用数学点儿的话写下来,就是:

  1. 随机地选择两个非常大的素数 p 和 q,比如 2 和 5;
  2. 密钥对的公共部分就是 N = pq,就是例子中 N = 2 x 5 = 10;
  3. 算出一个中间数 M = (p – 1)(q – 1),比如 M = (2 – 1) x (5 – 1) = 1 x 4 = 4;
  4. 选择一个小于 M,且与 M 互质的数 e,比如 e = 3;
  5. 根据 d x e mod M = 1 算出 d,比如 d = 7 因为 7 x 3 mod 4 = 1;
  6. 烧掉所有写着 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),把加了密的密码给解出来了。

dcmmcm3k_9584tzs8fb_b

(二战德国所使用的的洛伦兹密码机。图片来源: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的一条私人讯息。她可以用以下的方式来产生一个公钥和一个密钥

  1. 随意选择两个大的素数pqp不等于q,计算N=pq
  2. 根据欧拉函数,不大于N且与N互质的整数个数为(p-1)(q-1)
  3. 选择一个整数e与(p-1)(q-1)互质,并且e小于(p-1)(q-1)
  4. 用以下这个公式计算dd× e ≡ 1 (mod (p-1)(q-1))
  5. pq的记录销毁。

e是公钥,d是私钥。d是秘密的,而N是公众都知道的。Alice将她的公钥传给Bob,而将她的私钥藏起来。

加密消息

假设Bob想给Alice送一个消息m,他知道Alice产生的Ne。他使用起先与Alice约好的格式将m转换为一个小于N的整数n,比如他可以将每一个字转换为这个字的Unicode码,然后将这些数字连在一起组成一个数字。假如他的信息非常长的话,他可以将这个信息分为几段,然后将每一段转换为n。用下面这个公式他可以将n加密为c

EXTERN_0000

计算c并不复杂。Bob算出c后就可以将它传递给Alice。

解密消息

Alice得到Bob的消息c后就可以利用她的密钥d来解码。她可以用以下这个公式来将c转换为n

EXTERN_0001

得到n后,她可以将原来的信息m重新复原。

解码的原理是

EXTERN_0002

以及ed ≡ 1 (mod p-1)和ed ≡ 1 (mod q-1)。费马小定理证明

EXTERN_0003     和     EXTERN_0004

这说明(因为pq不同的素数)

EXTERN_0005

==========哦快乐的分割线==========

好了,回到我们饥肠辘辘的大宝的故事来吧。

“我现在验证一段话,如果你能解出来,就算这营业执照是你的吧。”大宝说着掏出一张白纸,背着摊主在纸上胡乱写下几个字——“戈壁滩上打酱油”。

大宝从证书中取出钥匙——也就是公钥了,再在纸上这么一比划,“戈壁滩上打酱油”几个字儿顿时被加密成 0101110…(篇幅所限,此处略去上千个 0、1)…1010101。

“给你,试试吧。”

“我说是我的就是我的,”摊主从怀里摸出一把旧钥匙(私钥,当然要藏好了),又在纸上一比划,“那还能错的了了!”

0 和 1 渐渐隐去,“戈壁滩上打酱油”几个字儿又冒了出来——解密验证成功,大宝无言以对,只得承认证书里的公钥的确是摊主本人的,除非摊主从真所有者那里抢的私钥。

“好吧,就算这证书是你的吧。那你凭什么说,你就是证书上写的,”大宝撇了一眼营业执照,“什么致富宝什么的?”

大宝说的没错,每个人都可以伪造证书,就算这公钥确实属于他又能何如。

“这买卖真难做!我不干了!”摊主这回真的急了。

“你不干了,我还要吃饭呢!”大宝也急了,二话不说把摊主拉到了工商局——颁发营业执照的公信机构。(可见,吃饭对大宝来说是多么重要)

到了工商局,办事员业务非常熟悉。

“证书真伪辨别是么,请出示证书。”

办事员拿着手持式扫描仪一扫,证书复印件就叮叮当当地出现在一旁的打印机中。只见他操起一把大剪刀,对着复印件“咔嚓”就是一刀,将证书拷贝一份为二。要不说他业务熟悉么,这一刀不偏不倚,刚刚好把前面提到过的电子签名部分剪了下来。

要说这电子签名是啥,还得先说这证书是怎么签发的。

dcmmcm3k_96dt2tk7dp_b

(证书是怎样炼成的——最右边 OK 的那个。图片来源:OpenClipart.org,GFDL)

当初“致富宝”开道创业的时候,写过一份营业执照申请函,内容就是现在这剪下的两半中,比较大的那一半——电子签名是小半。工商局在评审了申请函之后,准予营业,于是签署了这一份证书,而证书中的电子签名正是官方签署的证据。

这到底还是公钥和私钥的讨论。话说工商局自己也有一对儿密钥,专门用来签署营业执照。当申请函得到批准的时候,办事员用工商局专用私钥在申请函上一比划,这申请函就被“加密”成了一段电子签名,也可以说,工商局在申请函上签名批准了。请注意,这申请函里到底包含什么呢?正如前面提到过,基本信息是必须有的,另外一个很重要的部分就是申请者——或者叫摊主——的公钥。毕竟公钥也是一种数据嘛,当作申请函数据的一部分来加密了。别弄浑了哦,办事员用工商局的私钥,加密了包含有摊主公钥的申请函,制作成了摊主证书的电子签名部分。这工商局的私钥可是公信机构独有的,平常要锁在很大的保险柜里的,所以签署出来的证书才是真的。

那我们就看看下一步,办事员怎么来辨别真伪吧。

“这是我们工商局的公钥,大家可以免费索取的。”办事员从柜台里搬出一箱子钥匙,说。

“那照这么说,有了这个,”大宝捡起一枚钥匙说,“我自己也能辨别真伪咯。”

“没错。”办事员也拿起一枚钥匙,在电子签名那一半上一比划,龙飞凤舞的电子签名乎的一下,变成了一份申请函的模样。

“哎哟,好像不对哦。”办事员拿过剪下的大半,跟刚解密出来的申请函一比,“这哪是致富宝啊,明明写的是致富堡嘛。”

大宝四下一看,那山寨摊主早溜之大吉了。真是虚惊一场,好歹大宝没有把钱给了那钓鱼的山寨摊主。

理论上,假的电子签名是不可能解密成跟原文仅一字之差的——实际上是什么都解不出来的,只有真的签名才能解出原文来。另外为了减小数据量和其它考虑,原文在签名之前,做过摘要处理。故事中做了一些简化,特此声明。另外,虽然说两种密钥都可以加解密,但专业地来说,公钥是用来做加密和验证的,私钥是用来做解密和签名的。

如果您拥有一份“个人电子证书”,那么您也可以用您的私钥签署数据——比如发电子邮件,那么收到信的人都可以用您证书中的公钥进行验证,以确认信件肯定是您亲笔签署的;反之,如果您的朋友有一份电子证书,那么您就可以很放心地用公钥加密一些只有您朋友可以阅读的数据,然后安全地通过您不信任的传播媒体——比如互联网——传递到您朋友的手中。电子签名在一定程度上,还保证了数据的完整性和不可抵赖性。

dcmmcm3k_99f2psk5dt_b

(一封给大宝的签名信,计算机可以验证其中的 PGP 签名)

后面发生的事情,就是大宝跟他验过真身的“致富宝”隔着一条河交易的过程了。没错,我是说隔着一条河——这个城市似乎忘记修桥了,大宝只能扯着嗓子喊,把他的银行卡密码告诉“致富宝”才行。现在互联网啊,真是危机四伏,你说那个路由节点上没趴着三五成群的嗅探器的(夸张手法,请保留意见)。要是大宝真个把密码喊出来,那没等他吃完饭,卡里的钱就全没了。所以咧,大宝就跟“致富宝”商量了一个办法。

这个办法当然就是加密咯。大宝想用对方的公钥加密自己的密码,然后“喊”过去,对方解密出来就搞定了。但问题是,大宝的数学实在是太差了,要算乘方的话,手指头根本不够他掰的。况且,要加密的也不仅仅只是 6 位密码,还有像“中国农业银行青岛市分行麦岛支行”这样的银行名,还有很长的银行卡号,更是还有大宝的大名——大卫/阿基米德/宝兰德/罗纳尔迪尼柯夫斯基。要让他把这些都加密算出来,非把他饿死不可,非对称加密算法并不适合于大批量的数据加密。所以,大宝想出了另一个办法——对称加密算法

说白了,就是用同一个,也是唯一一个密钥做加密解密的算法。原因么,简单呗。比如说,银行卡密码还是 8,那么加密就是 8 x 9 = 72,解密就是 72 / 9 = 8,这里的 9 就是对称密钥。

这种办法的缺点很明显,在双方进行加密通信之前,必须得先商量好一个对称密钥。并且一旦这个对称密钥丢了,那么所有数据都不安全了。像大宝这样隔着一条河,大声地告诉对方“喂~密钥是 9!你除以 9 就行了!”,无异于直接把密码告诉守在一旁的骇客。

大宝也不笨。9 作为对称密钥,不也是串儿数据么,反正也不长,用刚才想用的“非对称加密算法”,加密了再喊过去就是了呗,问题解决。

但是,这单单一个 9 实在是太好猜了,骇客只须认得九九表,就能一个一个地试出来。相比于用成百上千年才能破解的“非对称密钥”,数到九九八十一简直就是一眨眼的功夫。

不过要么怎么说“魔高一尺,道高一丈”呢,大宝有的是锦囊妙计。他把密码、银行名、卡号、持卡人姓名拼在一起,再随机分成一小份儿一小份儿的,然后用不同的对称密钥,分别加密。这样就增加了破解的难度,即使骇客破解出其中的一部分,也无法得到足够的信息去盗取钱财。而实际中,还有更多的锦囊来保证信息的安全。

于是,我们就看到大宝为了买到他的宫爆鸡丁,开始了 0 和 1 的传输。他先随便定下了一个对称密钥,然后用“致富宝”证书的公钥对其加密并传给对方;等对方解密出同一个对称密钥之后,大宝开始用对称算法加密传输数据;过了 1 分钟,暂停传输,重新定一个新的对称密钥,重复上述过程,直至数据全部传输完成。顺便说一句,这种为了安全和效率的综合考虑,混合使用对称算法和非对称算法的方法,叫做“数字信封”机制,像 HTTPSSSH/SFTP,以及选择使用SSL/TLS 的 IRCIMAP 等协议,都是采用类似的这种机制实现的。

密码正确,确认付款,大宝终于吃到了他的宫爆鸡丁,故事也到此告一段落了。但是现实生活中,如果您在网上交易的时候,应该怎么做,才能保证数据的安全呢?

首先,您可以仔细观察浏览器的地址栏,如果是像“https://fantix.org”这样以 https 打头的地址,那么您可以相信,至少这个地址采用了上述公钥办法做验证,并且所有数据都是加密传输的;否则如果是像“http://fantix.org”这样的 http(没有 s)打头的,就完全没有公钥私钥这一说,更没有身份验证的机制(只是说传输协议上没有保证,不代表不通过其他方法进行加密或验证),并且,发送未加密的数据就如同在互联网上“喊”一样,相当危险。

dcmmcm3k_98hjvpp6hc_b

(我的网站已经加密,但貌似我的证书不是那么可信……)

其次,一般浏览器像 FireFox,都会自动验证服务器证书的真伪,比如域名是否相符,是否在有效期内等。并且一般浏览器内嵌了很多公信机构 CA 的证书(公钥),您不需要自己跑到工商局去,浏览器会搞定的。一旦发现有冒名顶替者,必然会弹出大字儿,提醒您不要上了钓鱼网站的当。(广告!FireFox 还可以辨识钓鱼网站,如您不慎勿入其中,则 FireFox 将用醒目的红字儿来警示您。)

在 FireFox 3 中,如果您浏览的页面被公信机构验证是货真价实的,证书合法有效,那么地址栏中“https”前面应该是绿色的,点击它可以看到经营者信息;如果数据仅仅是加密过,不会被第三方窃听到的话,“https”前面的图标背景是蓝色的(如上图);而对于普通的“http”协议,背景是没有特殊警示颜色的,比如在我的 Ubuntu 中,它是灰扑扑的。

补充说明,我们只谈了公钥安全机制,但并不是说绿色的标志就一定安全——比如说一些木马就是最大的威胁。所以,如果您使用木马和病毒比较多的操作系统——比如说 Microsoft Windows 的话(尤其是怕黑屏,没有及时更新的盗版系统),我还是建议您,不要因为 FireFox 3 的绿色标志,就把杀毒软件、杀木马软件卸载掉。

这就是公钥安全机制与宫爆鸡丁的故事了,更流行的叫法是 PKI(Public-key Infrastructure, 公钥基础设施),包括一沓子算法、协议,还有一整套公信机构 CA(Certificate Authority,身份认证机构)的官僚体系。没准过不了多久,我们就会人手一份个人电子证书,连身份证都免了。

原文地址: http://songshuhui.net/archives/12755

发表评论

电子邮件地址不会被公开。 必填项已用*标注