大整数乘法器的FPGA设计与实现

大整数乘法是公钥加密中最为核心的计算环节,实现运算快速的大数乘法单元是RSA, ElGamal,全同态等密码体制中急需解决的问题之一。针对全同态加密(FHE)应用需求,该文提出一种基于Schönhage-Strassen算法(SSA)的768 kbit大整数乘法器硬件架构。采用并行架构实现了其关键模块64k点有限域快速数论变换(NTT)的运算,并主要采用加法和移位操作以保证并行处理的最大化,有效提高了处理速度。该大整数乘法器在Stratix-V FPGA上进行了硬件验证,通过与CPU上使用数论库(NTL)和GMP库实现的大整数乘法运算结果对比,验证了该文设计方法的正确性和有效性。实验结果表明,该方法实现的大整数乘法器运算时间比CPU平台上的运算大约有8倍的加速。     

基于FPGA的有限域NTT算法设计与实现

大数乘法是公钥加密系统中最为核心的模块,同时,也是RSA、全同态等加密方案里最耗时的模块,因此,快速实现大数乘法是急需解决的问题。64K点有限域NTT作为大数乘法器的关键组件,文中采用并行架构实现NTT的运算,运算中基本采用加法和移位操作,以保证实现大量的并行处理,提高了处理速度。该组件在Stratix-V FPGA上得到了实现,工作在123.78 MHz频率下,运行结果表明,在FPGA上的效率是CPU上运行速度的60倍。运行结果与GMP运算库进行比较,验证了有限域64K点NTT算法的正确性。     

大整数乘法器设计

本文提出了一种有符号大整数乘法的实现算法,该算法避免了部分积的符号扩展,使部分积之间的累加比较规则,易于VLSI实现.并且文中给出了该算法的一种逻辑实现结构,这种结构减少了乘法计算过程中进位传递加法的次数,加快了乘法计算的速度.     

使用数论变换的超快速傅里叶变换

本文证明用数论变换(NTT)能非常有效地计算离散傅里叶变换(DFT)值,而乘法次数可进一步减少。这是因为考虑数论变换和离散傅里叶变换的某些简单特性,把一个长度为P的离散傅里叶变换实乘总数减少到(P-1)。这样,每点所需实乘法次数还不到一次。适当选择变换长度和数论变换,每点     

用分治算法求大整数相乘问题的进一步分析

对利用分治算法解决大整数相乘问题作了进一步深入的研究和分析.在原来的分治算法的基础上,将输入规模为n的两个大整数各分成规模相等的k(2≤k≤n)部分,证明了通过恒等变形可将其乘积中的k²次乘法降为k(k+1)/2次;给出了计算两个大整数乘积的计算复杂度;证明了利用分治算法将两个大整数各分成规模相等的两部分来进行处理时的计算复杂度是最小的,进而表明利用分治算法将大整数各分成规模相等的两部分来进行处理是合理的.     

用于全同态加密的数论变换乘法蝶形运算优化及实现

全同态加密(FHE)可以真正从根本上解决云计算时将数据及其操作委托给第三方时的数据安全问题.针对全同态加密中占较大比例的大整数乘法运算优化需求,该文提出一种数论变换乘法蝶形运算的操作数合并算法,利用取模操作的快速算法,分别可将基16和基32运算单元的操作数减少到43.8%和39.1%.在此基础上,设计并实现了数论变换基32运算单元的硬件设计架构,在SMIC 90 nm工艺下的综合结果显示,电路的最高工作频率为600 MHz,面积1.714 mm2.实验结果表明,该优化算法提升了数论变换乘法蝶形运算的计算效率.     

一款RSA模乘幂运算器的设计与实现

通讯技术的高速发展需要更高性能的密码处理设备.本文介绍的RSA模乘幂运算器,采用蒙哥马利模乘法算法和指数的从右到左的二进制方法,并根据大整数模乘法运算和VLSI实现的要求进行改进,提供高速RSA模乘幂运算能力.该RSA运算器在其模乘法器中使用了进位保留加法器结构以避免长进位链.我们提出了信号多重备份的方法,解决大整数运算结构中关键信号广播带来的负载问题.     

采用数論变换和有限字长的变换域数字滤波

尽管离散付立叶变换(DFT)是在复数域定义的,然而数论变换(NTT)却是在有限域和环内运算的。这些NTT中的某些变换具有类似于快速付立叶变换(FFT)的快速变换结构,因而能用于快速数字信号处理。本文对采用NTT进行变换域信号处理的计算效果以及信噪此(SNR)性能作了研究。特别是,分析了有限字长(b≤16)和长变换长度对NTT滤波的影响。分析表明,对于短的字长或中到大的变换长度,NTT滤波比定点运算的FFT滤波能达到更好的SNR。最后,提出了一种具有单基或混合基快速变换结构的新的NTT。虽然这些NTT需要高效率地实现取模运算,然而对于在8≤b≤16范围内的任一给定的工作长度b,这些新的NTT的变换长度是最佳的。     

基于矩的无乘法离散傅立叶变换

提出了一种无乘法实现离散傅立叶变换(DFT)的新算法:通过模运算和泰勒展开,把DFT的计算转化为离散矩和常系数乘积的形式;然后,通过在二进制系统中进行比特运算和移位运算,把浮点乘积转化为定点的整数加法.离散矩可由全加法实现,因此新算法只涉及整数加法和移位运算.此外,为该算法设计出脉动阵列VLSI结构,并和现有结构进行了对比分析.分析结果表明新结构不涉及乘法运算,节约了硬件资源,加快了运算速度.该方法也可以推广到其他离散变换的计算.     

