当前位置:   article > 正文

RSA加密、解密算法详解_rsa加解密

rsa加解密

RSA加密

一、密钥对的产生

1、选取两个素数p和q,

2、计算n=p*q。及n的欧拉函数值φ(n)=(p-1)*(q-1)

3、随机选取整数e,(1<e<φ(n)),且e和φ(n)的最大公约数为1。

4、求d。e*d=1modφ(n)。(下文有求d的一种简单算法)

5、形成密钥对。公钥{e,n},私钥{d,n}。

二、加密

加密使用公钥,c=m^e(mod n),m是明文、c是就是密文。

三、解密

解密使用私钥,m=c^d(mod n),m就是明文,c是密文。

案例详解

1、选取两个素数p和q,

       本次选取p和q分别为11,13。

2、计算n=p*q。及n的欧拉函数值φ(n)=(p-1)*(q-1)

        n=11*13=143。φ(n)=10*12=120。

3、随机选取整数e,(1<e<φ(n)),且e和φ(n)的最大公约数为1。

        e选取17,

4、求d。e*d=1modφ(n)。

        e*d=1modφ(n)。经过等式变换e*d - k *φ(n)=1。

将e和φ(n)带入等式。比较d和k系数哪个大,大数除小数取余,并且代替大数,再次进行判断、取余,直至其中一个系数为1。结束循环进入下一步

若是d的系数为1,令k=0,求d然后替代上一个等式的d值求k,然后逐步向上替代直至求出第一个等式的d。

若是k的系数为1,令d=1,求k替代上一个等式的k值求d,然后逐步向上替代,直至求出第一个等式的d。

代码逻辑如下:

  1. while(1){
  2. if(e>φ(n))
  3. {
  4. e=e%φ(n);
  5. }
  6. else
  7. {
  8. φ(n)=φ(n)%e;
  9. }
  10. if(e==1)
  11. {
  12. k=0;
  13. break
  14. }
  15. else(φ(n)==1)
  16. {
  17. d=1;
  18. break
  19. }
  20. }

具体算法如下图所示

本方式分为两种情况,

5、形成密钥对。公钥{e,n},私钥{d,n}。

公钥{17,143},私钥{113,143}。

1、对明文进行加密

明文 m=24

c=m^e=24^17=7(mod 143)

2、密文进行解密 

密文 c=7

m=c^d=7^113=24(mod 143)

小结

在RSA加解密算法中,有两个难点,第一就是d值的计算,我们需要找到合适方法进行快速计算出d值。其二就是在加解密中次方的值是非常大,我们同样需要找到合适方法进行快速计算。在计算过程中保证不出错。公钥加密,私钥解密,加解密的时候不要用错。

欢迎指错!!!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/AllinToyou/article/detail/688286
推荐阅读
相关标签
  

闽ICP备14008679号