Final EPSRC Report, Contract No: GR/S98160/02

New Approach to Data Encryption Using Two-dimensional New Transforms

Prof. S. Boussakta and Prof. M. Darnell

School of Electrical, Electronic and Computer Engineering

University of Newcastle upon Tyne, NE1 7RU

Summary

The introduction of computer networks and the widespread use of the internet, coupled with big advances in communications technology, have made it possible to trade and exchange information or send messages from the office or home to most places in the world. As the variety of data exchanged across a network has increased dramatically over the last few years, so the threat of its interception during transmission or storage has become a major concern. Algorithms which help prevent intercept and enhance data security are now of primary importance. These require novel, efficient and low-complexity encryption algorithms that can offer security for fast evolving communication applications which have grown in size and complexity, encompassing a wide diversity of business functions which must be secured against intrusion threats that are continually increasing in frequency and sophistication [1,2]. Most of existing symmetrical encryption algorithms operate mainly on fixed-size blocks and key lengths. These algorithms are not scalable and, though secure at this stage, may soon be challenged by sophisticated crypto analysis and the rapid increase in processor power and parallel processing technology [3, 4]. The consequence if those algorithms are broken is severe and the search for a viable replacement that can be trusted may take several years; hence, research in this area should be continuous and intensive. Therefore, the aim of this project is to develop a basis for utilizing cryptographic schemes based on advanced transform techniques in various applications for secure communications and data storage.

Therefore, the specific goals of this research are to develop new approaches to data encryption based on novel transforms. These include:

  1. Investigation and development of novel transform-based algorithms for data encryption.
  2. Development of suitable fast algorithms to speed up the process of encryption/decryption.
  3. Implementation of the new algorithms for different types of data.
  4. Extension of the theory to high dimensions for increased security.

Work carried out

The project was divided into four tasks: firstly new encryption algorithms were developed and tested. Secondly the study and development of fast algorithms for efficient implementation of the new encryption systems were carried out. This showed that the new approach can achieve high performance and allows the new algorithms to be applied in novel application areas. Thirdly the best implementations from the algorithms developed in Task 2 for encrypting different types of data were implemented and compared against existing procedures. The main emphasis was on the speed and complexity of the algorithm and its robustness against brute force attacks. The most promising algorithm designs were identified and simulated on general purpose computers, FPGAs and DSPs implementation.

Examples of encryption using this new approach

Example 1: As a simple example, consider the encryption of the following message,

