基于背包问题的Merkle-Hellman背包公 钥体制
基于有限域上离散对数问题的ElGamal 公钥体制
基于椭圆曲线的ECC密码体制
……
公钥密码体制介绍
公钥密码体制加解密过程主要有以下几步 ：
不一样的密码
安全的公开密钥密码达到的功能
（1）简化密钥分配及管理问题
➢ 公钥体制用于数据加密时：
两两互不相同，构成一个1~p-1的全体数 的一个排列。对于任意数b及素数p的原元 a，可以找到一个唯一的指数 i，满足
b ai mod p , 0<=i<=p-1
则称指数i为以a为底、模p的b的离散对数。
1.基本原理
用户A
公开 YA 秘密 XA
用户B
YB 公开
XB 秘密
计算
计算
会话秘密 KA 密钥交换过程 KB 会话秘密
应用最广泛的公钥密码算法 只有美国专利，且已于2000年9月到期
1．RSA算法要点
算法产生一对密钥，一个人可以用密钥对中 的一个加密消息，另一个人则可以用密钥对 中的另一个解密消息。同时，任何人都无法 通过公钥确定私钥，也没有人能使用加密消 息的密钥解密。只有密钥对中的另一把可以 解密消息。
➢ 对方收到消息后，为了确定信源的真实性，用对方的解密密钥解 密签名消息──称为（签名）验证，如果解密后的消息与原消息 一致，则说明信源是真实的，可以接受，否则，拒绝接受。
4.2 Diffie-Hellman 密钥交换算法
W.Diffie和M.E.Hellman于1976年提出的，让A和B 两个陌生人之间建立共享秘密密钥的公开密钥算 法，称为Diffie-Hellman算法，它定义了公开密 钥密码体制。它的目的是使得两个用户安全地交 换一个密钥以便用于以后的报文加密，这个算法 本身限于密钥交换的用途。许多商用产品都使用 这种密钥交换技术。
在Diffie-Hellman密钥交换算法中的单向函数 是模指数运算。它的逆过程是离散对数问题，其 Diffie-Hellman算法的保密性基于求mod p解离散 对数问题的困难。
离散对数
定义素数p的原元（原始根）为这样一个 数，他能生成1~p-1所有数的一个数。现 设a为p的原元，则
a mod p, a2 mod p,L , a p1 mod p
c= me mod n=857 mod 143=123，并发送给 李先生。
李先生在收到密文c=123后，利用只有他自己 知道的秘密密钥计算：m= cd mod n =123103 mod 143=85，所以，李先生可以得到张小姐发 给他的真正的信息m=85，实现了解密。
7．RSA算法的安全性
依赖于大数分解，但是否等同于大数分解一直 未能证明。不管怎样，分解n是最显然的攻击方法 。 1994年4月26日，美国各大媒体报道：由RSA发 明人在17年前出的129位数字已被因子分解，并破 解了附带的密语：
公开密钥密码体制的产生，是密码学革命 性的发展。一方面，为数据的保密性、完 整性、真实性提供了有效方便的技术。另 一方面，科学地解决了密码技术的瓶颈 ──密钥的分配问题。
公钥体制算法
第一个公钥体制是1977年由Rivest， Shamir，Adleman提出的，称为RSA 公钥体制，其安全性是基于整数的因子 分解的困难性。RSA公钥体制已得到了 广泛的应用。
➢ 3)为保证安全性，n 至少也要 600 bits以上 ，且还在增加。在运算上要付出代价。
12. RSA算法和DES算法比较
比较1
在加密、解密的处理效率方面，DES算法 优于RSA算法。因为DES密钥的长度只有５６ 比特，可以利用软件和硬件实现高速处理； RSA算法需要进行诸如２００比特整数的乘幂 和求模等多倍字长的处理，处理速度明显慢于 DES算法。
续（2）
比较3 在安全性方面，DES算法和RSA算法
的安全性都较好，还没有在短时间内破译 它们的有效的方法。
比较4 在签名和认证方面，DES算法从原理
上不可能实现数字签名和身份认证，但 RSA算法能够容易地进行数字签名和身份 认证。
13. 基于DES和RSA的加密方案
设发送方为A(加密密钥为Kea,解密密钥为 Kda),接收方为B(加密密钥为Keb,解密密钥为 Kdb)。
1978年由Ron Rivest、AdiShamir和Len Adleman发明。
➢ “A method for obtaining digital signatures and public key cryptosystem”
是一种块加密算法。
➢ 明文和密文在0~n-1之间,n是一个正整数
特征与不足
➢特征：
•（1）仅当需要时才产生密钥，减少储存时间，减 少受攻击的机会； •（2）除对全局参数的约定外，密钥交换不需要事 先存在的基础结构。
➢不足：
➢（1）没有通信双方身份的信息； ➢（2）计算是密集性的，容易受到阻塞性攻击； ➢（3）没办法防止重放攻击； ➢（4）容易受到中间人攻击。
4.3 RSA算法
4.RSA 的使用
发送方要加密明文M:
➢ 获得接收方的公钥 KU={e,N} ➢ 计算: C=Me mod N, where 0≤M<N
接收方解密密文C:
➢ 使用自己的私钥 KR={d,N} ➢ 计算: M=Cd mod N
注意：M必须比N小
5．RSA例1
①取两个质数p=11，q=13，p和q的乘积为 n=p×q=143，算出另一个数z=(p-1)×(q-1)=120； ②再选取一个与z=120互质的数，例如e=7，则
2.RSA算法描述
加密： C=Me mod N, where 0≤M<N 解密： M=Cd mod N 公钥为（e，N）， 私钥为（d，N） 必须满足以下条件：
➢ 计算Me和Cd是比较容易的 ➢ 由e和N确定d是不可行的
3.RSA 密钥产生过程
随机选择两个互质大素数 p, q (p，q 必须保密) 计算 n=p.q 计算z =(p-1)(q-1) 随机选择整数 e，使得1<e<z且gcd(e,z)=1 计算d ：d=e-1 mod z 且 0≤ d ≤ n 公布公钥: KU={e，n} 保存私钥: KR={d，n}
2.交换示例 为了计算简单，使用很小数字。设P=47和47
的一个原元，a=3。
A选择秘密密钥XA=8，B选择秘密密钥XB=10， 各自计算其公开密钥。
（1）双方各自计算
➢ 用户A计算：YA=3 8mod 47=6561 mod 47=28 mod 47
➢ 用 户 B 计 算 ： YB=3 10mod 47= 59049 mod 47=17 mod 47
密钥交换过程
(1)选择一个素数P和它的一个原元a;
(公2)开通密信钥方YAA选: 择自己的秘密密钥XA,并计算自己的 YA=a XA mod P
(3)通信方B选择自己的秘密密钥XB,并计算自己的 公开密钥YB: YB=a XB mod P
(4)通信双方A和B交换YA和YB； (5)A独立计算会话密钥，B独立计算会话密钥KS； (6)通信双方利用会话密钥KS进行通信。
➢ p、q不相同，即不要太接近，又不能差别太大 ➢ p-1、q-1都有大素数因子，增加猜测φ(r) 难度 ➢ gcd( p-1，q-1)应当小
RSA算法的脆弱性(续)
4)p、q选择不当，则变换周期性、封闭性而泄密 例：p=17，q=11，e=7，则n=187。 设m=123，则 C1=1237 mod 187=183 C2=1837 mod 187=72 C3=727 mod 187=30 C4=307 mod 187=123 明文m经过4次加密，恢复成明文。
公开密钥=（n，e）=（143，7）。 ③ 对于这个e值，可以算出其逆：d=103。 ④ 因为e×d=7×103=721，满足e×d mod z =1 ；即721 mod 120=1成立。
则秘密密钥=（n，d）=（143，103）。
6．RSA例2
张小姐需要发送机密信息（明文）m=85给李 先生，她已经从公开媒体得到了李先生的公开密 钥(n，e)=(143，7)，于是她算出加密值：
➢ 可见，这里省去了从秘密信道传递密钥的过程 。这是公钥体制的一大优点。
密成密文，此后只有拥有解密密钥 的人才能解密。
（3）实现不可否认功能
➢ 公钥体制用于数字签名时：
➢ 信源为了他人能够验证自己发送的消息确实来自本人，他将自己 的秘密（解密）密钥公布，而将公开（加密）密钥严格保密。与 别人通信时，则用自己的加密密钥对消息加密──称为签名，将 原消息与签名后的消息一起发送.
续（1）
比较2
在密钥的管理方面，RSA算法比DES 算法更加优越。因为RSA算法可采用公开 形式分配加密密钥，对加密密钥的更新也 很容易，并且对不同的通信对象，只需对 自己的解密密钥保密即可；DES算法要求 通信前对密钥进行秘密分配，密钥的更换 困难，对不同的通信对象，DES需产生和 保管不同的密钥。
2.交换示例（续） （2）交换YA和YB； （3）交换密钥后，A、B分别计算共享的秘密
会话密钥KA、KB： ➢ 用 户A计 算： KA=YB XA mod 47=178 mod
47=4 mod 47
➢ 用户B计算： KB=YA XB mod 47=2810 mod 47=4 mod 47
A和B双方独立地决定采用数据“4”作为 会话密钥。
第二讲 信息安全技术
第2章 密码技术基础 第3章 对称密码体系 第4章 公钥密码体系 第5章 公钥基础设施PKI 第6章 信息隐藏技术
第四章 内容
4.1公钥密学概述 4.2 Diffie-Hellman 密钥交换算法 4.3 RSA算法