第 %#卷第 &
期 "###年)"
月 微 电 子 学
*+,-./0/,1-.2+,3
4567%#89 & :;<
7"### ==================================================================
= 文章编号!)##>$%%&(?"###@$#&$#%A )$#>
周 芬8高志强
清华大学 微电子研究所设计室8北京
)###B >@
摘 要! C D E
公开密钥加密技术是目前使用最广泛的加密技术F 文章提出了快速并行的算法8使 C D E 公开密钥加密速度提高了很多F 模乘算法是模幂算法的核心8基于 G 5H I J 5K ;L M 算法8提出了 一种改进的快速高基模乘算法8该算法求出了乘法的最终积8使得乘法和模减运算同时进行8并且 所有的运算是以字节为单位F 模幂算法采用从右到左扫描指数的方法8可以使得两次模乘运算同时 中图分类号! 文献标识码! U V %A %7#B
E
W X Y Z [\]^_X ‘a b c \d e d Z f X Z f \dg _h \‘f Z i j X d ]k Z Y l X ‘]m X ‘e k j c _e j e d Z X Z f \d
n O o p q ;H 8r E o n s t $u t v H J
w x y z {z |z }~!"{#$~}%}#z $~x {#y 8&y {x ’(|)*x {+}$y {z ,8-}{.{x ’ )###B >8/0102({x )
@ g 3Y Z ‘X 4Z ! C D E 56R 6t <Q ;M <L M 5I 5$T M T I ;K t T v L ;6v I t 7;6M T v 8;I ;<s H 565J M
89s t <s t T 9t :;6M 6T ;:t H I 5:v M ;T T ;<6L ;
;6;<I L 5H t <<5KK 6H t <v I t 5H 0<H I s t T 5v 5;L 8I s ;5v L v 66;6t I M 58I s ;v 6J 5L t I s K t T t K 5L 57;:t HK v H M 9v M T 8T 5I s ;;H <L M 5I t 5H L v I ;t H <L ;v T ;T 0G 5:66v L K 66I t 56t <v I t 5H v 6J 5L t I s K t T I s ;<5L ;58K 5:66v L ;=55H ;H I t v I t 5H 0E
8v T I K 5:66v L K 66I t 56t <v $
I t 5H v 6J 5L t I s K
R v T ;:5H G 5H I J 5K ;L M ;T v 6J 5L t I s K
t T 5L 555T ;:0<H I s ;t K 5L 57;:v 6J 5L t I s K 8I s ;8t H v 65L 5:6<I 58I s ;
K 66I t 56t <v I t 5H t T <v 6<66v I ;:89s t <s K v Q ;T K 66I t 56t <v I t 5H v H :K 5:66v L L ;:6<I t 5H L 6H v I I s ;T v K ;I t K ;0E 66I s ;55;L v $ I t 5H T v L ;R v T ;:5H 95L :T 0G 5:66v L ;=55H ;H I t v I t 5H v 6J 5L t I s K T <v H T ;H <L M 5I t 5H 8L 5K L t J s I I 56;8I 8T 5I 95K 5:66v L K 66I t 56t <v I t 5H T<v HR ;5L 5<;T T ;:5v L v 66;66M 0U s ;s v L :9v L ;v L <s t I ;<I 6L ;t T K v :;6558K 5:66v L <5H I L 566;L 8K 5:66v L ;=55H ;H I t v I t 5H <5H I L 566;L 8:v I v L ;J t T I ;L 8v H :K 5:66v L K 66I t 56t <v I t 5H 55;L v I t 5H 6H t I T 0E I v <65<Q 58)##GO P 8I s ;;H $ <L M 5I t 5H L v I ;t T v R 56I %A #
Q R S T 85L ()"$R 55;L v H :T
0 >e ?m \‘]Y ! G 5:66v L ;=55H ;H I t v I t 5H v 6J 5L t I s K ’G 5:66v L K 66I t 56t <v I t 5H v 6J 5L t I s K ’V 6R 6t <$Q ;M <L M 5I 5J L v 5s M
’ @;I 95L Q :v I v T ;<6L t I M
a a g A A ! &)"#B
它可以进行数字签名和身份验证F C D E
算法的理论 基础是一种特殊的可逆模幂运算8它的安全性是基于分解大数的困难性F
C D E 算 法 的 加 密 过 程 为!2C "D
?K 5:E @
8解 密 过 程 为!"C 2:
?K 5:E @F 其 中8" 为
明 文8即 待
加密的数据82为密文8即加密以后的数据8F 为加引 言
) 信息时代飞速的发展8给人们带来了新的生活 方式8又给人们带来了信息安全的观念F 数据加密N 数字签名和身份验证是网络中不可缺少的环节F 数 据加密技术是网络中最基本的安全技术8它是通过 对网络中传输的信息进行加密来保障其安全性的
F 现在有很多加密算法8其中 C D E
公钥密码算法是目 前比较安全且使用最广泛的一种加密算法8而且用 万方数据
程越复杂8加密速度越慢8但同时破译也就越困难F 一 般 情 况 下8"N 2N F N G N E 都 为 ()"
位 以 上 的 二 进 制整数F 随着数据量的增加8软件加密往往不能满
收稿日期!"###$#%$#&’ 修回日期!"###$#($%#
速度的要求&因此&硬件加密是将来加密技术应用的目标’本文采用并行的模幂算法和模乘算法&优化了硬件结构&使加密速度提高了近(倍’=
Y%*%>
再生制动@/A B*%C/O670/
=
Z D*-Y D I Q D S2[U V%-./0P2>
Y D I7*-Y D I Q D S I Z D12\P>
F
dpppD@-Y R]12Y R*Y R61>
A G C5A H Y R>
模幂算法
#
模幂算法)*+,-./012就是进行一系列的
模乘运算&+为3位二进制整数-4
567456#8 474%2#&即待加密的数据&1为3位二进制整数
-4567456#8474%2#&即模数&9为3位二进制整数-:567:56#8:7:%2#&为加密密钥’根据扫描密钥的方向不同&模幂算法可以分为两种&一种为从左到右的扫描&一种为从右到左的扫描’两种方法的执行时间不一样&前者采用串行计算&后者采用并行计算&平均条件下&后者比前者快7;<；倍&但它的硬件规模要大一些’为了提高速度&本文采用第二种方法&其算法如下$
+97-+&9&12
=
)*7>
*+./01>
@/A B*7C/3670/
=
D@>-:D*72)*?E)-./012>
*?E?-./012>
F
A G C5A H)>
F
在算法的循环体中&运算)*?E)-./012和
*?E?-./012可以由两个模乘器并行完成’由此可见&完成一次模幂运算需要进行3I7次模乘运算的时间’提高模乘运算的速度是提高模幂运算速度的关键’一般情况下&1是<7#位或<7#位以上的二进制整数&用除法进行模乘运算是不能满足速度的要求的’为此&J/H C K/.G A L在7"M!年提出了一种模加右移的模乘算法&从而避免了通常求模算法中费时的除法步骤’下面给出J/H C K/.G A L算法的基本形式’
N为O位P进制整数Q R67Q R6#8Q7Q%2A&S为
O
位P进制整数-T
R67T R6#8T7T%2A&1
为O位P进制整
F
由Z
D
的求法可知&-Y
D I Q D S I Z D12
能被P整除&
因此&循环结束后&P R*N S I+1&其中&+*4
%I 47P I4#P#I8I4R67P R67&则W Y R*N S I+1X #W1&由此得出$Y R X#1&且Y R*N S W67-./012&其中&W67满足W W67-./012*67’算法的最后一
步是进行后处理&保证Y
R X1&
即Y
R*N S W67-./0 12’虽然Y R 并不是模乘所需要的真正结果&但只要在模幂算法中稍微修改一下就可以调用这个模乘算法进行计算了’为便于^_‘a实现&一般取P*#b&c 为一个正整数&则1 为3*c[O位二进制整数’
从算法中可以看出&求Y
儒林外史人物形象分析D I7
的过程中&有两次加法d两次乘法和一次移位操作&移位操作避免了操作
数位数的扩展&这是J/H C K/.G A L算法的特点’但是&在运算过程中&两次加法运算必须顺次进行’为了提高算法的并行性&本文提出了一个改进的J/H C K/.G A L算法’在改进的算法中&两次乘加运算同时进行&从而提高了算法的并行性’改进的模乘算法可以使模乘运算的速度提高近一倍’下面是改进后的算法$
++#-N&S&12
=
Y%*%>e*Q%S>
@/A B*%C/O6#0/
=
Z D-Y D I f%2[U V%-./0P2>
Y D I7*-Y D I f%I Z D12\P>
e*e\P I Q D I7S>
F
Z R67*-Y R67I f%2[U V%-./0P2>
Y R*-Y R67I f/I Z R6712\P>
数-U
R67U R6#8U7U%2A&P 和1 互质&U V为U
曙光考试%
关于模P Y*Y I e> % R67R
的逆&即U
%U V%-./0P2*67&
设W*P R&N S X W1’基为P的J/万H方C K/数.据G A L算法如下$
++7-N&S&12
D@-Y]12Y*Y61> R I7R I7R I7
A G C5A H Y R I7>
F
算法中的 % 是用来求乘积部分结果的&设 ’(
)
*(’+,’- ./由算法可知/01, 2( 301, 41, 5167
8 9&而由 51的求法可 知/901, 2( 01, 41, 516&
当 计 算 到 0: 时/9:0:( 4;, 429, 4<9<, = , 4:> 29:> 2
, / 35;,529, = , 5:> 29:> 2
76/则 .0:( ’?, @6/0:
并不是最终结果/它还需要加上乘积的高 A 位/即
0:, 2( 0:, ’B /因为 .0:, .’B ( ’?, @6, .’B
( ’, @6( )*, @6/所 以/0:, 2( )*.> 23CD E 67/经过后处理/0:, 2()*.> 23CD E 67
& @@2和 @@<；这两个算法的共同点是每次循环 都有两次加法和两次乘法/不同点在于/算法 @@2
中/两 次 加 法 必 须 顺 次 进 行/算 法 @@<；中/两 次 加 法可以同时进行/这样就提高了算法的并行性&算法
@@<；的 实 质 是 它 求 出 了 乘 法 的 每 一 位/供 模 减 使 用&但它并不是先求出整个乘积/再进行模减运算/ 而是使乘法运算和求模运算同步进行/这样不但提 高了速度/而且避免了操作数的扩展/因为一旦求出 了乘积的某一位/就求出了一个 51/然后就对乘积 % 进行移位/直到剩下乘积的高 A 位&由于求 % 和求
0可以同时处理/并且互相不受影响/因此/@@<；比 @@2速度快&
由于模乘算法并没有得出最终 结 果/ 因此/模幂运算应该做一些相应的调整/下面是调整 后的模幂算法&
@F <3@/F /67 G
H ( 2I J (@@<3@/.
<
CD E 6/67I K D L M ( ;N D O
> 2E D
G
1K 3P 1( 27 H (@@<3J /H /67I J (@@<3J /J /67I Q L R N S L T H
I Q
模 幂 算 法 @F <；调 用 了 改 进 后 的 模 乘 算 法 @@</与 @F 2不同的是第一步求出了 J (@.3CD E 67/这就使得在运算结束时/H ( @U CD E 6&这样/ 模幂算法和模乘算法都采用了并行处理/因此/加密 速率显然得到了提高&
器主要由两个模乘器以及模幂控制器组成/模乘器
又 由 模 乘 控 制 器 和 模 乘 运 算 单 元 以 及 存 储 单 元 组
成&本文采用了基为 9( <
V
的模乘算法/乘法和加法 应该以字长为 V 的字节为单位/每次求 0或 % 都
分 别需 要 A 次 乘 加 运 算&每 个 模 乘 器 需 要 两 个 W X W 位的乘法器和<W , W , W 位的加法器/分别供 0和 %
使用&在每个周期内/只要稍微调整一下算法/两个
乘法器和加法器可以同时工作/这样就保证资源不
被浪费&模乘算法中/输入数据 Z Z 需要存储起 来/根据算法的特点移位寄存器可以用作存储器/
这样易于控制&模乘器的控制单元由两个计数器和 一些控制码产生电路构成&从模幂算法可以看出/两
个模乘器有一些共同的地方&首先/它们同时工作/因此两个模乘器可以只用一个控制器I 另外两个模
乘器的部分输入是相同的/它们可以用同样的存储 器资源&经过这些优化/整个结构的资源就可以少一 些&图2所示是模幂运算器的结构示意图&调墨油
图2 模幂运算的结构示意图
模乘运算单元主要用来计算 和 它们分别 0 %/
需要一个乘法器和一个加法器以及寄存器/图<；是模 乘运算单元中的求 0或 % 的一个模块&
我的音乐库图< 模乘器结构图
硬件结构
# 从图<；可以看出/电路的最大延 迟 是 一 个 W X W
位乘法器的延迟&为了减小延迟/提高电路的时钟频
率 /乘法器可以采用波茨编码Z ]^__^‘R a L R R
和超前 由于模幂运算就是进行一系列的模乘运算/而
有两个模乘万运方算数需据要同时进行/因此/整个模幂运算
进位加法等技术’另外(用传输门逻辑还可以进一步
提高速度’用这些方法(!%位的乘法器延迟不超过)& *+(因此(时钟频率可以达到)&&,-.’
若模数/ 为0位二进制数(模乘运算时取12
%3(则42056(也就是说(/为4 个字长为6的多精度数(一个模乘运算共需要4%个时钟周期(而模幂运算需要约0个模乘运算的时间(则整个运算需要04%20!56%个时钟周期’当时钟频率为7时(运算所花的时间为6%750% 89:5+’显然(6越大(7越大(
则速度越高’但受到工艺的限制(6和7都不能无限制地加大’在频率7一定的情况下(6的选择受到7
的限制’当时钟频率为)&&,-.时(6可以取到!%(
加密速率可以达到!"&385+(比其它的模幂运算器
要快近#倍’
采用高基模乘算法提高了运算的并行性(但它有一个不足之处(就是随着数据位数0的增加(加密速率呈平方递减’当02%&#；时(加密速率就会降到"<=>385+’0越大(加密安全性就越高(但加密速率就越小’因此(0的选取是根据对安全性的要求多大来确定的’通常情况下(或)&%#就很难被破译’因此( 本文的工作有很高的应用价值’
结论
#
计算机网络安全越来越受到人们的重视(数据加密技术是网络安全的基础(但加密速率却很难提高’本文旨在提高@A加密速率(提出了算法和硬件结构上的改进’由于在多方面都进行了并行处理(加密速率提高了很多对于位操作数在
’>)% ( )&& ,-.的时钟频率下(加密速率可以达到!"&385+(是其它方法的倍
# ’
参考文献$
B)C?9D E+:?F(@G H I9J A(AK L E I H*F M A I E:G N K O N J N8P
:H9*9*Q K9Q9:H L+9Q*H:R J E+H*K S R8L9T P3E U T J U S:N+U+P
:E I+B V C M W N II R*9T H:9N*+N O A W,()"<;X%)Y%Z$)%&
[)%\=
B%C,N*:Q N I E J U]F M,N K R L H J I R L:9S L9T H:9N*^9:G N R::J9H L K9D9+9N*B V C M,H:G E
I H:9T+N O W N I S R:H:9N*()";>X##
Y)<&Z$>)"[>%)=
B!C_G V-(,N N*@V M,N K R L H J I R L:9S L9T H:9N*I E:G N K
B V
C M‘a a]J N T E E K9*Q+$W N I S R:E J+H*K b9Q9:H L c E T G P
*9d R E+()"";X)#>Y#Z$!)<[!);=
B#C e N T W e(A T H J c(e H L9+39f@M A*H L U.9*Q H*K T N I S H J P 9*Q,N*:Q N I E J U I R L:9S L9T H:9N*H L Q N J9:G I+B V C M V,9P
T J N E L E T:J N I E T G@U+:E I+()""\X)\Y\Z$%\[!!=
@R W G9G U R H*Q(-^H*Q@G9G H J*(W G E*]N+N*Q(E:H L M A* B>C
9I S J N D E K,N*:Q N I E J U g+H L Q N J9:G I O N J G9Q G P+S E E K
@A S R8L9T P3E U T J U S:N+U+:E I B V C M‘a a a c J H*+h F@‘
@U+:E I+()"""X<Y%Z$%;&[ %;#=
作者简介$周芬Y)"<\=))j Z(女Y汉族Z(江苏省淮安市人()""；年
<
月于清华大学电子工程系微电子学专业获学士学位(同年"月在清华大学
微电子所攻读硕士学位(主要研究方向为@A加密算法的研究及其h F P
@‘实现’
万方数据iiiiiiii iiiiiiii
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议