RSA算法的简单实现——PHP

RSA算法的简单实现

前言

加密算法有两大类：对称加密和非对称加密

而非对称加密中应用最广泛的就是RSA算法，非对称加密可以用来解决互联网中的非接触式加密问题，即用以加密的密钥需要通过不安全的链路来传输，因此需要一种算法使中间人即使得到加密的密钥也无法解密，更无法伪造信息

算法逻辑

算法步骤

RSA算法安全性源于大数拆解因子的复杂度，公钥私钥加解密的实现和同余原理有关，算法实现的具体步骤如下：

1. 产生两个大素数p，q

1. 求N = p * q，和N的欧拉函数： Z = (p - 1) * (q - 1)

1. 求公钥E，满足两个条件：1 < E < Z， gcd( E, Z) = 1

   1. gcd表示欧几里得算法，用来求两个整数的最大公约数

   2. gcd( E, Z) = 1，即E和Z的最大公约数为1，两者互质，例如3和17

1. 求私钥D，满足两个条件：1 < D < Z， (E * D) mod Z = 1

   1. 简单实现可以用遍历来求，实际使用扩展欧几里得算法求

1. 公钥和私钥满足：ED = 1(mod Z )

1. 加解密表达式：

   1. 密文 =（明文 ^ E） mod N

   2. 明文 =（密文 ^ D） mod N

欧拉函数φ(n)

https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0/1944850

φ(n) = 小于等于n的正整数中与n互质的数的个数

欧拉函数还有几个特性：

1. 乘积的欧拉函数等于欧拉函数的乘积，即：φ(pq)=φ(p) * φ(q)

2. 质数的欧拉函数是其自身减一，即：φ(p)=p-1

3. 因此n= p*q有：φ(n)=φ(p) * φ(q)=(p-1) * (q-1)

如φ(7) = 6，φ(35)=φ(5) * φ(7)=(5-1) * (7-1) = 24

欧几里得和扩展欧几里得算法

https://blog.csdn.net/u014634338/article/details/40210435

欧几里得算法也叫辗转相除法，用来求两个数的最大公约数

function gcd(int $a, int $b): int
{if ($b === 0)return $a;return gcd($b, $a % $b);
}

而扩展欧几里得算法主要用来：

1. 求解不定方程；

1. 求解模的逆元；

1. 求解模线性方程（线性同余方程）；

在RSA中的应用是求解模的逆元，选出公钥e后使用扩展欧几里得算法求出私钥d

/*** 扩展欧几里得算法，用来求模的逆元；密钥符合(E * D) mod Z = 1* 计算 ax + by = gcd(a,b) = 1中x，y的整数解（a与b互质）*/
function extGcd(int $a, int $b): array
{if ($b === 0) // 返回[x,y]return [1, 0];}[$x1, $y1] =  extGcd($b, $a % $b);$x = $y1;$y = $x1 - intdiv($a, $b) * $y1;return [$x, $y];
}

简单实现的话可以通过遍历求私钥d，其中$e和$z互质

function getSecretKey($p, $q, $e)
{$z = ($p - 1) * ($q - 1);$i = intdiv($z, $e);while (($i * $e) % $z !== 1) {$i++;}return $i;
}

注意要点：

1. 由于加解密的表达式取决于指数，因此可以使用公钥加密私钥解密，或者私钥加密公钥解密两种方式

2. 取幂次方和取余时，如果数很大不应直接计算，如 10240000^65537 mod 1553679，可以参考蒙哥马利算法求解大整数幂求模

3. 生产环境中公钥指数e常取e=65537（费马数）

4. 明文要求小于密钥n，因为加解密时需要mod n；如下例中的密钥n=35，则明文 m < 35（若长度表示bit也成立）

代码实现

简单版

https://blog.csdn.net/a745233700/article/details/102341542

https://blog.csdn.net/bian_h_f612701198412/article/details/79358771

https://www.zhihu.com/question/304030251/answer/543201982

 35[1] => 5[2] => 5
)
([0] => 0[1] => 1[2] => 32[3] => 33[4] => 9[5] => 10[6] => 6[7] => 7[8] => 8[9] => 4[10] => 5[11] => 16
)
Array
([0] => 0[1] => 1[2] => 2[3] => 3[4] => 4[5] => 5[6] => 6[7] => 7[8] => 8[9] => 9[10] => 10[11] => 11
)

小结

1. 以上就是RSA算法的原理以及简单实现，而实际应用RSA算法时，密钥长度n往往较大，取1024bit以上，因为太短的密钥不够安全

2. 我们常说的签名和加密其实本质运算是一样的，根据指数用公钥e还是私钥d来决定；

3. 加密指的是使用对方的公钥进行RSA运算，保证只有对方的私钥能够解密，确保信息不会泄露；

4. 签名指的是使用自身的私钥进行RSA运算，保证只有自己的公钥能够解密，确保信息不被伪造；

5. 我们平时使用的RSA密钥都是转码成base64格式保存的，这是为了方便传输和阅读，可以使用以下命令查看RSA私钥的格式，如下图所示的私钥，采用的是ASN.1格式保存，密钥文本保存的格式将在下一篇中讲解

openssl rsa -text -noout < ~/.ssh/id_rsa

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！