信息系统安全与课件公钥密码学chap

1、 问题的提出问题的提出 问题的提出问题的提出4问题的提出问题的提出9.1.1 公钥密码机制公钥密码机制 公开密钥算法是公开密钥算法是非对称算法非对称算法，即密钥分为公钥和私钥，因，即密钥分为公钥和私钥，因此称此称双密钥体制双密钥体制 双钥体制的公钥可以公开，因此也称双钥体制的公钥可以公开，因此也称公钥算法公钥算法基于数学函数而不是代替和换位，基于数学函数而不是代替和换位，密码学历史上唯一的一密码学历史上唯一的一次真正的革命次真正的革命公钥密码学是公钥密码学是1976年由年由Diffie和和Hellman在其在其“密码学新方密码学新方向向”一文中提出的公钥算法的出现，给密码的发展开辟了一文中提出

2、的公钥算法的出现，给密码的发展开辟了新的方向。公钥算法虽然已经历了新的方向。公钥算法虽然已经历了2020多年的发展，但仍具多年的发展，但仍具有强劲的发展势头，在有强劲的发展势头，在鉴别系统和密钥交换鉴别系统和密钥交换等安全技术领等安全技术领域起着关键的作用域起着关键的作用9.1 公钥密码学及公钥密码体制基本原理公钥密码学及公钥密码体制基本原理从最初一直到现代，几乎所有密码系统都建立在基从最初一直到现代，几乎所有密码系统都建立在基本的本的替代和置换替代和置换工具的基础上。工具的基础上。在用了数千年的本质上可以手算完成的算法之后，在用了数千年的本质上可以手算完成的算法之后，常规的密码学随着常规的密

3、码学随着转轮加密转轮加密/解密机解密机的发展才出现的发展才出现了一个重大进步。了一个重大进步。机电式变码旋转软件使得极其复杂的密码系统被研机电式变码旋转软件使得极其复杂的密码系统被研制出来。有了计算机后，更加复杂的系统被设计出制出来。有了计算机后，更加复杂的系统被设计出来。来。但是不管是转轮机还是后来的但是不管是转轮机还是后来的DES（数据加密标（数据加密标准），虽然代表了重要的进展，却仍然依赖于替代准），虽然代表了重要的进展，却仍然依赖于替代和置换这样的基本工具。和置换这样的基本工具。密码学历史上唯一的一次真正的革命密码学历史上唯一的一次真正的革命7 公钥密码系统可用于以下三个方面：公钥密码

4、系统可用于以下三个方面： (1) 通信保密：此时将公钥作为加密密钥，私钥作通信保密：此时将公钥作为加密密钥，私钥作为解密密钥，通信双方不需要交换密钥就可以实为解密密钥，通信双方不需要交换密钥就可以实现保密通信。现保密通信。 Alice的公钥Joy明文输入 加密算法，如RSA传输密文解密算法明文输出Alice的私钥Bob的公钥环TedAliceMike任何人向Alice发送信息都可以使用同一个密钥(Alice的公钥)加密没有其他人可以得到Alice 的私钥，所以只有Alice可以解密公钥密码体制的加密功能公钥密码体制的加密功能公钥密码体制的加密功能公钥密码体制的加密功能 Bob向向AliceAl

5、ice发消息发消息X， AliceAlice的公钥为的公钥为KUa,私钥为私钥为KRa 加密加密 Y = EKUa(X) 解密解密 X = DKRa(Y) 因为只有因为只有Alice知道知道私钥，所以其，所以其他人都无法解密。他人都无法解密。2022-2-24910(2) (2) 数字签名：将私钥作为加密密钥，公钥作为解数字签名：将私钥作为加密密钥，公钥作为解 密密钥，可实现由一个用户对数据加密而使多个密密钥，可实现由一个用户对数据加密而使多个用户解读。用户解读。Bob的公钥Joy明文输入 加密算法，如RSA传输密文解密算法明文输出Bob的私钥Alice的公钥环TedBobMike公钥密码系统

6、的签名公钥密码系统的签名/认证原理认证原理Bob向向Alice 发送消息发送消息，用，用A的私钥加密（的私钥加密（签名）签名）Alice收到密文后，用收到密文后，用Bob的公钥解密（验的公钥解密（验证）证）公钥密码体制的认证公钥密码体制的认证 Bob向向Alice发送消息发送消息X Bob的公钥为的公钥为KUb，私钥为，私钥为KRb “加密加密”： Y = EKRb(X) （数字签名）（数字签名） “解密解密”： X = DKUb(Y) 因为经过因为经过Bob的秘密钥加密，只有的秘密钥加密，只有Bob才能才能做到。因此做到。因此Y可当做可当做Bob对消息对消息X的数字签的数字签名。名。另一方面

