火鸟财经

全国首家区块链官方媒体

剖析区块链财经数据,解读政策导向,把脉产业动态。

一文读懂密码学发展简史

2019-04-25 14:35:37    来源:火鸟财经    作者:高承实    点击:

区块链技术作为一种新型信任关系构建技术,采用了密码技术和网络空间安全技术的最新成果,尤其是身份认证和隐私保护、数字签名相关技术。高博士亲述密码学前世今生,可谓吊足了众人对密码学的探索欲。


微信图片_20190425142634.jpg



密码学发展简史


从历史角度看,密码学可以大致分为古典密码学和近现代密码学两个阶段。两者以现代信息技术的诞生为分界点,现在所讨论的密码学多是指后者,建立在信息论和数学成果基础之上。此外,随着量子计算和量子通信的研究,量子密码学(Quantum Cryptography)受到越来越多的关注,被认为会对已有的密码学安全机制产生较大的影响。


古典密码学


古典密码学源自数千年前。最早在公元前1900 年左右的古埃及,就出现过使用特殊字符和简单替换式密码来保护信息。美索不达米亚平原上曾出土一个公元前 1500 年左右的泥板,其上记录了加密描述的陶器上釉工艺配方。古希腊时期(公元前800 ﹣前146 年)还发明了通过物理手段来隐藏信息的“隐写术”,例如使用牛奶书写、用蜡覆盖文字等。后来在古罗马时期还出现了基于替换加密的凯撒密码,据称凯撒曾用此方法与其部下通信而得以命名。这些手段多数是采用简单的机械工具来保护秘密,在今天看来毫无疑问是十分简陋,很容易破解的。严格来看,可能都很难称为密码科学。


微信图片_20190425142718.jpg


近代密码学


近现代密码的研究源自第一、二次世界大战中对军事通信进行保护和破解的需求。1901 年 12 月,意大利工程师 Guglielmo Marconi(奎里亚摩•马可尼)成功完成了跨越大西洋的无线电通信实验,在全球范围内引发轰动,推动了无线电通信时代的带来。无线电极大提高了远程通信的能力,但存在着天然缺陷——它很难限制接收方,这意味着要想保护所传递信息的安全,必须采用可靠的加密技术。对无线电信息进行加密以及破解的过程直接促进了近现代密码学和计算机技术的出现。反过来,这些科技进步也影响了时代的发展。一战时期德国外交部长Arthur Zimmermann(阿瑟•齐默尔曼)拉拢墨西哥构成抗美军事同盟的电报(1917 年1月16日)被英国情报机构—40号办公室破译,直接导致了美国的参战;二战时期德国使用的恩尼格玛(Enigma)密码机(当时最先进的加密设备)被盟军成功破译(1939年到1941年),导致大西洋战役德国失败。据称,二战时期光英国从事密码学研究的人员就达到7000人,而他们的成果使二战结束的时间至少提前了一到两年时间。需要说明的是,恩尼格玛(Enigma)密码机也是密码学发展史上的一个标志性事件,对古典密码算法的应用到了相当高的水准。


微信图片_20190425142758.jpg


接下来,就是可以称为密码学发展史上的里程碑性事件了。1945年9月1日,Claude Elwood Shannon(克劳德•艾尔伍德•香农)完成了划时代的内部报告《A Mathematical Theory of Cryptography(密码术的一个数学理论)》,1949 年 10 月,该报告以《Communication Theory of Secrecy Systems(保密系统的通信理论)》为题在 Bell System Technical Journal(贝尔系统技术期刊)上正式发表。这篇论文首次将密码学和信息论联系到一起,为对称密码技术提供了数学基础。这也标志着近现代密码学的正式建立。这也是密码学发展史上的第一座里程碑性事件。


密码学发展史上的第二个里程碑性事件是DES的出现。DES全称为Data Encryption Standard,即数据加密标准,是一种使用密钥加密的分组密码算法,1977年被美国联邦政府的国家标准局确定为联邦资料处理标准(FIPS),并授权在非密级政府通信中使用,随后该算法在国际上广泛流传开来。


密码学发展史上的第三个里程碑性事件就是我们区块链中广泛应用的公钥密码,也就是非对称密码算法的出现。1976年11月,Whitfield Diffie 和 Martin E.Hellman 在 IEEE Transactions on Information Theory 上发表了论文《New Directions in Cryptography(密码学的新方向)》,探讨了无需传输密钥的保密通信和签名认证体系问题,正式开创了现代公钥密码学体系的研究。在公钥密码发现以前,如果需要保密通信,通信双方事先要对加解密的算法以及要使用的密钥进行事先协商,包括送鸡毛信,实际上是在传送密钥。但自从有了公钥密码,需要进行秘密通信的双方不再需要进行事前的密钥协商了。公钥密码在理论上是不保密的,在实际上是保密的。也就是说,公钥密码是可以破解的,但需要极长的时间,等到破解了,这个秘密也没有保密的必要了。


