2.2 密码算法
2.2.2 RSA算法
2.RSA算法举例
产生密钥
①设选择了两个素数，p=7，q=17。 ②计算出n=p*q=7×17=119 ③计算出φ=(p-1)*(q-1)=(7-1)(17-1)=96。 ④从[0，95]中选择一个与96互素的数e。选e=5。 得5*d=1 mod 96解出d。不难得出，d=77,因为 e*d=5×77=385=4×96 + 1=1 mod 96。 ⑤ 公开密钥PK={e,n}={5,119}， 秘密密钥SK={d,n}={77,119}。
密码技术
密码学



包括两部分：数据加密和密码破译 数据加密：对信息进行加密和解密的技 术 加密算法，解密算法，密钥管理技术 密码破译：攻破加密信息的技术 破解加密信息，破解密钥
密码
数据加密的基本概念：



明文（plaintext,P）:未加密的信息或数据 密文（ciphertext,C）加密的信息或数据 加密算法（E）：将明文转化为密文的处理过程 解密算法（D）将密文转化为明文的处理过程 加密密钥（KE）控制加密过程的一种信息或数据 解密密钥（KD）控制解密过程的一种信息或数据 加密过程：C=E(KE,P), 解密过程：P=D(KD,C)
对DES的评述

DES算法存在的问题与挑战 55次尝试 强力攻击：2 47次尝试 差分密码分析法：2 43次尝试 线性密码分析法：2
DES搜索速度估算
密钥长度(bit) 40 48 56 64 72 80 88 96 112 128 穷举时间 78秒 5 小时 59天 41年 10，696年 2，738，199年 700，978，948年 179，450，610，898年 11，760，475，235，863，837年 770，734，505，057，572，442，069年
②计算φ(n)。计算出n的欧拉函数φ(n)=（p-1）（q-1）， φ(n)定义为不超过n并与n互素的数的个数。 ③ 选择 e。用户从[0, φ(n) - 1]中选择一个与φ(n)互素的 数e作为公开的加密指数。 ④ 计算d。计算出满足下式的d， ed= 1 modφ(n) 作为解密指数。
⑤ 得出所需要的公开密钥和秘密密钥： 公开密钥（即加密密钥）PK {e, n} 秘密密钥（即解密密钥）SK {d, n}
64位明文 DES算法 64位密文
64位密钥（56位有效）
DES的结构图
明文输入（64位码） 初始变换IP
乘积变换
逆初始变换IP-1
密文输出（64位码）
DES 加 密 标 准
输入（64位）
初始变换IP
58 60 62 64 57 59 61 63
50 52 54 56 49 51 53 55
42 44 46 48 41 43 45 47
RSA算法
2.RSA算法举例
现在设明文 X为19。公开密钥={5,119}，私有密钥={77,119} 加密运算过程 2476099 195= 119 明文 =20807 及余数 66 密文 解密运算过程 1.27…×10140
6677= 密文
119
=1.06×10138 及余数 明文 19
2.2.2 3、RSA算法的安全性
RSA算法
RSA的安全性依赖于大数分解困难。公钥和私钥 都是两个大素数（ 大于 100个十进制位）的函数。 据猜测，从一个密钥和密文推断出明文的难度等同于 分解两个大素数的积。
目前， RSA的一些变种算法已被证明等价于大数分解。 不管怎样，分解n是最显然的攻击方法。现在，人们 已能分解140多个十进制位的大素数。因此，模数n须 选大一些，因具体适用情况而定。
EPK（DSK（X）） ＝ X不能用PK解密 在计算机上可以容易地产生成对的PK和SK 从已知的PK不可能推导出SK，即从PK到SK 是“计算上不可能的”。
加密和解密算法都是公开的。
RSA算法相关概念
1、什么是“素数”？
2、什么是“互质数”（或“互素数” ） 3、什么是模指数运算？
互质数判别方法（不限于此）
乘积变换
Li-1
乘积变换中的一次迭代
64位密钥 置换选择1 C0(28位) 循环左移 C1(28位) D0(28位) 循环左移 D1(28位) (56位) 循环左移 Ci(28位) 循环左移 Di(28位) (56位)
密钥表的计算逻辑
循环左移： 1 1 2 1 3 2 4 2 5 2 6 2 7 2 8 2 9 10 11 12 13 14 15 16 1 2 2 2 2 2 2 1