7、，任何人只要得不到另一方面，任何人只要得不到Bob的秘密钥的秘密钥就不能篡改就不能篡改Y，所以以上过程获得了对消息，所以以上过程获得了对消息来源和消息完整性的认证。来源和消息完整性的认证。2022-2-2412图图4-2 公钥密码体制认证框图公钥密码体制认证框图 加密算法解密算法发送者A接收者B密码分析员(窃听者)mAKScAPKASKm密钥源2022-2-2413 在实际应用中，特别是用户数目很多时，以上在实际应用中，特别是用户数目很多时，以上认证方法需要认证方法需要很大的存储空间很大的存储空间，因为每个文件，因为每个文件都必须以明文形式存储以方便实际使用，同时都必须以明文形式存储以方便实际

8、使用，同时还必须存储每个文件被加密后的密文形式即数还必须存储每个文件被加密后的密文形式即数字签字，以便在有争议时用来认证文件的来源字签字，以便在有争议时用来认证文件的来源和内容。和内容。 改进的方法是减小文件的数字签字的大小，即改进的方法是减小文件的数字签字的大小，即先将文件经过一个函数压缩成长度较小的比特先将文件经过一个函数压缩成长度较小的比特串，得到的比特串称为串，得到的比特串称为认证符认证符。 认证符具有这样一个性质：认证符具有这样一个性质： 如果保持认证符如果保持认证符的值不变而修改文件这在计算上是不可行的。的值不变而修改文件这在计算上是不可行的。 用发送者的秘密钥对认证符加密，加密后

9、的结用发送者的秘密钥对认证符加密，加密后的结果为原文件的数字签字。果为原文件的数字签字。2022-2-2414 以上认证过程中，由于消息是由用户自己的秘以上认证过程中，由于消息是由用户自己的秘密钥加密的，所以消息不能被他人篡改，但却密钥加密的，所以消息不能被他人篡改，但却能被他人窃听。这是因为任何人都能用用户的能被他人窃听。这是因为任何人都能用用户的公开钥对消息解密。为了同时提供认证功能和公开钥对消息解密。为了同时提供认证功能和保密性，可使用双重加、解密。保密性，可使用双重加、解密。2022-2-2415图图4.3 公钥密码体制的认证、保密框图公钥密码体制的认证、保密框图2022-2-2416

10、 发方首先用自己的发方首先用自己的私钥私钥SKA对消息对消息m加密，用加密，用于提供于提供数字签名数字签名。再用收方的。再用收方的公钥公钥PKB第第2次次加加密密，表示为，表示为c=EPKBESKAm 解密过程为解密过程为m=DPKADSKBc 即收方先用自己的即收方先用自己的私钥私钥,再用发方的再用发方的公钥公钥对收到对收到的密文两次解密。的密文两次解密。 鉴别保密鉴别保密 :():( )baabKUKRKUKRAB ZEEXB EEZX9.1.2 公钥密码的应用公钥密码的应用加密加密/解密解密数字签名数字签名密码交换密码交换 公钥密钥的应用范围公钥密钥的应用范围加密加密/解密：解密：数字签

11、名数字签名(身份鉴别身份鉴别)密钥交换密钥交换公钥密钥遭受穷举攻击，密码越长越好；但为了加解密，公钥密钥遭受穷举攻击，密码越长越好；但为了加解密，密钥又要足够短；因此公钥密码仅限于密钥管理和签名中密钥又要足够短；因此公钥密码仅限于密钥管理和签名中算法算法加加/解密解密 数字签名数字签名密钥交换密钥交换RSA是是是是是是Diffie-Hellman否否否否是是DSS否否是是否否对公钥密码算法的误解对公钥密码算法的误解 公开密钥算法比对称密钥密码算法更安全？公开密钥算法比对称密钥密码算法更安全？ 任何一种算法都依赖于密钥长度、破译密码的工任何一种算法都依赖于密钥长度、破译密码的工作量，从抗分析角度

12、，没有一方更优越作量，从抗分析角度，没有一方更优越 公开密钥算法使对称密钥成为过时了的技术？公开密钥算法使对称密钥成为过时了的技术？ 公开密钥很慢，只能用在密钥管理和数字签名，公开密钥很慢，只能用在密钥管理和数字签名，对称密钥密码算法将长期存在对称密钥密码算法将长期存在 使用公开密钥加密，密钥分配变得非常简单？使用公开密钥加密，密钥分配变得非常简单？ 事实上的密钥分配既不简单，也不有效事实上的密钥分配既不简单，也不有效5.1.3 公钥密码的要求公钥密码的要求 涉及到各方：发送方、接收方、攻击者涉及到各方：发送方、接收方、攻击者 涉及到数据：公钥、私钥、明文、密文涉及到数据：公钥、私钥、明文、密

13、文 公钥算法的条件：公钥算法的条件： 产生一对密钥是产生一对密钥是计算可行的计算可行的 已知公钥和明文，产生密文是已知公钥和明文，产生密文是计算可行的计算可行的 接收方利用私钥来解密密文是接收方利用私钥来解密密文是计算可行的计算可行的 对于攻击者，利用公钥来推断私钥是对于攻击者，利用公钥来推断私钥是计算不可行的计算不可行的 已知公钥和密文，恢复明文是已知公钥和密文，恢复明文是计算不可行的计算不可行的 (可选可选)加密和解密的顺序可交换加密和解密的顺序可交换Company Logo22 陷门单向函数陷门单向函数公钥密码系统是基于陷门单向函数的概公钥密码系统是基于陷门单向函数的概念。念。 单向函数

