DES算法

DES加密算法的背景 发明人：美国IBM公司W. Tuchman 和 C. Meyer 1971-1972年研制成功。 产生：美国国家标准局（NBS)1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案。 标准化：DES算法1975年3月公开发表，1977年1月15日由美国国家标准局颁布为数据加密标准（Data Encryption Standard），于1977年7月15日生效。

明文 64位码 输入 初始变换 IP 乘积变换 逆初始变换 IP-1 密文 64位码 输出

输入（64位） 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 初始变换 IP 输出（64位） L0（32位） R0（32位）

置换码组 输入（64位） 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 逆初始变换 IP-1 输出（64位）

左32位 右32位 Li-1 Ri-1 扩展置换 64位密钥 48位(明文) 异或 +++++…+++++ 作第i次迭代的 计算机子密钥Ki 密钥 程序表 48位(密钥) 8组6位码 选择函数 输入：6位 输出：4位 S1 S2 S8

32位 置换 32位 异域 +++++...++++++ Li-1 32位 Ri-1 Li Ri 乘积变换中的一次迭代 左32位 右32位

加密函数的选择 运算E A 32位 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 选择运算E 选择运算E的结果 48位

1 0 1 1 0 0 输入6位 10 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 S1 使用选择函数S1 的例子 0 0 1 0 输出4位

选择函数的输出 （32位） 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 置换P 加密函数的结果 （32位）

64位密钥 密钥表的计算逻辑 置换选择1 C0(28位) D0(28位) 循环左移 循环左移 C1(28位) D1(28位) K1 循环左移： 1 1 9 1 2 1 10 2 3 2 11 2 4 2 12 2 5 2 13 2 6 2 14 2 7 2 15 2 8 2 16 1 C0(28位) D0(28位) 循环左移 循环左移 C1(28位) D1(28位) K1 置换选择2 (56位) (48位) 循环左移 循环左移 Ci(28位) Di(28位) Ki 置换选择2 (56位) (48位)

密钥（64位） 置换选择1 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 33 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 C0(28位) D0(28位)

Ci(28位) Di(28位) 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 置换选择2 Ki(48位)

L0R0 ←IP(明文) L1←R0 R1← L0(R0,K1) L2←R1 R2← L1(R1,K2) …… L16←R15 R16← L15(R15,K16) 密文← IP-1(R16L16) 加密方程： L0R0 ←IP(<64位明文>) Ln←Rn-1 Rn← Ln-1(Rn-1,Kn) <64位密文>← IP-1(R16L16) 解密方程： R16L16 ←IP(<64位密文>) Rn-1←Ln Ln-1← Rn(Ln,Kn) <64位明文>← IP-1(L0R0)

DES设计原理 重复交替使用选择函数S和置换运算P两种变换（confusion + diffusion)

DES算法的公开性与脆弱性 DES的两个主要弱点： DES的半公开性：S盒的设计原理至今未公布 由报道表明S盒在次序上、内容上是最优的。 密钥容量：56位不太可能提供足够的安全性 DES的半公开性：S盒的设计原理至今未公布 由报道表明S盒在次序上、内容上是最优的。

Double-DES vs. Triple-DES C =DES (K2, DES(K1, M)) 仅达到257，而不是2112 C = DES(K1,DES-1(K2,DES(K1,M))) M = DES-1(K1,DES(K2,DES-1(K1,C))) C = DES (K3,DES (K2,DES(K1,M)))

Triple-DES的四种模型 DES-EEE3：三个不同密钥，顺序使用三次加密算法 DES-EDE3：三个不同密钥，依次使用加密-解密-加密算法 DES-EEE2：K1=K3，同上 DES-EDE2：K1=K3，同上

DES算法存在的问题与挑战 强力攻击：255次尝试 差分密码分析法：247次尝试 线性密码分析法：243次尝试

对DES攻击结果及其启示 1997年1月28日美国RSA数据安全公司悬赏“秘密密钥挑战”竞赛 48位的RC5 313小时/3500台计算机 1997年3月13日Rocke Verser设计一个攻击程序（DESCHALL），参加的志愿者有78516个，第96天（6月17日晚10：39）Michael Sanders破译成功，获1万美圆奖金。搜索量为24.6%。

密钥长度(bit) 穷举时间 40 78秒 48 5 小时 56 59天 64 41年 72 10，696年 80 2，738，199年 88 700，978，948年 96 179，450，610，898年 112 11，760，475，235，863，837年 128 770，734，505，057，572，42， 069年

RSA

RSA 1990年6月20日美国“数学家找到155位大数因子分解方法--美国加密体制受到威胁” RSA: Ronald L Rivest, Adi Shamir, Leonard Adleman, (A Method for Obtaining Digital Signatures and Public-key Cryptosystems, Communications of the ACM 21 No.2 pp120-126,1978)

素数：只能被1和它本身整除的自然数；否则为合数。 每个合数都可以唯一地分解出素数因子 6 = 2 ·3 999999 = 3·3·3·7·11·13·37 27641 = 131·121 从2 开始试验每一个小于等于√27641 的素数。 整数n的十进制位数 因子分解的运算次数 所需计算时间（每微秒一次） 50 1.4x1010 3.9小时 75 9.0x1012 104天 100 2.3x1015 74年 200 1.2x1023 3.8x109年 300 1.5x1029 4.0x1015年 500 1.3x1039 4.2x1025年

