欢迎光临
我们一直在努力

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

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

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

(传说中的宫爆鸡丁。来源:

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 – 初稿完成。

赞(0) 打赏
未经允许不得转载:新席地网博客 » 公钥安全机制与宫爆鸡丁的故事
分享到: 更多 (0)
标签:

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  • Q Q(选填)

新席地网-苏州网站制作,360度全景摄影,微信小程序营销推广,抖音运营推广

QQ :13945502电话:17895058839

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

×
订阅图标按钮