现代密码技术

现代密码技术DES、RSA《计算机网络安全》Chapter33.1数据加密标准DES19世纪70年代，DES(theDataEncryptionStandard)最初由IBM公司提出。DES是一种分组密码，它采用56比特长的密钥将64比特的数据加密成64比特的密文。DES完全公开了加密、解密算法。因而是一个最引人注目的分组密码系统。它一直是国际上商用保密通信和计算机通信的最常用加密算法。特别是应用于保护金融数据的安全（例如：ATM取款机）。3.1数据加密标准DESDES的发展1977年正式颁布为数据加密标准（DES-DataEncryptionStandard）。1979年，美国银行协会批准使用DES。1980年，DES成为美国标准化协会(ANSI)标准。1984年，ISO开始在DES基础上制定数据加密的国际标准。美国国家安全局NSA每隔年对该算法进行评估，1994年，决定1998年12月之后不再使用DES。现已经确定了选用Rijndael算法作为高级加密算法AES。3.1数据加密标准DES分组密码就是一个明文分组被当作一个整体来产生一个等长（通常）的密文分组的密码，通常使用的是64或者128位分组大小。分组密码的实质是，设计一种算法，能在密钥控制下，把n比特明文简单而又迅速地置换成唯一n比特密文，并且这种变换是可逆的（解密）。现在使用的大多数对称分组加密算法都是基于Feistel分组密码结构的。3.1数据加密标准DES设计原则分组长度分组越长则安全性越高，但加/解密速度越低，分组长度为64位是一个合理的折衷。密钥长度密钥越长越安全，但加/解密速度越低，64位长的密钥已被证明是不安全的，128位是常用的长度迭代次数迭代越多越安全，通常为16次迭代子密钥产生算法越复杂则密码分析越困难轮函数越复杂则抗密码分析的能力越强分组密码的两个基本设计方法。（如何挫败基于统计方法的密码分析？Shannon建议了两种对付统计分析的方法：扩散和混淆)（1）扩散(diffusion)：扩散指使明文的统计特征消散在密文中，可以让每个明文数字尽可能地影响多个密文数字获得，等价于说每个密文数字被许多明文数字影响。一个扩散的例子就是当前明文字母开始的若干明文字母之和(mod26)作为对应的密文字母。在二进制分组密码中，对明文进行置换后再用某个函数作用，重复多次就可获得较好的扩散效果。因为原始明文中的不同位对密文某一位都会产生影响。3.1数据加密标准DES3.1数据加密标准DES（2）混淆(confusion)其目的在于使作用于明文的密钥和密文之间的关系复杂化，是明文和密文之间、密文和密钥之间的统计相关特性极小化，从而使统计分析攻击不能奏效。3.1数据加密标准DES•乘积密码（ProductCipher）就是以某种方式连续执行两个或多个简单密码（如替代、置换），以使得所得到的最后结果或乘积比其任意一个组成密码都更强的分组密码。Shannon提出交替使用混淆和扩散进行乘积密码。基于Shannon理论，Feistel建议交替地使用代换和置换。Feistel密码结构方法将输入分组分成左右两部分。以右半部数据和子密钥作为参数，对左半部数据实施代换操作。将两部分进行互换，完成置换操作。优点能够产生雪崩效应快速软件加解密易于分析可自行设计的内容：分组长度密钥长度轮数子密钥生成算法轮函数LEi=REi-1REi=LEi-1F(REi-1,Ki)FKiLiRiRoundiLi-1Ri-1Feistel每一轮的加密(替换+置换)3.1数据加密标准DES3.1数据加密标准DESDES加密操作DES在加解密过程中，将明文和密文分成64比特的分组进行操作。其一大特点是解密过程与加密过程是相似的。首先对64比特的明文分组进行IP置换。IP置换将输入分组的第58比特作为输出的第1比特，输入的第50比特作为输出的第2比特，依次类推。然后用密钥k对得到的结果进行迭代操作。最后再对迭代操作的结果进行IP-1置换产生输出分组。下面是DES算法的略图。48bitsubkey58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157408481656246432397471555236331386461454226230375451353216129364441252206028353431151195927342421050185826331419491757253.1数据加密标准DES（1）初始置换与逆置换IP：IP-1：例如：IP(675a69675e5a6b5a)=(ffb2194d004df6fb)加密：Li=Ri-1Ri=Li-1⊕f(Ri-1,ki)FKiLiRiRoundiLi-1Ri-1（2）Feistel每一轮的加密过程3.1数据加密标准DES解密：Ri–1=LiLi–1=Rif(Ri–1,Ki)＝Rif(Li,Ki)1)其中函数f的定义如下图所示：E是一种输入为32比特，输出为48比特的置换，具体的置换方法如下，其置换方法和IP类似。32123454567898910111213E：121314151617161718192021202122232425242526272829282930313212)E扩展(32-48)称s1,s2,…,s8为s盒，实现明文消息在密文消息空间中的随机非线性分布，可以抵抗差分分析攻击DC。s盒的运算规则为，输入的6比特数据的第一和第六比特为s和的行数，其余比特决定s盒的列数，例如，当s1的输入为011011时，其输出为0101。s114413121511831061259070157414213110612119538411481362111512973105015128249175113141006133)S盒子的设计(压缩置换)DES的核心部分8个S盒P为一个输入和输出都为32比特的置换，具体形式如下：1672021291228171152326P：5183110282414322739191330622114254)P置换第16比特→第1比特第07比特→第2比特…………第25比特→第32比特DES算法的密钥k由一个56位的密钥以及附加的8位奇偶校验位组成，经过密码扩展算法可以把它扩展为16个子密钥。其中迭代次数与左移的比特数关系如下：迭代次数12345678910111213141516左移位数11222222122222213.1数据加密标准DES5）轮密钥的产生56位28位28位56位28位28位56位56位574941332517915850423426181025951433527PC-1：19113605244366355473931231576254463830221466153453729211352820124141711241532815621102319124268PC-2：1672720132415231374755304051453348444939563453464250362932两个置换选择（舍弃了奇偶校验位，即第8，16，…，64位）（舍弃了第9,18,22,25,35,38,43,54比特位）总结：DES一轮迭代的过程DES解密操作由迭代操作的定义，显然可以得到Ri-1=LiLi-1=Ri⊕f(Li,ki)若记加密算法每一轮的操作为Ti，我们可以方便的得出解密算法：DES-1=IP-1∘T1∘T2∘…T15∘T16∘IP3.1数据加密标准DESDES的雪崩效应雪崩效应AvalancheEffect明文或密钥的一比特的变化，引起密文许多比特的改变。如果变化太小，就可能找到一种方法减小有待搜索的明文和密文空间的大小。如果用同样密钥加密只差一比特的两个明文：0000000000000000......000000001000000000000000......000000003次循环以后密文有21个比特不同，16次循环后有34个比特不同如果用只差一比特的两个密钥加密同样明文：3次循环以后密文有14个比特不同，16次循环后有35个比特不同56位密钥长度问题56-bit密钥有256=72,057,584,037,927,936≈7.2亿亿之多强力搜索(bruteforcesearch)似乎很困难，20世纪70年代估计要1000－2000年技术进步使穷举搜索成为可能1997年1月29日，RSA公司发起破译RC4、RC5、MD2、MD5，以及DES的活动，破译DES奖励10000美金。结果仅搜索了24.6%的密钥空间便得到结果，耗时96天。1998年在一台专用机上(EFF)只要三天时间即可1999年在超级计算机上只要22小时!3.1数据加密标准DESDES的强度S-box问题其设计标准没有公开，但是迄今没有发现S盒存在致命弱点计时攻击计时攻击利用的事实是加密或解密算法对于不同的输入所花的时间有细微的差别DES能够很好地抵抗计时攻击弱密钥(注意避免)弱密钥：8个弱密钥半弱密钥：2个半弱密钥3.1数据加密标准DESDES的强度DESCrackerTheElectronicFrontierFoundationbuilttheso-calledDESCrackersupercomputerin1998tocrack56-bitDESencryption.ItlaterwonRSALaboratory'sDESChallengeIIcontestinabout56hours.DESCrackerhad26(andlater27)systemboards,eachwith32or64customAWT-4500DeepCrackchips,foratotalofabout1,500to1,800chips.3.2非对称密码-RSA对称算法的缺陷为事先协商密钥，需另外的安全信道或KDC不能满足签名的需求密钥数量多21C2nnn3.2非对称密码-RSANewDirectionsinCryptographyWhitfieldDiffie，Hellman1976提出了公钥密码算法的概念和思路提出了鉴别和签名问题提出了D-H密钥协商协议国际上已提出了许多公钥密码体制，主要有：基于大整数因子分解问题的RSA；另一类是基于离散对数问题的ElGamal公钥密码和椭圆曲线公钥密码。3.2非对称密码-RSA对称密码和非对称密码各有利弊。非对称密码体制在几方面易受攻击（例如伪装），且加/解密很慢。但它有突出的优点，可以与对称密码体制一起创建完美和有效的密码机制，可以提供高级别的安全性。因此，公钥密码一般用于密钥分发、数据完整性、消息认证等方面。3.2非对称密码-RSA单向函数函数值计算很容易：已知x，很容易计算y=f(x)逆计算是不可行的：已知y，很困难计算x=f-1(y)举例：打碎/拼接、平方/开方、乘法/分解单向陷门函数如果知道某个陷门(秘诀)，即能容易恢复x（陷门即为私钥）举例：魔方的置乱/恢复如果有那个口诀，就能很快恢复单向散列函数抗冲突性质背包问题背包问题描述已知一长度为b的背包及长度分别为a1,a2,…an的n个物品假定这些物品的直径与背包相同若从这些物品中选出若干个正好装满这个背包那么究竟是那些物品?即求解其中ai和b都是正整数背包问题是著名的np完备类困难问题至今没有好的求解方法,而对2n中可能进行搜索实际上是不可能的3.2非对称密码-RSA公钥算法参数建立每个用户生成密钥对(Ke、Kd)Ke或Kd是一个或几个数(大数)而不是随机比特（对称算法）Ke需要公开Kd得自己秘密保留(公钥publickey私钥privatekey密钥secretk