大整数模运算的软件实现方案

本文给出了一种基于Montgomery改进算法,以及变长滑动窗口算法的大整数模指数运算的软件实现方案,从加快模乘法运算速度和减少模乘法的运算次数两方面入手,快速、有效地解决了诸多密码算法中的大整数模乘运算问题。     

用于全同态加密的数论变换乘法蝶形运算优化及实现

全同态加密(FHE)可以真正从根本上解决云计算时将数据及其操作委托给第三方时的数据安全问题。针对全同态加密中占较大比例的大整数乘法运算优化需求,该文提出一种数论变换乘法蝶形运算的操作数合并算法,利用取模操作的快速算法,分别可将基16和基32运算单元的操作数减少到43.8%和39.1%。在此基础上,设计并实现了数论变换基32运算单元的硬件设计架构,在SMIC 90 nm工艺下的综合结果显示,电路的最高工作频率为600 MHz,面积1.714 mm²。实验结果表明,该优化算法提升了数论变换乘法蝶形运算的计算效率。     

A high-speed multiplier using a redundant binary adder tree

A 16-bit /spl times/ 16-bit multiplier for 2 two's-complement binary numbers based on a new algorithm is described. This multiplier has been fabricated on an LSI chip using a standard n-E/D MOS process technology with a 2.7-/spl mu/m design rule. This multiplier is characterized by use of a binary tree of redundant binary adders. In the new algorithm, n-bit multiplication is performed in a time proportional to log/SUB 2/ n and the physical design of the multiplier is constructed of a regular cellular array. This new algorithm has been proposed by N. Takagi et al. (1982, 1983). The 16-bit/spl times/16-bit multiplier chip size is 5.8 /spl times/ 6.3 mm/SUP 2/ using the new layout for a binary adder tree. The chip contains about 10600 transistors, and the longest logic path includes 46 gates. The multiplication time was measured as 120 ns. It is estimated that a 32-bit /spl times/ 32-bit multiplication time is about 140 ns.     

A low logic depth complex multiplier using distributed arithmetic

A combinatorial complex multiplier has been designed for use in a pipelined fast Fourier transform processor. The performance in terms of throughput of the processor is limited by the multiplication. Therefore, the multiplier is optimized to make the input-to-output delay as short as possible. A new architecture based on distributed arithmetic, Wallace-trees, and carry-lookahead adders has been developed. The multiplier has been fabricated using standard cells in a 0.5-μm process and verified for functionality, speed, and power consumption. Running at 40 MHz, a multiplier with input wordlengths of 16+16 times 10+10 bits consumes 54% less power compared to an distributed arithmetic array multiplier fabricated under equal conditions     

High speed multiplier using Nikhilam Sutra algorithm of Vedic mathematics

This article presents the design of a new high-speed multiplier architecture using Nikhilam Sutra of Vedic mathematics. The proposed multiplier architecture finds out the compliment of the large operand from its nearest base to perform the multiplication. The multiplication of two large operands is reduced to the multiplication of their compliments and addition. It is more efficient when the magnitudes of both operands are more than half of their maximum values. The carry save adder in the multiplier architecture increases the speed of addition of partial products. The multiplier circuit is synthesised and simulated using Xilinx ISE 10.1 software and implemented on Spartan 2 FPGA device XC2S30-5pq208. The output parameters such as propagation delay and device utilisation are calculated from synthesis results. The performance evaluation results in terms of speed and device utilisation are compared with earlier multiplier architecture. The proposed design has speed improvements compared to multiplier architecture presented in the literature.     

大数乘法器的设计与硬件实现

RSA算法是目前被认为可以实现安全通信的理想的公钥密码体制之一，其主要操作实际上是一系列基本的大整数模乘运算。本文对模乘部分的核心部件大数乘法器进行了研究，并给出平行四边形大数乘法器的设计思想与硬件实现方法。     

FDM调制解调中高速（I）FFT硬件设计

提出了一种64点，512点和1024点（I）FFT（（逆）快速傅里叶变换）的硬件实现方法，适合应用在正交频分复用（OFDM）系统中，实现时采用了16位精度的复数来表示输入输出数据。该算法在运算过程去除了所有的乘法器在运算过程中没有使用乘法器，使得运算速度得到较大地提高。     

N bit result integer multiplier with overflow detector

This study is designed to suggest an N bit result integer multiplier with overflow detector indicating an N bit multiplication result and overflow status with an N bit multiplier and multiplicand input. The overflow is determined by the lower N bit result of multiplication and the number of leading sign bits of the multiplier and the multiplicand     

A 286 MHz 64-b floating point multiplier with enhanced CG operation

This paper presents a high speed 64-b floating point (FP) multiplier that has a useful function for computer graphics (CG). The critical path delay is minimized by using high speed logic gates and limiting the stage number of series transmission gates (TGs). The high speed redundant binary architecture is applied to the multiplication of significands. This FP multiplier has a special function of “CG multiplication” that directly multiplies a pixel data by an FP data. This multiplier was fabricated by 0.5-μm CMOS technology with triple-level metal of interconnection. The active area size is 4.2×5.1 mm². The operating cycle time is 3.5 ns at the supply voltage of 3.3 V, which corresponds to the frequency of 286 MHz. Implementation of CG multiplication increases the transistor count only 4%. Also, CG multiplication has no effect on the delay in the critical path