Performance analysis of Jordan Totient RSA (Jk-RSA) and NTRU

International Journal of Scientific & Engineering Research, Volume 5, Issue 3, March-2014 1099

ISSN 2229-5518

Performance analysis of Jordan Totient RSA (Jk- RSA) and NTRU

Sulaiman AlMuhteb1, Prof. Padmavathamma Mokkala2

1Research Scholar, Department of Computer Science, S.V.University, Tirupathi

*HOD, Department of Computer Science, S.V.University, Tirupathi

1samuh56@yahoo.com 2 prof.padma@hotmail.com

Abstract— Providing secure, efficient, reliable communication quickly is one of the significant facts of today. This work addresses the issues of performance analysis of RSA, J k -RSA and NTRU cryptographic algorithms and concludes which algorithm is faster and consumes less time for encryption and decryption. The NTRU algorithm was chosen because its security is based on the difficulty of factoring large numbers. J k - RSA where the modulus may have power of the two prime factors. The benefit of NTRU is lower computational cost for the decryption and signature primitives, provided that J k -RSA is used.

Index Terms— NTRU, RSA, Jordan Totient RSA , CRT, E-commercial, truncated polynomial ring and embedded security

——————————  ——————————

1. INTRODUCTION

RSA[1,2,3] algorithm invented by Rivest, Shamir and Adleman in 1978 is the most popularly used security algorithm in public key cryptosystems. It’s widely used to secure network traffic, email, e-commerce and e-business systems for applications in digital signatures and encryptions. Since RSA is based on arithmetic modulo of large numbers,
Implementing new Public Key Cryptosystems which was an extend variant analyzed in using the properties of Jordan Totient function Jk-RSA modulus so that it consists of r primes p1,p2,--------, pr instead of the traditional two primes p and q.

which requires large number of computations, fast implementation of RSA becomes vitally important for the performance of cryptosystems. On the other hand, software solutions are inherently flexible for all kinds of emerging

Compute N= ∏ pi = p1. p2 ............... pr

i =1

and

cryptosystems but comparatively slow. Hence it is necessary

JK (N) = n ∏

(1 − p− k )

= (pk − 1)(pk − 1)− − − − − (pk − 1)

to develop efficient methods to implement RSA over software platforms. Jk-RSA has been proposed to speed up RSA implementations; Jk-RSA[4,5] implementations require two major operations: squaring reduction and multiplication reduction. The benefit of J k-RSA is lower computational cost for the decryption and signature primitives, provided that the

= ∏ (

i=1

p k − 1)

p|k

1 2 r

CRT (Chinese Remainder Theorem) is used. Better performance can be achieved on single processor platforms, but to a greater extent on multiprocessor platforms, where the modular exponentiations involved can be done in parallel.
The NTRU (Number Theory Research Unit) cryptosystem [1-
3], patented by the company NTRU. NTRU is based on the algebraic structures of certain polynomail rings. NTRU has attracted considerable interest and is being considered by the efficient embedded security standards [4] and the IEEE P1363 study group for future public-key cryptography standards [5]. NTRU looks to be much quicker than its major opponents namely RSA, and subsequently has focused on the embedded markets (e.g., cell Phones and RFID chips) where processing power is scarcer.

2. IMPLEMENTATION

2.1. Jk - RSA CRYPTOSYSTEM:

Choose a random integer e< JK(N) such that gcd (e, Jk (N)) = 1.
Compute the integer d Which is the inverse of e i.e, ed = 1 (mod Jk(n))

2.2. Encryption Process

For a given plain text ‘m’ which belongs to ‘ZN ‘ the encryption algorithm is the same as that of the original RSA
Ciphertext c = me mod N

2.3. Decryption Process

In order to decrypt a cipher-text c:
For a given cipher text ‘c’ which belongs to ‘ZN ‘ the decryption algorithm is the same as that of the original RSA

International Journal of Scientific & Engineering Research, Volume 5, Issue 3, March-2014 1100

ISSN 2229-5518

Decryption message (plain text) m = cd mod N

2.4. Data flow

