当前位置：文档之家 › 非对称密码体制课件

非对称密码体制课件

  • 格式：ppt
  • 大小：501.00 KB
  • 文档页数：16

下载文档原格式

  / 16

合集下载

密码技术基础知识ppt课件

密码技术基础知识ppt课件

19
公钥基础设施
PKI系统组成
证书发布系统 证书发布系统负责证书的发放，如可以通过用户自己
，或是通过目录服务器发放。目录服务器可以是一个组织中现 存的，也可以是PKI方案中提供的。
20
公钥基础设施
PKI的应用
PKI的应用非常广泛，包括应用在web服务器和浏览器 之间的通信、电子邮件、电子数据交换(EDI)、在Intenet上的 信用卡交易和虚拟私有网(VPN)等。
对称加密算法相比非对称加密算法来说，加解密的效率要高得 多。但是缺陷在于对于秘钥的管理上，以及在非安全信道中通讯时， 密钥交换的安全性不能保障。所以在实际的网络环境中，会将两者混 合使用。
12
目录
公钥基础设施
简介 PKI系统组成 PKI的应用
13
公钥基础设施
简介
PKI是“Public Key Infrastructure”的缩写，意为“公钥基础 设施”。简单地说，PKI技术就是利用公钥理论和技术建立的提供信息 安全服务的基础设施。公钥体制是目前应用最广泛的一种加密体制， 在这一体制中，加密密钥与解密密钥各不相同，发送信息的人利用接 收者的公钥发送加密信息，接收者再利用自己专有的私钥进行解密。 这种方式既保证了信息的机密性，又能保证信息具有不可抵赖性。
26
数字摘要技术
数字摘要的常用技术
4、Base64 Base64是一种基于64个可打印字符来表示二进制数据的方法 ，由于2的6次方等于64，所以每6位为一个单元，对应摸个可打印字 符，三个娭毑有24位，，对应4个Base64单元，即三个字节需要用4个 打印字符来表示。
27
数字摘要技术
数字摘要的应用
40
密钥管理技术
密钥的分配
第5章非对称密码体制与典型算法

第5章非对称密码体制与典型算法

（5）他人即使知道公开密钥 PUb和密文c，要想恢复报文 m在计
算上也是不可行的。
（6）加密和解密函数可以以两个次序中的任何一个来使用: m＝dPRb(ePUb(m)) 第5章 m=ePUb(dPRb(m))
7
非对称密码体制与典型算法
三、陷门单向函数
满足下列条件：
• 给定x，容易计算y=f(x) • 给定y =f(x), 难以计算出x • 存在陷门δ，已知δ 时,对给定的 任何y，若相应的x存在，则计 算x使y=f(x)是容易的
明文:
第5章
public
19
非对称密码体制与典型算法
二、RSA算法的实现问题
•如何产生大素数p和q ?
•如何快速计算 am mod
n？
第5章
非对称密码体制与典型算法
20
二、RSA算法的实现问题
1、产生大素数p和q
WITNESS(a,n)； a 是基数，判断奇数n是否为素数 将(n-1) 表示为二进制形式bkbk-1…b0; d 1; 返回值 for i k downto 0 do FALSE：n一定不是素数 { TRUE: n可能是素数 x d; d (d d) mod n; if (d = 1) and (x 1) and (x n -1) then return FALSE; if (bi = 1) then d (d a) mod n; } if (d 1) then return FALSE; return TRUE; 第5章 非对称密码体制与典型算法
陷门
第5章
非对称密码体制与典型算法
10
一、RSA算法描述
1、算法描述
• 明文空间P＝密文空间C=Zn • 密钥的生成
《非对称密码体制》课件

《非对称密码体制》课件

