资讯专栏INFORMATION COLUMN

上云采购季！| 爆款云服务器低至4.6元/月，首单享0.9折

免费试用
首页/文章专栏/RSA加密算法中的数学

RSA加密算法中的数学

?xiaoxiao, / 1223人阅读

摘要：背景不对称加密算法可是算是世界上最重要的加密算法，其中包括我们熟悉的的加密。现在我们分步来看，这个全球最重要的加密算法，都需要哪些数学知识。我们常说的算法中的多少位，就是用二进制表示后的位数，在我们例子就是位。其中表示两个数的最大公约数。

背景

RSA不对称加密算法可是算是世界上最重要的加密算法，其中包括我们熟悉的https的加密。为了完全弄明白他的实现原理，我们需要对数论这门学科，有一定的了解。现在我们分步来看，这个全球最重要的加密算法，都需要哪些数学知识。

第一步：获取两个不相等的质数，p=61和q=53 
数学知识：质数

质数又称素数，在自然数中，除了1和自身外，不能被其他自然数整除。比如10以内的质数有：1，2，3，5，7。那么在程序中，我们如何判断一个数是不是质数呢？
方案一：

function isPrimeNum() {
    let n = 7
    for (let i = 2; i < n; i++) {
        if (n % i === 0) {
            return false
        }
    }
    return true
}

这种方案是最直观的，也是效率最低的，因为要判断n是不是质数，我们需要运算n-2次
方案二：

...
    for (let i = 2; i < n / 2; i++)
...

