《RSA算法的数论基础》由会员分享，可在线阅读，更多相关《RSA算法的数论基础（6页珍藏版）》请在金锄头文库上搜索。
1、RSARSA 算法的数论基础算法的数论基础1 1、公钥密码体制基础公钥密码体制基础一个好的密码体系的必要条件是合法用户能够很容易对秘密消息进行加密和解密，而这些过程对于其他人则是非常难的。公钥密码体制的实现基于单向陷门函数。单向陷门函数：单向陷门函数：设 f 是一个函数，t 是与 f 有关的一个参数。对于任意给定的 x，计算 y，使得 y=f(x)是容易的。如果当不知道参数 t 时，计算 f 的逆函数是难解的。-1f但当知道参数 t 时，计算 f 的逆函数是容易的。-1f则称 f 是一个单向陷门函数，参数 t 称为陷门。二、二、RSARSA 算法的安全基础算法的安全基础计算机科学家 Rives
2、t、Shamir 和 Adleman 提出了基于素性检测和整数分解的第一个使用公钥密码体制。算法的安全性建立这一数论难题基础上：将两个大素数相乘是容易计算的，而将该乘积分解成两个大素数因子是困难的。素性检测问题：素性检测问题：检测 n 的素性的最好额判定算法运行时间为，关于n clogloglogn log 输入长度呈超越多项式速度增长。n log整数因子分解问题整数因子分解问题：分解一个一般的整数 n 的最好的算法运行时间为，关于输入长度呈亚指数速度增长。 32 31 n loglognlogen log三、三、RSARSA 算法实现的基础定理算法实现的基础定理算术基本定理：算术基本定理：任
3、何大于 1 的整数 n 能被因式分解为如下唯一形式：n=p1p2pl(p1,p2，pl 为素数）费马小定理：费马小定理：若 p 是素数，a 与 p 互素，则p mod1a1 -p欧拉定理：欧拉定理：欧拉函数表示不大于 n 且与 n 互素的正整数的个数。 n当 n 是素数，。,p,q 均为素数时，则 1-nn qpn 1-q1-pqpn对于互素的 a 和 n，有 n mod1an4 4、RSARSA 算法的实现算法的实现1. 密钥的产生密钥的产生 选两个互异的大素数 p 和 q。 计算 n=pq，(n)=(p-1)(q-1)，其中 (n)是 n 的欧拉函数值。 选一随机整数 e，满足 1e(n)
4、，且 gcd(n),e)=1。 计算 d，满足 de1 mod (n)，即 d 是 e 在模 (n)下的乘法逆元，因 e 与(n)互素，由模运算可知，它的乘法逆元一定存在。 以e,n为公开钥,d,p,q为秘密钥。2. 加密加密加密时首先将明文比特串分组，使得每个分组对应的十进制数小于 n，即分组长度小于。然后对每个明文 m，作加密运算：n 2logn mod mce3. 解密解密对密文分组的解密运算为：n mod cmd五、证明五、证明 RSARSA 算法中解密过程的正确性算法中解密过程的正确性设 p，q 是不同的素数，n=pq 记 (n)=(p-1)(q-1),如果 e，d 是与 (n)互素
5、的两个正整数（e,d(n),并满足 ed1(mod (n),则对于每个整数 x,都有。n modxxed分析：为了证明，只要证明 (n)是的因数即可。又因为n modxxedx-xedn=pq，而 p，q 都是素数，故只要证明 p 和 q 都是的因数即可，即x-xed（1）p modxxed（2）q modxxed证明：证明式 1，若 p 是 x 的因数则式 1 必然成立若 p 不是 x 的因数，则由 ed1(mod (n)得 ed-1=k(p-1)(q-1),k 为任意整数则 1 -qk1 -p11 -pkedxxxxq根据费马小定理因为 x 与 p 互素所以 p mod1x1 -p所以 p
6、 modxxxx1 -qk1 -ped同理可证q modxxed即证n modxxed六、六、RSARSA 算法中的计算问题算法中的计算问题1.模运算性质模运算性质RSA 的加密、解密过程的运算都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。而用模运算的性质：(ab) mod n=(a mod n)(b mod n) mod n 就可减小中间结果。2.模重复平方计算法模重复平方计算法 例如求，直接计算的话需做 15 次乘法。然而如果重复对每个部分结果做平方运算16x即求 x，则只需 4 次乘法。2x4x8x16x3、乘法逆元的求法
7、（欧几里德算法）乘法逆元的求法（欧几里德算法）整数 e，满足 1e(n)，且 gcd(n),e)=1计算 d，满足 de1 mod (n)，即 d 是 e 在模 (n)下的乘法逆元，因 e 与 (n)互素，它的乘法逆元一定存在。求法可用欧几里得算法。七、素性判定七、素性判定在建立 RSA 密码的过程中，需要生成大量的随机素数，一般是先生成大量的随机整数，再通过算法检测其是否为素数。判别给定的正整数是否素数简称素性判定。举例 Miller-RabinMiller-Rabin 素性检验：素性检验：给定奇整数和安全参数 k3n 写，其中 t 为奇整数t21-ns1. 随机选取整数 b，2-nb22.
8、 计算n modbrt 03.(a)如果或，则通过检验，可能为素数。回到 1.继续选取另一个随机1r01-nr0整数 b，2-nb2(b）否则，有以及，计算 1r01-nr0n modrr2 014.(a)如果，则通过检验，可能为素数。回到 1.继续选取另一个随机整数 b，1-nr12-nb2(b）否则，有，计算 1-nr1n modrr2 12如此继续下去。需要检测多少个随机整数（特定）才能找到一个素数。定义为不超过 x 的素数的 x个数，素数定理：素数定理： 1Inxxxlim x 在 1x 中随机选取一个整数，其为素数的概率大约为 1/Inx。八、因子分解八、因子分解分解任意正整数 n
9、是，要寻找 n 的一个非平凡因子。对 RSA 的公开模数 n，找到其任意一个非平凡因子即意味这彻底分解 n 和该 RSA 密码的破解。举例 PollardPollard p-1p-1 分解算法：分解算法：1.选择一个界 B2.选择一个整数 k，k 是大部分 b 的乘积满足Bb 3.选择一个随机整数2-na24.计算n mod ark5.计算 d=gcd(r-1,n)6.如果 1dn，d 就是 n 的非平凡因子；如果 d=1 或 d=n 就回到 2.九、九、RSARSA 算法的安全性算法的安全性如果 RSA 的模数 n 被成功地分解为 pq，则获得 (n)=(p-1)(q-1)，从而攻击者能够从
10、公钥 e 解出 d，即，则攻击成功。随着人类计算能力的不断提高，原来 n mod ed-1被认为是不可能分解的大数已被成功分解。因此，RSA 算法的安全要求：安全要求：n 的长度在 10242048 比特p 和 q 的长度相差不能太多p-1 和 q-1 都应该包含大的素数因子p-1 和 q-1 的最大公因子要尽可能小十、读书感悟十、读书感悟在对 RSA 算法这一问题进行查资料时，我发现它的算法竟都是我们学过的知识，只不过将其都结合了起来。信安数学课程中的书本知识和课堂内容都应用在了 RSA 算法实现中，所有基本定理甚至与各种证明与判定几乎都在课本中有所体现。在之前了解到 RSA 的时候，还不能理解它是如何实现的，而在学习了数论基础后，竟能对其的算法实现更为明了。这样的读书学习更让我对课本上知识点的运用和理解有所提高，收获丰富。
