对提高RSA算法中大数模乘运算速率的思考*

doi:10.12267/j.issn.2096-5931.2023.06.012

摘要/Abstract

摘要：

RSA算法的核心是大数模乘运算,提高其运算速率不仅对改进RSA算法本身有着重要的意义,而且,如果能够通过专用集成电路快速而低成本的实现,将会对电子商务的推广产生积极作用。在研究蒙哥马利算法的基础上,提出一种基于并行前缀加法器架构的基2-Montgomery模乘运算,构建了1 024 bit的Kogge-stone加法器。仿真结果表明,该方法可以有效减少模乘运算中操作数的延迟时间,在一定程度上提高大数模乘的运算效率。

关键词: RSA算法, 基2-Montgomery, Montgomery算法, Kogge-stone加法器

Abstract:

The core of RSA algorithm is large number modular multiplication. Improving its operation speed is not only of great significance to the improvement of RSA algorithm, but also will have a certain positive effect on the promotion of e-commerce if the speed can be achieved quickly and cheaply through application specific integrated circuit. Based on the study of Montgomery algorithm, this paper proposes a basic 2-Montgomery modular multiplication operation based on the parallel prefix adder architecture, and constructs a 1 024-bit Kogge-stone adder. The simulation results show that the proposed method can effectively reduce the delay time of operand and improve the efficiency of large number modular multiplication to a certain extent.

Key words: RSA algorithm, basic 2-Montgomery, Montgomery algorithm, Kogge-stone adder

中图分类号:

TP301.6

贾斌斌, 王忠庆, 方炜. 对提高RSA算法中大数模乘运算速率的思考^*[J]. 信息通信技术与政策, 2023, 49(6): 84-90.

JIA Binbin, WANG Zhongqing, FANG Wei. Thoughts on improving rate of large number modular multiplication in RSA algorithm[J]. Information and Communications Technology and Policy, 2023, 49(6): 84-90.

导出引用管理器 EndNote|Ris|BibTeX

链接本文:

http://ictp.caict.ac.cn/CN/10.12267/j.issn.2096-5931.2023.06.012

http://ictp.caict.ac.cn/CN/Y2023/V49/I6/84

图/表 14

图1 RSA算法实现的模块

表1 Montgomery乘法

输入:A,B,r,p
输出:A×B×r^-1mod p
Monm(A,B,r,p)
{t=A×B
u=(t+ $t × p m o d r$ )p/r
if u≥p
return u-p
}

表1 Montgomery乘法

输入:A,B,r,p
输出:A×B×r^-1mod p
Monm(A,B,r,p)
{t=A×B
u=(t+ $t × p m o d r$ )p/r
if u≥p
return u-p
}

表2 基2-Montgomery算法关键步骤

输入:A,B,P
S $0$ =0;
for i 0 to k-1 loop;
q_i= $S i 0 + A i B 0$ mod2;
S $i + 1$ = $S i + A i B + q i n$ div2;
end loop;
return S[k]

表2 基2-Montgomery算法关键步骤

输入:A,B,P
S $0$ =0;
for i 0 to k-1 loop;
q_i= $S i 0 + A i B 0$ mod2;
S $i + 1$ = $S i + A i B + q i n$ div2;
end loop;
return S[k]

表3 Kogge-stone加法器

$S i = p i ⊕ C i - 1 (i = 1 … N)$
$c i = g i + C i - 1 × g i$
$C 0 = C i n, C o u t = C i n$
进位项与产生项: $P i = A i ⊕ B i, g i = A i × B i$
得出进位链为: $C i = g i + C i - 1 ⊕ P i$
$x i = a i + x i - 1 ⊕ b i$

表3 Kogge-stone加法器

$S i = p i ⊕ C i - 1 (i = 1 … N)$
$c i = g i + C i - 1 × g i$
$C 0 = C i n, C o u t = C i n$
进位项与产生项: $P i = A i ⊕ B i, g i = A i × B i$
得出进位链为: $C i = g i + C i - 1 ⊕ P i$
$x i = a i + x i - 1 ⊕ b i$

