分组密码

维基百科,自由的百科全书
跳转至: 导航搜索

密码学中,分组加密Block cipher,又称分块加密),是一种对称密钥算法。它将明文分成多个等长的模块(block),使用确定的算法和对称密钥对每组分别加密解密。分组加密是极其重要的加密协议组成,其中典型的如DESAES作为美国政府核定的标准加密算法,应用领域从电子邮件加密到银行交易转帐,非常广泛。

现代分组加密建立在迭代的思想上产生密文。其思想由克劳德·香农在他1949年的重要论文《保密系统的通信理论》(Communication Theory of Secrecy Systems)中提出,作为一种通过简单操作如替代和排列等以有效改善保密性的方法。[1] 迭代产生的密文在每一轮加密中使用不同的子密钥,而子密钥生成自原始密钥。

DES加密在1977年由前美国国家标准局(今“美国国家标准与技术研究所”)颁布,是现代分组加密设计的基础思想。它同样也影响了密码分析的学术进展。

简述[编辑]

分组加密包含两个成对的算法:加密算法E和解密算法D,两者互为反函数。每个算法有两个输入:长度为n的组,和长度为k位的密钥;两组输入均生成n位输出。将两个算法看作函数,K表示长度为k的密钥(密钥长度),P表示长度为n的分组,P也被表示为明文C表示密文,则满足:

E_K(P) = C \; ; \quad E_K^{-1}(C)=P
E_K(P) := E(K,P): \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^n,

对于任意密钥KEK(P)是输入的组的一个置换函数,且不可逆地落在{0,1}n区间。E的反函数(解密算法)定义为:

E_K^{-1}(C) := D_K(C) = D(K,C): \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^n,

例如,一个分组加密算法使用一段 128 位的分组作为明文,相应输出 128 位的密文;而其转换则受加密算法中第二个输入的控制,也就是密钥k。解密算法类似,使用 128 位的密文和对应的密钥,得到原 128 位的明文。

  • 每一个密钥实际上是选择了n位输入排列的(2^n)!种组合中的一种[2]

大多数的分组密码在在加密算法中会重复使用某一函数进行多轮运算,典型的轮数在4-32次之间,每一轮的函数R使用不同的子密钥Ki,由原密钥生成,作为输入:

M_i = R_{K_i}(M_{i-1})

其中M_0是最初的明文,M_i是第i轮加密后的密文。

历史[编辑]

Lucifer一般被认为是第一个现代分组密码,由IBM在1970年代基于霍斯特·費斯妥(Horst Feistel)的工作完成。它的一个修改版本是数据加密标准,被美国政府纳入联邦资料处理标准,并于1976年正式发布,至今仍被广泛应用。

当时设计DES密码的最初目的是为了抵抗某些美国国家安全局NSA)和IBM知道的密码分析方法,直到1980年代末期,这种被称为差分分析的方法才被毕汉姆(Eli Biham)和萨莫尔(Adi Shamir)独立重新发现[3]线性分析是另一种方法,NSA松井充发布这种实验性的密码分析方法[4]之前还并不知道。DES作为早期的分组密码,最早成为密码标准,引领了很多密码学和密码分析的研究。另一种分组密码标准高级加密标准(AES)被美国国家标准与技术研究院(NIST)采纳,即将逐渐取代DES目前的位置。

优缺点[编辑]

设计原则[编辑]

扩散(diffusion)和扰乱(confusion)是影响密码安全的主要因素[5]。扩散的目的是让明文中的单个数字影响密文中的多个数字,从而使明文的统计特征在密文中消失,相当于明文的统计结构被扩散[6]。例如,最简单的方法让明文中的一个数字影响密文中的k个数字,可以用:

c_n = \sum^k_{i=1}m_{n+i}

扰乱是指让密钥与密文的统计信息之间的关系变得复杂,从而增加通过统计方法进行攻击的难度。扰乱可以通过各种代换算法实现。

设计安全的分组加密算法,需要考虑对现有密码分析方法的抵抗,如差分分析、线性分析等,还需要考虑密码安全强度的稳定性。此外,用软件实现的分组加密要保证每个组的长度适合软件编程(如8、16、32……),尽量避免位置换操作,以及使用加法、乘法、移位等处理器提供的标准指令;从硬件实现的角度,加密和解密要在同一个器件上都可以实现,即加密解密硬件实现的相似性[7]

参见[编辑]

参考资料[编辑]

  1. ^ Shannon, Claude. Communication Theory of Secrecy Systems. Bell System Technical Journal. 1949年, 28 (4): 656–715. 
  2. ^ Matt Bishop. Introduction to Computer Security First Edition. Addison-Wesley Professional. 2004年. ISBN 0321247442 (英文). 
  3. ^ Eli Biham and Adi Shamir. Differential cryptanalysis of DES-like cryptosystems. Journal of Cryptology. 1991年, 4 (1). doi:10.1007/BF00630563 (英文). 
  4. ^ Mitsuru Matsui. The First Experimental Cryptanalysis of the Data Encryption Standard, CRYPTO. 1994. doi:10.1007/3-540-48658-5_1. 
  5. ^ C.E. Shannon. Communication theory of secrecy systems.. Bell System Technology Journal. 1949年, 28: 656-715 (英文). 
  6. ^ 黄皓. 分组加密的原理. 《计算机系统信息安全》课程讲义. 南京大学. 2010年9月28日 [2011-07-29] (中文). 
  7. ^ 冯登国,吴文玲,张文涛. 《分组密码的设计与分析》 第二版. 清华大学出版社. 2009年年. ISBN 9787302204602 (中文).