A Novel methodology for Implementation RSA algorithm using FFT in Galois Field

  IJETT-book-cover  International Journal of Engineering Trends and Technology (IJETT)          
© 2015 by IJETT Journal
Volume-30 Number-2
Year of Publication : 2015
Authors : S.Syamkumar, Ch.Umasankar


S.Syamkumar, Ch.Umasankar"A Novel methodology for Implementation RSA algorithm using FFT in Galois Field", International Journal of Engineering Trends and Technology (IJETT), V30(2),67-74 December 2015. ISSN:2231-5381. www.ijettjournal.org. published by seventh sense research group

In the past decade, one of the most significant advances in cryptography has been the introduction of the first fully homomorphism encryption scheme (FHE). This advance resolved and opened the door to many new applications. Indeed, using a FHE one may perform an arbitrary number of computations directly on the encrypted data without revealing of the secret key. Thus an untrusted party, such as a remotely hosted server, may perform computations on behalf of the owner on the data without compromising privacy. This property of FHE is precisely what makes it invaluable for the cloud computing platforms today. A fully homomorphic encryption (FHE) scheme is envisioned as being a key cryptographic tool in building a secure and reliable cloud computing environment, as it allows arbitrarily evaluation of a cipher text without revealing the plaintext. However, existing FHE implementations remain impractical due to their very high time and resource costs. Of the proposed schemes that can perform FHE to date, a scheme known as FHE over the integers has the advantage of comparatively simpler theory, as well as the employment of a much shorter public key making its implementation somewhat more practical than other competing schemes. This paper presents the first hardware implementations of encryption primitives for FHE over the integers using FPGA technology. First of all, a super-size hardware multiplier architecture utilizing the Integer-FFT multiplication algorithm is proposed, and a super-size hardware Barrett modular reduction module is designed incorporating the proposed multiplier. Next, two encryption primitives that are used in two schemes of FHE over the integers are designed employing the proposed super-size multiplier and modular reduction modules.


1. G. D. Sutter, J.-P. Deschamps, and J. L. Imaña, ?Modular multiplication and exponentiation architectures for fast RSA cryptosystem based on digit serial computation, IEEE Trans. Ind. Electron., vol. 58, no. 7, pp. 3101–3109, Jul. 2011.
2. S. Yazaki and K. Abe, ?VLSI design of Karatsuba integer multipliers and its evaluation, IEEE Trans. Electron., Inf. Syst., vol. 128, no. 2, pp. 220–230, Feb. 2008
3. A. Schönhage and V. Strassen, ?Schnelle Multiplikation Großer Zahlen, Computing, vol. 7, no. 3, pp. 281–292, 1971.
4. P. Montgomery, ?Modular multiplication without trial division, Math.Comput., vol. 44, no. 170, pp. 519–521, 1985.
5. S. Yazaki and K. Abe, ?An optimum design of FFT multidigit multiplier and its VLSI implementation, Bull. Univ. Electro-Commun., vol. 18,no. 1, pp. 39–45, 2006.
6. J. W. Cooley and J. W. Tukey, ?An algorithm for the machine calculation of complex Fourier series, Math. Comput., vol. 19, no. 90, pp. 297–301,1965.
7. L. Jia, Y. Gao, and H. Tenhunen, ?A pipelined sharedmemory architecture for FFT processors, in Proc. 42nd IEEE Midwest Symp. Circuits Syst., vol. 2. Aug. 1999, pp. 804–807.
8. K. Kalach and J. P. David, ?Hardware implementation of large number multiplication by FFT with modular arithmetic, in Proc. 3rd Int. IEEENEWCAS Conf., Jun. 2005, pp. 267–270.
9. J. Solinas, ?Generalized mersenne numbers, Blekinge College Technol., Karlskrona, Sweden, Tech. Rep. 06/MI/006, 1999

Modular multiplication, Rivest–Shamir–Adleman (RSA) cryptosystem, very large scale integration architecture, FHE, GF polynomial.