DES算法.

Presentation on theme: "DES算法."— Presentation transcript:

1 DES算法

2

3 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日生效。

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

5 输入（64位） 初始变换 IP 输出（64位） L0（32位） R0（32位）

6 置换码组 输入（64位） 逆初始变换 IP-1 输出（64位）

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

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

9 加密函数的选择 运算E A 32位 选择运算E 选择运算E的结果 48位

10 输入6位 10 2 S1 使用选择函数S1 的例子 输出4位

11 选择函数的输出 （32位） 置换P 加密函数的结果 （32位）

12 64位密钥 密钥表的计算逻辑 置换选择1 C0(28位) D0(28位) 循环左移 循环左移 C1(28位) D1(28位) K1
循环左移： C0(28位) D0(28位) 循环左移 循环左移 C1(28位) D1(28位) K1 置换选择2 (56位) (48位) 循环左移 循环左移 Ci(28位) Di(28位) Ki 置换选择2 (56位) (48位)

13 密钥（64位） 置换选择1 C0(28位) D0(28位)

14 Ci(28位) Di(28位) 置换选择2 Ki(48位)

15 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)

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

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

18 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)))

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

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

21 对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%。

22 密钥长度(bit) 穷举时间 秒 小时 天 年 ，696年 80 2，738，199年 ，978，948年 ，450，610，898年 ，760，475，235，863，837年 ，734，505，057，572，42， 069年

23 RSA

24 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 pp ,1978)

25 素数：只能被1和它本身整除的自然数；否则为合数。
每个合数都可以唯一地分解出素数因子 6 = 2 ·3 = 3·3·3·7·11·13·37 = 131·121 从2 开始试验每一个小于等于√27641 的素数。 整数n的十进制位数 因子分解的运算次数 所需计算时间（每微秒一次） x 小时 x 天 x 年 x x109年 x x1015年 x x1025年

26 定义 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)

27 欧拉定理：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)

28 例子 其中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)

29 设选择的公开密钥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}之内时，明文与密文就是一对一了。

30 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。

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

32 (1) 明文用数字表示 空白=00， A=01, B=02, …, Z=26
用RSA算法加密与解密的过程： 例：明文=“RSA ALGORITHM” (1) 明文用数字表示 空白=00， A=01, B=02, …, Z=26 (2) 利用加密变换公式 C=mPK mod r, 即C = mod 2867=2756 C= (mod 2867) =2756 (3) 解密 M= (mod 2867)= 1819

33 关于素数的分布 素数定理：当X变得很大时，从2到X区间的素数(X)与X/ln(X)的比值趋近于1，即 (X) lim x = 1 X/ln(X) (X) X/ln(X) X (X) X/ln(X) 10, , , 100, , , 1,000, , , 10,000, , , 100,000, ,761, ,428, 1,000,000, ,847, ,254,

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

35 对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

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

37 谢谢