3. NTRU

NTRU[6-8] is based on the algebraic structures of certain polynomail rings. The name NTRU is short for N-th degree truncated polynomial ring, or in mathematical notation
with convolution multiplication and all polynomials in the ring have integer coefficients and degree at most N-1

NTRU is actually a parameterised family of cryptosystems; each system is specified by three integer parameters (N, p, q) which represent the maximal degree for all polynomials in the truncated ring R, a small modulus and
a large modulus, respectively, where it is assumed that N is prime, q is always larger than p, and p and q are coprime; and four sets of polynomials and (a polynomial part of the private key, a polynomial for
generation of the public key, the message and a blinding
value, respectively), all of degree at most .

3.1. Public key generation:

Sending a secret message from User A to User B requires the

generation of a public and a private key. The public key is known by both user A and B and the private key is only known by user B. To generate the key pair two polynomials f and g, with coefficients much smaller than q, with degree at most and with coefficients in {-1,0,1} are required. They can be considered as representations of the residue classes of polynomials modulo in R. The polynomial must satisfy the additional requirement that the inverses modulo q and modulo p (computed using the Euclidean algorithm) exist, which means that

and must hold. So when the chosen f is not invertible, user B has to go back and try another f.

Both f and are User-B’s private key. The public key h is generated computing the quantity
Example: In this example the parameters (N, p, q) will have the values N = 11, p = 3 and q = 32 and therefore the polynomials f and g are of degree at most 10. The system parameters (N, p, q) are known to everybody. The polynomials are randomly chosen, so suppose they are represented by

Using the Euclidean algorithm the inverse of f modulo p and modulo q, respectively, is computed

Which creates the public key h (known to both User A and B )

computing the product

3.2. Encryption

User-A, who wants to send a secret message to User-B, puts her message in the form of a polynomial m with coefficients
{-1,0,1}. In modern applications of the encryption, the message polynomial can be translated in a binary or ternary representation. After creating the message polynomial, Alice chooses randomly a polynomial r with small coefficients (not restricted to the set {-1,0,1}), that is meant to obscure the message.

This ciphertext hides User A’s messages and can be sent
safely to user-B.Example: Consider that User-A wants to send
a message that can be written as polynomial

and that the randomly chosen ‘blinding value’ can be expressed as

The cipher text e that represents her encrypted message to

User-B will look like

International Journal of Scientific & Engineering Research, Volume 5, Issue 3, March-2014 1101

ISSN 2229-5518

With User-B’s public key h the encrypted message e is computed:

3.3. Decryption

Anybody knowing r could compute the message m; so r must not be revealed by User-A. In addition to the publicly available information, User-B knows his own private key. Here is how he can obtain m: First he multiplies the encrypted message e and part of his private key f

By rewriting the polynomials, this equation is actually representing the following computation:

Instead of choosing the coefficients of a between 0 and q – 1 they are chosen in the interval [-q/2, q/2] to prevent that the original message may not be properly recovered since Alice chooses the coordinates of her message m in the interval [-p/2, p/2]. This implies that all coefficients of already lie within the interval [-q/2, q/2] because the polynomials r, g, f and m and prime p all have coefficients that are small compared to q. This means that all coefficients are left unchanged during reducing modulo q and that the original message may be recovered properly. The next step will be to calculate a modulo p:

Because.
Knowing b User-B can use the other part of his private key to recover User-A’s message by multiplication of b and

because the property was required for.
Example: The encrypted message e from User-A to User-B is multiplied with polynomial f
where User-B uses the interval [-q/2, q/2] instead of the interval [0, q – 1] for the coefficients of polynomial a to prevent that the original message may not be recovered correctly.
Reducing the coefficients of a mod p results in

which equals .
In the last step the result is multiplied with from User-B’s private key to end up with the original message m

Which indeed is the original message User-A has sent to User- B.

4. Analysis of NTRU and J k -RSA

