第6章公钥密码体制

1、Information Security：Principles & Applications第第6章章 公钥密码体制公钥密码体制Char 7 pp.2本章概要本章概要o 公钥密码的概念、特点和应用范围。公钥密码的概念、特点和应用范围。o 数论基础数论基础o RSARSA算法加、解密过程。算法加、解密过程。o 其它公钥算法简介。其它公钥算法简介。o 教学要求：原理要清楚，数论不深究。教学要求：原理要清楚，数论不深究。 Information Security：Principles & Applications6.1公钥密码的基本思想 Char 7 pp.4o 密钥分配密钥分配:

2、:通信密钥太多，管理和分发困难。通信密钥太多，管理和分发困难。n 传统密钥管理：两两分别用一对密钥时，则传统密钥管理：两两分别用一对密钥时，则n n个用户个用户需要需要C(n,2)=n(n-1)/2C(n,2)=n(n-1)/2个密钥，当用户量增大时，个密钥，当用户量增大时，密钥空间急剧增大。如密钥空间急剧增大。如: :n n=100 n=100 时，时，C(100,2)=4,995C(100,2)=4,995n n=5000n=5000时，时，C(5000,2)=12,497,500C(5000,2)=12,497,500o 数字签名和认证数字签名和认证n 传统加密算法无法实现抗抵赖的需求传

3、统加密算法无法实现抗抵赖的需求对称密钥面临的困题对称密钥面临的困题Char 7 pp.5密码体制上的突破密码体制上的突破o DiffieDiffie & Hellman, & Hellman, 密码学新方向密码学新方向( (New Direction in New Direction in Cryptography), 1976Cryptography), 1976。o 首次公开提出了首次公开提出了“公开密钥密码编码学公开密钥密码编码学”的概念。的概念。o 这是一个与对称密码编码截然不同的方案：这是一个与对称密码编码截然不同的方案：n 公钥算法是基于数学函数；传统对称密码算法基

4、于公钥算法是基于数学函数；传统对称密码算法基于替换和置换。替换和置换。n 公钥密码学是非对称的，它使用两个独立的密钥；公钥密码学是非对称的，它使用两个独立的密钥；传统对称密码使用一个密钥。传统对称密码使用一个密钥。Char 7 pp.6公钥密码的定义（公钥密码的定义（1）用抽象的观点来看，公钥密码是一种陷门单向函数。用抽象的观点来看，公钥密码是一种陷门单向函数。单向陷门函数是满足单向陷门函数是满足下列条件的函数下列条件的函数f f：n(1)(1)给定给定x x，计算，计算y=y=f(xf(x) )是容易的；是容易的；n(2)(2)给定给定y, y, 计算计算x x使使x=fx=f-1-1(y)

5、(y)是困难的。是困难的。( (所谓计算所谓计算x=fx=f-1-1(y)(y)困难是指计算上相当复杂，已无实际意义困难是指计算上相当复杂，已无实际意义) )n(3)(3)存在存在，已知，已知 时时, ,对给定的任何对给定的任何y y，若相应的，若相应的x x存在，则存在，则计算计算x x使使x=fx=f-1-1(y)(y)是容易的。是容易的。 仅满足仅满足(1)(1)、(2)(2)两条的称为单向函数；第两条的称为单向函数；第(3)(3)条称为陷门性，条称为陷门性， 称为陷门称为陷门信息；满足（信息；满足（1 1）、（）、（2 2）、（）、（3 3）就是单向陷门函数，公钥密码就是基）就是单向陷

6、门函数，公钥密码就是基于这一原理设计的，将辅助信息（陷门信息）作为秘密密钥。于这一原理设计的，将辅助信息（陷门信息）作为秘密密钥。 Char 7 pp.7o 当用陷门函数当用陷门函数f f作为加密函数时，可将作为加密函数时，可将f f公开，这相当于公开公开，这相当于公开加密密钥。此时加密密钥便称为公开钥，记为加密密钥。此时加密密钥便称为公开钥，记为KUKU。 f f函数的函数的设计者将设计者将 保密，用作解密密钥，此时保密，用作解密密钥，此时 称为秘密钥匙，称为秘密钥匙，记为记为KRKR。由于加密函数是公开的，任何人都可以将信息。由于加密函数是公开的，任何人都可以将信息x x加加密成密成y=y

7、=f(xf(x) )，然后送给函数的设计者（当然可以通过不安全，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有信道传送）；由于设计者拥有KRKR，他自然可以解出，他自然可以解出x=fx=f-1-1(y)(y)。o 单向陷门函数的第单向陷门函数的第(2)(2)条性质表明窃听者由截获的密文条性质表明窃听者由截获的密文y=y=f(xf(x) )推测推测x x是不可行的。是不可行的。公钥密码的定义（公钥密码的定义（2）Char 7 pp.8o 一对（一对（两个两个）密钥：）密钥：n 使用一个密钥进行加密，用另一个相关的密钥进行使用一个密钥进行加密，用另一个相关的密钥进行解密解密o

8、用加密密钥生成的密文只有使用其对应的解用加密密钥生成的密文只有使用其对应的解密密钥才能解密。密密钥才能解密。n 两个密钥的关系满足：两个密钥的关系满足：o 两个密钥是不相同；两个密钥是不相同；o 在仅知道密码算法和加密密钥的情况下，要在仅知道密码算法和加密密钥的情况下，要推断解密密钥在计算上是推断解密密钥在计算上是不可行不可行的。的。o 两个密钥中的两个密钥中的任何一个任何一个都可以用来加密，另都可以用来加密，另一个用来解密。（如一个用来解密。（如RSARSA）公钥算法基本特征公钥算法基本特征Char 7 pp.9o 密钥管理密钥管理n 加密密钥是公开的；加密密钥是公开的； n 解密密钥需要妥