密码算法的评价指标,其中一个就是保密性,可分为理论上保密和事实上保密。理论上保密的密码算法只有一种,就是序列密码,一次一密。明文有多长,密钥就有多长,密文就有多长,密钥要具有完全的随机性。现代密码学的发展与电气技术特别计算机信息理论和技术关系密切,已经发展为包括随机数、Hash 函数、加解密、身份认证等多个课题的庞大领域,相关成果为现代信息系统特别互联网奠定了坚实的安全基础。


量子密码学


量子密码学(Quantum Cryptography)随着量子计算和量子通信的研究而被受到越来越多的关注,被认为会对已有的密码学安全机制产生较大的影响。量子计算的概念最早是物理学家费曼于1981年提出,基本原理是利用量子比特可以同时处于多个相干叠加态,理论上可以同时用少量量子比特来表达大量的信息,并同时进行处理,大大提高计算速度。量子计算目前在某些特定领域已经展现出超越经典计算的潜力。如基于量子计算的Shor算法(1994年提出),理论上可以实现远超经典计算速度的大数因子分解。


2016年3月,人类第一次以可扩展的方式,用Shor算法完成对数字15的质因数分解。这意味着目前广泛应用的非对称加密算法,包括基于大整数分解的RSA、基于椭圆曲线随机数的ECC等将来都将很容易被破解。当然,现代密码学体系并不会因为量子计算的出现而崩溃。一方面,量子计算设备离实际可用的通用计算机还有较大距离,密码学家可以探索更安全的密码算法。另一方面,很多安全机制尚未发现能加速破解的量子算法,包括数字签名(基于Hash)、格(Lattice)密码、基于编码的密码等。量子通信则可以提供对密钥进行安全协商的机制,有望实现无条件安全的“一次性密码”。量子通信基于量子纠缠效应,两个发生纠缠的量子可以进行远距离的实时状态同步。一旦信道被窃听,则通信双方会获知该情况,丢弃此次传输的泄露信息。该性质十分适合进行大量的密钥分发,如1984年提出的BB84协议,结合量子通道和公开信道,可以实现安全的密钥分发。


微信图片_20190425142830.jpg


密码技术分类


古典密码学技术主要可分为替换和置换两种,相对较为简单。现代密码学可以有多种分类方法,分组-序列是一种分类,对称-非对称也是一种。我们把这些分类技术组合在一起,按对称密码技术、非对称密码技术来阐述。


对称密码技术


对称加密算法,顾名思义,加密和解密过程的密钥是相同的。该类算法优点是加解密效率(速度快,空间占用小)和加密强度都很高。缺点是参与方需要提前持有密钥,一旦有人泄露则系统安全性被破坏。


对称密码从实现原理上可以分为两种:分组密码和序列密码。前者将明文切分为定长数据块作为基本加密单位,应用最为广泛。后者则每次只对一个字节或字符进行加密处理,且密码不断变化,只用在一些特定领域(如数字媒介的加密)。


分组对称加密代表算法包括DES、3DES、AES、IDEA 等。

•DES(Data Encryption Standard):经典的分组加密算法,最早是 1977 年美国联邦信息处理标准(FIPS)采用 FIPS-46-3,将 64 位明文加密为 64 位的密文。其密钥长度为 64 位(包括 8 位校验码),现在已经很容易被暴力破解。所谓暴力破解,就是对可能的密钥逐一进行测试。因为DES的有效密钥只有56位,因此它的密钥空间就是2的56次方大小。这个密钥空间在当前的计算能力下是很容易被破解的

•3DES:三重 DES 操作:加密 --> 解密 --> 加密,处理过程和加密强度优于 DES,但现在也被认为不够安全。DES就是刚才提到的美国军方1970年代发表的分组密码算法。3DES是在后来DES被强大的计算能力破解之后被设计出来的,它对DES的密码强度有所加强,但在安全性上仍然不是十分安全。

•AES(Advanced Encryption Standard):由美国国家标准研究所(NIST)采用,取代 DES 成为对称加密实现的标准,1997﹣2000年NIST从15个候选算法中评选 Rijndael算法(由比利时密码学家 Joan Daemon 和 Vincent Rijmen 发明)作为AES,标准为FIPS-197。AES也是分组算法,分组长度为128、192、256位三种。AES的优势在于处理速度快,整个过程可以数学化描述,目前尚未有有效的破解手段;

•IDEA(International Data Encryption Algorithm):1991 年由密码学家 James Massey 与华人密码学家来学嘉共同提出。设计类似于3DES,密钥长度增加到 128 位,具有更好的加密强度。


