SEA: A High-Performance Modular Long Integer Exponentiation Coprocessor

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.