Research Article
FPGA Implementation of Multistage Knapsack Public Key Cryptosystem
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 71 - Issue 19 |
| Published: June 2013 |
| Authors: Oday Abdul Lateef Abdul Ridha, Bassim Sayed Mohammed, Thamir Rashed Saeed, Jafar Wadi Abdul Sadah |
10.5120/12594-9247
|
Oday Abdul Lateef Abdul Ridha, Bassim Sayed Mohammed, Thamir Rashed Saeed, Jafar Wadi Abdul Sadah . FPGA Implementation of Multistage Knapsack Public Key Cryptosystem. International Journal of Computer Applications. 71, 19 (June 2013), 15-21. DOI=10.5120/12594-9247
@article{ 10.5120/12594-9247,
author = { Oday Abdul Lateef Abdul Ridha,Bassim Sayed Mohammed,Thamir Rashed Saeed,Jafar Wadi Abdul Sadah },
title = { FPGA Implementation of Multistage Knapsack Public Key Cryptosystem },
journal = { International Journal of Computer Applications },
year = { 2013 },
volume = { 71 },
number = { 19 },
pages = { 15-21 },
doi = { 10.5120/12594-9247 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2013
%A Oday Abdul Lateef Abdul Ridha
%A Bassim Sayed Mohammed
%A Thamir Rashed Saeed
%A Jafar Wadi Abdul Sadah
%T FPGA Implementation of Multistage Knapsack Public Key Cryptosystem%T
%J International Journal of Computer Applications
%V 71
%N 19
%P 15-21
%R 10.5120/12594-9247
%I Foundation of Computer Science (FCS), NY, USA
Abstract
This paper presents hardware implementation of multistage trapdoor knapsack public key cryptosystem which is primarily based on Merkle-Hellman scheme. So far, multistage knapsack is not broken and there has not been known a specific attack against this system. Modular multiplier is the critical and fundamental part of the hardware implementation. In this paper, Montgomery's multiplication algorithm is modified with great hardware reduction. An efficient and optimized architecturefor modular multiplication is proposed. Three stages knapsack public cryptosystem are implemented on DE2-115 FPGA development kit. The either implemented stages (encryption or decryption) take <1% of available FPGA resources. The required clock cycles for encryption process of a one stage is equal to the encryption key length plus one, whereas decryption process of a one stage requires twice decryption key length. The stages can be easy operated in pipeline to speedup cryptosystem operations.
References
- W. Diffie and M. Hellman : New direction in cryptography,IEEE Trans. Information Theory Vol. IT-22 pp. 644-654, 1976.
- R. C. Merkle and M. Hellman: Hiding information andsignatures intrapdoor knapsacks, IEEE Trans. InformationTheory Vol. IT-24, pp 525-530, 1978.
- B. Chor and R. L. Rivest : A knapsack type public keycryptosystembased on arithmetic in finite fields, IEEE Trans. Information Theory Vol. IT-34, pp901-909, 1988.
- L. Adleman:On Breaking Generalized Knapsack Public KeyCryptosytems, Proc. 15th Annual ACM Symposium onTheory of Computing, pp. 402-412,1983.
- A. M. Odlyzko:Cryptoanalytic attacks on the multiplicativeknapsack cryptosystem and on Shamir's fast signaturescheme, IEEE Trans. Information Theory Vol. IT-30, pp. 594-601, 1984.
- C. P. Schnorr and H. H. Horner: Attacking the Chor-Rivestcryptosystem by improved lattice reduction, J. ElectronicColloquium on Computational Complexity, ECCC Vol. 2, No. 26 pp. 1-12, 1995.
- M. K. Lai : Knapsack cryptosystems, the past and the future, available at http:// ww. ics. uci. edu/~ming/knapsack. html, 2001.
- M. S. Lee : Improved cryptanalysis of a knapsack-basedprobabilisticencryption scheme, J. Information Science 222,pp. 779-783, 2013.
- H. A. Hussain, J. W. A. Sada, S. M. Kalipha: New multistageknapsack public-key cryptosystem, Int. J. Systems ScienceVol. 22, No. 11 pp. 2313-2320, 1991.
- P. L. Montgomery: Modular multiplication without trialdivision, Math. Comput. Vol. 44, No. 170, pp. 519-521, 1985.
- G. D. Sutter, J. P. Deschamps& J. L. Iman'a: Modularmultiplication and exponentiation architectures for fast RSAcryptosystem based on digital serial computation, IEEETrans. On Industrial Electronics Vol. 58, No. 7 July 2011.
Index Terms
Keywords