表4 Kogge-stone并行算法

对于序列,满足, $x 1 x 2 x 3 … x N x i = f (x i - 1 x i - 2 … x i - m)$ 一阶递归如下:
$x i = a i × x i - 1 + b i$ ;
定义函数:$\widehat{Q}=(m, n)=\sum_{j=n}^{m}\left(\prod_{r=j+1}^{m} a_{r}\right) \times b_{r}$
其中 $∏ r = m + 1 m a r = 1$
以8 bit加法器为例
结果:x₁=b₁= $Q ︿ 1,1$
x₂=a₂×x₁+b₂=a₂×b₁+b₂= $Q ︿ 1,1$
…
x₈=a₈×x₇+b₈= $Q ︿ 8,1$
即: $Q ︿ 1,1$ =x₁=b₁
$Q ︿ 2,1$ =x₂=a₂×b₁+b₂=a₂× $Q ︿ 1,1$ + $Q ︿ 2,2$
…
$Q ︿ 8,1$ =x₈=a₈×b₇+b₈=a₈×a₇×a₆×a₅× $Q ︿ 4,1$ + $Q ︿ 8,5$

表4 Kogge-stone并行算法

对于序列,满足, $x 1 x 2 x 3 … x N x i = f (x i - 1 x i - 2 … x i - m)$ 一阶递归如下:
$x i = a i × x i - 1 + b i$ ;
定义函数:$\widehat{Q}=(m, n)=\sum_{j=n}^{m}\left(\prod_{r=j+1}^{m} a_{r}\right) \times b_{r}$
其中 $∏ r = m + 1 m a r = 1$
以8 bit加法器为例
结果:x₁=b₁= $Q ︿ 1,1$
x₂=a₂×x₁+b₂=a₂×b₁+b₂= $Q ︿ 1,1$
…
x₈=a₈×x₇+b₈= $Q ︿ 8,1$
即: $Q ︿ 1,1$ =x₁=b₁
$Q ︿ 2,1$ =x₂=a₂×b₁+b₂=a₂× $Q ︿ 1,1$ + $Q ︿ 2,2$
…
$Q ︿ 8,1$ =x₈=a₈×b₇+b₈=a₈×a₇×a₆×a₅× $Q ︿ 4,1$ + $Q ︿ 8,5$

图2 Kogge-stone树形图

表5 混合Montgomery算法

int result=0;
bit carry=0,x
for i to n
q_i= $r 0 i$ ⊕(a_i+b₀)
for j to n
start(a_i,q_i)
$1,1$ :x=mb_j
$1,0$ :x=b_j;
$0,1$ :x=b_j;
$0,0$ :x=0;
$r j i + 1$ = $r j + 1 i$ ⊕x⊕carry
end for
carry= $r j + 1 i a n d x j$ or( $r j + 1 i$ and carry)or(carry and x_j)
end for
return result

表5 混合Montgomery算法

int result=0;
bit carry=0,x
for i to n
q_i= $r 0 i$ ⊕(a_i+b₀)
for j to n
start(a_i,q_i)
$1,1$ :x=mb_j
$1,0$ :x=b_j;
$0,1$ :x=b_j;
$0,0$ :x=0;
$r j i + 1$ = $r j + 1 i$ ⊕x⊕carry
end for
carry= $r j + 1 i a n d x j$ or( $r j + 1 i$ and carry)or(carry and x_j)
end for
return result

图3 加法接口示意图

图4 混合Montgomery算法接口示意图

图5 混合Montgomery算法数据流

图6 处理单元pe结构

表6 Montgomery运算三种表达式

算法名称	公式
普通Montgomery	Mon $A, B, r, p$ =A×B×r^-1mod p
基2-Montgomery	Mon_2 $A, B, p$ =A×B×2^-ⁿmod p
基8-Montgomery	Mon_8 $A, B, p$ =A×B×2^-3(ⁿ^-1)mod p

表6 Montgomery运算三种表达式

