# Public Key Cryptosystem based on Number Theoretic Transforms resisting brute force attack.

1. Introduction

As the progress of modern information technology is rapid, security is an important technique of many applications including electronic commerce, secure internet access and virtual private networks. To protect the transmitted data from eavesdropping by an adversary, the message should be disguised before sending it through an insecure communication channel. This is achieved by a cryptosystem. Specially designed mathematical algorithms can transform messages into some thing unreadable (encryption) and back (decryption).

The most popular and well defined security primary technique RSA algorithm proposed by Ronald L. Rivest et al  is based on modular exponentiation and the security of the system is based on the hard ness of integer factorization problem. In RSA the cipher text C is obtained for the plaintext message M [member of] [z.sup.*.sub.N] as C = [M.sup.e] mod N, where N is the product of two large prime numbers of same length, e is the public key chosen such that it is relatively prime with the Euler totient function [phi](N) and 1 < e < [phi](N). Plain text is obtained back by computing [C.sup.d] mod N, where 1 < d < [phi](N) is the secret key such that ed [equivalent to] 1 mod [phi](N). Taher ElGamal [4, 11] described a modular exponentiation based cryptosystem on the multiplicative cyclic group [Z.sup.*.sub.p] of the field [Z.sub.p] generated by [alpha] [not equal to] 1 with p to be a large prime number. To communicate secretly with A, entity B first gets A's public key (p, [alpha], [[alpha].sup.a] mod p), where a [member of] [Z.sup.*.sub.p]. Then B chooses a random integer k, 2 [less than or equal to] k [less than or equal to] p - 1, encrypts the message M as [delta] [equivalent to] M[([[alpha].sup.a]).sup.k] modp and sends the cipher text as ([gamma], [delta]), where [gamma] [equivalent to][ [alpha].sup.k] mod p. From the cipher text ([gamma], [delta]), entity A obtains the plaintext by finding the product [[gamma].sup.-a] [delta] mod p. The security of ElGamal cryptosystem is based on computational hard discrete logarithm problem. Breaking the ElGamal cryptosystem is equivalent to solving the DiffieHellman problem posed by W. Diffie and M. Hellman . Mukesh Kumar Singh  analyzed a public key cryptosystem with matrices and the security of system depends on the difficulty of solving a system of multivariate congruence equations over a specified commutative ring.

In this paper, a public key cryptosystem using Number theoretic transforms (NTT) [7, 8, and 12] over the ring of integer modulo a composite number n resistible against brute force attack is discussed. The key agreement in the proposed system is similar to that of ElGamal cryptosystem and the system has the advantage of high speed encryption and decryption rates compared with other public key cryptosystems based on exponentiation as the encryption and decryption algorithm involve only two modular exponentiation terms [[beta].sup.ab] and [[beta].sup.-ab].

The paper is organized such that, section (2) discusses the over view of the public key cryptosystem based on number theoretic transforms published in "International journal of Computational Mathematical Sciences", section (3) the brute force attack, section (4) the key agreement resistible against brute force attack, section (5) pubic key encryption and decryption algorithm, section (6) the security aspect and section (7) an illustration and (8) conclusion.

2. Over view of Public Key Cryptosystem Based on Number Theoretic Transforms

In this section the overview public key cryptosystem based on number theoretic transforms published in "International journal of Computational Mathematical Sciences" and the mathematical primitives behind the scheme are discussed.

2.1 Number Theoretic Transform (NTT) over a ring [Z.sup.*.sub.N]

Let {[h.sub.n]} be a sequence of m integers (m- point integer sequence), the parameters [beta], m are mutually prime with a composite number N, [mm.sup.-1] [equivalent to] 1 mod N, [[beta].sup.m] [equivalent to] 1 mod N and [m-1.summation over (k=0)][[beta].sub.uk] = O mod N, equivalently, [([[beta].sup.u] - 1), N)] = 1 for every u such that m/u is a prime. Then the NTT is defined as

[H.sub.k] [equivalent to] [m-1.summation over (n=0)] [h.sub.n][[beta].sup.nk] mod N, k = 0,1, 2,...,m -1

Inverse number theoretic transforms (INTT) is defined as

[h.sub.k] [equivalent to] [m.sup.-1] [m-1.summation over (n=0)] [H.sub.k] [[beta].sup.-nk]

2.2 Euler totient function

If N [greater than or equal to] 1 the Euler totient function [phi](N) is the number of positive integers not exceeding N, which are relatively prime to N.

2.3 Discrete logarithm problem

Given a finite cyclic group G of order n, a generator [alpha] of G and an element b [member of] G, find the integer x, 0 [less than or equal to] x [less than or equal to] n - 1 such that [[alpha].sup.X] = b mod n.

