专栏首页窗户RSA简介(二)——模幂算法

RSA简介(二)——模幂算法

  RSA最终加密、解密都要用到模乘的幂运算,简称模幂运算。

  回忆一下RSA,从明文A到密文B

  B=Ae1%N

  对B解密回到明文A,就是

  A=Be2%N

  其中,一般来说,加密公钥中的e1一般会比较小,取65537居多,但解密的时候,这个e2是一个非常非常大的数,显然,直接通过e2次模乘来解密是不现实的。

  为了让RSA的加密、解密成为现实,我们必须要找一个好的算法来做模幂运算。

  借上一节我设定的符号,以区别于传统上的幂的数学表示,

  定义a#b为a和b的模乘,

  定义a##n为n个a的模乘,或称a的n阶模乘。

  a = a##1,

  a##2 = a#a,

  a##4 = (a##2) # (a##2),

  ...

  a##2n = (a##2n-1) # (a##2n-1),

  从而,进行了n次模乘,分别获得了1、21 、22 ...2n 个a的模乘结果,

  而1、21 、22 ...2n 取其中任意一部分的和可以覆盖1~2n-1的所有整数。

  从而我们得到了一个算法来计算a##b:

  先不断通过每次得到的新结果自己同自己模乘,得到

  a、a##2、a##4...a##2n,使得满足2n≤b<2n+1,

  再将b化为二进制表示,实际上也就是表示为2的各次幂相加形式,

  然后找到对应每个2的幂次a模乘结果,

  然后再把这些结果依次模乘,得到最终结果。

  打个比方,如果想求a##21,

  21用二进制表示为10101,所以21 = 16+4+1,

  第一步,求得a##2,a##4,a##8,a##16,

  第二步,取a,a##4,a##16,三者模乘就是最终需要的结果。

  当然,可以把第一步求a的2n阶模乘和第二步取需要的模乘融合在一起,这样就不需要存储每一个a的2n阶模乘结果,从而存储空间可以为常数级,而之前存储空间为线性级。

  该算法用bc描述如下:

#!/usr/bin/bc -q
define mod_mul(a1,a2,n)// a1*a2%n
{
        return a1*a2%n;
}

define mod_exp(a,b,n)// a^b%n
{
        while(b%2==0) {
                a = mod_mul(a,a,n);
                b /= 2;
        }
        ret = a;
        b /= 2;
        while(b!=0) {
                a = mod_mul(a,a,n);
                if(b%2 == 1)
                        ret = mod_mul(a,ret,n);
                b /= 2;
        }
        return ret;
}
a=read();
b=read();
n=read();
print mod_exp(a,b,n),"\n"
quit

  该算法求a##b所做模乘次数:

  求各个a的2n阶模乘,所做模乘次数为log2b取整,也就是b的二进制的位数减1;

  取相应的2的正整数次幂的模乘结果再做模乘,所做模乘次数为b的二进制中1的个数减1。

  两者加一起为模乘次数。

  比如上面想求a##21,21用二进制表示为10101,所以该算法所需要模乘次数为(5-1)+(3-1)=6次。

  但此算法未必是最优的,我们来看看如下例子:

  想求a##441,

  441用二进制展开为110111001,于是模乘次数应该是(9-1)+(6-1)=13次。

  但我们可以用另外一种方式来求a##441,

  441 = 21 * 21,

  a##441 = (a##21) ## 21,

  我们求b = a##21需要6次模乘,

  再求b##21需要6次模乘,总共只需要12次模乘,比刚才少了1次。

  441是合数,我们再取个质数,239。

  239写成二进制是11101111,那么根据我们的算法应该做的模乘次数为(8-1)+(7-1)=13次。

  239 = 14*17+1,

  a##239 = ((a##14) ## 17) # a,

  先求b = a##14,需要5次模乘,

  再求c = b##1,需要5次模乘,

  最后再与a模乘,需要1次模乘,

  总共11次模乘,比13次要少。

  但是,即便是合数分解了,也未必得到更好的结果。

  例如49 = 7*7,

  分解前,49表示为二进制为110001,要做(6-1)+(3-1)=7次模乘,

  可是分解后,7表示为二进制制为111,

  总共要做(3-1)+(3-1)+(3-1)+(3-1)=8次模乘了。

  从而我们可以知道,我们给出的算法虽然是一个线性时间算法,但未必是最优算法,不过做到线性时间算法,从运算时间复杂度上来说,的确没有时间复杂度是这个算法的低阶无穷大级的算法了,从这个意义上,此算法已经“最优”了。

  如何做到最少次模乘?

  本问题为以下问题:

  (1)集合A初始为{1}

  (2)每一步从集合A中取两个数a和b,ab可相同,让c = a+b,再把c并入集合A,

    A = A∪{c}

  (3)输入正整数e,求A里面有元素e的最小步骤的过程。

  可惜此问题获得最优解似乎没有很好的算法,甚至远高于RSA可能基于的安全性——大数分解,但存在相对好的算法,从而可以用来改进我们的模幂算法。

  模幂算法是RSA的核心,不仅仅加密解密的时候需要,寻找密钥的时候也是需要的。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • RSA简介(一)——数论原理

      RSA是最常用的非对称加密算法。   所谓非对称加密,就是说有两个密钥,一个密钥加密只可以用另外一个密钥解密,一般一个作为公钥,公开给所有人用来加密用,而另...

    窗户
  • Scheme来实现八皇后问题(2)

      上一章讲了用1~n的排序来表示n皇后的解,然后通过枚举1~n所有的排列、判定谓词过滤所有排列得到最终的所有解。

    窗户
  • 汉诺塔——各种编程范式的解决

      理解递归,汉诺塔(Tower of Hanoi)是个很适合的工具,不大不小,作为最开始递归的理解正合适。从而学习各种计算机语言乃至各种编程范式的时候,汉诺塔...

    窗户
  • 【开源公告】腾讯Node.js基础设施TSW正式开源

    TSW是面向WEB前端开发者,以提升问题定位效率为初衷,提供云抓包、全息日志和异常发现的Node.js基础设施。

    TSW
  • 【开源公告】腾讯Node.js基础设施TSW正式开源

    腾讯开源
  • Bootstrap Metronic 学习记录(一)简介

    1.简介   是一个基于Bootstrap 3.x的高级管理控制面板主题。Bootstrap Metronic - 是一个完全响应式管理模板。基于Bootstr...

    用户1149182
  • css+ js 实现圆环时钟

    小蔚
  • 懒人神器 autoenv

    前言 每次去不同的项目下运行程序都要更改相对应的 Python 环境,那么有什么办法可以省去这繁琐的一步吗?答案肯定是有的,Kenneth Reitz 已经为我...

    木制robot
  • 致童年丨高通推《恐龙战队》VR体验,带你重温儿时记忆

    VRPinea
  • C# CRC8实现

    http://www.cnblogs.com/canny/archive/2004/12/27/82468.aspx

    用户3135539

扫码关注云+社区

领取腾讯云代金券