炉匠：科普一下网络绑票背后的技术（一）

2015-1-28 05:53 AM| 发布者: 星光| 查看: 779| 评论: 37|原作者: 炉匠

摘要: Normal 0 false false false EN-US JA X-NONE ...

过圣诞过年乱哄哄，好久没写科普了。好容易等到一个不用打牌的周末，写点什么呢？据说写科普的最高境界是写自己不懂的科学。咱就向这个高度靠拢一下吧。

一个恐怖故事

那天 (01/24/1015) 听到美国国家公共电台（NPR）里讲的一个恐怖故事：一个人的计算机中了病毒，把他所有的文件，电邮，照片都被病毒加了密，完全没法读了。勒索者说你可以交勒索费（Ransomware) 把它们赎回来。由于计算机加密后是目前技术不可解的，受害者只好乖乖交钱，赎回一个密码，解开了他所有文件。NPR的这个节目［1］做的不错，为了加深听众印象，他们专门找了一个受害者当场电话叩应：这是一个中招的警察局，里面的一个警察用局里的机器看网，不知点了个什么中了毒。立刻把警局所有文件锁住了，里面包括15年来所有办案文件，案件照片，口供等等。这些重要文件肯定是有备份的，可是备份机也同时被感染了，所以把所有备份都同样加了密。警局抓狂了，找来FBI，然后FBI说这个加密和米国国安局水平是一样的，没解。您还是认栽，按找勒索者的要求付赎票费吧。你们的文件比原则更重要，等等等等。于是老革命遇上新问题，警察蜀黍硬着头皮上网学买网币（bitcoin)，然后乖乖交钱，拿回所有文件。

好，我很感兴趣了。这种勒索背后究竟是什么技术呢？为啥能一个穷小子做案后，倾国王的千军万马，全部经费解不开呢？这道理实际很简单，就是正运算容易，逆运算难。比如算术里的正运算乘法，其逆运算是除法。乘法有口诀，但是除法就没有。小学老师教我们做除法的时候用“试商”就是先假想一个答案，然后用乘法验证其是否对。这样用两个数通过乘法算出一个结果，要把结果通过逆运算还原成那两个数，就要花费更多的时间。如果需要世界最强的计算机花费一万年才能解开，那就算理论上肯定能解开，实际上却行不通，基本就勒索成功了。

逆运算为什么这样难

那么什么逆运算这么难呢？就是咱小学学过的质因数分解，是乘法的逆运算。质因数分解就是一个数分解成几个相乘的质数，比如把 1457分解成 37 乘以 41。我们可以用一个计算器把两个质数很快地乘起来，比如把两个质数，1000000000193 和999999999673 相乘得到999999999865999999936889，这需要的时间可以忽略不计，但把999999999865999999936889，分解成上面两个质数，需要的时间就长多了。所以当两个质数都很大，比如都在几百位时，分解解质因数的计算时间就大到几百年甚至几万年，谁都不能容忍的地步了。这样如果用其中一个质数作为密码，别人虽然知道两数之积也没办法。

说到这份上，我就顺便科普一点信息加密和密码学吧。所谓加密就是把咱们说的大白话通过一个变换变成常人不懂的乱码，这样就可以通过公共的渠道传播信息，虽然谁都能收到你的乱码，但只有你和你的收信人能对乱码进行变换和反变换。

红灯记的故事

举个例子，如果你把wang_luo_bang_piao (网络绑票) 这个短语加密成不可解密的乱码，可以用一串随机数，如319981309075395484….，作为密码钥匙来加密。方法非常简单，就是字母串对准密钥字符串，然后根据密钥的数字对字母在字母表上进行位移。如第一个字母w 对密钥第一位3，移三位，w,x,y,z,变成z。第二位字母a对准密钥的第二位1，移一位变b。如此整个字母短语就变成了乱码 zbwphmxoibhsjiumis, 没有密码钥就不可分解的了。看到这您一定会说，既然加密这么简单，为什么你还要讲上面一大通什么质数啊，分解啊什么的，直接用随机数位移加密不就行了吗？可是这里还有个细节：您的随机数密钥必须要只给收信人，如果泄露给外人，你的密码就没秘密了。这个细节在样板戏里演过，就是红灯记里李玉和把密电码藏在粥底下的故事。这个密电码就是一本写着一串串随机数的书，发信者和收信者每封电报用一页。数学方法证明，只要随机数密电码不重复使用，这种加密手法是不可破解的。问题来了。战争中指挥部要和那么多战斗单位联系，如果用不重复的随机秘密本，实际操作有问题。一个折中的办法就是利用很长，很少重复的数字串来加密，密级低的通讯用重复较多的密钥，密级高的通讯用重复很少的密钥。可是这个问题带来的问题就是同一信息有可能出现在密级低和密级高的电报中。敌方从密级低的电报入手，破译后再攻密级高的。这种破译技术的一个传奇故事就是国军的密码破译家导致山本五十六的行程暴露，被美机埋伏击落。

