常见的加密算法可以分成三类,对称加密算法,非对称加密算法和密码杂凑函数(Hash函数)。上述算法的安全性都依赖于计算安全性。但随着量子计算机的诞生与性能的不断提高,为抵抗量子计算的后量子时代密码被提上议程,越来越得到研究者们的重视。
密码学发展简史:
古典密码算法的核心基础是替换与移位,安全性也主要是依靠不公开算法来保证的。1883年,密码学家Kerckhoff在其《军事密码学》中提出了著名的“Kerckhoff准则”,即密码算法的安全性应完全只依赖于密钥的安全,算法则可以是公开的。对于商用密码系统而言,公开密码算法的优点包括:有利于对密码算法的安全性进行公开测试评估;防止密码算法设计者在算法中隐藏后门;易于实现密码算法的标准化;有利于使用密码算法产品的规模化生产,实现低成本和高性能等。
1949年香农发表《保密系统的通信理论》,正式标志着现代密码学的诞生,也标志着加密算法的重心向应用数学上的转移。他提出了两种隐蔽明密文之间关系的技术:混乱和扩散,对应于代换和置换两大现代密码设计准则,并开创了用信息理论研究密码的新途径。文中所提出的破译密码的计算量理论与计算机理论中的计算复杂性理论相结合,已成为评价密码安全性的一个重要准则。
1976年Diffie和Hellman发表了《密码学的新方向》,首次证明了发送端和接收端无密钥传输的保密通信是可能的,提出了著名的D-H密钥交换协议,从而开创了公钥密码学的新纪元。随后,分组密码算法DES(Data Encryption Standard)于1997年发布。1978年,Rivest、Shamir和Adleman提出了RSA公钥密码体制。1990年,Rivest提出了MD4密码杂凑函数。1993年,美国国家标准与技术研究院(NIST)陆续发布了SHA系列杂凑函数。20世纪90年代,随着计算机处理能力的增强与差分密码分析和线性密码分析等密码分析技术的提出,DES的安全性受到了极大地威胁。因此, NIST又于1997年发起了高级加密标准AES的征集。
我们当前评估密码安全性的方法通常是计算安全性,即使用目前最好的方法攻破它所需要的计算远远超出攻击者的计算资源水平,则可以定义这个密码体制是安全的。而量子计算机的出现对如今广泛基于计算安全的公钥密码体制造成了极大的威胁。因此,NIST在2016年12月发布了后量子密码算法征集公告,并于今年2月公布了26种进入半决赛的密码算法,包括公钥加密和密钥建立、以及数字签名算法。
一、对称加密算法
1.1 对称加密算法概要
对称加密算法指加密和解密使用相同密钥,或从一个密钥很容易推导出另一个密钥的加密算法。对称加密算法的优点在于加解密的高速度和使用长密钥时的难破解性。假设企业内用户有n个,两两之间采用不同的对称密钥进行通信,则整个企业共需要
至少
个密钥,密钥的生成和分发都将成为企业的恶梦。对称加密算法的安全性取决于加密密钥的保存情况,但要求企业中每一个持有密钥的人都保守秘密是不可能的,他们通常会有意无意的把密钥泄漏出去——如果一个用户使用的密钥被入侵者所获得,入侵者便可以读取该用户密钥加密的所有文档,如果整个企业共用一个加密密钥,那整个企业文档的保密性便无从谈起。
图1对称密码算法模型
1.2 常见的对称加密算法
对称密码算法主要分为序列密码算法与分组密码算法两大类。
1.2.1 序列密码算法
序列密码也成流密码,是用密钥产生一个密钥流
,然后利用此密钥流依次对明文
进行加密,这样产生的密码就是序列密码,也称流密码。
序列密码的保密性完全取决于密钥的随机性。如果密钥是真正的随机数,则这种体制在理论上就是不可破译的。但这种方式所需的密钥量大得惊人,在实际上是不可行的。目前一般采用伪随机序列来代替随机序列作为密钥序列,也就是序列存在着一定的循环周期。这样序列周期的长短就成为保密性的关键。如果周期足够长,就会有比较好的保密性。
序列密码具有实现简单、便于硬件实施、加解密处理速度快、没有或只有有限的错误传播等特点,因此在实际应用中,特别是专用或机密机构中保持着优势,典型的应用领域包括无线通信、外交通信。但每次只能对一个数据位进行加密和解密的序列密码并不适用于软件实现。
常见的伪随机数发生器有线性反馈移位寄存器(Linear Feedback Shift Register, LFSR)、非线性反馈移位寄存器(Nonlinear Feedback Shift Register, NFSR)、二次剩余发生器(Blum and Shub Register, BBS Blum)等。
常见的真随机数发生器一般使用物理方法,将具有随机性质的物理过程转换为随机数,如粒子放射源、放射性衰变、电子设备的热噪音等。
常见的序列密码算法有:A5-1序列密码算法(用于蜂窝式移动电话系统语音和数字加密)、RC4密码算法、欧洲eSTREAM项目评选的Salsa20/12(软件实现)以及Grain v1、Trivium(硬件实现)等。
图2线性反馈移位寄存器模型
我国商用密码标准序列密码算法为ZUC,即祖冲之算法,是移动通信3GPP机密性算法EEA3和完整性孙发EIA3的核心,也是我国自主设计的第一个成为国际密码标准的密码算法。ZUC算法是一个同步流密码算法,逻辑上分为三层:素数域
上的线性反馈移位寄存器、比特重组层(BR)与非线性函数。
1.2.2 分组密码算法
与序列密码算法按位(bit)加密不同,分组密码(block cipher)的数学模型是将明文消息编码表示后的数字(简称明文数字)序列,划分成长度为n的组(可看成长度为n的矢量),每组分别在密钥的控制下变换成等长的输出数字(简称密文数字)序列。分组密码易于软硬件实现且不需要同步,因此在现代密码产品和分组交换网络中有着广泛的应用。按照算法结构的不同,分组密码可以分为三类:Feistel结构、SPN结构和Lai-Massey结构。
Feistel结构的优势在于加解密方式相同、节省资源;但缺点是扩散速度低,为达到一定的安全性通常需要迭代更多的轮数。代表算法有DES算法、ISO/IEC国际标准算法Camellia、密码学家布鲁斯·施奈尔(Bruce Schneier)设计的开源算法Blowfish、日本NTT公司的DES算法在软件应用方面的后补FEAL算法、以及我国的商业分组密码标准SM4等。
SPN结构相较于Feistel结构具有更好的扩散性;但加解密不对称造成了一定程度的实现资源浪费。代表算法包括AES、Serpent、韩国加密标准ARIA、三维分组密码算法3D等。
Lai-Massey结构可以提供与Feistel结构相仿的安全性,且轮函数同样可以采用不可逆的变换。但由于轮函数相对复杂,算法安全性难于分析,在密码设计方面的应用没有前面两种广泛。
表1常见分组密码算法
我国商用密码标准中主要分组密码算法有SM1 、SM4与SM7三种。其中SM1分组长度与密钥长度均为128bit,算法安全保密强度及相关软硬件实现性能与AES相当。该算法不公开,仅以IP核的形式存在于芯片中。
SM4分组密码算法用于无线局域网产品,分组长度与密钥长度也都为128bit,加密算法和密钥扩展算法都采用32轮非线性迭代结构,是一个Feistel型的分组密码算法。
SM7算法分组长度与密钥长度均为128bit,算法不公开,适用于非接触式IC卡应用,包括身份识别类(门禁卡、工作证、参赛证)、票务类(大型赛事门票、展会门票)与支付通卡类(积分卡、一卡通)等。
二、非对称加密算法
非对称加密算法是指加密和解密使用不同密钥的加密算法,也称为公私钥加密。公钥与私钥是一对,如果用公钥对数据进行加密,只有用对应的私钥才能解密。
假设两个用户要加密交换数据,双方交换公钥,使用时一方用对方的公钥加密,另一方即可用自己的私钥解密。如果企业中有n个用户,企业需要生成n对密钥,并分发n个公钥。由于公钥是可以公开的,用户只要保管好自己的私钥即可,因此加密密钥的分发将变得十分简单。同时,由于每个用户的私钥是唯一的,其他用户除了可以可以通过信息发送者的公钥来验证信息的来源是否真实,还可以确保发送者无法否认曾发送过该信息。非对称加密虽然较好地解决了密钥分发与保管的问题,同时具有较高的算法复杂性。但其缺点是加解密速度要远远慢于对称加密,在某些极端情况下,甚至能比非对称加密慢上1000倍。
常见的非对称加密算法有基于大整数因子分解难题的RSA算法、椭圆曲线密码算法ECC、背包算法、Diffie-Hellman、ElGamal算法等。
图3公钥密码算法加解密模型
我国的商用密码标准算法中非对称密码算法包括基于椭圆曲线的SM2密码算法与基于对的标识密码算法。SM2在我国商用密码体系中被用来替换RSA算法,它与RSA相比复杂度更高、处理速度更快、机器性能消耗更小。
表2 SM2与RSA对比
SM9算法与SM2相似,包括数字签名算法、密钥交换协议和密钥封装机制。其使用了椭圆曲线上对这一个工具,不同于传统意义。
三、杂凑函数
杂凑函数也称散列函数、Hash算法,是一种单向算法,用户可以通过Hash算法对任意长度的目标信息生成一段特定长度的唯一的Hash值,却不能通过这个Hash值反推得目标信息。结果Hash值通常被称为摘要。因此Hash算法常用于安全加密、唯一标识、数据校验、分布式系统、不可还原的密码存储以及信息完整性校验等。
图4杂凑函数
杂凑函数主要分为两大类:MD系列与SHA系列。MD系列算法主要包括MD4、MD5、HAVAL等,SHA系列主要包括SHA-0、SHA-1、SHA-256与SHA-512。SHA算法建立在MD4算法的迭代基础之上,其基本框架与MD4类似。
表3常见杂凑函数
在很长的一段时间内,MD5和SHA-1一直是广泛使用的杂凑函数。2004年,我国学者王小云等人利用差分分析找到了MD5算法的碰撞并给出了第一个实例。2005年,研究人员发现了SHA-1算法的理论破解方法。为应对杂凑函数危机,NIST在2007年向全世界公开征集SHA-3杂凑函数的设计方法,并于2012年宣布获胜算法Keccak为下一代标准。
Keccak算法采取了海绵结构,与之前的SHA系列算法完全不同。该算法不仅可用于计算散列值,还可以用于伪随机数生成器、序列密码、认证加密、消息认证码等。
值得一提的是,区块链技术中主要用到的密码技术就是杂凑函数与非对称加密算法。前者被用于构建区块以及确认交易的完整性,后者则用于交易中的转账操作。
我国商用密码标准中的杂凑算法为SM3,适用于商用密码应用中的数字签名和验证、消息认证码的生成与验证、随机数生成,可满足多种密码应用的安全需求。在SM2和SM9标准中使用。
图5区块链中的杂凑函数
图6交易转账
四、后量子加密算法
量子计算是一种遵循量子力学规律调控量子信息单元进行计算的新型计算模式。从可计算的问题来看,量子计算机只能解决传统计算机所能解决的问题,但是从计算的效率上,由于量子力学叠加性的存在,目前某些已知的量子算法在处理问题时速度要快于传统的通用计算机。
目前,存在一些复杂性问题还未找到对应的高效量子计算攻击方法,基于这类问题设计的密码算法就叫做后量子密码算法。主要包括基于格(格上向量、最近向量困难问题)的密码算法、基于纠错码(随机编码的译码困难问题)的密码算法和基于多变量(多变量二次方程求解困难问题)的密码算法、基于Hash的签名算法、基于椭圆曲线(超奇异椭圆曲线上的同源问题)的密码算法等。
图7后量子密码时代
在NIST公布的进入第二轮评估的26个后量子密码算法中,我国提交的LAC顺利入选,是我国自主设计的密码算法在国际密码算法标准化进程中迈出的有力一步。
领取专属 10元无门槛券
私享最新 技术干货