现代密码技术

现代密码技术 DES RSA 计算机网络安全 Chapter3 3 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数据加密标准DES 3 1数据加密标准DES 2 混淆 confusion 其目的在于使作用于明文的密钥和密文之间的关系复杂化 是明文和密文之间 密文和密钥之间的统计相关特性极小化 从而使统计分析攻击不能奏效 3 1数据加密标准DES 乘积密码 ProductCipher 就是以某种方式连续执行两个或多个简单密码 如替代 置换 以使得所得到的最后结果或乘积比其任意一个组成密码都更强的分组密码 Shannon提出交替使用混淆和扩散进行乘积密码 基于Shannon理论 Feistel建议交替地使用代换和置换 Feistel密码结构 方法将输入分组分成左右两部分 以右半部数据和子密钥作为参数 对左半部数据实施代换操作 将两部分进行互换 完成置换操作 优点能够产生雪崩效应快速软件加解密易于分析可自行设计的内容 分组长度密钥长度轮数子密钥生成算法轮函数 LEi REi 1REi LEi 1 F REi 1 Ki Feistel每一轮的加密 替换 置换 3 1数据加密标准DES 3 1数据加密标准DES DES加密操作DES在加解密过程中 将明文和密文分成64比特的分组进行操作 其一大特点是解密过程与加密过程是相似的 首先对64比特的明文分组进行IP置换 IP置换将输入分组的第58比特作为输出的第1比特 输入的第50比特作为输出的第2比特 依次类推 然后用密钥k对得到的结果进行迭代操作 最后再对迭代操作的结果进行IP 1置换产生输出分组 下面是DES算法的略图 48bitsubkey 5850423426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725 3 1数据加密标准DES 1 初始置换与逆置换 IP IP 1 例如 IP 675a69675e5a6b5a ffb2194d004df6fb 加密 Li Ri 1Ri Li 1 f Ri 1 ki 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 12131415161716171819202120212223242524252627282928293031321 2 E扩展 32 48 称s1 s2 s8为s盒 实现明文消息在密文消息空间中的随机非线性分布 可以抵抗差分分析攻击DC s盒的运算规则为 输入的6比特数据的第一和第六比特为s和的行数 其余比特决定s盒的列数 例如 当s1的输入为011011时 其输出为0101 s11441312151183106125907015741421311061211953841148136211151297310501512824917511314100613 3 S盒子的设计 压缩置换 DES的核心部分 8个S盒 P为一个输入和输出都为32比特的置换 具体形式如下 1672021291228171152326P 518311028241432273919133062211425 4 P置换 第16比特 第1比特第07比特 第2比特 第25比特 第32比特 DES算法的密钥k由一个56位的密钥以及附加的8位奇偶校验位组成 经过密码扩展算法可以把它扩展为16个子密钥 其中迭代次数与左移的比特数关系如下 迭代次数12345678910111213141516左移位数1122222212222221 3 1数据加密标准DES 5 轮密钥的产生 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 IP 3 1数据加密标准DES DES的雪崩效应 雪崩效应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数据加密标准DES DES的强度 S box问题其设计标准没有公开 但是迄今没有发现S盒存在致命弱点计时攻击计时攻击利用的事实是加密或解密算法对于不同的输入所花的时间有细微的差别DES能够很好地抵抗计时攻击弱密钥 注意避免 弱密钥 8个弱密钥半弱密钥 2个半弱密钥 3 1数据加密标准DES DES的强度 DESCrackerTheElectronicFrontierFoundationbuilttheso calledDESCrackersupercomputerin1998tocrack56 bitDESencryption ItlaterwonRSALaboratory s DESChallengeII contestinabout56hours DESCrackerhad26 andlater27 systemboards eachwith32or64customAWT 4500DeepCrackchips foratotalofabout1 500to1 800chips 3 2非对称密码 RSA 对称算法的缺陷为事先协商密钥 需另外的安全信道或KDC不能满足签名的需求密钥数量多 3 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密钥secretkey 公钥的发布从Ke推导Kd的困难性使Ke不怕被公开公开的目录服务公钥Ke要在专门机构 CA 登记 3 2非对称密码 RSA 公钥算法加密加密 如果有人要给该用户发送消息P 先获得该用户的公开钥Ke加密C E P Ke 传输解密D C Kd P除非拥有Kd 否则不能解开 一般用于传输会话密钥 和签名及鉴别 3 2非对称密码 RSA 公钥密码算法的实现对称算法替换混乱基于某些数学特性 从公钥推导私钥理论可能 但计算困难 从私钥到公钥容易 大整数的分解离散对数问题 公钥算法用来加密图示 消息来源鉴别和数字签名 使用加密 解密操作对称的算法 如RSA对消息H签名 S Sig H Kd 验证Ver C Ke H消息H必然是Kd的持有人签署的 公钥算法用来鉴别图示 RSA算法 在Diffle和Hellman提出公钥的设想后两年 MIT的Rivest Shamir和Adleman联合提出了被人们称之为RSA的公钥密码系统 其基础是数论的欧拉定理 其安全性依赖于大整数因数分解的困难性 基本参数分组密码算法基于整数乘法明 密文分组以及公 私钥被看作小于n的整数加 解密是模乘运算 RSA参数建立 找素数选取两个512bit的随机素数p q计算模n和Euler函数 n n pq n p 1 q 1 找ed 1mod n ed r n 1 选取数e 用扩展Euclid算法求数d发布发布 e n 这是公钥ked保密 d n 是私钥kd 扩展的辗转除法 扩展Euclid算法举例 22 1mod3131 1 22 9 1 22 9即30 22 9mod3122 2 9 422 2 1 22 4即3 22 4mod319 2 4 1 1 22 2 3 22 1即24 22 1mod3128 1mod7575 2 28 19 2 28 19即73 28 19mod7528 1 19 928 1 2 28 9即3 28 9mod7519 2 9 1 2 28 2 3 38 1即67 28 1mod75269 1mod349349 1 269 80 1 269 80即 1 269269 3 80 29269 3 1 269 29即4 26980 2 29 22 1 269 2 4 269 22即 9 26929 1 22 7 4 269 1 9 269 7即13 26922 3 7 1 9 269 3 13 269 1即 48 269得301 Euler欧拉函数 欧拉函数 n 定义为小于n而互素的正整数的个数也即模n的简化剩余集 互素 的元素个数举例 若p q都是素数 p p 1 p q p q p 1 q 1 pq p q 1比如n 15 3 5 p q则 n 3 1 5 1 8即8 1 2 4 7 8 11 13 14 欧拉定理 如果a n互素 则a n 1modn 或即a n 1 amodn比如n 15 3 5 n 81 2 4 5 7 8 11 13 148 1mod15而3 6 9 10 128 1mod15 RSA加密解密 加密明文分组m做为整数须小于nc memodn解密m cdmodnRSA的安全性是基于加密函数ek x xe modn 是一个单向函数所以对的人来说求逆计算不可行而Bob能解密的陷门是分解n pq知 n p 1 q 1 从而用欧氏算法解出解密私钥d RSA的正确性 证明依据Euler定理 在modn的含义下cd me d medmodn mk n 1modn mmodn 据Euler定理 关于mk n 1 如果n pq 则mk n 1 mmodn如果m和n互素 直接使用欧拉定理即得如果m和n不互素 则公因子必是p 或者q 事实上 此时mk n 1 mmodp 因为m是p的倍数 mk n 1 mmodq 根据Fermat小定理 mk n 1 mmodpq 由以上两式 Fermat小定理 若p是素数 gcd a p 1 则ap 1 1modp 或即ap amodp举例25 1 1mod5411 1 1mod11证明见备注 RSA实例 选p 7 q 17则n pq 119且 n p 1 q 1 6 16 96取e 5则d 77 5 77 385 4 96 1 1mod96 公钥 5 119 私钥 77 119 加密m 19则c memodn 195mod119 66mod119解密c 66m cdmodn 6677mod119 19mod119 RSA考虑 素数必须够大 否则对手可能很快分解n判定 试除法不可行判定 采用Miller Rabin概率测试方法强素数 p 1 2和 q 1 2应是素数选取较小的e 较大的d e 3 65537快速计算X Y Z RSA中基本计算的复杂度 大数的加 减计算复杂度O k O k 字加法 K是大数的字宽度大数的乘 除 逆元 计算复杂度O k2 O k2logk 字乘法 大数指数运算xcmodnO k2logc 字乘法 注 都是在modn下 模幂乘举例 97221 2003 都在模2003意义下 97221 97128 64 16 8 4 1 9712897649716978974971依次计算971 972 974 978 9716 97128一直平方下去即可 并保持模2003如果某次方在1式出现 则累乘累积开始是1 乘法次数O log2Y 模幂乘算法实现 计算W X YmodZW 1ForeachbitofY Y1Y2 YkW W W ZifYi 1thenW W X ZEndfor 分解里程碑 十 二进制日期MIPS年方法69 1983二次筛法106 1989100 332April19917quadraticsieve110 365April199275quadraticsieve120 398June1993830quadraticsieve129 428April19945000quadraticsieve130 43