Aspects	NTRU	Jk -RSA
Key Size	¼ of RSA of Same size	½ of RSA of Same size
Key Generation	100 times faster than Jk-RSA	50 times faster than RSA
Encryption (sec)	113 times faster than Jk-RSA	60 times faster than RSA
Decryption(sec)	112ms	160 ms
Computation power	Too less than compared to both	Average than compared to both
Speed	1300 times faster	200 times faster
Efficiency	Fastest	Average

NTRU cryptosystem is gaining more popularity slowly because it’s key size is very small, key generation, encryption speed, decryption speed are much faster and computation power requires very less, Operation speed is very fast, more efficient, consuming less space and more suitable for mobile devices[9,10].

5. CONCLUSI ONS:

In this research, we propose a NTRU and l Jk-RSA cryptography. From the results we obtained it is proved that NTRU gives more protection for the data from Jk-RSA . Only authorized user can retrieve the encrypted data and decrypt it. Even if anyone happens to read the data accidentally, the original meaning of the data will not be understood. Also we argued that the importance of security and privacy of data stored and retrieved. We utilize NTRU provides us efficient and secured data processing in the cryptography.

6. Future work:

International Journal of Scientific & Engineering Research, Volume 5, Issue 3, March-2014 1102

ISSN 2229-5518

Moreover, the NTRU cryptosystem could be applied to many areas where ever we can use J k-RSA and RSA cryptosystem, such as digital forensics, online voting or E- commercial, etc.

REFERENCE

[1] Ari Juels and Jorge Guajardo, http://www.rsa.com/rsalabs/staff/bios/ajuels/publications/kegv er/kv-extended.pdf

[2] RSA,http://www.cryptool.org/images/ct1/presentations/RSA/R

SA-Flash-en/player.html

[3] Online RSA example, http://www.gax.nl/wiskundePO/

[4] Prof. Padmavathamma , “New Variant Cryptosystem based on Jk- RSA Cryptosystem” published in the International Journal of Computer Engineering ,Vol.1 No.2 July-December 2009, pp 145 –

150.

[5] Prof. Padmavathamma , “New Variant Digital Signature schemes based on Jk-RSA Cryptosystem” published in the International Journal Computation Intelligence Research Application, July- December 2009.

[6] http://en.wikipedia.org/wiki/NTRUEncrypt

[7] J. Hoffstein, J. Pipher, J. H. Silverman, “NTRU: A Ring Based Public Key Cryptosystem,”Algorithmic Number Theory (ANTS III), Portland, OR, June 1998,J.P. Buhler (ed.),Lecture Notes in Computer Science 1423, Springer-Verlag, Berlin, 1998, pp. 267-288

[8] Xiaoyu Shen;Zhenjun Du; Rong Chen: “Research on NTRU Algorithm for Mobile Java Security”, in International Conference Scalable Computing and Communications; EighthInternational Conference on Embedded Computing (SCALCOM- EMBEDDEDCOM'09),2009.page(s):366–369

[9] Sameer Hasan Al-Bakri, M. L. Mat Kiah, A. A. Zaidan, B. B. Zaidan and Gazi MahabubulAlam: “Securing peer -to-peer mobile communications using public key cryptography: Newsecurity strategy”,International Journal of the Physical Sciences Vol. 6(4), pp.

930-938, 18, February, 2011

[10] John Welham: “Implementation and Comparison of XTR and NTRU Against Current Cryptographic Algorithms”, Master of Science Thesis, Department of Computer Science,University of Bristol, UK, September–2002

AUTHORS PROFILE

1Mr. Sulaiman AlMuhteb1, is a research Scholar from S.V.University Tirupati, AP, India he presented papers and attended international conferences. His areas of interest are Mobile technologies, Network security and Cloud computing.

2Prof. Dr. M.Padmavathamma is working as Head of Department of Computer Science, S.V.University, Tirupati, AP. India. She has vast experience of 26 years in teaching. She has guided 10 P.hD’s, 12 M.Phils and published 53 articles in International/National Journals. She has attended and chaired many International conferences conducted by various International organizations at various places around the world. Currently she is director of projects funded by UGC,DST India. Her Areas of interest are Network Security, Cloud computing and Data Mining.