高速可配置RSA密码协处理器的ASIC设计
后需要判断m是否大于N,如果大于N,必须再做减法,这在硬件设计上会增加额外的芯片面积。本文通过在模乘循环过程中增加一次循环,就可以免去最后的减法(见算法五)。
1.3 高基Montgomery算法
把n位大整数A,B,N分别表示成s位r进制整数,即A=(as-1 as-2…a0),B=(bs-1bs-2…b0)r,N=(ns-1ns-2…n0)r,且R=rs,s=n/r,则有N P>
算法四:高基Montgomery算法
Function M(A,B)
S:=0;m=0;
(1)计算中间结果m[i]:
for i=0 to s-1
{for j=0 to i
{s:=s+a[j]*b[i-j]+m[j]*n[i-j];}
m[i]:=s*n′[i] mod r;
s:=s+m[i]n[i]
s:=s/r;}
(2)计算最终结果并存于m[i]中:
for i=s to 2s-1
{for j=i-s+1 to s-1
{s=s+a[j]b[I-j]+m[j]n[I-j]}
m[i-s]:=s mod r
s:=s/r}
算法五:从右往左扫描的免减高基模乘算法
(1)预处理:
R2=R*R mod N;(事先计算出来,可消除R-1带来的影响)
P=M(M,R2);
C=1;
(2)中处理:
for i=0 to n-2
if e[i]=1 then C=M(C,P);
P=M(P,P);
next i;
if e[n-1]=1 then C=M(C,P);
return C;(计算C=M(Me))
(3)后处理:
C=M(C,1);(免去了montgomery算法每次的减法运算)。
2 协处理器体系结构
2.1 SPU整体结构与模块划分
SPU与CPU通过CROSSBAR[3]交叉通信开关进行通信,而SPU与MEM之间则采取DMA方式直接通信,这样可以消除数据存取的速度瓶颈。同时,当SPU进行加解密工作时,CPU可以并行执行其他指令(只要不发生数据相关)。
SPU划分为控制模块,数据通道和存储单元。其中控制单元主要用于密钥移位控制,控制密钥的降幂,并根据密钥产生乘或平方控制信号。另外,控制单元还包括一个状态控制器,用于对前处理、中处理和后处理各个运算环节的控制。
数据通道部分则由Montgomery模乘单元和平方单元构成,两个单元并行,根据控制单元产生的控制信号来进行相应的操作,产生部分积和中间结果。
存储单元大小为8 Kbit,分为两部分。一部分是4 KB的RAM,用于加解密过程中暂存数据,以便形成流水线;另一部分是4 KB的ROM,用于存放公钥和密钥,掉电可以保存数据。
系统框图如图1所示。
2.2 流水线设计
为了实现高速、可配置的RSA密码协处理器,采用了按字读入的高基模乘算法,同时对模幂单元采用流水线结构:这样一方面可以增加数据吞吐率,加快数据运算速度;另一方面可以通过增减流水线的级数来增强可配置性。
从按字读入的高基模乘算法(算法五)中可以看出,每次密钥长度为N bit的RSA加解密过程是一次幂指数为N的模幂运算,而一次这样的模幂运算则是N次模乘运算。因此通过设计模幂流水线结构,可以大大增加RSA加解密的速度。
流水线结构的模幂运算如图2所示。明文M经过T级流水线数据通路,最后输出密文C;对于一个N位的RSA加密系统来说,如果采用T级流水线,则每一级流水线需要循环做N/T次MM运算。RSA的运算速度取决于一级流水线的速度。
2.3 DMA通道的工作过程
SPU向DMA控制器发出DMA请求,DMA控制器在接到SPU发出的DMA请求后,向CPU发出总线请求,请求CPU脱离对总线的控制,而由DMA控制器接管对系统总线的控制;CPU在执行完当前指令的当前总线周期后,向DMA控制器发出总线响应信号,CPU脱离对系统总线的控制,处于等待状态(但一直监视DMAC);DMA控制器接管对系统总线的控制;DMA控制器向SPU发出DMA应答信号,DMA控制器把存储器与SPU之间进行数据传送所需要的有关地址送到总线,通过控制总线向存储器和SPU发出读或写信号,从而完成一个字节的传送;当设定的字节数据传送完毕后(DMA控制器自动计数),DMA控制器将总线请求信号变成无效,同时脱离对总线的控制;CPU检测到总线请求信号变成无效后(CPU一直监视着),也将总线响应信号变成无效,CPU恢复对系统总线的控制,继续执行被DMA控制器中断的当前指令的当前总线周期。
2.4 存储体结构设计
SPU内部共设计两部分RAM,都使用双口存储体,主要用作数据输入、输出缓存。双口RAM分A和B两部分,每部分的深度32,宽度64,即32×64的存储空间;一块RAM可以存储2 KB的数据,输入输出各需要一块作为缓存,也就是说片内共设计4 KB的RAM。双口RAM的两部分是对称的,但是对每部分的读写都是独立的,当需要加密或解密时,数据先输入到A部分,当A部分输入满2 KB数据时,数据继续输入到B中,此时运算模块读取A中的数据计算,当B部分数据输入满时,运算模块已经计算完A中的数据,然后读取B中的数据,输出则是相反的过程,如此形成加解密数据流,运算流程如图3所示。
本文基于改进的按字输入的从右往左扫描的高基Montgomery模乘算法,
- ASIC设计规范(06-06)
- Windows CE 进程、线程和内存管理(11-09)
- RedHatLinux新手入门教程(5)(11-12)
- uClinux介绍(11-09)
- openwebmailV1.60安装教学(11-12)
- Linux嵌入式系统开发平台选型探讨(11-09)