一种高性能大数模幂协处理器SEA

SEA: A High-Performance Modular Long Integer Exponentiation Coprocessor

大数模幂是许多公钥算法中的主要操作和计算瓶颈.SEA是一种针对大数模幂的高性能协处理器,其主要采用如下3种加速方法:①采用二进制并行模幂算法(PBME)和以基数长度为处理字长的高基数Montgomery算法(RBHRMMM);②将算法映射到脉动阵列处理结构,并交替计算平方和乘以掩盖RBHRMMM算法中的相关,同时应用定向技术消除PBME算法中的相关;③基于“先拆分乘法、后将累加压缩”的思想优化关键路径.SEA完成1024b完整大数模幂仅需72738个时钟周期,采用基于标准单元的正向设计流程实现,其面积为4.2×4.2mm2,等效门数为739933.目前,SEA已经在0.18μm1P6MCMOS工艺上流片成功,主频133MHz,峰值功耗为962.26mW,使用SEA后,完成一次1024bRSA签名仅需316.9μs.

Modular exponentiation of long integers is the primary operation of several public-key algorithms and often the bottleneck for implementation. A high-performance modular exponentiation coprocessor, SEA, is presented here, and three novel ways are employed. First, a parallel binary modular exponentiation algorithm (PBME) is used to decrease cycles, and a high radix Montgomery modular multiplication algorithm is modified to the radix based high radix Montgomery modular multiplication algorithm (RBHRMMM) to increase the frequency; second when mapping algorithms to a systolic array, modular square and modular multiplication are alternatively computed to cover up the dependencies between iterations in the RBHRMMM algorithm and the bypass is used to eliminate the dependencies in the PBME algorithm; third, multipliers are split first, and then accumulations are compressed as partial products to decrease carry propagation delay in the critical path. The SEA can do a full 1024-bit modular exponentiation in 72738 cycles and is implemented based on standard cells, its die area being 4.2×4.2mm^2 which equals 739933 gates. Now the SEA has been taped out successfully in 0.18μm 1P6M CMOS technology, the working frequency of SEA is 133MHz, the power is 962.26mW, and a 1024-bit RSA signature can be finished in 316.9μs with SEA.