密码机之迷

（待续，下面还有江青同志抹眼泪的八卦，看我有没有精神写了）

收藏分享邀请

上一篇：田农：2015 底特律国际汽车展下一篇：漫人：818灰机——寡妇制造机F-104（五）

发表评论

最新评论

引用 2015-2-1 02:45 PM: 炉匠: 我所知的重要错误是每次daily setting 的三个字母重复发一遍如EIN，发两遍成了如AZTKSG。这样就让人逐渐发现同样字母在转轮转后的表现。由于可以利用于破译的密 ...
这个是电影里面的错误。。实际中Alan肯定早就利用这个了。这个戏剧性情节太假了。他不会那么笨。

引用 2015-2-1 12:47 PM: waspking: 不管怎样，这个是最重要的Crib。我狗了一下，很多人批评这个错误了。
我所知的重要错误是每次daily setting 的三个字母重复发一遍如EIN，发两遍成了如AZTKSG。这样就让人逐渐发现同样字母在转轮转后的表现。由于可以利用于破译的密码电报非常多，就有大量的initial six letters.最后终于拼出所有组合。

引用 2015-2-1 11:55 AM: tieshu: 谢谢姥姥解释，很有帮助！
记得很多年前，有一个加密是多少位的什么限制，好像是一般人和公司只能用６４ｂｉｔ，　只有国家安全部门可以用１２８ｂｉｔ，好像就 ...
好像以前美国连一般的加密技术都不让老百姓用。记不得什么时候开始政策变了。

现在key size应该没有限制了。（我猜）

