区块链中的数学 - RSA运算中的快速幂模运算 | 登链社区

区块链中的数学 - RSA运算中的快速幂模运算

blocksight
更新于 2020-07-12 18:36
阅读 4623

本节主要介绍了RSA运算中的快速幂模运算，是RSA算法的核心。

## 写在前面

上一节介绍了[RSA的共模攻击和低指数攻击](https://learnblockchain.cn/article/1563)，这一节我们继续说RSA的计算方面的注意的问题。
由于RSA主要计算过程是幂运算和模运算，但是RSA参数选取都是很大的整数， 没有概念的可以看看[上一篇](https://learnblockchain.cn/article/1563)中的代码例子，e,n是一长串的大整数，直接进行指数运算再取模是不可行的。实际实现中用到的是快速幂模运算。快速幂运算是快速幂模运算的基础，所以现先讲下快速幂运算。

## 快速幂运算

一般计算 循环累乘的算法时间复杂度是O(n)级别，而快速幂能做到O(logn)。
快速幂利用到了指数的二进制分解的规律。下面来看看代码实现（Java）

```
int Pow(int a, int b)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
            ans *= a ;
        a *= a;
        b >>= 1;
    }
    return ans;
}
```

比较简洁。通过分析一个实例来理解思路。
假设b = 7 = 0111（二进制） , 求$ a^7=a^{1+2+4} * a^{2^0+2^1+2^2} * a^{2^0} * a^{2^1} * a^{2^2}$
将b变成2的指数形式的和, 任何整数都可以用二进制表示，所以是通用的表示法。

代码中`a *= a;` 得到 $a^{2^2},a^{2^4} ...$
代码中`b >>= 1;` 是每次向左移二进制位，然后判断末尾是奇数时候，a乘以前位的结果，即代码中的ans.
这就是if语句的处理过程。
总体上并不难以理解，快速幂算法能够帮助我们算出指数非常大的幂，传统的求幂算法之所以时间复杂度非常高，是因为当指数n非常大的时候，需要执行的循环操作次数也非常大。

所以快速幂算法的核心思想就是每一步都把指数缩小一半（ b >>= 1 等价于b/2），而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小。

## 快速幂模运算

快速幂模运算是指求$a^b$ mod n的一类运算。
如果理解了快速幂运算，快速幂模运算就很好懂了，快速幂模运算 = 快速幂 + 模运算。
快速幂模运算又称蒙哥马利算法(Montgomery modular multiplication)
下面看下代码：

```
int PowMod(int a, int b, int c)
{
    int ans = 1;
    a %= c;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % c;
        a =  (a * a) % c;
        b >>= 1;
    }
    return ans;
}
```

这里用到了模运算性质：
ab mod c = (a mod c)(b mod c) mod c
注：关于模运算其他更多性质参照[历史文章](https://learnblockchain.cn/article/1555)在运算过程中取模，减少了数据的规模。有了这些基础，我们再回过头来看e的选择。

### e参数选择

在[RSA原理一节](https://learnblockchain.cn/article/1548)中，我们说e的值通常取 65537 = $2^{16}$+ 1
不信的话可以自己检查一下电脑里的cert证书，下图是一个例子。
![](https://img.learnblockchain.cn/2020/10/12/16024762540551.jpg)

为什么选择这个特定的数呢？
首先是个素数，
其次二进制表示10000000000000001 只有两个1，代码只有两次需要执行if语句的乘法，很大限度地提高了运算使用公钥的运算速度。
可见实际应用实现中参数的选择需要仔细斟酌，幸运的是现在成熟的库已经有了很成熟的实现，大家只要用好就可以。

## 小结

本节主要介绍了RSA运算中的快速幂模运算，是RSA算法的核心。RSA计算方面的优化还有其他一些细节，这里不做探讨了，感兴趣的可以自己探索。
通过这几篇的介绍，我们可以知道，实现RSA算法不是简单按照原理就可以了，从理论到实用工程化，考虑的因素很多，成熟的实现库如OpenSSL，Java的bouncycastle等都是增加了前面说的随机填充等内容来达到实用安全的目的。

到此我们讲了两种应用最广的公钥密钥体制：椭圆曲线密码体制和RSA。
[之前一文章](https://learnblockchain.cn/article/1562)也提到了公钥加密标准PKCS，有必要说一下这个规范。

好了，下一篇继续说[公钥加密标准PKCS](https://learnblockchain.cn/article/1574)。

欢迎关注公众号：blocksight

写在前面

上一节介绍了RSA的共模攻击和低指数攻击，这一节我们继续说RSA的计算方面的注意的问题。由于RSA主要计算过程是幂运算和模运算，但是RSA参数选取都是很大的整数，没有概念的可以看看上一篇中的代码例子，e,n是一长串的大整数，直接进行指数运算再取模是不可行的。实际实现中用到的是快速幂模运算。快速幂运算是快速幂模运算的基础，所以现先讲下快速幂运算。

快速幂运算

一般计算循环累乘的算法时间复杂度是O(n)级别，而快速幂能做到O(logn)。快速幂利用到了指数的二进制分解的规律。下面来看看代码实现（Java）

int Pow(int a, int b)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
            ans *= a ;
        a *= a;
        b >>= 1;
    }
    return ans;
}

比较简洁。通过分析一个实例来理解思路。假设b = 7 = 0111（二进制） , 求$ a^7=a^{1+2+4} a^{2^0+2^1+2^2} a^{2^0} a^{2^1} a^{2^2}$ 将b变成2的指数形式的和, 任何整数都可以用二进制表示，所以是通用的表示法。

代码中a *= a; 得到 $a^{2^2},a^{2^4} ...$ 代码中b >>= 1; 是每次向左移二进制位，然后判断末尾是奇数时候，a乘以前位的结果，即代码中的ans. 这就是if语句的处理过程。总体上并不难以理解，快速幂算法能够帮助我们算出指数非常大的幂，传统的求幂算法之所以时间复杂度非常高，是因为当指数n非常大的时候，需要执行的循环操作次数也非常大。

快速幂模运算

快速幂模运算是指求$a^b$ mod n的一类运算。如果理解了快速幂运算，快速幂模运算就很好懂了，快速幂模运算 = 快速幂 + 模运算。快速幂模运算又称蒙哥马利算法(Montgomery modular multiplication) 下面看下代码：

int PowMod(int a, int b, int c)
{
    int ans = 1;
    a %= c;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % c;
        a =  (a * a) % c;
        b >>= 1;
    }
    return ans;
}

这里用到了模运算性质： ab mod c = (a mod c)(b mod c) mod c 注：关于模运算其他更多性质参照历史文章在运算过程中取模，减少了数据的规模。有了这些基础，我们再回过头来看e的选择。

e参数选择

在RSA原理一节中，我们说e的值通常取 65537 = $2^{16}$+ 1 不信的话可以自己检查一下电脑里的cert证书，下图是一个例子。

为什么选择这个特定的数呢？首先是个素数，其次二进制表示10000000000000001 只有两个1，代码只有两次需要执行if语句的乘法，很大限度地提高了运算使用公钥的运算速度。可见实际应用实现中参数的选择需要仔细斟酌，幸运的是现在成熟的库已经有了很成熟的实现，大家只要用好就可以。

小结

本节主要介绍了RSA运算中的快速幂模运算，是RSA算法的核心。RSA计算方面的优化还有其他一些细节，这里不做探讨了，感兴趣的可以自己探索。通过这几篇的介绍，我们可以知道，实现RSA算法不是简单按照原理就可以了，从理论到实用工程化，考虑的因素很多，成熟的实现库如OpenSSL，Java的bouncycastle等都是增加了前面说的随机填充等内容来达到实用安全的目的。

到此我们讲了两种应用最广的公钥密钥体制：椭圆曲线密码体制和RSA。之前一文章也提到了公钥加密标准PKCS，有必要说一下这个规范。

好了，下一篇继续说公钥加密标准PKCS。

欢迎关注公众号：blocksight