loading深圳学历教育www.szstudy.com.cn深圳成人高考 数据加密技术的研究综述
可以用一个循环求得： C=0;
FOR i=0 to n
C=C+A*B[i]*0x100000000 % N RETURN C
事实上，有一种蒙哥马利算法能够更快地完成多次循环的乘模运算，但是其原理涉及较多的数论知识，且实现起来比较麻烦，对速度虽有提高，经测试也不会超过一个数量级，所以暂且不予考虑。 素数测试
数论学家利用费马小定理研究出了多种素数测试方法，目前最快的算法是拉宾米勒测试算法，其过程如下： （1）计算奇数M，使得N=(2**r)*M+1 （2）选择随机数A （3）对于任意i （5）让A取不同的值对N进行5次测试，若全部通过则判定N为素数 若N 通过一次测试，则N 不是素数的概率为 25%，若N 通过t 次测试，则N 不是素数的概率为1/4**t。事实上取t 为5 时，N 不是素数的概率为 1/128，N 为素数的概率已经大于99.99%。 在实际应用中，可首先用300—500个小素数对N 进行测试，以提高拉宾米勒测试通过的概率，从而提高测试速度。而在生成随机素数时，选取的随机数最好让 r=0，则可省去步骤（3） 的测试，进一步提高测试速度。 输入输出 大数的输入输出是通过字符串来完成的，事实上很容易实现，例如按照十进制格进行处理，则： 输入： X=0 FOR i=0 TO n X=X*10 X=X+(int)(str[n]-48) RETURN X 21 深圳学历教育www.szstudy.com.cn深圳成人高考 数据加密技术的研究综述 输出： str= WHILE(X>0) str=(char)(X-48)+str RETURN str [5] 4.4 RSA探索 RSA算法中的加密解密操作，都是大整数的算术运算，在硬件实现上需要长的(千位以上的)运算结构。目前，在集成电路中进行大整数算术运算的结构设计，需要做全局数据广播，不仅扇出大、延时长，而且需要的连线资源很大。全局信号的广播问题，在现有关于RSA硬件实现的文献资料中很少提及。实际上，对于任何在深亚微米工艺条件下实现的集成电路，全局信号的广播都是需要认真解决的问题。对于RSA模乘幂运算器这样一个数据宽度特别大的结构，这个问题尤其重要，直接影响到设计的性能。 在基于冗余阵列的设计中，针对现有结构中存在的问题，我们对蒙哥马利算法进行优化，并采用将信号广播流水化的方法，解决长整数运算结构中关键信号广播带来的负载问题。我们采用在信号广播中插入中间寄存器的方法，设计者在RTL的层次控制扇出节点的数量，从而减少扇出，降低关键路径的延迟，提高时钟频率。相对于未优化的结构，新设计的时钟频率提高100～154％，模乘幂运算速度提高99～153％，而面积的增加仅有5～28％。 在基于脉动阵列的设计中，尽管脉动阵列的结构可以解决进位链的传递问题，但是，仍然有一部分全局信号需要从控制部件广播到乘法器的特定位置。我们在新的RSA模乘幂运算器的设计中提出一种被称作“分布式模块簇”(DMC：DistributedModuleCluster)的结构，以提高长整数运算结构的可扩展性，减少全局信号的扇出。该策略使得除了时钟之外的其它信号的传播都限定在一个模块内部或者相邻两个模块之间，为解决长整数的运算结构在深亚微米工艺实现时所遇到的全局信号广播问题提供了可行的解决方案。针对基于脉动阵列结构的模乘法器，我们提出一种冗余策略用以完成模乘法器的动态分割，但是关键路径的延迟不受影响。这种冗余策略可以支持中国剩余定理的应用。基于DMC的设计与基于冗余结构的优化设计相比，虽然在运算速度方面各有优势，但是DMC结构不象冗余结构一样需要针对不同的结构长度进行细致的调整，因而DMC结构具有更好的可扩展性。与基于冗余结构的优化设计相比，基于DMC结构的设计主频提高43～65％，公钥运算速度降低15～26％，而由于在硬件上直接支持CRT，私钥运 22 深圳学历教育www.szstudy.com.cn深圳成人高考 数据加密技术的研究综述 算速度提高52～76％。 在针对DMC结构进行的设计空间的探索中，我们详细探讨了采用部分并行的脉动阵列结构实现蒙哥马利算法的问题，实现了一系列不同长度和不同结构的运算单元，从中选择具有比较高的运算性能和性价比的结构。实验结果表明，如果以关键路径延迟×单元面积作为时间-面积代价指标，那么全部串行的脉动阵列结构，即每个运算单元处理一位数据的设计，与同类结构相比具有比较高的运算性能和性价比。 在基于脉动阵列的设计中，相邻的运算单元存在数据依赖关系，因而每隔一个周期就会有一个周期的空闲。从算法的层次上看，这种数据依赖关系是无法消除的。但是，我们的实验发现，在部分并行的脉动阵列中，如果不采用交替执行的结构，而是两个模乘法分别采用一套运算模块并发执行，并且适当调整一些关键信号的时序，可以消除因为数据依赖关系而引起的空隙。通过对逻辑综合和物理实现的结果进行分析发现，相对于基于交叉执 行 结 构 的 DMC 而 言 ， 新 的 并 发 执 行 结 构 CE-DMC(ConcurrentExecutionDistributedModuleCluster)主频降低10～29％，但是完成RSA模乘幂运算需要的时钟周期数仅仅是前者的50％，所以运算速度提高42～98％。 另外，在RSA模乘幂运算的设计中，控制单元中有若干个1000位以上的寄存器。对长寄存器的快速存取，控制电路的扇出很大，从而使得时钟周期比较长。我们提出并采用“两阶段访问”(TSA：Two-StageAccess)方法和在信号广播中插入中间寄存器的方法，以减少扇出，降低关键路径的延迟。RSA加密算法是一种非对称加密算法。在公钥加密标准和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。 对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。但在分布式计算技术和量子计算机理论日趋成熟的今天，RSA加密安全性受到了挑战。 23 深圳学历教育www.szstudy.com.cn深圳成人高考 数据加密技术的研究综述 24