5. 计算私钥
使用扩展欧几里得算法，计算d, 满足d*e % phi(n) = 1。
2. 计算n
计算n=p*q。
4. 选择公钥
选择一个与phi(n)互质的整数e。
6. 完成
完成后，公钥由n和e组成，私钥由d组成。
RSA算法的解密过程
1. 加密数据
使用公钥(n, e)加密消息M，产生密文C。
2. 计算明文
1
1. 选择素数
选择一个素数q, 以及一个大素数p = kq + 1, 保护q。
2
2. 选取g值
选择一个能提供一个循环群的数g(1 <= g <= p-1)。
3
3. 计算x,y
任意选择一个512位的长整数k，然后计算x = g^k mod p, y = (hash(M) + x*a)/k mod q, hash(M)为M的哈希值。
使用私钥d，计算出原始消息M。M = Cd (mod n)
3. 完成
接收方使用私钥d，根据公式计算出M。
RSA算法的安全性分析
RSA算法显然会受到攻击，但我们认为这个算法还是安全的。攻击者可以使用因子分解算法来破解RSA 算法，但是这需要一个非常长的时间。对于RSA算法安全保护的加强，一般使用扩展和混淆技术。
非对称密码的优势
提高了数据传输的安全性， 避免了密钥管理的麻烦。
小提示
有时候也会将它们结合使 用，来发挥它们的优势。
典型的非对称密码算法
目前最流行的非对称密码算法有：RSA算法、DSA算法、ECC算法等。下图是其概述:
RSA算法
使用65000位的密钥。在加密 时使用一个公钥，但需要一个 私钥才能进行解密。
非对称密码体制
精品课件-应用密码学-9-非对称密码

精品课件-应用密码学-9-非对称密码

设明文m=19，则由加密过程得密文为 c≡195 mod 119≡2476099 mod 119≡66; 解密过程为 m ≡ 6677mod 119≡19.
29 29
RSA算法模幂运算问题
RSA中的计算问题 1. RSA的加密与解密过程
RSA的加密、解密过程都为求一个整数的整数次幂， 再取模。如果按其含义直接计算，则中间结果非常大，有可 能超出计算机所允许的整数取值范围。如上例中解密运算6677 mod 119，先求6677再取模，则中间结果就已远远超出了计算 机允许的整数取值范围。而用模运算的性质： (a×b) mod n=[(a mod n)×(b mod n)] mod n 就可减小中间结果。
即mkφ(n)+1≡m mod n，所以cd mod n≡m.
19 19
RSA保密通信示意图
20
欧拉(Euler)函数 设 (m)为小于或等于m且与m互素的正整数个数，称 (m)为欧拉(Euler)函数。 例如， (3)＝2， (5)＝4， (8)＝4。 显然，当p为素数时， (p)＝p－1。
21
证明RSA算法中解密过程的正确性. 证明： 由加密过程知c≡me mod n，所以 cd mod n≡med mod n≡m1 mod φ(n) mod n mod n
≡mkφ(n)+1
17 17
RSA算法
下面分两种情况： ① m与n互素，则由Euler定理得 mφ(n)≡1 mod n,mkφ(n)≡1 mod n,mkφ(n)+1≡m mod n 即cd mod n≡m。 ② gcd(m,n)≠1，先看gcd(m,n)=1的含义，由于n=pq，所以 gcd(m,n)=1意味着m不是p的倍数也不是q的倍数。 因此gcd(m,n)≠1意味着m是p的倍数或q的倍数，不妨设m=tp， 其中t为一正整数。
非对称密码体制课件

非对称密码体制课件

f(x) = ax。式中，xGF(p)，x为满足0 x<p－1的整数，其逆运算是 GF(p)中定义的对数运算，即 x=logay (0 x<p－1)
• 由x求y：即使当p很大，也不难实现。为方便计算令a=2。例如 p=2100时，需作100乘法。利用高速计算机由x计算ax可在0.1毫秒 内完成。
• 从ax计算x：当p=2100时，以平均速度的计算机进行计算需时约 1010.7秒(1年=107.5秒，故约为1600年！其中假定存储量的要求能 够满足)。
• 双方事先约定：用户之间自己秘密会面(第一次远距离通信如何办？)
2020/11/18
非对称密码体制
3
非对称密码基本概念：非对称密码的提出
• 对称密码的局限性 • 密钥管理的困难性问题 • 陌生人间的保密通信问题 • 数字签名问题
非对称密码(1976年由W. Diffie和M. Hellman提出)与对称密码的几点 区别：
一个可逆函数f：AB，若它满足：
• 对所有xA，易于计算f(x)；
• 对“几乎所有xA”由f(x)求x“极为困难”，以至于实际上不可能 做到，则称f为一单向(One-way)函数。
定义中的“极为困难”是对现有的计算资源和算法而言。
2020/11/18
非对称密码体制
9
非对称密码基本概念：单向函数
例一：令f是在有限域GF(p)中的指数函数，其中p是大素数，即 y =
2020/11/18
非对称密码体制
12
非对称密码体制：Diffie-Hellman密码体制
• Diffie和Hellman在《密码学新方向》一文中给出了非对称密码算法的思想 • 它不是真正意义上的非对称密码实例，仅仅是一个单向函数； • 算法的目的是使得两个用户安全地交换一个会话密钥。
非对称密码体制ppt课件

非对称密码体制ppt课件


病原体侵入机体，消弱机体防御机能 ，破坏 机体内 环境的 相对稳 定性， 且在一 定部位 生长繁 殖，引 起不同 程度的 病理生 理过程
小结
非对称密码体制 公开密钥加密系统基本原理如图所示。
公开密钥加密系统的优势是具有保密功能和鉴别功能。 公钥体制的主要特点：将加密和解密能力分开，实现多用户加 密的信息只能由一个用户解读，或一个用户加密的信息可由多用户 解读。
务，如：与哈希函数联合运用可生成数字签 名，可用于安全伪随机数发生器的构造，零 知识的证明等。
病原体侵入机体，消弱机体防御机能 ，破坏 机体内 环境的 相对稳 定性， 且在一 定部位 生长繁 殖，引 起不同 程度的 病理生 理过程
实例：使用加密软件PGP
• 软件介绍：PGP是全球著名的、在信息安 全传输领域首选的加密软件，其技术特性 是了非对称的“公钥”和“私钥”加密体 系，创造性地把RSA公钥体系和传统的加 密体系结合起来，是目前最难破译的密码 体系之一。
• Alice拥有Joy、Mike、Bob和Ted四个人的公钥。 当Alice采用Bob的公钥对明文进行加密，然后把 密文进行传输。当Bob收到后，应用Bob的私钥进 行解密，得到原始明文。即使在传输过程中，被 其他人得到密文，由于他们不拥有Bob的私钥， 所以不能进行解密，不能得到原始明文。这就是 公钥密码体制的加密过程。
病原体侵入机体，消弱机体防御机能 ，破坏 机体内 环境的 相对稳 定性， 且在一 定部位 生长繁 殖，引 起不同 程度的 病理生 理过程
实例：使用加密软件PGP
• 操作步骤：
– （1）安装软件； – （2）汉化软件； – （3）注册软件； – （4）创建和设置初始用户； – （5）导出并分发公钥； – （6）导入并设置其他人的公钥； – （7）使用公钥加密文件； – （8）将加密文件发送给对方； – （9）使用私钥进行解密。
《非对称加密PKI》课件

《非对称加密PKI》课件


非对称加密的原理
密钥对的生成和使用
理解非对称加密的密钥对的生成和使用方法。
数字签名的作用和过程
深入了解数字签名在数字安全中的作用和运作过 程。
PKI的应用场景
1 网络安全中的应用
探索PKI在互联网和企业网络安全中的广泛应用。
2 数字证书的使用和管理
了解数字证书在PKI中的重要作用和管理方法。
PKI的优势和挑战
《非对称加密PKI》PPT课 件
非对称加密PKI是一种关键的数字安全技术。本课件将介绍PKI的定义、作用， 非对称加密原理，应用场景，优势和挑战，趋势，以及一些成功的案例分析。
PKI的介绍
定义和作用
了解PKI的定义和PKI在保护网络安全中的作用。
基本概念和原理
掌握PKI的基本概念和基于非对称加密的原理。
高安全性和信任度
PKI提供高度安全的保护，并建立起数字信任体 系。
实施和维护的困难和成本
了解PKI实施和维护可能面临的挑战和成本。
PKI的发展趋势
1
新的技术和方法的出现
探索PKI领域中新兴的技术和方法，如区块链和量子加密。
2
对数字安全的影响和前景
分析PKI对于数字安全的未来发展和影响。
PKI的案例分析
互联网银行
介绍互联网银行如何成功应用PKI技术保护用户数 据和交易安全。
安全电子邮件
探索PKI如何实现电子邮件的安全传输和身份验证。
总结
通过本课件，您了解了非对称加密PKI的基本原理、应用场景和发展趋势。希 望这对于提升您的数字安全认识和能力有所帮助。
பைடு நூலகம்
4第四讲 非对称密码体制

4第四讲 非对称密码体制


