密码技术基础

1、计算机网络安全基础2.3 非对称密码公用密钥私有密钥密码学又称公用密钥密码。它通过使用两个数字互补密钥，绕过了排列共享的问题。这两个密钥，一个是尽人皆知的，而另一个只有拥有者才知道，尽人皆知的密钥叫做公用密钥，而只有密钥拥有者才知道的密钥叫做私有密钥，或称专用密钥。这两种密钥合在一起称为密钥对。公用密钥可以解决安全分配密钥问题，因为它不需要与保密密钥通信，所需传输的只有公用密钥。这种公用密钥不需要保密，但对保证其真实性和完整性却非常重要。如果某一信息用公用密钥加密，则必须用私有密钥解密，这就是实现保密的方法。如果某一信息用私有密钥加密，那么，它必须用公用密钥解密。这就是实现验证的方法。 计算机

2、网络安全基础2.3 非对称密码公钥密码技术示意图公钥密码技术示意图密钥本密钥本加密加密C=E(eB ,m)解密解密m=D(dB ,m)公钥公钥eBmm密文密文用户用户A用户用户BceB :用户用户B的公开密钥的公开密钥(公钥公钥) dB :用户用户B的秘密密钥的秘密密钥(私钥私钥)计算机网络安全基础2.3 非对称密码2. 公钥密码体制的原理公钥密码体制的原理 (1) 单向函数单向函数单向函数单向函数：一个可逆函数：一个可逆函数y=f(x)，如果对于给定所如果对于给定所有有x A，能方便地计算出能方便地计算出f(x)；对于给定所有对于给定所有y，求求x是困是困难的，以至于实际上是做不到的难的，以

3、至于实际上是做不到的。例：例： 有限域有限域GF(p)上，上，y=f(x)=bx ， x GF(p) 逆运算：逆运算： x=logbN计算机网络安全基础2.3 非对称密码 (2) 构造公钥密码常用的单向函数构造公钥密码常用的单向函数n多项式求根：多项式求根：n y=f(x)=(Xn+an-1Xn-1+a1x+a0) mod pn离散对数离散对数n y=f(x)-ax mod pn逆：逆：x=logby mod pn大整数分解大整数分解1)若已知两个大素数若已知两个大素数p、q，求求n=pXq仅需一次乘法，仅需一次乘法，但已知但已知n求求p、q则是一道难题。则是一道难题。计算机网络安全基础公用密

4、钥系统的最流行的例子是由麻省理工学院的Rom Rivest、Adi Shamir和Len Adleman开发的RSA系统。另一个系统叫做Diffie-Hellman，该系统直接从本身不是密钥的公用“组成部分”中产生共享保密密钥。这两种系统各有优点，互为补充，因而常常组合在一起。2.3 非对称密码计算机网络安全基础RSARSA是在Diffie-Hellman算法问世两年之后，由Rivest、Shamir和Adelman在MIT作出的，并于1978年公布。RSA要求每一个用户拥有自己的一种密钥：（1）公开的加密密钥，用以加密明文；（2）保密的解密密钥，用于解密密文。2.3 非对称密码计算机网络安全

5、基础2.3 非对称密码n欧拉函数： 对于一个正整数n，小于n且和n互质的正整数的个数，记做：(n)。其中(1)被定义为1，但是并没有任何实质的意义。n对于素数p，(p)= p -1. 对于两个素数p、q，n = pq 满足(n) =(p-1)(q-1)n欧拉定理 对于互质的整数a和n，有a(n) 1 mod n计算机网络安全基础2.3 非对称密码RSA参数建立n找素数n选取两个大的随机素数p,qn计算模n和Euler函数(n)nnpqn (n)=(p-1)(q-1)n找ed1 mod (n)n选取数e，用扩展Euclid算法求数dn发布n发布(e,n)，这是公钥kend保密，(d, n)是私钥