2.4 Integer Factorization problem

Given a positive integer n, find its prime factorization: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [p.sub.i]'s pair wise distinct primes and [e.sub.i] [greater than or equal to] 1.

2.5 Key Agreement

To communicate with each other securely the entities A and B agree the public parameter N = pq, where p and q are two large and distinct secret primes and the secret parameters are [phi](N) = (p - 1) (q - 1) and r = gcd(p - 1, q -1). They also agree the public parameters [beta], m assumed in section 2.1 and satisfying gcd([beta], [beta](N)) = 1.

* Entity A chooses a large secret key a [member of] [Z.sup.*.sub.N-1], computes the public key [[beta].sup.a] mod N and sends ([[beta].sup.a]mod N, x) to B, where x = ([[beta].sup.a] mod N)(r + [k.sub.1]) mod [phi](N) and [k.sub.1] is the least positive integer such that r + [k.sub.1] is relatively prime with [phi](N).

* Entity B chooses a large secret key b [member of] [Z.sup.*.sub.N-1] and computes the public key [[beta].sup.b] mod N and sends ([[beta].sup.b] mod N, y) to A, where y = ([[beta].sup.b] mod N) (r + [k.sub.2]) mod((N) and [k.sub.2] is the least positive integer such that r + [k.sub.2] is relatively prime with [phi](N). Obviously k = [k.sub.2].

* B computes ([[beta].sup.a] mod N) (r + [k.sub.1]) mod [phi](N) and checks whether it is equal to x.

* A computes ([[beta].sup.b] mod N)(r + [k.sub.2]) mod ((N) and checks whether it is equal toy.

2.6 Encryption

The plain text message is encoded as blocks of sequences {[h.sub.0], [h.sub.1], [h.sub.m-1]} of integers in [Z.sup.*.sub.N] and [h.sub.k] is encrypted as [H.sub.k] = [[beta].sup.ab] [m- 2.summation over (n=0)] [h.sub.n] [[beta].sup.nk] mod N for k = 0, 1,...,m-1.

2.7 Decryption

The plain text sequence {[h.sub.0], [h.sub.1],...,[h.sub.m-1]} is obtained from the cipher text {[H.sub.0], [H.sub.1],...,[H.sub.m-1]} by computing [h.sub.k] = [m.sup.-1] [[beta].sup.-ab][m-1.summation over (n=0P [H.sub.nk] mod N for k = 0, 1,...,m - 1.

3. Brute force attack

The keys used for encryption and decryption are [[beta].sup.ab] and [[beta].sup.-ab] respectively and [beta] satisfies [[beta].sup.m] = 1modN. In turn implies [([[beta].sup.-1]).sup.m] [equivalent to] 1 mod N. For a, b in [Z.sup.*.sub.N], the value of [[beta].sup.-ab] mod N is one among [[beta].sup.-1], [[beta].sup.-2], [[beta].sup.-3],...,[[beta].sup.-(m-1)]. As m, N and [beta] are kept public, an attacker may try for all possible values [[beta].sup.-1], [[beta].sup.-2], [[beta].sup.-3],..., [[beta].sup.-(m-1)] as decryption keys and recover the plain text.

3.1 Key Agreement resisting brute force attack

To achieve the key agreement resistible against brute force attack, Entities A and B agree the parameters N, [beta], m, r as in section (2.1).

* A sends the public key pair ([x.sub.1] = [[beta].sup.a] mod [phi](N), [x.sub.2] = [x.sub.1] (r + k) mod [phi](N)) to B, with a [member of] [Z.sup.*.sub.N] secret key of A and k is the largest positive integer less than [phi](N) relatively prime with [phi](N).

* B sends the public key pair ([y.sub.1] = [[beta].sup.b] mod [phi](N), [y.sub.2] = [y.sub.1](r + k) mod [phi](N)) to A, with b [member of] [Z.sup.*.sub.N] secret key of B. The keys used for encryption and decryption are [k.sub.1] = [[beta].sup.ab] mod [phi](N) and [k.sub.2] = [([[beta].sup.ab] mod [phi](N)).sup.-1] mod N respectively.

* Entity B verifies the public key of A by checking [x.sub.2] = [x.sub.1] (r + k) mod [phi](N).

* The entity A verifies the public key of B by checking the equation [y.sub.2] = [y.sub.1] (r + k) mod [phi](N).

* Because of the trapdoor integer factorization problem, it is computationally infeasible for an intruder to find the Euler totient function [phi](N). The intruder cannot impersonate as A or B by sending the public key as ([z.sub.1], [z.sub.2]), with [z.sub.1] = [[beta].sup.c]mod [phi](N), [z.sub.2] = [z.sub.1](r + k) mod [phi](N), where c is his/her secret key satisfying [z.sub.2] = [z.sub.1](r + k) mod [phi](N). Hence in this scenario the man in middle attack is impossible.

3.3 Encryption

The plain text message is encoded in to blocks of sequences {[h.sub.0], [h.sub.1],...,[h.sub.m-1]} of integers all less than N and each element of the sequence [h.sub.k] is encrypted as

[H.sub.k] = [k.sub.1] [m-1.summation over (n=0)] [h.sub.n][[beta].sup.nk] mod N for k = 0, 1,...,m - 1. The cipher text is {[H.sub.0], [H.sub.1], [H.sub.2] ... [H.sub.m-1]} can be represented in the matrix form as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3.4 Decryption

The plain text sequence {[h.sub.0], [h.sub.1],...,[h.sub.-1]} is obtained from the cipher text sequence {[H.sub.0], [H.sub.1], [H.sub.m-1]} by computing [h.sub.k] = [m.sup.-1] [k.sub.2] [m-1.summation over (n=0)] [H.sub.n] [[beta].sup.-nk] mod N for k = 0, 1,...,m - 1, where [k.sub.2] = [([[beta].sup.ab] mod [phi](N)).sup.-1] mod N. The decryption is represented as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

4. Data integrity

To achieve the service data integrity the hash value of the message may be considered as the first element of the first m-point integer sequence of the plain text and hence the first element of the first m-point integer sequence of the cipher text is the encryption of the hash value. The verifier after decrypting the cipher text can check, whether the first element is the hash value of the decrypted message.

5. Security of the Cryptosystem

It is assumed that no one modifies or shuffle the cipher text sequence. The encryption and decryption are done with the secret keys [[beta].sup.ab] mod ((N) and [([[beta].sup.ab] mod [phi](N)).sup.-1] mod((N) respectively. By the hardness of integer factorization problem given N, it is difficult to its factors p, q and in turn [phi](N). From the known public keys [[beta].sup.a] mod [phi](N) and [[beta].sup.b] mod [phi](N), it is computationally infeasible to find the secret keys [[beta].sup.ab] mod [phi](N), because of the integer factorization problem it is computationally infeasible to and Diffie Hellmann problem. Also it is not easy to find the secret keys a and b from known [[beta].sup.a] mod((N) and [[beta].sup.b] mod[phi](N), because of the hard discrete logarithm problem. Using the encryption and decryption algorithm an intruder may frame 2m equations AX [equivalent to] B mod N involving the unknown values [[beta].sup.ab][h.sub.0], [[beta].sup.ab][h.sub.1],...,[[beta].sup.ab][h.sub.m- 1]. Using these values it is impossible to find [[beta].sup.ab], [h.sub.0], [h.sub.1],...,[h.sub.m-1] separately and hence it is computationally infeasible to recover the secret keys used for encryption and decryption.

6. Numerical illustration

In this section the proposed algorithm is illustrated using Mathematica version 6. Entities A and B agree the public parameter N = 37 x 73 = 2701, [beta] = 673, [[beta].sup.-1] mod N = 1200, m = 9 and the secret parameters [phi](N) = 2592 and r = gcd(36,72) = 36.

6.1 Key agreement:

To communicate with each other secret A selects the secret key as a =1955 and sends the public key pair [x.sub.1] = 193, [x.sub.2] = 1571. B chooses b =1124 and computes the public key [y.sub.1] = 769, [y.sub.2] = 995. The keys for encryption and decryption are 2113 and 1989. Let the plaintext message "PUBLIC KEY CRYPTOSYSTEMS USING NTT". It is encoded as 1621 0212 0903 0011 0525 0003 1825 1620 1519 2519 2005 1319 0021 1909 1407 0014 2020. Assume that the hash value of the message as h(m, [phi](N)) = 1900, then the plaintext is encoded as two 9 point integer sequences{ 1900, 1621, 0212, 0903, 0011, 0525, 0003, 1825,1620} and{1519, 2519, 2005, 1319, 0021,1909, 1407, 0014, 2020}.

6.2 Encryption

The first sequence of integers

[h.sub.0] = 1621, [h.sub.1] = 0212, [h.sub.2] = 0903, [h.sub.3] = 0011, [h.sub.4] = 0525, [h.sub.5] = 0003, [h.sub.6] = 1825, [h.sub.7] = 1620, [h.sub.8] = 15 is encrypted as [H.sub.0] = 1217, [H.sub.1] = 1373, [H.sub.2] = 0838, [H.sub.3] = 1840, [H.sub.4] = 0799, [H.sub.5] = 2096, [H.sub.6] = 0793, [H.sub.7] = 0646, [H.sub.8] = 2225 using the encryption algorithm given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Similarly the sequence {1519, 2519, 2005, 1319, 0021, 1909, 1407, 0014, 2020} is encrypted as {0168, 1819, 0225, 0087, 2387, 0843, 1438, 0416, 0348}, in turn the entire cipher text is 1217, 1373, 0838, 1840, 0799, 2096, 0793, 0646, 2225, 0168, 1819, 0225, 0087, 2387, 0843, 1438, 0416, 0348

6.3 Decryption

The sequence {1217, 1373, 0838, 1840, 0799, 2096, 0793, 0646, 2225} is decrypted as {1900, 1621, 0212, 0903, 0011, 0525, 0003, 1825, 1620} using the decryption process given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Similarly the sequence of cipher text {0168, 1819, 0225, 0087, 2387, 0843, 1438, 0416, 0348} is decrypted as {1519, 2519, 2005, 1319, 0021, 1909, 1407, 0014, 2020}. After decryption the receiver decodes the message 1900 1621 0212 0903 0011 0525 0003 1825 1620 1519 2519 2005 1319 0021 1909 1407 0014 2020 to get the plain text "PUBLIC KEY CRYPTOSYSTEMS USING NTT". The receiver computes the hash value of the plaintext and compares with the first element of the first sequence. If they are equal then the receiver conforms that the data is not manipulated by an intruder during the transmission process of the message.

7. Conclusion

In this paper it is analyzed how the public key cryptosystem based on number theoretic transforms over a ring of integer modulo a composite number N is vulnerable to brute force attack. The solution to resist such attack is provided by modifying the key agreement. The security of the system is based on the solvability of multivariate linear congruence equations which is very complex, discrete logarithm problem and integer factorization problem. This cryptosystem also provides authentication by the key agreement and data integrity by assigning the first element of the m -point integer sequence as the hash value of the message. Impersonation is also not possible as it is computationally infeasible to find the Euler totient function and in turn man in the middle attack is avoided.

References

 Alfred Menezes J, Paul Van Oorchot C, Scott A Vanstone, "Hand book of Applied Cryptography", CRC Press, 1997.

 S.Cabay and T.P.L.Lam, "Congruence Techniques for the Exact Solution of Integer Systems of linear equations, ACM Transactions on Mathematical Software, Vol.3, No. 4, pp 386-397, Dec 1977.

 W.Diffie and M.Hellman, "New Directions in Cryptography ", IEEE Transactions on Information Theory, vol.IT-22,pp 472-492, 1976.

 Elsayed Mohammed, A.E.Emarah and KH.El-Shennawy, "A Blind Signature Scheme based on Elgamal Signature" Seventeenth National Radio Science Conference, Minufiya University, Egypt, Feb 2000.

 Jacques Patarin, "Hidden Field Equations and Isomorphism of Polynomials two new families of Asymmetric Algorithms", Eurocrypt'96, Springer Verlag, pp.33-48

 Mukesh Kumar Singh, "Public Key Cryptography with Matrices", Proceedings of the IEEE Workshop on Information Assurance, United States Military Academy pp 146-152, June 2004.

 H.J.Nussbaumer, "Fast Fourier Transform and Convolution Algorithms", Springer- Verlag, 1981.

 Ramesh C.Agarwal and C.Sidney Burrus, "Number Theoretic Transforms to implement Fast Digital Convolution", Proceedings of the IEEE, vol.63, No.4, 1975.

 Ronald L.Rivest, Adi Shamir, and Leonard M.Adleman, "A method for obtaining digital Signatures and Public-Key Cryptosystems", Communications of the ACM, vol 21, no2, pp.120-126, Feb 1978.

 Tom M. Apostol, "Introduction to Analytic Number Theory" Springer-Verlag 1976

 Taher Elgamal, "A public Key Cryptosystem and a Signature Scheme based on discrete Logarithms", IEEE transactions on information Theory, Vol.IT31, No4, July 1985.

 Vassil S. Dimitrov, Todor V. Cooklev and Borislav Donevsky, "Number Theoretic Transforms over the Golden Section Quadratic Field" IEEE Transactions signal processing, vol.43, No.8, August 1995.

C. Porkodi * and R. Arumuganathan (#)

Department of Mathematics and Computer Applications PSG College of Technology, Coimbatore- 641 004. Tamilnadu, India

Email: * porkodi_c2003@yahoo.co.in, (#) ran_psgtech@yahoo.co.in
COPYRIGHT 2009 Research India Publications
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2009 Gale, Cengage Learning. All rights reserved.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |