第五章 公钥密码
- 格式：doc
- 大小：1.84 MB
- 文档页数：43
密码学教案 第五章 公钥密码 第五章 公钥密码
5.1概述 一. 传统密码不适合计算机网络时代 保密通信进入计算机网络时代，传统密码便逐渐暴露出其固有弱点。 [1] 传统密码要求通信双方利用安全信道进行密钥K的预先通信，在实际应用中，这可能是非常困难的。
[2] 使用传统密码体制进行秘密通信，要求不同用户间应约定不同的密钥。若网络上有n个用户，则需要2nC个密钥。
2)1(2nnCn
如果n＝1000，则50000021000C。这么多密钥的管理和必须的更换都
将是十分繁重的工程。
[3] 每个用户必须记下与其他n-1个用户通信所用的密钥，由于数量巨大，只能记录在本上或存储在计算机内存或外存上，这本身就是极不安全的。
鉴于传统密码在密钥分配与管理上的困难等原因，Diffie和Hellman提出了公钥密码体制的思想。
二. 公钥密码体制
公钥密码体制将加密密钥与解密密钥分开，并将加密密钥公开，解密密钥保密。这样，每个用户拥有两个密钥：公开钥（公钥）和秘密钥（私钥），所有公开钥均被记录在类似电话号码簿的密码本中。 公钥密码思想：每个用户有一个加密用的密钥ke，还有一个解密用的密
钥kd，将ke公开，kd保密，而且的公开ke不至于妨碍kd的安全。可将各用户的ke集中成公钥文件，像电话本一样公开发给所有用户。 若B欲与A保密通信，查公钥文件得A的加密用公钥ke
(A)
，用之加密得
密文 )()(mcAkeE 密码学教案 第五章 公钥密码 将c寄给A，A用只有他自己才掌握的解密密钥kd(A) 解密恢复明文m )()(cmAkdD
任何第三者截获密文c后，由于不掌握解密密钥kd(A)，无法求出明文m。 公钥密码体制的安全性体现在：即从已知的公开钥、加密算法与在信道上截获的密文不能求出明文或秘密钥。
由于ke(A) ≠ kd
(A)
，故公钥密码也称为―非对称密码‖；与之相对，传统密码
因通信双方用的密钥相同，被称为―对称密码‖。
可以毫不夸张的说―没有公钥密码，就没有近代密码学‖。 三. 公钥密码体制原理
公钥密码体制原理如图5.1所示。其中加、解密变换EB、DB满足如下三
个条件：
[1] DB是EB的逆变换，即Mm（明文空间），均有
mmcBBB)()(EDD
[2] 在已知B的公开钥与秘密钥条件下，EB与DB均是多项式时间的确定
性算法。 [3] 对Mm，找到算法BD，使得mmBB)(ED是非常困难的。所谓―非常困难‖是指在现有的资源与算法下寻找BD是不现实的。
用户A加密解密用户B
密钥本分析员明文m密文c=EB(m)DB(c)=m
EB
图5.1 公钥密码体制框图 结论：公钥密码体制永远不能提供无条件的安全性。
四. 陷门单向函数 1. 单向特性 某种函数其计算容易，但求逆困难的特性称为单向特性。 如，B方公开密码学教案 第五章 公钥密码 的加密变换BE是很容易计算的，但计算BD满足mcB)(D（即解密）将
是困难的（对除了B外的其他人而言）。
2. 单向函数 一般来说，当一个函数f是一对一的，且对任意x容易计算)(xf，但计算1f非常困难，即已知y，找出x满足yxf)(非常困难，这种函数f称
为单向函数。 在密码体制中，单向函数起着非常重要的作用。 例 假设n是两个大的素数p和q的乘积，e是一个正整数，定义
)(mod)(nxxfe 此时的)(xf即是一个单向函数。事实上，它是RSA加密函数。
3. 陷门 陷门即是一些秘密信息的集成。 单向函数不是构造公钥密码体制的充要条件。从B方观点看，如果他想解密，可以从各种有效途径中得到报文。即B拥有一个陷门，使得求BE
的逆容易进行，也就是说B能够有效地解密，因为他知道有关的一些额外的秘密知识。
4. 陷门单向函数 如果一个函数是单向函数，但在具有某种陷门知识时很容易计算逆，则称这样的函数为陷门单向函数。
5.2计算复杂性理论
计算复杂性理论是分析密码技术的计算要求和研究破译密码固有难度的基础。 5.2.1 算法复杂性 算法的计算复杂性是用该算法所需的计算时间(T )和存储空间(S )要求来度量的。 当给定一个特定的求解问题的算法后，执行这个算法的计算时间要求密码学教案 第五章 公钥密码 和存储空间要求也随之确定。通常，我们不是以一个具体的计算机来
做这项实验，而是把上述概念：计算时间和存储空间进行抽象，以该实例所需输入数据的长度n的函数 f (n)来表示，则n越大，所需花费的时间代价和空间代价f (n)也越大。 f (n)通常表示为形如O [g(n)]的―量级‖函数，并称为―大O ‖表示法。 f (n)= O [g(n)]表示存在满足下面要求的常数c和n0
)()(ngcnf，当0nn
例 设f (n)=8n+10，那么f (n)= O (n)，因为 8n+10≤9n，当n≥10， 即g(n) =n，c=9，n0=10。
例 若f (n)=at nt + at -1 nt -1 +…+a1 n + a0，式中t为常数。
则f (n)= O (nt )，即忽略了全部常数和低阶项。
用―量级‖函数度量一种算法的时间和空间要求的优点在于： [1] 该函数与所用的体制无关，因而不必知道具体系统中不同指令的准确的定时关系 和代表不同类型数据所用的比特数。 [2] 该函数还能清楚地表示出算法的时间和空间要求是如何随输入数据的长度增长而 增长的规律。 例 若T=O(n2
)，则输入数据长度增加一倍，就会使算法运行时间增加4倍。
若T=O(2n )，则输入数据长度增加一倍，就会使算法运行时间增加2倍。
通常，算法可按其时间和空间的复杂性进行如下分类： [1] 常数级：O(1)，即算法的复杂性不依赖于n。 [2] 线性的：O(n)，即算法的复杂性随n线性增长。 [3] 二次方的：O(n2 )，即算法的复杂性随n的二次方增长。 [4] 三次方的：O(n3 )，即算法的复杂性随n的三次方增长。 [5] 指数级：O(t f (n) ) ，这里t是常数，f (n)是n的函数。 [2]~[4] 都是多项式，它们的复杂性是O(nt )，这里t是常数。 包含有一个多项式的时间复杂性的算法族被称为多项式时间算法。 密码学教案 第五章 公钥密码 任何密码算法的一个基本要求是：加、解密只需要多项式时间的代价，
破译需要指数时间代价。 当n增长时，算法的时间复杂性能够在现实算法是否实际可行方面有巨大差别，见表5.1。 表5.1 不同运算族运行时间 类型 复杂性 运算次数 运算时间 常数的 线性的 二次方的 三次方的 指数的 O(1) O(n) O(n2 ) O(n3 ) O(t f (n) ) 1 106 1012 1018 10301030 1微秒 1秒 11.6天 32000年 3.1×10301016年
所以，对一个密码体制的强力攻击的时间复杂性与可能的密钥总数成正比，它是密钥长度的指数函数。 如果n是密钥长度，强力攻击的时间复杂性是O(2n )。对DES，若
用112比特密钥代替原有的56比特密钥，则强力攻击的时间复杂性由256（2285年，假定106次/秒）提高为2112（1020年，假定106次/秒）。
5.2.2 问题复杂性和NP完全问题
1. P－问题 利用多项式的概念可以把问题进行分类，如果一个问题已经找到了一个多项式算法，就称这个问题为一个P－问题，或者说它属于P类。
2. 确定性与非确定性 若一个算法中每一步计算中，下一步是唯一的，则称该算法是确定性的；若一个算法，在它的某一计算步骤必须从有限个可选项中选出一个作为下一步，则称该算法是非确定性的。 属于P－类的算法都是确定性的，且P－时间是受限的，即执行时间是多项式时间。 密码学教案 第五章 公钥密码 3. NP－问题
NP－问题是指用非确定性算法在多项式时间内可以解决的问题，即不确定性多项式类。也就是说：对于一个问题的任何实例，人们对所给出的任意一个猜测，都能在多项式时间里判断这个猜测是否正确。 若用P、NP分别表示P问题、NP问题，则显然有P ≤ NP。 对于每个NP问题，究竟有无确定性算法在多项式时间内求解？是否有P = NP？NP问题看上去比P问题困难得多，但至今尚未证明：P ≠ NP。这是计算复杂性理论中的著名难题。
2006.10.26（星期四）第十三次课截止于此 4. 归约
设x1和x2是两个问题，若x1可用多项式时间的确定性算法转化为x2，而
x2的解又可用多项式时间的确定性算法转化为x1，则称x1可归约为x2，记为
x1∝x2。
5. NP完全问题 设x是一个给定的问题，如果对NPx，均有xx，则称x是困难问题，且NPx，则x称为NP完全问题或NPC问题。 NPC问题是NP问题中最困难的问题。 当前已有数百个问题证明是NP完全问题。NP完全问题的发现为人们提供了一种判定一个问题是―难问题‖的标准。 目前一般认为，NP完全问题不可能找到多项式算法。
结论：在现代密码中，一个密码系统的破译常常可归结为求解某个数学问题，数学问题的算法求解复杂性可通过计算复杂性理论来描述，因此
[1] 计算复杂性理论为破译密码的计算复杂度提供了实际的度量方法。 [2] 计算复杂性理论中的一些典型的数学问题给人们提供了设计实用安全的高强度密码系统的基础。 例 基于NPC类中的背包问题设计了背包公开钥密码系统；
基于NP问题的大数因子分解问题设计了RSA公开钥密码系统。
