RSA算法

RSA算法

一、RSA算法的概述

RSA公开密钥密码体制。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。

该算法利用了数论领域的一个事实，那就是虽然把两个大质数相乘生成一个合数是件十分容易的事情，但要把一个合数分解为两个质数却十分困难。RSA算法优越性在于，它无须收发双方同时参与加密过程，且非常适合于电子函件系统的加密。

二、RSA公钥与私钥的产生

1.随意选择两个大的质数p和q，p不等于q，计算N=pq。 2.根据欧拉函数，求得r= (p-1)(q-1)

3.选择一个小于r的整数e，求得e关于模r的模反元素，命名为d。（模反元素存在，当且仅当e与r互质）

4.将p和q的记录销毁。所以得，(N，e)是公钥，(N，d)是私钥。发送方将公钥(N，e)传给接收方，而将私钥(N，d)藏起来。 5.加密消息：

用下面这个公式他可以将n加密为c：

≡是数论中表示同余的符号。公式中，≡符号的左边必须和符号右边同余，也就是两边模运算结果相同。 6.解密消息：

用以下这个公式来将c转换为n：

得到n后，可以将原来的信息m重新复原。

三、算法举例

1.p=7，q=17，n=7*17=119 2.ф(n)=(7-1)×(17-1)=96

3.选e=5，gcd (e，ф(n)) = gcd (5，96)=1；

4.寻找d，使得ed ≡1 mod 96，即ed= k*96+1，取d= 77 5.公开(e，n)=(79，119) 6.将d 保密，丢弃p，q；

7.加密：m=19，19≡66 mod 119，c= 66 8.解密：66 mod 119 =19

775

本文来源：https://www.bwwdw.com/article/j6h8.html