算法名称	公式
普通Montgomery	Mon $A, B, r, p$ =A×B×r^-1mod p
基2-Montgomery	Mon_2 $A, B, p$ =A×B×2^-ⁿmod p
基8-Montgomery	Mon_8 $A, B, p$ =A×B×2^-3(ⁿ^-1)mod p

表7 模乘运算资源对比结果

设计	LUT/FF数量	优化方法	器件
本文	5 158/10 491	KSA+基2-Montgomery	ZYNQ-7020
其他方式一	27 820	CSA+Montgomery	Virtex-5

表8 模乘运算时间对比结果

设计	数据长度/bit	时间/μs	时钟周期	优化方法	器件
本文	1 024	111.15	735	KSA+基2-Montgomery	ZYNQ-7020
其他方式一	1 024	—	1 028	CSA+Montgomery	Virtex-5
其他方式二	1 024	452.49	22 634	SMM方法	EP3SL340F1760C
其他方式三	1 024	2 200	—	普通Montgomery	—
其他方式四	1 024	90 350	—	大整数平方改进后的Montgomery	—

参考文献 14

[1]	邬贵明, 谢向辉, 吴东, 等. 高基Montgomery模乘阵列结构设计与实现[J]. 计算机工程与科学, 2014, 36(2):201-205.
[2]	车文洁, 董秀则, 高献伟, 等. Montgomery模乘法器的实现与优化[J]. 计算机应用与软件, 2017, 34(3):312-315+333.
[3]	肜丽, 姜明富. RSA加密方式中Montgomery算法的研究与改进[J]. 信阳农业高等专科学校, 2013, 23(4):107-109.
[4]	高献伟, 张晓楠, 董秀则. 基于FPGA的Montgomery模乘器的高效实现[J]. 计算机应用研究, 2017, 34(11):3424-3427.
[5]	李泉龙. 基于Kogge-Stone算法与多米诺逻辑的64位高性能加法电路设计[D]. 成都: 西南交通大学, 2016.
[6]	ZHAO S L, HUANG H, LIU Z W, et al. An efficient signed digit montgomery modular multiplication algorithm[J]. Microelectronics Journal, 2021(3):105099.
[7]	PARIHAR A, NAKHATE S. High-speed high-throughput VLSI architecture for RSA montgomery modular multiplication with efficient format conversion[J]. Journal of The Institution of Engineers (India): Series B, 2019, 100(2):217-222. doi: 10.1007/s40031-019-00384-1
[8]	LEE M X, MUHAMMAD M A Z, AINY H A, et al. VLSI implmentation of a fast Kogge-stone parallel-prefix adder[J]. Journal of Physics Conference, 2018:1049.
[9]	邵佳佳, 乌力吉, 张向民. 智能卡中非对称算法模幂运算单元的设计与验证[J]. 微电子学与计算机, 2015, 32(2):37-41.
[10]	程碧倩, 刘光柱, 肖昊. 改进的蒙哥马利模乘算法及FPGA实现[J]. 电子科技, 2022, 35(7):58-63.
[11]	王开宇, 唐祯安, 赵赟, 等. 基于改进CSA-蒙哥马利的RSA加密处理器实现[J]. 大连理工大学学报, 2013, 53(2):294-297.
[12]	孙建林. 基于FPGA的RSA快速加密算法的改进[D]. 保定: 河北大学, 2016.
[13]	陈逢林, 苏厚勤. Montgomery算法的改进及其在RSA中的运用[J]. 计算机应用与软件, 2006, 23(6):109-111.
[14]	靳蓓蓓, 张仕斌. Montgomery模幂运算的一种改进方案[J]. 长春大学学报(自然科学版), 2006, 16(4):48-51.

编辑推荐

Metrics

阅读次数

全文

1170

HTML			PDF

最新录用	在线预览	正式出版	最新录用	在线预览	正式出版
0	0	980	0	0	190

来源	本网站	其他网站

次数	1126	44
比例	96%	4%

摘要

258

最新录用	在线预览	正式出版

0	0	258

	来源	本网站

	次数	258
	比例	100%