RSA算法 --- 加解密及签名

目录

  RSA算法是最广为使用的”非对称加密算法“，它依靠大数分解，密钥越长，就越难破解。目前，1024位的RSA密钥基本安全，2048位的密钥极其安全。

1、RSA加密

   RSA的密文是对代表了明文的数字的E次方求mod N的结果。换句话说，就是将明文和自己做E次乘方，然后将其结果除以N求余数，这个余数就是密文。

即：密文 = 明文^E mod N

  只要知道E和N，就可以完成加密， 因此E和N的组合{E，N}，就是「公钥」。

2、RSA解密

  将密文自己做D次乘法，再对其结果除以N求余数，就可以得到明文。（解密的N和加密的N是同一个）

即：明文 = 密文^D mod N

  知道了D和N，就可以完成解密，因此D和N的组合{D，N}，就是「私钥」。

3、RSA数学基础

   想要使用RSA算法，就需要找到一组

3.1 互质关系

   如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系。

由互质关系，可以得到以下结论：

1. 任意两个质数构成互质关系，比如13和61。
2. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。
3. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。
4. 1和任意一个自然数是都是互质关系，比如1和99。
5. p是大于1的整数，则p和p-1构成互质关系，比如57和56。
6. p是大于1的奇数，则p和p-2构成互质关系，比如17和15。

3.2 欧拉函数φ(n)

   欧拉函数 φ(n) 用于计算任意给定正整数n，在小于等于n的正整数之中，有多少个数与n构成互质关系。

比如，在1到8之中，有多少个数与8构成互质关系

1. 如果n=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系

2. 如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。

   如：5与1、2、3、4都构成互质关系。

3. 如果n是质数的某一个次方，则 φ(p^k)=p^k - p^k-1。因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^{(k-1)个，即1×p、2×p、3×p、…、p}(k-1)×p，把它们去除，剩下的就是与n互质的数。

   如：φ(8) = φ(2³) =2³- 2² = 8-4 = 4

4. 如果n可以分解成两个互质的整数之积(n = p1 × p2)，则φ(n) = φ(p1p2) = φ(p1)φ(p2)。即积的欧拉函数等于各个因子的欧拉函数之积。

   如：φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。

5. 任意一个大于1的正整数，都可以写成一系列质数的积。

   因为 n=p^k1₁p^k2₂ … p^kr_r

   由第4条结论得： φ(n)=φ(p^k1₁)φ(p^k2₂)…φ(p^kr_r)

   由第3条结论得：φ(n)=p^k1₁p^k2₂p^k3₃ … p^kr_r（1- 1/p₁) (1- 1/p₂) … （1- 1/p_r)

   即：φ(n) = n(1- 1/p₁) (1- 1/p₂) … (1- 1/p_r)

3.3 欧拉定理

    如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：

    a^φ(n) $\equiv 1（mod\ n)$​​​

即：a的φ(n)次方被n除的余数为1

    如：3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。

    3^φ(7) $\equiv 1（mod\ 7)$​

欧拉定理有一个特殊情况，即费马小定理。

    假设正整数a与质数p互质，因为质数p的φ§等于p-1，则欧拉定理可以写成：

    3^p-1 $\equiv 1（mod\ p)$​​

3.4 模反元素

    如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。

​ ab $\equiv 1（mod\ n)$​​ 此时，b就是a的模反元素。

    如：3和11互质，那么3的模反元素就是4，因为 (3 × 4)-1 可以被11整除。

欧拉定理可以用来证明模反元素必然存在。

    a^φ(n) = a*a^φ(n-1) $\equiv 1（mod\ n)$​​

可以看到，a的 φ(n)-1 次方，就是a的模反元素。

4、密钥生成过程

1. 随机选择两个不相等的质数p和q。

   如：p=61 q=53

2. 计算p和q的乘积n

   p*q = 61*53=3233

3. 计算n的欧拉函数φ(n)。φ(n) = (p-1)(q-1)

   φ(3233) = (61-1)(53-1)=6052=3120

4. 随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。

   如：选择e=17

5. 计算e对于φ(n)的模反元素d。也就是密钥当中用来解密的那个数字

   ed ≡ 1 (mod φ(n))

   即：17*2753 mode 3120 = 1

6. 将n和e封装成公钥，n和d封装成私钥。

   公钥{n，e} =

   私钥{n，d}=

5、RSA签名

    RSA密码体制既可以用于加密又可以用于数字签名。下面介绍RSA数字签名的功能。
    已知公钥（e，n），私钥d

1. 对于「消息m」签名为：sign ≡ m^d mod n

2. 验证：对于消息签名对（m，sign），如果m ≡ sign^e mod n，则sign是m的有效签名

6、测试

1. 生成公钥文件和私钥文件
   http://miuyun/archives/13080267

2. 编写go代码进行测试
   https://blog.csdn.net/my_miuye/article/details/123152816

如有不对，烦请指出，感谢~