6、 kd计算机网络安全基础2.3 非对称密码n加密n明文分组m做为整数须小于nc=me mod nn解密m=cd mod n计算机网络安全基础2.3 非对称密码RSA参数建立n找素数n选取两个大的随机素数p,qn计算模n和Euler函数(n)nnpqn (n)=(p-1)(q-1)n找ed1 mod (n)n选取数e，用扩展Euclid算法求数dn发布n发布(e,n)，这是公钥kend保密，(d, n)是私钥 kd计算机网络安全基础RSA实例n选选p7，q17则则npq119且且(n)(p-1)(q-1)61696n取取e5则则d77 (57738549611 mod 96)n公钥（公钥（5，1

7、19），私钥（），私钥（77，119） n加密加密m19则则cme mod n= 195 mod 119 = 66 mod 119n解密解密c66mcd mod n = 6677mod 11919 mod 119计算机网络安全基础RSA需要考虑的因素n素数素数n必须够大，否则对手可能很快分解必须够大，否则对手可能很快分解nn判定，试除法不可行判定，试除法不可行n判定，采用判定，采用Miller-Rabin概率测试方法概率测试方法n强素数强素数n(p-1)/2和和(q-1)/2应是素数应是素数n选取较小的选取较小的e（较大的（较大的d）ne：3、65537n快速计算快速计算 XY%Z计算机网络安

8、全基础Diffie-Hellman密钥交换算法 Diffie-Hellman密钥交换算法 常用做密钥的分配并满足：k gx mod p（在g自乘幂x后，然后除以p，k为余数）Diffie-Hellman密钥交换算法 计算机网络安全基础如果知道g、x和p，则很容易计算k。但是，如果知道k、g和p，则很难在合理的时间内以类似规模的数计算x。当所有的数都很大时，p是很大的素数。在此情况下，数y叫做公用分量，而x叫做私有分量或专用分量。这些分量本身不是密钥，但是，它们可以用来制作共享保密密钥。Diffie-Hellman密钥交换算法 计算机网络安全基础 Diffie-Hellman体制：确定一个大数p

9、及GF(p)的本原元素a.一用户设为A选择一随机数xA,计算 ： 将yA公开, xA保密.只有x自己掌握，用户B要与A进行保密通信，查得yA，计算他们建的通信密钥：A收到密文后，可以先计算出通信密钥 ：即：A可以查得公开的密钥yB,计算出kAB,然后利用它来解密。公开yA或yB要求xA或xB等价于求离散对数loga(yA)或loga(yB). 计算机网络安全基础 n证明证明KKKYbXa mod qKYaXb mod q (gXb)Xa mod q (gXa)Xb mod q g(XbXa) mod q g(XaXb) mod qn举例举例 q97，g5A选选Xa36，B选选Xb58，则则Ya

10、5369750，Yb5589744交换交换50，44A算算K44369775，B算算K50589775n分析（别人怎么计算分析（别人怎么计算K?）别人看到了别人看到了Ya和和Yb，但需要计算但需要计算Xa或或Xb，即要算离散对数即要算离散对数YagXa mod q，或或YbgXb mod qDiffie-Hellman密钥交换算法 计算机网络安全基础2.4 密钥分配与管理技术密钥分配方案：解决网络环境中需要进行安全通信的密钥分配方案：解决网络环境中需要进行安全通信的实体间建立共享密钥的问题。实体间建立共享密钥的问题。 1. 密钥分配的基本方法：密钥分配的基本方法： （对于通信双方（对于通信双方

11、A和和B）(1)密钥由密钥由A决定，然后通过物理方法安全传递给决定，然后通过物理方法安全传递给B.(2)密钥由可信的第三方密钥由可信的第三方C选取，并通过物理方法安全传选取，并通过物理方法安全传 递给递给A和和B.(3)如果如果A和和B事先已有一密钥，那么其中一方选取新密钥事先已有一密钥，那么其中一方选取新密钥后，用已有的密钥加密新密钥送给另一方。后，用已有的密钥加密新密钥送给另一方。(4)如果如果A和和B都有一个到可信的第三方都有一个到可信的第三方C的保密信道，那的保密信道，那么么C就可以为就可以为A和和B选取密钥后安全地发送给选取密钥后安全地发送给A和和B。(5)如果如果A和和B都在可信的