14、单向函数是是易于计算但求逆困难易于计算但求逆困难的函数的函数，而，而陷门单向函数陷门单向函数是在不知道陷门信息是在不知道陷门信息情况下求逆困难，而在知道陷门信息时情况下求逆困难，而在知道陷门信息时易于求逆的函数。易于求逆的函数。满足上述条件找到单向陷门函数函数满足上述条件找到单向陷门函数函数 满足下列条件的函数满足下列条件的函数f f： (1) 给定给定x，计算，计算y=f(x)是容易的是容易的 (2) 给定给定y, 计算计算x使使y=f(x)是困难的是困难的 (3) 存在存在z，已知，已知z 时时, 对给定的任何对给定的任何y，若相应的，若相应的x存存 在，则计算在，则计算x使使y=f(x)

15、是容易的是容易的所谓计算所谓计算x= x= f-1(Y)(Y)困难是指计算上相当复杂，已无困难是指计算上相当复杂，已无实际意义实际意义寻找合适的单向陷门函数是公钥密码体制应用的关键单向陷门函数举例：单向陷门函数举例：离散对数离散对数大整数分解大整数分解背包问题背包问题单向陷门函数说明单向陷门函数说明仅满足仅满足(1)、(2)两条的称为两条的称为单向函数单向函数；第；第(3)条称为陷门性，条称为陷门性，z 称为称为陷门信息陷门信息当用陷门函数当用陷门函数f作为加密函数时，可将作为加密函数时，可将f公开，这相当于公开公开，这相当于公开加密密钥，此时加密密钥便称为公钥，记为加密密钥，此时加密密钥便称

16、为公钥，记为Pkf函数的设计者将函数的设计者将陷门信息陷门信息z保密，用作解密密钥，此时保密，用作解密密钥，此时z称为称为秘密钥匙，记为秘密钥匙，记为Sk。由于设计者拥有。由于设计者拥有Sk，他自然可以解出，他自然可以解出x=f-1(y)单向陷门函数的第单向陷门函数的第(2)条性质表明窃听者由截获的密文条性质表明窃听者由截获的密文y=f(x)推测推测x是不可行的是不可行的对称密码对称密码 公钥密码公钥密码一般要求：1、加密解密用相同的密钥和算法、加密解密用相同的密钥和算法2、收发双方必须共享密钥、收发双方必须共享密钥安全性要求：1、密钥必须保密、密钥必须保密2、没有密钥，解密不可行、没有密钥，

17、解密不可行3、知道算法和若干密文不足以确定、知道算法和若干密文不足以确定密钥密钥一般要求：1、加密解密算法相同，但使用不同、加密解密算法相同，但使用不同的密钥的密钥2、发送方拥有加密或解密密钥，而、发送方拥有加密或解密密钥，而接收方拥有另一个密钥接收方拥有另一个密钥安全性要求：1、两个密钥之一必须保密、两个密钥之一必须保密2、无解密密钥，解密不可行、无解密密钥，解密不可行3、知道算法和其中一个密钥以及若、知道算法和其中一个密钥以及若干密文不能确定另一个密钥干密文不能确定另一个密钥9.2 RSA算法算法 RSA算法是算法是1978年由年由R.Rivest, A.Shamir和和L.Adleman

18、提出的一提出的一种用数论构造的公钥密码体制，该体制已得到广泛的应用。种用数论构造的公钥密码体制，该体制已得到广泛的应用。RivestShamirAdleman2002 Turing Award (June03)28RSARSA体制体制 最容易理解和实现的公钥算法最容易理解和实现的公钥算法; ; 经受住了多年深入的攻击经受住了多年深入的攻击; ; 其理论基础是一种特殊的可逆模幂运算，其其理论基础是一种特殊的可逆模幂运算，其安全性基于分解大整数的困难性；安全性基于分解大整数的困难性； RSARSA既可用于加密，又可用于数字签名，已既可用于加密，又可用于数字签名，已得到广泛采用；得到广泛采用； RS

19、ARSA已被许多标准化组织已被许多标准化组织( (如如ISOISO、ITUITU、IETFIETF和和SWIFTSWIFT等等) )接纳；接纳； 目前许多国家标准仍采用目前许多国家标准仍采用RSARSA或它的变型或它的变型 迄今为止理论上最为成熟完善的公钥密码体迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。制，该体制已得到广泛的应用。 大整数分解问题大整数分解问题：将两个整数乘起来是简单的，但：将两个整数乘起来是简单的，但是将一个整数分解为几个整数的乘积是困难的，尤是将一个整数分解为几个整数的乘积是困难的，尤其是当这个数比较大的时候。迄今为止没有有效的其是当这个数比较大的时

