Thoughts on improving rate of large number modular multiplication in RSA algorithm

doi:10.12267/j.issn.2096-5931.2023.06.012

Abstract

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

CLC Number:

TP301.6

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.

Add to citation manager EndNote|Ris|BibTeX

URL:

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

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

Figures/Tables 14

输入: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
}

输入: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
}

输入: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]

输入: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]

$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$

$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$

对于序列,满足, $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$

对于序列,满足, $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$

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

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

算法名称	公式
普通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

算法名称	公式
普通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

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

设计	数据长度/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	—

References 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.