12、第三方都在可信的第三方C发布自己的公开密钥，发布自己的公开密钥，那么他们用彼此的公开密钥进行保密通信那么他们用彼此的公开密钥进行保密通信。计算机网络安全基础2.4 密钥分配与管理技术2. 对称密码技术的密钥分配方案对称密码技术的密钥分配方案集中式密钥分配方案集中式密钥分配方案由由KDC或一组节点组成的层次结构负责密钥的产生和分或一组节点组成的层次结构负责密钥的产生和分配。配。假定假定A和和B分别与分别与KDC有一个共享密钥有一个共享密钥Ka和和Kb，则则:AKDC: IDA/IDB/N1KDC A : EkaKs/ IDA/IDB/N1/EkbKs/IDAA B : EkbKs/IDAB A

13、: EksN2A B : Eksf(N2)KDCAB12345计算机网络安全基础2.4 密钥分配与管理技术(2) 分布式密钥分配方案分布式密钥分配方案 各节点具有相同的地位，他们之间的密钥分配取决于他各节点具有相同的地位，他们之间的密钥分配取决于他们之间的协商，不受任何其他方限制。们之间的协商，不受任何其他方限制。设设A和和B已共享一主密钥已共享一主密钥MKm，则过程如下：则过程如下：AB: IDA/N1BA : EMKmKs/ IDA/IDB/f(N1)/N2A B : EKsf(N2)AB123计算机网络安全基础2.4 密钥分配与管理技术3. 非对称密码技术的密钥分配方案非对称密码技术的密

14、钥分配方案 在非对称密码体制中，要求私钥只有只有通信一方知道，在非对称密码体制中，要求私钥只有只有通信一方知道，而公钥则是公开的。而公钥则是公开的。(1)公钥的分配公钥的分配公开发布公开发布公用目录公用目录公钥机构公钥机构公钥证书公钥证书计算机网络安全基础2.4 密钥分配与管理技术(1)利用非对称技术分配对称密码技术密钥利用非对称技术分配对称密码技术密钥简单分配简单分配ABPKA/IDAEPKAKs计算机网络安全基础2.4 密钥分配与管理技术具有保密和认证功能的密钥分配具有保密和认证功能的密钥分配 假定假定A和和B已完成了公钥交换，则：已完成了公钥交换，则：ABEPKBN1/IDAEPKBN2

15、EPKAN1/N2EPKAEKAKs计算机网络安全基础2.4.2 密钥管理技术1. 密钥生成密钥生成密钥空间的大小密钥空间的大小密钥长度密钥长度对于公钥密码体制，需要满足一定的数学特征对于公钥密码体制，需要满足一定的数学特征计算机网络安全基础2.4.2 密钥管理技术2. 密钥的使用密钥的使用从存储介质上获得密钥进行加密和解密的技术活从存储介质上获得密钥进行加密和解密的技术活动。动。计算机网络安全基础2.4.2 密钥管理技术3. 密钥的存储密钥的存储保证密钥在存储过程中的机密性、认证性、保证密钥在存储过程中的机密性、认证性、完整性，防止泄露和修改。完整性，防止泄露和修改。计算机网络安全基础2.4.2 密钥管理技术4. 密钥的备份密钥的备份/恢复恢复密钥主管无法提供密钥时读取加密数据。密钥主管无法提供密钥时读取加密数据。计算机网络安全基础2.4.2 密钥管理技术5. 密钥的泄露与撤消密钥的泄露与撤消密钥安全是所有协议、技术、算法安全的基本条件；密钥安全是所有协议、技术、算法安全的基本条件；密钥可能会丢失、被盗、或以其它方式被泄露。密钥可能会丢失、被盗、或以其它方式被泄露。计算机网络安全基础2.4.2 密钥管理技术6. 密钥的有效期密钥的有效期密钥使用时间越长，泄露的机会越大；密钥使用时间越长，泄露的机会越大；如果密钥已泄露，使用越久，损失越大；如果密钥已泄露，使用越