20、候。迄今为止没有有效的算法来解决这个问题，甚至我们连这个问题的计算算法来解决这个问题，甚至我们连这个问题的计算复杂度量级是多少都不知道。复杂度量级是多少都不知道。数论基础数论基础 同余同余 给定一个正整数m，如果两个整数a和b满足（a-b）能够整除m，即（a-b）/m得到一个整数，那么就称整数a与b对模m同余，记作ab(mod m)。对模m同余是整数的一个等价关系。数论基础数论基础 每个合数都可以唯一地分解出素数因子每个合数都可以唯一地分解出素数因子6 = 2 3999999 = 333711133727641 = 131121从从2 开始试验每一个小于等于开始试验每一个小于等于27641 的

21、素数。的素数。素数：只能被素数：只能被1和它本身整除的自然数；否则为合数。和它本身整除的自然数；否则为合数。整数整数n的十进制位数的十进制位数 因子分解的运算次数因子分解的运算次数 所需计算时间（每微秒一次）所需计算时间（每微秒一次）501.4x10103.9小时小时759.0 x1012104天天1002.3x101574年年2001.2x10233.8x109年年3001.5x10294.0 x1015年年5001.3x10394.2x1025年年数论基础数论基础数论基础数论基础mmmEuler 函数函数当当m是素数时，小于是素数时，小于m的所有整数均与的所有整数均与m互素，因此互素，因此

22、(m)=m-1对对m=pq, p和和q 是素数，是素数，(m)=(p)(q)=(p-1)(q-1)Euler 函数函数举例举例 设设p=3, q=5, 那么那么 （15）= （3）* * ( (5）=（3-1）* * （5-1） = =8 这这8个模个模15的剩余类是的剩余类是： 8个整数与个整数与15是互素的是互素的 1，2，4，7，8，11，13，14 对对 m = p q , p 和和 q 是 素 数 ，是 素 数 ，(m)=(p)(q)=(p-1)(q-1)例如：例如：20=225，有两个素数，有两个素数2和和5，这样，这样， (20) =20(1-1/2)(1-1/5)=8即即20中

23、有中有8个整数与个整数与20是互素的，即它们没有是互素的，即它们没有2或或5为因子：为因子：1, 3, 7, 9, 11, 13, 17, 19数论基础数论基础数论基础数论基础数论基础数论基础数论基础数论基础扩展的欧几里得算法求逆元扩展的欧几里得算法求逆元79*d mod 3220 = 1 （1）；或者79*d 1mod3220；或者d=79-1(mod3220)这里就要用到欧几里得算法（又称辗转相除法），解法如下：（a）式子（1）可以表示成79*d-3220*k=1（其中k为正整数）；（b）将3220对79取模得到的余数60代替3220，则变为79*d-60*k=1；（c）同理，将79对60

24、取模得到的余数19代替79，则变为19*d-60*k=1；（d）同理，将60对19取模得到的余数3代替60，则变为19*d-3*k=1；（e）同理，将19对3取模得到的余数1代替19，则变为d-3*k=1；当d的系数最后化为1时，令k=0，代入（e）式中，得d=1；将d=1代入（d）式，得k=6；将k=6代入（c）式，得d=19；将d=19代入（b）式，得k=25；将k=25代入（a）式，得d=1019，这个值即我们要求的私钥d的最终值。此时，我们即可得到公钥PK=（e，n）=79，3337，私钥SK=1019，3337，后面的加密和解密直接套相应公式即可。RSA算法的实现算法的实现 实现的步

25、骤如下：秘钥产生实现的步骤如下：秘钥产生 (1) Bob寻找出两个大素数寻找出两个大素数p和和q (2) Bob计算出计算出n=pq 和和(n)=(p-1)(q-1) (3) Bob选择一个随机数选择一个随机数e (0e (n)，满足，满足gcd(e,(n)=1 (4) Bob使用辗转相除法计算使用辗转相除法计算d=e-1(mod(n)，即，即ed 1(mod(p-1)(q-1) (5) Bob在目录中（在目录中（e,n)作为公钥作为公钥. （6）(d,n)或者或者d作为私钥作为私钥.密码分析者攻击密码分析者攻击RSA体制的关键点在于体制的关键点在于如何分解如何分解n。若分。若分解成功使解成功

26、使n=pq，则可以算出，则可以算出(n)（p-1)(q-1)，然后由公，然后由公开的开的e，解出秘密的，解出秘密的dRSA算法编制算法编制 参数参数T=NT=N；私钥私钥SK=SK= (d,n) ；公钥公钥PK=PK=（e,n) ； 设：明文设：明文M M，密文，密文C C，那么：，那么： 用公钥作业：用公钥作业：M Me e mod N = C mod N = C 用私钥作业：用私钥作业：C Cd d mod N = M mod N = MRSA Example1.Select primes: p=17 & q=112.Compute n = pq =1711=1873.Comput

27、e (n)=(p1)(q-1)=1610=1604.Select e : gcd(e,160)=1; choose e=75.Determine d: de=1 mod 160 and d 160 Value is d=23 since 237=161= 1160+16.Publish public key Kp=7,1877.Keep secret private key Ks=23,187RSA Example cont sample RSA encryption/decryption is: given message M = 88 (nb. 88187) encryption:C =

28、887 mod 187 = 11 decryption:M = 1123 mod 187 = 88 2022-2-24469.2.2 RSA算法中的计算问题算法中的计算问题1. RSA的加密与解密过程的加密与解密过程-求幂运算求幂运算RSA的加密、解密过程都为求一个整数的的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许则中间结果非常大，有可能超出计算机所允许的整数取值范围。如上例中解密运算的整数取值范围。如上例中解密运算6677 mod 119，先求，先求6677再取模，则中间结果就已远远超

29、再取模，则中间结果就已远远超出了计算机允许的整数取值范围。而用模运算出了计算机允许的整数取值范围。而用模运算的性质：的性质：(ab) mod n=(a mod n)(b mod n) mod n 就可减小中间结果。就可减小中间结果。M Me e mod N = C mod N = C. 75 = 74.71 = 3.7 = 10 mod 112022-2-2447再者，考虑如何提高加、解密运算中指数运再者，考虑如何提高加、解密运算中指数运算的有效性。例如求算的有效性。例如求x16，直接计算的话需做，直接计算的话需做15次乘法。然而如果重复对每个部分结果做次乘法。然而如果重复对每个部分结果做平方

30、运算即求平方运算即求x，x2，x4，x8，x16则只需则只需4次乘次乘法。法。求求am可如下进行，其中可如下进行，其中a，m是正整数：是正整数： 将将m表示为二进制形式表示为二进制形式bk bk-1b0，即，即 m=bk2k+bk-12k-1+b12+b0 因此因此12012222kkkbbbbbmaaaaaa 2022-2-2448例如：例如：19=124+023+022+121+120，所以，所以a19=(a1)2a0)2a0)2a1)2a1从而可得以下快速指数算法：从而可得以下快速指数算法：c=0; d=1；For i=k downto 0 do c=2c;d=(dd) mod n;if

