RSA 算法中的计算问题

 

作者：鄢喜爱 杨金民 田华

RSA 中的加密和解密过程都为求一个整数的整数次幂。如果按其含义直接计算, 则中间结果运算量非常大, 运算速度慢, 且有可能超出计算机所允许的整数取值范围。如果利用模运算性质: ( a* b) mod n= [ (a mod n) * (b mod n) ] modn, 就可以减小中间结果, 提高运算速度。

求a的m次方mod n 可按如下步骤进行, 其中a, m 是正整数。

首先将 m 表示成二进制形式bk , bk- 1, ,,b0 , 然后按如下快速指数算法进行:

c= 0;d= 1
for ( i= k; i< = 0; i- - )
{ c= 2* c;
d= (d* d) % n;
if ( bi= = 1)
{
c= c+ 1;
d= ( d* a) % n;
} }
return d

其中, c 是指数; d 是中间结果;return d 为*终所求的结果。

例3: 求上面实例中的123的103次方mod 143。

将103 表示为 1100111, 算法的演示过程见表2, 得出123的103次方mod 143= 85。

表2 快速指数算法的结果

超时代软件致力于加密算法的研究，并在视频加密方面解决了视频流大小与加密强度和加解密时间之前的冲突。