9、善保存；解密密钥需要妥善保存； n 在当今具有用户量大、消息发送方与接收方具有明在当今具有用户量大、消息发送方与接收方具有明显的信息不对称特点的应用环境中表现出了令人乐显的信息不对称特点的应用环境中表现出了令人乐观的前景。观的前景。 o 数字签名和认证数字签名和认证n 只有解密密钥能解密，只有正确的接收者才拥有解只有解密密钥能解密，只有正确的接收者才拥有解密密钥。密密钥。公钥密码体制优点公钥密码体制优点Char 7 pp.10o 明文明文：算法的输入。可读信息或数据。：算法的输入。可读信息或数据。o 加密算法加密算法：对明文进行各种转换。：对明文进行各种转换。o 公钥和私钥公钥和私钥：算法的输

10、入。一个用于加密，一个用：算法的输入。一个用于加密，一个用于解密。算法执行的变换依赖于公钥和私钥。于解密。算法执行的变换依赖于公钥和私钥。o 密文密文：算法的输出。依赖于明文和密钥，对于给定：算法的输出。依赖于明文和密钥，对于给定的消息，不同的密钥产生不同明文。的消息，不同的密钥产生不同明文。o 解密算法：接收密文和相应的密钥，并产生原始的解密算法：接收密文和相应的密钥，并产生原始的明文。明文。公钥密码组成公钥密码组成Char 7 pp.11公钥密码加密公钥密码加密/解密模型解密模型对称密码通信模型对称密码通信模型Char 7 pp.12公钥密码公钥密码/加解过程加解过程o 每一用户产生一对密

11、钥，用来加密和解密消息。每一用户产生一对密钥，用来加密和解密消息。o 用户将其中一个密钥存于公开的寄存器或其他可访问的文件用户将其中一个密钥存于公开的寄存器或其他可访问的文件中，该密钥称为公钥，另一个密钥是私有的，称为私钥。用中，该密钥称为公钥，另一个密钥是私有的，称为私钥。用户可以拥有若干其他用户的公钥户可以拥有若干其他用户的公钥o 若若BobBob要发消息给要发消息给AliceAlice，则，则BobBob用用AliceAlice的公钥对消息加密。的公钥对消息加密。o AliceAlice收到消息后，用其私钥对消息进行解密。由于只有收到消息后，用其私钥对消息进行解密。由于只有 AliceA

12、lice知道其自身的私钥，所以其他接收者均不能解密出消知道其自身的私钥，所以其他接收者均不能解密出消息。息。o 在公钥密码中，通信各方均可以访问公钥，而私钥是各通在公钥密码中，通信各方均可以访问公钥，而私钥是各通信方在本地产生的，不进行分配。只要控制了私钥，通信就信方在本地产生的，不进行分配。只要控制了私钥，通信就是安全的。在任何时候，用户可以改变其私钥并公布相应的是安全的。在任何时候，用户可以改变其私钥并公布相应的公钥以代替原来的公钥。公钥以代替原来的公钥。Char 7 pp.13公钥密码通信保密性分析图公钥密码通信保密性分析图对称密码保密性对称密码保密性Char 7 pp.14公钥密码通信

13、保密性分析公钥密码通信保密性分析o 消息源消息源A A产生消息产生消息X=XX=X1 1,X,X2 2,X Xm m,其中其中X X的的M M个元素是某个有个元素是某个有穷字母表上的字符，穷字母表上的字符，A A欲将消息欲将消息X X发送给发送给B B。B B产生公钥产生公钥KUKUb b和和私钥私钥KRKRb b，其中只有，其中只有B B知道知道KRKRb b，而，而KUKUb b则是公开的可访问的，则是公开的可访问的，所以所以A A也可访问也可访问KUKUb b。o 对作为输入的消息对作为输入的消息X X和加密密钥和加密密钥KUbKUb，A A生成密文生成密文Y=YY=Y1 1,Y,Y2

14、2,Y Yn n: Y=: Y=E EKUbKUb(X(X) )o 期望的接收方因为拥有相应的私钥，所以可进行逆变换：期望的接收方因为拥有相应的私钥，所以可进行逆变换：X=X=D DKRbKRb(Y(Y) )o 攻击者可以观察到攻击者可以观察到Y Y并且可以访问并且可以访问KUKUb b，但是它不能访问，但是它不能访问KRKRb b或者或者X X，所以他无法知道，所以他无法知道X X，从而实现了保密通信。，从而实现了保密通信。Char 7 pp.15公钥密码认证模型公钥密码认证模型Char 7 pp.16公钥密码认证过程公钥密码认证过程o 每一用户产生一对密钥，用来加密和解密消息。每一用户产生

15、一对密钥，用来加密和解密消息。o 每一个用户将其中一个密钥存于公开的寄存器或其他可访问每一个用户将其中一个密钥存于公开的寄存器或其他可访问的文件中，该密钥称为公钥，另一个密钥是私有的。每一个的文件中，该密钥称为公钥，另一个密钥是私有的。每一个用户可以拥有其他若干个其他用户的公钥。用户可以拥有其他若干个其他用户的公钥。o 若若BobBob要发消息给要发消息给AliceAlice，且需要向，且需要向AliceAlice提供认证，则提供认证，则BobBob用用私钥对消息加密。私钥对消息加密。o AliceAlice收到消息后，用收到消息后，用BobBob的公钥对消息进行解密。由于只有的公钥对消息进行