31、 bi =1 then c=c+1;d=(da) mod nreturn d.2022-2-24492. RSA密钥的产生密钥的产生 产生密钥时，需要考虑产生密钥时，需要考虑两个大素数两个大素数p、q的选取的选取，以及，以及e的选取和的选取和d的计算。的计算。 因为因为n=pq在体制中是公开的，因此为了防止敌在体制中是公开的，因此为了防止敌手通过穷搜索发现手通过穷搜索发现p、q，这，这两个素数两个素数应是在一应是在一个个足够大足够大的整数集合中选取的大数。如果选取的整数集合中选取的大数。如果选取p和和q为为10100左右的大素数，那么左右的大素数，那么n的阶为的阶为10200，每个明文分组可以

32、含有每个明文分组可以含有664位（位（102002664），），即即83个个8比特字节，这比比特字节，这比DES的数据分组（的数据分组（8个个8比比特字节）大得多，这时就能看出特字节）大得多，这时就能看出RSA算法的优算法的优越性了。因此越性了。因此如何有效地寻找大素数是第一个如何有效地寻找大素数是第一个需要解决的问题。需要解决的问题。2022-2-2450 寻找大素数时一般是先寻找大素数时一般是先随机选取一个大的奇数随机选取一个大的奇数（例如用伪随机数产生器），然后用例如用伪随机数产生器），然后用素性检验算法素性检验算法检验这一奇数是否为素数，如果不是则选取另一检验这一奇数是否为素数，如果不

33、是则选取另一大奇数，重复这一过程，直到找到素数为止。大奇数，重复这一过程，直到找到素数为止。 素性检验算法通常都是概率性的，但如果算法被素性检验算法通常都是概率性的，但如果算法被多次重复执行，每次执行时输入不同的参数，算多次重复执行，每次执行时输入不同的参数，算法的检验结果都认为被检验的数是素数，那么就法的检验结果都认为被检验的数是素数，那么就可以比较有把握地认为被检验的数是素数。可以比较有把握地认为被检验的数是素数。 可见寻找大素数是一个比较繁琐的工作。然而在可见寻找大素数是一个比较繁琐的工作。然而在RSA体制中，只有在产生新密钥时才需执行这一体制中，只有在产生新密钥时才需执行这一工作。工作

34、。 p和和q决定出后，下一个需要解决的问题是如何决定出后，下一个需要解决的问题是如何选取满足选取满足1e(n)和和gcd(n),e)=1的的e，并计算，并计算满足满足de1 mod (n)的的d。这一问题可由推广的。这一问题可由推广的Euclid算法完成。算法完成。RSA 的安全性的安全性 三种三种攻击攻击 RSA的方法的方法: 1，强力穷举密钥，强力穷举密钥:尝试所有可能的密钥。因此，尝试所有可能的密钥。因此，e 和和d 的位数越大，算法就越安全的位数越大，算法就越安全。然而，在密钥。然而，在密钥产生和加密解密中使用的计算都非常复杂，所以产生和加密解密中使用的计算都非常复杂，所以密钥越大，系