14
四、若干数论基础
原根（primitive root) 离散对数方法基于原根概念 素数p的原根定义：
若a是素数p的原根，0<a<p，当k=1，2，┈，p-1时，分别计算 a k mod p ，可以使1，2， ┈ ，p-1 中的每一种状态都出现一 次。
15
四、若干数论基础
离散对数
对任意的整数b和素数p原根a ，我们可以找到唯一的指数x满足
(The Discrete Logarithm Problem, ElGamal体制）
椭圆曲线上的离散对数问题
（The Elliptic Curve Discrete Logarithm Problem,类比的 ElGamal体制）
10
四、若干数论基础
设a、b为整数，且不全为0，
则gcd(a,b)表示a和b的最大公因子。 如果gcd(a,b)=1，称a和b互为素数（互素）。
A用其私钥加密，得到数字签名，然后，再用B的公钥加密
KU b 提供保密性 KRa 提供鉴别
9
三、公开密钥密码体制
公钥算法的安全性完全建立在计算复杂性理论基础上，或者 说建立在对一个特定的数学难题求解的困难上（NP问题）。
背包问题 又称子集合问题（subsetsum)，属于NP问题。 大整数分解问题 （The Integer Factorization Problem, RSA体制） 离散对数问题 有限域的乘法群上的离散对数问题
− 不能用于交换任意信息 − 允许两个用户可以安全地建立一个秘密信息，用于后续的通讯过程 − 该秘密信息仅为两个参与者知道 • 算法的安全性依赖于有限域（素域FP ）上计算离散对数的难度。即对任意 x x 正整数x，计算 g 是容易的；但是，已知g和y求x，使y= g ，在计算上几 乎不可能的 • 在美国的专利1997年4月29日到期
精品课件-应用密码学-第5章 非对称密码(3)

精品课件-应用密码学-第5章 非对称密码(3)

2020/11/19
2020/11/19
15
1155
图5-1 y2≡x3+x+6所表示的曲线 图5-4 y2≡x3+x+6 (mod 11)所表示的曲线
通过比较y2≡x3+x+6在平面的曲线（见图5-1所示）和y2≡x3+x+6 ( mod 11) 在平面上的点（如图5-4所示），直观感觉没有太多的联系。
P +Q+ R1=O。则P+Q =- R1=R，如图5-2。
2020/11/19
2020/11/219020/11/
图5-2 R=P+Q示意图 2020/11/19
8
8 88
点P的倍点定义为：过P点做椭圆曲线的切线，设与椭圆曲线交于R1, 则 P+P+ R1=O, 故2P=- R1=R。如图5-3。
2020/11/19
5
5 55
本章的介绍以第一种椭圆曲线为主，如图5-1是y2≡x3+x+6所表示的曲线，该图 可以用matlab实现。显然该曲线关于x轴对称。
图5-1 y2≡x3+x+6所表示的 曲线
2020/11/19
2020/11/219020/11/
2020/11/19
6
6 66
2．椭圆曲线的加法
2020/11/19
2020/11/19
2020/11/19
20
2200
- ④ 计算点:(x1,y1)=kP - ⑤ 计算点:(x2,y2)=kQ，如果x2=0，则返回第③步 - ⑥ 计算:c=mx2 - ⑦ 传送加密数据(x1,y1,c)给B
（4）解密过程
当实体B解密从A收到的密文(x1,y1,c)时，执行步骤：
应用密码学第5章非对称密码体制

应用密码学第5章非对称密码体制


第5章 非对称密码体制
例5－4 此例为判定合数为素数的例子，此处以n=25，
a=7为例。 取n=25，25-1=23*3，即s=3，t=3。 由Miller-Rabin概率检测算法，得 a=73≡18(mod 25)，i=0，b2=182≡-1(mod 25) 输出：n是素数。 实际上，25是合数。这时可以通过另选择一个a(1<a<n1)，(n，a)=1，如a=2，再次运行算法。
x b (modm ) 2 2 ... x bn (modmn )
第5章 非对称密码体制
的解为：
’ x≡M1M1
b1+
’ M2M2
b2+…+
’ MnMn
bn(modm)
对该定理的理解， 需要注意的是，m=m1m2…mn=miMi， 故 Mi=m/mi。 m1, m2, …,mn 是两两互素的正整数， 故 （Mi, mi） =1, 通过 MiMi’≡1modmi 计算的逆元一定存在。
为在没有共享密钥前，双方只能用明文的方式进行通信，显 然是不安全的；第二种方式的时间需求比较大；第一种方式 从时间和代价上来看，都难以符合需要。在非对称密码体制 产生前，用得较多的解决办法就是第二种方式，但效率是比 较低的。那么如何才能有效地解决这个问题，以用较小的代 价、较高的效率实现通信双方的密钥传递呢？正是由于这个 需求，促使了非对称密码体制的产生。
m＝2310，M1＝462，M2＝385，M3＝330，M4＝210
利用辗转相除法求得 M1’＝－2，M2’＝1，M 3’＝1，M 4’＝1。 所以，x≡1·(－2)· 462＋5· 1· 385＋ 4· 1· 330＋10·1·210≡4421≡2111(mod 2310)
非对称密码体制