定义 RSA的密钥 p和q是素数 （秘密的） r = p · q (r) = (p-1)(q-1) （秘密的） SK是秘密密钥（解密密钥） （秘密的） PK是公开密钥（加密密钥） X是明文 （秘密的） Y是密文 且PK满足：(PK, (r) )=1; SK满足：SK·PK = 1 mod (r) 同余 如果a和b都是整数，而m是一个固定的正整数，则当m 够整除a-b时，称a, b对模m同余，记为 a  b(mod m)

欧拉定理：a (r) ≡1 (mod r) 其中：① a对r必须是互素的； ② (r) =r(1-1/p1)(1-1/p2)…(1-1/pn) p1,p2,…,pn是r的素数因子 (r) 是r的欧拉函数，它确定1,2,…,r中有多少个是与r互素的因子。 例如：20=2·2·5，有两个素数2和5，这样， (20) =20(1-1/2)(1-1/5)=8 即20中有8个整数与20是互素的，即它们没有2或5为因子： 1, 3, 7, 9, 11, 13, 17, 19 推广欧拉定理： 若a ≡b (mod r) ，则对于任意幂m，有am ≡ bm (mod r) am (r) ≡1 (mod r) 若a ≡b (mod r) ，则对于任意的整数c，有ac ≡ bc (mod r) Xm (r)+1 ≡X (mod r)

例子 其中r=p·q, M[0, r-1] 若p=2,q=3,则r=p*q=6, (r) =(p-1)·(q-1)=2 根据欧拉定理，我们有： 对于集合{1,2,3,4,5}中与r=6互素的数X，有X (r) ≡1 (mod r)； 对于集合{1,2,3,4,5}中所有的X，有X (r)+1 ≡X (mod r)； X X (r) (mod r) X (r)+1 (mod r) 0 0 0 1 1 1 2 4 2 3 3 3 4 4 4 5 1 5

设选择的公开密钥PK和秘密密钥SK，使得： PK·SK=m (r) +1 或等价于： PK·SK≡1 (mod (r) ) 则有： XPK·SK≡X (mod r) 现在，我们可以建立加密和解密的表示： EPK(X)=Y≡ XPK (mod r) DSK(Y)≡ YSK (mod r)≡ XPK·SK (mod r) ≡X (mod r) 由于乘法运算的可交换性质，SK·PK=PK·SK, 有： DSK(EPK(X))=EPK(DSK(X))≡ X (mod r) 注意：对任意整数m, XPK (mod r)≡（X+mr）PK (mod r),所以每一个明文X,X+r,X+2r, …,X+mr将产生同样的密文。 若限定X在集合{1,2,…,r-1}之内时，明文与密文就是一对一了。

RSA算法的加密方程与解密方程是： C=MPK mod r M=CSK mod r 其中r=p·q, M[0, r-1] 　　定理２　若d=(a,n)表示d为a,n的最大公约数gcd，则只要a,n的gcd能整除b，同余式aX≡b (mod n)就是可解的，而且在这种情况下同余式有d个解。 若a与n分别定义为SK和(r)，则当且仅当gcd(SK, (r))=1，即SK与(r) 互素时，gcd(SK, (r))才能整除1。当X定义为PK时，仅当SK与(r) 互素，同余式SK·X≡1 (mod (r))才有解。若a=PK，X的解将为SK。

例子 例：p=47, q=61, (r)=2760时 gcd(2760,167)=1。 PK公开密钥的计算： 167＊1223＝１　mod (2760)

(1) 明文用数字表示 空白=00， A=01, B=02, …, Z=26 用RSA算法加密与解密的过程： 例：明文=“RSA ALGORITHM” (1) 明文用数字表示 空白=00， A=01, B=02, …, Z=26 1819 0100 0112 0715 1809 2008 1300 (2) 利用加密变换公式 C=mPK mod r, 即C = 18191223 mod 2867=2756 C=18191223 (mod 2867) =2756 2756 2001 0542 0669 2347 0408 1815 (3) 解密 M=2756 167(mod 2867)= 1819

关于素数的分布 1 - 100 25 101 - 200 21 201 - 300 16 301 - 400 16 401 - 500 17 501 - 600 14 601 - 700 16 701 - 800 14 801 - 900 15 901 - 1000 14 素数定理：当X变得很大时，从2到X区间的素数(X)与X/ln(X)的比值趋近于1，即 (X) lim x = 1 X/ln(X) (X) X/ln(X) X (X) X/ln(X) 1000 168 145 1.159 10,000 1,229 1,086 1.132 100,000 9,592 8,686 1.104 1,000,000 78,498 72,382 1.084 10,000,000 664,579 620,421 1.071 100,000,000 5,761,455 5,428,681 1.061 1,000,000,000 50,847,478 48,254,942 1.054

在 2到X的区间中，随机选择一个值为素数的概率近似等于(X)/(X-1)。 可以证明，在找到一个素数之前，大约平均要进行(X-1)/ (X)≈ln(X)次实验。 《An Introduction to the Theory of Numbers》1972, I. Niven, H.A. Zuckman

对RSA的攻击方法 1、强力攻击（穷举法）：尝试所有可能的私有密钥 2、数学分析攻击：各种数学方法，等价与两个素数乘积的因子分解 3、时间性攻击：取决于解密算法的运算时间 因子分解问题有三类方法： 1、分解n， n=pq,  (n)=(p-1)(q-1)  d = e-1 mod (n) 2、直接确定 (n)，  d = e-1 mod (n) 3、直接确定 d

其它对RSA的攻击 对RSA公共模数的攻击 对RSA低加密指数的攻击 对RSA低解密密指数的攻击 对RSA的加密和签名的攻击

谢谢