35、统运行越慢。密钥越大，系统运行越慢。 2，时间攻击：依赖，时间攻击：依赖解密算法的运行时间解密算法的运行时间，利用，利用CPU处理某些特殊的模乘比较慢的规律来确定每处理某些特殊的模乘比较慢的规律来确定每一位指数一位指数RSA 的安全性的安全性 3，数学攻击数学攻击 ：实质上是对两个素数乘积的分：实质上是对两个素数乘积的分解解. RSA的安全性是基于大整数素因子分解的困的安全性是基于大整数素因子分解的困难性，难性，而大整数因子分解问题是数学上的著名而大整数因子分解问题是数学上的著名难题，至今没有有效的方法予以解决，因此可难题，至今没有有效的方法予以解决，因此可以确保以确保RSA算法的安全性。现在

36、，人们已能分算法的安全性。现在，人们已能分解多个十进制位的大素数。因此，解多个十进制位的大素数。因此，模数模数n 必须必须选大一些选大一些，因具体适用情况而定。目前，人们，因具体适用情况而定。目前，人们已能分解已能分解140多个十进制位的大素数，这就要多个十进制位的大素数，这就要求使用更长的密钥，速度更慢。求使用更长的密钥，速度更慢。 RSA算法的安全性分析算法的安全性分析密码分析者攻击密码分析者攻击RSA体制的关键点在于体制的关键点在于如何分解如何分解n若分解成功使若分解成功使n=pq，则可以算出，则可以算出(n)（p-1)(q-1)，然后由公开的然后由公开的e，解出秘密的，解出秘密的d若使

37、若使RSA安全，安全，p与与q必为足够大的素数，使分析者必为足够大的素数，使分析者没有办法在多项式时间内将没有办法在多项式时间内将n分解出来分解出来RSA算法的安全性分析算法的安全性分析建议选择建议选择p和和q大约是大约是100位的十进制素数位的十进制素数模模n的长度要求至少是的长度要求至少是512比特比特，EDI攻击标准使用的攻击标准使用的RSA算法中规定算法中规定n的长度为的长度为512至至1024比特位之间，但比特位之间，但必须是必须是128的倍数的倍数国际数字签名标准国际数字签名标准ISO/IEC 9796中规定中规定n的长度位的长度位512比比特位特位RSA算法的安全性分析算法的安全

38、性分析 为了抵抗现有的整数分解算法，对为了抵抗现有的整数分解算法，对RSA模模n的素因子的素因子p和和q还有如下要求：还有如下要求： (1) |p-q|很大，通常很大，通常 p和和q的长度相同；的长度相同； (2) p-1 和和q-1分别含有大素因子分别含有大素因子p1和和q1 (3) P1-1和和q1-1分别含有大素因子分别含有大素因子p2和和q2 (4) p+1和和q+1分别含有大素因子分别含有大素因子p3和和q3RSA算法的安全性分析算法的安全性分析为了提高加密速度，通常取为了提高加密速度，通常取e为特定的小整数为特定的小整数如如EDI国际标准中规定国际标准中规定 e 2161ISO/I