非对称密码体制


非对称密码体制
非对称密码体制的基本概念 非对称密码体制的原理 RSA算法 RSA算法中的计算问题 RSA算法的安全性 非对称密码体制的应用
非对称密码体制的基本概念
非对称密码（公钥密码）与所有以前的密码方法的不同点
基于的基本思想不同 密钥的使用方式不同
公钥密码算法的密钥具有如下特点
是加密密钥与解密密钥是本质上不同的 是大多数公钥密码算法的加密密钥和解密密钥具有互换的性质，即两者是相对的
网络信息安全技术
非对称密码体制
非对称密码体制（Asymmetric CryptoSystem），也称为公钥密码体制（Public Key Cryptosystem），是现代密码学的重要组成部 分。公钥密码的思想在1976年由Diffie和Hellman在 其《密码学新方向》一文中提出。Rivest、Shamir 和Adleman在1978年提出了首个非对称密码体制， 即著名的RSA公钥密码体制。非对称密码体制的发明 是现代密码的具有里程碑意义的重要事件，它的出现 标志着现代密码学的创立。
可以通过加密算法生成密文：
C EPKB (M )
接收方B使用私有密钥容易通过解密算法对密文进行解密，以恢复原来的明文
从公开密钥PKB推出私有密钥SKB，在计算上是不可行的
非对称密码体制的原理
定义 单向陷门函数满足下列条件的函数f:D→V
1）对于任意给定的x∈D，计算y=f(x)是容易的。 2）对于几乎所有任意给定y∈V，计算x∈D使得y=f(x)，
RSA算法中的计算问题
即计算(m)cmod N是RSA非对称密码 体制中的主要运算，其计算可以由 c-1次的模乘来实现，然而当比较
(m)c mod N 的有大效时计，算这问不题是一个好的算法，因为

Lecture05非对称密码体制


62，93，81，88，102，37
加密
明文消息m=011000110101101110 分组m=011000 110101 101110
011000对应93+81=174 110101对应62+93+88+37=280 101110对应62+81+88+102=333
密文为：174 280 333
对公钥密码体制的要求
（1）参与方B容易通过计算产生一对密钥
（公开密钥KUb和私有密钥KRb） （2）对于发送方A，通过计算产生对应的密文：C＝EKUb（M） （3）接收方B使用私有密钥解密所得的密文以便恢复原来的报
文：M＝DKRb（C）＝DKRb（EKUb（M）） （4）敌对方即使知道公开密钥KUb，要确定私有密钥KRb在计
公开密钥密码系统的分析方法
强行攻击。 公开密钥算法本身可能被攻破。 可能报文攻击(对报文本身的强行攻击)。
公钥密码系统的应用类型
加密/解密 数字签名 会话密钥交换
背包问题用于公钥密码学
做法：明文为X，S为密文 奥妙在于有两类背包，一类可以在线性时间
内求解，另一类则不能 把易解的背包问题修改成难解的背包问题
如何计算ab mod n？
要点1：(a x b) mod n = [(a mod n) x (b mod n)] mod n] 要点2：a16=aaaaaaaaaaaaaaaa
=a2, a4,a8, a16
更一般性的问题：am
k
m的二进制表示为bkbk-1…b0, 则 m bi 2i
i0
计算am mod n
由私人密钥产生公开密钥 设私人密钥为（2，3，6，13，27，52），其中 w=31,m=105；那么一般的包序列： 2*31 mod 105=62 3*31 mod 105=93 6*31 mod 105=81 13*31 mod 105=88 27*31 mod 105=102 52*31 mod 105=37 公有密钥为（62，93，81，88，102，37）

非对称加密与认证PPT课件

