RSA 中的平方-乘 ，模幂运算

2019-04-13 11:44发布

站内文章 / 模拟电子
13776 0 1168
考虑模指数，即计算形如的函数，在RSA密码体制中，加密和解密运算都是模指数运算。计算 可以通过c-1次模乘来实现，然而，如果c非常大，其效率会很低下。 著名的平方-乘可以把计算所需的模乘的次数降低。 以计算 X24为例：

X24  将指数表示为 二进制形式  X11000  表示为Xb1b2b3b4b5
开始扫描指数的每个Bit:         下面的红体表示数值为2进制表示

1:     初始值  x = x1;                初始化设置，b1 = 1  ,扫描第一个bit时不需要做其他操作

2:      X2 = X10                                  b2=1，先平方
         X2 * X = X3 =X11                         再乘以 X

3：   (X3)2 = X6 = X110                    b3= 0，只需要一次平方

4:    (X6)2  = X12 = X1100                 b4 = 0，只需要一次平方

5： (X12)2 = X24 = X11000                b5 = 0,只需一次平方

通过观察运算过程中指数的二进制表示的变化能更好的理解算法，一次平方操作会让指数向左移一位，并在最右边添加0，
而与 X 相乘的操作即在指数的最右边位置上填上 1

热门文章