引用 2015-2-1 11:53 AM: tieshu: 查了一下维基，好像Ｇ和Ｎ都是公开的，但没说怎么公开。原则上说根据ｐｕｂｌｉｃ　ｋｅｙ的不同会有所变化？如果是这样，是不是ｅｍｂｅｄ在ｐｕｂｌｉｃ　ｋｅ ...
N 是个很大的质数。N 选好了，再选 G。G is 一个 modular N 系统下的根数。也就是说， G^x mod N (where x 在0和N之间）可以生成出所有的N以下的正整数。

N and G are two non-secrete numbers used be the system, everyone can see them. They are NOT public keys. A public key should belong to somebody. But N and G belong to the system.

引用 2015-2-1 11:27 AM: 炉匠: G是个公开的大数。
查了一下维基，好像Ｇ和Ｎ都是公开的，但没说怎么公开。原则上说根据ｐｕｂｌｉｃ　ｋｅｙ的不同会有所变化？如果是这样，是不是ｅｍｂｅｄ在ｐｕｂｌｉｃ　ｋｅｙ　里呢

引用 2015-1-31 11:10 PM: hanxin: 这个问题问的好。

可以把password分成两半。各半对应到相应的一个整数，比如用每个字符的ASCII码乘以字符的位置，再都加起来。反正对应到一个整数就行。

然后 ...
谢谢姥姥解释，很有帮助！
记得很多年前，有一个加密是多少位的什么限制，好像是一般人和公司只能用６４ｂｉｔ，　只有国家安全部门可以用１２８ｂｉｔ，好像就是和解密的时间有关的。不知道现在是否还有这样的限制。

引用 2015-1-31 11:06 PM: hanxin: a 是 Alice 的密码。收到 (G^b) mod N = X 之后，计算

(X^a) mod N

就是

(G^b)^a mod N

Bob也做同样的计算，用他的 b ，这样，他们两人就共享一个同样的密码 ...
N 是public key 吗？
这种纯数学的问题真是很神秘啊！最近看到一个关于圆周角是３６０度的解释，也是非常神奇！

引用 2015-1-31 09:18 PM: tieshu: 哇，这个解释得好棒！姥姥原来是加密专家。问题是密码是如何对应到两个区大的质数的呢？
这个问题问的好。

可以把password分成两半。各半对应到相应的一个整数，比如用每个字符的ASCII码乘以字符的位置，再都加起来。反正对应到一个整数就行。

然后从这个整数往下（或往上）找，总能找的一个质数（伪质数）。用伪质数这个词，是因为判断质数其实挺费时间的。但是，有高效的算法判断一个数是质数的概率是多少。我们可以定个下限，比如，90％。找个数，90％可能是质数。这个能很快找到。

其实，用质数乘积加密password的方法，我只在教课书上看到。也可能最早的unix系统用过（记不清了？）。现在，大家都用 sha1, sha256 等，更先进的算法。

引用 2015-1-31 08:48 PM: tieshu: 俺还有点糊涂，G是什么？Alice收到(G^b)MOD N，如何能算出(G^b)^a？
a 是 Alice 的密码。收到 (G^b) mod N = X 之后，计算

(X^a) mod N

就是

(G^b)^a mod N

Bob也做同样的计算，用他的 b ，这样，他们两人就共享一个同样的密码了。

引用 2015-1-31 04:03 PM: 炉匠: 因为每次 HEIL出来的不一样，有时是XDRZ，有时是PKLI 甚至XCXC。
不管怎样，这个是最重要的Crib。我狗了一下，很多人批评这个错误了。

引用 2015-1-31 03:50 PM: waspking: 炉匠害得我作为去看Turing的电影了。里面有个情节太假？如果德国佬每天6点都有一个信息，最后都是“害！希特勒”，那不就可以根据这个解码？怎么还需要顿 ...
因为每次 HEIL出来的不一样，有时是XDRZ，有时是PKLI 甚至XCXC。

引用 2015-1-31 03:45 PM: tieshu: 俺还有点糊涂，G是什么？Alice收到(G^b)MOD N，如何能算出(G^b)^a？
G是个公开的大数。

引用 2015-1-31 12:05 PM: 炉匠害得我作为去看Turing的电影了。里面有个情节太假？如果德国佬每天6点都有一个信息，最后都是“害！希特勒”，那不就可以根据这个解码？怎么还需要顿悟？

引用 2015-1-31 09:25 AM: 炉匠: 谢姥姥，终于明白了。刚才还糊涂。
俺还有点糊涂，G是什么？Alice收到(G^b)MOD N，如何能算出(G^b)^a？

引用 2015-1-31 09:16 AM: hanxin: 两人不需知道对方的private key。他们一个收到 (G^a) mod N，一个收到 ((G ^b) mod N。注意，他们看不到对方的那个指数。他们只需要接到数之后，再做一次次方的 ...
是这个关键

引用 2015-1-31 09:09 AM: hanxin: 炉匠，其实你讲了两种不同的加密类型。要注意把他们分开。

（1）用密码的加密方法
（2）不用密码的加密方法

（1）是我们通常在输送，存储文件时用的。我们用一 ...
哇，这个解释得好棒！姥姥原来是加密专家。问题是密码是如何对应到两个区大的质数的呢？

引用 2015-1-29 11:29 PM: hanxin: 两人不需知道对方的private key。他们一个收到 (G^a) mod N，一个收到 ((G ^b) mod N。注意，他们看不到对方的那个指数。他们只需要接到数之后，再做一次次方的 ...
谢姥姥，终于明白了。刚才还糊涂。

引用 2015-1-29 09:19 PM: G^a means G to power of a （G 的 a 次方）

mod N means 除N取余数

引用 2015-1-29 09:13 PM: 两人不需知道对方的private key。他们一个收到 (G^a) mod N，一个收到 ((G ^b) mod N。注意，他们看不到对方的那个指数。他们只需要接到数之后，再做一次次方的运算。求出的数就是 shared key 了。窃听者不知道 a, 也不知道 b, 所以无法求出 shared key.

引用 2015-1-29 09:04 PM: 炉匠: 太感谢了。实际上这篇文章只想介绍一下Diffie–Hellman–Merkle 系统的公开密码问题，避免红灯记里送密码本的麻烦。可是我自己也没完全懂，正好问你一下：假设Al ...
原来你是想讲 Diffie–Hellman。这个也很又意思。如果我没记错的话，这是用了如下原理：

((G^a) ^b) = ((G^b) ^a) mod N

如果只知道 ((G^a) ^b) mod N 和 a, 很难求出 b，同理
如果只知道 ((G^a) ^b) mod N 和 b, 很难求出 a.

这里， a and b are private keys for Alice and Bob. They will use
((G^a) ^b) mod N as their shared key.

窃听者只能看到 Alics 和 Bob 把 (G^a) mod N 和 (G^b) mod N 传送给对方。但仅有这两个数是求不出以下三个值的：
a,
b, and
((G^a) ^b) mod N

查看全部评论(37)

		自动登录	找回密码
密码			注册

炉匠：科普一下网络绑票背后的技术（一）

最新评论

相关分类