热搜:
 
当前位置: 首页 » 资讯 » 正文

【比特币之父】加密野史:从山本五十六到中本聪

放大字体  缩小字体 发布日期:2018-06-22  来源:比特币之父  作者:比特币之父  浏览次数:4
核心提示:【比特币之父】加密野史:从山本五十六到中本聪
   【比特币之父】加密野史:从山本五十六到中本聪

  偷袭珍珠港得手后,山本五十六决定偷袭中途岛。

  他派出四条先锋航母,航母指挥官们踮起脚尖,举起望远镜,争相脑补美军措手不及的画面时,美军轰炸机突然从云里穿出,遮住了天。

  日军措手不及,几百架战机还没来得及飞、就被闷死在甲板上。

  十分钟内,先锋航母全部喷火,王牌飞行员们直到被烤焦也没想到,美国人早就截获了他们的偷袭情报。

  是谁走漏了风声?

  一、对称加密的软肋

  日军通讯密码以复杂出名,由一万个五位数组成,而且,太平洋战争期间升级12次,看似牢不可破,却难挡百密一疏。

  这都怪美军击沉过一艘日本潜艇,从船舱里捞出来一份密码本,上面记满密语,美军由此洞穿日军80%的密电,并且得知:山本五十六正计划偷袭AF,但AF究竟在哪里?

  美军翻到珍珠港被袭前夜的电报,山本五十六要求日本战机从马绍尔群岛出发,注意避开AF的空中侦察。

  从地图上看,AF只能是中途岛。

  为证实猜想,中途岛美军用明文假报淡水设备故障,日军截获情报,扭头告诉主力部队:带上淡水净化器,因为AF淡水匮乏。美军截获消息,确认AF就是中途岛。

  最终,山本五十六的全部机密像X光片一样,摊在罗斯福总统的办公桌上,美国未战先胜。

  物理战场的赢家,无一不是信息战场的胜者。就在同时,英国破译出德军的密码,加速了二战的结束。

  二战时期的国家,真正的家当不是飞机、不是航母,而应该是密码本。当守护机密的重担全压在密码本上时,却没有东西能守护密码本本身,这是对称加密的软肋。

  可二战之后就少有密码被破的事迹,特别是80年代美苏冷战期间,两国都使出奶劲破译对方密电,最后却都竹篮打水。

  为什么会这样?这要从非对称加密的鼻祖RSA算法说起。

  二、什么是RSA算法?

  1977年,Rivest、Shamir和Adleman三位教授用名字的首字母命名一种新算法:RSA,可它居然不需要密码本,这在当时就像吃饭不需要碗筷刀叉。

  为什么会那样清新脱俗?关键在于RSA把密码本拆分成公钥和私钥:公钥公开,用来加密;私钥私藏,用来解密。

  RSA的原理很简单,但要先回忆三个初中数学小概念:质数、互质和取模。

  质数:只能被它本身和1整除的自然数。比如:2、3、5、7、11、13、17……即:我们没法把一个质数拆成两个自然数之积。

  互质:公约数只有1的两个正整数,比如:5和72互质。

  取模:即除法中的余数,运算符是mod,比如7 ÷ 3 = 2余1,所以,7 mod 3 = 1。

  RSA用四步设定密钥(公钥和私钥):

  1、找两个质数P和Q,P和Q相乘得到Max,即 Max = P × Q

  2、把两个质数分别减1,相乘得到M,即 M = (P-1) × (Q-1)

  3、找一个正整数E,使E与M互质,且 E<M

  4、找一个正整数D,使D × E 除以M余1,即(D × E) mod M = 1

  E是公钥,加密就是让原文自乘(E-1)次,得到密文。

  D是私钥,解密就是让密文自乘(D-1)次,得到原文。

  我们挑两个质数:P=7, Q=13

  Max = P × Q = 91

  M = (P-1) × (Q-1) = 72

  随机选公钥E=5,因为5与72互质,且5小于72

  找到私钥D=29,因为5 × 29 ÷ 72 余 1

  如果,你想把字符C传给你朋友,怎么加密才能抵抗破解?

  字符C在ASCII码中对应的数字是67,加密原理很简单:

  把原文67自乘4次(E-1次),注意:当自乘结果超过Max(Max = 91)时,需将结果取模后再乘。

  活体演示:

  原文67自乘第1次:

  67 × 67 = 4489 > 91

  所以,4489 mod 91 = 30

  把上一步的结果30拿过来,自乘第2次:

  30 × 67 = 2010 > 91

  所以,2010 mod 91 = 8

  自乘第3次:

  8 × 67 = 536 > 91

  所以,536 mod 91 = 81

  自乘第4次:

  81 × 67 = 5427 > 91

  所以,5427 mod 91 = 58

  自乘4次之后,加密结束,得到密文58。查ASCII码表,58对应” : “,把“ : ”发出去,即使被截获,也不会泄露信息,因为对方没有私钥,解不了密。

  那么,掌握私钥的人如何解密?

  很简单,类似于加密,解密是用密文58自乘28次(D-1次),但每次相乘结果超过Max时,需取模后再乘:

  密文58自乘第1次:

  58 × 58 = 3364 > 91

  所以,3364 mod 91 = 88

  把上一步结果88拿过来,自乘第2次:

  88 × 58 = 5104 > 91

  所以,5104 mod 91 = 8

  照葫芦画瓢,第3次:

  8 × 58 = 464 > 91

  所以,464 mod 91 = 9

  第4次:

  9 × 58 = 522 > 91

  所以,522 mod 91 = 67

  第5次:

  67 × 58 = 3886 > 91

  所以,3886 mod 91 = 64

  第6次:

  64 × 58 = 3712 > 91

  所以,3712 mod 91 = 72

  第7次:

  72 × 58 = 4176 > 91

  所以, 4176 mod 91 = 81

  第8次:

  81 × 58 = 4698 > 91

  所以, 4698 mod 91 = 57

  第9次:

  57 × 58 = 3306 > 91

  所以, 3306 mod 91 = 30

  第10次:

  30 × 58 = 1740 > 91

  所以,1740 mod 91 = 11

  第11次:

  11 × 58 =638 > 91

  所以, 638 mod 91 = 1

  第12次:

  1 × 58 = 58 < 91

  58 < 91,所以不用取模,直接把58拖下来乘

  第13次 :

  58 × 58 =3364 > 91

  所以, 3364 mod 91 = 88

  我们发现,从第13次开始重复第1次结果:

  第14次:8

  第15次:9

  第16次:67

  第17次:64

  第18次:72

  第19次:81

  第20次:57

  第21次:30

  第22次:11

  第23次:1

  第24次:58

  第25次:88

  第26次:8

  第27次:9

  第28次:67

  解密完成,67就是原文。

  我们发现,解密过程出现两道轮回,实际只有12种可能,而且存在密文与原文相同的情形(第12次),那是因为我们用的是小质数:7和13,现实中的质数稍微大一点:

  P =

  3388495837466721394368393204672181522815830368604993048084925840555281177

  Q =

  11658823406671259903148376558383270818131012258146392600439520994131344334162924536139

  Max = P × Q =

  39505874583265144526419767800614481996020776460304936454139376051579355626529450683609727842468219535093544305870490251995655335710209799226484977949442955603

  选用大质数后,解密过程出现的可能性将超千亿,概率上不支持破解者发现规律。

  另一方面,破解密文的唯一方式是破解密钥,而Max和公钥是公开信息,于是,破解私钥唯一的方法是从Max中分解出P和Q。

  已知P和Q计算乘积,普通电脑一瞬间就能算出Max,可如果想把Max拆成P和Q,那就应了一句古话:没有耕坏的地,只有累死的牛。

  我国最拉风的超级计算机神威·太湖之光,装备4万个处理器,占地足足一栋别墅,拆分1个200位数字,至少要等1000年。往前推1000年,那是北宋时期,我国历史上最善于解密的包青天年方十八。

  所以,与其说是在大海捞针,不如说是在太阳系中排查一颗原子,撞上大运的概率比原子还小。

  正算容易倒推难,这在密码学上称为陷门函数(Trapdoor Function),是非对称加密安全性的根基。陷门函数像是出站口的旋转门:出门容易,但想进来,那只有把门拱坏一条路。

  RSA是古典和现代加密技术的分水岭,它的诞生堪称历史性突破,但和其他突破一样,随着历史一路颠簸,RSA身上悬挂的缺陷也开始叮当作响。

  比如:

  有些算法已能拆分特定的大数,所以为求安全,人们会用更大的质数,但这样,密钥长度会被拉长,最终拖慢加解密速度。

  用户陷入两难:拉长密钥吧不便捷,不拉长密钥不安全。总得有种更出彩的算法,才能让人有盼头。

  于是,地平线上又升起一种新算法:椭圆曲线加密。

  三、什么是椭圆曲线加密?

  椭圆曲线加密(Elliptic Curve Cryptography )即ECC,1985年由Koblitz和Miller两位教授发明,被公认为最强的通用加密法。

  和RSA一样,ECC也是非对称加密:公钥加密,私钥解密。但两者生成公钥和私钥的机制不同,ECC比RSA更安全、更便捷。

  为什么?我们从一个方程说起:

  y² = x³ + ax + b(a和b是常数)

  即使没在教科书里见过,你也完全不必害怕,只要画出来,你就会发现这不过是只插在竹签上的章鱼。

  图1 椭圆曲线

  章鱼的轮廓就是椭圆曲线,它的身体沿x轴对称,而且,任何竹签直插上去和章鱼轮廓最多有三个交点。

  如果你去查资料,你会发现ECC的公式天罗地网,任何一个公式都会缠住你,但你马上就会知道,即使ECC看起来艰涩,但本质上不过是一局桌球游戏,只是桌球的弹射规律有点奇怪。

  我们在椭圆曲线上任选一点A开球。

  1、球打向B,弹往另一交点,再折向交点与x轴的对称点C;

  2、到C后会弹向A,途经曲线交点时,球会折向交点的对称点D;

  3、到D后会沿AD方向,射向曲线与直线的另一交点,接着弹到交点的对称点E;

  图2 椭圆曲线(动图)

  动图描绘的是3次撞击过程,桌球叮叮咚咚撞n次后,停在终点。

  如果你知道起点坐标和撞击次数n,就能算出终点坐标。可是,这时有人跑进来,他知道起点和终点坐标,如果你问他,撞击次数n是多少?他会和球一样愣在原地,因为真的没法算。

  撞击次数n就是你的私钥,一个你选的超大整数;桌球撞击n次停下,而终点坐标相当于公钥;如果你想再做一个公钥,那么改变起点坐标即可。

  椭圆曲线方程、起点和终点坐标完全公开,但计算球撞了几次才停下来却没有捷径、只能一次次试,这项事业比RSA中拆分Max的任务还要艰巨,都能把量子计算机们累出血,这就是为什么说ECC比RSA更安全的原因。

  同样面对228位长度的密钥,如果破解RSA需要烧开一勺水的能量,那么破解ECC所需要的能量,足以烧开地球上所有的水。

  ——德国数学家 Lenstra

  ECC早已无处不在:我们的第二代身份证都基于ECC,美国政府部门也用ECC加密内部通信,开源浏览器Foxfire、谷歌的Chrome、苹果的iMessage服务都使用ECC。

  除此之外,匿名网络Tor用ECC保护使用者隐私。中本聪曾经穿梭在各大论坛,但他的身份至今是谜,全靠Tor网络底层的ECC。

  而中本聪的业余小发明——比特币,也使用ECC的数字签名算法ECDSA(Elliptic Curve Digital Signature Algorithm),不单安全性能好,而且ECDSA签起名来要比RSA签名快两个数量级。准确地说,256位的私钥用ECDSA要比2048位的RSA签名算法快20倍,是四轮车和三轮车的差别。

  尽管花好稻好,可ECC也非完美无缺。

  ECC需要一些随机数,而随机数的产生有赖于生成器里的“种子”,曾有人爆料:美国国家安全局(NSA)曾经对随机数生成器动过手脚,让破解难度大幅降低,这样就便于特工破译采用ECC加密的数据。

  爆料者的名字叫斯诺登,他是美国棱镜门事件的主角。

  根据曝光材料,NSA开发出一条伪随机数曲线secp256r1。可幸运的是,中本聪并没有选择NSA的伪随机数曲线secp256r1,而是使用了另一条非伪随机数曲线secp256k1,带着比特币躲过密码学历史上的一支暗箭,否则只要暴露过公钥的人都有一定概率被NSA内部人士猜出私钥。

  结语

  中本聪被公认为非对称加密年代冲刷出来的天才,而山本五十六却被定格在对称加密时代,一份密码本让它丢的不仅是四艘航母,还有自己的命。

  1943年4月18日,美国空军稳稳击落山本五十六的座机,解密文件显示,美军破译出日军JN25密码本,提前获知机密行程,让他成为对称加密时期最高级别的祭品。

  和对称加密相比,非对称加密可以把秘密写在明信片上,消灭了密码本被破解的问题,但加密技术进化之路并非坦途,因为密码攻防问题始终存在。

  所以,并不存在绝对安全的加密方法,如果有种算法可以让我们安全享用50年,就已经足够,至于进化中的问题,就让进化本身来修补。

  本文于2018年6月16日发布于微信公众号:概念地图 gainianditu

  发文时比特币价格 ¥43320.17

转自:www.wgdsb.com

 
关键词: 比特币之父
 
[ 资讯搜索 ]  [ 加入收藏 ]  [ 告诉好友 ]  [ 打印本文 ]  [ 违规举报 ]  [ 关闭窗口 ]

 

 
推荐图文
推荐资讯
点击排行
 
网站首页 | 关于我们 | 股票配资 | 使用协议 | 版权隐私