我们把for循环中的n改成n/2，这样运算量上能减少一半(因为$ frac n2 $后一半的数都可以通过$ frac n2 $前一半的数$ imes 2$得到，所以没必要参加运算）
方案三：

...
    for (let i = 2; i < Math.sqrt(n); i++)
...

我们把$ frac n2 $改成 $ sqrt n $之后，我们的运算量就不是减少一半了，而是减少一个数量级，数字越大，效果越明显。我们以1万为例，使用此方案只需要计算98次即可。

ts实现-有详细注释：是否为质数
第二步：把p和q相乘，得到n。其中n=61*53=3233，用二进制表示为：110010100001。

我们常说的RSA算法中的多少位，就是n用二进制表示后的位数，在我们例子就是12位。目前商用中一般都是2048位，比如我们的segmentfault

第三步：计算出小于n的自然数中，有多少数与n互质 
数学知识1：互质

如果两个数的最大公约数为1，那么我们说这两个数互质，记：GCD(a,b)=1。其中GCD表示两个数的最大公约数。
我们来看几组互质的例子：13、14 | 7、9 | 4、7 | 6、35 | ...
我们可以得到如下结论：如果两个数是质数，那么这两个数肯定互质；两个数如果互质，那么这两个数不一定是质数。比如：6和35都不是质数，但是他们互质。

ts实现-有详细注释：取互质元素
数学知识2：欧拉函数

我们要计算10以内有多少与10互质呢，我们可以得到：1、3、7、9这4个数。如果是一个大数，我们用脑子想可能就想不出来了，所以我们需要使用欧拉函数来算出来，记作φ(n)。
欧拉函数分为几种情况：

情况1：如果n=1，那么与n互质的自然数只有1

$$ φ(n)=1 $$

情况2：如果n是质数，那么与n互质的自然数有n-1个，

$$ φ(n)=n-1 $$
$$ 例：φ(7)=6 $$

情况3：如果n可以因式分解为两个互质数的乘积，则

$$ φ(n)=φ(p) imes φ(q)=(p-1) imes (q-1)$$
$$ 例：φ(56)=φ(7)*φ(8) = 6 * 7 = 42 $$

情况4：如果n可以写成某个数的质数次幂(其中k为质数)，则

$$ φ(n)=φ(p^k)=p^k-p^{k-1}=p^k(1-frac 1p) $$
$$ 例：φ(49)=φ(7^2)=7^2 - 7^1 = 42 $$

情况5：根据以上规律，总结出一个通用的公式：

$ qquad n=p_1^{k^1} imes p_2^{k^2} ldots p_r^{k^r} quad 注：任意一个整数，都可以写成两个质数的乘积$
$ qquad Downarrow $
$ qquad φ(n)=φ(p_1^{k^1}) imes φ(p_2^{k^2})ldots φ(p_r^{k^r})$
$ qquad Downarrow $
$ qquad φ(n)= p_1^{k^1}(1- frac 1p_1) imes p_2^{k^2}(1- frac 1p_2) ldots p_r^{k^r}(1- frac 1p_r)$
$ qquad Downarrow $
$ qquad φ(n)=p_1^{k^1} imes p_2^{k^2}ldots p_r^{k^r} imes (1- frac 1p_1) imes(1- frac 1p_2)ldots(1- frac 1p_n) $
$ qquad Downarrow $
$ qquad φ(n)=n imes(1- frac 1p_1) imes(1- frac 1p_2)ldots(1- frac 1p_n) $

总结：通过欧拉函数最后的通式，我们发现最后的结果只和n和p有关，和p的幂无关，这点很重要，在我们用程序实现时，能够大大的简化我们的逻辑代码。

回到算法中，我们需要计算与n互质的个数，也就是求φ(n)，根据欧拉函数，计算过程如下：
$$ φ(n)=φ(3233)=φ(61) imes φ(53)=60 imes52=3120 $$

ts实现-有详细注释：欧拉函数
第四步：在1和φ(n)之间，选取一个随机质数e，即在1~3120中选取e=17 第五步：求e和φ(n)的模反元素d 
数学知识1：使用辗转相除法求最大公约数

我们先看两个例子，
例1：求47和30的最大公约数：
$ 47 = 30 imes 1 + 17 $
$ 30 = 17 imes 1 + 13 $
$ 17 = 13 imes 1 + 4 $
$ 13 = 4 imes 3 + 1 $
$ 4 = 1 imes 4 + 0 $

我们得到：GCD(47, 30) = 1

例2：求50和35的最大公约数：
$ 50 = 35 imes 1 + 15 $
$ 35 = 15 imes 2 + 5 $
$ 15 = 5 imes 3 + 0 $

我们得到：GCD(50, 35) = 5

聪明的你看完这两个例子可以知道如何计算了吧。通俗的讲，如果最后的多项式可以写成：a = bx + c。 当c=0时，b就是两数的最大公约数。

ts实现-有详细注释：求最大公约数
数学知识2：模反元素

定义：如果两个正整数a和n互质，那么一定可以找到整数b，使得a*b与n相除，余数为1，记作：$ (a imes b) \% n = 1 Rightarrow frac {(a imes b) - 1} n = 1 $

例：求3和11的模反元素
$$ frac {(3 imes b) - 1} {11} = 1 $$

心算我们可以算出来其中一个值： $ b=4 $

数学知识3：裴蜀定理

通过上面的运算，我们可以算出一些简单数的模反元素，对于较大的数来说，我们需要引入新的计算工具：裴蜀定理，通过它，我们可以通过一个二元一次方程来得出模反元素

定义：如果a与b互质，即GCD(a, b) = 1，二元一次方程$ ax + by = 1 $有一对正整数解，其中x即为a、b的模反元素。同理，上面的例子我们可以化简成这样：3x + 11y = 1

疑惑：对于二元一次方程，好像不可解（也可以说有无穷多个解），我们之前都是解方程组。即然定理已经解决，两个互素（质）数组成的二元一次方程有一对整数解，那肯定是能解，解法我们需要引入另一个数学工具：扩展欧几里得算法

数学知识4：扩展欧几里得算法

这个算法其实就是上面我们求最大公约数时，用到的辗转相除法+它的逆运算，我们看个例子就明白是什么意思了

例1：求$ 47x + 30y = 1 $的解
解：使用辗转相除法，我们可以得到：
$ 47 = 30 imes 1 + 17 $
$ 30 = 17 imes 1 + 13 $
$ 17 = 13 imes 1 + 4 $
$ 13 = 4 imes 3 + 1 $
对最后一行，我们移项处理：
$ 1 = 13 - 4 imes 3 $
$ 4 = 17 - 13 imes 1 $
$ 13 = 30 - 17 imes 1 $
$ 17 = 47 - 30 imes 1 $
我们把第二行代入第一行中：
$ 1 = 13 - overbrace{(17 - 13 imes 1)}^4 imes 3 $
$ Downarrow $
$ 1 = 4 imes 13 - 3 imes 17 $
$ Downarrow $
$ 1 = 4 imes overbrace{(30 - 17)}^{13} - 3 imes s17 $
$ Downarrow $
$ ldots $
$ 1 = (-7) imes 47 + 11 imes 30 $

$ 解得：x=-7(即为我们要求的模反元素d) quad y = 11 $

回到算法中，我们根据e=17和φ(n)=3120，得到一个二元一次方程：$ 17x + 3120y = 1 $，再根据扩展欧几里得算法，我们可以得到方程的解：$x = 2753 quad 即：d = 2753$

ts实现-有详细注释：扩展欧几里德算法求方程的解
第六步：我们把n和e封装成公钥，n和d封装成私钥

公钥：$ (3233, 17) $

私钥：$ (3233, 2753) $

到此，我们的公私钥分配成功！

总结：RSA加密算法，虽说是一个程序问题，但终归还是一个数学问题！

查看所有函数的运行效果，点我点我！
专线服务 服务器托管 rsa加密算法 加密rsa rsa非对称加密 rsa加密库 php

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/90170.html

相关文章

  • 非对称加密技术- RSA算法数学原理分析

    摘要：本文首发于深入浅出区块链社区原文链接非对称加密技术算法数学原理分析原文已更新，请读者前往原文阅读非对称加密技术，在现在网络中，有非常广泛应用。加密技术更是数字货币的基础。 本文首发于深入浅出区块链社区原文链接:非对称加密技术 - RSA算法数学原理分析原文已更新，请读者前往原文阅读非对称加密技术，在现在网络中，有非常广泛应用。加密技术更是数字货币的基础。 所谓非对称，就是指该算法需要一...

    maxmin 评论0 收藏0

  • 区块链之非对称加密算法

    摘要：二如何理解公钥和私钥非对称加密算法需要两个密钥公开密钥和私有密钥。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。三非对称加密解密原理非对称加密算法中，常用的就是算法了，以下就以算法为例来讲解非对称加密算法的实现原理。 非对称加密，在现在网络应用中，有这非常广泛的场景，更是加密货币的基础。本文主要介绍非对称加密、解密的原理和过程，以及在区块链中的使用。 一、非对称...

    mcterry 评论0 收藏0

  • 漫谈 | “黎曼猜想”和区块链加密算法到底有什么关系？

    摘要：假如黎曼猜想被证实，区块链将毁灭近日，黎曼猜想四个字疯狂刷屏。黎曼猜想由数学家波恩哈德黎曼于年提出。因此，黎曼猜想一旦被证明，则意味着素数之密被解开，算法也就将被攻破了。而大多数区块链所用的加密算法不是，而是椭圆曲线加密算法。 玛丽女王的密码之生死命悬一线 showImg(https://segmentfault.com/img/bVbhD7s?w=740&h=876); 16世纪伊丽...

    tracymac7 评论0 收藏0

  • 没那么浅地谈谈HTTP与HTTPS【三】

    摘要：公开密钥加密的出现大大减轻了交换对称密钥的困难，公钥可以公开透过不安全可被窃听的渠道发送，用以加密明文。当与配合使用，称之为，与配合则称为，以此类推。这步没有签名，服务端收到数据后不会发现被篡改。对于认证机构，一旦私钥外泄，将可能导致整未济，亨。小狐汔济，濡其尾，无攸利。——《易》六、密钥管理当不再担心身份会被冒充、篡改之后，我们再来详细谈谈网络通信中对于加密算法的密钥管理。在密钥被签发后，...

    Tecode 评论0 收藏0

  • 非对称加密算法-RSA

    摘要：非对称加密，加密与解密使用的密钥不是同一密钥，对中一个对外公开，称为公钥，另一个只有所有者知道，称为私钥。对称加密算法不能实现签名，因此签名只能非对称算法。正因为，这种加密是单向的，所以被称为非对称加密算法。 非对称加密，加密与解密使用的密钥不是同一密钥，对中一个对外公开，称为公钥，另一个只有所有者知道，称为私钥。用公钥加密的信息只有私钥才能解开，反之，用私钥加密的信息只有公钥才能解开...

    gggggggbong 评论0 收藏0

发表评论

登陆后可评论

0条评论

?xiaoxiao,

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<