传统加密算法

3、异或加密法

异或规则： 0 xor 1=1 1 xor 0=1 1xor 1=0 0 xor 0=0
异或规律：假如X xor Y=Z 则有X xorZ=Y Zxor Y=X


举例：
X=1011 0110 Y=0110 1101 Z=1101 1011
应用

原文：Who are you 密钥：123123123

明文 加密 Ｅ
密文
解密后的明文 解密 Ｄ

k
k

密 钥 产生器


加密和解密表示为： ＥＫ（Ｍ）＝Ｃ ＤＫ（Ｃ）＝Ｍ 解密算法是加密算法的 逆运算 加密密钥和解密密钥相 同； 加密算法强度高； 密钥传递需专用通道；
DES算法


为二进制编码数据设计的，可以对计算机数据进行密 码保护的数学运算。DES的保密性仅取决于对密钥的保 密，而算法是公开的。 64位明文变换到64位密文，密钥64位，实际可用密钥 长度为56位。
2.公开密钥密码体制
每个用户产生一对密钥PK和SK
基 本 思 想
加密密钥（即公开密钥）PK 公开
解密密钥（即私有密钥）SK 保密 加密算法E和解密算法D也都是公开
私有密钥SK由公开密钥PK决定，但 却不能根据PK计算出SK
2.公开密钥密码体制
公 开 密 钥 算 法 描 述
DSK（EPK（X）） ＝ X EPK（DSK（X）） ＝ X
DES的发展
.三重DES
三重DES (Triple DES)是Tuchman提出的，并在 1985 年成为美国的一个商用加密标准[RFC 2420]。三重DES使 用两个（或三个）密钥，执行三次DES算法。 其做法有许多的方式： DES-EEE3 DES-EDE3 DES-EEE2 DES-EDE2，
密码破译技术



已知密文：攻击者仅仅掌握密文，试图破译对 应的明文，加密算法和密钥 已知明文：攻击者掌握了大量的明文和对诮的 采用相同加密算法和密钥加密的密文，试图破 译加密这些密文的算法和密钥 选择明文：攻击者可以向被攻击的加密系统提 交无数个选择的明文并查对生成的密文，试图 破译加密系统的加密算法和密钥
传统加密算法

1、替换密码： 如凯撒密码
举例：



明码表 A B C D E F G H I J K L M N O P QRSTUVWXYZ 密码表D E F G H I J K L M N O P Q R S TUVWXYZABC 明文 F O R E S T 密文 IRUHVW
34 36 38 40 33 35 37 39
26 28 30 32 25 27 29 31
18 20 22 24 17 19 21 23
10 12 14 16 9 11 13 15
2 4 6 8 1 3 5 7
输出（64位） L0（32位） R0（32位）
置换码组 输入（64位）
逆初始变换IP-1
RSA算法 1.算法的描述 （1）RSA公开密钥加、解密算法
设用整数X表示明文， 用整数Y表示密文（X和Y均小于n），
加密算法 加密：Y = Xe mod n
解密算法 解密：X = Yd mod n
RSA算法 1.算法的描述 (2)RSA密钥的产生
①计算n。秘密地选择两个大素数p和q，n= pq。n称为 RSA算法的模数。
置换选择2
K1
(48位)
置换选择2
Ki
(48位)
对DES的评述

对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%。
32 31 30 29 28 27 26 25
输出（64位）
左32位
Li-1
右32位
乘积变换 Ri-1 选择
64位密钥
48位(明文) 模2加 +++++…+++++ 48位(密钥) 8组6位码 S1 S2
作第i次迭代的 密钥 计算机子密钥Ki 程序表 选择函数 输入：6位 输出：4位
S8
32位 置换 32位 模2加+++++...++++++ 32位 Ri-1 Li 左32位 Ri 右32位
密码系统
明文用Ｍ或Ｐ表示，密文用C表示。加密函 数Ｅ作用于Ｍ得到密文Ｃ。 可用数学公式表示： EK（M）＝C 相反地，解密函数Ｄ作用于Ｃ产生Ｍ： DK（C）＝M 先加密后再解密，原始的明文将恢复，故下 面的等式必须成立： DK（EK（M））＝M
密码系统


密码编码学与密码分析学合起来即为密 码学。 密码编码学是密码体制的设计学，而密 码分析学则是在未知密钥的情况下从密 文推演出明文或密钥的技术。