序列加密,又称流加密。1949年,Claude Elwood Shannon(信息论创始人)首次证明,要实现绝对安全的完善保密性(Perfect Secrecy),可以通过“一次性密码本”的对称加密处理。即通信双方每次使用跟明文等长的随机密钥串对明文进行加密处理。序列密码采用了类似的思想,每次通过伪随机数生成器来生成伪随机密钥串。代表算法包括 RC4 等。


总结下,对称加密算法适用于大量数据的加解密过程;不能用于签名场景;并且需要提前安全地分发密钥。


微信图片_20190425142917.jpg


非对称密码技术


非对称加密是现代密码学的伟大发明,它有效解决了对称加密需要安全分发密钥的问题。非对称加密中,加密密钥和解密密钥是不同的,分别被称为公钥(Public Key)和私钥(Private Key)。私钥一般通过随机数算法生成,公钥可以根据私钥生成。其中,公钥一般是公开的,他人可获取的;私钥则是个人持有并且要严密保护,不能被他人获取。


非对称加密算法优点是公私钥分开,无需安全通道来分发密钥。缺点是处理速度(特别是生成密钥和解密过程)往往比较慢,一般比对称加解密算法慢2﹣3 个数量级;同时加密强度也往往不如对称加密。非对称加密算法的安全性往往基于数学问题,包括大数质因子分解、离散对数、椭圆曲线等经典数学难题。代表算法包括:RSA、ElGamal、椭圆曲线(Elliptic Curve Crytosystems,ECC)、SM2 等系列算法。


•RSA:经典的公钥算法,1978 年由 Ron Rivest、Adi Shamir、Leonard Adleman 共同提出,三人于 2002 年因此获得图灵奖。算法利用了对大数进行质因子分解困难的特性,但目前还没有数学证明两者难度等价,或许存在未知算法可以绕过大数分解而进行解密。

•ElGamal:由 Taher ElGamal设计,利用了模运算下求离散对数困难的特性,比 RSA 产生密钥更快。被应用在 PGP 等安全工具中。

•椭圆曲线算法(Elliptic Curve Cryptography,ECC):应用最广也是强度最早的系列算法,基于对椭圆曲线上特定点进行特殊乘法逆运算(求离散对数)难以计算的特性。最早在 1985 年由 Neal Koblitz 和 Victor Miller 分别独立提出。ECC 系列算法具有多种国际标准(包括 ANSI X9.63、NIST FIPS 186-2、IEEE 1363-2000、ISO/IEC 14888-3 等),一般被认为具备较高的安全性,但加解密过程比较费时。其中,密码学家 Daniel J.Bernstein 于 2006 年提出的 Curve25519/Ed25519/X25519 等算法(分别解决加密、签名和密钥交换),由于其设计完全公开、性能突出等特点,近些年引起了广泛关注和应用。

•SM2(ShangMi 2):中国国家商用密码系列算法标准,由中国密码管理局于 2010 年 12 月 17 日发布,同样基于椭圆曲线算法,一般认为其安全强度优于 RSA 系列算法。


非对称加密算法适用于签名场景或密钥协商过程,但不适于大量数据的加解密。除了SM2 之外,大部分算法的签名速度要比验签速度慢(1﹣2个数量级)。RSA 类算法被认为已经很难抵御现代计算设备的破解,一般推荐商用场景下密钥至少为 2048 位。如果采用安全强度更高的椭圆曲线算法,256 位密钥即可满足绝大部分安全需求。


微信图片_20190425142946.jpg



消息认证码


消息认证码通过对消息的摘要进行加密,可以防止消息被篡改和认证身份。消息认证码利用对称加密加密算法,对消息完整性进行保护。其基本过程为对某个消息,利用提前共享的对称密钥和散列算法进行处理,得到消息认证码值(HMAC)。该 HMAC 值持有方可以向对方证明自己拥有某个对称密钥,并且确保所传输消息内容未被篡改。


典型的HMAC 生成算法包括 K,H,M 三个参数。

K 为提前共享的对称密钥,H 为提前商定的 Hash 算法(如 SHA-256),M 为要传输的消息内容。三个参数缺失了任何一个,都无法得到正确的 HMAC 值。


消息认证码可以用于简单证明身份的场景。如Alice、Bob 提前共享了 K 和 H。Alice 需要知晓对方是否为 Bob,可发送一段消息 M 给 Bob。Bob 收到 M 后计算其 HMAC 值并返回给 Alice,Alice 检验收到 HMAC 值的正确性可以验证对方是否真是 Bob。


消息认证码的主要问题是需要提前共享密钥,并且当密钥可能被多方同时拥有(甚至泄露)的场景下,无法追踪消息的真实来源。如果采用非对称加密算法,则能有效的解决这个问题,即数字签名。


    点击加载更多

    推荐作家