16、解密。由于只有 BobBob知道其自身的私钥，所以其他发送者均不能生成能用知道其自身的私钥，所以其他发送者均不能生成能用BobBob公钥解密的消息。由此可以确认此消息来源于公钥解密的消息。由此可以确认此消息来源于BobBob。Char 7 pp.17公钥密码认证分析图公钥密码认证分析图Char 7 pp.18公钥密码认证分析公钥密码认证分析o消息源消息源A A产生消息产生消息X=XX=X1 1,X,X2 2,X Xm m,其中其中X X的的M M个元素是某个有穷字母表上个元素是某个有穷字母表上的字符，的字符，A A欲将消息欲将消息X X发送给发送给B B。A A产生公钥产生公钥KUKUa a和

17、私钥和私钥KRKRa a，其中只有，其中只有A A知道知道KRaKRa，而，而KUKUa a则是公开的可访问的，所以则是公开的可访问的，所以B B也可访问也可访问KUKUa a。oA A向向B B发送消息前，先用发送消息前，先用A A的私钥对消息加密，的私钥对消息加密，B B则用则用A A的公钥对消息解密。的公钥对消息解密。由于是用由于是用A A的私钥对消息加密，所以只有的私钥对消息加密，所以只有A A可加密消息，因此，整个加密可加密消息，因此，整个加密后的消息就是数字签名。除此之外只有拥有后的消息就是数字签名。除此之外只有拥有A A 的私钥才能产生上述加密的私钥才能产生上述加密后的消息，因此