Original data(pliantext: One of the aims of encryption is to ensure security by protecting data during transmission or storage.

Encrypted data (ciphertext): x¢¤ìmaøÌ¢SPCŠ¿8³7WWýœJrƒª’Ÿ`2f… {Õz6›.Ø¡8™ã삦‘žz»àÅrI¨38*Æøh”ä>y¢¤Ÿz¯åÀ

Decrypted data:

One of the aims of encryption is to ensure security by protecting data during transmission or storage.

However, if a third party tried to decrypt the data without proper knowledge of the key or tampered with it (even changing a single bit), decryption will lead to totally different data as shown below:

Decrypted data by taking the inverse transform ( a single bit has been changed):

V$þåî/ûÎeæÍÅ;xS—º}hUù®ß±ŠÀAbÉ¿ÿdS]‹—¼oE[ÏÏeŠü1N#®fàQܱٔ@Õ“>ñ¡®

Example 2: Assume a file “Hello, World!”needs to be encrypted through this system (for illustrative purposes, we use a small modulus 257 but for a secure system we could use a modulus of the order 232 or higher). The plaintext is padded with the “space” character to fill the block size of 16. Its ASCII presentation is:

P.T= (72,101,108,108,111,44,32,87,111,114,108,100,33,32,32,32). The user randomly selects a private key: U=(68,16,15,126,74,35,178,204,95,247,39,196,27,47,231,239). The Ciphertext is worked out as:

C.T= (20,35,207,141,54,151,89,133,8,105,137,144,181,76,140,32), where five round-keys are generated in the key expansion module for encryption and decryption. Translate that to characters C.T= ¶ # ¤ ì 6 ù Y à i ë É Á L î. The plaintext can be easily retrieved through the decryption processes. However, two special situations are shown here in order to show the robustness of this newly-developed cryptosystem.

  1. When changing one bit of the ciphertext, the decrypted plaintext is: PT’=(105,176,106,219,165,67,

75,144,58,117,141,68,103,210,4,201). Plaintext in Character: i░j█ÑCKÉ:uìDgÊ♦╔

  1. When changing one bit of the private key, the decrypted plaintext is: PT’=(112,190,171,199,71,54,

111,47,31,192,205,206,134,148,146,16). Plaintext in Character : p¥½ÃG6o/▼└═╬åöÆ►

The above decryption results show the avalanche effect and the completeness effect clearly; these are two properties that play important roles in the structure design of substitution-permutation encryption networks.

Implementation of the proposed approach for different types of data:

As planned in the project, several tests and examples are used to explain the nature and prove the validity of the proposed algorithms. Different files such as PDF, document, postscript files, video clips and various image formats have been encrypted and decrypted using the new approach successfully. The encrypted files also were tested using the file transfer protocol over wireless links. The files were successfully decrypted.

Also, the encryption system was implemented on different platforms i.e general purpose computers, parallel DSP systems using the Sharc-processors and FPGA. These algorithms were first implemented on a Pentium Processor 4 with speed of 2GHz and 256 MB RAM and compiled using DV-C++4940. The encryption speed is found to be very fast for most applications that run on general purpose computers and in most cases less than 1 Mbyte/secof data. For example, encrypting a file of 25.7 Mbytes takes 5.3 sec.

The proposed architectures in Figure 1 have been tested and implemented in FPGA using the Virtex-II family of devices. The proposed three architectures have different performances in terms of speed and area usage [13]. When comparing them, Architecture-III is the most efficient in terms of speed and throughput rate, achieving up to 7.89 Gbit /sec. The other two architectures have comparable speed performances. The three architectures also have comparable area usage performances, with Architecture-III using less area then the other two. Architecture-I is the most efficient in terms of using the logic in the chip for short sequences. Also the architecture, shown in Figure 2, has been tested and implemented in an FPGA chip achieving a throughput rate of up to 4.2 Gbits/sec. It uses 2.5N2 registers and is 50% efficient. The efficiency can be further increased to 100% at an extra cost of 0.5N2registers [14, 18, 19].

(a) (b) (c)

Figure 1. (a) Architecture-I,(b) II and (c) Architecture-III

Figure 2. ith round butterfly architecture

References:

  1. New challenges, New thinking, Security & Privacy, IEEE Computer Society, 2002.
  2. Hellman, M. E.:“An overview of public key cryptography”, IEEE Communications Magazine, May 2002.
  3. Courtois, T. C., Goubin, L.: “Open problems in multivariate cryptoanalysis”, STORK Cryptography workshop, November 2002, Belgium.
  4. Warren, D., S.: “AES seems weak. 2. Linear time secure cryotography.”Available at
  5. Boussakta, S. and Holt, A.G.J.: “Number theoretic transforms and their applications in image processing”, Advances in imaging and electron physics, 111, pp.1-90, 1999.
  6. Boussakta, S.:“Algorithms and development of the number theoretic and related fast transforms with applications”, PhD thesis, 1990.
  7. Alshibami, O., Boussakta, S., Aziz, M.: “Fast algorithm for the 2-D new Mersenne number transform’, ElsevierInternational Journal on Signal Processing, August 2001, Vol. 81, pp. 1725-1735.
  8. Ammar, B., Boussakta, S., Darnell, M. and Yang, Z.B.: “A proposal for simple symmetric key cryptosystem based on key-dependent S-box,” ISCTA’07 Proc., Ambleside, UK, July 2007.
  9. Shannon, C.: “Communication Theory of Secrecy Systems” Bell System Technical Journal, vol. 28, pp. 656-715, 1949.
  10. Massey,J. L.: “On the Optimality of SAFER+ Diffusion”, Second AES Candidate Conference, Rome, Italy, 22-23, March, 1999.
  11. Daemen, J.: and Rijmen, V.: ‘AES Proposal, AES algorithm submission’, September 3, 1999, available at
  12. Nyamweno, S., Boussakta, S., and Markarian, G.: “COFDM Encryption using AES”, International Symposium on Broadband Communications (ISBC’04), 12th-15th December, 2004, Harrogate, UK
  13. .Nibouche, O., Boussakta, S., and Darnell, M.: “A New architecture for radix-2 new Mersenne number transform”, IEEE International Conference on Communications (ICC 2006), Istanbul, Turkey, 11-15 June 2006
  14. Nibouche, O., Boussakta, S., Darnell, M.: “Pipeline architecture for the 2-D New Mersenne number transform vector radix algorithm”, submitted to IEEE Transactions on Signal Processing.
  15. S. Boussakta, O. Alshibami, and M. Aziz, “3-D Vector radix algorithm for the 3-D new Mersenne number transform”, IEE Proceedings.-Vis. Image Signal Process., April 2001, Vol. 148, 2001, pp.127-135
  16. Boussakta, S, Alshibami, O and Aziz, M: “Radix-222 algorithm for the 3-D discrete Hartley transform. IEEE Trans. Signal Process., SP-49 (12), 3145-56, Dec. 2001.
  17. Aziz, M.; Boussakta, S.; “Efficient residue reduction algorithm using DSP circular buffer registers.”, 15th International Conference on Digital Signal Processing, Cardif, 1 July007, PP.12-314.
  18. Nibouche, O., Boussakta, S., Darnell, M. , Benaissa, M.: “Algorithm and pipeline architectures for 2-D FFT and FFT-like transforms.”, submitted to Elsevier’s Signal Processing journal.
  19. Aziz, M.; Boussakta, S.: “Efficient 3-D parallel filtering algorithm”, 15th European Signal Processing Conference, Poznan, Poland, September 2007
  20. Patel, R.A., Benaissa, M., Boussakta, S.: “Fast modulo 2n-2(n-2)+1 additions: a new class of adders for RNS”, IEEE Transactions on Circuits and Systems-I, Regular papers, Vol. 54, No.6, June 2007.
  21. Patel, R.A., Benaissa, M., Boussakta, S.: “Efficient new approach for modulo 2n-1 addition in RNS”, IEE Proceedings on Computers and Digital Techniques, Volume 153, Issue 6, Nov. 2006. PP. 399 – 405.