为A。
2020/10/13
2
谢谢您的指导
THANK YOU FOR YOUR GUIDANCE.
感谢阅读！为了方便学习和使用，本文档的内容可以在下载后随意修改，调整和打印。欢迎下载！
汇报人：XXXX 日期：20XX年XX月XX日
3
加 密/解 密 操 作
a 网络中的每个系统都产生一对密钥（公钥和私钥） b 每个系统公布自己的公钥 c 当A要发送报文给BB的公钥加密这个报文 d B收到报文后就用自己的私钥解密报文，由于其他人没
有B的私钥，所以就算截获报文也无法解密。
2020/10/13
1
认证操作
a 网络中的每个系统都产生一对密钥（公钥和私钥） b 每个系统公布自己的公钥 c 当A要向B认证自己时，就用A的私钥加密这个报文 d B收到报文后就用A的公钥解密报文，由于其他人没

密码学6非对称密码体制课件

φ(pq)=φ(p)φ(q)=(p-1) (q-1) 例： φ(15)=φ(3)φ(5)=2*4=8(1,2,4,7,8,11,13,14)
• 当e与m互素，则存在正整数d，使得
ed=1 (mod m) 称d是e关于模m的乘法逆元（简称“模 乘逆元”或“模逆元”），记作e-1 例如：设m=13，
则5*8=40=3*13+1=1 (mod 13) 故 5-1=8 • 欧拉定理
6.1 概述
6.1.1 对称密码体制的缺陷
• 密钥的安全传递比较困难
• n个用户多点通信所需密钥数为n(n-1)/2个
• 难以提供对主动攻击的抗击
6.1.2 公钥（非对称）密码体制的基本思想
Whitfield Diffie和Martin Hellman在1976年 首先提出：用公开的密钥（公钥）加密，用与之 对应的不公开的密钥（私钥）解密。
（将一个充分大的正整数分解成两个 素数之积几乎是不可能的） 1. 数学基础是著名的欧拉(Euler)数论
6.3.2 RSA密码体制的创建 • 选择两个充分大的不同的素数p和q • 计算积n=pq及其欧拉数φ(n)=(p-1)(q-1) • 选择一个介于1到φ(n)之间且与φ(n)互素的正整 数e 即1<e<φ(n)且GCD(e,φ(n))=1 • 求出d=e-1 (mod φ(n) ) 即e d=1 (mod φ(n) )
公钥密码体制提出的标志性文献──密码学 的新方向：
W.Diffie and , New Directions in Cryptography, IEEE Transaction on Information Theory, V.IT22.No.6, Nov 1976, PP.644-654
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