39、EC9796中甚至允许取中甚至允许取e3这时加密速度一般比解密速度快这时加密速度一般比解密速度快10倍以上倍以上RSA的速度的速度由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA的缺点的缺点A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大。C)为保证安全性，n 至少也要 600 bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。D)目前，SET(Secure Elect

40、ronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。大素数产生大素数产生 素数生成过程素数生成过程: 随机选择一个奇数随机选择一个奇数n(如通过伪随机数发生器如通过伪随机数发生器) 随机选择随机选择a, 使使an 进行素性测试进行素性测试(例如用例如用Miller-Rabin算法算法),若若n没有通过没有通过测试测试,抛弃抛弃n,转到转到 如果通过了足够次数的测试如果通过了足够次数的测试,认为认为n是素数。是素数。 素数理论素数理论: 在在N附近，每附近，每ln(N)个整数中有一个素数个整数中有一个素数补充补充 反复平方乘反复平方乘例如：

41、例如：5*20=95，367，431，640，625=25 mod35；原理：如原理：如20=10100（0，1，10，101，1010，10100）=（0，1，2，5，10，20）1=0*2+1；2=1*2；5=2*2+1；10=5*2；20=10*2；10 2121 2252 212105 222010 225(5 )55mod355(5)525mod355(5 )5255 3125 10mod355(5 )10100 30mod355(5 )30900 25mod35 人物说明 Euler Leonhard (1707-1783) 欧拉，莱奥哈尔德：欧拉，莱奥哈尔德：(1707-1783

42、) 瑞士数学家，尤其他对瑞士数学家，尤其他对微积分的开创性贡献，以及他的复数、对数、三角函数和微积分的开创性贡献，以及他的复数、对数、三角函数和月球运动等理论而闻名于世月球运动等理论而闻名于世物理学家物理学家. Fer.mat Pierre de (1601-1665) 费马，皮尔费马，皮尔德：德：(1601-1665) 法国数学家，他有系统地阐法国数学家，他有系统地阐述了现代数理论和概率论述了现代数理论和概率论. Euclid欧几里得欧几里得(约公元前约公元前3世纪的古希腊数学家世纪的古希腊数学家) 他把逻辑学中他把逻辑学中的演绎原理应用到几何学中，籍以由定义明确的公理导出的演绎原理应用到几

43、何学中，籍以由定义明确的公理导出语句语句.离散对数公钥加密算法：离散对数公钥加密算法：自阅自阅是目前最为热门的公钥加密算法是目前最为热门的公钥加密算法，其安全性要远远，其安全性要远远高于基于大数分解的高于基于大数分解的RSA算法。安全性依赖于离散算法。安全性依赖于离散对数难解问题：对数难解问题：离散对数问题可以描述为：给定一个质数p，和有限域Zp上的一个本原元a，对Zp上整数b，寻找唯一的整数c，使得acb(mod p)。一般的，如果仔细选择p，则认为该问题是难解的，且目前还没有找到计算离散对数问题的多项式时间算法。为了抵抗已知的攻击，p至少应该是150位的十进制整数，且p-1至少有一个大的素

44、数因子。下面是一个使用离散对数的例子：Alice和Bob首先商议好p的值，本例假设为p=2579，则本原元为a=2。假设Alice要发送消息x =1299给Bob，则1）Bob选择随机数r=765作为自己的私钥，计算q=2r mod p=2756 mod 2579=949，作为公钥给Alice；2）Alice选择随机数k =853，计算y=2k mod p=2853 mod 2579=435，作为公钥给Bob；3）Alice计算密文e =x*qk mod p=1299*949853 mod 2579=2396，并传递给Bob；4）Bob接收到密文后，计算x =e*(yr)(-1) mod p=

45、2396*(435765)(-1) mod 2579=1299，从而得到原文。5.4 Diffie-Hellman密钥交换算法密钥交换算法Diffie和和Hellman在其里程碑意义的文章中，虽然给出在其里程碑意义的文章中，虽然给出了密码的思想，但是没有给出真正意义上的公钥密码了密码的思想，但是没有给出真正意义上的公钥密码实例，也既没能找出一个真正带实例，也既没能找出一个真正带陷门陷门的单向函数的单向函数然而，他们给出单向函数的实例，并且基于此提出然而，他们给出单向函数的实例，并且基于此提出Diffie-Hellman密钥交换算法密钥交换算法 Diffie-Hellman密钥交换密钥交换 允许

46、两个用户可以安全地交换一个秘密信息，用于后续的允许两个用户可以安全地交换一个秘密信息，用于后续的通讯过程通讯过程 算法的安全性依赖于计算离散对数的难度算法的安全性依赖于计算离散对数的难度素数素数p的原始根定义：如果的原始根定义：如果a是素数是素数p的原始根，则数的原始根，则数a mod p, a2 mod p, , ap-1 mod p是不同的并且包含是不同的并且包含1到到p-1的整数的某种排列。的整数的某种排列。对任意的整数对任意的整数b，我们可以找到唯一的幂，我们可以找到唯一的幂i满足满足b=ai mod p 0=i=(p-1)指数指数i 称为称为b的以的以a为底为底 (或基或基)的模的模

47、p离散对数离散对数 。记为。记为dloga,p(b)Diffie-Hellman密钥交换协议描密钥交换协议描述述Alice和和Bob协商好一个大素数协商好一个大素数p，和大的整数，和大的整数g，1gp，g最好是最好是FP中的中的本原元（原始根）本原元（原始根），即，即FP*p和和g无须保密，可为网络上的所有用户共享无须保密，可为网络上的所有用户共享 。Diffie-Hellman密钥交换协议描述密钥交换协议描述当当Alice和和Bob要进行保密通信时，他们可以按如下步骤来要进行保密通信时，他们可以按如下步骤来做：做： (1) Alice选取大的随机数选取大的随机数x，并计算，并计算 X = g

48、x(mod P) (2) Bob选取大的随机数选取大的随机数x ，并计算，并计算 X = gx (mod P) (3) Alice将将X传送给传送给Bob；Bob将将X 传送给传送给Alice (4) Alice计算计算K= (X )X(mod P); Bob计算计算K =（X) X (mod P), 易见，易见，K = K =g xx (mod P)由由(4)知，知，Alice和和Bob已获得了相同的秘密值已获得了相同的秘密值K双方以双方以K作为加解密钥以传统对称密钥算法进行保密通信作为加解密钥以传统对称密钥算法进行保密通信 Generate randomXa pCalculateYa=aX

49、a mod pGenerate randomXb pCalculateYb=aXb mod pUser AUser BYaYbCalculateK=(Yb)Xa mod pCalculateK=(Ya)Xb mod pDiffie-Hellman Key ExchangeDiffie-Hellman安全性安全性离散对数的计算离散对数的计算:y gx mod p 已知已知g,x,p,计算计算y是容易的是容易的 已知已知y,g,p,计算计算x是困难的是困难的 Diffie-Hellman密钥交换的攻击密钥交换的攻击 replay攻击攻击中间人攻击图示中间人攻击图示ABK = aXaXbOABK =

