聊一聊密码学

搬砖俱乐部

发布于 2019-06-15 17:35:23

1.7K0

发布于 2019-06-15 17:35:23

文章被收录于专栏：BanzClubBanzClub

古代的加密和解密

在古代，战争双方的将军，都会通过传信兵，来调遣各支队伍。假如，A国派出的传信兵，被B国俘虏了，那A国的作战计划将会被B国获取，这样，B做针对性战略，将会直接导致战争结果的倾斜。那需要怎么解决这个问题呢？

其实智慧的古人们，早就想到要通过对传递书信进行加密的处理，以避免上面情况的发生。如：中国古代的兵书《太公兵法》中的阴符和阴书，阴符就是不同长度的阴符，代表不同情况：长一尺，表示大获全胜；长八寸，表示守城敌人已投降等等。阴书是将书信分成三个部分，分给三个传信兵，只有三个部分放到一起才能完整的懂得书信的意思。古代西方军队之间也使用保密的通信方式，古罗马大帝凯撒发明了凯撒密码，就是将所有字母安装字母表的顺序循环移位得到新的字母。只有知道字母位移的规则，才能正确的知道书信的内容。这种“字母表替换”的加密方法，一直应用到二战期间，只不过规则越来越复杂。

凯撒密码位移盘

古代为了解决信息通信的安全性，发明了信息的加密方法，在中世纪，密码学已经在军事、国事、外交、宗教大量的使用了，所以破解加密信息，也逐渐有了持续研究的土壤，由此发展成为了密码分析学。阿拉伯学者肯迪，发明了《解码手册》，主要的思想是通过统计密文中出现频率最高的字母\符合，用一份同样语言的明文中出现频率最高的依次替换，从而破解密文。频率分析方法适用于西方的文字类型，当然，这种方法只能破解通过简单的替换规则加密的密文。

密码大战

无线电报的发明使人类的进入了电子通信的时代，而无线电通信属于广播式通信，任何人都能接收到电报信号，所以，电文的加密解密将变得尤为重要。密码学起源于战争，也是在战争中发展起来的，而且发展的尤为迅速。在第一次世界大战和第二次世界大战中，各个国家都成立了专门的密码机构，密码专家之间互相斗法。

在第一次世界大战时，英国成立了“Room 40”，负责破解德国的电报信号。最著名的就是破解了“齐默尔曼电报”，促使美国的参战，从而导致了德国的失败。一战时，破译工作很多是人工方式，到了二战时，无论是在密码学的技术、理论还是应用方面，在此期间都发生了革命性的变化。

齐默尔曼电报密文和破译明文

从密码学的技术方面来看，基于机械和电气原理的加密解密装置全面取代了手工密码，不仅大大提高了加密解密的速度，也使密码的复杂度大大提高。

从密码学的理论方面来看，大量的数学和统计学知识被应用于密码分析和破解。于是，大量的数学家不断加入密码队伍，逐渐取代了语言学专家、猜谜高手，并成为密码战场的主力军。

从密码学的应用方面来看，参战各国都已经认识到密码决定着战争胜负的关键，于是，各国都开始研制和采用最先进的密码设备，建立最严密的密码安全体系。

当时德国的电气工程师发明了著名的恩尼格玛密码机，是当时最先进的商用密码设备，德国军队基于恩尼格玛密码机（Enigma），进行了军用改造，并且很快在德国军队中使用，成为当时德军最重要的通信加密工具。

为了破解“Enigma”，各个国家都付出了很大的心血。波兰最先破译了德国的“Enigma”，并发明了回转机、穿孔纸和“炸弹”机，并且将技术和设备都交给了英法两国。德军不断升级加密方式，也使后续的破译工作越来越难，随着波兰和法国相继战败，最后破解“Enigma”的重任就落在了英国人的肩上。

在第二次世界大战时英国最神秘的地方——布雷契莱庄园，负责截听和破译国外无线通信的情报机构，正式名称叫“政府密码学校”，前身就是“Room 40”，而对破解“Enigma”做出最大贡献的就是阿兰·图灵——现代计算机科学的奠基人，负责改进波兰的炸弹机，提升了破译效率，并且升级了破解理论。当时的“炸弹”机很类似现在的超级计算机。

布雷契莱庄园人为反法西斯战争的胜利做出了巨大贡献，后来随着战争的胜利，布雷契莱庄园人被要求宣誓不泄露秘密，并且销毁所有设备和资料，很多卓越的数学家继续研究计算机理论，为计算机的发展做出了巨大贡献。“政府密码学校”战后也改名为“政府通信司令部”，直到多年以后，这部分历史才被世人所知，如果这些人的功劳，当时被人们知道的话，将会是巨大的轰动。

美国先后成立了自己的密码机构，美国黑室、美国陆军密码局和美国海军密码局。其中比较成功的一次破译工作是中途岛海战，当时日军偷袭了珍珠港后，美国海军密码局获取了大量日军关于“某地方”的电报，当时猜测就是美国在大平洋重要的军事基地中途岛，所以，美国率先埋伏在中途岛附近，终于，在中途岛一举击败了日本海军大将山本五十六率领的联合舰队，扭转了太平洋战区的战局，在这场战争中，破解日军情报是美国获胜的关键。

从某种程度上讲，两次世界大战就像两次各个国家之间的密码大战，谁能破解密码或者谁能掌握最先进的加密技术，谁就能主导战争的胜利，这就更加促使了密码学的发展，为现代密码学提供了大量的理论基础和实战经验。

