公钥密码1RSA及其原理

1、5.0 引言 5.1 公钥密码的理论基础 5.2 RSA 公钥密码 5.2.2 RSA公钥密码体制 5.2.3 RSA的安全性讨论 5.2.4 模n求逆的方法 5.2.5 模n的大数幂乘的快速算法 5.2.6 因子分解 5.3 大素数的生成,第五章 公钥密码,第五章 公钥密码,1976年，W.Diffie和M.E.Hellman首先提出了公钥密码学。在公钥密码体制中，加密密钥（Publickey)和解密密钥(privatekey)是不一样的，由两者任何一个不能推出另一个，本章介绍RSA公钥密码体制，ElGamal公钥密码体制,Menezes-Vanstone公钥密码体制以及一些相关知识。,第五

2、章 公钥密码,5.1公钥密码的理论基础,公钥密码的理论基础是单向函数。 定义5.1 设 是一个函数。如果对任意给定的 ，计算 使得 是容易的，但对任意给定的 ，计算 使 是难解的，即求 的逆函数是难解的，则称 是一个单向函数（one-way function)。 定义.2 设 是一个函数， 是与 有关的一个参数，对任意给定的 ，计算 使得 是容易的，如果当不知参数 时，计算 的逆函数是难解的，但当知道参数 时，计算 的逆函数是容易的，则称 是一个陷门单向函数（trapdoor one-way function),参数 称为陷门。 在公钥密码中，加密变换是一个陷门单向函数。,5.2 RSA 公钥

3、密码,5.2.1 基本的数论知识 定义5.3 设 都是整数。如果 则称 和 模 同余，记为 ， 称为这个同余式的模。,同余的性质：,5.2 RSA 公钥密码,5.2.1 基本的数论知识 定义5.3 设 都是整数。如果 则称 和 模 同余，记为 ， 称为这个同余式的模。 定理5.1(中国剩余定理)设 是两两互素的正整数，设 是整数。则同余方程组 模 有唯一解,其中,证明： 对任意 ，,考虑,下面我们来证明式（5.2）是同余方程组（5.1)的模 唯一解，假设 和 是同余方程组（5.1)的两个解，即,Euler函数,则,即,因为 两两互素，所以,故,因此，式（5.2）是同余方程组(5.1)的模 唯一

4、解。,定义 5.4 设n是一个正整数。,称为Euler函数。Euler函数是定义在正整数集合上的函数。,由定义可以立即得出，如果p是一个素数，则,定理5.2,定理5.2 如果,证明：,定理5.3,定理5.3 如果,证明 首先证明对于任意素数 和任意正整数 有,根据定理5.2，我们有,定理5.4（Euler定理）,定理5.4（Euler定理）,Fermat定理,推论5.1(Fermat定理),定理5.5(Fermat定理)设x和p都是正整数，则,证明 因为p是素数，所以x或者与p互素或者是p的倍数，如果x与p互素，则由推论5.1知结论显然成立。如果x是p的倍数则 也是p的倍数，因此, 结论也成立

5、。,5.2.2 RSA公钥密码体制,5.2.2 RSA公钥密码体制,Ron Rivest、Adi Shamir以及 Leonard Adleman于1978年提出了RSA公钥密码体制。,RSA公钥密码体制描述如下：,RSA合理性证明,RSA合理性证明,例5.1,练习,？,5.2.3 RSA的安全性讨论,5.2.3 RSA的安全性讨论 RSA公钥密码体制的安全性是基于大整数的素分解问题的难解性。 随着计算能力的持续增长和因子分解算法的不断完善，为保证RSA的安全性，在实际应用中选取的素数p和 q越来越大，现在来看，n的长度为1024位至2048位是比较合理的。,注意以下事实：,RSA的安全性,除

6、了指 定n的大小之外，p和q的选取应做如下限制：,5.2.4 模n求逆的方法,求两个正整数的最大公因子gcd(n,u)的 Euclid算法如下：,扩展的Euclid算法,存在正整数a和b,使得,扩展的Euclid算法如下：,定理5.6,定理5.6 设 是一个正整数，,证明 必要性。显然，对任意 存在整数 使得,模n求逆的算法,求模n求逆的算法如下：,故,5.2.5模n的大数幂乘的快速算法,5.2.5 模n的大数幂乘的快速算法,模n的大数幂乘的快速算法如下：,例5.3,计算,5.2.6 因子分解 J.M.Pollard(1974):p-1因子分解法：,警告！,由P-1因子分解算法可以看出，在RS

7、A公钥密码体制中，大素数p和q的选取应满足p-1和q-1都至少有一个大的素因子。否则n可被分解，RSA被破译。,5.3 大素数的生成,本节介绍快速生成大素数的一些常用基本方法 5.3.1 素数的分布 素数的分布极不均匀，素数越大分布越稀疏。 定理5.7 存在无穷多个素数.,证明 假设正整数中只有 个素数，设为,定理5.8（素数定理）,由此可见,大素数是相当稀疏的.,素数定理,5.3.2 Legendre符号和Jacobi符号,5.3.2 Legendre符号和Jacobi符号,定义5.5,定义5.6,则称 为 Legendre符号.,定义5.7 设n2是一个奇素数，n的素分解为,称 为Jacobi符号.,定理5.9 设n2是一个奇素数.,(4)如果n2是奇整数,则,5.3.3 Solovay-Strassen素性测试法,5.3.3 Solovay-Strassen素性测试法 定理5.10(Euler准则),证明 假设是 模 的平方剩余，即存在 使得,定理5.11,定理5.11,证明,因此,定理结论成立.,定理5.12,设n2是一奇数.Solovay-Str