50、 aXaXoOK = aXbXo Diffie-Hellman密钥交换的攻击密钥交换的攻击中间人攻击中间人攻击1 双方选择素数双方选择素数p以及以及p的一个原根的一个原根a(假定假定O知道知道)2 A选择选择Xap,计算计算Ya=aXa mod p, AB: Ya3 O截获截获Ya,选选Xo,计算计算Yo=aXo mod p,冒充冒充AB:Yo4 B选择选择Xbp,计算计算Yb=aXb mod p, BA: Yb5 O截获截获Yb,冒充冒充BA:Yo6 A计算计算: (Xo)Xa (aXo)Xa aXoXa mod p7 B计算计算: (Xo)Xb (aXo)XXb aXoXb mod p8

51、O计算计算: (Ya)Xo aXaXo mod p, (Yb)Xo aXbXo mod pO无法计算出无法计算出aXaXb mod pO永远必须实时截获并冒充转发永远必须实时截获并冒充转发,否则会被发现否则会被发现 防范措施防范措施 1，使用共享的对称密钥加密，使用共享的对称密钥加密DH交换；交换； 2，使用公钥加密，使用公钥加密DH交换；交换； 3，使用私钥签名，使用私钥签名DH交换；交换； 经典例子经典例子 Diffie-Hellman密钥交换算法密钥交换算法 背包算法背包算法 RSA算法算法 椭圆曲线密码算法椭圆曲线密码算法ECC5.5 椭圆曲线密码介绍椭圆曲线密码介绍 在在2005年年

52、2月月16日，日，NSA宣布决定采用椭圆曲线密宣布决定采用椭圆曲线密码的战略作为美国政府标准的一部分，用来保护码的战略作为美国政府标准的一部分，用来保护敏感但不保密的信息。敏感但不保密的信息。NSA推荐了一组被称为推荐了一组被称为Suit B的算法，包括用来密钥交换的的算法，包括用来密钥交换的Menezes-Qu-Vanstone椭圆曲线和椭圆曲线和Diffie-Hellman椭圆曲线，用椭圆曲线，用来数字签名的椭圆曲线数字签名算法。这一组中来数字签名的椭圆曲线数字签名算法。这一组中也包括也包括AES和和SHA。 5.5 椭圆曲线密码介绍椭圆曲线密码介绍 1985年年Miller,Koblit

53、z 独立提出独立提出y2+axy+by=x3+cx2+dx+e 曲线上的点连同曲线上的点连同无穷远点无穷远点O的集合的集合(定义见下页）定义见下页） 运算定义：运算定义： 若曲线三点在一条直线上若曲线三点在一条直线上,则其和为则其和为O O用作加法的单位：用作加法的单位：O = -O; P+O = P 一条竖直线交一条竖直线交X轴两点轴两点P1、P2，则，则P1+P2+O=O，于是，于是P1 = -P2 如果两个点如果两个点Q和和R的的X轴不同，则画一连线，得到第三点轴不同，则画一连线，得到第三点P1，则，则Q+R+P1=O，即，即Q+R=-P1 2倍，一个点倍，一个点Q的两倍是，找到它的切线

54、与曲线的另一个的两倍是，找到它的切线与曲线的另一个交点交点S，于是，于是Q+Q=2Q=-S (1) 无穷远元素（无穷远点，无穷远直线）无穷远元素（无穷远点，无穷远直线） 平面上任意两相异直线的位置关系有相交和平行两种平面上任意两相异直线的位置关系有相交和平行两种。引入无穷远点，是两种不同关系统一。引入无穷远点，是两种不同关系统一。 ABL1， L2L1，直线直线AP由由AB起绕起绕A点依逆时针方向转点依逆时针方向转动，动，P为为AP与与L1的交点。的交点。L2L1PBAPQQ=BAP /2 AP L2可设想可设想L1上有一点上有一点P，它为，它为L2和和L1的交点，称之为的交点，称之为。直线直

55、线L1上的无穷远点只能有一个。上的无穷远点只能有一个。（因为过（因为过A点只能有一条平行于点只能有一条平行于L1的直线的直线L2，而两直线的交点，而两直线的交点只能有一个。）只能有一个。）结论：结论：1*. 平面上一组相互平行的直线，有公共的无穷远点。平面上一组相互平行的直线，有公共的无穷远点。（为与无穷远点相区别，把原来平面上的点叫做（为与无穷远点相区别，把原来平面上的点叫做）2* .平面上任何相交的两直线平面上任何相交的两直线L1,L2有不同的无穷远点。有不同的无穷远点。原因：若否，则原因：若否，则L1和和L2有公共的无穷远点有公共的无穷远点P，则过两相异点，则过两相异点A和和P 有相异两直线，与公理相矛盾。有相异两直线，与公理相矛盾。 椭圆曲线密码示意图椭圆曲线密码示意图 有限域上椭圆曲线有限域上椭圆曲线有限域上椭圆曲线有限域上椭圆曲线y2 x3+ax+b mod p p是奇素数是奇素数,且且4a3+27b2 0 mod p针对所有的针对所有的0= x p