• 解决了对称密码的诸多局限性
2020/11/18
非对称密码体制
4
非对称密码基本概念：非对称密码体制
明文
加密器 EK
PK
密钥产生器
密文
解密器 DK
SK
明文
• 密钥—(PK, SK) • PK：俗称公钥(Public Key)，通常公钥是公开的，可以被任何实 体通过有效渠道获取； • SK：俗称私钥(Secret Key)，通常私钥是保密的，不能被任何实 体通过非法渠道获取；
2020/11/18
非对称密码体制
3
非对称密码基本概念：非对称密码的提出
• 对称密码的局限性 • 密钥管理的困难性问题 • 陌生人间的保密通信问题 • 数字签名问题
非对称密码(1976年由W. Diffie和M. Hellman提出)与对称密码的几点 区别：
• 双钥——双钥密码、公钥密码
• 基于数学函数，而非替换和换位
2020/11/18
非对称密码体制
6
非对称密码基本概念：非对称密码的算法组成
密钥生成KG( ) • 根据输入的安全参数 ，输出公钥和私钥对(PK, SK)
• 加密E( ) • 根据输入的公钥和消息，输出密文。
• 解密D( ) • 根据输入的解密私钥和密文，算法输出消息或输出表示密文不合法的特殊符号“?”
明文
加密器 EK
K
密文
解密器 DK
K
明文
密钥产生器
• 密钥管理：若N个人相互保密通信，每人必须拥有(N-1)个私钥，N很 大时，需要保存的私钥很多。如何解决？
• 可信中心分发：共需要发N*(N-1)/2个私钥：例如N =1000时, 999 *1000/2 = 499500
• 双方事先约定：用户之间自己秘密会面(第一次远距离通信如何办？)
两个难题 • 陷门函数其实就不是单向函数，因为单向函数是在任何条件下求 逆都是困难的；
• 陷门可能不止一个，通过试验,一个陷门就可容易地找到逆。如 果陷门信息的保密性不强，求逆也就不难。
2020/11/18
非对称密码体制
11
非对称密码体制组成
• 非对称密码体制的基本概念 • Diffie-Hellman密码体制 • 背包密码体制 • RSA密码体制 • Elgamal密码体制 • 椭圆曲线密码体制
2020/11/18
非对称密码体制
13
Diffie-Hellman密码体制：密钥交换系统工作原理
发送者
接收者的公 钥加密
加密
接收者
接收者的私 钥解密
会话密钥交换阶段 解密
2020/11/18
保密信息交换阶段
非对称密码体制
14
Diffie-Hellman密码体制：本原元和离散对数
• 本原元：对于一个素数q • 如果数值amodq, a2modq,…,aq-1modq是各不相同的整数； • 并且以某种排列方式组成了从1到q-1的所有整数； 则称整数a是素数q的一个本原元。
f(x) = ax。式中，xGF(p)，x为满足0 x<p－1的整数，其逆运算是 GF(p)中定义的对数运算，即 x=logay (0 x<p－1)
• 由x求y：即使当p很大，也不难实现。为方便计算令a=2。例如 p=2100时，需作100乘法。利用高速计算机由x计算ax可在0.1毫秒 内完成。
• 从ax计算x：当p=2100时，以平均速度的计算机进行计算需时约 1010.7秒(1年=107.5秒，故约为1600年！其中假定存储量的要求能 够满足)。
一个可逆函数f：AB，若它满足：
• 对所有xA，易于计算f(x)；
• 对“几乎所有xA”由f(x)求x“极为困难”，以至于实际上不可能 做到，则称f为一单向(One-way)函数。
定义中的“极为困难”是对现有的计算资源和算法而言。
2020/11/18
非对称密码体制
9
非对称密码基本概念：单向函数
例一：令f是在有限域GF(p)中的指数函数，其中p是大素数，即 y =
2020/11/18
非对称密码体制
7
非对称密码基本概念：非对称密码的原理
• 非对称密码体制：加密密钥与解密密钥不同
明文
加器
解密器 DK
明文
SK
• 非对称密码、认证系统的的安全性主要取决于构造非对称算法所依赖的数学问题。要求加 密函数具有单向性，即求逆的困难性。因此，设计双钥体制的关键是先要寻求一个合适的 单向函数。
2020/11/18
非对称密码体制
10
非对称密码基本概念：单向陷门函数
• 满足下列条件的函数f称为单向陷门函数： • 给定x，计算y = f(x)是容易的； • 给定y，计算x使y = f(x)是困难的； • 存在z，已知z时, 对给定的任何y，若相应的x存在，则计算x使y = f(x)是容易的。
2020/11/18
非对称密码体制
5
非对称密码基本概念：设计要求
• 参与方B容易通过计算产生一对密钥； • 在知道公开密钥和待加密消息的情况下，发送方A容易产生密文； • 接受方B使用私有密钥容易通过计算解密所得密文，以便恢复原来的
消息； • 敌手在知道公开密钥的情况下，确定私有密钥计算上不可行； • 敌手在知道公开密钥和密文的情况下，恢复消息计算上不可行； • 两个密钥中的任何一个可以用来加密，对应的另一个用来解密。
2020/11/18
非对称密码体制
8
非对称密码基本概念：单向函数
• 令函数f是集A到集B的映射，以f：AB表示。若对任意x1x2，x1,
x2A，有f(x1)f(x2)，则称f为单射，或1-1映射，或可逆的函数。 • f 为 可 逆 的 充 要 条 件 是 ： 存 在 函 数 g:BA ， 使 对 任 意 xA 有 g[f(x)]=x。
非对称密码体制
2020/11/18
非对称密码体制
1
非对称密码体制组成
• 非对称密码体制的基本概念 • Diffie-Hellman密码体制 • 背包密码体制 • RSA密码体制 • Elgamal密码体制 • 椭圆曲线密码体制
2020/11/18
非对称密码体制
2
非对称密码基本概念：对称密码面临的困难
2020/11/18
非对称密码体制
12
非对称密码体制：Diffie-Hellman密码体制
• Diffie和Hellman在《密码学新方向》一文中给出了非对称密码算法的思想 • 它不是真正意义上的非对称密码实例，仅仅是一个单向函数； • 算法的目的是使得两个用户安全地交换一个会话密钥。
• 密钥交换(秘密共享) • 发送方和接受方基于公钥密码体制交换会话密钥； • 会话密钥采用对称加密体制加密需要保密传输的消息。