18、该消息可用于认证源与数据完整性。后的消息，因此该消息可用于认证源与数据完整性。o作为任何第三方只要都可以很容易的收到认证消息作为任何第三方只要都可以很容易的收到认证消息Y Y，因此该过程不提，因此该过程不提供保密。供保密。Char 7 pp.19公钥密码的保密与认证图公钥密码的保密与认证图Char 7 pp.20公钥密码保密与认证过程分析公钥密码保密与认证过程分析o 对于单次加密只提供认证或保密的问题，可以采用两次运用对于单次加密只提供认证或保密的问题，可以采用两次运用公钥密码的方式即提供加密又提供认证：公钥密码的方式即提供加密又提供认证：Z=Z=E EKUbKUbEEKRaKRa(X(X)

19、) X=X=D DKUaKUaDDKRbKRb(Z(Z)o 发送方首先用其私钥对消息加密，得到数字签名，然后再用发送方首先用其私钥对消息加密，得到数字签名，然后再用接收方的公钥加密，所得密文只有被拥有私钥的接收方解密。接收方的公钥加密，所得密文只有被拥有私钥的接收方解密。这样可保证消息的保密性。这样可保证消息的保密性。o 缺点：在每次通信中要执行四次复杂的公钥算法。缺点：在每次通信中要执行四次复杂的公钥算法。Char 7 pp.21常见公钥算法适用范围常见公钥算法适用范围Char 7 pp.22对称密码和公钥密码比较（对称密码和公钥密码比较（1） 对称密码对称密码运行条件：运行条件：1、加密和

20、解密使用同一个、加密和解密使用同一个密钥和一个算法。密钥和一个算法。2、发送方和接收方必须共、发送方和接收方必须共享密钥和算法。享密钥和算法。 公公钥密码钥密码运行条件：运行条件：1 1、用同一个算法进行加密、用同一个算法进行加密和解密，而密钥有一对，和解密，而密钥有一对，其中一个用于加密，另一其中一个用于加密，另一个用于解密。个用于解密。2 2、发送方和接收方每个拥、发送方和接收方每个拥有一对相互匹配的密钥中有一对相互匹配的密钥中的一个的一个( (不是同一个不是同一个) )。Char 7 pp.23对称密码和公钥密码比较（对称密码和公钥密码比较（2） 对称密码对称密码安全条件：安全条件：1、

21、密钥必须保密。、密钥必须保密。2、如果不掌握其他信息，要、如果不掌握其他信息，要想解密报文是不可能或者想解密报文是不可能或者至少是不现实的。至少是不现实的。3、知道所用的算法加上密文、知道所用的算法加上密文的样本必须不足以确定密的样本必须不足以确定密钥。钥。 公钥密码公钥密码安全条件：安全条件：1 1、两个密钥中的一个必、两个密钥中的一个必须保密。须保密。2 2、如果不掌握其他信息，、如果不掌握其他信息，要想解密报文是不可能要想解密报文是不可能或者至少是不现实的。或者至少是不现实的。3 3、知道所用的算法加上、知道所用的算法加上一个密钥加上密文的样一个密钥加上密文的样本必须不足以确定密钥。本必

22、须不足以确定密钥。Char 7 pp.24公钥密码的保密与认证图公钥密码的保密与认证图Char 7 pp.25公钥密码保密与认证过程分析公钥密码保密与认证过程分析o 对于单次加密只提供认证或保密的问题，可以采用两次运用对于单次加密只提供认证或保密的问题，可以采用两次运用公钥密码的方式即提供加密又提供认证：公钥密码的方式即提供加密又提供认证：Z=Z=E EKUbKUbEEKRaKRa(X(X) ) X=X=D DKUaKUaDDKRbKRb(Z(Z)o 发送方首先用其私钥对消息加密，得到数字签名，然后再用发送方首先用其私钥对消息加密，得到数字签名，然后再用接收方的公钥加密，所得密文只有被拥有私钥

23、的接收方解密。接收方的公钥加密，所得密文只有被拥有私钥的接收方解密。这样可保证消息的保密性。这样可保证消息的保密性。o 缺点：在每次通信中要执行四次复杂的公钥算法。缺点：在每次通信中要执行四次复杂的公钥算法。Char 7 pp.26常见公钥算法适用范围常见公钥算法适用范围Char 7 pp.27对称密码和公钥密码比较（对称密码和公钥密码比较（1） 对称密码对称密码运行条件：运行条件：1、加密和解密使用同一个、加密和解密使用同一个密钥和一个算法。密钥和一个算法。2、发送方和接收方必须共、发送方和接收方必须共享密钥和算法。享密钥和算法。 公公钥密码钥密码运行条件：运行条件：1 1、用同一个算法进行

24、加密、用同一个算法进行加密和解密，而密钥有一对，和解密，而密钥有一对，其中一个用于加密，另一其中一个用于加密，另一个用于解密。个用于解密。2 2、发送方和接收方每个拥、发送方和接收方每个拥有一对相互匹配的密钥中有一对相互匹配的密钥中的一个的一个( (不是同一个不是同一个) )。Char 7 pp.28对称密码和公钥密码比较（对称密码和公钥密码比较（2） 对称密码对称密码安全条件：安全条件：1、密钥必须保密。、密钥必须保密。2、如果不掌握其他信息，要、如果不掌握其他信息，要想解密报文是不可能或者想解密报文是不可能或者至少是不现实的。至少是不现实的。3、知道所用的算法加上密文、知道所用的算法加上密

25、文的样本必须不足以确定密的样本必须不足以确定密钥。钥。 公钥密码公钥密码安全条件：安全条件：1 1、两个密钥中的一个必、两个密钥中的一个必须保密。须保密。2 2、如果不掌握其他信息，、如果不掌握其他信息，要想解密报文是不可能要想解密报文是不可能或者至少是不现实的。或者至少是不现实的。3 3、知道所用的算法加上、知道所用的算法加上一个密钥加上密文的样一个密钥加上密文的样本必须不足以确定密钥。本必须不足以确定密钥。Char 7 pp.29公钥密码算法应满足条件公钥密码算法应满足条件 假设消息源为假设消息源为A，要发送的消息为，要发送的消息为M，消息接收方为，消息接收方为B。B的公钥的公钥KUb，私

26、，私钥钥KRb。oB产生一对密钥（公钥产生一对密钥（公钥KUb ，私钥，私钥KRb ）在计算上是容易的。）在计算上是容易的。o已知公钥已知公钥KUb和要加密的消息和要加密的消息M，发送方，发送方A产生相应的密文在计算上是产生相应的密文在计算上是容易的：容易的：C=EKUb（M）o接收方接收方B使用其私钥对接收方的密文解密以恢复明文在计算上是容易的：使用其私钥对接收方的密文解密以恢复明文在计算上是容易的：M=DKRb（C）= DKRbEKUb（M）o已知公钥时，攻击者要确定私钥，在计算上是不可行的。已知公钥时，攻击者要确定私钥，在计算上是不可行的。o已知公钥和密文，攻击者要恢复明文已知公钥和密文

27、，攻击者要恢复明文M在计算上是不可行的。在计算上是不可行的。o加密和解密函数的顺序可以交换：加密和解密函数的顺序可以交换： M= DKUb EKRb（M）=EKUb DKRb （M）目前只有两个满足这些条件的算法：目前只有两个满足这些条件的算法：RSA、椭圆密码体制、椭圆密码体制Char 7 pp.30(1)(1)基于大整数因子分解的基于大整数因子分解的RSARSA算法；算法；(2)(2)椭圆曲线公钥算法；椭圆曲线公钥算法；(3)(3)基于因子分解问题的基于因子分解问题的RabinRabin算法；算法；(4)(4)基于有限域中离散对数难题的基于有限域中离散对数难题的ElGamalElGamal

28、公钥密码算公钥密码算法法(5)(5)基于代数编码系统的基于代数编码系统的McElieceMcEliece公钥密码算法；公钥密码算法； (6)(6)基于基于“子集和子集和”难题的难题的Merkle-HellmanMerkle-Hellman Knapsack Knapsack公钥密码算法；公钥密码算法； (7)(7)目前被认为安全的目前被认为安全的KnapsackKnapsack型公钥密码算法型公钥密码算法Chor-Chor-RivestRivest。 公钥密码算法公钥密码算法Information Security：Principles & Applications6.2 6.2 数论

29、简介数论简介Char 7 pp.32数论术语数论术语o最大公因子最大公因子 ：任意有限个整数：任意有限个整数 的公因子中的最大一个。必的公因子中的最大一个。必然存在并且惟一，记为然存在并且惟一，记为 。o最小公倍数最小公倍数 ：任意有限个整数：任意有限个整数 的公倍数中的最小一个的公倍数中的最小一个 。必然存在并且惟一，记为必然存在并且惟一，记为 。o同余式同余式 ：设：设n是一个正整数，是一个正整数， 如果如果 ，则称，则称a和和b模模n同余，记作：同余，记作： ，称整数，称整数n为同余模。为同余模。o加法逆元加法逆元 ：设：设 ，如果存在，如果存在 满足满足 ，则称，则称x是是a的的模模n

30、加法逆元。加法逆元。o乘法逆元乘法逆元 ：设：设 ，如果存在，如果存在 满足满足 ，则称，则称x是是a的模的模n乘法逆元，记为乘法逆元，记为 a-1 (mod n)。naaa,21 ),gcd(21naaa naaa,21 ),(21naaalcm Zba,nbnamodmod)(modnba nZanZx)(mod0naxnZanZx)(mod1nax Char 7 pp.33整数和模整数和模定义：设定义：设a,b,ca,b,c是任意的三个整数，若满足是任意的三个整数，若满足b=acb=ac则称则称a a整除整除b,ab,a( (或或c c）是）是b b的因子，的因子，b b是是a a（或（

31、或c c）的倍数，记）的倍数，记为为 abab; ;若若a a不能整除不能整除b b，记为记为a a！b.b.性质：性质：（1 1） 若若baba, , 则下列各式成立则下列各式成立 (b0) (b0) (b)ab)a, , b(ab(a), (), (b)(ab)(a), ), baba（2 2）若）若cbcb且且baba (c0,b0), (c0,b0), 则则caca（3 3）若）若baba (b0), (b0), 则则bacbac（4 4） 若若baba且且bcbc (b0), (b0), 则则b(ab(ac c) )（5 5） 若若abab且且baba (a0,b0), (a0,b0

32、), 则则a=a=b bChar 7 pp.34定理定理6.2.1 6.2.1 设设a,ba,b是两个整数，是两个整数，b1b1，则存在唯一确，则存在唯一确定的整数定的整数q q、r r使满足使满足a=a=bq+rbq+r； 其中其中0rb0r=2)=2)是任意整数，若有是任意整数，若有 d|ad|a1 1,d| a,d| a2 2,d|ad|an n，则称则称d d是是a a1 1,a,a2 2,a,an n的公因子。的公因子。 若若d d是是a a1 1,a,a2 2,a,an n的一个公因子，对的一个公因子，对a a1 1,a,a2 2,a,an n的任一个公因子的任一个公因子c c，存

33、在存在c c d d，则称则称d d是是a a1 1,a,a2 2,a,an n的最大公因子，记为的最大公因子，记为 gcdgcd （ a a1 1,a,a2 2,a,an n ）若若gcd(al,a2,an)=1, 称称al,a2,an是互素。是互素。在互素的正整数中在互素的正整数中, 不一定有素数不一定有素数. 例如例如(25,36)=1, 但但25和和36都都不是素数而是合数不是素数而是合数.Char 7 pp.36最大公因子的性质最大公因子的性质任何不全为任何不全为0的两个整数的最大公因子存在且唯一的两个整数的最大公因子存在且唯一o 设整数设整数a与与b不全为不全为0，则存在整数，则存

34、在整数x和和y，使得，使得ax+by=gcd(a,b)。特别地，如果。特别地，如果a、b互素，则有互素，则有ax+by=1o 若若gcd(a,b)=d, 则则gcd (a|d, b|d)=1o 若若gcd(a,x)=gcd(b,x)=1,那么那么gcd(ab,x)=1o 若若c|(ab),gcd(b,c)=1,则则c|aChar 7 pp.37最小公倍数最小公倍数设设a a1 1,a,a2 2,a,an n和和m m都是正整数都是正整数, , n2. n2. 若若a ai i|m|m, , 1in, 1in, 则称则称m m是是a a1 1,a,a2 2,a,an n的公倍数的公倍数. .o

35、在在a a1 1,a,a2 2,a,an n所有公倍数中最小的那一个所有公倍数中最小的那一个, , 称为称为a a1 1,a,a2 2,a,an n的最小公倍数的最小公倍数, , 记为记为lcm(alcm(a1 1,a,a2 2,a,an n）Char 7 pp.38素数定义素数定义o 一个大于一个大于1且只能被且只能被1和它本身整除的整数和它本身整除的整数, 称为素数称为素数; 否则否则, 称为合数称为合数.o 素数有无穷多个；素数有无穷多个；o 如果如果p是一个素数，且是一个素数，且p|ab,则则p|a或或p|b;o 记记PAI(x)为不大于为不大于x的素数个数，则的素数个数，则o 即对于

36、充分大的即对于充分大的x，可以用，可以用xlnx近似的表示近似的表示PAI(x)Char 7 pp.39算术基本定理算术基本定理o 算术基本定理：任意一个正整数算术基本定理：任意一个正整数n(n1)可以唯一地可以唯一地表示为若干个素数的乘积。这里唯一的意义表示为表示为若干个素数的乘积。这里唯一的意义表示为不考虑素因子的次序。不考虑素因子的次序。o 任意一个整数任意一个整数n(n0,n1)可以唯一地表示为可以唯一地表示为p1 p2 pk ( k=1 )，p1 ,p2, ,pk是素数。是素数。o 任意一个整数任意一个整数n(n0,n1)可以唯一地表示为可以唯一地表示为 p1r1 p2r2 pkrk

37、，p1 ,p2, ,pk是质数，是质数，r1,r2,rk是是正整数。正整数。Char 7 pp.40强素数强素数on n是一个整数，是一个整数，n=n=pqpq, ,且且p p、q q满足以下属性时，称满足以下属性时，称n n为强素数：为强素数：o(1)gcd(p-1,q-1)(1)gcd(p-1,q-1)比较小；比较小；o(2)p-1(2)p-1和和q-1q-1都有大素因子都有大素因子( (记记p p* *,q,q* *) )；o(3)p(3)p* *-1-1和和q q* *-1-1都有大的素因子；都有大的素因子；o(4)p+1(4)p+1和和q+1q+1都有大的素因子；都有大的素因子；o(

38、5)(p-1)/2(5)(p-1)/2和和(q-1)/2(q-1)/2都是素数都是素数o对于强素数，即使采用特殊的因子分解方法，对整数对于强素数，即使采用特殊的因子分解方法，对整数n n的因子分解也非的因子分解也非常困难。常困难。o强素数：强素数：439351292910452432574786963588089477522344331强素数强素数第六章第六章一种强素数因子分解的量子算法一种强素数因子分解的量子算法.pdf实现实现Char 7 pp.41欧拉函数欧拉函数欧拉函数欧拉函数(n n) )：表示区间：表示区间1,n1,n中中与与 n n 互素的整数的个数；互素的整数的个数；习惯上，习

39、惯上，欧拉函数的性质：欧拉函数的性质：( (1 1) )素数素数 p p，有，有( (p p)=)=p p11；( (2 2) )( (n n) )为积性函数，即，如果为积性函数，即，如果gcd(m,ngcd(m,n)=1,)=1, ( (mnmn)=)=( (m m) )( (n n) )(3)(3)对于对于n n属于属于Z Z，n n22，(4)(4)对于素数对于素数p,q,np,q,n= =pq,pq,( (n n)=)=(pq(pq)=(p-1)(q-1)=(p-1)(q-1)(5)(5)如果如果n n属于属于Z Z，n5n5，则，则积性函数：积性函数：在数论上，对于正整数在数论上，对

40、于正整数n的一个算术函数的一个算术函数 f(n)，当，当中中f(1)=1且当且当a,b互质，互质，f(ab)=f(a)f(b)完全积性函数完全积性函数: 若某算术函数若某算术函数f(n)符合符合f(1)=1，且就算，且就算a,b不互质，不互质，f(ab)=f(a)f(b)。Char 7 pp.42欧拉函数前欧拉函数前30项项Char 7 pp.43欧拉定理欧拉定理对于任意互素的对于任意互素的a 和和 n ，有：，有：等价形式：等价形式：nanmod1)(fnanmoda)+1(fChar 7 pp.44Euclidean算法算法(1)根据根据: (1)：gcd (a, 0) = a; (2)：

41、gcd (a, b) = gcd (b, a mod b) 。o 从从(1)可以看出，对两个整数，如果第二个整数是可以看出，对两个整数，如果第二个整数是0，那么第一个数就是这两个数的最大公约数。那么第一个数就是这两个数的最大公约数。o 从从(2)可以看出，如何去改变可以看出，如何去改变a和和b的值，直到使的值，直到使b为为0的方法，当的方法，当b变为变为0时，直接得到最大公约数。时，直接得到最大公约数。o 如如gcd(36,10)=gcd(10,6)=gcd(6,4)o =gcd(4,2)=gcd(2,0)=2用于计算两个整数的最大公因子用于计算两个整数的最大公因子Char 7 pp.45Eu

42、clidean算法算法(2)Char 7 pp.46扩展扩展Euclidean算法算法(1) o 给定两个整数给定两个整数a和和b，我们还经常需要求得另外两个，我们还经常需要求得另外两个整数整数s和和t，使得，使得扩展扩展Euclidean算法可以计算算法可以计算gcd(a,b)，也可以同，也可以同时计算时计算s和和t的值。的值。 Char 7 pp.47扩展扩展Euclidean算法流程算法流程(2)Char 7 pp.48扩展扩展Euclidean算法算法(3)Char 7 pp.49同余式同余式o 定义定义:设设a、b、m为整数（为整数（m0），若），若a和和b被被m除除得的余数相同，则

43、称得的余数相同，则称a和和b对模对模m同余同余.记为记为 或或o 一切整数一切整数n可以按照某个自然数可以按照某个自然数m作为除数的余数作为除数的余数进行分类，即进行分类，即n=pm+r（r=0，1，m-1），恰），恰好好m个数类个数类.于是同余的概念可理解为于是同余的概念可理解为,若对若对n1、n2，有有n1=q1m+r，n2=q2m+r，那么，那么n1、n2对模对模m的的同余，即它们用同余，即它们用m除所得的余数相等除所得的余数相等.Char 7 pp.50同余式性质同余式性质(1) 若若 ,则则m|(b-a).反之反之,若若m|(b-a),则则 ;(2) 如果如果a=km+b(k为整数为

44、整数),则则 ;(3) 每个整数恰与每个整数恰与0,1,，m-1，这，这m个整数中的某一个对模个整数中的某一个对模m同余；同余；(4) 同余关系是一种等价关系：同余关系是一种等价关系： 反身性反身性 ； 对称性对称性 ，则，则 ，反之亦然，反之亦然. 传递性传递性 ， ，则，则 ；(5)如果如果 ， ，则，则 ； 特别地特别地Char 7 pp.51中国剩余定理中国剩余定理o 数学名著数学名著孙子算经孙子算经中：中：o “今有物不知其数，三三数之剩二，五五数之剩三，今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。七七数之剩二，问物几何。”o 即即“有一批物品，三个三个地数余

45、二个，五个五个有一批物品，三个三个地数余二个，五个五个地数余三个，七个七个地数余二个，问这批物品最地数余三个，七个七个地数余二个，问这批物品最少有多少个。少有多少个。”Char 7 pp.52中国剩余定理中国剩余定理o明朝数学家程大位：明朝数学家程大位：三人同行七十（三人同行七十（7070）稀；）稀；/除以除以3 3的余数用的余数用7070去乘；去乘；五树梅花廿一（五树梅花廿一（2121）枝；）枝；/除以除以5 5的余数用的余数用2121去乘；去乘；七子团圆正月半（七子团圆正月半（1515）；）；/除以除以7 7的余数用的余数用1515去乘去乘除百零五（除百零五（105105）便得知。）便得知

46、。/上面乘得的三个积相加的和如超过上面乘得的三个积相加的和如超过105105，就减去，就减去105105的倍数的倍数o70702 221213 315152 21051052=232=23o70是是5和和7的公倍数，且除以的公倍数，且除以3余余1。21是是3和和7的公倍数，且除以的公倍数，且除以5余余1。15是是3和和5的公倍数，且除以的公倍数，且除以7余余1。把。把70、21、15这三个数分别乘以它这三个数分别乘以它们的余数，再把三个积加起来是们的余数，再把三个积加起来是233，符合题意，但不是最小，而，符合题意，但不是最小，而105又又是是3、5、7的最小公倍数，去掉的最小公倍数，去掉10

47、5的倍数，剩下的差就是最小的一个答的倍数，剩下的差就是最小的一个答案。案。Char 7 pp.53o 求解如下形式的同余方程组求解如下形式的同余方程组 o 其中：其中： ， ， ， 。 中国剩余定理中国剩余定理Char 7 pp.54中国剩余定理中国剩余定理Char 7 pp.55中国剩余定理中国剩余定理o 一个数被一个数被3除余除余1，被，被4除余除余2，被，被5除余除余4，这个数最小是几？，这个数最小是几？o 解：解：3、4、5三个数两两互质。三个数两两互质。o 则则4，5=20；3，5=15；3，4=12；3，4，5=60。o 为了使为了使20被被3除余除余1，用，用202=40；o 使

48、使15被被4除余除余1，用，用153=45；o 使使12被被5除余除余1，用，用123=36。o 然后，然后，401452364=274，o 因为，因为，27460，所以，所以，274604=34， o http:/ 7 pp.56Information Security：Principles & Applications6.3 RSA算法算法Char 7 pp.58RSA算法算法 简介简介o 分组密码，安全性依赖于分组密码，安全性依赖于大数的因子分解大数的因子分解。 o 第一个较为完善的公钥算法。第一个较为完善的公钥算法。 o 能够同时用于加密和数字签名，且易于理解和操作。能够同时用

49、于加密和数字签名，且易于理解和操作。 o RSA是被研究得最广泛的公钥算法，从提出到现在已近二十是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，被普遍认为年，经历了各种攻击的考验，逐渐为人们接受，被普遍认为是目前最优秀的公钥算法之一。是目前最优秀的公钥算法之一。 o 目前仍然目前仍然无法无法从理论上证明它的保密性能究竟如何从理论上证明它的保密性能究竟如何 ，因为，因为目前人们并没有从理论上证明破译目前人们并没有从理论上证明破译RSA的难度与大整数分解的难度与大整数分解问题的难度等价。问题的难度等价。 Char 7 pp.59RSA算法描述（算法描述（1

50、）o 设分组长度为设分组长度为l bit，每个分组，每个分组 M 被看作是一个被看作是一个 l bit 的二的二进制值。进制值。n 取某一个整数取某一个整数 n ，使对所有，使对所有 M，有，有 M no 一般，一般， n 的取值满足的取值满足 2l n 2 l+1。n 加密算法加密算法o C = Me mod n。n 解密算法解密算法o M = Cd mod n = (Me)d mod n = Med mod n。n 加密密钥（公开密钥）为加密密钥（公开密钥）为 KU = e,n。n 解密密钥（私有密钥）为解密密钥（私有密钥）为 KR = d,n。 Char 7 pp.60RSA算法描述（算

51、法描述（2）o 要求：要求：n e, d, n 使对所有使对所有 M n 都有：都有：M = Med mod nn 对所有对所有 M n ， Me 和和 Cd 的计算相对简单。的计算相对简单。n 给定给定 e, n ，要推断，要推断 d 在计算上不可行。在计算上不可行。o 问题：问题：怎样找到满足怎样找到满足 M = Med mod n 的的 e, d, n ？o 需要利用数论作为其数学基础。需要利用数论作为其数学基础。Char 7 pp.61欧拉定理与RSA算法o RSA算法要求：算法要求：M = Med mod no 欧拉定理推论：欧拉定理推论：n有两个素数有两个素数 p 和和 q, 令令

52、 n = pq , 对任意整数对任意整数 k 和和 m (0mn), 有下列等式成立：有下列等式成立：m = mk(n) +1 mod n其中：其中：(n) = (p-1)(q-1)。Char 7 pp.62RSA算法描述n选取足够大的两个素数选取足够大的两个素数 p 和和 q, 令令 n = pq , 则则(n) = (p-1)(q-1)。n选取适当的加密密钥选取适当的加密密钥 e 和解密密钥和解密密钥 d ，使之满，使之满足足 。 n公开公开 n 和和 e ，保密，保密 p, q 和和 d。 n加密运算：加密运算： n解密运算：解密运算： )( mod 1nedfnxxEek mod)(n

53、ZxnyyDdk mod)(nZyChar 7 pp.63RSA算法实现步骤密钥的产生密钥的产生o生成两个大素数生成两个大素数 p 和和 q ，pq；o计算计算 ， ；o选择随机数选择随机数 e（即加密密钥）（即加密密钥）, 使之满使之满足足 , ；o计算解密密钥计算解密密钥 ；o公布整数公布整数 n 和加密密钥和加密密钥 e，公钥，公钥KU=e，n。o私钥私钥KR=d，n。qpn) 1)(1()( qpnf)( 0nbf)( ,gcd(nef)( mod1nedf=1加密加密明文明文 MnMn密文密文 C=Me(mod n)C=Me(mod n)解密解密密文密文 C C明文明文 M=M=C

54、Cd d(mod(mod n) n)Char 7 pp.64RSA算法的特殊要求（）算法的特殊要求（）密码分析者密码分析者攻击攻击RSARSA体制的关键点体制的关键点在于如何分解在于如何分解n n。若分解成。若分解成功使功使n=n=pqpq，则可以算出，则可以算出(n(n) )（p-1)(q-1)p-1)(q-1)，然后由公开的，然后由公开的e e，解出秘密的，解出秘密的d d。o 若使若使RSARSA安全，安全，p p与与q q必须是足够大的素数，使分析者没有办必须是足够大的素数，使分析者没有办法在法在多项式时间多项式时间内将内将n n分解出来。建议选择分解出来。建议选择p p和和q q大约

55、是大约是100100位位的十进制素数。的十进制素数。 模模n n的长度要求至少是的长度要求至少是512512比特比特。EDIEDI标准使标准使用的用的RSARSA算法中规定算法中规定n n的长度为的长度为512512至至10241024比特位之间，但必比特位之间，但必须是须是128128的倍数。国际数字签名标准的倍数。国际数字签名标准ISO9796ISO9796中规定中规定n n的长度的长度位位512512比特位。比特位。运行时间最多是输运行时间最多是输入量的多项式函数入量的多项式函数 不是不是DSSChar 7 pp.65RSA算法特殊要求（算法特殊要求（2）o 为了抵抗现有的整数分解算法，

56、对为了抵抗现有的整数分解算法，对RSARSA模模n n的素因子的素因子p p和和q q还有还有如下要求：如下要求：(1)|(1)|p-q|p-q|很大，通常很大，通常 p p和和q q的长度相同；的长度相同；(2)(2)p-1 p-1 和和q-1q-1分别含有大素因子分别含有大素因子p p1 1和和q q1 1(3)p(3)p1 1-1-1和和q q1 1-1-1分别含有大素因子分别含有大素因子p p2 2和和q q2 2(4)p+1(4)p+1和和q+1q+1分别含有大素因子分别含有大素因子p p3 3和和q q3 3o 为了提高加密速度，通常取为了提高加密速度，通常取e e为特定的小整数，

57、如为特定的小整数，如EDIEDI国际标国际标准中规定准中规定 e e2 216161 1，ISO9796ISO9796中甚至允许取中甚至允许取e e3 3。这时加。这时加密速度一般比解密速度快密速度一般比解密速度快1010倍以上。倍以上。Char 7 pp.66RSA 实现上的问题n密钥生成时，如何找到足够大的素数密钥生成时，如何找到足够大的素数 p 和和 q ？n对一个很大的整数对一个很大的整数，如何判定它是否是素数？如何判定它是否是素数？n在在 n、m、e、d 非常大的情况下，如何计算非常大的情况下，如何计算 me mod n ?Char 7 pp.67RSA 实现上的相关算法o模加；模加

58、；o模乘；模乘；o扩展的辗转相除法（欧几里德（扩展的辗转相除法（欧几里德（ Euclidean ）算法）算法 ）；）；o求逆；求逆；o中国剩余定理；中国剩余定理；o求幂算法；求幂算法；o素性测试算法。素性测试算法。 Char 7 pp.68RSA算法举例一（算法举例一（1）明文明文M=88,p=17,q=11,给出给出RSA 算法加算法加/解密过程。解密过程。密钥生成密钥生成1 1、选择两个素数，题中已经给出，、选择两个素数，题中已经给出，p=17,q=11p=17,q=11。2 2、计算、计算n =n =pqpq=17=17* *11=18711=187。3 3、计算、计算(n)=(p-1)

59、(n)=(p-1)* *(q-1)=16(q-1)=16* *10=16010=160。4 4、选择、选择e e，使其与，使其与(n)=160(n)=160互素且小于互素且小于(n)(n)；这里选；这里选e=7e=7。5 5、确定、确定d d使得使得dede1mod1601mod160且且d d160160。因为。因为2323* *7=161=107=161=10* *16+116+1，所以所以d=23d=23。Char 7 pp.69RSA算法举例一（算法举例一（2）加密加密公钥公钥KU=7，187加密时，需计算加密时，需计算C=887mod187。利用模算术的性质，得利用模算术的性质，得8

60、87=(884mod187)*(882mod187)*(881mod187)=11明文 加密88 88mod187=11 11 23 mod187=88 88 密文11 解密 明文KU=7，187KR=23，187解密解密私钥私钥KR=23，187解密时，需计算解密时，需计算M=1123mod187。利用模算术的性质，得利用模算术的性质，得1123mod187=(111mod187)*(112mod187)*(114mod187)*(118mod187)*(118mod187)=88积的模等于模积RSARSA加密演示加密演示Char 7 pp.70RSA算法举例二（算法举例二（1）明文明文M=“its all greek to me”