现代密码学

在第二次世界大战结束后不久，计算机技术突飞猛进，在具有超强计算能力的计算机面前，机器时代的加密解密都显得不堪一击，而且在计算机通信网络普及的今天，各种文本、声音、图像、视频等信息都可以进行数字化，对信息时代通信安全又有了新的挑战。而新密码学的任务已经不只限于传统密码学的“保密通信”，而是含义更广的“信息安全”，包括“保密通信”、“数据加密”、“数字签名”等。并且不仅局限于军事、外交、政治，开始全面进入经济、商业、科学、教育等各个领域，可以说现代密码学已经成为今天被广泛关注的信息安全的理论基础。

摘要加密

MD5、SHA等加密算法属于单向加密算法，具有不可逆性，非传统意义上的加密，只适用于数据的完整性校验。如：密码的密文存储。

对称加密

IBM以“数据加密标准”（Data Encryption Standard）名称公布了其数据加密研究团队开发出来的一种算法，即DES：

DES是一种对称加密算法，加密和解密使用同一个秘钥，步骤如下：

DES是基于组块的加密算法：

1、将明文分割成大小为二进制64位的组块，一般不足64位的需要进行补位；

2、对每个组块进行初始变换位置（Initial permutation IP）得到新64位的组块T0，进行左右分割，得到L0和R0；

3、对T0进行16次迭代运算，设第i次迭代得到的结果为Ti（LiRi）；

4、对第16次迭代结果T16进行最后一次变换位置（IP的逆运算），就得到了加密组块。

其实，整个加密过程最重要的就是迭代运算，即费斯泰尔运算：

1、首先将R，通过扩展运算E，变为48位文本；

2、把上面的结果与秘钥的48位文本，进行异或运算，仍然得到48位文本；

3、把上面的文本分为8块，每块6位，分别输入8个S盒中进行替换运算，每个盒子里有4个比特的数字，4位将会替换6位的数字，然后输出8组4比特的数据，即32位数据；

4、经过S盒替换后，进行P盒置换。

DES的解密和加密过程一样，只是那16次迭代运算的顺序对调过来了。

由于DES的密钥长度比较短，后来很多团队通过“穷举法”，破解了DES加密，于是美国国家标准与技术研究院（NIST），要征集一个新的方案代替DES，即“高级加密标准”（Advanced Encryption Standard）—AES，AES包括AES128，AES192，AES256，其实指的就是秘钥长度，可以满足不同等级的安全需求。AES是通过分组和矩阵运算实现的，目前唯一可以成功攻击AES算法的是旁道攻击，说明AES具有很高的安全性。

非对称加密

一开始因特网只用于军事、科研和教育领域，但人们很早就意识到它的商业价值。如果身处异地的人们，无须直接见面，通过公共的计算机网络就可以进行保密通信，交换数据和资料等，甚至支付和转账。为了实现这个伟大的梦想，首先要解决一系列有关网络通信的安全问题。基于这个问题，迪菲和赫尔曼发表了论文，并提出了构建公钥密码系统，文章指出网络通信的两个关键：保密和认证，保密指通信的信息进行加密，收信方再解密获取原文；认证是指身份认证和内容认证，发送者是指定的发送者，不能冒名顶替，并且内容不会被篡改，即数字签名。

在公钥密码系统中，每位计算机网络的通信者都应该有两个密钥，一个是对外保密的“私钥”，另一个是对网络上所有人公开的“公钥”，公钥和私钥都可以进行加密，但私钥加密信息必须用对应的公钥解密，公钥加密的则用对应的私钥解密。

RSA加密算法的提出，令公钥密码系统得以真正的实现，是由作者姓名首字母命名的算法，目前成为了最常用的非对称加密算法。RSA算法的本质是分解两个大素数的积（100到200位十进制数或者更大），计算两个数的积容易，但是分解两个素数的积是公认的数学难题。

基于RSA算法的思想，数学家又提出来ECC（椭圆曲线加密法—Elliptic Curve Cryptography）算法，ECC算法是基于离散对数问题，虽然ECC相比于RSA计算更复杂，但从数学角度来看，他们属于同一安全等级的加密算法。

未来密码学

机器密码时代，我国由于国情原因落后欧美国家一大截，不过在电子计算机时代，我国慢慢缩小了差距，而在未来的量子计算时代，我国也始终处于第一梯队，那么量子计算有哪些特点，会淘汰电子计算时代的密码技术吗？

很遗憾看了很多资料，还是没有理解量子具体什么意思（可能思维被宏观世界固化，确实水平有限），只能大概的理解量子状态不是传统理解的0或者1，可以即是0又是1，这是量子态的“状态叠加”；另外还有“量子纠缠”，量子纠缠是一种不需要介质或者传播的超距作用，是微观世界的现象，处于纠缠态的量子将被视为一个整体。

而伟大的科学家们，已经发明出来了量子计算机。量子计算机能够实现电子计算机所做不到的并行算法，并且有实验表明，量子计算机可以很轻易的破解RSA和ECC算法，所以在可以控制更多量子的时候，传统的加密方法将变得一击即破。所以，为了对抗未来的量子计算机，人们发明了适用于未来的加密方法—“量子密码”，当身处异地的两个人使用量子密码通信时，任何人都无法监听，因为一旦监听就会干扰密码的量子状态而被通信双方察觉。随着量子科技的发展，肯定会有新的安全方式，适用于量子科技时代，我们将一直站在巨人的肩膀上前进。