论文部分内容阅读
RSA密码系统是目前应用最为广泛的公开密钥密码系统。RSA密码系统中最核心的运算是模乘幂运算，即计算YEmodN。模乘幂运算由一系列模乘法运算实现，模乘法运算是模乘幂运算的基础。蒙哥马利模乘法算法是应用最广泛的模乘法算法之一。
本文论述了我们在深亚微米工艺条件下设计高性能RSA模乘幂运算电路方面的研究工作。在深亚微米工艺条件下，集成电路的性能瓶颈已经从逻辑单元转向了单元连线。RSA算法中的加密解密操作，都是大整数的算术运算，在硬件实现上需要长的(千位以上的)运算结构。目前，在集成电路中进行大整数算术运算的结构设计，需要做全局数据广播，不仅扇出大、延时长，而且需要的连线资源很大。全局信号的广播问题，在现有关于RSA硬件实现的文献资料中很少提及。实际上，对于任何在深亚微米工艺条件下实现的集成电路，全局信号的广播都是需要认真解决的问题。对于RSA模乘幂运算器这样一个数据宽度特别大的结构，这个问题尤其重要，直接影响到设计的性能。
在基于冗余阵列的设计中，针对现有结构中存在的问题，我们对蒙哥马利算法进行优化，并采用将信号广播流水化的方法，解决长整数运算结构中关键信号广播带来的负载问题。我们采用在信号广播中插入中间寄存器的方法，设计者在RTL的层次控制扇出节点的数量，从而减少扇出，降低关键路径的延迟，提高时钟频率。相对于未优化的结构，新设计的时钟频率提高100～154％，模乘幂运算速度提高99～153％，而面积的增加仅有5～28％。
在基于脉动阵列的设计中，尽管脉动阵列的结构可以解决进位链的传递问题，但是，仍然有一部分全局信号需要从控制部件广播到乘法器的特定位置。我们在新的RSA模乘幂运算器的设计中提出一种被称作“分布式模块簇”(DMC：DistributedModuleCluster)的结构，以提高长整数运算结构的可扩展性，减少全局信号的扇出。该策略使得除了时钟之外的其它信号的传播都限定在一个模块内部或者相邻两个模块之间，为解决长整数的运算结构在深亚微米工艺实现时所遇到的全局信号广播问题提供了可行的解决方案。针对基于脉动阵列结构的模乘法器，我们提出一种冗余策略用以完成模乘法器的动态分割，但是关键路径的延迟不受影响。这种冗余策略可以支持中国剩余定理的应用。基于DMC的设计与基于冗余结构的优化设计相比，虽然在运算速度方面各有优势，但是DMC结构不象冗余结构一样需要针对不同的结构长度进行细致的调整，因而DMC结构具有更好的可扩展性。与基于冗余结构的优化设计相比，基于DMC结构的设计主频提高43～65％，公钥运算速度降低15～26％，而由于在硬件上直接支持CRT，私钥运算速度提高52～76％。
在针对DMC结构进行的设计空间的探索中，我们详细探讨了采用部分并行的脉动阵列结构实现蒙哥马利算法的问题，实现了一系列不同长度和不同结构的运算单元，从中选择具有比较高的运算性能和性价比的结构。实验结果表明，如果以关键路径延迟×单元面积作为时间-面积代价指标，那么全部串行的脉动阵列结构，即每个运算单元处理一位数据的设计，与同类结构相比具有比较高的运算性能和性价比。
在基于脉动阵列的设计中，相邻的运算单元存在数据依赖关系，因而每隔一个周期就会有一个周期的空闲。从算法的层次上看，这种数据依赖关系是无法消除的。但是，我们的实验发现，在部分并行的脉动阵列中，如果不采用交替执行的结构，而是两个模乘法分别采用一套运算模块并发执行，并且适当调整一些关键信号的时序，可以消除因为数据依赖关系而引起的空隙。通过对逻辑综合和物理实现的结果进行分析发现，相对于基于交叉执行结构的DMC而言，新的并发执行结构CE-DMC(ConcurrentExecutionDistributedModuleCluster)主频降低10～29％，但是完成RSA模乘幂运算需要的时钟周期数仅仅是前者的50％，所以运算速度提高42～98％。
另外，在RSA模乘幂运算的设计中，控制单元中有若干个1000位以上的寄存器。对长寄存器的快速存取，控制电路的扇出很大，从而使得时钟周期比较长。我们提出并采用“两阶段访问”(TSA：Two-StageAccess)方法和在信号广播中插入中间寄存器的方法，以减少扇出，降低关键路径的延迟。